IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v275y2019i1p280-294.html
   My bibliography  Save this article

A matheuristic for the driver scheduling problem with staff cars

Author

Listed:
  • Perumal, Shyam S.G.
  • Larsen, Jesper
  • Lusby, Richard M.
  • Riis, Morten
  • Sørensen, Kasper S.

Abstract

In the public bus transport industry, it is estimated that the cost of a driver schedule accounts for approximately 60% of a transport company’s operational expenses. Hence, it is important for transport companies to minimize the overall cost of driver schedules. A duty is defined as the work of a driver for a day and the driver scheduling problem (DSP) is concerned with finding an optimal set of driver duties to cover a set of timetabled bus trips. Numerous labor regulations and other practical conditions enforce drivers to travel within the city network to designated bus stops to start/end duty, to take a break or to takeover a bus from another driver. This paper focuses on the driver scheduling problem with staff cars (DSPSC), where staff cars can be utilized by the drivers to fulfill their travel activities. However, staff cars should always be returned to the depot and can perform multiple round trips during the day. The problem is restricted by the number of cars available at the depot. We present a matheuristic for solving the DSPSC and the proposed method is tested on instances from Danish and Swedish companies. A comparison with a state-of-the-art mixed integer programming (MIP) solver indicates that the matheuristic provides better solutions, with comparable computation times, for 6 out of 10 large instances. For instances that have more than 6 staff cars and 1200 bus trips, the improvement is 13–15% on average.

