IDEAS home Printed from https://ideas.repec.org/a/eee/transe/v177y2023ics1366554523002132.html
   My bibliography  Save this article

Tactical planning for dynamic technician routing and scheduling problems

Author

Listed:
  • Nielsen, Clara Chini
  • Pisinger, David

Abstract

We consider the tactical planning aspect of a dynamic technician routing and scheduling problem with a time horizon of several days. In this problem study, some tasks are known beforehand, while others arrive dynamically. The tactical planning is to schedule the known tasks, such that we minimize the overall driving distance while ensuring short service times for the dynamic tasks. Without tactical planning, the known tasks would be spread throughout the whole area as they are scheduled based on a first-come-first-serve principle. In this study, we partition the area into disjoint slices covering the full plane and then assign the slices to individual work days. The partitioning of the area will be constructed with a balanced sweep algorithm using two approaches: The first is based on a parallel sweep-line following a given angle, while the second is based on a rotating sweep-line around a given origin. To guide the partitioning, we aim to minimize the degree of dynamism, which in our case is defined by the number of dynamic tasks, the distance from known tasks to dynamic tasks, and the tightness of the time windows. The tactical planning is evaluated using real-life and synthetic clustered data, where some of the tasks are known beforehand, and some are dynamic. We benchmark the various partitioning approaches against the default strategy of serving all known tasks on a first-come-first-serve basis. Computational results are reported showing around a 10% reduction in driving distance when using tactical planning. Furthermore, we show that up to 70% of the technicians can have a non-dynamic work day, without a significant increase in driving distance.

