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

References

• Akkerman F, Luy J, van Heeswijk W, Schiffer M (2023) Handling large discrete action spaces via dynamic neighborhood construction. Preprint, submitted May 31, https://arxiv.org/abs/2305.19891v1.Google Scholar
• Alinaghian M, Aghaie M, Sabbagh MS (2019) A mathematical model for location of temporary relief centers and dynamic routing of aerial rescue vehicles. Comput. Indust. Engrg. 131:227–241.Crossref, Google Scholar
• Alonso-Mora J, Wallar A, Rus D (2017) Predictive routing for autonomous mobility-on-demand systems with ride-sharing. 2017 IEEE/RSJ Internat. Conf. Intelligent Robots Systems (IROS) (IEEE, Piscataway, NJ), 3583–3590.Google Scholar
• Basso R, Kulcsár B, Sanchez-Diaz I, Qu X (2022) Dynamic stochastic electric vehicle routing with safe reinforcement learning. Transportation Res. Part E Logist. Transportation Rev. 157:102496.Crossref, Google Scholar
• Bengio Y, Lodi A, Prouvost A (2021) Machine learning for combinatorial optimization: A methodological tour d’horizon. Eur. J. Oper. Res. 290(2):405–421.Crossref, Google Scholar
• Bent RW, Van Hentenryck P (2004) Scenario-based planning for partially dynamic vehicle routing with stochastic customers. Oper. Res. 52(6):977–987.Link, Google Scholar
• Berthet Q, Blondel M, Teboul O, Cuturi M, Vert JP, Bach F (2020) Learning with differentiable perturbed optimizers. Adv. Neural Inform. Processing Systems 33 (Curran Associates, Inc., Red Hook, NY), 9508–9519.Google Scholar
• Blondel M, Martins AF, Niculae V (2020) Learning with Fenchel-Young losses. J. Machine Learn. Res. 21(1):1314–1382.Google Scholar
• Carpentier P, Chancelier JP, Cohen G, De Lara M (2015) Stochastic Multi-stage Optimization, Probability Theory and Stochastic Modeling, vol. 75 (Springer, Cham, Switzerland).Crossref, Google Scholar
• Chu H, Zhang W, Bai P, Chen Y (2023) Data-driven optimization for last-mile delivery. Complex Intelligent Systems 9:2271–2284.Crossref, Google Scholar
• Dalle G, Baty L, Bouvier L, Parmentier A (2022) Learning with combinatorial optimization layers: A probabilistic approach. Preprint, submitted July 27, https://arxiv.org/abs/2207.13513.Google Scholar
• Elmachtoub AN, Grigas P (2022) Smart “predict, then optimize.” Management Sci. 68(1):9–26.Link, Google Scholar
• Elmachtoub AN, Liang JCN, McNellis R (2020) Decision trees for decision-making under the predict-then-optimize framework. Proc. Machine Learn. Res. 119:2858–2867.Google Scholar
• Enders T, Harrison J, Pavone M, Schiffer M (2023) Hybrid multi-agent deep reinforcement learning for autonomous mobility on demand systems. Proc. Machine Learn. Res. 211:1–13.Google Scholar
• Fikar C (2018) A decision support system to investigate food losses in e-grocery deliveries. Comput. Indust. Engrg. 117:282–290.Crossref, Google Scholar
• Flatberg T, Hasle G, Kloster O, Nilssen EJ, Riise A (2007) Dynamic and stochastic vehicle routing in practice. Zeimpekis V, Tarantilis CD, Giaglis GM, Minis I, eds. Dynamic Fleet Management, Operations Research/Computer Science Interfaces Series, vol. 38 (Springer, Boston), 41–63.Crossref, Google Scholar
• Gendreau M, Guertin F, Potvin JY, Taillard E (1999) Parallel tabu search for real-time vehicle routing and dispatching. Transportation Sci. 33(4):381–390.Link, Google Scholar
• Hildebrandt FD, Thomas BW, Ulmer MW (2023) Opportunities for reinforcement learning in stochastic dynamic vehicle routing. Comput. Oper. Res. 150:106071.Crossref, Google Scholar
• Joe W, Lau HC (2020) Deep reinforcement learning approach to solve dynamic vehicle routing problem with stochastic customers. Proc. Internat. Conf. Automated Planning Scheduling (AAAI Press, Palo Alto, CA), 394–402.Google Scholar
• Jungel K, Parmentier A, Schiffer M, Vidal T (2023) Learning-based online optimization for autonomous mobility-on-demand fleet control. Preprint, submitted February 8, https://arxiv.org/abs/2302.03963.Google Scholar
• Kool W, van Hoof H, Welling M (2019) Attention, learn to solve routing problems! Internat. Conf. Learn. Representations (ICLR, Appleton, WI).Google Scholar
• Kool W, Juninck JO, Roos E, Cornelissen K, Agterberg P, van Hoorn J, Visser T (2022a) Hybrid genetic search for the vehicle routing problem with time windows: A high-performance implementation. 12th DIMACS Implementation Challenge Workshop.Google Scholar
• Kool W, Bliek L, Numeroso D, Reijnen R, Afshar RR, Zhang Y, Catshoek T, et al. (2022b) The EURO Meets NeurIPS 2022 Vehicle Routing Competition. https://neurips.cc/virtual/2022/competition/50085.Google Scholar
• Kotary J, Fioretto F, Van Hentenryck P, Wilder B (2021) End-to-end constrained optimization learning: A survey. Preprint, submitted March 30, https://arxiv.org/abs/2103.16378.Google Scholar
• Liang E, Wen K, Lam WHK, Sumalee A, Zhong R (2022) An integrated reinforcement learning and centralized programming approach for online taxi dispatching. IEEE Trans. Neural Networks Learn. Systems 33(9):4742–4756.Crossref, Google Scholar
• Liu S, He L, Shen ZJM (2021) On-time last-mile delivery: Order assignment with travel-time predictors. Management Sci. 67(7):4095–4119.Link, Google Scholar
• Nagata Y, Kobayashi S (2010) A memetic algorithm for the pickup and delivery problem with time windows using selective route exchange crossover. Schaefer R, Cotta C, Kołodziej J, Rudolph G, eds. Parallel Problem Solving from Nature, PPSN XI. PPSN 2010, Lecture Notes in Computer Science, vol. 6238 (Springer, Berlin), 536–545.Crossref, Google Scholar
• Nazari M, Oroojlooy A, Snyder L, Takac M (2018) Reinforcement learning for solving the vehicle routing problem. Bengio S, Wallach H, Larochelle H, Grauman K, Cesa-Bianchi N, Garnett R, eds. Adv. Neural Inform. Processing Systems 31 (Curran Associates, Inc., Red Hook, NY).Google Scholar
• Nicolai B (2016) Amazon liefert pakete innerhalb von zwei stunden. Welt (March 2016), https://www.welt.de/wirtschaft/article153690106/Amazon-liefert-Pakete-innerhalb-von-zwei-Stunden.html.Google Scholar
• Ojeda Rios BH, Xavier EC, Miyazawa FK, Amorim P, Curcio E, Santos MJ (2021) Recent dynamic vehicle routing problems: A survey. Comput. Indust. Engrg. 160:107604.Crossref, Google Scholar
• Oliver I, Smith D, Holland JR (1987) A study of permutation crossover operators on the traveling salesman problem. Grefenstette JJ, ed. Genetic Algorithms and Their Applications (Psychology Press, New York), 224–230.Google Scholar
• Parmentier A (2021) Learning structured approximations of operations research problems. Preprint, submitted July 9, https://arxiv.org/abs/2107.04323.Google Scholar
• Parmentier A (2022) Learning to approximate industrial problems by operations research classic problems. Oper. Res. 70(1):606–623.Link, Google Scholar
• Parmentier A, T’Kindt V (2021) Learning to solve the single machine scheduling problem with release times and sum of completion times. Preprint, submitted January 4, https://arxiv.org/abs/2101.01082.Google Scholar
• Pflug GC, Pichler A (2014) Multistage Stochastic Optimization, Springer Series in Operations Research and Financial Engineering (Springer, Cham, Switzerland).Crossref, Google Scholar
• Pillac V, Gendreau M, Guéret C, Medaglia AL (2013) A review of dynamic vehicle routing problems. Eur. J. Oper. Res. 225(1):1–11.Crossref, Google Scholar
• Placek M (2022) Same-day delivery market size in U.S. 2019–2024. https://www.statista.com/statistics/1068886/us-same-day-delivery-market-size/.Google Scholar
• Raza SM, Sajid M, Singh J (2022) Vehicle routing problem using reinforcement learning: Recent advancements. Gupta D, Sambyo K, Prasad M, Agarwal S, eds. Advanced Machine Intelligence and Signal Processing (Springer Nature Singapore, Singapore), 269–280.Crossref, Google Scholar
• Ritzinger U, Puchinger J, Hartl RF (2016) A survey on dynamic and stochastic vehicle routing problems. Internat. J. Production Res. 54(1):215–231.Crossref, Google Scholar
• Soeffker N, Ulmer MW, Mattfeld DC (2022) Stochastic dynamic vehicle routing in the light of prescriptive analytics: A review. Eur. J. Oper. Res. 298(3):801–820.Crossref, Google Scholar
• Steever Z, Karwan M, Murray C (2019) Dynamic courier routing for a food delivery service. Comput. Oper. Res. 107:173–188.Crossref, Google Scholar
• Tang X, Qin Z, Zhang F, Wang Z, Xu Z, Ma Y, Zhu H, Ye J (2019) A deep value-network based approach for multi-driver order dispatching. Proc. 25th ACM SIGKDD Internat. Conf. Knowledge Discovery Data Mining (ACM, New York), 1780–1790.Google Scholar
• Ulmer MW, Soeffker N, Mattfeld DC (2018) Value function approximation for dynamic multi-period vehicle routing. Eur. J. Oper. Res. 269(3):883–899.Crossref, Google Scholar
• van Doorn J, Lan L, Pentinga L, Wouda N (2022) Solving a static and dynamic VRP with time windows using hybrid genetic search and simulation. EURO Meets NeurIPS Vehicle Routing Competition, https://github.com/ortec/euro-neurips-vrp-2022-quickstart/blob/main/papers/OptiML.pdf.Google Scholar
• Vidal T (2022) Hybrid genetic search for the CVRP: Open-source implementation and swap* neighborhood. Comput. Oper. Res. 140:105643.Crossref, Google Scholar
• Vidal T, Laporte G, Matl P (2020) A concise guide to existing and emerging vehicle routing problem variants. Eur. J. Oper. Res. 286(2):401–416.Crossref, Google Scholar
• Vidal T, Maculan N, Ochi LS, Vaz Penna PH (2016) Large neighborhoods with implicit customer selection for vehicle routing problems with profits. Transportation Sci. 50(2):720–734.Link, Google Scholar
• Wallar A, Van Der Zee M, Alonso-Mora J, Rus D (2018) Vehicle rebalancing for mobility-on-demand systems with ride-sharing. 2018 IEEE/RSJ Internat. Conf. Intelligent Robots Systems (IROS) (IEEE, Piscataway, NJ), 4539–4546.Google Scholar
• Zhou M, Jin J, Zhang W, Qin Z, Jiao Y, Wang C, Wu G, Yu Y, Ye J (2019) Multi-agent reinforcement learning for order-dispatching via order-vehicle distribution matching. Proc. 28th ACM Internat. Conf. Inform. Knowledge Management (Association for Computing Machinery, New York), 2645–2653.Google Scholar