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

Autores

DOI:

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

Palavras-chave:

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

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.

Downloads

Não há dados estatísticos.

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:

<http://link.springer.com/article/10.1007%2Fs00291-007-0110-7>

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: <http://link.springer.com/chapter/10.1007%2F3-540-45356-3_82>

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: <https://www.macs.hw.ac.uk/~dwcorne/pesaII.pdf> 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: <https://repositorio-aberto.up.pt/bitstream/10216/11426/2/Texto%20integral.pdf> 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:

<http://link.springer.com/article/10.1023%2FA%3A1022287504028>

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:

<http://link.springer.com/chapter/10.1007%2F978-3-540-73312-6_3>

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:

<http://repub.eur.nl/pub/6779/few_huisman_20040220.pdf>

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:

<http://pubsonline.informs.org/doi/abs/10.1287/trsc.1040.0104>

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: <http://d-nb.info/987434659/34> 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: <https://www.deutsche-digitale-bibliothek.de/binary/TLQVJPFLN7RTLDCM6BQMXWSJ6T6KZGS2/full/1.pdf> 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:

<http://e-collection.library.ethz.ch/eserv/eth:24689/eth-24689-01.pdf>

Acesso em: 12 ago. 2015.

Downloads

Publicado

21-04-2016

Como Citar

Prata, B. de A. (2016). Um algoritmo genético multiobjetivo para a programação integrada de veículos e tripulações. TRANSPORTES, 24(1), 19–30. https://doi.org/10.14295/transportes.v24i1.975

Edição

v. 24 n. 1 (2016)

Seção

Artigos

Licença

Ao submeter um manuscrito para publicação neste periódico, todos os seus autores concordam, antecipada e irrestritamente, com os seguintes termos:

  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. 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.