Um algoritmo genético multiobjetivo para a programação integrada de veículos e tripulações

Bruno de Athayde Prata

Resumo


O Vehicle and Crew Scheduling Problem (VCSP) é um difícil problema de Otimização Combinatória, objeto de pesquisa continuada ao longo dos últimos anos. Tendo em consideração a gama de variáveis relacionadas com o VCSP, há uma série de características práticas do problema que não têm sido contempladas nas soluções geradas computacionalmente. Os modelos existentes na literatura focam somente na minimização de custos. No entanto, outros objetivos ou critérios devem ser considerados como, por exemplo, a redução nos intervalos de lanche dos tripulantes. Este artigo tem como objetivo reportar o desenvolvimento de uma abordagem multiobjetivo, baseada em um Algoritmo Genético, para a otimização integrada da programação de veículos e tripulações em sistemas de transporte público. Experimentos computacionais são apresentados e discutidos. Os resultados obtidos apontam para a possibilidade de, com o uso da abordagem proposta, se obter ganhos significativos em termos de custos de operação e em termos da redução dos tempos de planejamento.


Palavras-chave


Transporte Público; Otimização Combinatória Multiobjetivo; Pareto-based Selection Algorithm.

Texto completo:

PDF

Referências


Baita, F.; Pesenti, R.; Ukovich, W. e Favaretto, D. (2000) A Comparison of Different Solution Approaches to the Vehicle Scheduling Problem in a Practical Case. Computers & Operations Research, v. 27, p. 1249–1269.

DOI: 10.1016/S0305-0548(99)00073-8

Ball, M., Bodin, L. e Dial, R. (1983) A Matching Based Heuristic for Scheduling Mass Transit Crews and Vehicles. Transportation Science, v. 17, p. 4–31.

Bartodziej, P., Derigs, U., Malcherek, D. e Vogel U. (2007) Models and Algorithms for Solving Combined Vehicle and Crew Scheduling Problems With Rest Constraints: an Application to Road Feeder Service Planning in Air Cargo Transportation. OR Spectrum, v. 31, p. 405–429. Disponível em:

Acesso em: 12 ago. 2015.

Beasley, J. E. e Chu, P.C. (1998) Constraint Handling in Genetic Algorithms: the Set Partitioning Problem. Journal of Heuristics, v. 11, p. 323–357. DOI: 10.1023/A:1008668508685

Ceder, A. (2002) Urban transit scheduling: framework, review and examples. Journal of Urban Planning and Development, v. 128, p. 225–244. DOI: 10.1061/(ASCE)0733-9488(2002)128:4(225)

Corne, D. W.; Knowles, J. D.; Oates, M. J. (2000) The Pareto Envelope-based selection algorithm for multiobjective optimization. Proceedings of sixth International Conference on parallel problem solving from Nature, Paris, 2000. Disponível em:

Acesso em: 12 ago. 2015.

Corne, D. W.; Jerram, N. R.; Knowles, J. D.; Oates, M. J. (2001) PESA-II: Region-based selection in evolutionary multiobjective optimization. Proceedings of the Genetic and Evolutonary Computation Conference (GECCO–2001), San Francisco. Disponível em: Acesso em: 12 ago. 2015.

Daduna, J. R. e Paixão, J. M. P. (1995) Vehicle Scheduling for public mass transit – an Overview. In: Daduna, J. R., Branco, I. e Paixão, J. M. P. (Eds.) Computer-Aided Transit Scheduling, Lecture Notes in Economics and Mathematical Systems, Springer, v. 430, p. 76–90.

Deb, K. Multi-objective optimization using evolutionary algorithms. Chichester: John Wiley & Sons, 2001.

Dias, M. T. G. (2005) A new approach to the bus driver scheduling problem using multiobjective genetic algorithms. Ph.D. Thesis (Doctorate in Engineering Sciences). Faculty of Engineering, University of Porto, Porto. Disponível em: Acesso em: 12 ago. 2015.

Falkner, J. C. e Ryan, D. M. (1992) Express: Set Partitioning for Bus Crew Scheduling in Christchurch. In: Desrochers, M. e Rosseau, J. M. (Eds.) Computer-Aided Transit Scheduling: Proceedings of the Fifth International Workshop, Springer, p. 359–378.

Fischetti, M., Lodi, A., Martello, S. e Toth, P. (2001) A Polyhedral Approach to Simplified Crew Scheduling and Vehicle Scheduling Problems. Management Science, v. 47, p. 833–850. DOI: 10.1287/mnsc.47.6.833.9810

Fleurent, C. e Rosseau, J. M. (2007) Integrated Vehicle and Crew Scheduling in Practice. In: Technical Report GIRO, Montreal.

