IDEAS home Printed from https://ideas.repec.org/a/eee/jomega/v75y2018icp139-153.html
   My bibliography  Save this article

An integrated algorithm for shift scheduling problems for local public transport companies

Author

Listed:
  • Ciancio, Claudio
  • Laganà, Demetrio
  • Musmanno, Roberto
  • Santoro, Francesco

Abstract

This paper presents an integrated approach to solve two shift scheduling problems for local public bus companies: the first one aims at finding a schedule for vehicles, given a set of rides to do; the second one aims at assigning drivers to vehicle schedules. The first subproblem to be faced is the Multiple Depot Vehicle Scheduling Problem that is known to be NP-hard. Therefore, heuristic algorithms are needed to find feasible solutions for real-life instances. In this work a starting solution for this problem is found by using a greedy algorithm. This solution is then improved by a simulated annealing strategy that exploits several local search techniques. The second problem to deal with is the Crew Scheduling Problem where each trip is assigned to a driver. This problem is still NP-Hard. In this paper an initial solution for the Crew Scheduling Problem is firstly found with a classical sequential approach. This solution is then modified by changing the allocation of trips on vehicles in order to minimize the combined objective function. Both the problems have been modeled taking into account as more real-world constraints as possible. Several constraints take into account the European Union restrictions related to how the driver shifts must be composed. The proposed problem is different from the ones presented in the literature, as the mathematical model, and the related algorithm, are designed based on real world-requirements. Computational results have been carried out on large real-word instances. The results show that the proposed algorithm is able to find quickly good solutions within a limited computational time.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:jomega:v:75:y:2018:i:c:p:139-153
    DOI: 10.1016/j.omega.2017.02.007
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0305048316304789
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.omega.2017.02.007?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. Mauro Dell'Amico & Matteo Fischetti & Paolo Toth, 1993. "Heuristic Algorithms for the Multiple Depot Vehicle Scheduling Problem," Management Science, INFORMS, vol. 39(1), pages 115-125, January.
    2. 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.
    3. Ghoseiri, Keivan & Szidarovszky, Ferenc & Asgharpour, Mohammad Jawad, 2004. "A multi-objective train scheduling model and solution," Transportation Research Part B: Methodological, Elsevier, vol. 38(10), pages 927-952, December.
    4. David S. Johnson & Cecilia R. Aragon & Lyle A. McGeoch & Catherine Schevon, 1989. "Optimization by Simulated Annealing: An Experimental Evaluation; Part I, Graph Partitioning," Operations Research, INFORMS, vol. 37(6), pages 865-892, December.
    5. Olli Bräysy & Michel Gendreau, 2005. "Vehicle Routing Problem with Time Windows, Part I: Route Construction and Local Search Algorithms," Transportation Science, INFORMS, vol. 39(1), pages 104-118, February.
    6. L Cavique & C Rego & I Themido, 1999. "Subgraph ejection chains and tabu search for the crew scheduling problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 50(6), pages 608-616, June.
    7. Crevier, Benoit & Cordeau, Jean-Francois & Laporte, Gilbert, 2007. "The multi-depot vehicle routing problem with inter-depot routes," European Journal of Operational Research, Elsevier, vol. 176(2), pages 756-773, January.
    8. Kliewer, Natalia & Mellouli, Taieb & Suhl, Leena, 2006. "A time-space network based exact optimization model for multi-depot bus scheduling," European Journal of Operational Research, Elsevier, vol. 175(3), pages 1616-1627, December.
    9. Karla L. Hoffman & Manfred Padberg, 1993. "Solving Airline Crew Scheduling Problems by Branch-and-Cut," Management Science, INFORMS, vol. 39(6), pages 657-682, June.
    10. Celso C. Ribeiro & François Soumis, 1994. "A Column Generation Approach to the Multiple-Depot Vehicle Scheduling Problem," Operations Research, INFORMS, vol. 42(1), pages 41-52, February.
    11. Cynthia Barnhart & Ellis L. Johnson & George L. Nemhauser & Martin W. P. Savelsbergh & Pamela H. Vance, 1998. "Branch-and-Price: Column Generation for Solving Huge Integer Programs," Operations Research, INFORMS, vol. 46(3), pages 316-329, June.
    12. Pepin, A.S. & Desaulniers, G. & Hertz, A. & Huisman, D., 2006. "Comparison of heuristic approaches for the multiple depot vehicle scheduling problem," Econometric Institute Research Papers EI 2006-34, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    13. 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.
    14. Koulamas, C & Antony, SR & Jaen, R, 1994. "A survey of simulated annealing applications to operations research problems," Omega, Elsevier, vol. 22(1), pages 41-56, January.
    15. 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.
    16. Haghani, Ali & Banihashemi, Mohamadreza & Chiang, Kun-Hung, 2003. "A comparative analysis of bus transit vehicle scheduling models," Transportation Research Part B: Methodological, Elsevier, vol. 37(4), pages 301-322, May.
    17. Beasley, J. E. & Cao, B., 1996. "A tree search algorithm for the crew scheduling problem," European Journal of Operational Research, Elsevier, vol. 94(3), pages 517-526, November.
    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. Basso, Franco & Guajardo, Mario & Varas, Mauricio, 2020. "Collaborative job scheduling in the wine bottling process," Omega, Elsevier, vol. 91(C).
    2. Asvin Goel & Thibaut Vidal & Adrianus Leendert Kok, 2021. "To team up or not: single versus team driving in European road freight transport," Flexible Services and Manufacturing Journal, Springer, vol. 33(4), pages 879-913, December.
    3. Marlin Ulmer & Martin Savelsbergh, 2020. "Workforce Scheduling in the Era of Crowdsourced Delivery," Transportation Science, INFORMS, vol. 54(4), pages 1113-1133, July.
    4. Neves-Moreira, Fábio & Veldman, Jasper & Teunter, Ruud H., 2021. "Service operation vessels for offshore wind farm maintenance: Optimal stock levels," Renewable and Sustainable Energy Reviews, Elsevier, vol. 146(C).
    5. Neves-Moreira, Fábio & Amorim-Lopes, Mário & Amorim, Pedro, 2020. "The multi-period vehicle routing problem with refueling decisions: Traveling further to decrease fuel cost?," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 133(C).
    6. 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.

    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. 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.
    2. Jing-Quan Li, 2014. "Transit Bus Scheduling with Limited Energy," Transportation Science, INFORMS, vol. 48(4), pages 521-539, November.
    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. 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.
    5. 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.
    6. Kulkarni, Sarang & Krishnamoorthy, Mohan & Ranade, Abhiram & Ernst, Andreas T. & Patil, Rahul, 2018. "A new formulation and a column generation-based heuristic for the multiple depot vehicle scheduling problem," Transportation Research Part B: Methodological, Elsevier, vol. 118(C), pages 457-487.
    7. 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.
    8. Eveborn, Patrik & Flisberg, Patrik & Ronnqvist, Mikael, 2006. "Laps Care--an operational system for staff planning of home care," European Journal of Operational Research, Elsevier, vol. 171(3), pages 962-976, June.
    9. Pan, Hanchuan & Liu, Zhigang & Yang, Lixing & Liang, Zhe & Wu, Qiang & Li, Sijie, 2021. "A column generation-based approach for integrated vehicle and crew scheduling on a single metro line with the fully automatic operation system by partial supervision," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 152(C).
    10. 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.
    11. 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.
    12. 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.
    13. Mohamed Haouari & Farah Zeghal Mansour & Hanif D. Sherali, 2019. "A New Compact Formulation for the Daily Crew Pairing Problem," Transportation Science, INFORMS, vol. 53(3), pages 811-828, May.
    14. Amy Mainville Cohn & Cynthia Barnhart, 2003. "Improving Crew Scheduling by Incorporating Key Maintenance Routing Decisions," Operations Research, INFORMS, vol. 51(3), pages 387-396, June.
    15. Rosemary T. Berger & Collette R. Coullard & Mark S. Daskin, 2007. "Location-Routing Problems with Distance Constraints," Transportation Science, INFORMS, vol. 41(1), pages 29-43, February.
    16. Ricard, Léa & Desaulniers, Guy & Lodi, Andrea & Rousseau, Louis-Martin, 2024. "Increasing schedule reliability in the multiple depot vehicle scheduling problem with stochastic travel time," Omega, Elsevier, vol. 127(C).
    17. Raymond Kwan & Ann Kwan, 2007. "Effective search space control for large and/or complex driver scheduling problems," Annals of Operations Research, Springer, vol. 155(1), pages 417-435, November.
    18. Omar Foutlane & Issmail Hallaoui & Pierre Hansen, 2022. "Distributed Integral Column Generation for Set Partitioning Problems," SN Operations Research Forum, Springer, vol. 3(2), pages 1-22, June.
    19. 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.
    20. Haase, Knut, 1999. "Retail business staff scheduling under complex labor relations," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 511, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.

    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:jomega:v:75:y:2018:i:c:p:139-153. 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/wps/find/journaldescription.cws_home/375/description#description .

    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.