Vehicle Scheduling with Network Flow Models
DOI:
https://doi.org/10.14295/transportes.v6i2.250Resumo
Este trabalho retrata a primeira fase de uma pesquisa de doutorado voltada para a utilização de modelos de fluxo em redes para programação de veículos (de ônibus, em particular). A utilização de modelos deste tipo ainda e muito pouco explorada na literatura, principalmente pela dificuldade imposta pelo grande numero de variáveis resultante. Neste trabalho são apresentadas formulações para tratamento do problema de programação de veículos associados a um único depósito (ou garagem) como problema de fluxo em redes, incluindo duas técnicas para reduzir o numero de arcos na rede criada e, conseqüentemente, o numero de variáveis a tratar. Uma destas técnicas de redução de arcos foi implementada e o problema de fluxo resultante foi direcionado para ser resolvido, nesta fase da pesquisa, por uma versão disponível do algoritmo Simplex para redes. Problemas teste baseados em dados reais da cidade de Reading, UK, foram resolvidos com a utilização da formulação de fluxo em redes adotada, e os resultados comparados com aqueles obtidos pelo método heurístico BOOST, o qual tem sido largamente testado e comercializado pela School of Computer Studies da Universidade de Leeds, UK. Os resultados alcançados demonstram a possibilidade de tratamento de problemas reais com a técnica de redução de arcos.
ABSTRACT
This paper presents the successful results of a first phase of a doctoral research addressed to solving vehicle (bus, in particular) scheduling problems through network flow formulations. Network flow modeling for this kind of problem is a promising, but not a well explored approach, mainly because of the large number of variables related to number of arcs of real case networks. The paper presents and discusses some network flow formulations for the single depot bus vehicle scheduling problem, along with two techniques of arc reduction. One of these arc reduction techniques has been implemented and the underlying network flow problem addressed to be solved, in research, using a code of the network Simplex algorithm. Test problems based on real cases from the city of Reading, UK, were solved by the network flow approach and the results were compared with those provided by the BOOST system, which has been well tested and commercialized by the School of Computer Studies, University of Leeds, UK. The results show the feasibility of real case treatment with the adopted approach.
Downloads
Downloads
Publicado
Como Citar
Edição
Seção
Licença
Ao submeter um manuscrito para publicação neste periódico, todos os seus autores concordam, antecipada e irrestritamente, com os seguintes termos:
- Os autores mantém os direitos autorais e concedem à Revista TRANSPORTES o direito de primeira publicação do manuscrito, sem nenhum ônus financeiro, e abrem mão de qualquer outra remuneração pela sua publicação pela ANPET.
- Ao ser submetido à Revista TRANSPORTES, o manuscrito fica automaticamente licenciado sob a Licença Creative Commons Attribution, que permite o compartilhamento do trabalho com reconhecimento da autoria e da publicação inicial neste periódico.
- Os autores têm autorização para assumir contratos adicionais separadamente, para distribuição não exclusiva da versão do trabalho publicada neste periódico (ex.: publicar em repositório institucional ou como capítulo de livro), com reconhecimento da publicação inicial nesta revista, desde que tal contrato não implique num endosso do conteúdo do manuscrito ou do novo veículo pela ANPET.
- Os autores têm permissão e são estimulados a publicar e distribuir seu trabalho online (ex.: em repositórios institucionais ou na sua página pessoal) depois de concluído o processo editorial. Como a Revista TRANSPORTES é de acesso livre, os autores são estimulados a usar links para o site da Revista TRANSPORTES nesses casos.
- Os autores garantem ter obtido a devida autorização dos seus empregadores para a transferência dos direitos nos termos deste acordo, caso esses empregadores possuam algum direito autoral sobre o manuscrito. Além disso, os autores assumem toda e qualquer responsabilidade sobre possíveis infrações ao direito autoral desses empregadores, isentando a ANPET e a Revista TRANSPORTES de toda e qualquer responsabilidade neste sentido.
- Os autores assumem toda responsabilidade sobre o conteúdo do trabalho, incluindo as devidas e necessárias autorizações para divulgação de dados coletados e resultados obtidos, isentando a ANPET e a Revista TRANSPORTES de toda e qualquer responsabilidade neste sentido.