Freling, R., Wagelmans, A. P. M. e Paixão, J. M. P. (1999) An Overview of Models and Techniques for Integrating Vehicle and Crew Scheduling. In: Wilson, N. H. M. (ed.) Computer-aided Transit Scheduling, Lecture Notes in Economics and Mathematical Systems, Springer, v. 471, p. 441–460, Springer.

Freling, R., Huisman, D. e Wagelmans, A.P.M. (2001) Applying an Integrated Approach to Vehicle and Crew Scheduling in Practice. In: Voβ, S. e Daduna, J. R. (eds.) Computer-aided Transit Scheduling, Lecture Notes in Economics and Mathematical Systems, Springer, v. 505, p. 73–90.

Freling, R., Huisman, D. e Wagelmans, A. P. M. (2003) Models and Algorithms for Integration of Vehicle and Crew Scheduling. Journal of Scheduling, v. 6, p. 63–85. Disponível em:

Acesso em: 12 ago. 2015.

Friberg, C. e Haase, K. (1999) An Exact Branch and Cut Algorithm for the Vehicle and Crew Scheduling Problem. In: Wilson, N. H. M. (ed.) Computer-aided Transit Scheduling, Lecture Notes in Economics and Mathematical Systems, Springer, v. 471, p. 63–80.

Gaffi, A. e Nonato, M. (1999) An Integrated Approach to Ex-urban Crew and Vehicle Scheduling Problem. In: Wilson, N. H. M. (ed.) Computer-aided Transit Scheduling, Lecture Notes in Economics and Mathematical Systems, Springer, v. 471, p. 103–128.

Groot, S. W. e Huisman, D. (2008) Vehicle and Crew Scheduling: Solving Large Real-World Instances with an Integrated Approach. In: Hickman, M. Mirchandani e Voβ, S. (eds.) Computer-aided Transit Scheduling, Lecture Notes in Economics and Mathematical Systems, Springer, v. 600, p. 43–56. Disponível em:

Acesso em: 12 ago. 2015.

Haase, K., Desaulniers, G. e Desrosiers, J. (2001) Simultaneous Vehicle and Crew Scheduling in Urban Mass Transit Systems. Transportation Science, v. 35, p. 286–303. DOI: 10.1287/trsc.35.3.286.10153

Huisman, D. (2004) Integrated and Dynamic Vehicle and Crew Scheduling. Tese (Doutorado), Tinbergen Institute, Erasmus University Rotterdam, Rotterdam. Disponível em:

Acesso em: 12 ago. 2015.

Huisman, D., Freling, R. e Wagelmans, A.P.M. (2005) Multiple-depot Integrated Vehicle and Crew Scheduling. Transportation Science, v. 39, p. 491–5025. Disponível em:

Acesso em: 12 ago. 2015.

Klabjan, D., Johnson, E. L., Nemhauser, G. L., Gelman, E. e Ramanaswamy, S. (2001) Solving Large Airline Crew Scheduling Problems: Random Pairing Generation and Strong Branching. Computational Optimization and Applications, v. 20, p. 73–91. DOI: 10.1023/A:1011223523191

Kliewer, N., Amberg, B., e Amberg, B. (2012) Multiple Depot Vehicle and Crew Scheduling with Time Windows for Scheduled Trips. Public Transport, v. 3, p. 213–244. DOI: 10.1007/s12469-011-0049-6

Konak, A.; Coit, D. W. e Smith, A. E. (2006) Multiobjective Optimization Using Genetic Algorithms: a Tutorial. Reliability Engineering and System Safety, v. 91, p. 992–1007.DOI: 10.1016/j.ress.2005.11.018

Laurent, B. e Hao, J.K. (2007) Simultaneous Vehicle and Driver Scheduling: a Case Study in a Limousine Rental Company. Computers & Industrial Engineering, v. 53, p. 542–558. DOI: 10.1016/j.cie.2007.05.011

Laurent, B. e Hao, J. K. (2008) Simultaneous Vehicle and Crew Scheduling for Extra Urban Transports. In: XXI International Conference on Industrial Engineering & Other Applications of Applied Intelligent Systems, Wroclaw.

DOI: 10.1007/978-3-540-69052-8_49

Lourenço, H. R.; J. P. Paixão; Portugal, R. (2000) Multiobjective Metaheuristics for the Bus-driver Scheduling Problem. Transportation Science, v. 35, p. 331–342.DOI: 10.1287/trsc.35.3.331.10147

Mesquita, M. e Paias, A. (2008) Set Partitioning/covering-based Approach for the Integrated Vehicle and Crew Scheduling Problem. Computers & Operations Research, v. 35, p. 1562–1575. DOI: 10.1016/j.cor.2006.09.001

