ads:
Jodelson Aguilar Sabino
Otimização com
colônia de formigas aplicada à
programação de operações de locomotivas de manobras
Tese de Doutorado
Tese apresentada ao programa de pós-graduação
em Engenharia de Produção da PUC-Rio como parte
dos requisitos parciais para obtenção do título de
Doutor em Engenharia de Produção.
Orientador: Dr. José Eugênio Leal
Departamento de Engenharia Industrial – PUC, Rio de Janeiro, Brasil
Co-orientador: Dr. Thomas Günther Stützle
IRIDIA/CoDE – Université Libre de Bruxelles, Bruxelas, Bélgica
Rio de Janeiro
Março de 2008
PUC-Rio - Certificação Digital Nº 0321287/CA
ads:
Jodelson Aguilar Sabino
Otimização com colônia de formigas aplicada à
programação de operações de locomotivas de manobras
Tese apresentada como requisito parcial para obtenção do títu
lo de
Doutor pelo Programa de Pós-
Graduação em Engenharia da Produção
da PUC-Rio. Aprovada pela Comissão Examinadora abaixo assinada.
Prof. José Eugê
nio Leal
Orientador
Departamento de Engenharia Industrial - PUC-Rio
Prof. Marc Reimann
University of Warwick
Prof. Reinaldo Morabito Neto
UFSCar
Prof. Fabiano Mezadre Pompermayer
Consultor Autônomo
Prof. Madiagne Diallo
Departamento de Engenharia Industrial - PUC-Rio
Prof. Fernanda Maria Pereira Raupp
Departamento de Engenharia Industrial - PUC-Rio
Prof. José Eugênio Leal
Coordenador Setorial do Centro Técnico Científico - PUC-Rio
Rio de Janeiro, 31 de março de 2008
PUC-Rio - Certificação Digital Nº 0321287/CA
Todos os direitos reservados. É proibida a reprodução total ou parcial
do trabalho sem autorização da universidade, do autor e do orientador.
Jodelson Aguilar Sabino
Graduou-se em Matemática na UFES (Universidade Federal do Espírito
Santo) em 1986. Concluiu a pós-graduação em gerência de projetos em
2001. Em 2002 recebeu o Student Paper Award do RASIG - IFORMS
(Institute for Operations Research and Management Science). Concluiu
o Mestrado em Informática na UFES em 2004. Pesquisador convidado
do IRIDIA/CoDE na ULB (Université Libre de Bruxelles) em 2006.
Trabalha na Vale, na área de Tecnologia da Informação, desde 1987.
Atualmente é Gestor de Projetos de Tecnologia da Informação em
Vitória (ES), atuando no atendimento a demandas corporativas da área
de logística.
Ficha Catalográfica
Sabino, Jodelson Aguilar
Otimização com colônia de formigas aplicada à
programação de operações de locomotivas de manobras / Jodelson
Aguilar Sabino ; orientador: José Eugênio Leal ; co-orientador:
Thomas Günther Stützle. – 2008.
111 f. : il. (color.) ; 30 cm
Tese (Doutorado em Engenharia Industrial)–Pontifícia
Universidade Católica do Rio de Janeiro, Rio de Janeiro, 2008.
Inclui bibliografia
1. Engenharia industrial – Teses. 2. Otimização por
colônia de formigas. 3. Planejamento operacional de pátios
ferroviários. 4. Sistemas de transporte ferroviário. 5. Roteirização. I.
Leal, José Eugênio. II. Stützle, Thomas Günther. III. Pontifícia
Universidade Católica do Rio de Janeiro. Departamento de
Engenharia Industrial. IV. Título.
CDD: 658.5
PUC-Rio - Certificação Digital Nº 0321287/CA
ads:
Dedico este trabalho a Jacqueline, Thomas e Eric Sabino
PUC-Rio - Certificação Digital Nº 0321287/CA
Agradecimentos
Ao meu orientador, Prof. Dr. José Eugênio Leal, pelo apoio e estímulo em todas
as etapas da realização deste trabalho.
Ao meu co-orientador, Dr. Thomas Stützle e ao Dr. Mauro Birattari, pelas
contribuições relevantes e pela agradável companhia durante os doze meses em
que estive com eles.
Ao Dr. Marco Dorigo, por acreditar em mim e por disponibilizar pessoas e
recursos no momento certo.
Aos membros da banca examinadora, pela leitura crítica e minuciosa deste
trabalho e pelos comentários e sugestões encaminhados, os quais foram
fundamentais para a melhoria de sua versão final.
À Vale, pelo suporte e patrocínio.
Aos meus colegas da Vale, da PUC-Rio e do IRIDIA/CoDE pelas
colaborações e
pela companhia.
Aos meus amigos e familiares pelo apoio fundamental nas horas difíceis.
À minha esposa e filhos, a quem coube a tarefa mais difícil e mais importante de
suportar a minha ausência e me incentivar nos momentos em que eu estava
presente.
PUC-Rio - Certificação Digital Nº 0321287/CA
Resumo
Sabino, Jodelson Aguilar; Leal, José Eugênio; Stützle, Thomas Günther.
Otimização com colônia de formigas aplicada à programação de
operações de locomotivas de manobras. Rio de Janeiro, 2008. 111p. Tese
de Doutorado - Departamento de Engenharia Industrial, Pontifícia
Universidade Católica do Rio de Janeiro.
Este trabalho trata da modelagem e solução de um problema complexo da
vida real: o planejamento de operações de locomotivas de manobras. Sua principal
motivação é o desenvolvimento de uma aplicação prática para apoio ao
planejamento operacional de grandes pátios ferroviários, visando à utilização
eficiente de seus recursos. A questão fundamental considerada é a definição de
qual locomotiva deve executar quais manobras, em que ordem estas manobras
devem ser executadas e qual a rota a ser utilizada em cada manobra de modo a
reduzir os custos operacionais e aumentar a produtividade do sistema ferroviário.
Um pátio ferroviário de grandes proporções é usado como referência para
desenvolver um modelo matemático, baseado na teoria dos grafos, que representa
o problema proposto como um problema de coleta e entrega com frota
heterogênia, janelas de tempo e restrições de capacidade. O modelo desenvolvido
considera os principais elementos e variáveis do caso real, tais como o leiaute do
pátio, os acordos de nível de serviço e as restrições operacionais vigentes. A
técnica proposta para resolução do problema é Otimização Com Colônia de
Formigas, utilizando duas colônias de formigas. Os testes computacionais avaliam
diversas combinações de parâmetros e variantes do algoritmo proposto para
identificar a que produz os melhores resultados. O baixo consumo de recursos
computacionais e a qualidade das soluções obtidas mostram que o algoritmo
proposto é capaz de produzir soluções eficientes para problemas com proporções e
características reais.
Palavras-chave
Otimização com colônia de formigas, planejamento operacional de pátios
ferroviários, sistemas de transporte ferroviário, roteirização.
PUC-Rio - Certificação Digital Nº 0321287/CA
Abstract
Sabino, Jodelson Aguilar; Leal, José Eugênio; Stützle, Thomas Günther.
Otimização com colônia de formigas aplicada à programação de
operações de locomotivas de manobras. Rio de Janeiro, 2008. 111p. Tese
de Doutorado - Departamento de Engenharia Industrial, Pontifícia
Universidade Católica do Rio de Janeiro.
This thesis targets the modeling and solving of a real life complex problem:
the switch engine’s operational planning in railroad yards. Its main motivation is
the development of a practical application to help operational planners of large
railroad yards to achieve efficient resource utilization. The key issue addressed in
this research is the determination of which switch engine shall perform which
switch orders, in which sequence the switch orders shall be performed and which
is the route to follow while performing the switch orders in order to produce
operational savings and improve the railroad system productivity. A huge railroad
yard is regarded as a reference for designing a mathematical model, based on
graph theory, which represents the proposed problem as a pickup and delivery
problem with heterogeneous fleet, time windows and capacity constraints. The
model takes into consideration the main elements and variables of the real world
case like the yard layout, the service level agreements and the operational
constraints in effect. The proposed technique for solving this problem is based on
ACO – Ant Colony Optimization with two ant colonies. The computational tests
evaluate several parameter combinations and algorithm variants to identify the
one that leads to better results. The computational resource consumption and the
solution quality show that the proposed algorithm is able to produce efficient
solutions to realistic and large problem instances.
Keywords
Ant colony optimization, railroad yard operational planning, railroad
transportation systems, routing.
PUC-Rio - Certificação Digital Nº 0321287/CA
Sumário
1 Introdução 12
2 Apresentação do Problema 15
2.1. Conceitos e terminologia 15
2.2. Etapas do planejamento operacional de pátios ferroviários 21
2.3. Enunciado 29
2.4. Modelagem do Problema utilizando grafos 31
2.5. O PPOLM como um problema estático 44
3 Revisão da literatura 46
3.1. Planejamento operacional de pátios ferroviários 46
3.2. Problema de coleta e entrega 49
3.3. Otimização com Colônia de Formiga 52
4 Metodologia de solução do problema 58
4.1. Escolha dos algoritmos 58
4.2. Construção do plano de trabalho das locomotivas de manobras 59
4.3. Cálculo da atratividade 62
4.4. Regras de decisão 65
4.5. Regras de atualização de feromônio 66
4.6. Detalhes sobre a implementação do algoritmo YoYo 68
4.7. Determinação da rota de cada passo 75
5 Testes computacionais 82
PUC-Rio - Certificação Digital Nº 0321287/CA
5.1. O programa gerador de ordens de serviço 82
5.2. Preparação dos experimentos e métricas utilizadas 88
5.3. Resultados 91
6 Conclusão 99
7 Referências Bibliográficas 103
PUC-Rio - Certificação Digital Nº 0321287/CA
Lista de Figuras
Figura 1: Área de um pátio ferroviário em operação 16
Figura 2: Etapas da realização de uma manobra 18
Figura 3: Um controlador de Pátio em seu posto de trabalho.
Toronto, Ontário, Canadá. 20
Figura 4: Etapas do planejamento operacional de pátios
ferroviários 23
Figura 5: Grafo descritivo do leiaute da área B do pátio K 34
Figura 6: Correspondência entre os grafos G e G´ 36
Figura 7: Caminho de coleta e entrega O
e
no grafo G 37
Figura 8: Duas linhas adjacentes e o cálculo da distância entre
elas 39
Figura 9: Movimentos possíveis de uma formiga a partir do
estado i 54
Figura 10: Algoritmo ACO genérico, baseado em Maniezzo &
Carbonaro (1999) 55
Figura 11: Caminho de uma formiga com três passos
destacados 61
Figura 12: Algoritmo CompetAnts, conforme Reimann (2002) 62
Figura 13: Rotina ACO usada no algoritmo YoYo 70
Figura 14: Rotina RegraDecisão, usada na rotina ACO 71
Figura 15: Rotina SortearResposta, usada rotina RegraDecisão 72
Figura 16: Rotina Viável, usada rotina RegraDecisão 72
Figura 17: Matriz M (p+q, p+q, 2) de feromônios 74
Figura 18: Horizonte de planejamento dividido em intervalos 77
Figura 19: Matriz Z de alocação de pátio após movimento do
comboio κ 79
Figura 20: Comboio estacionado em A, pronto para se deslocar
até B. 79
Figura 21: Dimensões envolvidas no cálculo do tempo de
alocação das linhas 80
PUC-Rio - Certificação Digital Nº 0321287/CA
Figura 22: Pátio de descarregamento RRT1 utilizado nos testes
computacionais. 84
Figura 23: Diagrama de Fluxo de Dados do programa SOGY 86
Figura 24: Comparação da qualidade da solução para as
regras CME e RNK 92
Figura 25: Comparação das soluções CME e RNK variando
n_orders e m 94
Figura 26: Comparação das regras RNK e CME variando ρ e β 96
Figura 27: Número médio de iterações para CME e RNK
variando n_orders e m 97
Figura 28: Boxplot do tempo de CPU para todas as
combinações de parâmetros considerando n_orders=60 98
PUC-Rio - Certificação Digital Nº 0321287/CA
1
Introdução
A arte e a ciência têm seu ponto de encontro no método.
EDWARD BULWER-LYTTON
A resolução de problemas de otimização tem sido assunto de grande
interesse tanto no campo industrial quanto científico. As aplicações práticas se
multiplicam e se aperfeiçoam à medida que a teoria se expande e se aprimora, que
novos métodos, modelos e técnicas são divulgados e que os recursos
computacionais se tornam mais acessíveis. Mesmo em áreas tradicionais como
manufatura e logística, a aplicação das técnicas de otimização continua trazendo
retorno financeiro e propiciado também o desenvolvimento de novos modelos de
negócio com geração de vantagens competitivas.
Os resultados obtidos com a aplicação das modernas técnicas de otimização
e gerenciamento de processos têm despertado o interesse de estudiosos e peritos
em todo o mundo: O congresso internacional do INFORMS (Institute for
Operations Research and Management Sciences), realizado em Pittsburgh (PA),
EUA em novembro de 2006, contou com mais de 3.000 apresentações de
trabalhos teóricos e práticos aplicáveis em diversas áreas como manufatura,
suprimentos, e-business, leilões, biotecnologia, saúde e transporte.
A solução de problemas práticos usando técnicas de inteligência artificial e
matemática aplicada é muito mais que simplesmente o desenvolvimento de um
algoritmo. Em primeiro lugar, os problemas encontrados na vida real, geralmente
são muito complexos e envolvem a manipulação de uma extensa quantidade de
dados. Assim, a solução dos mesmos requer habilidade no emprego de técnicas
para a utilização eficiente dos recursos computacionais e conhecimento de
PUC-Rio - Certificação Digital Nº 0321287/CA
13
métodos matemáticos capazes de produzir um modelo que leve a uma solução
viável obtida dentro de um tempo razoável. Além disso, é indispensável a
comunicação com profissionais e cientistas da área de conhecimento específica do
problema abordado e de suas áreas afins, pois só assim é possível produzir uma
solução que explore as estruturas de dados, os processos e os métodos daquela
aplicação específica e, ao mesmo tempo, seja capaz de tratar as complicações
práticas do dia a dia. Por fim, é requerido conhecimento dos conceitos básicos de
economia e gerenciamento envolvidos no negócio, já que a busca da solução
ótima acaba por se converter em redução de custos, aumento da produtividade ou
melhoria da qualidade do produto final (Lubbecke, 2001).
Este trabalho trata de um problema prático que surge durante o
planejamento de operações de pátios ferroviários: Deseja-se determinar um plano
de trabalho de baixo custo para um conjunto de locomotivas de manobras, visando
atender ordens de serviço que devem ser executadas em um dado horizonte de
tempo. O referido plano deve especificar qual locomotiva deve executar qual
manobra, a ordem em que estas manobras devem ser executadas e o caminho que
cada locomotiva deve seguir durante a execução de seu plano de trabalho. Para
pátios com grande atividade, este problema pode se tornar complexo a tal ponto
que a experiência e a intuição de uma boa equipe de planejamento não sejam mais
suficientes para produzir boas soluções com regularidade. Além do número de
variáveis e restrições envolvidas, a meta de reduzir o custo fixo e o custo variável
conduz a um problema que por natureza tem dois objetivos, eventualmente
conflitantes, que precisam ser alcançados simultaneamente. Nesse contexto, surge
o interesse pelo desenvolvimento de uma ferramenta computacional que seja
capaz de sugerir soluções melhores que as obtidas manualmente pela equipe de
planejamento operacional do pátio.
A literatura em otimização de operações de pátios ferroviários é escassa,
principalmente no que diz respeito ao planejamento de trabalho das locomotivas
de manobras. Com efeito, este é um dos poucos trabalhos conhecidos nessa área,
sendo este o único, no melhor conhecimento do autor, que considera o conflito de
rotas das locomotivas de manobras em sua modelagem e resolução.
O restante deste documento é estruturado como segue: o capítulo 2 descreve
brevemente os conceitos e a terminologia da rotina operacional de pátios
PUC-Rio - Certificação Digital Nº 0321287/CA
14
ferroviários e, com base nesses conceitos, formaliza a definição do problema em
questão. O capítulo 3 identifica e classifica as referências mais importantes
utilizadas nos estudos que levaram à modelagem e à solução proposta. A
metodologia utilizada para resolução do problema é detalhada no capítulo 4,
juntamente com as particularidades e modificações necessárias nos métodos
tradicionais para derivar a solução proposta. Os testes computacionais e os
resultados obtidos são resumidos no capítulo 5. O capítulo 6 apresenta a
conclusão final, destacando as contribuições mais importantes deste trabalho e as
possibilidades de continuação do mesmo. O capítulo 7 encerra este documento
com as referências bibliográficas.
PUC-Rio - Certificação Digital Nº 0321287/CA
2
Apresentação do Problema
O pensamento só começa com a dúvida.
ROGER MARTIN DU GARD
Este capítulo apresenta a descrição por extenso e o enunciado formal do
problema de programação de operações das locomotivas de manobra de um pátio
ferroviário ou, simplesmente, PPOLM como será chamado neste trabalho. A
descrição por extenso do problema é precedida de uma breve apresentação dos
principais conceitos e da terminologia técnica específica de operações de pátios
ferroviários. A formulação matemática do problema é apresentada após a
definição dos elementos e conceitos necessários.
2.1.
Conceitos e terminologia
Os elementos mais importantes de uma ferrovia são os vagões, nos quais a
carga ou os passageiros são transportados; as locomotivas, que dão o poder de
locomoção aos vagões; os trilhos, que se agrupam para formar as linhas sobre as
quais as locomotivas e os vagões circulam; a tripulação, que opera o sistema
ferroviário e as cargas ou passageiros, que são transportados.
No sistema ferroviário, um conjunto de vagões com mesmas características
físicas ou operacionais é chamado de bloco. Um conjunto de blocos é puxado ou
empurrado por uma ou mais locomotivas e forma assim um conjunto maior de
blocos e locomotivas que é chamado de trem. Quando se fala sobre ordens de
serviço no contexto de pedidos de manobras a serem executadas em um pátio
ferroviário, um bloco é um conjunto de vagões que pode conter vagões com
origens ou tipos diferentes e que são agrupados de diversas formas visando
PUC-Rio - Certificação Digital Nº 0321287/CA
16
atender requisitos temporários específicos da operação do pátio. Visando
estabelecer claramente esta diferenciação entre blocos que trafegam na ferrovia e
os blocos que trafegam dentro dos pátios, este documento chama os blocos de
pátio de conjunto de vagões, ao invés de blocos.
Os trens se locomovem sobre trilhos que formam linhas que conectam
estações, pátios e terminais formando assim uma rede ferroviária. Terminais
ferroviários e outras localidades onde os trens são formados ou desmembrados são
chamados pátios ferroviários ou simplesmente pátios. Analisado sob o aspecto
físico, um pátio ferroviário (veja Figura 1) é um local onde a estrada de ferro se
expande em uma vasta área composta de linhas paralelas conectadas por
aparelhos de mudança de via (AMVs) e outros dispositivos ferroviários que
permitem a passagem de uma linha para outra.
Figura 1: Área de um pátio ferroviário em operação
Funcionalmente, os pátios são os nós da rede ferroviária onde os trens que
chegam são desmembrados e trens que saem são formados, vagões são
carregados, descarregados e transferidos de um trem para outro e onde ocorrem
algumas funções complementares tais como inspeção, estacionamento e
classificação de vagões, troca de tripulação, abastecimento de locomotivas e
PUC-Rio - Certificação Digital Nº 0321287/CA
17
manutenção e limpeza de vagões e locomotivas. Os pátios são divididos em áreas
formadas por conjuntos de linhas destinadas a atender cada uma destas funções
operacionais.
Locomotivas podem atuar em viagens, provendo tração para os trens que
transportam blocos entre pátios da ferrovia ou podem operar movimentando
conjunto de vagões dentro dos limites de um pátio. Neste último caso as
locomotivas são chamadas locomotivas de manobras.
Este trabalho trata da programação de operações das locomotivas de
manobra na rotina diária de um pátio ferroviário. Esta programação é feita em
ciclos regulares de curta duração (i.e. algumas horas) denominados horizontes de
planejamento.
Uma manobra é um transporte de um conjunto de vagões de uma linha de
origem para uma linha de destino dentro de um pátio. No contexto deste trabalho,
o conjunto formado por uma locomotiva de manobra mais os vagões acoplados a
ela será denominado de comboio. Uma ordem de serviço é um pedido de execução
de uma manobra.
A execução de uma manobra corresponde à seguinte seqüência de operações
que envolvem um conjunto de vagões, uma equipe de planejamento e operação e
uma locomotiva de manobra:
A viagem escoteira, que é o deslocamento da locomotiva sem
nenhum vagão acoplado, de sua posição inicial até o local de coleta
dos vagões;
O acoplamento, que é a operação de conectar vagões à locomotiva
de manobra;
O transporte, que é a operação de movimentação realizada pela
locomotiva de manobra ao transportar um conjunto de vagões de
uma linha de origem até uma linha de destino;
O serviço é uma fase opcional que eventualmente sucede o
transporte e ocorre quando a operação a ser executada com os
vagões no local de entrega requer a assistência da locomotiva de
manobras;
PUC-Rio - Certificação Digital Nº 0321287/CA
18
O desacoplamento que é a última fase de uma manobra e consiste na
separação dos vagões da locomotiva de manobra, tornando-a
disponível, a partir deste momento, para realizar outra manobra.
Figura 2: Etapas da realização de uma manobra
A Figura 2 mostra uma escala horizontal representando um intervalo de
tempo que vai das 06h10min até as 07h24min de um dia qualquer, onde estão
indicadas as etapas e os principais eventos ocorridos no decorrer de uma manobra
fictícia realizada durante este intervalo de tempo.
Em um dado instante dentro de um horizonte de planejamento, uma
locomotiva pode estar em uma, e somente uma, das seguintes situações:
1. Em modo de transporte, i.e., movendo um conjunto de vagões de sua
linha de coleta até a sua linha de entrega;
2. Em modo escoteira, ou seja, movendo-se sozinha, sem nenhum vagão
acoplado a ela. Isto ocorre, geralmente, quando a locomotiva de
manobra se desloca de sua posição inicial até a linha onde estão os
vagões a serem coletados na próxima manobra a ser realizada;
3. Em modo de espera, ou seja, ociosa e com seu motor ligado, estacionada
em uma das seguintes linhas:
Na linha de coleta e pronta para iniciar o acoplamento, mas
esperando a hora permitida para a coleta dos vagões. Isto
ocorre, por exemplo, quando uma locomotiva deve coletar
um conjunto de vagões na área de descarregamento e quando
PUC-Rio - Certificação Digital Nº 0321287/CA
19
ela chega à linha de coleta, a operação de descarregamento
ainda não foi concluída, sendo necessário, portanto, aguardar
o término do descarregamento;
Em uma determinada linha de seu caminho (incluindo a linha
de origem), aguardando que a linha seguinte seja liberada por
outra locomotiva ou comboio que esteja trafegando por ela;
Em sua última linha de entrega porque, de acordo com o
plano de trabalho definido para ela, depois daquela última
entrega não há mais manobras a serem executadas no
horizonte de planejamento atual;
Na linha de coleta ou na linha de entrega aguardando que um
técnico de operação ferroviária faça o acoplamento ou
desacoplamento de vagões à locomotiva.
4. Em modo desativada, isto é, em algum lugar fora ou dentro do pátio mas
parada e com o motor desligado. Isto ocorre, por exemplo, se de acordo
com o plano de trabalho em execução, a locomotiva não tem nenhuma
manobra a ser executada durante todo o horizonte de planejamento atual,
assim, ela fica parada e com o motor desligado até o início do próximo
horizonte de planejamento. Outro exemplo é quando a locomotiva está
em manutenção. Uma locomotiva em modo desativada pode,
teoricamente, não ser considerada como parte da frota que serve àquele
pátio em questão durante o horizonte de planejamento.
Uma manobra pode ser classificada por tipo, de acordo com a tarefa do pátio
à qual ela está relacionada. Assim, uma manobra pode ser de desmembramento de
trens que chegam, carregamento ou descarregamento de vagões, deslocamento
para inspeção para verificar a necessidade de limpeza de um conjunto de vagões
ou manutenção de um vagão específico, classificação para retirada de
determinados vagões de um conjunto ou ordenação dos mesmos de acordo com
um critério pré-estabelecido, de formação de trens que vão partir do pátio ou
simplesmente de deslocamento de vagões dentro do pátio, seja para levar ou trazer
das áreas de limpeza ou manutenção ou para organizar melhor os vagões no pátio,
de modo a simplificar a realização de tarefas planejadas para o futuro.
PUC-Rio - Certificação Digital Nº 0321287/CA
20
Os profissionais responsáveis pelas operações de um pátio ferroviário
normalmente se dividem em equipes de tripulação, de planejamento de operações,
de manutenção e de apoio administrativo. As funções mais importantes para o
contexto deste trabalho são:
O maquinista, que é a pessoa responsável pela condução da
locomotiva;
O técnico de operação ferroviária (TOF), que faz principalmente os
acoplamentos e desacoplamentos;
O planejador, que define as manobras a serem feitas a partir da
consolidação das demandas operacionais do pátio;
O controlador de pátios e terminais (Figura 3), que monitora as rotas
feitas pelas locomotivas de manobra dentro do pátio e define e
informa aos maquinistas as manobras a serem realizadas.
Figura 3: Um controlador de Pátio em seu posto de trabalho. Toronto, Ontário, Canadá.
Diferente da abordagem proposta em Crainic et al. (1980), que considera os
custos de operações de pátios estratificados pelo tipo da manobra, este trabalho
classifica os custos operacionais de um pátio ferroviário em custos fixos e custos
variáveis, seja qual for o tipo de manobra. Os custos fixos estão relacionados ao
custo de propriedade dos ativos do pátio, sendo a frota de locomotivas de manobra
o único ativo de interesse no contexto deste trabalho. Os custos variáveis estão
PUC-Rio - Certificação Digital Nº 0321287/CA
21
relacionados à utilização das locomotivas e consideram principalmente o consumo
de combustível, o desgaste ocorrido com o funcionamento das mesmas e o custo
da tripulação e demais profissionais envolvidos na realização das manobras.
Indicadores de desempenho são medidas utilizadas pelas equipes de gestão
do sistema ferroviário para planejamento, avaliação do nível de eficácia e
fornecimento de informações para entidades governamentais. O ciclo médio de
vagões é o indicador de desempenho com periodicidade de apuração mensal que
expressa, em dias, o intervalo entre carregamentos de vagões. A sua aplicabilidade
está na verificação de adequação dos planos de transporte, especialmente os
tempos alocados às operações de carregamento e descarregamento de vagões
(Diógenes, 2002). Albuquerque (2006) analisa alguns modelos para a avaliação do
desempenho logístico de sistemas ferroviários de carga e apresenta o ciclo médio
de vagões como o indicador mais significativo da produtividade do material
rodante.
2.2.
Etapas do planejamento operacional de pátios ferroviários
O planejamento de sistemas de transporte ferroviário envolve o tratamento
de diversos recursos humanos e materiais que se relacionam numa rede complexa
de decisões, interdependências e regras que afetam seus componentes de forma
distribuída (Crainic, 2002). Em seu trabalho voltado para ferrovias de transporte
público de passageiros, Lindner (2000) sugere uma decomposição hierárquica do
processo de planejamento ferroviário, estruturando-o em cinco etapas. Este
tratamento hierárquico pode ser utilizado como referência para modelagem
voltada para otimização dos processos e possibilita a divisão do planejamento em
tarefas mais simples de modo que a solução ótima encontrada para uma etapa
serve de entrada para o problema subseqüente. Bussieck ET al. (1997) apresentam
claramente o principal ponto positivo e negativo desta abordagem: uma vantagem
técnica evidente é que os problemas mais simples são mais fáceis de serem
resolvidos com os métodos e recursos computacionais disponíveis. Por outro lado,
não se espera encontrar uma solução ótima para o sistema como um todo ao final
do processo e isso é, certamente, uma desvantagem.
A classificação utilizada no presente trabalho foi apresentada em Assad
(1980) e define três níveis para o planejamento de transporte ferroviário:
PUC-Rio - Certificação Digital Nº 0321287/CA
22
estratégico, tático e operacional. Desenvolvida em um modelo baseado em
ferrovias de transporte de cargas, esta classificação se baseia no fluxo de
informações e a forma como são definidas as políticas e diretrizes do sistema
ferroviário. Sua simplicidade e clareza fizeram com que esta classificação fosse
adotada em muitos outros trabalhos como em Kraft (1998), Winter (1999), Crainic
(2002), Garcia & Gutierrez (2003), Sabino (2004) e Crainic & Kim (2007).
Na classificação de Assad, o planejamento Estratégico é de longo prazo.
Normalmente é um capítulo ou componente do planejamento da organização
como um todo e envolve a alta administração da empresa em decisões sobre
grandes investimentos de capital no decorrer dos próximos anos ou décadas.
Decisões tomadas no planejamento estratégico orientam políticas gerais de
desenvolvimento da empresa e envolvem elementos como o desenho da malha
ferroviária e sua evolução no tempo, a localização de seus pátios de manobras e
terminais, a aquisição de recursos como vagões e locomotivas e a definição da
carteira de serviços e as políticas de tarifação do sistema ferroviário.
O Planejamento Tático é de médio prazo e visa determinar, em um
horizonte de alguns meses, a forma com que devem ser feitas a alocação e
utilização dos recursos de modo a obter o melhor desempenho possível do sistema
como um todo. Neste nível de decisão os dados são sumariados, as políticas
abstraídas e as decisões são sensíveis apenas à variações consideráveis nos
parâmetros do sistema, tais como as alterações sazonais nas demandas de tráfego
(Crainic & Roy, 1988). Um exemplo típico de uma decisão tática é o desenho da
rede de serviços, incluindo determinação do tipo de serviço a ser oferecido,
programação de serviços (definição de prioridade, capacidade e freqüência dos
trens), definição de rotas de trens (i.e. definição de origem, destino, rota física e
paradas intermediárias) e reposicionamento da frota para uso no próximo período
de planejamento.
O Planejamento Operacional é de curto prazo, feito por unidades locais de
gerenciamento tais como gerentes de pátio e supervisores do centro de controle de
operações. Este nível de planejamento ocorre em um ambiente altamente
dinâmico em que fatores temporais têm um papel importante e a representação
detalhada dos veículos, da topologia e das atividades é essencial. São
PUC-Rio - Certificação Digital Nº 0321287/CA
considerados no nível operacional o planejamento de embarques, a programação
de veículos, a auditoria de
de baixo custo, garantindo que as demandas sejam atendidas no prazo e que o
impacto das variações no fluxo de operações seja minimizado. Um bom plano de
ope
rações de pátio, por exemplo, resulta em uma utilização eficiente das linhas de
pátio e das locomotivas de manobra, e esta eficiência é medida em função da
satisfação do cliente e dos custos associados.
trabalho propõe a decomposição do planejamento operacional de pátios
ferroviários em três etapas, como mostra a
resultado de entrevistas e validações feitas com o pessoal de c
técnicas do processo de planejamento operacional, tal qual é desenvolvido na
rotina diária de um pátio real.
Figura
seguem e está fundamentada na cronologia na qual as informações sobre as
manobras futuras se tornam disponíveis para a equipe de planejamento
operacional.
considerados no nível operacional o planejamento de embarques, a programação
de veículos, a auditoria de
O objetivo do planejamento operacional é garantir uma operação eficiente e
de baixo custo, garantindo que as demandas sejam atendidas no prazo e que o
impacto das variações no fluxo de operações seja minimizado. Um bom plano de
rações de pátio, por exemplo, resulta em uma utilização eficiente das linhas de
pátio e das locomotivas de manobra, e esta eficiência é medida em função da
satisfação do cliente e dos custos associados.
Em
adição
trabalho propõe a decomposição do planejamento operacional de pátios
ferroviários em três etapas, como mostra a
resultado de entrevistas e validações feitas com o pessoal de c
técnicas do processo de planejamento operacional, tal qual é desenvolvido na
rotina diária de um pátio real.
Figura
4
: Etapas do planejamento operacional de pátios ferroviários
A classificação proposta neste tr
seguem e está fundamentada na cronologia na qual as informações sobre as
manobras futuras se tornam disponíveis para a equipe de planejamento
operacional.
ESTRATÉGICO
considerados no nível operacional o planejamento de embarques, a programação
de veículos, a auditoria de
carga
O objetivo do planejamento operacional é garantir uma operação eficiente e
de baixo custo, garantindo que as demandas sejam atendidas no prazo e que o
impacto das variações no fluxo de operações seja minimizado. Um bom plano de
rações de pátio, por exemplo, resulta em uma utilização eficiente das linhas de
pátio e das locomotivas de manobra, e esta eficiência é medida em função da
satisfação do cliente e dos custos associados.
adição
à tradicional classificação hierárquica pr
trabalho propõe a decomposição do planejamento operacional de pátios
ferroviários em três etapas, como mostra a
resultado de entrevistas e validações feitas com o pessoal de c
técnicas do processo de planejamento operacional, tal qual é desenvolvido na
rotina diária de um pátio real.
: Etapas do planejamento operacional de pátios ferroviários
A classificação proposta neste tr
seguem e está fundamentada na cronologia na qual as informações sobre as
manobras futuras se tornam disponíveis para a equipe de planejamento
PLANEJAMENTO
ESTRATÉGICO
organização das
considerados no nível operacional o planejamento de embarques, a programação
carga
s e o g
O objetivo do planejamento operacional é garantir uma operação eficiente e
de baixo custo, garantindo que as demandas sejam atendidas no prazo e que o
impacto das variações no fluxo de operações seja minimizado. Um bom plano de
rações de pátio, por exemplo, resulta em uma utilização eficiente das linhas de
pátio e das locomotivas de manobra, e esta eficiência é medida em função da
satisfação do cliente e dos custos associados.
à tradicional classificação hierárquica pr
trabalho propõe a decomposição do planejamento operacional de pátios
ferroviários em três etapas, como mostra a
resultado de entrevistas e validações feitas com o pessoal de c
técnicas do processo de planejamento operacional, tal qual é desenvolvido na
rotina diária de um pátio real.
: Etapas do planejamento operacional de pátios ferroviários
A classificação proposta neste tr
seguem e está fundamentada na cronologia na qual as informações sobre as
manobras futuras se tornam disponíveis para a equipe de planejamento
PLANEJAMENTO
DE PÁTIOS
FERROVIÁRIOS
TÁTICO
1. Coleta e
organização das
tarefas
considerados no nível operacional o planejamento de embarques, a programação
s e o g
erenciamento de avarias.
O objetivo do planejamento operacional é garantir uma operação eficiente e
de baixo custo, garantindo que as demandas sejam atendidas no prazo e que o
impacto das variações no fluxo de operações seja minimizado. Um bom plano de
rações de pátio, por exemplo, resulta em uma utilização eficiente das linhas de
pátio e das locomotivas de manobra, e esta eficiência é medida em função da
satisfação do cliente e dos custos associados.
à tradicional classificação hierárquica pr
trabalho propõe a decomposição do planejamento operacional de pátios
ferroviários em três etapas, como mostra a
Figura
resultado de entrevistas e validações feitas com o pessoal de c
técnicas do processo de planejamento operacional, tal qual é desenvolvido na
: Etapas do planejamento operacional de pátios ferroviários
A classificação proposta neste tr
abalho está detalhada nos parágrafos que se
seguem e está fundamentada na cronologia na qual as informações sobre as
manobras futuras se tornam disponíveis para a equipe de planejamento
PLANEJAMENTO
FERROVIÁRIOS
OPERACIONAL
organização das
2. Identificação
das manobras
considerados no nível operacional o planejamento de embarques, a programação
erenciamento de avarias.
O objetivo do planejamento operacional é garantir uma operação eficiente e
de baixo custo, garantindo que as demandas sejam atendidas no prazo e que o
impacto das variações no fluxo de operações seja minimizado. Um bom plano de
rações de pátio, por exemplo, resulta em uma utilização eficiente das linhas de
pátio e das locomotivas de manobra, e esta eficiência é medida em função da
à tradicional classificação hierárquica pr
oposta por Assad, este
trabalho propõe a decomposição do planejamento operacional de pátios
Figura
4
. Esta decomposição foi
resultado de entrevistas e validações feitas com o pessoal de c
técnicas do processo de planejamento operacional, tal qual é desenvolvido na
: Etapas do planejamento operacional de pátios ferroviários
abalho está detalhada nos parágrafos que se
seguem e está fundamentada na cronologia na qual as informações sobre as
manobras futuras se tornam disponíveis para a equipe de planejamento
OPERACIONAL
2. Identificação
das manobras
considerados no nível operacional o planejamento de embarques, a programação
erenciamento de avarias.
O objetivo do planejamento operacional é garantir uma operação eficiente e
de baixo custo, garantindo que as demandas sejam atendidas no prazo e que o
impacto das variações no fluxo de operações seja minimizado. Um bom plano de
rações de pátio, por exemplo, resulta em uma utilização eficiente das linhas de
pátio e das locomotivas de manobra, e esta eficiência é medida em função da
oposta por Assad, este
trabalho propõe a decomposição do planejamento operacional de pátios
. Esta decomposição foi
resultado de entrevistas e validações feitas com o pessoal de c
ampo e análises
técnicas do processo de planejamento operacional, tal qual é desenvolvido na
: Etapas do planejamento operacional de pátios ferroviários
abalho está detalhada nos parágrafos que se
seguem e está fundamentada na cronologia na qual as informações sobre as
manobras futuras se tornam disponíveis para a equipe de planejamento
3. Definição da
programação de
locomotivas de
manobra
23
considerados no nível operacional o planejamento de embarques, a programação
O objetivo do planejamento operacional é garantir uma operação eficiente e
de baixo custo, garantindo que as demandas sejam atendidas no prazo e que o
impacto das variações no fluxo de operações seja minimizado. Um bom plano de
rações de pátio, por exemplo, resulta em uma utilização eficiente das linhas de
pátio e das locomotivas de manobra, e esta eficiência é medida em função da
oposta por Assad, este
trabalho propõe a decomposição do planejamento operacional de pátios
. Esta decomposição foi
ampo e análises
técnicas do processo de planejamento operacional, tal qual é desenvolvido na
abalho está detalhada nos parágrafos que se
seguem e está fundamentada na cronologia na qual as informações sobre as
manobras futuras se tornam disponíveis para a equipe de planejamento
3. Definição da
programação de
locomotivas de
manobra
PUC-Rio - Certificação Digital Nº 0321287/CA
24
2.2.1. A Coleta e organização das tarefas
A primeira etapa do planejamento operacional considera as seguintes
informações, as quais são normalmente conhecidas com 24 horas de antecedência:
Programação de Trens – Também conhecido como tabela de
horários de trem. O Plano de Trens, um dos principais produtos do
planejamento tático, influencia diretamente as operações do pátio
(e.g.: as manobras de recepção e formação são definidas em função
da programação de chegada e partida dos trens). A programação de
trens é a solução do problema de escalonamento de trens, o qual
identifica as rotas dos trens, suas freqüências semanais e suas tabelas
de horários de modo a minimizar o custo de transporte das cargas de
seus locais de origem até os seus locais de destino. A escala de trem,
depois de definida, é executada repetidamente a cada período pré-
definido (e.g.: uma semana) durante certo tempo (e.g.: três meses) ou
até que se faça uma revisão extraordinária. É importante notar que a
escala de tempo envolvida nestas atividades de planejamento é de
alguns dias a alguns meses;
Plano de Carregamento e Descarregamento – Trata-se de uma
lista contendo todas as operações de carregamento previstas para o
pátio para o horizonte de planejamento seguinte, normalmente de
algumas horas. No plano de carregamento é especificado o cliente, a
área do pátio onde deve ocorrer o carregamento e os detalhes
pertinentes aos vagões a serem carregados como, por exemplo, peso,
localização e número de identificação do vagão. As operações de
descarregamento compõem, analogamente, o Plano de
Descarregamento;
Uma tarefa, no contexto desta etapa, se refere a uma demanda operacional
de mais alto nível para o pátio, como por exemplo, formar um trem, descarregar
os vagões de um trem ou inspecionar um lote de vagões e em seguida realizar as
manutenções e limpezas necessárias. Uma tarefa não está associada a uma
locomotiva específica e normalmente requer a realização de várias manobras para
atendê-la. As informações consideradas sobre cada tarefa nesta etapa são o tipo de
PUC-Rio - Certificação Digital Nº 0321287/CA
25
tarefa a ser executada, o número de vagões envolvidos, as áreas de origem e
destino para cada operação, o tipo de carga e informações sobre o cliente a ser
atendido. Eventualmente saber-se-á a localização dos vagões a serem
considerados na tarefa e alguma informação sobre quando a tarefa deverá ser
executada.
Nesta etapa não há restrições a serem consideradas nem otimização a ser
feita. O mais importante é certificar-se que todas as tarefas a serem executadas no
horizonte de planejamento em questão foram consideradas e que todos os dados
implícitos foram tratados ao ponto de se transformarem em informações
estruturadas o bastante para serem manipuladas nas etapas seguintes. Por
exemplo, as seguintes informações sobre prazos vão determinar, posteriormente, o
horário mais cedo ou mais tarde possível para realizar as manobras
correspondentes a uma tarefa:
O prazo para conclusão da tarefa de modo a atender o nível de
serviço contratado com os clientes;
O horário mais cedo que a tarefa pode iniciar, considerando o
horário de término de alguma outra tarefa que seja pré-requisito
desta.
Ao contrário das outras duas etapas do planejamento operacional, que serão
apresentadas a seguir, esta primeira etapa não é um processo de tomada de
decisão, mas simplesmente uma coleta e classificação de dados. O produto que
deve ser entregue como resultado desta etapa será chamado neste documento de
lista das tarefas e constitui-se numa compilação sistemática, classificada em
ordem cronológica, de todas as operações com execução prevista para o horizonte
de planejamento dado.
Na prática, parte das tarefas programadas para o pátio é composta de
informações extemporâneas que chegam pelos meios de comunicação tradicionais
(e.g. e-mail, fax, telefone) e a outra parte consiste de informações obtidas através
de interfaces com sistemas de informações já existentes para a gestão dos
processos que geram demandas para o pátio.
A lista das tarefas é uma fonte de informação muito importante para vários
processos de planejamento e de avaliação no contexto da ferrovia. Por exemplo,
PUC-Rio - Certificação Digital Nº 0321287/CA
26
esta lista pode ser utilizada no planejamento tático, já que ele fornece indicações
sobre a utilização dos recursos do pátio em médio prazo (e.g.: linhas, locomotivas
de manobras e demanda por equipagem em cada área do pátio considerando o
plano de trens e as rotinas de carregamento e descarregamento atuais).
2.2.2.Identificação das Manobras
A segunda etapa do planejamento operacional do pátio considera todas as
tarefas planejadas e não planejadas e as manobras herdadas do horizonte de
planejamento anterior. Nesta etapa, o planejador de pátio elabora a lista completa
de todas as manobras necessárias para o próximo horizonte de planejamento o
qual compreende algumas horas. Espera-se que esta etapa esteja concluída alguns
minutos antes do início do horizonte de planejamento ao qual ela se refere, de
modo a permitir a execução das tarefas da terceira etapa antes do início do
referido horizonte de planejamento.
Nesta segunda etapa também é necessário considerar o horário limite para
início e término de cada manobra e o tempo máximo permitido de atraso para
começo e fim da mesma, conforme acordo de nível de serviço firmado com o
cliente. Em caso de atraso, o contrato com o cliente normalmente prevê um valor
em moeda corrente que representa a penalidade a ser paga, caso as operações de
carregamento ou descarregamento excedam este atraso máximo permitido. Neste
caso, os limites acordados e os valores das penalidades previstas devem ser
considerados como restrições.
As tarefas consideradas nesta etapa podem ser classificadas da seguinte
forma:
Tarefas planejadas: são todas as tarefas que constam na lista das
tarefas, ou seja, aquelas identificadas na etapa anterior;
Tarefas não planejadas: são todas as operações de pátio que
ocorrerão no próximo horizonte de planejamento, mas que não foram
consideradas na etapa anterior de construção da lista de macrotarefas
porque elas não eram conhecidas naquele momento. Este grupo
inclui as tarefas surgidas pouco tempo antes do início da segunda
etapa de planejamento, como, por exemplo, pedidos de levar ou
trazer vagões para manutenção ou limpeza. Neste grupo também se
PUC-Rio - Certificação Digital Nº 0321287/CA
27
incluem algumas demandas imprevisíveis, extemporâneas, urgentes
ou imprecisas, eventualmente vindas diretamente do próprio cliente
como um pedido especial;
Tarefas herdadas do horizonte de planejamento anterior são as
manobras atrasadas ou postergadas do horizonte de planejamento
anterior. Estas tarefas são muito bem detalhadas e apresentadas na
forma de uma lista de manobras a ser executadas no decorrer do
horizonte de planejamento que está sendo tratado.
O objetivo da segunda etapa do planejamento operacional é identificar
todas as manobras necessárias para realizar as operações de pátio que serão
realizadas no horizonte de planejamento em questão, especificando:
Linha de origem;
Linha de destino;
Quantidade de vagões;
Peso do conjunto de vagões a ser deslocado;
Janelas de tempo para realização da manobra, ou seja, os horários
mais cedo e mais tarde possíveis para coletar e para entregar os
vagões a serem transportados;
Identificação da manobra que é pré-requisito para a manobra em
questão (se houver).
Esta lista deve incluir as manobras de desmembramento, carregamento e
descarregamento, classificação, envio e retorno de vagões para limpeza e
manutenção, inspeção, além das manobras dos seguintes tipos:
Manobras implícitas de puxar vagões do início de uma linha e deixá-
los em outra linha para tornar acessíveis vagões que estão
localizados atrás destes.
Manobras de reposicionamento de vagões para tornar mais rápidas
manobras futuras. Em geral este tipo de manobra é uma demanda do
plano de distribuição de vagões vazios no pátio e ou do plano de
classificação dos vagões que estão na área de estacionamento.
PUC-Rio - Certificação Digital Nº 0321287/CA
28
Manobras especiais de levar locomotivas escoteiras para locais como
área de abastecimento ou troca de equipe.
O recurso mais importante na etapa de identificação das manobras são as
linhas do pátio. Deseja-se monitorar a ocupação de linhas e definir a seqüência na
qual estas operações devem ocorrer de modo a minimizar gargalos de alocação no
decorrer das manobras planejadas para o horizonte de planejamento em questão. É
importante notar que o estado de ocupação das linhas do pátio não é uma variável
binária que simplesmente define se a linha está ocupada ou não. Pode ser que uma
linha esteja parcialmente ocupada de tal modo que, embora existam vagões
estacionados nela, outros vagões possam ser adicionados sem que a capacidade da
linha seja excedida.
O processamento da etapa de identificação das manobras deve manter linhas
desocupadas o bastante para acomodar os vagões nas áreas de pátio de destino das
manobras previstas para o futuro. Para tanto, é preciso explorar a flexibilidade das
janelas de tempo e acompanhar o estado de alocação das linhas de cada área do
pátio com o passar do tempo, garantindo que os conjuntos de vagões caibam nas
linhas de destino das manobras que os envolvem.
2.2.3.Definição do plano de trabalho das locomotivas de manobras
Esta é a última das três etapas e é executada pelo controlador de pátio. O
principal dado de entrada para esta etapa é a lista produzida na etapa de
identificação das manobras contendo todas as manobras a serem executadas.
O objetivo desta etapa é definir qual locomotiva deve executar qual
manobra (alocação) e também a ordem de execução destas manobras
(seqüenciamento) de modo a não violar nenhuma restrição operacional (e.g.:
janela de tempo ou capacidade da locomotiva para movimentar o peso do bloco)
e, ao mesmo tempo, minimizar o custo operacional do pátio. Para executar esta
etapa do planejamento, é necessário fornecer informações sobre o leiaute do pátio
e sobre as locomotivas de manobra disponíveis nele e enumerar detalhadamente
todas as manobras a serem realizadas durante um horizonte de planejamento
especificado.
PUC-Rio - Certificação Digital Nº 0321287/CA
29
É importante observar que as manobras implícitas, de reposicionamento e
manobras especiais devem ser identificadas na segunda etapa e especificadas
explicitamente como dado de entrada desta etapa.
O objetivo de redução do custo operacional da etapa 3 equivale,
indiretamente, à redução das seguintes grandezas:
(a) O tempo total de realização de todas as manobras, incluindo o
tempo de espera caso haja conflito de uso de uma mesma linha por
duas locomotivas de manobra, o qual é diretamente proporcional
ao custo variável;
(b) A quantidade de locomotivas necessárias para realizar todas as
manobras da lista, a qual é o componente do custo fixo;
Vale notar que ao reduzir o tempo total para realização de todas as
manobras reduz-se o tempo de permanência dos vagões no pátio, o que implica
diretamente na redução do ciclo médio de vagões. Por outro lado, a redução da
quantidade de locomotivas necessárias, se praticada consistentemente por um
longo tempo, pode resultar em uma recomendação de redução do número de
locomotivas necessárias para a operação do pátio.
Este trabalho é dedicado à modelagem e ao desenvolvimento de uma
ferramenta computacional de apoio à decisão para a terceira etapa do
planejamento operacional de pátios ferroviários.
2.3.
Enunciado
O PPOLM é, na verdade um problema de otimização combinatória que
surge na terceira etapa do planejamento operacional de pátios ferroviários e seu
enunciado, por extenso, pode ser redigido como segue.
Dadas as seguintes informações sobre o pátio:
1. Leiaute do pátio, incluindo comprimento das linhas;
2. Lista de manobras a serem executadas, incluindo detalhes como
origem, destino e vagões a serem transportados;
PUC-Rio - Certificação Digital Nº 0321287/CA
30
3. Lista das locomotivas de manobra disponíveis, incluindo
informações como a localização inicial e capacidade de cada uma.
Deseja-se encontrar uma sugestão de:
1. Uma programação para as locomotivas de manobra, i.e., a definição
de quais ordens de serviço devem ser executadas por cada
locomotiva e a seqüência na qual cada locomotiva deve executar
suas ordens de serviço;
2. Uma rota completa a ser seguida por cada locomotiva na execução
de suas ordens de serviço, considerando a programação sugerida
de tal modo que nenhuma das restrições operacionais do pátio seja violada e que o
custo operacional da programação e da rota sugeridas seja mínimo.
As restrições mais importantes a serem consideradas são:
(a) Cada ordem de serviço pode ter a si associada janelas de tempo, que
especificam o horário mais cedo e mais tarde possível para coletar e
para entregar os vagões a serem transportados.
(b) Todas as ordens de serviço planejadas devem ser executadas, ou
pelo menos iniciadas, durante o Horizonte de planejamento;
(c) Nem toda locomotiva pode executar qualquer manobra. O peso total
do conjunto de vagões a ser movido não pode ser maior do que o
peso máximo que a locomotiva é capaz de puxar ou empurrar.
(d) Certas ordens de serviço podem ter outra como pré-requisito. Isto
ocorre, por exemplo, quando uma seqüência de operações deve ser
realizada com um mesmo conjunto de vagões ou quando o conjunto
de vagões a ser movido se encontra atrás de outros vagões que,
portanto, precisam ser movidos antes que a locomotiva tenha acesso
aos vagões referenciados naquela ordem de serviço;
Neste contexto, uma boa sugestão significa uma solução de custo
operacional mínimo.
PUC-Rio - Certificação Digital Nº 0321287/CA
31
2.4.
Modelagem do Problema utilizando grafos
Este item apresenta a definição dos elementos envolvidos no PPOLM
baseado em Teoria de Grafos (Diestel, 2005). Estas definições são utilizadas
primeiramente para a apresentação do enunciado formal do problema e depois são
referenciadas como suporte para explanações posteriores.
2.4.1.
Locomotivas e ordens de serviço
Seja um Horizonte de Planejamento
h
∆
de duração h que se inicia no
momento h
s
e termina no momento h
f
(de tal modo que h = h
f
– h
s
).
Seja E o conjunto formado por todas as locomotivas de manobra disponíveis
no pátio durante o horizonte de planejamento
h
∆
. Cada locomotiva e tem a si
associado um peso máximo q
e
que ela é capaz de puxar ou empurrar e as linhas do
pátio onde ela se encontra no início e no final do Horizonte de Planejamento, as
quais serão chamadas de
e
+
e
e
−
respectivamente.
Seja R um conjunto de ordens de serviço que devem ser executadas durante
o intervalo
[ , ]
s f
h h h
∆ =
. Associada a cada ordem de serviço r em R existe um
conjunto de vagões com um peso total w
r
e comprimento total y
r
que precisa ser
coletado na linha
r
+
e entregue na linha
r
−
, ambas localizadas em um pátio
ferroviário. O instante
r
t
+
em que os vagões serão coletados na linha
r
+
deve estar
dentro de um intervalo de tempo
[ , ]
r r
s f
r t t
+ +
+
∆ =
e a hora de entrega
r
t
−
deve
estar dentro do intervalo de tempo
[ , ]
r r
s f
r t t
− −
−
∆ =
. Este dois intervalos de tempo
são chamados janela de tempo de coleta e janela de tempo de entrega
respectivamente.
Uma locomotiva se desloca pelo pátio a uma velocidade s
e
que varia
principalmente de acordo com:
A sua capacidade de tração;
O peso que está sendo puxado ou empurrado (quando a locomotiva
trafega escoteira, este peso é o próprio peso da locomotiva).
PUC-Rio - Certificação Digital Nº 0321287/CA
32
As restrições de segurança ou operacionais da linha por onde passa a
locomotiva. Por exemplo, uma restrição de segurança pode limitar a
velocidade de deslocamento em certas linhas do pátio ou uma
locomotiva pode ter que parar durante o seu percurso e esperar até
que a linha adiante seja desocupada por um comboio que por ela
esteja trafegando.
Da resistência ao movimento para o trecho considerado no
deslocamento. Segundo Castello Branco & Ferreira (2000), esta
resistência depende de vários fatores tais como atrito, características
da via permanente (resistência de curvas e rampas), ventos
(principalmente ventos laterais) e a avaliação quantitativa destes
fatores tem sido objeto de estudos desde o início da ferrovia, todavia,
a menos de algumas poucas revisões de termos ocorridas ao longo de
décadas, as fórmulas propostas por W. J. Davis em 1926, conhecidas
como Fórmulas Davis continuam sendo usadas até os dias de hoje e
consideradas boas aproximações.
Dos fatores relacionados acima, os mais relevantes são a capacidade de
tração da locomotiva e o peso dos vagões a serem transportados, já que as
locomotivas de manobras circulam em velocidades relativamente baixas e os
pátios em geral não costumam ter quantidade considerável de aclives, declives e
curvas.
2.4.2.
Grafo de ordens de serviço
Seja
( , )
G V A
=
um grafo orientado, ponderado nos arcos, onde o conjunto
V de seus nós é formado por todas as linhas lógicas do pátio que possam ser o
local de coleta ou entrega de alguma manobra ou ainda a localização inicial de
alguma das locomotivas do conjunto E. Os nós
v
deste grafo são conectados por
arcos
a
em
A
que denotam a existência de um caminho conectando os nós
i
e
j
de tal forma que a locomotiva de manobras pode perfazer este caminho iniciando
no nó
i
e terminando no nó
j
. O peso de cada arco de G é um vetor que representa
o custo do deslocamento entre os seus dois nós adjacentes na direção especificada.
PUC-Rio - Certificação Digital Nº 0321287/CA
33
Cada elemento do vetor dos pesos representa o custo de percorrer o referido
caminho passando por uma seqüência específica de linhas do pátio.
Note que ao invés de linhas físicas, aqui se utiliza o conceito de linhas
lógicas, que são distintas para cada manobra. Assim, para cada linha física do
pátio que ocorre mais de uma vez como origem ou destino no conjunto R de
ordens de serviço, o grafo G contém tantas cópias distintas de nós associados a
esta mesma linha física quanto for o número de ordens de serviço que fazem
referência a esta linha. O grafo G tem, portanto, exatamente 2|R| vértices, onde |R|
é o número de ordens de serviço, já que a cada manobra estão associadas duas
linhas lógicas, uma de origem e uma de destino.
2.4.3.
Grafo descritivo do leiaute do pátio
Seja
( , )
G V A
′ ′ ′
=
um grafo misto, conexo e ponderado nos nós e nos arcos,
onde o conjunto
V
′
de seus nós descreve todas as linhas do pátio. Os nós
v
′
deste
grafo são conectados por arcos
a
′
em
A
′
para descrever o leiaute do pátio de tal
forma que conexões entre linhas adjacentes são representadas pelos arcos ou
arestas que ligam os nós adjacentes correspondentes. Arcos entre dois nós de
G
′
indicam que uma locomotiva só pode movimentar entre estes nós na direção
correspondente. Arestas ligando dois nós de
G
′
indicam a possibilidade de
movimentação de locomotivas em ambas as direções entre aqueles nós. O peso de
cada nó
v
′
de
G
′
é o comprimento
v
l
′
da linha de pátio correspondente. O peso de
cada arco ou aresta de
G
′
é a distância entre o par de linhas do pátio conectadas
por aquele arco ou aquela aresta.
Na parte superior da Figura 5 há o desenho de uma região hipotética
denominada área B, pertencente a um pátio chamado Pátio K. A área B contém
sete linhas, representadas pelos segmentos em preto e identificadas por um
número dentro de um quadrado cinza, e quatro AMVs, representados por pares de
segmentos cinzas dispostos em ângulo agudo. A seta cinza na parte superior da
linha 3 indica que há uma regra operacional que determina a circulação por esta
linha em uma única direção. A parte inferior da figura mostra o grafo G´
associado a este setor de pátio. Vale notar que os nós 1, 3 e 5 do grafo G´ estão
PUC-Rio - Certificação Digital Nº 0321287/CA
34
conectados por arcos unidirecionais, indicando a direção única de tráfego
permitida na circulação entre as linhas 1 e 3 e 3 e 5.
Figura 5: Grafo descritivo do leiaute da área B do pátio K
Cabe aqui uma explicação sobre a modelagem do leiaute do pátio utilizando
o grafo orientado G´: Fisicamente, não há restrição quanto à direção de tráfego
nas linhas do pátio, porém, no dia a dia da operação do pátio é comum o
estabelecimento de regras que obrigam ou recomendam o tráfego em uma direção
específica para determinadas linhas. Isto ocorre com o objetivo de atender
critérios de segurança ou simplesmente melhorar a circulação pelo pátio, por
exemplo, evitando-se que comboios freqüentemente se cruzem trafegando em
direções contrárias. A opção pelo uso de um grafo misto para o mapeamento das
linhas do pátio considera a possibilidade de informar eventuais regras de direção
de circulação para linhas específicas. Assim, a implementação das estruturas de
dados para representação do leiaute do pátio e dos algoritmos para percorrê-la
tornam-se mais simples e as soluções são geradas naturalmente aderentes às regras
de circulação.
1
2
4
5
1
2
4
3
5
Área B do Pátio K
Grafo G´ associado
6
7
6
7
3
PUC-Rio - Certificação Digital Nº 0321287/CA
35
2.4.4.
Correspondência entre G e G´
A Figura 6 mostra a correspondência entre os grafos G e G´. Para clareza do
desenho, nem todos os arcos de G´ estão representados nesta figura. No plano
superior contém a representação do grafo G´ e o plano inferior contém a
representação do grafo G. As linhas verticais pontilhadas que unem os dois planos
indicam correspondências entre nós dos grafos G e G´. Nós empilhados no grafo
G indicam linhas do pátio que são origem ou destino de mais de uma manobra e,
nestes casos, o número de nós empilhados de G indicam exatamente quantos nós
correspondem a um único nó em G´. Note que:
em todos os nós de G´ têm um nó correspondente em G: De
fato, uma linha que não é origem e nem destino de nenhuma
manobra aparece como um nó de G´, mas não aparece como um nó
de G.
Um nó de G´ pode ter mais de um nó correspondente em G: Caso
mais de uma manobra tenham como origem ou destino uma mesma
linha;
Todo nó de G tem um único correspondente em G´: Como toda
origem ou destino de manobra tem que ser uma linha do pátio, todos
os nós de G têm um correspondente em G´;
Há uma associação natural entre arcos do grafo G e caminhos do
grafo G´: Os arcos de G representam uma ligação entre a origem e o
destino de pelo menos uma manobra ou o deslocamento de uma
locomotiva escoteira para coletar o conjunto de vagões de uma
manobra. Por outro lado, os arcos ou arestas de G´ representam a
conexão física entre as linhas e, eventualmente, a direção única na
qual é possível trafegar entre duas linhas adjacentes. Dados dois nós
adjacentes v
1
e v
2
de G, há pelo menos um caminho em G´ com
origem e destino, respectivamente, nos nós correspondentes v
1
´ e v
2
´
de G´. Se v
1
´ e v
2
´ são adjacentes, então este caminho é único. Caso
contrário, pode existir mais de um caminho em G´ associado ao arco
(v
1
, v
2
) de
G.
PUC-Rio - Certificação Digital Nº 0321287/CA
36
Figura 6: Correspondência entre os grafos G e G´
É importante notar que, de acordo com as definições de G e G´, decorre que
'
V V
⊆
, ou, equivalentemente, todo nó v de G tem seu nó correspondente v´ no
grafo
G
′
.
2.4.5.
Caminho de Coleta e Entrega
Um caminho de coleta e entrega é um conjunto ordenado
1 2
{ , , ,..., , }
e n
O e v v v e V
+ −
= ⊆
(1)
representando um caminho direcionado simples em G para uma locomotiva
de manobra
e E
∈
, satisfazendo as seguintes condições:
{ , } { , }
e e
r r O r r O
+ − + −
⊂ ∨ ∩ = ∅
r R
∀ ∈
(2)
Se
j
v r
+
=
e
k
v r
−
=
para um dado
r R
∈
,
então
1
k j
= +
, ou
seja,
k
v
é um sucessor direto de
j
v
em
e
O
(3)
|
r e e
w q r R r O
+
≤ ∀ ∈ ∈
(4)
Se
k
v r
+
=
ou
k
v r
−
=
, sendo
k e
v O
∈
,
(5)
G
G´
PUC-Rio - Certificação Digital Nº 0321287/CA
37
então
k
k
v
v f
T t
≤
e
1 1
( )( )
max{ , }
k e
k k k k
v O
v s v v v
T t T t
− −
= +
s
e
T h
+
≥
e
f
e
T h
−
≤
(6)
Onde
k
v
T
é o instante no qual a locomotiva
e E
∈
chega ao nó
k
v V
∈
e
1
( )( )
e
k k
O
v v
t
−
é o tempo total necessário para percorrer o caminho mais curto indo do nó
v
k-1
ao nó v
k
.
A condição
(2)
força o emparelhamento da coleta com a entrega e a
condição
(3)
é a condição de carga única, ou full truckload, que estabelece que
toda coleta deve ser imediatamente seguida de sua respectiva entrega. A condição
(4)
é a restrição de capacidade. A condição
(5)
especifica as restrições de janela de
tempo de coleta e entrega: A locomotiva de manobras não pode chegar à linha de
coleta e nem à linha de entrega de cada manobra depois de seus respectivos finais
de janela de tempo e se a mesma chegar à linha de coleta ou de entrega antes do
início da janela de tempo correspondente, ela deverá esperar até o instante
k
v
s
t
.
Finalmente, a condição
(6)
especifica que todas as manobras planejadas devem ser
executadas dentro do intervalo de tempo
h
∆
.
Figura 7: Caminho de coleta e entrega O
e
no grafo G
e
+
2
r
+
r
r
1
r
−
1
r
+
e
2
r
−
1
k
r
+
−
1
k
r
−
−
2
k
r
+
−
k
r
+
k
r e
− −
=
2
k
r
−
−
PUC-Rio - Certificação Digital Nº 0321287/CA
38
A Figura 7 ilustra um caminho de coleta e entrega
O
e
em G. Os segmentos
contínuos representam o deslocamento de um comboio de pátio puxado ou
empurrado pela locomotiva
e
. Os segmentos pontilhados correspondem ao
deslocamento da locomotiva e no modo escoteira. Segmentos pontilhados e
contínuos são arcos do grafo G e os pequenos círculos redondos são nós deste
mesmo grafo.
O segmento ponto-tracejado representa uma seqüência de movimentos feitos
aos pares, primeiro em modo escoteira e depois em modo de transporte. A
locomotiva
e
inicia o seu caminho a partir de sua linha de estacionamento
representada pelo nó
e
+
, ou seja, onde se encontrava no momento do início do
Horizonte de Planejamento. A partir daí, a locomotiva e se desloca escoteira até a
linha
1
r
+
, de onde ela deverá coletar os vagões para a sua primeira manobra. Os
vagões especificados na manobra
1
r
são então acoplados à locomotiva
e
, que os
transporta até a linha de entrega
1
r
−
. Em seguida, a locomotiva
e
se desloca
escoteira até o ponto
2
r
+
para coleta dos vagões da segunda manobra e assim por
diante, até que a locomotiva
e
faz a sua última entrega na linha
k
r
−
que é também
a mesma linha onde ela estará estacionada ao final do Horizonte de Planejamento,
ou seja, utilizando a notação proposta
k
r e
− −
=
. Vale notar que o nó
e
-
de um
horizonte de planejamento é o nó
e
+
do próximo horizonte de planejamento.
2.4.5.1.Custo de um caminho de coleta e entrega
O custo fixo de um caminho de coleta e entrega é o custo de propriedade da
locomotiva associada a ele por unidade de tempo multiplicado pela duração do
horizonte de planejamento.
Como, por definição, um caminho de coleta e entrega é uma seqüência de
vértices do grafo
G
, o custo variável de um caminho de coleta e entrega é a soma
dos custos associados a todos os arcos de
G
contidas nele. Os itens que se seguem
apresentam duas definições para o custo associado aos arcos de G. A primeira
definição especifica o custo do caminho de coleta e entrega como função da
distância percorrida e a segunda definição especifica o custo como função do
tempo gasto para percorrer o caminho.
PUC-Rio - Certificação Digital Nº 0321287/CA
39
Sabe-se que todo nó
v
em
O
e
é, por definição, uma linha do pátio e,
portanto, tem seu nó correspondente
v´
no grafo
G´
. Sejam então dois nós
adjacentes
v
1
e
v
2
em um caminho de coleta e entrega
O
e
. A dupla (
v
1
, v
2
)
está
naturalmente associada à dupla (
v
1
´, v
2
´)
de
G´
, assim, define-se o custo associado
a um arco (
v
1
, v
2
)
de G como sendo igual ao custo associado a um caminho
correspondente
1 2
( , )
P v v
′ ′ ′
que vai de
v
1
´
até
v
2
´
em
G´
. Estes conceitos são a base
para as definições que se seguem, as quais são importantes elementos para a
definição da função objetivo do problema.
2.4.5.1.1.Custo variável baseado em distância
Como os nós do grafo
G´
são linhas do pátio, o valor associado ao arco
a
′
que une dois nós adjacentes
v
1
´
e
v
2
´
de
'
G
é definido como sendo a distância
entre o ponto médio da linha associada ao nó
v
1
´
e o ponto médio da linha
associada ao nó
v
2
´
. A Figura 8 mostra duas linhas adjacentes de um pátio de
comprimento
l
1
e
l
2
respectivamente e a distância
l
entre elas, calculada como
1 2
1 2
( , )
2
l l
D v v
+
′ ′
=
(7)
Figura 8: Duas linhas adjacentes e o cálculo da distância entre elas
Se as duas linhas
v
1
´
e
v
2
´
não são adjacentes, como
G´
é um grafo conexo,
decorre que existe pelo menos um caminho
{
}
1 2 1 1 2 1 2
( , ) , , ..., ,
n n
P v v v u u u u v V
−
′ ′ ′ ′ ′ ′
= = = ⊆
em
G´
unindo
v
1
´
a
v
2
´
, sendo
3
n
≥
. A distância percorrida em cada caminho
1 2
( , )
i
P v v
′ ′ ′
(com
1
i
≥
) é dada pela
seguinte fórmula:
1
1 2 1
1
( , ) ( , )
n
i k k
k
v v D u u
−
+
=
′ ′
ϒ =
∑
(8)
1 2
( , )
D v v
′ ′
l
1
linha v
1
´
linha v
2
´
l
2
PUC-Rio - Certificação Digital Nº 0321287/CA
40
A distância entre linhas
v
1
´
e
v
2
´
é dada então por
1 2 1 2
( , ) min{ ( , )}
i
v v v v
′ ′ ′ ′
ϒ = ϒ
(9)
O custo variável de um caminho de coleta e entrega
O
e
é então definido
como a distância total percorrida no caminho correspondente em G´:
1
, 1
( ) ( , )
e
e d z z
z z O
O c v v
ξ
+
+ ∈
′ ′
= ϒ
∑
(10)
onde
c
d
é um valor constante e igual ao custo médio de deslocamento da
locomotiva de manobra
e
por unidade de distância e
k
v
′
e
1
k
v
+
′
são nós de
G´
associados aos nós
k
v
e
1
k
v
+
de
O
e
.
O valor de
c
d
é uma aproximação e considera a média entre o custo de
deslocamento da locomotiva
e
no modo escoteira e o custo de deslocamento da
mesma no modo de transporte, acoplada a um conjunto de vagões de peso médio.
Esta é uma definição simples e intuitiva do custo variável de um caminho de
coleta e entrega: O custo é proporcional à distância total percorrida pela
locomotiva ao longo de seu caminho. Como o valor da constante
c
d
e o leiaute do
pátio são conhecidos e não variam durante o horizonte de planejamento, o custo
variável baseado em distância é também denominado de
custo variável estático
.
2.4.5.1.2.Custo variável baseado em tempo
O custo variável baseado em tempo depende:
Da locomotiva que está fazendo o percurso;
Do peso dos vagões que estão sendo tracionados;
Da distância a ser percorrida entre o nó de origem e o de destino;
Da hora em que a locomotiva parte do nó de origem;
De eventuais necessidades de espera durante o seu percurso até que a
linha seguinte esteja livre.
Da duração do deslocamento entre cada par de linhas representadas
por nós adjacentes do caminho de coleta e entrega.
PUC-Rio - Certificação Digital Nº 0321287/CA
41
Para computar o custo baseado em tempo de uma locomotiva
e
percorrer um
caminho de coleta e entrega
O
e
, primeiro considera-se todos os caminhos
possíveis do tipo
{
}
1 2 1 1 2 1 2
( , ) , , ..., ,
n n
P v v v u u u u v V
−
′ ′ ′ ′ ′ ′
= = = ⊆
em
G´
unindo
v
1
´
a
v
2
´
, sendo
3
n
≥
para cada par de nós
v
1
´
e
v
2
´
em
G´
,
associados ao
respectivos nós adjacentes do caminho de coleta e entrega. Depois, usa-se a
fórmula (11), a qual se baseia nos custos por unidade de tempo da locomotiva
e
em modo de transporte
c
t
,
modo escoteira
c
l
e modo de espera
c
s
e os tempos
correspondentes
t
t
,, t
l
e
t
s
em que a locomotiva
e
fica em cada um dos modos
durante o percurso de
v
1
´
a
v
2
´
.
1 2 1 2 1 2 1 2
( , ) , ) , ) , )
( ( (
i t t l l s s
v v c t v v c t v v c t v v
′ ′ ′ ′ ′ ′ ′ ′
ϒ = + +
(11)
A partir deste ponto, segue-se o mesmo raciocínio usado para o cálculo do
custo baseado em distância. A fórmula
(9)
toma a rota de
v
1
´
a
v
2
´
com menor
duração e finalmente a fórmula
(12)
é usada para calcular o custo variável baseado
em tempo para o caminho de coleta e entrega
O
e
.
1
, 1
( ) ( , )
e
e z z
z z O
O v v
ξ
+
+ ∈
′ ′
= ϒ
∑
(12)
Esta fórmula é muito parecida com a fórmula
(10)
, sendo que neste caso
c
d
não é usado porque o seu papel já foi desempenhado pelas constantes
c
t
,, c
l
e
c
s
.
O tempo de espera em cada linha do caminho de coleta e entrega depende
do exato momento em que o comboio chega àquela linha. A espera ocorre ou por
causa da restrição imposta pela janela de tempo ou devido à linha adiante estar
ocupada por outro comboio ou locomotiva. Esta variabilidade do custo
dependente do tempo faz com que o valor do custo só possa ser obtido através de
uma simulação da execução completa do caminho de coleta e entrega e
impossibilita o cálculo antecipado do custo das rotas entre cada par de nós
adjacentes do caminho de coleta e entrega, como ocorre no caso do custo baseado
em distância. Estas características do custo baseado em tempo conferem ao
mesmo o nome alternativo de
custo variável dinâmico
.
2.4.6.
Formulação
Seja um conjunto
PUC-Rio - Certificação Digital Nº 0321287/CA
42
{ }
e e E
O
∈
Φ =
(13)
de caminhos de coleta e entrega, tais que:
Dados
,
a b
r r R
∈
, se
r
a
é predecessor de
r
b
, então
a b
r r
T T
− +
<
(14)
e
e E
O V
∈
=
∪
(15)
A solução para o problema de programação de operações das locomotivas
de manobra (PPOLM) consiste em encontrar o conjunto Φ
*
que minimiza a
função objetivo:
*
* *
1 2
( ) ( ) ( )
| |
e
e
O
c c
C O
E d
θ ξ
∈Φ
Φ = Φ +
∑
(16)
onde
(Φ
*
)
é o número de caminhos de coleta e entrega em Φ
*
com mais de dois
elementos,
c
1
e
c
2
são constantes não negativas definidas pela equipe de
planejamento de operações de pátio,
|E|
é o tamanho da frota, ou seja, o número
de locomotivas de manobras disponíveis no pátio,
d
é uma estimativa da distância
máxima que a locomotiva de manobras mais rápida da frota conseguiria percorrer
escoteira durante o horizonte de planejamento
h
∆
e
( )
e
O
ξ
é o custo variável do
caminho de coleta e entrega de Φ
*
, percorrido pela locomotiva
e
, e calculado
utilizando-se a fórmula
(10)
ou a fórmula
(12)
.Vale notar que o valor do horizonte
de planejamento
h
∆
é comum a todos os caminhos de coleta e entrega contidos
em Φ
*
.
Eventualmente, para uma dada locomotiva
k
e E
∈
pode ocorrer que
{ , }
k
e k k
O e e
+ −
=
. Este caminho de coleta e entrega
k
e
O
, com apenas dois elementos,
representa a possibilidade da locomotiva
k
e E
∈
não executar nenhuma manobra
durante o horizonte de planejamento
h
∆
. Este tipo de conjunto de
Φ
*
não é
considerado no cálculo de
(Φ
*
)
e, portanto,
|E| ≥
(Φ
*
)
, ou seja,
(Φ
*
)
é o
número de locomotivas efetivamente utilizadas na solução do PPOLM.
Os valores
c
1
e
c
2
na fórmula
(16)
expressam a importância relativa do custo
fixo comparado ao custo variável na operação do pátio em estudo, tornando a
fórmula da função objetivo uma soma ponderada. Um método para cálculo destes
valores consiste em apurar o custo variável médio por unidade de tempo e
PUC-Rio - Certificação Digital Nº 0321287/CA
43
comparar com o custo fixo médio por locomotiva e por unidade de tempo e depois
estabelecer a relação de proporção entre os dois valores considerando,
adicionalmente, as metas do planejamento tático, como, por exemplo, diminuição
do número de locomotivas de manobras no pátio. Independentemente do método
utilizado para valores
c
1
e
c
2
, pode-se dizer que estes valores são arbitrariamente
definidos pelo usuário e têm como objetivo definir a importância do objetivo de
reduzir a frota de locomotivas utilizada no pátio comparada ao objetivo de fazer
com que as manobras sejam executadas mais rapidamente e com menor consumo
de combustível.
A fórmula
(14)
expressa a restrição de precedência do PPOLM. Esta
restrição identifica uma diferença importante no critério de seleção das soluções
viáveis entre o algoritmo CompetAnts e o algoritmo proposto neste trabalho.
A fórmula
(15)
faz com que todas as ordens de serviço sejam atendidas pela
coleção Φ de caminhos de coleta e entrega da fórmula
(13)
. O fato do valor de
*
( )
C
Φ
ser mínimo implica que não há ordem de serviço repetida em Φ
*
.
A fórmula
(16)
expressa o objetivo de reduzir o custo total associado ao
conjunto Φ
*
. O primeiro termo da soma é proporcional ao custo fixo da solução e
o segundo termo é proporcional ao custo variável
Os valores de
|E|
e
d
foram usados na fórmula
(16)
para impedir que haja
uma diferença considerável na magnitude dos dois elementos da soma. Estes
valores fazem com que as constantes
c
1
e
c
2
funcionem conforme desejado,
independente de fatores como a quantidade de veículos disponíveis no pátio, a
duração do horizonte de planejamento e a unidade de medida de deslocamento
utilizada.
O uso da fórmula do custo variável ou dinâmico para o cálculo de
( )
e
O
ξ
depende da qualidade das informações disponíveis sobre o pátio e do tempo de
processamento permitido para se apresentar a solução do problema. Se os tempos
envolvidos na fórmula
(11)
podem ser computados com um nível de confiabilidade
razoável, utiliza-se a fórmula
(12)
e obtém-se o custo variável dinâmico, caso
contrário, utiliza-se a fórmula
(10)
e obtém-se o custo variável estático. Além
disso, o uso da fórmula
(12)
implica em um maior tempo de processamento já que
o custo variável estático pode ser calculado inicialmente e usado durante todo o
PUC-Rio - Certificação Digital Nº 0321287/CA
44
decorrer do processo enquanto o custo variável dinâmico requer o cálculo e
atualização durante a construção da solução, já que varia em função do tempo.
Alguns profissionais da área questionam a importância de se considerar o
custo fixo na função objetivo já que, depois de adquirida ou alugada, a locomotiva
de manobras é normalmente alocada para trabalhar no pátio por um período
equivalente a vários horizontes de planejamento. Sendo assim, a redução de custo
obtida com a redução da frota não ocorre, normalmente, para o horizonte de
planejamento considerado. De fato, este argumento é válido se o planejamento for
considerado com uma perspectiva operacional, no entanto, a utilização recorrente
de um número menor de locomotivas de manobras do que o disponível no pátio ao
longo de sucessivos horizontes de planejamento é indício de que o planejamento
tático deve considerar a redução da frota para aquele pátio. De qualquer forma, os
valores de
c
1
e
c
2
na fórmula (16) dão ao usuário a flexibilidade de indicar, no
contexto da operação do pátio considerado, a importância do custo fixo em
relação ao custo variável, sendo possível, inclusive, atribuir o valor zero para
c
1
indicando que o custo variável não tem nenhuma importância para o problema
dado.
2.5.
O PPOLM como um problema estático
Uma característica importante dos problemas de roteamento em geral é o
modo como as requisições de transporte se tornam disponíveis. Um problema é
classificado como estático quando todas as requisições de transporte são
conhecidas antes da execução das rotas pelos veículos, e é classificado como
dinâmico se algumas requisições são conhecidas inicialmente e outras requisições
surgem em tempo real, depois que os veículos já iniciaram a execução das rotas,
sendo necessária a modificação da rota de algum veículo para inclusão da nova
requisição acrescentada. Outras diferenças entre o problema estático e o dinâmico,
bem como uma revisão dos métodos e resultados mais importantes para solução
dos dois tipos de problema pode ser encontrado em Mitrovic-Minic & Laporte
(2003).
No caso real utilizado como referência para a modelagem desenvolvida
neste trabalho, a maioria das demandas é produto de algum planejamento prévio e,
portanto, são conhecidas antes de sua execução, de modo que não é necessário
PUC-Rio - Certificação Digital Nº 0321287/CA
45
planejar a execução das ordens de serviço imediatamente após tomar
conhecimento das mesmas.
Havendo um planejamento prévio, é legítimo, portanto, assumir que em um
dado momento
t0
, todas as ordens de serviço a serem atendidas, dentro de um
horizonte de tempo definido previamente, são conhecidas (Lubbecke, 2001). Esta
premissa motiva a utilização do horizonte de planejamento
h
de duração
h
,
conforme definido no item 2.4.1, de modo que só são consideradas as ordens de
serviço que podem ser executadas até o tempo
t0 + h
. Vale notar que o valor de h
define, implicitamente, o tamanho da instância do problema, já que, para uma
freqüência constante de execução de manobras, este valor limita o número de
ordens de serviço a serem consideradas no planejamento.
Para tratar demandas emergenciais surgidas em um momento
t
(
t > t
0
,
t
∈
[h
i
,
h
f
]
) durante a execução de uma seqüência planejada de manobras pode-se,
simplesmente, registrar a situação do terminal naquele momento, juntamente com
as manobras ainda não executadas e adicionar a estas as novas manobras
emergenciais, submetendo este novo conjunto de informações para
processamento. Esta é a estratégia adotada na maioria das vezes, na prática, para
resolver problemas dinâmicos: O problema inicial é visto como uma seqüência de
problemas estáticos (Savelsbergh & Sol, 1995).
Vale lembrar que ao modelar o PPOLM como estático estabelece-se uma
restrição importante no tempo de execução do algoritmo que irá resolvê-lo: depois
de implementado o algoritmo no computador, o tempo de entrada de dados mais o
tempo de execução do programa resultante não pode ser maior do que a duração
do horizonte de planejamento dividido pelo número de vezes que se pode desejar
incluir novas ordens de serviço durante a execução do plano proposto.
PUC-Rio - Certificação Digital Nº 0321287/CA
3
Revisão da literatura
Pensar é mais interessante que saber e menos interessante que observar.
JOHANN WOLFGANG GOETHE
O objetivo deste capítulo é apresentar as referências mais importantes
relacionadas aos três principais tópicos cobertos neste trabalho que são o
planejamento operacional de pátios ferroviários, o problema de coleta e entrega e
a otimização com colônia de formigas.
Neste trabalho, o PPOLM é modelado como um problema de coleta e
entrega com vários veículos, restrição de janelas de tempo, capacidade e
precedência, composto com um problema de encontrar o caminho mais curto entre
dois vértices de um grafo onde o peso é dependente de espaço e tempo. O
problema de coleta e entrega é resolvido com uma metaheurística de otimização
com colônia de formigas envolvendo duas colônias e o caminho mínimo é
encontrado com o tradicional algoritmo de Dijkstra.
3.1.
Planejamento operacional de pátios ferroviários
A principal motivação deste trabalho é a redução dos custos operacionais de
pátios ferroviários. Neste contexto, espaço, tempo e custo são variáveis
interdependentes e constituem o foco principal da análise. Por exemplo, espaços
mais curtos percorridos pelas locomotivas de manobras implicam em menor
tempo para percorrê-lo e conseqüentemente menor consumo de combustível e
menor tempo de alocação dos recursos humanos envolvidos (e.g. tripulação,
técnicos de operação ferroviária), reduzindo assim o custo operacional do pátio.
PUC-Rio - Certificação Digital Nº 0321287/CA
47
Daganzo et al. (1983) destaca os dois componentes mais importantes do
ciclo médio de vagões: O tempo em que o vagão fica na ferrovia, que equivale,
em média, a 14% do ciclo médio de vagão e o tempo em que o vagão fica em
pátios, que corresponde a 62% do ciclo médio de vagão. Trabalhos mais recentes
como Dyke (2006) e Dirnberger & Barkan (2007) mostram que esta proporção de
distribuição dos componentes do ciclo de vagão não mudou muito durante as
últimas décadas. Isto significa que investimentos na melhoria operacional dos
pátios, visando reduzir o tempo de permanência dos vagões nos mesmos implicam
em um grande potencial de redução do ciclo de vagão e, conseqüentemente, em
uma perspectiva de melhoria considerável na eficiência do sistema de transporte
ferroviário como um todo. Com efeito, segundo Bektas et al. (2007), uma das
iniciativas mais importantes para aumentar a produtividade e a competitividade
das ferrovias é a gestão eficiente dos pátios ferroviários, fazendo com que os
vagões sejam processados o mais rápido possível, de modo a propiciar uma
utilização eficiente dos ativos e atender os horários de conexão.
Embora o investimento em melhorias operacionais de pátios sugira ganhos
potenciais, existem poucos trabalhos publicados nesta área. De acordo com
Lübbecke (2001), o trabalho pioneiro Charnes & Miller (1956) era o único
publicado sobre programação de trabalho para locomotivas de manobras em
pátios ferroviários em um intervalo de 45 anos até aquela data. Reis Jr. (2003),
estuda algoritmos de branch and bound paralelos para planejamento de manobras
em pátios e, finalmente, encerrando a lista das referências conhecidas sobre o
assunto, aparece Sabino (2004) que é a pesquisa precursora deste trabalho.
Reis Jr. (2003) é um trabalho de interesse peculiar para esta pesquisa já que
o mesmo usa como referência o mesmo ambiente industrial. Nesse trabalho, não
são apresentadas as características detalhadas do ambiente estudado, nem o
método utilizado para coleta dos dados reais, nem os dados de entrada usados nos
testes computacionais e nem as soluções encontradas para cada instância testada.
Isto torna impossível usá-lo como referência para uma comparação dos problemas
e dos métodos adotados para solução. No entanto, aparentemente, esse trabalho
estuda um problema similar ao PPOLM e, sem um tratamento formal do mesmo,
o modela como um problema de escalonamento de tarefas, caracterizando-o como
uma busca pelo melhor caminho em um grafo e um problema de programação de
PUC-Rio - Certificação Digital Nº 0321287/CA
48
manobras. O objetivo principal foi apresentar uma solução paralela para tais
problemas e a conclusão foi que, embora a técnica escolhida seja eficiente, ela é
sensível a problemas internos como gargalos de comunicação e anomalias. Do
ponto de vista de aplicação prática, não foi apresentado o resultado de testes
comparativos usando como referência dados reais ou mesmo a simulação destes.
A conclusão naquela época foi que, embora o algoritmo proposto tenha sido
considerado aplicável em qualquer pátio, o mesmo não considerava alguns
aspectos importantes tais como linhas férreas interditadas, rotas conflitantes e
lotes de vagão de diferentes tamanhos, já que estes itens foram relaxados para se
permitir um primeiro passo na solução dos problemas citados.
Kraft (1998) e Daganzo et al. (1983) tratam de outros problemas
relacionados ao planejamento operacional de pátios sem, no entanto, referenciar o
PPOLM especificamente. Kraft (1998) apresenta um método de controle
operacional e programação de carregamento e Daganzo et al. (1983) propõe um
procedimento para melhorar a eficiência das operações de classificações em pátios
ferroviários. Estes dois trabalhos foram as principais referências durante os
estudos que resultaram na decomposição do planejamento operacional de pátios
ferroviários em três etapas e forneceram os fundamentos para a modelagem do
caminho das locomotivas de manobras.
A maioria (e, de fato, a quase totalidade) dos estudos sobre planejamento
operacional de ferrovias aborda a movimentação de cargas pela ferrovia, a
programação de trabalho com as locomotivas de viagem, a atribuição de blocos a
trens e a definição da programação de trens. Trabalhos como Ahuja & Jha (2004)
e Ahuja et al. (2004), Crainic et al. (1984), Crainic & Roy (1988), Keaton (1989),
Marin & Salmeron (1996a, 1996b), Martinelli & Hualiang (1996), Crainic &
Laporte (1997), Gualda & Murgel (2000) e Crainic (2002), embora não tratem
especificamente das operações de pátio e sim do planejamento operacional e tático
de todo o sistema ferroviário, forneceram uma boa base sobre a terminologia e a
modelagem contribuindo para que a abordagem contida neste trabalho
considerasse o planejamento de pátios no contexto do sistema ferroviário como
todo.
Ahuja et al. (2002), Kuo & Nicholls (2007) e Vaidyanathan et al. (2008),
embora tratem da programação de trabalho de locomotivas visando a redução do
PUC-Rio - Certificação Digital Nº 0321287/CA
49
custo operacional, consideram locomotivas que viajam pela ferrovia para
transportar carga e não locomotivas que executam manobras em pátios.
Também na área de simulação não foi possível identificar trabalhos que
tratassem de planos de trabalho de locomotivas de manobra. A referência que
mais se aproxima deste assunto é Franzese et al. (2003) que apresenta um
simulador da Estrada de Ferro Vitória a Minas, da qual um dos pátios terminais é
exatamente o pátio de referência para a aplicação prática do algoritmo apresentado
nesta tese. Este simulador, que utiliza uma interface gráfica com o usuário
desenvolvida em Microsoft Excel®, se baseia no software ARENA®, da Rockwell
Automation para desenvolver um estudo cujo objetivo principal foi verificar se
trens com 320 vagões aumentariam a capacidade de transporte do sistema
ferroviário. Mais uma vez, o foco deste trabalho está na ferrovia e não no pátio.
Diante do número limitado de referências bibliográficas sobre o problema
específico do qual trata este trabalho, muitas informações importantes foram
obtidas através de entrevistas com profissionais da área.
3.2.
Problema de coleta e entrega
De acordo com o modelo proposto neste trabalho e considerando a
modelagem apresentada em Parragh et al. (2006), o problema que mais se
aproxima do PPOLM é o problema de coleta e entrega clássico. Mais
especificamente, pode-se dizer que o PPOLM é um problema de coleta e entrega
com janelas de tempo, como em Dumas et al. (1991), devido à especificação de
um intervalo de tempo para coleta e para entrega dos vagões, com múltiplos
veículos, como em Zhou et al. (2006), porque a solução pode utilizar mais de uma
locomotiva de manobra, com frota heterogênea, como em Lee et al. (2007), pois
as locomotivas de manobra podem ter capacidades de tração diferente, com carga
única, ou full truck load, como em Jin & Muriel (2005), já que uma locomotiva
não pode coletar vagões adicionais sem que antes tenha entregue os vagões que
esteja transportando, com precedências, como em Sigurd et al. (2000), pois há
uma ordem pré-definida para realizar certas manobras, e, finalmente, com
múltiplos objetivos, como em Lu & Dessouky (2004), já que deseja-se reduzir
tanto custo fixo, relacionado à quantidade de locomotivas necessárias para a
solução, quanto o custo variável, relacionado ao deslocamento das locomotivas
PUC-Rio - Certificação Digital Nº 0321287/CA
50
para realização das manobras planejadas. Em suma o PPOLM pode ser
considerado um problema de coleta e entrega com janelas de tempo, múltiplos
veículos, frota heterogênea, carga única, precedências e múltiplos objetivos.
O problema de coleta com janelas de tempo tem inúmeras aplicações
práticas referenciadas na literatura. Toth & Vigo (2002) citam alguns exemplos
clássicos como o transporte de deficientes físicos e idosos, transporte aéreo e
naval de cargas e tropas militares, serviços urbanos de coleta e entrega de
encomendas e planejamento de rotas de ônibus escolares. Motivados pela
diversidade de trabalhos disponível na literatura, alguns pesquisadores chegaram a
desenvolver levantamentos bibliográficos sobre o problema de coleta e entrega,
dentre os quais os seguintes foram referências importantes para este trabalho:
Savelsbergh & Sol (1995), que desenvolve uma análise sistemática
cobrindo todas as variações conhecidas até então do problema de
coleta e entrega. Para cada versão é apresentada a formulação e a
modelagem, bem como os métodos conhecidos para a solução;
Mitrovic-Minic (1998), que apresenta um levantamento sobre as
variações e métodos disponíveis para solução com foco no problema
de coleta e entrega com janelas de tempo, incluindo a formulação
matemática utilizada para o desenho de soluções exatas;
Parragh et al. (2006), que é o levantamento mais recente de modelos
para tratamento do problema de coleta e entrega e, em especial, faz
referência ao caso onde há itens transportados entre locais de coleta
e entrega (e não entre depósitos) e suas variações, desenvolvendo
uma classificação com respectivas formulações matemáticas e
métodos de solução conhecidos para cada caso.
Algoritmos para solução de problemas de coleta e entrega com janelas de
tempo e outras restrições são geralmente divididos em três classes:
Os algoritmos exatos, aplicados a modelos baseados em
programação inteira, que resolvem o problema usando métodos com
geração de colunas, branch-and-bound ou branch-and-cut como em
Dumas et al. (1991), Baldacci et al. (2004), Cordeau (2006),
Dell’Amico et al. (2006) e Ropke et al. (2007);
PUC-Rio - Certificação Digital Nº 0321287/CA
51
As heurísticas que constroem, por decomposição ou inserção, um
conjunto de rotas viáveis a partir do zero como em Lu & Dessouky
(2006) e Dell’Amico et al. (2007) ou procuram melhorar uma
solução inicial através da aplicação de um algoritmo de busca local
como em Nanry & Barnes (2000) e Cordeau & Laporte (2003).
As metaheurísticas, tais como Ant Colony Optimization (ACO),
Evolutionary Computation (EC), Simulated Annealing (SA) e Tabu
Search (TS), que segundo Dorigo & Stützel (2004), são métodos
heurísticos de propósito geral, desenvolvidos para guiar uma
heurística subordinada (e.g. uma heurística de construção ou de
busca local) em direção a regiões do espaço de busca que contenham
soluções de alta qualidade. Este é o caso de Li & Lim (2003), Barcus
(2004) e Tarantilis et al. (2005). Blum & Roli (2003) apresentam e
comparam as metaheurísticas mais importantes disponíveis na
literatura até aquela época.
O problema de coleta e entrega com janela de tempo é NP-difícil (Mitrovic-
Minic, 1998). Com efeito, algoritmos exatos têm requerido um consumo
considerável de recursos computacionais para encontrar a solução ótima de
problemas mais simples e com instâncias de tamanho modesto. Este é o caso de
Toth & Vigo (1997), que trata de um problema de coleta e entrega sem janelas de
tempo com uma técnica baseada em limites inferiores obtidos pela aplicação de
Relaxação Lagrangeana, combinada com o uso de planos de cortes, algoritmo
branch-and-bound, procedimentos de redução e critérios de dominância, para
resolver instâncias com 100 pontos de coleta e entrega, consumindo 1h40min de
tempo de CPU de um processador Pentium® de 60MHz. Outro exemplo mais
recente é Lu & Dessouky (2004) que, no melhor caso, consegue resolver um
problema de coleta e entrega com múltiplos veículos e múltiplos objetivos, mas
sem janelas de tempo com, no máximo, 5 veículos e 25 pontos de coleta,
requerendo, para tanto, três horas de tempo de CPU em um servidor Sunfire®
4800. Um caso prático do PPOLM tem cerca de 120 pontos de coleta e entrega, e
se deseja resolvê-lo em alguns minutos usando um computador de baixo custo.
Diante deste cenário, fica claro o motivo pelo qual é comum o uso de heurísticas
ou metaheurísticas para buscar soluções de problemas da vida real, já que deste
PUC-Rio - Certificação Digital Nº 0321287/CA
52
modo é possível encontrar boas soluções com tempo de CPU razoável e, portanto,
tempo de execução praticável.
Mesmo diante da diversidade de modelos, métodos e resultados reportados
na literatura, a avaliação do desempenho relativo de algoritmos para resolver
problemas de coleta e entrega com janelas de tempo é praticamente impossível, já
que até o momento não há conjuntos conhecidos de instâncias de referência (i.e.
benchmarks) para o caso genérico deste problema. Toth & Vigo (2002) explicam
que isto ocorre principalmente devido à diversidade de variações dos problemas
estudados, já que a maioria dos trabalhos se baseia em aplicações práticas, as
quais induzem modelagens específicas para a representação das restrições e da
função objetivo. Assim, os métodos são testados com dados simulados da situação
real em estudo e os resultados são comparados com os obtidos com as soluções
manuais em uso.
3.3.
Otimização com Colônia de Formiga
Otimização com Colônia de Formiga ou Ant Colony Optimization (ACO)
como são mais conhecidos na literatura, é uma classe de algoritmos que geram
soluções candidatas para um problema de otimização através de um mecanismo
construtivo onde a escolha do componente da solução a ser adicionado em cada
passo se baseia em um balanceamento probabilístico que considera trilhas de
feromônio artificial e informações heurísticas sobre o problema em questão
(Dorigo & Stützle, 2004).
Dentre os diversos algoritmos ACO disponíveis atualmente na literatura, o
primeiro a ser proposto foi o algoritmo Ant System (AS), apresentado nas versões
originais denominadas ant-density (Dorigo et al., 1991), ant-quantity (Colorni et
al., 1992) e ant-cycle (Dorigo, 1992). Atualmente ACO se caracteriza como uma
ferramenta de otimização poderosa e versátil, com um número crescente de
publicações e aplicações em diversas áreas da pesquisa operacional, gestão e
tecnologia (Gutjahr, 2007).
Problemas de otimização combinatória tratados com ACO são normalmente
codificados através de um grafo de construção completo G(V,A), onde os nós de
V são componentes da solução e os arcos de A são conexões entre os
PUC-Rio - Certificação Digital Nº 0321287/CA
53
componentes. Construir uma solução significa encontrar um caminho viável em
G. Por exemplo, no problema do caixeiro viajante, os nós correspondem aos
clientes, os arcos correspondem às ruas que conectam os clientes e uma solução
viável é um caminho hamiltoniano no grafo (Bianchi, 2006).
Os parágrafos seguintes apresentam uma visão geral do algoritmo Ant
System (AS) baseado na descrição apresentada em Dorigo et al. (2006).
Uma formiga é um agente computacional simples, que constrói
iterativamente uma solução para o problema de otimização em questão.
Usualmente, nos algoritmos ACO, cada formiga artificial parte de uma solução
vazia e adiciona componentes à sua solução parcial até conseguir uma solução
candidata completa. Soluções parciais para o problema são chamadas estados.
Assim, uma formiga move de um estado i para um estado j correspondente a uma
solução parcial mais completa para o problema. Em cada passo s, uma formiga a
determina o conjunto de expansões viáveis para o seu estado atual e escolhe uma
destas expansões, movendo-se para um novo estado, baseada na distribuição de
probabilidade que se segue.
A probabilidade
,
a
i j
p
de uma formiga se mover de um estado i para um
estado j depende da combinação de dois valores:
1. A atratividade η
do movimento, calculada antes do processo de
construção da solução e, portanto, considerada uma indicação prévia
do grau de atração do movimento;
2. O nível de feromônio τ
do movimento, que indica o quão eficiente
foi fazer aquele movimento no passado. Este valor é considerado
uma indicação posterior da atratividade do referido movimento, já
que é calculado durante o processo de construção da solução.
A Figura 9 ilustra as diversas possibilidades de passo de uma formiga partir
do estado i. Se o estado j ainda não foi visitado, ou seja, se ainda não pertence ao
caminho da formiga, a probabilidade de escolha deste estado é proporcional ao
nível de feromônio τ
e à atratividade η associado ao passo (i,j).
PUC-Rio - Certificação Digital Nº 0321287/CA
Figura
conjunto
com condições que dependem da definição do problema.
computadas como segue:
os que estão contidos no
calculada pela seguinte fórmula:
onde
atratividade
importância do feromônio em relação à
é de
finida como sendo o inverso do custo associado ao movimento de
Para o problema clássico do caixeiro viajante, por exemplo, onde o custo é a
distância entre dois nós, a
iteração.
reduzida, simulado assim o fenômeno da evaporação do feromônio, tal como
ocorre na natureza. Em seguida, o
encontrada por alguma formiga
Os demais caminhos
iteração
quantidade de feromôni
Figura
9
: Movimentos possíveis de uma formiga a partir do estado
A fórmula que define a distribuição de probabilidade em cada passo utiliza o
conjunto
in
viáveis
com condições que dependem da definição do problema.
computadas como segue:
os que estão contidos no
calculada pela seguinte fórmula:
τ
ij
é a quantidade de feromônio associado ao movimento de
atratividade
associada a este movimento
importância do feromônio em relação à
finida como sendo o inverso do custo associado ao movimento de
Para o problema clássico do caixeiro viajante, por exemplo, onde o custo é a
distância entre dois nós, a
A quantidade de feromônio d
iteração.
Inicialmente, todos os caminhos t
reduzida, simulado assim o fenômeno da evaporação do feromônio, tal como
ocorre na natureza. Em seguida, o
encontrada por alguma formiga
Os demais caminhos
iteração
t
do algoritmo, depois que todas as formigas completaram sua solução a
quantidade de feromôni
: Movimentos possíveis de uma formiga a partir do estado
A fórmula que define a distribuição de probabilidade em cada passo utiliza o
viáveis
a
que defin
com condições que dependem da definição do problema.
computadas como segue:
p
os que estão contidos no
conjunto
calculada pela seguinte fórmula:
a
ij
p
é a quantidade de feromônio associado ao movimento de
associada a este movimento
importância do feromônio em relação à
finida como sendo o inverso do custo associado ao movimento de
Para o problema clássico do caixeiro viajante, por exemplo, onde o custo é a
distância entre dois nós, a
atratividade
A quantidade de feromônio d
Inicialmente, todos os caminhos t
reduzida, simulado assim o fenômeno da evaporação do feromônio, tal como
ocorre na natureza. Em seguida, o
encontrada por alguma formiga
Os demais caminhos
não t
ê
do algoritmo, depois que todas as formigas completaram sua solução a
quantidade de feromôni
o é atualizada de acordo com a seguinte fórmula:
: Movimentos possíveis de uma formiga a partir do estado
A fórmula que define a distribuição de probabilidade em cada passo utiliza o
que defin
e as soluções inviáveis para a formiga
com condições que dependem da definição do problema.
,
a
i j
p
é igual a zero para todos os passos inviáveis (isto é,
conjunto
in
viáveis
calculada pela seguinte fórmula:
( )
ij ij
a
ij
iv inviáveis
p
α β
τ η
∉
=
∑
é a quantidade de feromônio associado ao movimento de
associada a este movimento
importância do feromônio em relação à
finida como sendo o inverso do custo associado ao movimento de
Para o problema clássico do caixeiro viajante, por exemplo, onde o custo é a
atratividade
A quantidade de feromônio d
eixada no caminho é atualizada em cada
Inicialmente, todos os caminhos t
reduzida, simulado assim o fenômeno da evaporação do feromônio, tal como
ocorre na natureza. Em seguida, o
s caminhos que
encontrada por alguma formiga
tem sua quantidade de feromônio incrementada.
ê
m
acréscimo de
do algoritmo, depois que todas as formigas completaram sua solução a
o é atualizada de acordo com a seguinte fórmula:
i
: Movimentos possíveis de uma formiga a partir do estado
A fórmula que define a distribuição de probabilidade em cada passo utiliza o
e as soluções inviáveis para a formiga
com condições que dependem da definição do problema.
é igual a zero para todos os passos inviáveis (isto é,
viáveis
a
), caso contrário, a probabilidade é
a
ij ij
iv iv
iv inviáveis
α β
α β
τ η
τ η
⋅
⋅
∑
é a quantidade de feromônio associado ao movimento de
associada a este movimento
e
os parâmetros
importância do feromônio em relação à
atratividade
finida como sendo o inverso do custo associado ao movimento de
Para o problema clássico do caixeiro viajante, por exemplo, onde o custo é a
é normalmente o inverso da distância.
eixada no caminho é atualizada em cada
Inicialmente, todos os caminhos t
ê
m sua quantidade de feromônio
reduzida, simulado assim o fenômeno da evaporação do feromônio, tal como
s caminhos que
tem sua quantidade de feromônio incrementada.
acréscimo de
sua quantidade de feromônio
do algoritmo, depois que todas as formigas completaram sua solução a
o é atualizada de acordo com a seguinte fórmula:
p
: Movimentos possíveis de uma formiga a partir do estado
A fórmula que define a distribuição de probabilidade em cada passo utiliza o
e as soluções inviáveis para a formiga
com condições que dependem da definição do problema.
A
é igual a zero para todos os passos inviáveis (isto é,
), caso contrário, a probabilidade é
é a quantidade de feromônio associado ao movimento de
os parâmetros
atratividade
. A
atratividade
finida como sendo o inverso do custo associado ao movimento de
Para o problema clássico do caixeiro viajante, por exemplo, onde o custo é a
é normalmente o inverso da distância.
eixada no caminho é atualizada em cada
m sua quantidade de feromônio
reduzida, simulado assim o fenômeno da evaporação do feromônio, tal como
s caminhos que
fazem parte
tem sua quantidade de feromônio incrementada.
sua quantidade de feromônio
do algoritmo, depois que todas as formigas completaram sua solução a
o é atualizada de acordo com a seguinte fórmula:
,
( , )
a
i j
p
τ η
: Movimentos possíveis de uma formiga a partir do estado
i
A fórmula que define a distribuição de probabilidade em cada passo utiliza o
e as soluções inviáveis para a formiga
a
, de acordo
A
s probabilidades são
é igual a zero para todos os passos inviáveis (isto é,
), caso contrário, a probabilidade é
é a quantidade de feromônio associado ao movimento de
i
para
os parâmetros
α
e β definem a
atratividade
normalmente
finida como sendo o inverso do custo associado ao movimento de
Para o problema clássico do caixeiro viajante, por exemplo, onde o custo é a
é normalmente o inverso da distância.
eixada no caminho é atualizada em cada
m sua quantidade de feromônio
reduzida, simulado assim o fenômeno da evaporação do feromônio, tal como
fazem parte
da soluç
tem sua quantidade de feromônio incrementada.
sua quantidade de feromônio
do algoritmo, depois que todas as formigas completaram sua solução a
o é atualizada de acordo com a seguinte fórmula:
h
j
i
k
54
A fórmula que define a distribuição de probabilidade em cada passo utiliza o
, de acordo
s probabilidades são
é igual a zero para todos os passos inviáveis (isto é,
), caso contrário, a probabilidade é
(17)
para
j, η
ij
é a
e β definem a
normalmente
finida como sendo o inverso do custo associado ao movimento de
i para j.
Para o problema clássico do caixeiro viajante, por exemplo, onde o custo é a
é normalmente o inverso da distância.
eixada no caminho é atualizada em cada
m sua quantidade de feromônio
reduzida, simulado assim o fenômeno da evaporação do feromônio, tal como
da soluç
ão
tem sua quantidade de feromônio incrementada.
sua quantidade de feromônio
. Em cada
do algoritmo, depois que todas as formigas completaram sua solução a
o é atualizada de acordo com a seguinte fórmula:
PUC-Rio - Certificação Digital Nº 0321287/CA
55
1
( ) ( 1)
m
k
ij ij ij
k
t t
τ ρ τ τ
=
= ⋅ − + ∆
∑
(18)
onde
ρ
é um valor definido pelo usuário que representa a persistência do
feromônio ao longo das iterações, m é o número de formigas e
k
ij
τ
∆
representa a
quantidade de feromônio deixada pela formiga k na aresta (i,j).
A contribuição de cada formiga para o depósito de feromônio em cada passo
de seu caminho é proporcional à qualidade da solução obtida por aquela formiga:
Quanto melhor for a qualidade da solução, maior é a quantidade de feromônio
depositado. Se o caminho da formiga k não inclui a aresta (i,j) então o valor de
k
ij
τ
∆
é zero.
ACO
Passo 1: Inicialização
Definir valor inicial do feromônio;
Definir solução com o pior valor possível;
Inicializar caminho com vazio;
Passo 2: Construção
Para cada formiga k repetir {
Calcular os valores de η;
Escolher o estado para movimentação usando a
probabilidade dada pela fórmula(17);
Adicionar o movimento escolhido ao conjunto inviáveis
κ
;
} Até que a formiga κ obtenha uma solução completa
ou desista;
[melhorar a solução com busca local] Opcional
Se (valor da nova solução é melhor que solução) {
Atualizar solução com o novo valor;
Atualizar caminho associado ao novo valor;
}
Passo 3: Atualização do feromônio
Para cada movimento do caminho da solução {
Calcular
k
ij
τ
∆
Atualizar a matriz de feromônios usando a fórmula (18)
}
Passo 4: Condição de término
Se (condição de término não satisfeita) vá para o passo2;
Figura 10: Algoritmo ACO genérico, baseado em Maniezzo & Carbonaro (1999)
A Figura 10 apresenta um procedimento ACO genérico em pseudo-código.
Primeiramente a matriz de feromônios é inicializada. Depois cada formiga tem a
PUC-Rio - Certificação Digital Nº 0321287/CA
56
chance de construir a sua própria solução completa ou desistir. A desistência
ocorre caso a formiga chegue a um estado sem possibilidade de movimento e não
estiver ainda com uma solução completa. Depois disso, o rastro de feromônio ao
longo dos caminhos percorridos é atualizado e finalmente a condição de término é
testada (e.g. depois de decorrido um determinado tempo de execução) para definir
se uma nova iteração será necessária. Um exemplo de condição de término seria
Em alguns casos, usa-se um algoritmo de busca local para aperfeiçoar cada
solução encontrada.
Embora a convergência do algoritmo ACO tenha sido provada (Dorigo &
Blum, 2005), não há estudos disponíveis na literatura sobre a velocidade de
convergência. Sendo assim, não há outra forma de medir o desempenho do
algoritmo a não ser a execução de extensos testes experimentais (Dorigo &
Stützle, 2004).
Dorigo et al. (2006), apresenta a família de algoritmos ACO como um
conjunto de métodos para resolver vários problemas de otimização combinatória,
quer sejam estáticos ou dinâmicos. A Tabela 1 mostra algumas aplicações bem
sucedidas da metaheurística ACO para resolver problemas clássicos de
otimização, e os respectivos anos de publicação.
Tabela 1: Aplicações de ACO, baseada em Dorigo, Birattari e Stützle, 2006
TIPO DE PROBLEMA
NOME DO PROBLEMA
AUTORES
ANO
ROTEAMENTO
CAIXEIRO VIAJANTE
DORIGO ET AL
1991, 1996
DORIGO E GAMBARDELLA
1997
STÜTZLE E HOOS
1997, 2000
ROTEAMENTO DE VEÍCULOS
GAMBARDELLA ET AL
1999
REIMANN ET AL
2004
ORDENAÇÃO SEQUENCIAL
GAMBARDELLA E DORIGO
2000
ATRIBUIÇÃO
ATRIBUIÇÃO QUADRÁTICA
STÜTZLE E HOOS
2000
MANIEZZO
1999
TABELA DE CURSOS
SOCHA ET AL
2002,2003
COLORAÇÃO DE GRAFOS
COSTA E HERTZ
1997
AGENDAMENTO
PROGRAMAÇÃO DE PROJETOS
MERKLE ET AL
2002
ATRASO TOTAL PONDERADO
DEN BESTEN ET AL
2000
MERKLE E MIDDENDORF
2000
PROGRAMAÇÃO DA PRODUÇÃO
BLUM
2005
SUBCONJUNTO
RECOBRIMENTO DE CONJUNTOS
LESSING ET AL
2004
ÁRVORES DE CARDINALIDADE i
BLUM E BLESA
2005
MOCHILA MÚLTIPLO
LEGUIZAMÓN E MICHALEWICZ
1999
CLIQUE MÁXIMO
FENET E SOLNON
2003
OUTROS
SATISFAÇÃO DE RESTRIÇÕES
SOLNON
2000,2002
REGRAS DE CLASSIFICAÇÃO
PARPINELLI ET AL
2002
MARRTENS ET AL
2006
REDES BAYESIANAS
CAMPOS ET AL
2002
ENROLAMENTO DE PROTEÍNAS
SHMYGELSKA E HOOS
2005
DOCKING PROTEÍNA-LIGANTE
KORB ET AL
2006
Lista não exaustiva de aplicações do algoritmo ACO agrupados por tipo de problema
PUC-Rio - Certificação Digital Nº 0321287/CA
57
Dorigo & Blum (2005) é uma boa referência teórica sobre a metaheurística
ACO. Este trabalho apresenta uma revisão dos resultados sobre convergência do
algoritmo, discute as relações entre ACO e outros métodos de aproximação e
identifica algumas questões em aberto como motivação para pesquisas futuras.
As referências mais importantes sobre ACO para este trabalho foram as que
apresentam casos de solução de problemas de otimização multi-objetivo em
sistemas de transporte. Neste contexto se destacam Reimann (2002), que
apresenta um algoritmo ACO com duas colônias de formigas para resolver um
problema de transporte com caminhões de carga similar ao PPOLM, Sabino
(2004) que é a pesquisa precursora deste trabalho e que apresenta um protótipo de
algoritmo para resolver o PPOLM e Gambardella et al. (2003), que apresenta duas
ferramentas para assistir o planejamento de roteiro em várias fases de um processo
de entrega de encomendas.
PUC-Rio - Certificação Digital Nº 0321287/CA
4
Metodologia de solução do problema
A direção é mais importante que a velocidade.
ROBERTO SCARINGELLA
Este capítulo apresenta uma visão geral da modelagem e método de solução
proposto para resolver o PPOLM. A estratégia de solução é baseada no uso da
metaheurística ACO.
4.1.
Escolha dos algoritmos
Os seguintes fatores foram os principais motivadores para a escolha da
metaheurística ACO para a construção do plano de trabalho das locomotivas de
manobra no PPOLM :
A facilidade de implementação e manutenção: Além da
implementação muito simples, novas restrições e características do
problema são adicionadas com mínima revisão de código. Estas
características se tornaram evidentes durante a fase de desenho e
codificação da aplicação;
A oportunidade de explorar o estado da arte em tendências e
ferramentas: o último workshop bianual sobre ACO e Swarm
Intelligence, realizado em Bruxelas, na Bélgica em 2006, contou
com 50 trabalhos apresentados a partir de uma seleção que
aproveitou 42% do total de trabalhos submetidos. Além disso, o
prêmio concedido pelo IFORMS-RASIG Group ao trabalho em
Sabino (2002), o qual é um dos precursores deste, mostrou o
interesse por esta nova abordagem, tanto pela comunidade
PUC-Rio - Certificação Digital Nº 0321287/CA
59
acadêmica como pelos profissionais da área de planejamento
ferroviário;
Os bons resultados em pesquisas anteriores: ACO tem se destacado
como uma técnica eficiente e flexível para resolver problemas de
otimização combinatória do tipo do PPOLM (Reimann, 2002;
Gambardella et al., 2003).
O algoritmo de Dijkstra foi a base para a implementação da lógica de
determinação da melhor rota dos comboios pelo pátio. Esta escolha foi feita
considerando os critérios de flexibilidade, escalabilidade, desempenho e
complexidade de implementação deste algoritmo comparado a outros métodos de
solução de problemas de determinação de caminho mínimo. A avaliação destes
critérios foi feita baseada nos modelos de desempenho apresentados em Foster
(2006) para projeto e implementação de programas eficientes.
4.2.
Construção do plano de trabalho das locomotivas de manobras
O algoritmo principal desenvolvido para solução do problema de
programação das locomotivas foi denominado YoYo - mnemônico de Yard
Operation Yeld Optimization. O algoritmo YoYo foi construído tomando como
base o algoritmo competATS, apresentado em Reimann (2002), que é uma
implementação de otimização com colônia de formigas onde há duas colônias
com regras de prioridade diferentes. Uma colônia, chamada de colônia Empty
Move (EM), busca soluções com baixo custo variável e para isso procura executar
as manobras de modo a minimizar o deslocamento total das locomotivas de
manobras. A outra colônia de formigas, chamada de colônia Waiting Time (WT)
busca soluções com baixo custo fixo, procurando assim reduzir a quantidade de
locomotivas de manobras necessárias.
As características do problema é que vão definir qual das duas colônias vai
conseguir chegar à melhor solução. Por exemplo, se as janelas de tempo são
curtas, então a colônia WT não vai ter muitas chances de atingir sua meta que é a
maximizar a utilização das locomotivas de manobras através da redução do tempo
de espera no ponto de coleta no caso da locomotiva chegar antes do horário
mínimo permitido. Por outro lado, se as janelas de tempo são longas a colônia WT
PUC-Rio - Certificação Digital Nº 0321287/CA
60
tende a obter melhores resultados. Considerando que tanto a redução do tempo de
espera quanto a redução dos movimentos vazios minimiza o custo total, a idéia é
explorar o ponto forte de ambas as colônias. Em primeiro lugar, o número de
formigas de cada colônia não é constante. Depois de cada iteração, parte das
formigas da colônia cuja média das soluções encontradas em cada iteração é
menor migram para a outra colônia, dando assim maior capacidade computacional
à outra colônia na próxima iteração. Além disso, algumas formigas utilizam não
só o feromônio de suas próprias colônias, mas também o feromônio da outra
colônia para influenciar suas decisões sobre como prosseguir na construção de
seus caminhos. As Formigas que utilizam somente o feromônio de suas colônias
são chamadas formigas nativas e as formigas que consideram também o
feromônio da outra colônia são chamadas formigas espiãs. O balanceamento entre
o número de formigas nativas e espiãs de uma colônia é definido em função da
melhor solução encontrada por cada colônia na iteração anterior.
Formigas das duas colônias constroem seus caminhos da mesma forma:
Iniciando no tempo t=0, uma locomotiva é escolhida e manobras são atribuídas
sequencialmente a esta locomotiva. A cada nova manobra atribuída, o tempo é
atualizado de acordo com o tempo necessário para realização da manobra. Novas
manobras são atribuídas até o fim do horizonte de planejamento ou até que, em
função das restrições do problema, não haja mais nenhuma atribuição possível
para esta locomotiva. Neste ponto, outra locomotiva de manobras é alocada para
compor a solução, o tempo volta ao valor zero e o processo de atribuição de
manobras a locomotivas continua. Este procedimento é repetido até que todas as
manobras estejam atribuídas ou até que haja mais nenhuma locomotiva que possa
ser colocada em uso. Para decidir qual manobra ou qual locomotiva será
adicionada ao seu caminho as formigas utilizam a atratividade η e a quantidade de
feromônio τ armazenada anteriormente por outras formigas ao longo do caminho.
Em suma, uma formiga constrói o seu caminho partindo de uma solução
inicial contendo apenas uma locomotiva e acrescentando elementos, que podem
ser manobras ou locomotivas, visando formar soluções parciais mais completas
até chegar a uma solução do PPOLM, ou seja, um plano de trabalho que envolva
todas as manobras a serem executadas no horizonte de planejamento dado.
PUC-Rio - Certificação Digital Nº 0321287/CA
61
O diagrama da Figura 11 mostra uma solução de um PPOLM. Os quadrados
representam locomotivas e os círculos representam manobras. Os segmentos
horizontais que unem cada elemento ao seu sucessor representam passos, ou seja,
mudanças de estado que correspondem à adição de itens a uma solução parcial,
formando assim o caminho da formiga.
Figura 11: Caminho de uma formiga com três passos destacados
Há três passos destacados na Figura 11, assinalados com os números 1, 2 e
3, indicando os três tipos possíveis de mudança de estado, conforme abaixo:
1. Nova Manobra (NOMA): Se a última operação feita foi a adição de
uma manobra no plano de trabalho de uma locomotiva e ainda é
possível adicionar mais manobras ao plano de trabalho desta mesma
locomotiva, o item adicionado será então mais uma manobra para
mesma locomotiva;
2. Nova Locomotiva (NOLO): Se a última operação feita foi a adição
de uma manobra ao plano de trabalho de uma locomotiva, mas não
é possível adicionar mais manobras ao plano de trabalho desta
mesma locomotiva, o item adicionado será uma nova locomotiva;
3. Primeira manobra (PRIMA): Se a última operação foi a adição de
uma locomotiva, o item adicionado será a primeira manobra desta
locomotiva.
Como em qualquer algoritmo de otimização baseado em colônias de
formigas, a mudança de estado, ou seja, o acréscimo de um novo item no caminho
da formiga depende da atratividade η e da quantidade de feromônio τ existente nas
arestas do grafo G(V,A) que ligam o nó i atual a cada um dos nós candidatos a ser
o próximo nó daquele caminho. Assim, as formigas selecionam a próxima
locomotiva, ou a próxima manobra, baseadas na atratividade, que guia o processo
construtivo para a minimização da função objetivo, e na quantidade de feromônio,
2
1
3
PUC-Rio - Certificação Digital Nº 0321287/CA
62
o qual fornece informações históricas sobre a qualidade das soluções obtidas nas
iterações anteriores.
O algoritmo CompetAnts é apresentada na Figura 12. Primeiramente são
definidas as soluções iniciais para as duas colônias. Depois disso, é determinado o
número de formigas nativas e espiãs de cada colônia. Em seguida, é feita uma
chamada ao algoritmo ACO (apresentado na Figura 10) para cada tipo de colônia.
Finalmente é apresentado o resultado do procedimento.
Algoritmo CompetAnts
Leitura dos parâmetros;
Initialização do sistema;
Execução da primeira iteração
Chamada ACO para a colônia EM;
Chamada ACO para a colônia WT;
Para
i
de 2 até
num_max
_itera
ções
Adaptação do número de formigas das colônias basead
o no
custo médio;
Determinação do número de espiões baseado na melhor
solução;
Execução da otimização
Chamada ACO para a colônia EM;
Chamada ACO para a colônia WT;
Fim Para
Gravação do resultado;
Figura 12: Algoritmo CompetAnts, conforme Reimann (2002)
4.3.
Cálculo da atratividade
A atratividade η é uma informação básica para a definição da fórmula que
guia o processo incremental de construção do caminho das formigas. Cada colônia
utiliza uma fórmula de atratividade diferente para as mudanças de estado.
A fórmula seguinte é usada para o cálculo da atratividade para a colônia
WT. Ela procura expressar a produtividade das locomotivas de manobras,
considerando improdutivo o tempo de espera, bem como o tempo de
deslocamento escoteira da locomotiva de manobras:
PUC-Rio - Certificação Digital Nº 0321287/CA
63
( )
WT
ij
t
η
=
4 [ 2 ( , )]
j j
K DTWE UT i t
e
− ⋅ + ⋅
se (i,j) é um passo
viável do tipo NOMA
ou PRIMA,
(19)
1
se (i,j) é um passo
viável do tipo NOLO,
0 nos demais casos
onde DTWE
j
é o instante final da janela de entrega e UT
j
(i,t) é o tempo
improdutivo estimado com a adição da manobra j ao caminho da formiga.
Caso o próximo elemento a ser adicionado no caminho seja uma manobra, o
valor de DTWEj é exatamente o valor fornecido como dado de entrada associado
àquela manobra e o valor de UT
j
(i,t) é dado pela seguinte fórmula:
( , ) ( ) ( , )
j j
UT i t WT t LT i j
= +
(20)
onde WT
j
(t) é a diferença entre o horário do início da janela de coleta e o horário
estimado de chegada da locomotiva de manobras à linha de coleta e LT(i,j) é o
tempo estimado de deslocamento da locomotiva de manobras escoteira até a linha
de coleta dos vagões. Vale notar que o valor de WT
j
(t) só é positivo se a
locomotiva de manobras chegar à linha de coleta antes do início da janela de
coleta. Neste caso, WT
j
(t) representa o tempo improdutivo que a locomotiva de
manobras tem que esperar até o horário mínimo permitido de início da manobra.
Os valores relacionados às janelas de tempo DTWE
j
e WT
j
(t) privilegiam o
encadeamento de manobras que estejam próximas umas das outras em relação ao
tempo. O valor de LT(i,j) faz com que a atratividade assuma valores menores
quanto maior é o tempo improdutivo de deslocamento das locomotivas na
condição escoteiras.
Os fatores 2 e 4 são exatamente os mesmos usados no algoritmo
CompetAnts e foram definidos em um estudo preliminar para ajuste de
parâmetros. A constante K foi introduzida durante os testes computacionais com
valores reais coletados na rotina de um pátio ferroviário e deve ser escolhido
PUC-Rio - Certificação Digital Nº 0321287/CA
64
convenientemente para evitar que o valor de
WT
ij
η
assuma um valor muito próximo
de zero.
O cálculo da atratividade para a colônia EM utiliza a seguinte fórmula:
EM
ij
η
=
,
16 ( )
i j
r r
e
− +
− ⋅ϒ
se (i,j) é um passo
viável do tipo NOMA,
(21)
,
16 ( )
j
e r
e
+
+
− ⋅ϒ
se (i,j) é um passo
viável do tipo PRIMA,
1
se (i,j) é um passo
viável do tipo NOLO,
0 nos demais casos
Nesta fórmula, seguindo o mesmo princípio do algoritmo CompetAnts, o
valor da atratividade é influenciado somente pela distância percorrida pela
locomotiva de manobra no modo escoteira até o ponto de coleta dos vagões da
manobra j, de modo que as formigas tendem a construir caminhos com menor
distância total percorrida. O fator -16 é exatamente o mesmo usado no algoritmo
CompetAnts, a função
ϒ
é a mesma da fórmula
(9)
, da página 36 e as linhas
i
r
−
e
j
r
+
são as linhas de entrega da manobra anterior e a linha de coleta da próxima
manobra respectivamente, sendo, naturalmente, a linha
i
r
−
substituída pela linha
e
+
no caso da mudança de estado do tipo PRIMA.
Tanto no caso do custo variável estático quanto no caso do custo variável
dinâmico, a distância e conseqüentemente o custo de deslocamento entre a linha
de coleta e a linha de entrega de uma manobra, fixado o instante de início deste
deslocamento, é constante. Assim, somente os deslocamentos na condição
escoteira podem ser minimizados para cumprir o objetivo da população EM, e
deste modo, a fórmula (21), utilizada no algoritmo CompetAnts, é apropriada para
o PPOLM.
PUC-Rio - Certificação Digital Nº 0321287/CA
65
É importante observar que, para as colônias WT e EM, a escolha da nova
locomotiva a ser alocada nas mudanças de estado do tipo NOLO depende somente
da quantidade de feromônio.
4.4.
Regras de decisão
As regras de decisão são as mesmas apresentadas em Reimann (2002). Uma
formiga nativa k
n
decide qual o próximo item a ser adicionado ao seu caminho
baseado na distribuição de probabilidade expressa por:
( )
n
k
ij
p t
=
[ ] [ ( )]
[ ] [ ( )]
h N
t
ij ij
t
ij ij
β
α
τ η
β
α
τ η
∈
∑
se
j
∈
(22)
0 caso contrário
onde é o conjunto de nós que, ao serem adicionados ao caminho da formiga
depois do nó i, não violam nenhuma das restrições do problema, α e β são os
parâmetros que determinam a influência relativa do feromônio e da atratividade,
( )
ij
t
η
é o valor da atratividade, calculado usando a fórmula (19) ou (21), de
acordo com a colônia a que pertence a formiga nativa k
n
e τ
ij
é a quantidade de
feromônio depositada no arco (i, j).
A regra de decisão utilizada pelas formigas nativas é a regra clássica do
algoritmo Ant Systems conforme Dorigo & Stützle (2004). Uma formiga espiã k
f
utiliza uma regra de decisão segundo uma distribuição de probabilidade baseada
na média ponderada entre o feromônio de sua própria colônia
,
n
i j
τ
e o feromônio
da outra colônia
,
f
i j
τ
dada por:
( )
f
k
ij
p t
=
[ (1 ) ] [ ( )]
[ (1 ) ] [ ( )]
n f
ij ij ij
n f
ih ih ih
h N
t
t
β
α
β
α
χ τ χ τ η
χ τ χ τ η
∈
⋅ + − ⋅
⋅ + − ⋅
∑
se
j
∈
(23)
0 caso contrário.
onde , α e β são os mesmos parâmetros da fórmula (22) e 0 ≤ χ ≤ 1 representa a
importância do feromônio da própria colônia em relação ao feromônio da outra
colônia.
PUC-Rio - Certificação Digital Nº 0321287/CA
66
Tanto as formigas nativas quanto as espiãs consideram, ao construírem seus
caminhos, todas as restrições apresentadas nas fórmulas de
(2)
a
(6)
, páginas 36 e
33, e mais a restrição de precedência da fórmula
(14)
, página 41.
No caso NOLO, como a atratividade é sempre 1, somente o feromônio
influencia na escolha da próxima locomotiva a ser alocada.
4.5.
Regras de atualização de feromônio
Foram testadas duas regras de atualização de feromônio. A primeira,
chamada de CME, usa o mesmo método proposto em Reimann (2002) e a
segunda, chamada RNK, segue a regra intitulada rank based ant system proposta
em Bullnheimer et al. (1999).
4.5.1.
Regra CME
Depois que todas as formigas tiveram a oportunidade de construir a sua
solução, os passos que compõem o caminho percorrido pelas formigas que
obtiveram as Λ melhores soluções são consideradas para atualização da
quantidade de feromônio.
Em primeiro lugar, a quantidade de feromônio destes arcos é reduzida. Esta
metáfora da evaporação do feromônio ocorre apenas uma vez para cada arco,
mesmo que esta faça parte de mais de um dos Λ caminhos. Em seguida é
depositada em cada arco uma quantidade de feromônio proporcional à qualidade
da solução que utilizou aquele arco. A regra de evaporação e depósito de
feromônio é definida pela fórmula:
1
, ( , ) ,
ij ij
i j J
λ
λ
τ ρ τ τ
Λ
=
= ⋅ + ∆ ∀ ∈
∑
e
0 1
ρ
≤ ≤
(24)
onde ρ é o parâmetro que define persistência do feromônio. O primeiro termo
desta soma especifica a evaporação e o segundo termo é um somatório que define
a quantidade
ij
λ
τ
∆
de feromônio a ser adicionado em cada arco de um dos Λ
melhores caminhos.
Apenas as formigas que obtiveram as Λ melhores soluções da iteração
depositam feromônio e a evaporação só ocorre nos caminhos percorridos por estas
PUC-Rio - Certificação Digital Nº 0321287/CA
67
formigas. A fórmula que define a quantidade de feromônio a ser depositada pela
formiga classificada na posição λ entre as Λ melhores é a seguinte:
ij
λ
τ
∆
=
1
1
λ
−
−
Λ
se
0
λ
≤ ≤ Λ
(25)
0 caso contrário
Nesta fórmula, proposta em Reimann (2002), o valor da função objetivo
apurado em iterações anteriores não é usado para o cálculo de
ij
λ
τ
∆
e o número Λ é
igual ao número total de formigas dividido por 16.
Este método de atualização da quantidade de feromônio é o mesmo do
algoritmo CompetAnts e será chamado neste trabalho de CME.
4.5.2.Regra RNK
Além do método original de atualização de feromônio usado no algoritmo
CompetAnts, foi testada uma variação chamada rank-based ant system,
referenciada neste trabalho como RNK, onde a formiga que obteve a melhor
solução até então deposita a maior quantidade de feromônio em cada iteração. De
acordo com Dorigo & Stützle (2004), o rank based ant system tem desempenho
um pouco melhor que o elitist ant system e significativamente melhor que o ant
system original. Esta posição de destaque do método RNK em relação a outros
métodos de atualização da quantidade de feromônio na trilha das formigas
despertou o interesse em considerar a regra RNK como alternativa à regra CME
para a solução do PPOLM.
No RNK, antes de realizar a atualização da quantidade de feromônio, as
formigas são classificadas em ordem não decrescente de custo da solução e a
quantidade de feromônio que uma formiga deposita depende da posição λ da
formiga nesta classificação. Em cada iteração apenas as primeiras (ω-1) formigas
e a formiga que obteve o melhor resultado até então podem depositar feromônio
em seus caminhos. A formiga que obteve o melhor resultado, considerando todas
as iterações ocorridas até então e incluindo a iteração atual dá a maior
contribuição, depositando feromônio com peso ω. A λ-ésima melhor formiga da
iteração atual contribui com peso max{0,ω-λ}. Sendo assim, a atualização do
feromônio é feita baseada na seguinte fórmula:
PUC-Rio - Certificação Digital Nº 0321287/CA
68
1
1
( )
ω
λ
λ
τ
τ ρ τ ω λ τ ω
−
=
+ ∆
= ⋅ − ⋅ ∆ + ⋅
∑
bs
ij ij ij
ij
(17)
onde
1/
ij
C
λ
λ
τ
=
∆
,
1/
bs bs
ij
C
τ
∆ =
,
bs
C
é o custo da melhor solução obtida até
então e
C
λ
é o custo da solução da λ-ésima melhor formiga na iteração atual.
Todos os custos são calculados através da fórmula
(16)
.
Uma diferença importante entre as duas regras de atualização de feromônio
propostas neste trabalho é que na regra RNK usa-se o custo
bs
C
para calcular a
quantidade de feromônio a ser acrescentada nos arcos dos melhores caminhos.
Como a formiga que obteve a melhor solução até então não necessariamente é da
iteração atual, este processo faz com que informação sobre a qualidade das
soluções anteriores seja passada para iterações seguintes, o que não ocorre na
regra CME, pois a mesma utiliza informações sobre a qualidade das soluções
obtidas somente na iteração atual. Testes computacionais apresentados em Sabino
et al. (2006) sugerem que o método RNK conduz a melhores resultados.
4.6.Detalhes sobre a implementação do algoritmo YoYo
Este item apresenta as principais rotinas utilizadas na implementação do
algoritmo YoYo, desenvolve uma estimativa de sua ordem de complexidade e
apresenta a estrutura de dados mais importante do algoritmo, a qual foi utilizada
para armazenamento das informações sobre feromônio.
4.6.1.
Lógica das principais rotinas
Este item apresenta o pseudocódigo das principais rotinas utilizadas na
implementação do algoritmo YoYo. A rotina principal ACO usa, em sua lógica, a
rotina RegraDecisão, que por sua vez usa as rotinas SortearResposta e Viável.
4.6.1.1.
Rotina ACO
O pseudocódigo da rotina ACO utilizada no algoritmo YoYo é apresentado
na Figura 13. O número total de formigas da colônia, o número de formigas espiãs
e o tipo de colônia (i.e. EM ou WT) são informados como parâmetros de entrada.
Inicialmente, são definidas seis matrizes de feromônio (apresentadas na Figura 17)
PUC-Rio - Certificação Digital Nº 0321287/CA
69
e é reservado espaço de memória para as estruturas de dados que armazenam
valores de custo para a função objetivo, e os respectivos caminhos encontrados
pelas melhores formigas. A variável que controla o tipo de item a ser adicionado
no caminho das formigas é inicializada com o valor PRIMA, pois todo caminho
começa por uma locomotiva e o primeiro item a ser identificado é então a
primeira manobra daquela locomotiva.
Seguem-se as iterações de construção de caminhos. Todas as m formigas
têm uma chance de construir seu caminho iniciando por cada locomotiva da frota
dada. Após definir se a formiga é nativa ou espiã, a construção do caminho
prossegue com a chamada da rotina RegraDecisão para definir qual será o
próximo item do caminho e, em seguida proceder os ajustes apropriados no tempo
e acrescentar o novo item na estrutura de dados que armazena os elementos do
caminho. Ao final da repetição de construção do caminho, caso se tenha obtido
uma solução viável (i.e., se o caminho contém as linhas lógicas de coleta e entrega
de todas as ordens de serviço do conjunto R), calcula-se o valor da função
objetivo e, caso este valor esteja entre os melhores, atualiza-se a lista dos
melhores caminhos. Depois que todas as formigas tiveram a chance de construir
seus caminhos, segue-se a atualização da matriz de feromônio.
PUC-Rio - Certificação Digital Nº 0321287/CA
70
ACO (num. formigas, num. espiãs, tipo de colônia)
Passo 1: Inicialização
01 Alocar memória e inicializar matrizes de feromônio;
02 Ler os valores de η;
03 Definir valor da solução com o pior valor possível;
04 Alocar memória e inicializar solução com caminho vazio;
05 Ler número de melhores formigas a ser considerado;
06 Alocar memória para armazenar valores das melhores
soluções e caminho das melhores formigas;
07 Inicializar item = PRIMA;
Passo 2: Construção
08 Para cada uma das |E| locomotivas repetir {
09 Inicializar caminho com a locomotiva v;
10 Zerar tempo;
11 Para cada uma das m formigas repetir {
12 Definir se a formiga vai ser nativa ou
espiã baseado no número especificado de
formigas espiãs;
13 Enquanto o caminho da formiga não contém
todas as manobras repetir {
14 Chamar rotina RegraDecisão (item, resposta)
15 Se item é NOLO {
16 Se resposta é OK {
17 Zerar tempo;
18 item = PRIMA;
19 Adicionar locomotiva ao
caminho;
}
20 Se não, interromper repetição;
}
21 Se item é PRIMA {
22 Se resposta é OK {
23 Atualizar tempo;
24 item = NOMA;
25 Adicionar manobra ao caminho;
}
26 Se não, interromper repetição;
}
27 Se item é NOMA {
28 Se resposta é OK {
29 Atualizar tempo;
30 item = NOMA;
31 Adicionar manobra ao caminho;
}
32 Se não, item = NOLO;
}
} /* fim da repetição para construção do caminho
33 Se caminho tem todas as manobras {
34 Computar valor da função objetivo (custo);
35 Atualizar lista dos melhores caminhos;
36 Atualizar média do custo;
}
} /* fim da repetição para cada formiga
37 Se alguma formiga encontrou solução então atualizar a
matriz de feromônio usando a fórmula (18);
} /* fim da repetição para cada locomotiva
Figura 13: Rotina ACO usada no algoritmo YoYo
PUC-Rio - Certificação Digital Nº 0321287/CA
71
4.6.1.2.
Rotina RegraDecisão
A rotina RegraDecisão, conforme apresentado na Figura 14, processa a
mudança de estado em cada passo da construção do caminho da formiga, ou seja,
identifica qual a próxima locomotiva ou a próxima manobra a ser adicionada ao
caminho. Para tanto, é especificado o tipo de item que se quer adicionar e espera-
se receber uma resposta identificando o item ou, em caso de inviabilidade, a
informação de que nenhum item pôde ser identificado.
RegraDecisão (item, resposta)
01 Alocar e inicializar lista de itens viáveis;
02 Se item é NOLO {
Para cada locomotiva v repetir {
Se v ainda não foi usada neste caminho {
Definir v como viável;
Calcular e armazenar probabilidade de escolha
desta locomotiva utilizando a fórmula
(22)
, caso
a formiga seja nativa ou utilizando a
fórmula
(23)
, caso contrário;
}
}
Se for encontrada alguma locomotiva viável {
SortearResposta (locomotivas viáveis, resposta);
Retornar resposta;
}
}
Se item é PRIMA ou NOMA {
Para cada manobra v repetir {
Se Viável (v,item) {
Adicionar v à lista de itens viáveis;
Calcular e armazenar probabilidade de escolha
desta manobra utilizando a fórmula
(22)
, caso
a formiga seja nativa ou utilizando a
fórmula
(23)
, caso contrário;
}
}
Se for encontrada alguma manobra viável {
SortearResposta (manobras viáveis, resposta);
Retornar resposta;
}
}
Figura 14: Rotina RegraDecisão, usada na rotina ACO
4.6.1.3.
Rotina SortearResposta
Esta rotina implementa o método de seleção por roleta, muito utilizado na
seleção de cromossomas em algoritmos genéticos, como em Obitko (1998).
Primeiro gera-se um número aleatório entre 0 e 1. Depois, a lista de itens viáveis é
PUC-Rio - Certificação Digital Nº 0321287/CA
72
percorrida, somando-se a probabilidade de escolha de cada item até que esta soma
ultrapasse o número aleatório gerado. Quando isto ocorre, o item da lista que
estava selecionado é o escolhido. O pseudocódigo da rotina SortearResposta está
apresentando na Figura 15.
SortearResposta (lista de itens viáveis, respo
sta)
01 Zerar soma acumulada;
03 Gerar um número aleatório rnd, tal que 0 ≤ rnd ≤ 1;
04 Para cada item viável e enquanto soma < rnd repetir {
05 Selecionar item viável;
06 Acumular em soma a probabilidade de escolha do item
viável selecionado;
}
07 resposta = item selecionado;
08 Retornar resposta;
}
09 Se não, resposta é [não OK];
Figura 15: Rotina SortearResposta, usada rotina RegraDecisão
4.6.1.4.
Rotina Viável
A rotina Viável verifica se a inclusão da manobra no caminho sendo
construído pela formiga pode ser feita atendendo todas as restrições dadas. Esta
rotina retorna um valor falso ou verdadeiro para a rotina RegraDecisão de acordo
com o resultado da verificação feita. Esta rotina tem uma lógica linear e apenas
valida, seqüencialmente, cada restrição operacional do PPOLM, conforme
apresentado na Figura 16.
Viável ()
01
Se esta manobra já consta no caminho atual, retorne falso;
02 Se a locomotiva que vai executar esta manobra não pode
chegar à linha de coleta antes do final da janela de tempo
de coleta, retorne falso;
03 Se o desacoplamento da locomotiva não pode ocorrer durante
a janela de tempo de entrega, retorne falso;
04 Se a capacidade de tração da locomotiva não é suficiente
para mover o conjunto de vagões desta manobra, retorne
falso;
05 Se esta manobra tem outra manobra predecessora que ainda
não está com a coleta já realizada, retorne falso;
06 Caso contrário, retorne verdadeiro.
Figura 16: Rotina Viável, usada rotina RegraDecisão
4.6.2.
Estimativa da ordem de complexidade
Para estimar a ordem de complexidade do algoritmo CompetAnts aplicado
no contexto da solução do PPOLM, basta observar que no algoritmo ACO da
PUC-Rio - Certificação Digital Nº 0321287/CA
73
Figura 13 da página 70, em cada iteração, iniciando por cada uma das |E|
locomotivas disponíveis no pátio, m formigas tentam construir uma solução que
contém, no máximo, (|E|+2n) passos, onde n é o número de ordens de serviço. Em
cada passo na construção do caminho, cada formiga deve escolher uma opção de
mudança de estado em um conjunto com menos de n opções. Temos então a
expressão |E|.m.(|E|+2n).n como primeira estimativa para a complexidade de
tempo do algoritmo proposto. Note que a complexidade do algoritmo proposto
não depende do número |E| de locomotivas, já que este número é limitado pela
quantidade de ordens de serviço, pois, no pior caso, cada ordem de serviço é
executada por uma locomotiva diferente. Outro detalhe importante é que todas as
demais operações do algoritmo CompetAnts, tais como a atualização e depósito de
feromônio são O(n
2
). Finalmente, deve-se considerar as duas possibilidades para
cálculo do custo variável. No caso do custo variável estático, tem-se uma tabela
com os valores das distâncias entre cada par de nós do grafo G´ armazenado em
uma matriz de adjacências de modo que o acesso é direto e não influencia na
complexidade do algoritmo. No caso do custo variável dinâmico, é necessário
refazer o cálculo para cada uma das possibilidades de mudança de estado. Este
cálculo é feito com o algoritmo de Dijkstra, que no pior caso tem ordem de
complexidade O(n
2
) (Black, 2006). Como o custo variável dinâmico é calculado
para cada uma das possibilidades de mudança de estado, tem-se um novo fator
O(n
2
) a ser considerado na complexidade final. Utilizando então a notação O e
considerando o que foi exposto acima, segue-se que a complexidade final de cada
iteração do algoritmo é O(m.n
2
) no caso de se utilizar o custo variável estático e
O(m.n
4
) no caso se utilizar o custo variável dinâmico. Desta forma, nota-se que o
algoritmo proposto é capaz de encontrar uma boa solução para o PPOLM com
ordem de complexidade polinomial e que o uso do custo variável dinâmico
aumenta o tempo de execução do algoritmo, em relação ao caso de uso do custo
variável estático, na proporção estimada do quadrado do número de ordens de
serviço do PPOLM.
4.6.3.Estrutura de dados para armazenar as informações de
feromônio
A quantidade de feromônio depositada em cada passo da construção do
caminho da formiga é armazenada em três matrizes de feromônio. Considerando
PUC-Rio - Certificação Digital Nº 0321287/CA
74
que há p= |R| manobras a serem executadas e q= |E| locomotivas disponíveis no
pátio, são utilizadas três matrizes, uma para cada um das três possibilidades
indicadas na Figura 11: Uma matriz (p x p) armazena a quantidade de feromônio
associado às possíveis decisões de adição de mais uma manobra para a mesma
locomotiva, uma matriz (p x q) armazena o feromônio associado às possíveis
decisões de adicionar uma das q locomotivas depois de executar uma das p
manobras e uma matriz (q x p) armazena a quantidade de feromônio associada à
decisão de adição da primeira manobra de uma locomotiva. Como é característica
do PPOLM a existência de algumas poucas locomotivas no pátio para atender a
dezenas de manobras, as três matrizes citadas acima são armazenas em uma única
estrutura matricial, onde são inutilizadas (q x q) elementos.
Como há duas colônias de formiga, cada uma com suas três matrizes de
feromônio, toda a informação de feromônio é então armazenada em uma única
matriz M ( p+q, p+q, 2 ), conforme indicado na Figura 17, onde o espaço de
memória não utilizado está indicado pela matriz quadrada (qxq) hachurada.
Figura 17: Matriz M (p+q, p+q, 2) de feromônios
p x p
p x q
q x p
q x q
p x p
p x q
q x p
q x q
Camadas de M =
2 colônias de
formiga
Colunas de M =
p manobras +
q locomotivas
Linhas de M =
p manobras +
q locomotivas
PUC-Rio - Certificação Digital Nº 0321287/CA
75
4.7.
Determinação da rota de cada passo
Se o custo variável a ser utilizado na função objetivo é estático, a rota de
cada passo do caminho de coleta e entrega depende somente do leiaute do pátio.
Desta forma, o caminho mínimo em G`, e o valor da distância percorrida neste
caminho para cada passo pode ser calculada uma vez e fornecida como dado de
entrada para o programa que implementa o algoritmo YoYo. Se o custo variável é
dinâmico, a determinação da rota mínima deve ser feita durante a construção do
caminho, pois a mesma varia com o tempo. A estrutura de dados para armazenar o
estado de ocupação das linhas do pátio e a rotina para determinação da rota
mínima e o cálculo do custo variável dinâmico estão detalhadas nos dois itens que
se seguem.
4.7.1.
A modelagem da alocação das linhas do pátio
Para identificar se há conflito de alocação de linhas quando as locomotivas
executam as manobras seguindo o plano definido pelo programa é fundamental
estabelecer um mecanismo de controle de alocação das linhas, de modo que dois
elementos (i.e. comboio, locomotiva escoteira ou conjunto de vagões) não possam
ocupar a mesma linha ao mesmo tempo.
Espaço e tempo são as variáveis de controle consideradas no processo e a
modelagem utilizada parte das seguintes premissas:
A velocidade de circulação ao longo de uma linha é um valor
constante, utilizado para todas as manobras. Para estimar este valor,
pode-se considerar o comprimento médio das linhas do pátio em
questão, as fórmulas para cálculo da curva de velocidade (Pachl,
2002) que consideram a oscilação da velocidade em função da
aceleração e frenagem da locomotiva e as fórmulas de Davis, que
consideram a resistência ao movimento.
Todo comboio cabe completamente dentro da linha de origem e
dentro da linha de destino. A garantia de capacidade das linhas de
origem e destino é um dos objetivos da etapa de identificação das
PUC-Rio - Certificação Digital Nº 0321287/CA
76
manobras, descrita no item 2.2.2. Vale observar que linhas de
circulação podem ser menores que o comprimento do comboio.
Linhas de circulação não podem ter vagões estacionados, ou seja, a
menos de ocupação por um comboio aguardando a liberação da linha
adiante, as linhas que estão entre a origem e o destino dos percursos
das locomotivas escoteiras e dos comboios estão sempre
desocupadas.
As duas últimas premissas acima tornam desnecessário considerar a
alocação das linhas pelos conjuntos de vagões estacionados antes e depois da
realização da manobra, restando somente a necessidade de controle de alocação
das linhas pelos comboios em deslocamento.
A modelagem das linhas do pátio e seu estado de alocação foi feita da
seguinte forma: Divide-se a duração do horizonte de planejamento
h
∆
em n
intervalos {i
0
, i
1
, i
2
,...,i
n-1
} de igual duração t
0
que são denominados intervalos de
alocação de linha, ou simplesmente intervalos, como serão referenciado neste
trabalho. Eventualmente, quando não existe
0
|
n n t h
∈ ⋅ = ∆
ℕ
, convenciona-se que
o intervalo i
n-1
é, excepcionalmente, o único intervalo com duração
0 0 0
( 1)
t h t n t
′
= ∆ − − <
.
O valor do intervalo t
0
deve ser definido levando em conta a velocidade
média de circulação das locomotivas de manobra no pátio e o tamanho das linhas
do pátio, de modo a representar uma duração conveniente para fins de controle de
alocação de linhas do pátio, conforme será mostrado adiante.
A fórmula proposta para estimativa inicial do valor do intervalo é a
seguinte:
0
min{ , }
2
v
a
l v G
t
s
′
′ ′
∈
=
(26)
onde
min{ ( ), }
l v v G
′
∈
é o tamanho da menor linha do pátio e s
a
é a velocidade
média de circulação das locomotivas de manobra no pátio.
A idéia da fórmula (26) é definir um tempo t
0
de modo que para percorrer
uma linha de pátio, uma locomotiva média, em condições normais, gaste pelo
menos dois intervalos. Esta fórmula pode ser utilizada para se estimar o valor
PUC-Rio - Certificação Digital Nº 0321287/CA
77
inicial de t
0
e a partir daí, podem ser feitos os ajustes necessários pela equipe de
planejamento de pátio.
Como será mostrado nos parágrafos que se seguem, o intervalo t
0
possibilita
a transformação do tempo em uma variável discreta, simplificando o controle de
alocação das linhas.
Figura 18: Horizonte de planejamento dividido em intervalos
A Figura 18 mostra o intervalo
h
∆
dividido em n intervalos de mesma
duração t
0
. Apenas os primeiros três intervalos e os últimos dois intervalos são
mostrados explicitamente. Os demais estão omitidos para simplificação do
desenho. Os círculos pretos nas extremidades dos intervalos indicam se esta
extremidade pertence ou não ao intervalo. Assim por exemplo,
2 0 0
{ | 2 3 }
i t t t t
= ≤ <
e
1 0 0
{ | ( 1) }
n
i t n t t nt
−
= − ≤ ≤
.
Diz-se que uma linha de pátio i está ocupada durante o intervalo i
k
se existe
um comboio, uma locomotiva ou um conjunto de vagões na linha i em algum
instante do intervalo i
k
.
O principal objetivo do intervalo é tornar o tempo uma variável discreta de
modo que seja possível mapeá-lo através de colunas de uma matriz. Desta forma,
o modelo de dados definido para controle da alocação das linhas se baseia numa
matriz e funciona da seguinte forma: Define-se uma matriz Z(n,l) onde n é o
número de intervalos em
h
∆
e l é o número de linhas do pátio. Desta forma, é
possível associar um intervalo a cada coluna da matriz Z e uma linha de pátio a
cada linha da matriz Z. Os elementos da matriz só podem assumir os valores 0 ou
1. O valor 1 no elemento z(i,j) da matriz Z indica que a linha i se encontra ocupada
i
0
i
1
i
2
i
(n-2)
i
(n-1)
(n-5)t
0
h
∆
t
0
PUC-Rio - Certificação Digital Nº 0321287/CA
78
durante o intervalo j e o valor 0 indica que a linha i se encontra livre durante o
intervalo j.
4.7.2.
O controle da alocação das linhas
O controle de alocação das linhas ocorre paralelamente à construção do
caminho das formigas. Inicialmente todos os elementos da matriz Z contêm o
valor zero. Em seguida, ainda como parte do processo de inicialização, atribui-se
o estado de ocupada durante todo o horizonte de planejamento para as linhas onde
as locomotivas estão localizadas inicialmente. A cada novo passo acrescentado no
caminho de coleta e entrega, calcula-se os intervalos em que cada linha estará
alocada no percurso e atualiza-se a matriz Z atribuindo-se o valor um aos
intervalos em que as linhas estão ocupadas e o valor zero aos intervalos em que
as linhas estão desocupadas.
O cálculo dos tempos de deslocamento se baseia nos seguintes valores
obtidos diretamente ou calculados a partir dos dados de entrada: tempo de
deslocamento da locomotiva na condição escoteira, tempo de espera, tempo de
transporte e tempo de serviço. É claro que o grau de precisão das informações
fornecidas pelo usuário (e.g. velocidade média das locomotivas, tempo de serviço
e comprimento das linhas do pátio) influencia diretamente a precisão dos cálculos
para controle de alocação das linhas.
As figuras e explicações que se seguem são usadas para mostrar as
premissas e o método utilizado para o cálculo dos tempos de alocação dos
intervalos. A Figura 19, na página 79, mostra as três primeiras linhas, as quatro
primeiras colunas e as quatro últimas colunas de uma matriz Z de alocação de
pátio. As linhas A, B e C do pátio estão associadas às primeiras linhas da matriz e
os n-1 intervalos que compõem o horizonte de planejamento estão associados às
respectivas colunas da matriz.
PUC-Rio - Certificação Digital Nº 0321287/CA
79
Matriz de alocação
de linhas do pátio
i
0
i
1
i
2
i
3
... i
n-4
i
n-3
i
n-2
i
n-1
Linha
A
1 0
0
0 ...
0
0 0 0
Linha B
0 0
0
1 ...
1
1 1 1
Linha C
0 1
1
0 ...
0
0 0 0
...
...
Figura 19: Matriz Z de alocação de pátio após movimento do comboio κ
Chamemos de κ o comboio composto de uma locomotiva e três vagões da
Figura 20. Se κ parte da linha A, passa pela linha C e depois fica estacionado até o
final do horizonte de planejamento na linha B, os valores da matriz mostram como
fica a representação correspondente à alocação das linhas do pátio para
representar este deslocamento de κ.
Figura 20: Comboio estacionado em A, pronto para se deslocar até B.
O comboio κ ocupa a linha A somente durante o primeiro intervalo, depois
passa pela linha C durante os intervalos i
1
e i
2
. Ao final do intervalo i
2
a linha C
está desocupada e o comboio κ já se encontra completamente na linha B, onde fica
estacionado até o fim do intervalo i
n-1
, ou seja, até o final do horizonte de
planejamento.
Como a unidade de tempo de alocação é medida em intervalos, se em algum
instante t, contido num intervalo i
k
, uma linha se encontra ocupada, então a linha é
considerada ocupada durante todo o intervalo i
k
.
Os tempos de ocupação dos intervalos são calculados considerando o
comprimento de cada linha por onde passa o comboio e o comprimento do
comboio. Uma linha por onde passa um comboio é considerada ocupada desde o
momento em que a frente do comboio atinge uma de suas extremidades até o
momento em que o final do comboio deixa a outra extremidade. A linha onde
Linha A
Linha C
Linha B
Linha D
PUC-Rio - Certificação Digital Nº 0321287/CA
inic
ialmente está localizado um comboio é considerada ocupada até que o
comboio deixe completamente a linha.
horizonte de planejamento ou até que uma manobra executada posteriormente
retire o
momento em que o início do comboio a atingir até o momento em que o centro do
comboio estiver alinhado com o seu centro, então a linha não será considerada
desocupada.
pronto para se deslocar até a linha B. A linha A aparece representada em preto e a
linha B em cinza. O ponto central de cada linha está assinalado com um
triângulo da cor da linha. Na figura estão indicados o comprimento
e os comprimentos das linhas A e B, que são
referência de cada linha é considerado o meio da linha. O meio do comboio é o
ponto de
inicialmente com o
com o
Figura
o deslocamento do comboio. Os respectivos tempos de deslocamento são então
obtidos como resultado da divisão do espaço percorrido pela velocidade de
deslocame
ialmente está localizado um comboio é considerada ocupada até que o
comboio deixe completamente a linha.
A linha de destino de um comboio é considerada ocupada até o fim do
horizonte de planejamento ou até que uma manobra executada posteriormente
retire o
comboio de lá.
momento em que o início do comboio a atingir até o momento em que o centro do
comboio estiver alinhado com o seu centro, então a linha não será considerada
desocupada.
A
Figura
pronto para se deslocar até a linha B. A linha A aparece representada em preto e a
linha B em cinza. O ponto central de cada linha está assinalado com um
triângulo da cor da linha. Na figura estão indicados o comprimento
e os comprimentos das linhas A e B, que são
referência de cada linha é considerado o meio da linha. O meio do comboio é o
ponto de
referência do comboio. Assim, o meio do comboio está alinhado
inicialmente com o
com o
meio
da linha B.
Figura
21
: Dimensões envolvidas no cálculo do tempo d
As seguintes proposições ilustram os critérios de cálculo de espaço durante
o deslocamento do comboio. Os respectivos tempos de deslocamento são então
obtidos como resultado da divisão do espaço percorrido pela velocidade de
deslocame
nto, a qual é deduzida a partir dos dados de entrada.
ialmente está localizado um comboio é considerada ocupada até que o
comboio deixe completamente a linha.
A linha de destino de um comboio é considerada ocupada até o fim do
horizonte de planejamento ou até que uma manobra executada posteriormente
comboio de lá.
Além disso, se a linha de destino não estiver livre desde o
momento em que o início do comboio a atingir até o momento em que o centro do
comboio estiver alinhado com o seu centro, então a linha não será considerada
Figura
21
mostra a vista lateral do comboio κ, localizado na linha A,
pronto para se deslocar até a linha B. A linha A aparece representada em preto e a
linha B em cinza. O ponto central de cada linha está assinalado com um
triângulo da cor da linha. Na figura estão indicados o comprimento
e os comprimentos das linhas A e B, que são
referência de cada linha é considerado o meio da linha. O meio do comboio é o
referência do comboio. Assim, o meio do comboio está alinhado
inicialmente com o
meio
da linha A e ficará, ao final do deslocamento, alinhado
da linha B.
: Dimensões envolvidas no cálculo do tempo d
As seguintes proposições ilustram os critérios de cálculo de espaço durante
o deslocamento do comboio. Os respectivos tempos de deslocamento são então
obtidos como resultado da divisão do espaço percorrido pela velocidade de
nto, a qual é deduzida a partir dos dados de entrada.
l
0
Linha A
l
a
ialmente está localizado um comboio é considerada ocupada até que o
comboio deixe completamente a linha.
A linha de destino de um comboio é considerada ocupada até o fim do
horizonte de planejamento ou até que uma manobra executada posteriormente
Além disso, se a linha de destino não estiver livre desde o
momento em que o início do comboio a atingir até o momento em que o centro do
comboio estiver alinhado com o seu centro, então a linha não será considerada
mostra a vista lateral do comboio κ, localizado na linha A,
pronto para se deslocar até a linha B. A linha A aparece representada em preto e a
linha B em cinza. O ponto central de cada linha está assinalado com um
triângulo da cor da linha. Na figura estão indicados o comprimento
e os comprimentos das linhas A e B, que são
referência de cada linha é considerado o meio da linha. O meio do comboio é o
referência do comboio. Assim, o meio do comboio está alinhado
da linha A e ficará, ao final do deslocamento, alinhado
: Dimensões envolvidas no cálculo do tempo d
As seguintes proposições ilustram os critérios de cálculo de espaço durante
o deslocamento do comboio. Os respectivos tempos de deslocamento são então
obtidos como resultado da divisão do espaço percorrido pela velocidade de
nto, a qual é deduzida a partir dos dados de entrada.
ialmente está localizado um comboio é considerada ocupada até que o
comboio deixe completamente a linha.
A linha de destino de um comboio é considerada ocupada até o fim do
horizonte de planejamento ou até que uma manobra executada posteriormente
Além disso, se a linha de destino não estiver livre desde o
momento em que o início do comboio a atingir até o momento em que o centro do
comboio estiver alinhado com o seu centro, então a linha não será considerada
mostra a vista lateral do comboio κ, localizado na linha A,
pronto para se deslocar até a linha B. A linha A aparece representada em preto e a
linha B em cinza. O ponto central de cada linha está assinalado com um
triângulo da cor da linha. Na figura estão indicados o comprimento
e os comprimentos das linhas A e B, que são
l
a
e
referência de cada linha é considerado o meio da linha. O meio do comboio é o
referência do comboio. Assim, o meio do comboio está alinhado
da linha A e ficará, ao final do deslocamento, alinhado
: Dimensões envolvidas no cálculo do tempo d
As seguintes proposições ilustram os critérios de cálculo de espaço durante
o deslocamento do comboio. Os respectivos tempos de deslocamento são então
obtidos como resultado da divisão do espaço percorrido pela velocidade de
nto, a qual é deduzida a partir dos dados de entrada.
Comboio κ
ialmente está localizado um comboio é considerada ocupada até que o
A linha de destino de um comboio é considerada ocupada até o fim do
horizonte de planejamento ou até que uma manobra executada posteriormente
Além disso, se a linha de destino não estiver livre desde o
momento em que o início do comboio a atingir até o momento em que o centro do
comboio estiver alinhado com o seu centro, então a linha não será considerada
mostra a vista lateral do comboio κ, localizado na linha A,
pronto para se deslocar até a linha B. A linha A aparece representada em preto e a
linha B em cinza. O ponto central de cada linha está assinalado com um
triângulo da cor da linha. Na figura estão indicados o comprimento
e
l
b
respectivamente. O ponto de
referência de cada linha é considerado o meio da linha. O meio do comboio é o
referência do comboio. Assim, o meio do comboio está alinhado
da linha A e ficará, ao final do deslocamento, alinhado
: Dimensões envolvidas no cálculo do tempo d
e alocação das linhas
As seguintes proposições ilustram os critérios de cálculo de espaço durante
o deslocamento do comboio. Os respectivos tempos de deslocamento são então
obtidos como resultado da divisão do espaço percorrido pela velocidade de
nto, a qual é deduzida a partir dos dados de entrada.
Linha B
l
b
ialmente está localizado um comboio é considerada ocupada até que o
A linha de destino de um comboio é considerada ocupada até o fim do
horizonte de planejamento ou até que uma manobra executada posteriormente
Além disso, se a linha de destino não estiver livre desde o
momento em que o início do comboio a atingir até o momento em que o centro do
comboio estiver alinhado com o seu centro, então a linha não será considerada
mostra a vista lateral do comboio κ, localizado na linha A,
pronto para se deslocar até a linha B. A linha A aparece representada em preto e a
linha B em cinza. O ponto central de cada linha está assinalado com um
triângulo da cor da linha. Na figura estão indicados o comprimento
l
0
do comboio
respectivamente. O ponto de
referência de cada linha é considerado o meio da linha. O meio do comboio é o
referência do comboio. Assim, o meio do comboio está alinhado
da linha A e ficará, ao final do deslocamento, alinhado
e alocação das linhas
As seguintes proposições ilustram os critérios de cálculo de espaço durante
o deslocamento do comboio. Os respectivos tempos de deslocamento são então
obtidos como resultado da divisão do espaço percorrido pela velocidade de
nto, a qual é deduzida a partir dos dados de entrada.
Linha B
80
ialmente está localizado um comboio é considerada ocupada até que o
A linha de destino de um comboio é considerada ocupada até o fim do
horizonte de planejamento ou até que uma manobra executada posteriormente
Além disso, se a linha de destino não estiver livre desde o
momento em que o início do comboio a atingir até o momento em que o centro do
comboio estiver alinhado com o seu centro, então a linha não será considerada
mostra a vista lateral do comboio κ, localizado na linha A,
pronto para se deslocar até a linha B. A linha A aparece representada em preto e a
linha B em cinza. O ponto central de cada linha está assinalado com um
pequeno
do comboio
respectivamente. O ponto de
referência de cada linha é considerado o meio da linha. O meio do comboio é o
referência do comboio. Assim, o meio do comboio está alinhado
da linha A e ficará, ao final do deslocamento, alinhado
As seguintes proposições ilustram os critérios de cálculo de espaço durante
o deslocamento do comboio. Os respectivos tempos de deslocamento são então
obtidos como resultado da divisão do espaço percorrido pela velocidade de
PUC-Rio - Certificação Digital Nº 0321287/CA
81
O comboio atinge a linha B após percorrer um espaço
0
( ) / 2
a
l l l
= −
e, a partir deste momento, a linha B é considerada ocupada;
O comboio só libera a linha A após o seu último vagão deixar a linha
A, ou seja, após percorrer o espaço
0 0 0
( ) / 2 / 2
a a
l l l l l l
′
= − + = +
;
O comboio chega à linha B depois de percorrer o espaço
( ) / 2
a b
l l l
′′
= +
.
Diante da modelagem utilizada nota-se que o controle de alocação de linhas
está baseado na divisão do horizonte de planejamento em unidades discretas de
tempo, chamadas de intervalo, e no mapeamento destes intervalos e das linhas do
pátio em uma matriz de alocação de linhas. Vale notar que o valor definido para a
duração do intervalo t
0
influencia na quantidade de memória necessária para a
matriz de alocação de linhas. Intervalos muito curtos implicam em uma matriz
com muitas colunas e numa demanda maior por recursos computacionais para
processar o controle de alocação de linhas. Intervalos muito longos, por outro
lado, reduziriam a precisão do controle de alocação de linhas do pátio,
comprometendo assim a qualidade das estimativas feitas durante a elaboração da
solução.
PUC-Rio - Certificação Digital Nº 0321287/CA
5
Testes computacionais
Por que só pensar? Por que não experimentar?
EDWARD JENNER
Este capítulo se inicia com a descrição dos critérios e métodos utilizados
para definição do conjunto de dados de teste, o qual foi utilizado para analisar o
comportamento do programa YoYo em diversas situações. O capítulo é concluído
com a apresentação dos resultados dos testes computacionais.
5.1.O programa gerador de ordens de serviço
A necessidade de desenvolvimento de um programa gerador de manobras -
denominado SOGY (Switch Order Generator for YoYo) - surgiu durante a fase
dos testes computacionais. Com o principal objetivo deste projeto é desenvolver
um algoritmo para solução do PPOLM e implementá-lo, na prática, como
ferramenta de apoio à decisão, desde o início havia o interesse em comparar as
operações recomendadas pelo programa YoYo com as operações efetivamente
executadas pelos profissionais responsáveis pelas operações do pátio em estudo.
Para comparar os dois planos, era necessário então registrar o plano gerado
na prática e submeter ao programa as mesmas informações que a equipe de
operação do pátio usou para elaborar o seu plano. Em seguida a idéia era
comparar o custo do plano gerado pela equipe com o custo do plano gerado pelo
programa.
Nos estágios iniciais do projeto, visando obter uma estimativa do retorno de
investimento e justificar a viabilidade do projeto, foram feitas algumas coletas
manuais de dados, simplesmente acompanhando a rotina das equipes de
planejamento e execução de manobras na sala de controle de operações de pátio,
PUC-Rio - Certificação Digital Nº 0321287/CA
83
durante o intervalo de tempo de algumas horas. Nestas sessões de coletas de
dados, eram registradas as ordens enviadas aos maquinistas e os tempos de
execução da manobra. As mesmas informações sobre as manobras a serem
executadas no intervalo de tempo amostrado eram então fornecidas ao programa
YoYo e, de posse dos resultados, era possível comparar o custo das manobras
executadas na prática com o custo do plano de manobras sugerido pelo programa.
Os primeiros resultados foram animadores. Os resultados obtidos naquela
época com o que pode ser chamado de um protótipo do programa YoYo,
conforme apresentado em Sabino (2004), foram considerados suficientes para
justificar o projeto, já que sugeriam uma considerável redução de custo com a
utilização da ferramenta de apoio à decisão. No entanto, a quantidade e a
confiabilidade dos dados coletados com um procedimento manual são
insuficientes para uma análise mais detalhada sobre a eficiência do método
proposto e principalmente para o ajuste fino dos parâmetros do programa visando
a sua aplicação prática. A estratégia adotada para superar estas dificuldades foi a
construção de um simulador capaz de gerar um conjunto de manobras a serem
executadas baseado nas características físicas e operacionais de um pátio
ferroviário. As manobras geradas por este simulador foram então tomadas como
modelo de referência para testes do programa YoYo.
Ocorre que o funcionamento de um pátio ferroviário é regido por vários
processos que interagem nem sempre de forma previsível, o que tornou o processo
de desenvolvimento do SOGY uma tarefa difícil. A estratégia adotada foi a
realização de entrevistas com a equipe de planejamento para definir as variáveis
que caracterizam o pátio, seguido de um estudo sobre o fluxo de operações das
manobras e finalmente a validação do processo de simulação e dos resultados
obtidos com profissionais experientes da área.
O pátio ferroviário submetido ao SOGY é o terminal de descarregamento
fictício RRT1, cujo leiaute é apresentado na Figura 22. A linha pontilhada
representa a ferrovia, de onde chegam os trens com vagões carregados e para onde
vão os trens de vagões vazios depois de descarregados. As linhas contínuas
representam linhas do pátio. A linha tracejada em cinza representa um trecho
especial do terminal destinado exclusivamente à circulação de locomotivas de
viagem. Os círculos escuros representam várias ramificações paralelas de uma
PUC-Rio - Certificação Digital Nº 0321287/CA
84
linha principal, onde podem ser estacionados vários conjuntos de vagões. Cada
círculo escuro representa um conjunto padrão, constituído de uma linha principal
e um total de até oito ramificações paralelas laterais de mesmo comprimento.
Assim, cada círculo escuro representa uma zona do pátio. Estão representadas as
zonas de recepção (RCP) e desmembramento (BKU) de trens, manutenção de
locomotivas (MNS), descarregamento (UNL1, UNL2, UNL3 e UNL4), um ponto
de inspeção, uma rampa de classificação (HPY) seguida de uma área de
estacionamento (PRK), uma área de limpeza (CLN), uma área de manutenção de
vagões (MNC) e uma área de formação de trens (MKU). Maiores detalhes sobre o
leiaute do terminal RRT1 podem ser obtidos em Sabino(2004).
Figura 22: Pátio de descarregamento RRT1 utilizado nos testes computacionais.
A Tabela 2 mostra as variáveis de entrada para o programa SOGY, usadas
para descrever as principais características do pátio fictício RRT1. Nesta tabela,
as informações estão agrupadas por escopo e além da especificação do conteúdo
das variáveis, estão indicados também os valores utilizados para geração dos
dados de entrada para os testes computacionais deste trabalho.
UNL1
UNL3
UNL4
BKU
RCP
MKU
PRK
CLN
MNC
HPY
MNS
X
ISP
UNL2
PUC-Rio - Certificação Digital Nº 0321287/CA
85
Tabela 2: Parâmetros do Programa SOGY
A Figura 23 mostra o Diagrama de Fluxo de Dados do programa SOGY
utilizando a notação de Yourdon & Coad (1991). O programa gera primeiramente
uma base de dados relacional com a programação de chegada de trens,
especificando, para cada bloco, informações como o horário de chegada do trem
que contém o bloco e a sua constituição em número de vagões e tipo de carga.
Esta base de dados é gerada baseado nos valores fornecidos para os parâmetros de
chegada, conforme definido na Tabela 2.
Escopo Especificação Valor
Geral Áreas do pátio ferroviário RCP, BKU, UNL, PRK,
CLN, MNT, MKU
Geral Horizonte de planejamento 6 h
Geral Peso médio de um vagão vazio 15 ton
Geral Peso médio de um vagão carregado 50 ton
Geral Tempo de serviço máximo permitido 2 h
Chegada Tempo entre duas chegadas
consecutivas de trens
20 min
Chegada Vetor que contém as probabilidades de
haver 1, 2, 3, 4 ou 5 blocos num trem
recém chegado
{0.65, 0.15, 0.10, 0.10,
0.05}
Partida Tempo entre duas partidas
consecutivas de trens
20 min
Descarga Tempo de serviço de uma descarga
longa (assistida)
0.2 h
Descarga Tempo médio de uma descarga de
duração curta (não assistida)
15 min
Descarga Probabilidade de uma manobra de
descarga ser assistida
0.4
Descarga Probabilidade de um conjunto de
vagões carregado não descarregar
durante o horizonte de planejamento
dado
0.2
Inspeção Probabilidade de um vagão requerer
manutenção após a inspeção
0.05
Inspeção Probabilidade de um conjunto de
vagões requerer limpeza após a
inspeção
0.01
Inspeção Número máximo de conjuntos de
vagões distintos criados após a
inspeção
10
classificação Probabilidade de um bloco localizado
na área de estacionamento necessitar
de manobras de classificação
0.3
PUC-Rio - Certificação Digital Nº 0321287/CA
86
Figura 23: Diagrama de Fluxo de Dados do programa SOGY
Em seguida, a base de dados com a programação de trens é lida pelo
processo Gerar BKU para criar uma base contendo as manobras, que contém,
inicialmente, uma manobra de coleta na área de recepção e entrega na área de
desmembramento para cada bloco que chega. A ordem dos blocos no trem que
PUC-Rio - Certificação Digital Nº 0321287/CA
87
chega ao pátio define as restrições de seqüência na execução das manobras de
desmembramento.
A base de dados switch orders é então lida e incrementada sucessivas
vezes, simulando, em ordem cronológica, as fases seguintes de descarregamento,
inspeção, ida e retorno para as áreas de limpeza e de manutenção, classificação e
depois formação. Como o processo é incremental, exceto quando informado
explicitamente por meio de uma das variáveis da Tabela 2, cada manobra de uma
etapa é pré-requisito de uma manobra correspondente gerada para a etapa
seguinte. Todos os valores de probabilidade informados como parâmetros para
especificar características do pátio consideram variáveis uniformemente
distribuídas.
O processo Gerar UL lê as manobras de desmembramento da base de
dados de manobras, considera a probabilidade do conjunto de vagões movido para
a área de desmembramento eventualmente não ser descarregado durante o
horizonte de planejamento dado e gera as manobras correspondentes de
movimentação da área de desmembramento para a área de descarregamento. O
tempo de serviço das manobras de descarregamento geradas depende do
parâmetro que informa a probabilidade de uma manobra ser assistida ou não e dos
tempos médios de descarregamento assistido e não assistido.
Para simular a fase de inspeção são consideradas as probabilidades de um
vagão requerer manutenção e de um conjunto de vagões requerer limpeza.
Baseado nestas probabilidades são geradas manobras de ida e volta para inspeção
e limpeza e a correspondente manobra de movimentação de vagões da área de
estacionamento para a área de formação. Caso um dado conjunto ou um dado
vagão não requeira limpeza nem manutenção, são geradas apenas manobras de
movimentação deste vagão, ou conjunto, com coleta na área de estacionamento e
entrega na área de formação.
Vale notar que o programa SOGY gera uma manobra de volta para cada
manobra de ida para manutenção e que o mesmo equilíbrio se observa entre o
número de conjuntos de vagões que vão e voltam da área de limpeza. Também as
manobras que têm como destino a área de formação são geradas a partir da
passagem de vagões pela inspeção e não de um plano de formação de trens. Estas
premissas são simplificações da rotina real, que facilitam o desenvolvimento do
PUC-Rio - Certificação Digital Nº 0321287/CA
88
programa sem representar alterações significativas na similaridade das manobras
geradas com as manobras usuais de um pátio real.
Com o programa SOGY, portanto, foi possível gerar o número necessário de
instâncias de entrada do programa YoYo para ajuste fino dos parâmetros e
comparação de métodos de solução do PPOLM.
5.2.
Preparação dos experimentos e métricas utilizadas
Os objetivos dos experimentos computacionais foram:
1. Verificar se uma das duas regras de atualização do feromônio
conduziria aos melhores resultados;
2. Descobrir se existiam valores recomendados para o número de
formigas, o expoente associado à informação heurística β e o fator
de persistência do feromônio ρ;
3. Verificar se os valores recomendados para os parâmetros do
algoritmo ACO mudam com a variação do tamanho da instância;
4. Verificar se o tempo médio de resposta para a obtenção de boas
soluções para o problema é razoável para utilização do programa
YoYo como ferramenta de apoio à decisão aplicável em situações
práticas no planejamento de operações de um pátio de manobras
real.
Para se obter um conjunto de entrada e dados de tamanho razoável, o
programa SOGY foi usado para gerar 50 instâncias de entrada, cada uma com
mais de 200 manobras a serem executadas em um horizonte de planejamento de 6
horas.
A Tabela 3 mostra os parâmetros operacionais usados nos experimentos. O
horizonte de planejamento foi definido com duração igual à de um turno de
trabalho do pátio real de referência deste estudo. O número de manobras a serem
planejadas é a variável mais importante na determinação do tamanho da instância
do problema. No caso real, observou-se uma média de 10 manobras por hora,
totalizando 60 manobras em um horizonte de planejamento de 6 horas, assim,
consideramos instâncias de 20 manobras, para representar uma instância de
tamanho pequeno, 60 manobras para representar um valor médio para um grande
PUC-Rio - Certificação Digital Nº 0321287/CA
89
pátio de manobras (já que o caso real em estudo é o maior pátio da América
Latina) e 100 manobras para representar um pátio de grandes dimensões ou com
alta carga de trabalho.
A importância do custo fixo foi definida como um valor estimado,
considerando o objetivo tático de um pátio real, segundo estimativas feitas em
conjunto com profissionais da área de planejamento operacional de pátios. O
número de locomotivas de manobras disponível foi definido bem acima da média
utilizada para o pátio de referência. Isto foi feito porque o interesse maior era em
determinar o número de locomotivas necessárias e não em testar a reação do
algoritmo a limitações no número de locomotivas. A posição inicial das
locomotivas foi definida distribuindo-as aleatoriamente pelas áreas do pátio em
linhas também definidas aleatoriamente. Para determinar a capacidade de tração
das locomotivas, tomou-se a capacidade dos cinco modelos de locomotivas mais
utilizados no caso real e um gerador de valores aleatórios uniformemente
distribuídos definiu quantas locomotivas seriam de cada um destes modelos, de
modo que o total de locomotivas fosse o número dado.
Parâmetro otação Valor(es)
Horizonte de planejamento (em horas)
h
6,0
Número de manobras a serem planejadas
n_orders
20; 60 e 100
Importância relativa do custo fixo
c
1
/c
2
0,8
Número de locomotivas disponíveis no pátio
n_vehicles
40
Tabela 3: Parâmetros operacionais utilizados nos experimentos computacionais
Os valores dos parâmetros do algoritmo ACO utilizados nos experimentos
são mostrados na Tabela 4. O número inicial de formigas para ambas as colônias
no algoritmo CompetAnts foi 40, então decidiu-se tomar três valores maiores que
este para investigar até onde valia a pena investir em processamento adicional (i.e.
aumentando o número de formigas) visando a obtenção de soluções melhores.
Esta estratégia também serviu para validar se o número de formigas recomendado
em Dorigo & Stützle (2004) para bom desempenho na solução do Problema do
Caixeiro Viajante era bom também para o PPOLM. Vale notar que a orientação de
que o número de formigas deve ser igual ao número de cidades do Problema do
Caixeiro Viajante deve ser convertida na especificação do número de formigas
PUC-Rio - Certificação Digital Nº 0321287/CA
90
igual ao dobro do número de manobras a serem executadas no PPOLM, já que
cada manobra está associada a dois pontos de parada na rota de uma locomotiva.
O expoente do feromônio, o valor inicial do feromônio e o número de
formigas que depositam feromônio foram definidos de acordo com as
recomendações de parâmetros proposta em Dorigo & Stützle (2004) para bom
desempenho do algoritmo Ant System na solução do Problema do Caixeiro
Viajante. A importância do feromônio da própria colônia em relação ao feromônio
da outra colônia foi definida com o mesmo valor usado em Reimann (2002), ou
seja, de modo que as formigas dêem a mesma importância ao feromônio de ambas
as colônias.
Devido à simplicidade de implementação e o menor tempo de execução
esperado, optou-se por utilizar o custo variável estático no cálculo do valor da
função objetivo. Diante da impossibilidade de desenvolver um sistema eficiente
para estimar, com razoável precisão, os tempos de deslocamento e espera durante
a realização das manobras, os eventuais conflitos de alocação de linhas pelos
comboios durante a execução do plano de manobras proposto foram deixados para
tratamento em tempo real pelas equipes de operação do pátio.
Parâmetro otação Valor(es)
Número inicial de formigas (para ambas
colônias)
m
40; 60; 100 e 200
Expoente do feromônio α 1
Expoente heurístico β 1; 3; 5 e 10
Fator de evaporação de feromônio ρ 0,02; 0,10; 0,50; 0,9
e 0,98
Valor inicial do feromônio τ
0
0,1
Importância do feromônio da própria população χ 0,5
Número de formigas que depositam feromônio
(apenas para a regra RNK)
w
6
Tabela 4: Parâmetros do algoritmo ACO utilizados nos experimentos computacionais
As versões RNK e CME do algoritmo foram executadas uma única vez
(Birattari, 2005) para 50 listas diferentes de manobras geradas pelo programa
SOGY. Para cada instância de manobras foram testadas todas as combinações
possíveis dos valores de parâmetros mencionados nas tabelas 3 e 4. Esta estratégia
de testes resultou em um conjunto de 240 combinações de parâmetros a serem
PUC-Rio - Certificação Digital Nº 0321287/CA
91
submetidas para cada algoritmo, produzindo 240 x 50 x 2 = 24000 resultados a
serem avaliados.
O programa termina depois de concluir a trigésima iteração do algoritmo
ACO. Este era o único critério de parada e, ao final, as seguintes informações
eram registradas para análise futura:
O valor da solução, ou seja, o melhor valor encontrado para a função
objetivo depois de 30 iterações;
O tempo de CPU consumido até encontrar a melhor solução. Vale
notar que este não é, necessariamente, o tempo total de CPU
consumido após as 30 iterações, já que, na maioria das vezes, a
melhor solução é encontrada antes da última iteração.
O número de iterações até o ponto em que a melhor solução foi
encontrada. Este valor foi registrado apenas para tornar possível
estimar o impacto da redução do número de iterações necessárias na
qualidade da solução.
Os dados coletados foram sumariados utilizando uma medida de tendência
central ao invés do melhor resultado encontrado (Birattari & Dorigo, 2007). Foi
usada análise de variância (ANOVA) com nível de significância de 5% para
comparar os resultados e avaliar se existia evidência de diferença entre as médias
das populações. Os conjuntos de dados com valores do número de manobras
diferentes não foram consolidados porque eles representam as diferentes cargas de
trabalho submetidas ao pátio e, portanto, devem ser analisados separadamente.
Ambos os algoritmos foram implementados em ANSI C e o código fonte foi
compilado com gcc versão 3.4.6. Todos os testes foram executados em ambiente
Red Hat Enterprise Linux, CentOS release 4.5 instalados em servidores AMD
opteron™ 244 com clock de 1,75 GHz, 1 Mb de memória L2 cache e 2 Gb de
memória RAM.
5.3.Resultados
A primeira análise feita foi uma comparação direta entre a qualidade da
solução obtida com a implementação das regras CME e RNK. A Figura 24 e a
Tabela 5 apresentam a média e o desvio padrão do valor da solução, considerando
PUC-Rio - Certificação Digital Nº 0321287/CA
92
todos os testes feitos para conjunto de dados de entrada contendo 20, 60 e 100
manobras. O histograma da Figura 24 mostra o resultado lado a lado e os
respectivos valores com precisão de 4 casas decimais são mostrados na Tabela 5.
Esta primeira análise sugere que não há diferença significativa na qualidade da
solução para nenhum dos valores de n_orders. A análise de variância suporta esta
hipótese intuitiva, já que a mesma não produz evidências de diferença
estatisticamente significativa entre os resultados obtidos para os algoritmos que
utilizam as regras CME e RNK.
Figura 24: Comparação da qualidade da solução para as regras CME e RNK
A primeira conclusão foi, então, que com base no sumário de todos os
resultados obtidos, agrupados por número de manobras e sem considerar os
parâmetros utilizados em cada caso, não é possível concluir que um dos dois
algoritmos testados apresenta melhor qualidade que o outro.
Tabela 5: Comparação da qualidade da solução para as regras CME e RNK
0,0
0,1
0,2
0,3
0,4
0,5
0,6
0,7
0,8
0,9
Média Desvio
Padrão
Média Desvio
Padrão
Média Desvio
Padrão
20 60 100
solução
Qualidade da solução por número de manobras
CME
RNK
n_orders
Algoritmo
n_orders
Solução
CME
RNK
20
Média
0,1246
0,1270
Desvio Padrão
0,0274
0,0306
60
Média
0,4213
0,4212
Desvio Padrão
0,0366
0,0466
100
Média
0,7789
0,7719
Desvio Padrão
0,0545
0,0828
PUC-Rio - Certificação Digital Nº 0321287/CA
93
Também o tempo de CPU, conforme apresentado na Tabela 6, apresentou
um desvio padrão relativamente grande para os três valores de número de
manobras testados, tornando, portanto, impossível identificar qualquer diferença
estatisticamente significativa.
A conclusão, baseada nos resultados gerais agrupados por número de
manobras, é que nenhum dos dois algoritmos testados produz resultados melhores
que o outro no que se refere a qualidade e custo das soluções.
Tabela 6: Tempo de CPU, em segundos, das soluções CME e RNK
O próximo passo foi verificar a influência dos parâmetros ACO na
qualidade da solução, sendo de particular interesse a identificação do valor
recomendado para os três parâmetros ACO que foram modificados: o número
inicial de formigas das duas colônias m, o expoente da atratividade β e o fator de
evaporação de feromônio ρ.
O histograma da Figura 25 compara a média das soluções para cada valor de
{40, 60, 100, 200}
m
∈
. As barras estão agrupadas de acordo com o número de
manobras do conjunto de dados de entrada.
Algoritmo
n_orders
Tempo de CPU (s)
CME
RNK
20
Média
1,29
1,17
Desvio Padrão
2,55
2,35
60
Média
29,89
23,08
Desvio Padrão
33,81
33,94
100
Média
79,71
71,62
Desvio Padrão
78,43
100,40
PUC-Rio - Certificação Digital Nº 0321287/CA
94
Figura 25: Comparação das soluções CME e RNK variando n_orders e m
Percebe-se que não há diferença significativa na qualidade da solução para
n_orders=20. Para n_orders=60 e n_orders=100, independente do algoritmo, a
solução melhora à medida que o valor de m aumenta. Além disso, o algoritmo
baseado na regra RNK produz melhores resultados que o que utiliza a regra CME
para m = 100 e m = 200. Todas estas conclusões são suportadas pelo teste
estatístico ANOVA. Por exemplo, na Tabela 7 o sumário contendo o resultado da
análise de variância simples das amostras com m = 200 e n_orders=60,
considerando um nível de significância de 0,05 mostra que existe uma diferença
estatisticamente significativa entre os valores das soluções quando se compara as
regras CME e RNK.
Tabela 7: Resultados de ANOVA com fator único para m =200 e n_orders=60
0,0
0,1
0,2
0,3
0,4
0,5
0,6
0,7
0,8
0,9
40 60 100 200 40 60 100 200 40 60 100 200
20 60 100
solução
Comparação da qualidade da solução obtida
CME
RNK
m
n_orders
Anova: fator único
RESUMO
Grupo Contagem Soma Média Variância
CME 1000 413,1341 0,413134 0,001293
RNK
1000
406,31
0,40631
0,001678
ANOVA
Fonte da variação SQ gl MQ F valor-P F crítico
Entre grupos 0,023284 1 0,023284 15,67681 7,78E-05 3,846117
Dentro dos grupos 2,967564 1998 0,001485
Total
2,990848
1999
PUC-Rio - Certificação Digital Nº 0321287/CA
95
O fato de valores maiores de m levarem a resultados melhores é uma
consequência do número adicional de soluções geradas quando se aumenta o valor
de m.
Quanto aos valores de ρ e β, chegou-se às seguintes conclusões após
analisar a média das soluções encontradas para combinações de m, ρ e β para cada
valor possível de n_orders:
Para o algoritmo baseado na regra RNK, ρ=0,5 produz as melhores
soluções, especialmente para valores maiores de m e independente
do valor de β. Isto é válido para qualquer valor de n_orders e a
melhor combinação é ρ=0,5 e β=5;
Para o algoritmo CME, ρ=0,98 e β=3 é a melhor combinação
considerando fixos n_orders=60 e n_orders=100. Os melhores
valores de ρ e β nem sempre são os mesmos. Por exemplo, para
n_orders=20 a melhor combinação é ρ=0,98 e β=1;
A regra RNK com sua melhor combinação ρ=0,5 e β=5 produz uma
solução melhor que qualquer combinação de parâmetros testados
com a regra CME para n_orders=60 e n_orders=100.
0,36
0,37
0,38
0,39
0,40
0,41
0,42
0,43
0,44
0,45
0,46
1 3 5 10
solução
β
Qualidade da solução obtida com a regra RNK
0,02
0,1
0,5
0,9
0,98
ρ
PUC-Rio - Certificação Digital Nº 0321287/CA
96
Figura 26: Comparação das regras RNK e CME variando ρ e β
Esta última conclusão é ilustrada com os dois histogramas da Figura 26 que
apresentam no eixo y a média das soluções obtidas utilizado as regras CME e
RNK, mantendo fixos m=100 e n_orders=60. Cada cor de barra no eixo x
representa um valor de ρ e cada conjunto agrupado de cinco barras representa um
valor de β, assim, para cada um dos quatro valores de β testados são mostrados os
valores correspondentes de ρ dispostos lado a lado. As barras estão dispostas com
os valores de β e ρ classificados em ordem crescente da esquerda para a direita.
Como os dois gráficos utilizam a mesma escala para o eixo y é fácil
observar que os melhores resultados são obtidos com o algoritmo RNK com
parâmetros ρ=0,5 e β=5.
Uma análise mais detalhada das características das regras CME e RNK
indica uma possível razão para o melhor desempenho da regra RNK: Como a
lógica da regra CME não repassa as informação sobre o desempenho da iterações
anteriores para as iterações seguintes, a regra RNK explora mais agressivamente a
melhor solução obtida até então e portanto é guiada mais diretamente para as
melhores soluções.
0,36
0,37
0,38
0,39
0,40
0,41
0,42
0,43
0,44
0,45
0,46
1 3 5 10
solução
β
Qualidade da solução obtida com a regra CME
0,02
0,1
0,5
0,9
0,98
ρ
PUC-Rio - Certificação Digital Nº 0321287/CA
97
Figura 27: Número médio de iterações para CME e RNK variando n_orders e m
A Figura 27 mostra, para os valores de m e n_orders testados, a média do
número de iterações necessárias até encontrar a melhor solução, considerando
ρ=0,5 e β=5. As barras correspondentes aos resultados obtidos com as regras
CME e RNK estão emparelhadas para cada valor de n_orders e agrupadas por
valor de m. É fácil observar que o número de iterações necessárias para encontrar
a melhor solução aumenta com o valor de n_orders. Como o desvio padrão do
número de iterações necessárias até encontrar a melhor solução é relativamente
alto em todos os casos testados, não foi possível obter diferença estatisticamente
significativa entre o número de iterações para os valores testados de n_orders e m.
De uma forma geral, o número de iterações e, portanto, o tempo de CPU
necessário para se chegar à solução do problema foram tão dispersos que ficou
impossível de se chegar a alguma conclusão sobre a comparação do custo
computacional para obtenção das soluções. O gráfico da Figura 28 dá uma idéia
de quão dirpersos estão os valores de tempo de CPU necessário considerando
todas as combinações dos parâmetros testados mantendo fixo n_orders=60. No
gráfico do tipo boxplot as extremidades superior e inferior das barras verticais
indicam a posição do primeiro e do terceiro quartil de dados respectivamente. As
extensões pontilhadas vão até o valor que que corresponde a 1,5 vezes a faixa
0,00
0,10
0,20
0,30
0,40
0,50
0,60
0,70
0,80
0,90
40 60 100 200 40 60 100 200 40 60 100 200
20 60 100
número médio de iterações
Número médio de iterações
CME
RNK
m
n_orders
PUC-Rio - Certificação Digital Nº 0321287/CA
98
interquartil indicada pela barra. Os valores atípicos, ou seja, que apresentam um
grande afastamento dos restantes, são indicados como pequenos círculos.
Figura 28: Boxplot do tempo de CPU para todas as combinações de parâmetros
considerando n_orders=60
Para verificar a possibilidade de utilização do algoritmo proposto para
resolver instâncias reais, foi avaliado o tempo de resposta das 50 execuções com o
algoritmo RNK utilizando a melhor combinação de parâmetros e considerando
n_orders=60, que é o tamanho de instância mais realista testada. O valor médio
deste tempo de resposta foi 82 segundos, com um desvio padrão de 0,5 segundos.
Este resultado corresponde às expectativas para aplicação prática, já que neste
tempo é possível refazer o planejamento de manobras mais de 100 vezes durante
um horizonte de planejamento padrão de 6 horas de duração. O número médio de
locomotivas de manobras necessárias para a solução destas instâncias de tamanho
real foi 4, o mínimo foi 3 e o máximo foi 7. Estes valores estão abaixo do
esperado para um pátio com esta carga de trabalho, segundo opinião de
profissionais da área. Estes resultados sugerem que a implementação do algoritmo
RNK para suporte à decisão de planejamento operacional de pátios pode reduzir,
inclusive, o número de locomotivas de manobras necessárias para a operação do
pátio.
rnkparm000049 rnkparm000057 rnkparm000065 rnkparm000073 rnkparm000081 rnkparm000089
0 50 100 150 200
CPU Needed for # SO = 60
sample
CPU Needed
PUC-Rio - Certificação Digital Nº 0321287/CA
6
Conclusão
Sempre em movimento o futuro está.
GUERRA NAS ESTRELAS V – O IMPÉRIO CONTRA-ATACA, LUCASFILM, 1980
Este trabalho desenvolveu uma análise sistemática da operação de um pátio
ferroviário, classificando-a em três etapas, apresentou a modelagem da terceira
etapa deste planejamento e propôs e implementou um algoritmo de solução do
problema identificado nesta etapa. Foi desenvolvido também um simulador de
manobras com o objetivo de gerar instâncias de teste para ajuste finos dos
parâmetros do algoritmo proposto e para análise da aplicabilidade dos resultados.
Com os testes computacionais desenvolvidos, os quais utilizaram dados de
entrada gerados pelo simulador de pátio, foi possível concluir que o algoritmo
YoYo é capaz de resolver o problema proposto, considerando as suas restrições
mais importantes e com muito poucas simplificações do caso real. Foram obtidas
boas soluções para instâncias com 60 ordens de serviço, consumindo, nestes
casos, menos de 2 minutos de tempo de CPU de um computador pessoal AMD
opteron® 244 com clock de 1,75 GHz e produzindo uma solução completa em
menos de 3 minutos.
Comparado com os demais trabalhos publicados sobre este assunto e
adicionando a este grupo o trabalho em Reimann (2002), esta pesquisa apresenta
algumas contribuições importantes sob o ponto de vista acadêmico, metodológico
e prático.
Considerando as pesquisas acadêmicas relacionadas:
Charnes & Miller (1956) foi o primeiro trabalho (e durante décadas
foi também o único) do qual se tem conhecimento sobre
PUC-Rio - Certificação Digital Nº 0321287/CA
100
programação de tarefas em pátios de manobras e, embora o autor
apresente detalhes práticos muito importantes, sua abordagem de
meados do século passado pode ser considerada apenas como uma
pesquisa preliminar do modelo complexo de planejamento de rotas
apresentado neste trabalho.
A solução desenvolvida no presente trabalho se baseia nas idéias
propostas em Reimann (2002) para planejamento de transporte de
cargas. A partir destas idéias, foram mapeados objetos similares na
rotina de pátios ferroviários e adicionadas novas estruturas,
parâmetros e procedimentos para tratar as características e restrições
específicas do PPOLM. Além disso, foi proposta uma nova regra de
atualização de feromônios que se mostrou mais eficiente para tratar o
PPOLM.
Comparado à tese de doutorado Lübbecke (2001), o presente
trabalho introduz uma nova abordagem para modelagem do
problema, adiciona os requisitos operacionais e restrições que são
próprias do pátio utilizado como referência para o estudo de caso e
propõe um método de solução original para tratar desta classe de
problemas. Particularmente, até o momento de conclusão desta tese
não havia nenhuma outra aplicação conhecida de algoritmos ACO
para resolver o PPOLM, a menos da pesquisa em Sabino (2004).
Comparada à modelagem apresentada na dissertação de mestrado em
Sabino (2004), este estudo estendeu a análise do PPOLM a mais que
um problema de atribuição de locomotivas a manobras, pois
considera os potenciais conflitos de alocação de linhas nas rotas das
locomotivas de manobras. Além disso, a fase de testes
computacionais recebeu uma contribuição significativa com o
advento do programa gerador de manobras, o qual possibilitou uma
análise mais detalhada dos resultados.
Sob o ponto de vista metodológico, esta pesqui sa apresenta as seguintes
contribuições:
PUC-Rio - Certificação Digital Nº 0321287/CA
101
Em extensão à tradicional classificação hierárquica do planejamento
ferroviário, este trabalho analisa mais detalhadamente o
planejamento operacional de pátios e propõe a decomposição do
mesmo em três etapas.
Com relação ao método usado para resolver o PPOLM, é sabido que
muitas implementações de ACO tratam de abstrações de problemas
do mundo real, como o problema do caixeiro viajante, mas esta
pesquisa foi motivada e realmente produz uma solução para um
problema da vida real.
Sobre a determinação das rotas mínimas, embora o método utilizado
seja o conhecido algoritmo de Dijkstra, a modelagem e estrutura de
dados utilizada, bem como a criação do conceito de distância
variável no tempo e o tratamento dos conflitos de alocação de linhas
constitui, por si só, uma das contribuições deste trabalho.
Finalmente, sob o aspecto prático, o projeto de aplicação do algoritmo aqui
proposto é atualmente uma realidade. Encontra-se em andamento a
implementação do YoYo como núcleo de uma ferramenta de suporte à decisão
para o planejamento operacional de pátio ferroviário. A conclusão deste projeto
concederá a este trabalho a oportunidade de implementação na vida real,
contribuindo para a melhoria dos processos de negócio.
As seguintes iniciativas são possibilidades de extensão futura desta
pesquisa:
Refinamento da estimativa da velocidade de deslocamento da
locomotiva, o que aumentaria a precisão da previsão de conflito por
alocação de linhas nas rotas das locomotivas;
Implementação e testes do algoritmo proposto para cálculo de rotas
mínimas utilizando o custo variável dinâmico;
Implementação de uma versão do algoritmo proposto utilizando
processamento paralelo. Desta forma, é provável que seja possível
obter soluções melhores em menor tempo de processamento e sem
aumento considerável do custo dos recursos computacionais
PUC-Rio - Certificação Digital Nº 0321287/CA
102
necessários, já que nota-se uma proliferação de computadores com
processadores de dois núcleos no mercado;
Aperfeiçoamento do algoritmo do programa SOGY, com a
introdução de variáveis aleatórias independentes para controlar o
fluxo de vagões por cada área do pátio;
Desenvolvimento de um método de aferição do grau de similaridade
dos resultados do programa SOGY com manobras reais,
possibilitando assim a avaliação da qualidade da simulação e
fornecendo, portanto, uma referência para aprimoramento do
programa;
Verificação da viabilidade de modelagem do PPOLM como
problema de programação inteira e implementação de novo
algoritmo de solução para o mesmo, utilizando as melhores técnicas
de obtenção de solução exata para este tipo de problema. O objetivo,
neste caso, seria verificar se é possível obter a solução do PPOLM
em um tempo razoável o bastante para a sua aplicação na vida real.
Desenvolvimento de uma análise de impacto da implantação do
algoritmo YoYo em um sistema ferroviário em operação, já que a
melhoria das operações de um pátio, isoladamente, pode provocar
gargalos em outros pátios ou em trechos da ferrovia. Esta análise de
impacto pode identificar a necessidade de outras ferramentas para
tornar viável a implantação da solução proposta em um pátio real.
PUC-Rio - Certificação Digital Nº 0321287/CA
7
Referências Bibliográficas
[1] AHUJA, R.K.; JHA, K.C. New Approaches for Solving the Block-to-Train
Assignment Problem, Department of Industrial & Systems Engineering,
University of Florida, Gainesville, FL, 2004. Relatório Técnico.
[2] AHUJA, R.K.; JHA, K.C.; LIU J. Solving real-life railroad blocking
problems. Department of Industrial & Systems Engineering, University of
Florida, Gainesville, FL, USA, 2004. Relatório Técnico,
[3] AHUJA, R.K.; LIU J.; ORLON, J.B.; SHARMA, D.; SHUGHART, L.A.
Solving real-life locomotive scheduling problems. Transportation Science, v.
32, p. 358-369, 2002.
[4] ALBUQUERQUE, M.C. Indicadores de desempenho no transporte ferroviário
de carga. Dissertação de mestrado. Pontifícia Universidade Católica do Rio de
Janeiro, Rio de Janeiro, 2006.
[5] ASSAD, A. A., Modeling of rail networks: Toward a routing/makeup model,
Transportation Research, v. 14B, p. 101-114, 1980.
[6] BALDACCI, R.; MANIEZZO, V. ; MINGOZZI, A. An exact method for the
car pooling problem based on Lagrangean column generation. Operations
Research, v. 52, p.422-439, 2004.
[7] BARCUS, L. et al. Routing Design for Less-Than-Truckload Motor Carriers
Using Ant Colony Techniques. Departamento de Economía de la Empresa,
Universidad Carlos III de Madrid, 2004. Relatório Técnico.
[8] BEKTAS, T.; CRAINIC, T.G.; MORENCY, V. Improving performance of
rail yards through dynamic reassignments of empty cars. Centre
Interuniversitaire de Recherche sur les Réseaux d’Entreprise, la Logistique et
le Transport (CIRRELT). Relatório Técnico. Disponível em :
<
http://www.forac.ulaval.ca:1037/Publications/Documents%20de%20travail
%202007/CIRRELT-2007-19.pdf >. Acesso em 12/12/2007.
PUC-Rio - Certificação Digital Nº 0321287/CA
104
[9] BIANCHI, L. Ant Colony Optimization and Local Search for the Probabilistic
Traveling Salesman Problem: A Case Study in Stochastic Combinatorial
Optimization. Tese de Doutorado, ULB – Université Libre de Bruxelles, 2006.
[10] BIRATTARI, M., DORIGO, M., How to assess and report the
performance of a stochastic algorithm on a benchmark problem: Mean or best
result on a number of runs? Optimization Letters, v. 1, n. 3, p. 309-311,
2007.
[11] BIRATTARI, M. On the estimation of the expected performance of a
metaheuristic on a class of instances. How many instances, how many runs?,
Technical Report. IRIDIA, Université Libre de Bruxelles, Brussels, Belgium,
2004.
[12] BLACK, Paul E. Dijkstra's algorithm. Dictionary of Algorithms and
Data Structures [online], Paul E. Black, ed., U.S. National Institute of
Standards and Technology. 2006. Publicação Online. Disponível em:
<
http://www.nist.gov/dads/HTML/dijkstraalgo.html>. Acesso em: 6/2/2008.
[13] BLUM, Christian; ROLI, Andrea. Metaheuristics in Combinatorial
Optimization: Overview and Conceptual Comparison. ACM Computing
Surveys, v. 35, n. 3, p. 268–308, 2003.
[14] BULLNHEIMER, B., HARTL, R.F., STRAUSS, C.: A new rank-based
version of the Ant System: A computational study. Central European
Journal for Operations Research and Economics, v. 7, p. 25–38, 1999.
[15] BUSSIECK, M. R., WINTER, T., ZIMMERMANN, U. T. Discrete
Optimization in Public Rail Transport. Mathematical Programming, v. 79,
p. 415-444, 1997.
[16] CASTELLO BRANCO, J. E. (Ed.); FERREIRA, R. (Ed.). Tratado de
estradas de ferro: material rodante. 438 p, Rio de Janeiro, 2000.
[17] CHARNES, A. & MILLER, M. H.: A model for the optimal programming
of railway freight train movements, Management Science, 3, 74–92, 1956.
[18] COLORNI, A.; DORIGO, M.; MANIEZZO, V. Distributed optimization
by ant colonies. Proceedings of the First European Conference on
Artificial Life. p. 134-142, Cambridge, MA, MIT Press, 1992.
PUC-Rio - Certificação Digital Nº 0321287/CA
105
[19] CORDEAU, J.-F. A branch-and-cut algorithm for the dial-a-ride problem.
Operations Research. n. 54, p. 573–586, 2006.
[20] CORDEAU J-F; LAPORTE G. A tabu search heuristic for the static multi-
vehicle dial-a-ride problem. Transportation Research Part B, n. 37, p. 579-
594, 2003.
[21] CRAINIC, Teodor Gabriel; KIM Intermodal Transportation. Handbooks
In Operations Research & Management Science: Transportation, n. 14, p.
467-529. C. Barnhart, G. Laporte (eds.). North Holland. Oxford, UK, 2007.
[22] CRAINIC, Teodor Gabriel. Long Haul Freight Transportation. Handbook
of Transportation Science. R.W. Hall (Ed.), 2nd Edition, Kluwer, 2002.
[23] CRAINIC, Teodor Gabriel; LAPORTE, Gilbert. Planning models for
freight transportation. European Journal of Operational Research. n. 97, p.
409-438, 1997.
[24] CRAINIC, Teodor Gabriel; ROY, Jacques. OR tools for tactical freight
transportation planning. European Journal of Operational Research. n. 33,
p. 290-297, 1988.
[25] CRAINIC, Teodor Gabriel; FERLAND, Jacques A.; ROUSSEAU, Jean
Marc. A Tactical Planning Model for Rail Freight Transportation.
Transportation Science, v.18, n. 2, p. 165-184, 1984.
[26] CRAINIC, Teodor Gabriel; FERLAND, Jacques A.; ROUSSEAU, Jean
Marc. Un modèle de planification pour le transport ferroviaire des
merchandises. Centre de Recherche sur les Transports. Publication # 195.
Université de Montréal. Montreal, Canadá, 1980.
[27] DAGANZO, Carlos F.; DOWLING, Richard G.; HALL, Randolph W.
Railroad Classification Yard Throughput: The Case of Multistage Triangular
Sorting. Transportation Research, vol. 17A, n. 2, p. 95-106, University of
California, Berkeley (CA), EUA, 1983.
[28] DELL’AMICO, M. ; RIGHINI, G.; SALANI, M. A Branch-and-Price
Approach to the Vehicle Routing Problem with Simultaneous Distribution and
Collection. Transportation Science, v. 40, n. 2, p. 235-247, 2006.
PUC-Rio - Certificação Digital Nº 0321287/CA
106
[29] DELL’AMICO, M. ; MONACI, M.; PAGANI, C; VIGO, D. Heuristic
approaches for the Fleet Size and Mix Vehicle Routing Problem with Time
Windows. Transportation Science, v. 41, n. 4, p. 516-526. 2007.
[30] DIESTEL, REINHARD. Graph Theory. 3.Ed. Heidelberg, Alemanha:
Springer-Verlag, 2005. 411p.
[31] DIÓGENES, G. S. Uma contribuição ao estudo dos indicadores de
desempenho operacional de ferrovias de carga: O caso da Companhia
Ferroviária do Nordeste. Dissertação de mestrado. COPPE/UFRJ, Rio de
Janeiro, 2002
[32] DIRNBERGER, J. R.; BARKAN, C. P. L. Lean railroading: Improving
railroad classification terminal performance through bottleneck management
methods. Transportation Research Record - Journal of the
Transportation Research Board, n. 1995, p. 52-61. 2007. Disponível em:
<
http://cee.uiuc.edu/railroad/CEE/pdf/Dirnberger%20&%20Barkan%202007.
pdf>. Acesso em: 31/5/2008.
[33] DORIGO, M., BIRATTARI, M., STÜTZLE, T. Ant colony optimization:
Artificial ants as a computational intelligence technique. IEEE
Computational Intelligence Magazine, v. 1, n. 4, p. 28-39, 2006.
[34] DORIGO , M. ; BLUM, C. Ant colony optimization theory: A survey.
Theoretical Computer Science, v. 344, n 2-3, p. 243-278, 2005.
[35] DORIGO, M., STÜTZLE, T.: Ant Colony Optimization. 7.ed.
Cambridge, MA, EUA: MIT Press, 2004. 305p.
[36] DORIGO, M.; STÜTZLE, T. The Ant Colony Optimization Metaheuristic:
Algorithms, Applications, and Advances. Université Libre de Bruxelles,
IRIDIA, Brussels, Belgium, 2000. Relatório Técnico.
[37] DORIGO, M., Optimization, Learning and Natural Algorithms, Tese de
Doutorado – Politecnico di Milano, 1992.
[38] DORIGO M., MANIEZZO V., COLORNI, A. Positive Feedback as a
Search Strategy. Politecnico di Milano, Dipartimento di Elettronica, Itália,
1991. Relatório Técnico.
PUC-Rio - Certificação Digital Nº 0321287/CA
107
[39] DUMAS, Y., DESROSIERS, J. e SOUMIS, F. The pickup and delivery
problem with time windows. European Journal of Operational Research, v.
54, p. 7-22, 1991.
[40] DYKE, Carl Van. Asset Velocity, Terminal Performance and Network
Fluidity. In: MULTIRAIL, 2006, Princeton, NJ, EUA. Disponível em: <
http://www.railplanning.com/MR2006docs/Carl%20Van%20Dyke_Network
%20Performance.pdf>. Acesso em: 31/5/2008.
[41] FOSTER, I. Designing and Building Parallel Programs. Online Publishing
Project of Addison-Wesley Inc., Argonne National Laboratory and the NSF
Center for Research on Parallel Computation. Publicação Online. 2005.
Disponível em: <http://www-unix.mcs.anl.gov/dbpp/>, Acesso em: 1/12/2006.
[42] FRANZESE, L. A. G. FIORONI, M. M. BOTTER, R. C. Railroad
Simulator on Closed Loop, Anais do Proceedings of the 2003 Winter
Simulation Conference; v. 2, p. 1602-1606, New Orleans, LA, EUA. 2003.
[43] GAMBARDELLA, L. M.; RIZZOLI, A. E.; OLIVERIO, F.;
CASAGRANDE, N.; DONATI, A. V.; MONTEMANNI, R.; LUCIBELLO,
E. Ant Colony Optimization for vehicle routing in advanced logistics systems.
MAS2003 - The International Workshop on Modeling & Applied
Simulation, p. 3-9, Ed. A. G. Bruzzone e R. Mosca, 2003.
[44] GARCIA, I.; GUTIERREZ, G. A simulation model for strategic planning
in rail freight transport systems. Institute of Transportation Engineers. ITE
Journal. v. 73, n. 9, 2003. Publicação Online. Disponível em:
<
http://findarticles.com/p/articles/mi_qa3734/is_200309/ai_n9269474>.
Acesso em: 21/12/2007.
[45] GUALDA, N.D.F., MURGEL, L. M. F. G., A Model for the Train
Formation Problem, Third International Meeting for Research in Logistics,
Trois-Rivières, Québec, Canada, 2000.
[46] GUTJAHR, WALTER J. First Steps to the Runtime Complexity Analysis
of Ant Colony Optimization. Technical Report. Department of Statistics and
Decision Support Systems, University of Vienna, Áustria, 2007.
PUC-Rio - Certificação Digital Nº 0321287/CA
108
[47] JIN, Y.; MURIEL, A. Single-Warehouse Multi-Retailer Inventory
Systems with Full TruckLoad Shipments. Relatório Técnico. Supply Chain
Management Lab, University of Massachussetts – Amherst, MA, EUA, 2005.
Disponível em: <
http://scmlab.ecs.umass.edu/jin/NRLJun05.pdf>. Acesso em:
4/3/2008.
[48] KEATON, M. H., Designing Optimal Railroad Operating Plans:
Lagrangian Relaxation and Heuristic Approaches, Transportation Research. v.
23B. n. 6, p. 415-431. Pergamon Press, Great Britain, 1989.
[49] KRAFT, E. R. A Reservations-Based Railway Network Operations
Management System. 244p. Tese de Doutorado. Department of Systems
Engineering, University of Pennsylvania, Philadelphia, PA, EUA, 1998.
[50] KUO, Ching-Chung; NICHOLLS, Gillian M. A mathematical modeling
approach to improving locomotive utilization at a freight railroad. Omega:
The International Journal of Management Science. v. 35, p. 472-485.
2007.
[51] LEE Y. H., KIM J. I., KANG K. H; KIM, K. H. A heuristic for vehicle
fleet mix problem using tabu search and set partitioning, Journal of the
Operational Research Society. 2007. Publicação Online. Disponível em:
<
http://www.palgrave-
journals.com/jors/journal/vaop/ncurrent/abs/2602421a.html>. Acesso em:
18/11/2007.
[52] LI, Haibing; LIM Andrew. A Metaheuristic for the Pickup and Delivery
Problem with Time WindowS. International Journal on Artificial
Intelligence Tools, v. 12, n. 2. p. 173-186, 2003.
[53] LINDNER, Thomas. Train Schedule Optimization in Public Rail
Transport. 139p. Tese de Doutorado – Departamento de Matemática e
Informática. Universidade de Braunschweig, Alemanha, 2000.
[54] LU, Quan; DESSOUKY, Maged M. A new insertion-based construction
heuristic for solving the pickup and delivery problem with time windows.
European Journal of Operational Research, v. 175, n. 2, p. 672-687, 2006.
PUC-Rio - Certificação Digital Nº 0321287/CA
109
[55] LU, Q, DESSOUKY, M. An Exact Algorithm for the Multiple Vehicle
Pickup and Delivery Problem. Transportation Science, v. 38(4), p. 503-514,
2004.
[56] LÜBBECKE, Marco. Engine Schedule by Column Generation. 181p. Tese
de Doutorado. Braunnschweig University of Technology, Alemanha, 2001.
[57] MANIEZZO, V., CARBONARO, A. Ant Colony Optimization: An
Overview. 20p. Scienze dell’Informazione, University of Bologna, Bologna,
Italy, 1999. Relatório Técnico.
[58] MARIN, A.; SALMERON, J. Tactical design of rail freight networks. Part
I: Exact and heuristic methods. European Journal of Operational Research.
n. 90, p. 26-44, 1996a.
[59] MARIN, A.; SALMERON, J. Tactical design of rail freight networks. Part
II: Local search methods with statistical analysis. European Journal of
Operational Research. n. 94, p. 43-53, 1996b.
[60] MARTINELLI, D.R.; HUALIANG, T., Optimization of Railway
Operations Using Neural Networks, Transportation Research, vol. 4, n. 1,
pp 33-49, United Kingdom, 1996.
[61] MITROVIC-MINIC, S. Pickup and Delivery Problem with Time
Windows: A Survey. Burnaby, BC, Canada. 43p. Technical report: SFU
CMPT TR 1998-12 – School of Computing Science, Simon Fraser University,
1998.
[62] MITROVIC-MINIC, S.; LAPORTE, G. Waiting Strategies for the
Dynamic Pickup and Delivery Problem with Time Windows. Technical
report: SFU CMPT TR 1998-12 – School of Computing Science, Simon
Fraser University, 2003.
[63] NANRY, W.P.; BARNES, J.W. Solving the Pickup and Delivery Problem
with Time Windows using Tabu Search, Transportation Research Part B, n.
34, p. 107-121, 2000.
[64] OBITKO, Marek. Uma introdução aos Algoritmos Genéticos com Java
applets. 1998. Tradução Hermelindo Pinheiro Manoel. Publicação Online.
PUC-Rio - Certificação Digital Nº 0321287/CA
110
Disponível em: <
http://www.professor.webizu.org/ga/>. Acesso em:
23/02/2008.
[65] PACHL, J.: Railway Operation and Control. VTD Publishing. 2002.
[66] PARRAGH, S. N.; DOERNER, K. F.; HARTL R. F. A survey on pickup
and delivery models Part II: Transportation between pickup and delivery
locations, Faculty of Business, Economic and Statistics, Department of
Business Studies, University of Vienna, Vienna, Austria, 2006. Relatório
Técnico.
[67] REIMANN, Marc. Ant Based Optimization in Goods Transportation.
141p. Tese de Doutorado – University of Vienna, Austria, 2002.
[68] REIS Jr., W.O. Um Otimizador Branch & Bound Paralelo para Manobras
em Pátios Ferroviários. Dissertação de Mestrado – Departamento de
Informática, Centro Tecnológico, Universidade Federal do Espírito Santo,
Vitória (ES), Brasil, 2003.
[69] ROPKE, Stefan; CORDEAU, Jean-François; LAPORTE, Gilbert. Models
and branch-and-cut algorithms for pickup and delivery problems with time
windows. etworks. v. 49, n. 4, p. 258-272, 2007.
[70] SABINO, J. A.; STÜTZLE T.; BIRATTARI, M.; LEAL, J. E. ACO
Applied to Switch Engine Scheduling in a Railroad Yard. In:__ Proceedings
of the 5th International Workshop on Ant Colony Optimization and
Swarm Intelligence - ATS 2006, Brussels, Belgium, 2006. p. 502-503.
[71] SABINO, J. A. Competição Entre Colônias de Formigas Aplicada à
Designação de Locomotivas de Manobras em Pátios Ferroviários. Dissertação
de Mestrado – Departamento de Informática, Centro Tecnológico,
Universidade Federal do Espírito Santo, Vitória (ES), Brasil, 2004.
[72] SABINO, J. A. Ant Colony Systems Applied to Switch Engine
Assignment and Routing in a Railroad Yard, Student Paper Award on
Management Science in Railroad Applications from RASIG, IFORMS
(Institute for Operations Research and Management Science) Annual
Meeting, San Jose, CA, USA, 2002.
PUC-Rio - Certificação Digital Nº 0321287/CA
111
[73] SAVELSBERGH, M.W.P.; SOL, M. The General Pickup and Delivery
Problem. Transportation Research. v. 29, p. 17-29, 1995.
[74] SIGURD, M., PISINGER, D., SIG, M. The pickup and delivery problem
with time windows and precedences. Technical report, University of
Copenhagen, 2000.
[75] TARANTILIS, C.D.; IOANNOU, G.; PRASTACOS, G. Advanced
vehicle routing algorithms for complex operations management problems.
Journal of Food Engineering. v.70, p.455–471, 2005.
[76] TOTH, P.; VIGO, D. The Vehicle Routing Problem. 1. Ed. Philadelphia,
PA, EUA: SIAM, 2002. 367p.
[77] TOTH, P.; VIGO, D. An Exact Algorithm for the Vehicle Routing
Problem with Backhauls. Transportation Science. v. 31, n. 4, p. 372–385,
1997.
[78] VAIDYANATHAN, Balachandran; AHUJA, Ravindra K.; LIU, Jian;
SHUGHART, Larry A. Real-life locomotive planning: New formulations and
computational results. Transportation Research Part B: Methodological. v.
42, n. 2, p. 147-168, 2008.
[79] WINTER, T. Online and Real-Time Dispatching Problems. PhD thesis,
Braunschweig University of Technology, Braunschweig, Germany, 1999.
[80] YOURDON, E.; COAD, P. Object-Oriented Analysis, 2nd Edition,
Englewood Cliffs, NJ: Prentice-Hall, 1991.
[81] ZHOU, C., TAN, Y., LIAO, L., LIU, Y. Solving the Multi-vehicle Pick-up
and Delivery Problem with Time Widows by New Construction Heuristic.
Proceedings of the Sixth international Conference on intelligent Systems
Design and Applications (ISDA'06), n. 2, Washington, DC, p. 1035-1042,
2006.
PUC-Rio - Certificação Digital Nº 0321287/CA
