IDEAS home Printed from https://ideas.repec.org/a/spr/joheur/v30y2024i5d10.1007_s10732-024-09527-0.html
   My bibliography  Save this article

A large-scale neighborhood search algorithm for multi-activity tour scheduling problems

Author

Listed:
  • Rana Shariat

    (McMaster University)

  • Kai Huang

    (McMaster University)

Abstract

In this research, we study multi-activity tour scheduling problems with heterogeneous employees in a service sector where demand varies greatly during the day. The goal is to reduce the overall over- and under- coverage. The shifts and breaks defined with variable starting periods and duration make the problem flexible and hard to solve. To address the problem, an integer programming (IP) model is first proposed. Due to the problem’s complexity, it is impossible to solve instances involving numerous employees and activities in a timely manner. So we propose a heuristic method based on a large neighborhood search algorithm. A combination of context-free grammar (CFG) and resource-constrained shortest path problem is used to create weekly schedules. Moreover, we propose a constraint on task repetition that CFG is unable to express, so we incorporate an IP extension into our proposed algorithm. Importantly, our approach does not rely on any commercial solver like CPLEX. Computational experiments are carried out on the industrial and randomly generated instances to evaluate the performance of the exact IP model solved by CPLEX and the proposed heuristic algorithm. Results reveal that our method outperforms CPLEX in both solution time and solution quality in larger instances.

