Abstract
We consider a novel variant of the heterogeneous vehicle routing problem (VRP) in which each customer has different availability time windows for every vehicle. In particular, this covers our motivating application of planning daily delivery tours for a single vehicle, where customers can be available at different times each day. The existing literature on heterogeneous VRPs typically distinguishes properties of the vehicle fleet such as costs or capacities, but apparently, windows of customers have only been regarded in a homogeneous fashion thus far. To solve the problem, we employ a branch-and-price framework based on a set partitioning formulation together with a parallelizable labeling algorithm. The heterogeneous time window structure yields notable computational gains by allowing to decompose the pricing problem as well as to utilize a customer-vehicle assignment branching rule. We show that this branching rule leads to more balanced search trees than the usual arc flow branching, and demonstrate its efficiency in numerical experiments.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Bestuzheva, K., Besançon, M., Chen, W.-K., Chmiela, A., Donkiewicz, T., van Doornmalen, J., Eifler, L., Gaul, O., Gamrath, G., Gleixner, A., Gottwald, L., Graczyk, C., Halbig, K., Hoen, A., Hojny, C., van der Hulst, R., Koch, T., Lübbecke, M., Maher, S. J., \(\ldots \), Witzig, J. (2021). The SCIP optimization suite 8.0. ZIB-report 21-41, Zuse Institute Berlin. http://nbn-resolving.de/urn:nbn:de:0297-zib-85309
Costa, L., Contardo, C., & Desaulniers, G. (2019). Exact branch-price-and-cut algorithms for vehicle routing. Transportation Science, 53(4), 946–985. https://doi.org/10.1287/trsc.2018.0878
Koç, Ç., Bektaş, T., Jabali, O., & Laporte, G. (2016). Thirty years of heterogeneous vehicle routing. European Journal of Operational Research, 249(1), 1–21. https://doi.org/10.1016/j.ejor.2015.07.020
Ryan, D. M., & Foster, B. A. (1981). An integer programming approach to scheduling. In A. Wren (Ed.), Computer scheduling of public transport (pp. 269–280).
Sol, M. (1994). Column generation techniques for pickup and delivery problems. Ph.D. thesis, Technische Universiteit Eindhoven, The Netherlands.
Solomon, M. M. (1984). Vehicle routing and scheduling with time window constraints: Models and algorithms (Heuristics). Ph.D. thesis, University of Pennsylvania, PA, USA.
Vidal, T., Laporte, G., & Matl, P. (2020). A concise guide to existing and emerging vehicle routing problem variants. European Journal of Operational Research, 286(2), 401–416. https://doi.org/10.1016/j.ejor.2019.10.010
Acknowledgements
The authors gratefully acknowledge funding by the German Federal Ministry for Education and Research, grant nos. 05M20MBA-LeoPlan and 05M20PDA-LeoPlan.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Mutzel, P., Niemann, T., Schürmann, L., Stiller, S., Tillmann, A.M. (2023). Vehicle Routing with Heterogeneous Time Windows. In: Grothe, O., Nickel, S., Rebennack, S., Stein, O. (eds) Operations Research Proceedings 2022. OR 2022. Lecture Notes in Operations Research. Springer, Cham. https://doi.org/10.1007/978-3-031-24907-5_21
Download citation
DOI: https://doi.org/10.1007/978-3-031-24907-5_21
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-24906-8
Online ISBN: 978-3-031-24907-5
eBook Packages: Business and ManagementBusiness and Management (R0)