# Combinatorial Optimization enriched Machine Learning to solve the Dynamic Vehicle Routing Problem with Time Windows

arXiv: https://arxiv.org/abs/2304.00789 · HTML: https://mlsanity.com/paper/2304.00789/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 43 references that are in the map.
- First posted on arXiv 3 Apr 2023.

## Builds on (most cited first, 12 of 12)

- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Smart "Predict, then Optimize"](https://mlsanity.com/paper/1710.08005/) (2017)
- [Reinforcement Learning for Solving the Vehicle Routing Problem](https://mlsanity.com/paper/1802.04240/) (2018)
- [End-to-End Constrained Optimization Learning: A Survey](https://mlsanity.com/paper/2103.16378/) (2021)
- [Hybrid Genetic Search for the CVRP: Open-Source Implementation and SWAP* Neighborhood](https://mlsanity.com/paper/2012.10384/) (2020)
- [Learning with Fenchel-Young Losses](https://mlsanity.com/paper/1901.02324/) (2019)
- [Learning with Combinatorial Optimization Layers: a Probabilistic Approach](https://mlsanity.com/paper/2207.13513/) (2022)
- [A concise guide to existing and emerging vehicle routing problem variants](https://mlsanity.com/paper/1906.06750/) (2019)
- [Learning-based Online Optimization for Autonomous Mobility-on-Demand Fleet Control](https://mlsanity.com/paper/2302.03963/) (2023)
- [Learning to solve the single machine scheduling problem with release times and sum of completion times](https://mlsanity.com/paper/2101.01082/) (2021)
- [Large neighborhoods with implicit customer selection for vehicle routing problems with profits](https://mlsanity.com/paper/1401.3794/) (2014)

## Built on by (most cited first, 10 of 10)

- [Structured Reinforcement Learning for Combinatorial Decision-Making](https://mlsanity.com/paper/2505.19053/) (2025)
- [Learning for routing: A guided review of recent developments and future directions](https://mlsanity.com/paper/2507.00218/) (2025)
- [Primal-dual algorithm for contextual stochastic combinatorial optimization](https://mlsanity.com/paper/2505.04757/) (2025)
- [Generalization Bounds of Surrogate Policies for Combinatorial Optimization Problems](https://mlsanity.com/paper/2407.17200/) (2024)
- [WardropNet: Traffic Flow Predictions via Equilibrium-Augmented Learning](https://mlsanity.com/paper/2410.06656/) (2024)
- [Combinatorial Optimization Augmented Machine Learning](https://mlsanity.com/paper/2601.10583/) (2026)
- [Learning with Local Search MCMC Layers](https://mlsanity.com/paper/2505.14240/) (2025)
- [Optimization-Augmented Machine Learning for Vehicle Operations in Emergency Medical Services](https://mlsanity.com/paper/2503.11848/) (2025)
- [Learning to Solve Orienteering Problem with Time Windows and Variable Profits](https://mlsanity.com/paper/2603.06260/) (2026)
- [Dynamic Vehicle Routing Problem with Prompt Confirmation of Advance Requests](https://mlsanity.com/paper/2603.07422/) (2026)

## Abstract (arXiv)

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 multi-stage stochastic optimization approaches that allow to solve the underlying dynamic vehicle routing problem are either 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, e.g., by showcasing the robustness of the encoded policy against unseen instances and scenarios.