Suggested Citation

  • Rana Shariat & Kai Huang, 2024. "A large-scale neighborhood search algorithm for multi-activity tour scheduling problems," Journal of Heuristics, Springer, vol. 30(5), pages 225-267, December.
    • Handle: RePEc:spr:joheur:v:30:y:2024:i:5:d:10.1007_s10732-024-09527-0
    DOI: 10.1007/s10732-024-09527-0
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10732-024-09527-0
    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/s10732-024-09527-0?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. Anuj Mehrotra & Kenneth E. Murphy & Michael A. Trick, 2000. "Optimal shift scheduling: A branch‐and‐price approach," Naval Research Logistics (NRL), John Wiley & Sons, vol. 47(3), pages 185-200, April.
    2. Hojati, Mehran & Patil, Ashok S., 2011. "An integer linear programming-based heuristic for scheduling heterogeneous, part-time service employees," European Journal of Operational Research, Elsevier, vol. 209(1), pages 37-50, February.
    3. Leslie C. Edie, 1954. "Traffic Delays at Toll Booths," Operations Research, INFORMS, vol. 2(2), pages 107-138, May.
    4. Hernández-Leandro, Noberto A. & Boyer, Vincent & Salazar-Aguilar, M. Angélica & Rousseau, Louis-Martin, 2019. "A matheuristic based on Lagrangian relaxation for the multi-activity shift scheduling problem," European Journal of Operational Research, Elsevier, vol. 272(3), pages 859-867.
    5. David Pisinger & Stefan Ropke, 2010. "Large Neighborhood Search," International Series in Operations Research & Management Science, in: Michel Gendreau & Jean-Yves Potvin (ed.), Handbook of Metaheuristics, chapter 0, pages 399-419, Springer.
    6. Musliu, Nysret & Schaerf, Andrea & Slany, Wolfgang, 2004. "Local search for shift design," European Journal of Operational Research, Elsevier, vol. 153(1), pages 51-64, February.
    7. Turgut Aykin, 1996. "Optimal Shift Scheduling with Multiple Break Windows," Management Science, INFORMS, vol. 42(4), pages 591-602, April.
    8. Alex Bonutti & Sara Ceschia & Fabio De Cesco & Nysret Musliu & Andrea Schaerf, 2017. "Modeling and solving a real-life multi-skill shift design problem," Annals of Operations Research, Springer, vol. 252(2), pages 365-382, May.
    9. Sandjai Bhulai & Ger Koole & Auke Pot, 2008. "Simple Methods for Shift Scheduling in Multiskill Call Centers," Manufacturing & Service Operations Management, INFORMS, vol. 10(3), pages 411-420, December.
    10. Gérard, Matthieu & Clautiaux, François & Sadykov, Ruslan, 2016. "Column generation based approaches for a tour scheduling problem with a multi-skill heterogeneous workforce," European Journal of Operational Research, Elsevier, vol. 252(3), pages 1019-1030.
    11. S M Al-Yakoob & H D Sherali, 2008. "A column generation approach for an employee scheduling problem with multiple shifts and work locations," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(1), pages 34-43, January.
    12. Kabak, Ozgur & Ulengin, Fusun & Aktas, Emel & Onsel, Sule & Topcu, Y. Ilker, 2008. "Efficient shift scheduling in the retail sector through two-stage optimization," European Journal of Operational Research, Elsevier, vol. 184(1), pages 76-90, January.
    13. Restrepo, María I. & Lozano, Leonardo & Medaglia, Andrés L., 2012. "Constrained network-based column generation for the multi-activity shift scheduling problem," International Journal of Production Economics, Elsevier, vol. 140(1), pages 466-472.
    14. Pastor, Rafael & Olivella, Jordi, 2008. "Selecting and adapting weekly work schedules with working time accounts: A case of a retail clothing chain," European Journal of Operational Research, Elsevier, vol. 184(1), pages 1-12, January.
    15. Marie-Claude Côté & Bernard Gendron & Louis-Martin Rousseau, 2011. "Grammar-Based Integer Programming Models for Multiactivity Shift Scheduling," Management Science, INFORMS, vol. 57(1), pages 151-163, January.
    16. Gary M. Thompson, 1995. "Improved Implicit Optimal Modeling of the Labor Shift Scheduling Problem," Management Science, INFORMS, vol. 41(4), pages 595-607, April.
    Full references (including those not matched with items on IDEAS)

    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. Van den Bergh, Jorne & Beliën, Jeroen & De Bruecker, Philippe & Demeulemeester, Erik & De Boeck, Liesje, 2013. "Personnel scheduling: A literature review," European Journal of Operational Research, Elsevier, vol. 226(3), pages 367-385.
    2. Arpan Rijal & Marco Bijvank & Asvin Goel & René de Koster, 2021. "Workforce Scheduling with Order-Picking Assignments in Distribution Facilities," Transportation Science, INFORMS, vol. 55(3), pages 725-746, May.
    3. Banu Sungur & Cemal Özgüven & Yasemin Kariper, 2017. "Shift scheduling with break windows, ideal break periods, and ideal waiting times," Flexible Services and Manufacturing Journal, Springer, vol. 29(2), pages 203-222, June.
    4. Ağralı, Semra & Taşkın, Z. Caner & Ünal, A. Tamer, 2017. "Employee scheduling in service industries with flexible employee availability and demand," Omega, Elsevier, vol. 66(PA), pages 159-169.
    5. Alex Bonutti & Sara Ceschia & Fabio De Cesco & Nysret Musliu & Andrea Schaerf, 2017. "Modeling and solving a real-life multi-skill shift design problem," Annals of Operations Research, Springer, vol. 252(2), pages 365-382, May.
    6. Lin, Shih-Wei & Ying, Kuo-Ching, 2014. "Minimizing shifts for personnel task scheduling problems: A three-phase algorithm," European Journal of Operational Research, Elsevier, vol. 237(1), pages 323-334.
    7. Jens O. Brunner & Jonathan F. Bard & Jan M. Köhler, 2013. "Bounded flexibility in days‐on and days‐off scheduling," Naval Research Logistics (NRL), John Wiley & Sons, vol. 60(8), pages 678-701, December.
    8. María I. Restrepo & Bernard Gendron & Louis-Martin Rousseau, 2016. "Branch-and-Price for Personalized Multiactivity Tour Scheduling," INFORMS Journal on Computing, INFORMS, vol. 28(2), pages 334-350, May.
    9. Chapados, Nicolas & Joliveau, Marc & L’Ecuyer, Pierre & Rousseau, Louis-Martin, 2014. "Retail store scheduling for profit," European Journal of Operational Research, Elsevier, vol. 239(3), pages 609-624.
    10. Mark W. Isken & Osman T. Aydas, 2022. "A tactical multi-week implicit tour scheduling model with applications in healthcare," Health Care Management Science, Springer, vol. 25(4), pages 551-573, December.
    11. Sana Dahmen & Monia Rekik & François Soumis, 2018. "An implicit model for multi-activity shift scheduling problems," Journal of Scheduling, Springer, vol. 21(3), pages 285-304, June.
    12. Aykin, Turgut, 2000. "A comparative evaluation of modeling approaches to the labor shift scheduling problem," European Journal of Operational Research, Elsevier, vol. 125(2), pages 381-397, September.
    13. Defraeye, Mieke & Van Nieuwenhuyse, Inneke, 2016. "Staffing and scheduling under nonstationary demand for service: A literature review," Omega, Elsevier, vol. 58(C), pages 4-25.
    14. Arjan Akkermans & Gerhard Post & Marc Uetz, 2021. "Solving the shift and break design problem using integer linear programming," Annals of Operations Research, Springer, vol. 302(2), pages 341-362, July.
    15. Anuj Mehrotra & Kenneth E. Murphy & Michael A. Trick, 2000. "Optimal shift scheduling: A branch‐and‐price approach," Naval Research Logistics (NRL), John Wiley & Sons, vol. 47(3), pages 185-200, April.
    16. Michael Römer, 2024. "Block-based state-expanded network models for multi-activity shift scheduling," Journal of Scheduling, Springer, vol. 27(4), pages 341-361, August.
    17. Restrepo, María I. & Gendron, Bernard & Rousseau, Louis-Martin, 2017. "A two-stage stochastic programming approach for multi-activity tour scheduling," European Journal of Operational Research, Elsevier, vol. 262(2), pages 620-635.
    18. Marie-Claude Côté & Bernard Gendron & Louis-Martin Rousseau, 2011. "Grammar-Based Integer Programming Models for Multiactivity Shift Scheduling," Management Science, INFORMS, vol. 57(1), pages 151-163, January.
    19. Douglas S. Altner & Anthony C. Rojas & Leslie D. Servi, 2018. "A two-stage stochastic program for multi-shift, multi-analyst, workforce optimization with multiple on-call options," Journal of Scheduling, Springer, vol. 21(5), pages 517-531, October.
    20. Gérard, Matthieu & Clautiaux, François & Sadykov, Ruslan, 2016. "Column generation based approaches for a tour scheduling problem with a multi-skill heterogeneous workforce," European Journal of Operational Research, Elsevier, vol. 252(3), pages 1019-1030.

    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:joheur:v:30:y:2024:i:5:d:10.1007_s10732-024-09527-0. 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.