OASIcs.ATMOS.2021.1.pdf
- Filesize: 1.04 MB
- 15 pages
Document
Efficient Duration-Based Workload Balancing for Interdependent Vehicle Routes
Authors
Carlo S. Sartori 
,
Pieter Smet ,
Greet Vanden Berghe
-
Part of:
Volume:
21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)
Series: Open Access Series in Informatics (OASIcs)
Conference: Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2021-09-27
File
Document Identifiers
Author Details
Acknowledgements
Editorial consultation provided by Luke Connolly (KU Leuven).
Cite AsGet BibTex
Carlo S. Sartori, Pieter Smet, and Greet Vanden Berghe. Efficient Duration-Based Workload Balancing for Interdependent Vehicle Routes. In 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021). Open Access Series in Informatics (OASIcs), Volume 96, pp. 1:1-1:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/OASIcs.ATMOS.2021.1
https://doi.org/10.4230/OASIcs.ATMOS.2021.1
Abstract
Vehicle routing and scheduling problems with interdependent routes arise when some services must be performed by at least two vehicles and temporal synchronization is thus required between the starting times of these services. These problems are often coupled with time window constraints in order to model various real-world applications such as pickup and delivery with transfers, cross-docking and home care scheduling. Interdependent routes in these applications can lead to large idle times for some drivers, unnecessarily lengthening their working hours. To remedy this unfairness, it is necessary to balance the duration of the drivers' routes. However, quickly evaluating duration-based equity functions for interdependent vehicle routes with time windows poses a significant computational challenge, particularly when the departure time of routes is flexible. This paper introduces models and algorithms to compute two well-known equity functions in flexible departure time settings: min-max and range minimization. We explore the challenges and algorithmic complexities of evaluating these functions both from a theoretical and an experimental viewpoint. The results of this paper enable the development of new heuristic methods to balance the workload of interdependent vehicle routes with time windows.
Subject Classification
ACM Subject Classification
- Applied computing → Transportation
- Computing methodologies → Temporal reasoning
- Mathematics of computing → Graph algorithms
Keywords
- Vehicle scheduling
- Workload balancing
- Route duration
- Interdependent routes
- Time windows
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Ousmane Ali, Jean-François Côté, and Leandro C. Coelho. Models and algorithms for the delivery and installation routing problem. European Journal of Operational Research, 291(1):162-177, 2021. URL: https://doi.org/10.1016/j.ejor.2020.09.011.
- Jan Christiaens and Greet Vanden Berghe. Slack induction by string removals for vehicle routing problems. Transportation Science, 54(2):417-433, 2020. URL: https://doi.org/10.1287/trsc.2019.0914.
- Michael B. Cohen, Yin Tat Lee, and Zhao Song. Solving linear programs in the current matrix multiplication time. Journal of the ACM, 68(1):3:1-3:39, 2021. URL: https://doi.org/10.1145/3424305.
-
Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein. Introduction to Algorithms. MIT press, 2009.
- Rina Dechter, Itay Meiri, and Judea Pearl. Temporal constraint networks. Artificial Intelligence, 49(1-3):61-95, 1991. URL: https://doi.org/10.1016/0004-3702(91)90006-6.
- Anders Dohn, Matias Sevel Rasmussen, and Jesper Larsen. The vehicle routing problem with time windows and temporal dependencies. Networks, 58(4):273-289, 2011. URL: https://doi.org/10.1002/net.20472.
-
Michael Drexl. A generic heuristic for vehicle routing problems with multiple synchronization constraints. Gutenberg School of Management and Economics-Discussion Paper Series: Mainz, Germany, 1412:43, 2014.
- Christian Fikar and Patrick Hirsch. Home health care routing and scheduling: A review. Computers & Operations Research, 77:86-95, 2017. URL: https://doi.org/10.1016/j.cor.2016.07.019.
- Hossein Hojabri, Michel Gendreau, Jean-Yves Potvin, and Louis-Martin Rousseau. Large neighborhood search with constraint programming for a vehicle routing problem with synchronization constraints. Computers & Operations Research, 92:87-97, 2018. URL: https://doi.org/10.1016/j.cor.2017.11.011.
- Nicolas Jozefowiez, Frédéric Semet, and El-Ghazali Talbi. Parallel and hybrid models for multi-objective optimization: Application to the vehicle routing problem. In Juan Julián Merelo Guervós, Panagiotis Adamidis, Hans-Georg Beyer, José Luis Fernández-Villacañas Martín, and Hans-Paul Schwefel, editors, Parallel Problem Solving from Nature - PPSN VII, 7th International Conference, Granada, Spain, September 7-11, 2002, Proceedings, volume 2439 of Lecture Notes in Computer Science, pages 271-280. Springer, 2002. URL: https://doi.org/10.1007/3-540-45712-7_26.
- Narendra Karmarkar. A new polynomial-time algorithm for linear programming. Combinatorica, 4(4):373-396, 1984. URL: https://doi.org/10.1007/BF02579150.
-
Lina Khatib, Paul H. Morris, Robert A. Morris, and Francesca Rossi. Temporal constraint reasoning with preferences. In Bernhard Nebel, editor, Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, IJCAI 2001, Seattle, Washington, USA, August 4-10, 2001, pages 322-327. Morgan Kaufmann, 2001.
- Renaud Masson, Fabien Lehuédé, and Olivier Péton. The dial-a-ride problem with transfers. Computers & Operations Research, 41:12-23, 2014. URL: https://doi.org/10.1016/j.cor.2013.07.020.
- Piotr Matl, Richard F. Hartl, and Thibaut Vidal. Workload equity in vehicle routing problems: A survey and analysis. Transportation Science, 52(2):239-260, 2018. URL: https://doi.org/10.1287/trsc.2017.0744.
- Piotr Matl, Richard F. Hartl, and Thibaut Vidal. Workload equity in vehicle routing: The impact of alternative workload resources. Computers & Operations Research, 110:116-129, 2019. URL: https://doi.org/10.1016/j.cor.2019.05.016.
- Belén Melián-Batista, Alondra De Santiago, Francisco Ángel-Bello, and Ada M. Alvarez. A bi-objective vehicle routing problem with time windows: A real case in tenerife. Applied Soft Computing, 17:140-152, 2014. URL: https://doi.org/10.1016/j.asoc.2013.12.012.
-
Snežana Mitrović-Minić and Gilbert Laporte. The pickup and delivery problem with time windows and transshipment. INFOR: Information Systems and Operational Research, 44:217-227, 2006.
- Martin W. P. Savelsbergh. The vehicle routing problem with time windows: Minimizing route duration. INFORMS Journal on Computing, 4(2):146-154, 1992. URL: https://doi.org/10.1287/ijoc.4.2.146.
- Donald K. Wagner. Shortest paths in almost acyclic graphs. Operations Research Letters, 27(4):143-147, 2000. URL: https://doi.org/10.1016/S0167-6377(00)00054-7.