IDEAS home Printed from https://ideas.repec.org/a/spr/orspec/v39y2017i4d10.1007_s00291-017-0485-z.html
   My bibliography  Save this article

Multi-objective integrated acyclic crew rostering and vehicle assignment problem in public bus transportation

Author

Listed:
  • F. Zeynep Sargut

    (Optym)

  • Caner Altuntaş

    (Kentkart Ege Elekronik A.Ş)

  • Dilek Cetin Tulazoğlu

    (Kentkart Ege Elekronik A.Ş)

Abstract

In this study, we try to solve a real planning problem faced in public bus transportation. It is a multi-objective integrated crew rostering and vehicle assignment problem. We model this problem as a multi-objective set partitioning problem. Most of the time, crew rostering problem with a single-objective function is considered, and the output may not satisfy some transport companies. To minimize the cost and maximize the fairness of the workload among the drivers, we define many criteria. Although crew rostering problem and its integrated versions appear in the literature, it is the first time these two problems are integrated. We propose a new multi-objective tabu search algorithm to obtain near Pareto-optimal solutions. The algorithm works with a set of solutions using parallel search. We test our algorithm for the case with ten objectives and define a method to choose solutions from the approximated efficient frontier to present to the user. We discuss the performance of our meta-heuristic approach.

Suggested Citation

  • F. Zeynep Sargut & Caner Altuntaş & Dilek Cetin Tulazoğlu, 2017. "Multi-objective integrated acyclic crew rostering and vehicle assignment problem in public bus transportation," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 39(4), pages 1071-1096, October.
    • Handle: RePEc:spr:orspec:v:39:y:2017:i:4:d:10.1007_s00291-017-0485-z
    DOI: 10.1007/s00291-017-0485-z
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s00291-017-0485-z
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s00291-017-0485-z?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Alberto Caprara & Paolo Toth & Daniele Vigo & Matteo Fischetti, 1998. "Modeling and Solving the Crew Rostering Problem," Operations Research, INFORMS, vol. 46(6), pages 820-830, December.
    2. Huisman, D. & Freling, R. & Wagelmans, A.P.M., 2003. "Multiple-Depot Integrated Vehicle and Crew Scheduling," Econometric Institute Research Papers EI 2003-02, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    3. Mesquita, Marta & Moz, Margarida & Paias, Ana & Pato, Margarida, 2015. "A decompose-and-fix heuristic based on multi-commodity flow models for driver rostering with days-off pattern," European Journal of Operational Research, Elsevier, vol. 245(2), pages 423-437.
    4. Helena R. Lourenço & José P. Paixão & Rita Portugal, 2001. "Multiobjective Metaheuristics for the Bus Driver Scheduling Problem," Transportation Science, INFORMS, vol. 35(3), pages 331-343, August.
    5. Bianco, Lucio & Bielli, Maurizio & Mingozzi, Aristide & Ricciardelli, Salvatore & Spadoni, Massimo, 1992. "A heuristic procedure for the crew rostering problem," European Journal of Operational Research, Elsevier, vol. 58(2), pages 272-283, April.
    6. Freling, R. & Huisman, D. & Wagelmans, A.P.M., 2000. "Models and algorithms for Integration of Vehicle and Crew Scheduling," ERIM Report Series Research in Management ERS-2000-14-LIS, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.
    7. Ernst, A. T. & Jiang, H. & Krishnamoorthy, M. & Sier, D., 2004. "Staff scheduling and rostering: A review of applications, methods and models," European Journal of Operational Research, Elsevier, vol. 153(1), pages 3-27, February.
    8. Hartog, A. & Huisman, D. & Abbink, E.J.W. & Kroon, L.G., 2006. "Decision support for crew rostering at NS," Econometric Institute Research Papers EI 2006-04, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    9. Ingmar Steinzen & Vitali Gintner & Leena Suhl & Natalia Kliewer, 2010. "A Time-Space Network Approach for the Integrated Vehicle- and Crew-Scheduling Problem with Multiple Depots," Transportation Science, INFORMS, vol. 44(3), pages 367-382, August.
    10. Abbink, E.J.W. & Albino, L. & Dollevoet, T.A.B. & Huisman, D. & Roussado, J. & Saldanha, R.L., 2010. "Solving Large Scale Crew Scheduling Problems in Practice," Econometric Institute Research Papers EI 2010-63, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    11. ManMohan Sodhi & Stephen Norris, 2004. "A Flexible, Fast, and Optimal Modeling Approach Applied to Crew Rostering at London Underground," Annals of Operations Research, Springer, vol. 127(1), pages 259-281, March.
    12. Carraresi, P. & Gallo, G., 1984. "A multi-level bottleneck assignment approach to the bus drivers' rostering problem," European Journal of Operational Research, Elsevier, vol. 16(2), pages 163-173, May.
    13. Erwin Abbink & Matteo Fischetti & Leo Kroon & Gerrit Timmer & Michiel Vromans, 2005. "Reinventing Crew Scheduling at Netherlands Railways," Interfaces, INFORMS, vol. 35(5), pages 393-401, October.
    14. Ibarra-Rojas, O.J. & Delgado, F. & Giesen, R. & Muñoz, J.C., 2015. "Planning, operation, and control of bus transport systems: A literature review," Transportation Research Part B: Methodological, Elsevier, vol. 77(C), pages 38-75.
    15. Margarida Moz & Ana Respício & Margarida Vaz Pato, 2009. "Bi-objective evolutionary heuristics for bus driver rostering," Public Transport, Springer, vol. 1(3), pages 189-210, August.
    16. Dennis Huisman & Richard Freling & Albert P. M. Wagelmans, 2005. "Multiple-Depot Integrated Vehicle and Crew Scheduling," Transportation Science, INFORMS, vol. 39(4), pages 491-502, November.
    17. Paola Cappanera & Giorgio Gallo, 2004. "A Multicommodity Flow Approach to the Crew Rostering Problem," Operations Research, INFORMS, vol. 52(4), pages 583-596, August.
    18. Michel Gamache & François Soumis & Gérald Marquis & Jacques Desrosiers, 1999. "A Column Generation Approach for Large-Scale Aircrew Rostering Problems," Operations Research, INFORMS, vol. 47(2), pages 247-263, April.
    19. Knut Haase & Guy Desaulniers & Jacques Desrosiers, 2001. "Simultaneous Vehicle and Crew Scheduling in Urban Mass Transit Systems," Transportation Science, INFORMS, vol. 35(3), pages 286-303, August.
    20. Kulturel-Konak, Sadan & Smith, Alice E. & Norman, Bryan A., 2006. "Multi-objective tabu search using a multinomial probability mass function," European Journal of Operational Research, Elsevier, vol. 169(3), pages 918-931, March.
    21. Mesquita, Marta & Moz, Margarida & Paias, Ana & Pato, Margarida, 2013. "A decomposition approach for the integrated vehicle-crew-roster problem with days-off pattern," European Journal of Operational Research, Elsevier, vol. 229(2), pages 318-331.
    22. Matthias Ehrgott & Xavier Gandibleux, 2004. "Approximative solution methods for multiobjective combinatorial optimization," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 12(1), pages 1-63, June.
    23. Nishi, Tatsushi & Sugiyama, Taichi & Inuiguchi, Masahiro, 2014. "Two-level decomposition algorithm for crew rostering problems with fair working condition," European Journal of Operational Research, Elsevier, vol. 237(2), pages 465-473.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Ana Paias & Marta Mesquita & Margarida Moz & Margarida Pato, 2021. "A network flow-based algorithm for bus driver rerostering," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 43(2), pages 543-576, June.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Ibarra-Rojas, O.J. & Delgado, F. & Giesen, R. & Muñoz, J.C., 2015. "Planning, operation, and control of bus transport systems: A literature review," Transportation Research Part B: Methodological, Elsevier, vol. 77(C), pages 38-75.
    2. Breugem, T. & Dollevoet, T.A.B. & Huisman, D., 2017. "Is Equality always desirable?," Econometric Institute Research Papers EI2017-30, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    3. Heil, Julia & Hoffmann, Kirsten & Buscher, Udo, 2020. "Railway crew scheduling: Models, methods and applications," European Journal of Operational Research, Elsevier, vol. 283(2), pages 405-425.
    4. Margarida Moz & Ana Respício & Margarida Vaz Pato, 2009. "Bi-objective evolutionary heuristics for bus driver rostering," Public Transport, Springer, vol. 1(3), pages 189-210, August.
    5. Markó Horváth & Tamás Kis, 2019. "Computing strong lower and upper bounds for the integrated multiple-depot vehicle and crew scheduling problem with branch-and-price," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 27(1), pages 39-67, March.
    6. Nishi, Tatsushi & Sugiyama, Taichi & Inuiguchi, Masahiro, 2014. "Two-level decomposition algorithm for crew rostering problems with fair working condition," European Journal of Operational Research, Elsevier, vol. 237(2), pages 465-473.
    7. Ingmar Steinzen & Vitali Gintner & Leena Suhl & Natalia Kliewer, 2010. "A Time-Space Network Approach for the Integrated Vehicle- and Crew-Scheduling Problem with Multiple Depots," Transportation Science, INFORMS, vol. 44(3), pages 367-382, August.
    8. Bach, L. & Dollevoet, T.A.B. & Huisman, D., 2014. "Integrating Timetabling and Crew," Econometric Institute Research Papers EI 2014-03, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    9. Lukas Bach & Twan Dollevoet & Dennis Huisman, 2016. "Integrating Timetabling and Crew Scheduling at a Freight Railway Operator," Transportation Science, INFORMS, vol. 50(3), pages 878-891, August.
    10. Dauzère-Pérès, Stéphane & De Almeida, David & Guyon, Olivier & Benhizia, Faten, 2015. "A Lagrangian heuristic framework for a real-life integrated planning problem of railway transportation resources," Transportation Research Part B: Methodological, Elsevier, vol. 74(C), pages 138-150.
    11. Thomas Breugem & Twan Dollevoet & Dennis Huisman, 2022. "Is Equality Always Desirable? Analyzing the Trade-Off Between Fairness and Attractiveness in Crew Rostering," Management Science, INFORMS, vol. 68(4), pages 2619-2641, April.
    12. Jing-Quan Li, 2014. "Transit Bus Scheduling with Limited Energy," Transportation Science, INFORMS, vol. 48(4), pages 521-539, November.
    13. Mesquita, Marta & Moz, Margarida & Paias, Ana & Pato, Margarida, 2015. "A decompose-and-fix heuristic based on multi-commodity flow models for driver rostering with days-off pattern," European Journal of Operational Research, Elsevier, vol. 245(2), pages 423-437.
    14. Maenhout, Broos & Vanhoucke, Mario, 2010. "A hybrid scatter search heuristic for personalized crew rostering in the airline industry," European Journal of Operational Research, Elsevier, vol. 206(1), pages 155-167, October.
    15. Attila Tóth & Miklós Krész, 2013. "An efficient solution approach for real-world driver scheduling problems in urban bus transportation," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 21(1), pages 75-94, June.
    16. Y. Wang (Ying) & Z. Shang (Zheming) & Huisman, D. & D'Ariano, A. & J.C. Zhang (Jinchuan), 2018. "A Lagrangian Relaxation Approach Based on a Time-Space-State Network for Railway Crew Scheduling," Econometric Institute Research Papers EI2018-45, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    17. Asvin Goel & Thibaut Vidal, 2014. "Hours of Service Regulations in Road Freight Transport: An Optimization-Based International Assessment," Transportation Science, INFORMS, vol. 48(3), pages 391-412, August.
    18. Rivi Sandhu & Diego Klabjan, 2007. "Integrated Airline Fleeting and Crew-Pairing Decisions," Operations Research, INFORMS, vol. 55(3), pages 439-456, June.
    19. Breugem, T. & van Rossum, B.T.C. & Dollevoet, T. & Huisman, D., 2022. "A column generation approach for the integrated crew re-planning problem," Omega, Elsevier, vol. 107(C).
    20. Jorge Amaya & Paula Uribe, 2018. "A model and computational tool for crew scheduling in train transportation of mine materials by using a local search strategy," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 26(3), pages 383-402, October.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:orspec:v:39:y:2017:i:4:d:10.1007_s00291-017-0485-z. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.