Mesquita M, Paias A, Respicio A (2009) Branching Approaches for Integrated Vehicle and Crew Scheduling. Public Transport, v. 1, p. 21–37. DOI: 10.1007/s12469-008-0005-2

Patrikalakis, G. e Xerokostas, D. (1992) Experimentation with a New Decomposition Scheme of the Urban Public Transport Scheduling. In: Desrochers, M. e Rosseau, J. M. (eds.) Computer-Aided Transit Scheduling: Proceedings of the Fifth International Workshop, Springer, p. 407–425.

Rodrigues, M. K., Souza, C.C. e Moura, A.V. (2006) Vehicle and Crew Scheduling for Urban Bus Lines. European Journal of Operational Research, v. 39, p. 491–5025. DOI: 10.1016/j.ejor.2004.06.035

Silva, G. P.; Prates e R. F. C. (2014) Otimização da Escala Mensal de Motoristas de Ônibus Urbano Utilizand a Heuristica Variable Neighborhood Search, Transportes, v. 22, p. 31–43. DOI: 10.14295/transportes.v22i1.698

Silva, T. A. e Silva, G. P. (2015) O Uso da Metaheurística Guided Local Search para Resolver o Problema de Escala de Ônibus Urbano. Transportes, v. 23, p. 105–116. DOI: 10.14295/transportes.v23i2.856

Silva, G.P. e Cunha, C.B. (2010) O Uso da Técnica de Busca em Vizinhaça de Grande Porte para a Programação da Escala de Motoristas de Ônibus Urbano. Transportes, v.18, p. 37–45. DOI: 10.14295/transportes.v18i2.422.

Steinzen, I. (2007) Topics in Integrated Vehicle and Crew Scheduling in Public Transport. Tese (Doutorado em Ciências da Computação em Negócios), Universidade de Paderborn, Paderborn. Disponível em: Acesso em: 12 ago. 2015.

Steinzen, I., Becker, M. e Suhl, L. (2007) A Hybrid Evolutionary Algorithm for the Vehicle and Crew Scheduling Problem in Public Transit. In: 2007 IEEE Congress on Evolutionary Computation – CEC, Singapore.

DOI: 10.1109/CEC.2007.4424963

Steinzen, I.; Ginter, V.; Suhl, L. e Kliewer, N. (2010) A Time-Space Network Approach for the Integrated Vehicle and Crew Scheduling Problem with Multiple Depots. Transportation Science, v. 44, p. 367–382. DOI: 10.1287/trsc.1090.0304

Valouxis, C. e Housos, E. (2002) Combined Bus and Driver Scheduling. Computers and Operations Research, v. 170, p. 8443–862. DOI: 10.1016/S0305-0548(00)00067-8

Weider, S. (2007) Integration of Vehicle and Duty Scheduling in Public Transport. Tese (Doutorado em Ciências Naturais), Universidade Técnica de Berlim, Berlim. Disponível em: Acesso em: 12 ago. 2015.

Wren, A. e Gualda, N. D. F. (1999) Integrated Scheduling of Buses and Drivers. In: Wilson, N. H. M. (ed.) Computer-aided Transit Scheduling, Lecture Notes in Economics and Mathematical Systems, Springer, v. 471, p. 155–176.

Wren, A. e Rosseau, J. M. (1995) Bus Driver Scheduling – an Overview. In: Daduna, J. R., Branco, I. e Paixão, J. M. P. (eds.) Computer-aided Transit Scheduling, Lecture Notes in Economics and Mathematical Systems, Springer, v. 430, p. 173–183.

Zitzler, E. e Thiele, L. (1999) Multiobjective Evolutionary Algorithms - A Comparative Case Study and the Strenght Pareto Approach. IEEE Transactions on Evolutionary Computation, v. 3, p. 257–271. DOI: 10.1109/4235.797969

Zitzler, E.; Laumanns, M. e Thiele, L. (2001) SPEA 2: Improving the Strenght Pareto Evolutionary Algorithm. In: Technical Report, Swiss Federal Institute Technology, Zurich. Disponível em:

Acesso em: 12 ago. 2015.




DOI: https://doi.org/10.14295/transportes.v24i1.975

Métricas do artigo

Carregando Métricas ...

Metrics powered by PLOS ALM


Direitos autorais 2016 Bruno de Athayde Prata

Licença Creative Commons
Esta obra está licenciada sob uma licença Creative Commons Atribuição 4.0 Internacional.

TRANSPORTES (ISSN: 2237-1346) é uma publicação da ANPET - Associação Nacional de Pesquisa e Ensino em Transportes (www.anpet.org.br)

 

Licença Creative Commons

Este obra está licenciado com uma Licença Creative Commons Atribuição-NãoComercial-CompartilhaIgual 4.0 Internacional.