Combinatorial Optimization-Enriched Machine Learning to Solve the Dynamic Vehicle Routing Problem with Time Windows

Léo Baty (), Kai Jungel (), Patrick S. Klein (), Axel Parmentier () and Maximilian Schiffer ()
Additional contact information
Léo Baty: CERMICS, École des Ponts, Champs sur Marne, 77455 Marne la Vallée Cedex 2, France
Kai Jungel: School of Management, Technical University of Munich, 80333 Munich, Germany
Patrick S. Klein: School of Management, Technical University of Munich, 80333 Munich, Germany
Axel Parmentier: CERMICS, École des Ponts, Champs sur Marne, 77455 Marne la Vallée Cedex 2, France
Maximilian Schiffer: School of Management, Technical University of Munich, 80333 Munich, Germany; Munich Data Science Institute, Technical University of Munich, 80333 Munich, Germany

Transportation Science, 2024, vol. 58, issue 4, 708-725

Abstract: With the rise of e-commerce and increasing customer requirements, logistics service providers face a new complexity in their daily planning, mainly due to efficiently handling same-day deliveries. Existing multistage stochastic optimization approaches that allow solving the underlying dynamic vehicle routing problem either are computationally too expensive for an application in online settings or—in the case of reinforcement learning—struggle to perform well on high-dimensional combinatorial problems. To mitigate these drawbacks, we propose a novel machine learning pipeline that incorporates a combinatorial optimization layer. We apply this general pipeline to a dynamic vehicle routing problem with dispatching waves, which was recently promoted in the EURO Meets NeurIPS Vehicle Routing Competition at NeurIPS 2022. Our methodology ranked first in this competition, outperforming all other approaches in solving the proposed dynamic vehicle routing problem. With this work, we provide a comprehensive numerical study that further highlights the efficacy and benefits of the proposed pipeline beyond the results achieved in the competition, for example, by showcasing the robustness of the encoded policy against unseen instances and scenarios.

Keywords: vehicle routing; structured learning; multistage stochastic optimization; combinatorial optimization; machine learning (search for similar items in EconPapers)
Date: 2024
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2023.0107 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:58:y:2024:i:4:p:708-725

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().