Suggested Citation

  • Nielsen, Clara Chini & Pisinger, David, 2023. "Tactical planning for dynamic technician routing and scheduling problems," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 177(C).
  • Handle: RePEc:eee:transe:v:177:y:2023:i:c:s1366554523002132
    DOI: 10.1016/j.tre.2023.103225
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S1366554523002132
    Download Restriction: Full text for ScienceDirect subscribers only

    File URL: https://libkey.io/10.1016/j.tre.2023.103225?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. 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.
    2. Ulrike Ritzinger & Jakob Puchinger & Richard F. Hartl, 2016. "A survey on dynamic and stochastic vehicle routing problems," International Journal of Production Research, Taylor & Francis Journals, vol. 54(1), pages 215-231, January.
    3. Catherine Cleophas & Jan Ehmke, 2014. "When Are Deliveries Profitable?," Business & Information Systems Engineering: The International Journal of WIRTSCHAFTSINFORMATIK, Springer;Gesellschaft für Informatik e.V. (GI), vol. 6(3), pages 153-163, June.
    4. Ehsan Pourjavad & Eman Almehdawe, 2022. "Optimization of the technician routing and scheduling problem for a telecommunication industry," Annals of Operations Research, Springer, vol. 315(1), pages 371-395, August.
    5. David Pisinger & Stefan Ropke, 2019. "Large Neighborhood Search," International Series in Operations Research & Management Science, in: Michel Gendreau & Jean-Yves Potvin (ed.), Handbook of Metaheuristics, edition 3, chapter 0, pages 99-127, Springer.
    6. Ji, Chenlu & Mandania, Rupal & Liu, Jiyin & Liret, Anne, 2022. "Scheduling on-site service deliveries to minimise the risk of missing appointment times," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 158(C).
    7. C E Cortés & M Gendreau & D Leng & A Weintraub, 2011. "A simulation-based approach for fleet design in a technician dispatch problem with stochastic demand," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(8), pages 1510-1523, August.
    8. Alberto Santini & Stefan Ropke & Lars Magnus Hvattum, 2018. "A comparison of acceptance criteria for the adaptive large neighbourhood search metaheuristic," Journal of Heuristics, Springer, vol. 24(5), pages 783-815, October.
    9. van Lon, Rinde R.S. & Ferrante, Eliseo & Turgut, Ali E. & Wenseleers, Tom & Vanden Berghe, Greet & Holvoet, Tom, 2016. "Measures of dynamism and urgency in logistics," European Journal of Operational Research, Elsevier, vol. 253(3), pages 614-624.
    10. A Larsen & O Madsen & M Solomon, 2002. "Partially dynamic vehicle routing—models and algorithms," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 53(6), pages 637-646, June.
    11. Niels Agatz & Ann Campbell & Moritz Fleischmann & Martin Savelsbergh, 2011. "Time Slot Management in Attended Home Delivery," Transportation Science, INFORMS, vol. 45(3), pages 435-449, August.
    12. Russell W. Bent & Pascal Van Hentenryck, 2004. "Scenario-Based Planning for Partially Dynamic Vehicle Routing with Stochastic Customers," Operations Research, INFORMS, vol. 52(6), pages 977-987, December.
    13. Chen, Xi & Thomas, Barrett W. & Hewitt, Mike, 2016. "The technician routing problem with experience-based service times," Omega, Elsevier, vol. 61(C), pages 49-61.
    14. Marlin W. Ulmer & Justin C. Goodson & Dirk C. Mattfeld & Marco Hennig, 2019. "Offline–Online Approximate Dynamic Programming for Dynamic Vehicle Routing with Stochastic Requests," Service Science, INFORMS, vol. 53(1), pages 185-202, February.
    15. Pahlevani, Delaram & Abbasi, Babak & Hearne, John W. & Eberhard, Andrew, 2022. "A cluster-based algorithm for home health care planning: A case study in Australia," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 166(C).
    16. Ines Mathlouthi & Michel Gendreau & Jean-Yves Potvin, 2021. "Branch-and-Price for a Multi-attribute Technician Routing and Scheduling Problem," SN Operations Research Forum, Springer, vol. 2(1), pages 1-35, March.
    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. Wang, Jianxin & Lim, Ming K. & Liu, Weihua, 2024. "Promoting intelligent IoT-driven logistics through integrating dynamic demand and sustainable logistics operations," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 185(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. Zhang, Jian & Woensel, Tom Van, 2023. "Dynamic vehicle routing with random requests: A literature review," International Journal of Production Economics, Elsevier, vol. 256(C).
    2. Dumez, Dorian & Lehuédé, Fabien & Péton, Olivier, 2021. "A large neighborhood search approach to the vehicle routing problem with delivery options," Transportation Research Part B: Methodological, Elsevier, vol. 144(C), pages 103-132.
    3. Fleckenstein, David & Klein, Robert & Steinhardt, Claudius, 2023. "Recent advances in integrating demand management and vehicle routing: A methodological review," European Journal of Operational Research, Elsevier, vol. 306(2), pages 499-518.
    4. María I. Restrepo & Frédéric Semet & Thomas Pocreau, 2019. "Integrated Shift Scheduling and Load Assignment Optimization for Attended Home Delivery," Transportation Science, INFORMS, vol. 53(4), pages 1150-1174, July.
    5. Zhang, Jian & Luo, Kelin & Florio, Alexandre M. & Van Woensel, Tom, 2023. "Solving large-scale dynamic vehicle routing problems with stochastic requests," European Journal of Operational Research, Elsevier, vol. 306(2), pages 596-614.
    6. Koch, Sebastian & Klein, Robert, 2020. "Route-based approximate dynamic programming for dynamic pricing in attended home delivery," European Journal of Operational Research, Elsevier, vol. 287(2), pages 633-652.
    7. Marlin W. Ulmer & Leonard Heilig & Stefan Voß, 2017. "On the Value and Challenge of Real-Time Information in Dynamic Dispatching of Service Vehicles," Business & Information Systems Engineering: The International Journal of WIRTSCHAFTSINFORMATIK, Springer;Gesellschaft für Informatik e.V. (GI), vol. 59(3), pages 161-171, June.
    8. Liu, Zeyu & Li, Xueping & Khojandi, Anahita, 2022. "The flying sidekick traveling salesman problem with stochastic travel time: A reinforcement learning approach," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 164(C).
    9. Singh, Nitish & Dang, Quang-Vinh & Akcay, Alp & Adan, Ivo & Martagan, Tugce, 2022. "A matheuristic for AGV scheduling with battery constraints," European Journal of Operational Research, Elsevier, vol. 298(3), pages 855-873.
    10. Vincent F. Yu & Yueh-Sheng Lin & Panca Jodiawan & Shih-Wei Lin & Yu-Chi Lai, 2023. "The Field Technician Scheduling Problem with Experience-Dependent Service Times," Mathematics, MDPI, vol. 11(21), pages 1-17, November.
    11. Côté, Jean-François & Alves de Queiroz, Thiago & Gallesi, Francesco & Iori, Manuel, 2023. "A branch-and-regret algorithm for the same-day delivery problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 177(C).
    12. Bruck, Bruno P. & Cordeau, Jean-François & Iori, Manuel, 2018. "A practical time slot management and routing problem for attended home services," Omega, Elsevier, vol. 81(C), pages 208-219.
    13. Ritzinger, Ulrike & Puchinger, Jakob & Rudloff, Christian & Hartl, Richard F., 2022. "Comparison of anticipatory algorithms for a dial-a-ride problem," European Journal of Operational Research, Elsevier, vol. 301(2), pages 591-608.
    14. Keskin, Merve & Branke, Juergen & Deineko, Vladimir & Strauss, Arne K., 2023. "Dynamic multi-period vehicle routing with touting," European Journal of Operational Research, Elsevier, vol. 310(1), pages 168-184.
    15. Avraham, Edison & Raviv, Tal, 2021. "The steady-state mobile personnel booking problem," Transportation Research Part B: Methodological, Elsevier, vol. 154(C), pages 266-288.
    16. Soeffker, Ninja & Ulmer, Marlin W. & Mattfeld, Dirk C., 2022. "Stochastic dynamic vehicle routing in the light of prescriptive analytics: A review," European Journal of Operational Research, Elsevier, vol. 298(3), pages 801-820.
    17. Marlin W. Ulmer & Alan Erera & Martin Savelsbergh, 2022. "Dynamic service area sizing in urban delivery," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 44(3), pages 763-793, September.
    18. Baals, Julian & Emde, Simon & Turkensteen, Marcel, 2023. "Minimizing earliness-tardiness costs in supplier networks—A just-in-time truck routing problem," European Journal of Operational Research, Elsevier, vol. 306(2), pages 707-741.
    19. Marlin W. Ulmer & Barrett W. Thomas & Dirk C. Mattfeld, 2019. "Preemptive depot returns for dynamic same-day delivery," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 8(4), pages 327-361, December.
    20. Frey, Christian M.M. & Jungwirth, Alexander & Frey, Markus & Kolisch, Rainer, 2023. "The vehicle routing problem with time windows and flexible delivery locations," European Journal of Operational Research, Elsevier, vol. 308(3), pages 1142-1159.

    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:transe:v:177:y:2023:i:c:s1366554523002132. 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/600244/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.