Suggested Citation

  • Perumal, Shyam S.G. & Larsen, Jesper & Lusby, Richard M. & Riis, Morten & Sørensen, Kasper S., 2019. "A matheuristic for the driver scheduling problem with staff cars," European Journal of Operational Research, Elsevier, vol. 275(1), pages 280-294.
    • Handle: RePEc:eee:ejores:v:275:y:2019:i:1:p:280-294
    DOI: 10.1016/j.ejor.2018.11.011
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221718309366
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2018.11.011?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. Li, Jingpeng & Kwan, Raymond S. K., 2003. "A fuzzy genetic algorithm for driver scheduling," European Journal of Operational Research, Elsevier, vol. 147(2), pages 334-344, June.
    2. Stefan Ropke & David Pisinger, 2006. "An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows," Transportation Science, INFORMS, vol. 40(4), pages 455-472, November.
    3. 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.
    4. Muller, Laurent Flindt & Spoorendonk, Simon & Pisinger, David, 2012. "A hybrid adaptive large neighborhood search heuristic for lot-sizing with setup times," European Journal of Operational Research, Elsevier, vol. 218(3), pages 614-623.
    5. Matteo Fischetti & Silvano Martello & Paolo Toth, 1987. "The Fixed Job Schedule Problem with Spread-Time Constraints," Operations Research, INFORMS, vol. 35(6), pages 849-858, December.
    6. 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.
    7. Gilbert Laporte & Roberto Musmanno & Francesca Vocaturo, 2010. "An Adaptive Large Neighbourhood Search Heuristic for the Capacitated Arc-Routing Problem with Stochastic Demands," Transportation Science, INFORMS, vol. 44(1), pages 125-135, February.
    8. Michael Ball & Lawrence Bodin & Robert Dial, 1983. "A Matching Based Heuristic for Scheduling Mass Transit Crews and Vehicles," Transportation Science, INFORMS, vol. 17(1), pages 4-31, February.
    9. Hong Li & Ying Wang & Shi Li & Sujian Li, 2015. "A Column Generation Based Hyper-Heuristic to the Bus Driver Scheduling Problem," Discrete Dynamics in Nature and Society, Hindawi, vol. 2015, pages 1-10, April.
    10. Martin Desrochers & François Soumis, 1989. "A Column Generation Approach to the Urban Transit Crew Scheduling Problem," Transportation Science, INFORMS, vol. 23(1), pages 1-13, February.
    11. 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.
    12. Lusby, Richard Martin & Schwierz, Martin & Range, Troels Martin & Larsen, Jesper, 2016. "An Adaptive Large Neighbourhood Search Procedure Applied to the Dynamic Patient Admission Scheduling Problem," Discussion Papers on Economics 1/2016, University of Southern Denmark, Department of Economics.
    13. Jourdan, L. & Basseur, M. & Talbi, E.-G., 2009. "Hybridizing exact methods and metaheuristics: A taxonomy," European Journal of Operational Research, Elsevier, vol. 199(3), pages 620-629, December.
    14. Tallys H. Yunes & Arnaldo V. Moura & Cid C. de Souza, 2005. "Hybrid Column Generation Approaches for Urban Transit Crew Management Problems," Transportation Science, INFORMS, vol. 39(2), pages 273-288, May.
    15. J-F Cordeau & G Laporte & A Mercier, 2001. "A unified tabu search heuristic for vehicle routing problems with time windows," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 52(8), pages 928-936, August.
    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. Melo, Rafael A. & Queiroz, Michell F. & Ribeiro, Celso C., 2021. "Compact formulations and an iterated local search-based matheuristic for the minimum weighted feedback vertex set problem," European Journal of Operational Research, Elsevier, vol. 289(1), pages 75-92.
    2. Shyam S. G. Perumal & Jesper Larsen & Richard M. Lusby & Morten Riis & Tue R. L. Christensen, 2022. "A column generation approach for the driver scheduling problem with staff cars," Public Transport, Springer, vol. 14(3), pages 705-738, October.
    3. Perumal, Shyam S.G. & Lusby, Richard M. & Larsen, Jesper, 2022. "Electric bus planning & scheduling: A review of related problems and methodologies," European Journal of Operational Research, Elsevier, vol. 301(2), pages 395-413.
    4. Perumal, S.S.G. & Dollevoet, T.A.B. & Huisman, D. & Lusby, R.M. & Larsen, J. & Riis, M., 2020. "Solution Approaches for Vehicle and Crew Scheduling with Electric Buses," Econometric Institute Research Papers EI-2020-02, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    5. Melo, Rafael A. & Queiroz, Michell F. & Santos, Marcio C., 2021. "A matheuristic approach for the b-coloring problem using integer programming and a multi-start multi-greedy randomized metaheuristic," European Journal of Operational Research, Elsevier, vol. 295(1), pages 66-81.
    6. Wang, Mengtong & Chen, Shukai & Meng, Qiang, 2024. "Robust safety driver scheduling for autonomous buses," Transportation Research Part B: Methodological, Elsevier, vol. 184(C).

    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. Shyam S. G. Perumal & Jesper Larsen & Richard M. Lusby & Morten Riis & Tue R. L. Christensen, 2022. "A column generation approach for the driver scheduling problem with staff cars," Public Transport, Springer, vol. 14(3), pages 705-738, October.
    2. Perumal, S.S.G. & Dollevoet, T.A.B. & Huisman, D. & Lusby, R.M. & Larsen, J. & Riis, M., 2020. "Solution Approaches for Vehicle and Crew Scheduling with Electric Buses," Econometric Institute Research Papers EI-2020-02, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    3. Niu, Huimin & Zhou, Xuesong & Tian, Xiaopeng, 2018. "Coordinating assignment and routing decisions in transit vehicle schedules: A variable-splitting Lagrangian decomposition approach for solution symmetry breaking," Transportation Research Part B: Methodological, Elsevier, vol. 107(C), pages 70-101.
    4. 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.
    5. Kuo, Yong-Hong & Leung, Janny M.Y. & Yan, Yimo, 2023. "Public transport for smart cities: Recent innovations and future challenges," European Journal of Operational Research, Elsevier, vol. 306(3), pages 1001-1026.
    6. 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.
    7. Perumal, Shyam S.G. & Lusby, Richard M. & Larsen, Jesper, 2022. "Electric bus planning & scheduling: A review of related problems and methodologies," European Journal of Operational Research, Elsevier, vol. 301(2), pages 395-413.
    8. Vadlamani, Satish & Hosseini, Seyedmohsen, 2014. "A novel heuristic approach for solving aircraft landing problem with single runway," Journal of Air Transport Management, Elsevier, vol. 40(C), pages 144-148.
    9. Guido, Rosita & Groccia, Maria Carmela & Conforti, Domenico, 2018. "An efficient matheuristic for offline patient-to-bed assignment problems," European Journal of Operational Research, Elsevier, vol. 268(2), pages 486-503.
    10. Seokgi Lee & Mona Issabakhsh & Hyun Woo Jeon & Seong Wook Hwang & Byung Chung, 2020. "Idle time and capacity control for a single machine scheduling problem with dynamic electricity pricing," Operations Management Research, Springer, vol. 13(3), pages 197-217, December.
    11. Dayarian, Iman & Crainic, Teodor Gabriel & Gendreau, Michel & Rei, Walter, 2016. "An adaptive large-neighborhood search heuristic for a multi-period vehicle routing problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 95(C), pages 95-123.
    12. TURKEŠ, Renata & SÖRENSEN, Kenneth & HVATTUM, Lars Magnus & BARRENA, Eva & CHENTLI, Hayet & COELHO, Leandro & DAYARIAN, Iman & GRIMAULT, Axel & GULLHAVE, Anders & IRIS, Çagatay & KESKIN, Merve & KIEFE, 2019. "Meta-analysis of metaheuristics: Quantifying the effect of adaptiveness in adaptive large neighborhood search," Working Papers 2019002, University of Antwerp, Faculty of Business and Economics.
    13. 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.
    14. 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.
    15. Farid Momayezi & S. Kamal Chaharsooghi & Mohammad Mehdi Sepehri & Ali Husseinzadeh Kashan, 2021. "The capacitated modular single-allocation hub location problem with possibilities of hubs disruptions: modeling and a solution algorithm," Operational Research, Springer, vol. 21(1), pages 139-166, March.
    16. A. Mingozzi & M. A. Boschetti & S. Ricciardelli & L. Bianco, 1999. "A Set Partitioning Approach to the Crew Scheduling Problem," Operations Research, INFORMS, vol. 47(6), pages 873-888, December.
    17. Turkeš, Renata & Sörensen, Kenneth & Hvattum, Lars Magnus, 2021. "Meta-analysis of metaheuristics: Quantifying the effect of adaptiveness in adaptive large neighborhood search," European Journal of Operational Research, Elsevier, vol. 292(2), pages 423-442.
    18. 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.
    19. 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.
    20. Ciancio, Claudio & Laganà, Demetrio & Musmanno, Roberto & Santoro, Francesco, 2018. "An integrated algorithm for shift scheduling problems for local public transport companies," Omega, Elsevier, vol. 75(C), pages 139-153.

    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:eee:ejores:v:275:y:2019:i:1:p:280-294. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.