Vehicle Scheduling with Network Flow Models

Abstract

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.