.

Authors

DOI:

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

Keywords:

Public Transport, Multiobjective combinatorial optimization, Pareto-based Selection Algorithm.

Abstract

The integrated vehicle and crew scheduling problem is a hard, widely studied Combinatorial Optimization problem over the years. Taking into consideration the range of variables related to the planning process of vehicles and drivers, there are several practical characteristics of the problem that are not reflected in the solutions generated computationally. The existing models focus on minimizing costs. However, other objectives must be considered as for example the reduction of meal breaks for the crews. This paper aims at presenting a multiobjective approach for the integrated vehicle and crew scheduling problem in public transport systems based on Genetic Algorithms. Computational results with real instances are presented and discussed. These results indicate that this new approach has a considerable potential for achieving significant gains in terms of operation costs and reduction in planning times.

Downloads

Download data is not yet available.

References

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

Published

2016-04-21

How to Cite

Prata, B. de A. (2016). TRANSPORTES, 24(1), 19–30. https://doi.org/10.14295/transportes.v24i1.975

Issue

Vol. 24 No. 1 (2016)

Section

Artigos

License

Authors who submit papers for publication by TRANSPORTES agree to the following terms:

  1. Authors retain copyright and grant TRANSPORTES the right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.

  2. Authors may enter into separate, additional contractual arrangements for the non-exclusive distribution of this journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in TRANSPORTES.

  3. Authors are allowed and encouraged to post their work online (e.g., in institutional repositories or on their website) after publication of the article. Authors are encouraged to use links to TRANSPORTES (e.g., DOIs or direct links) when posting the article online, as TRANSPORTES is freely available to all readers.

  4. Authors have secured all necessary clearances and written permissions to published the work and grant copyright under the terms of this agreement. Furthermore, the authors assume full responsibility for any copyright infringements related to the article, exonerating ANPET and TRANSPORTES of any responsibility regarding copyright infringement.

  5. Authors assume full responsibility for the contents of the article submitted for review, including all necessary clearances for divulgation of data and results, exonerating ANPET and TRANSPORTES of any responsibility regarding to this aspect.