Genetic Algorithms with Neural Cost Predictor for Solving Hierarchical Vehicle Routing Problems

References

• Akkerman F, Mes M (2022) Distance approximation to support customer selection in vehicle routing problems. Ann. Oper. Res., ePub ahead of print April 7, https://doi.org/10.1007/s10479-022-04674-8.Crossref, Google Scholar
• Akpunar ÖŞ, Akpinar Ş (2021) A hybrid adaptive large neighbourhood search algorithm for the capacitated location routing problem. Expert Systems Appl. 168:114304.Crossref, Google Scholar
• Arnold F, Gendreau M, Sörensen K (2019) Efficiently solving very large-scale routing problems. Comput. Oper. Res. 107:32–42.Crossref, Google Scholar
• Ba JL, Kiros JR, Hinton GE (2016) Layer normalization. Preprint, submitted July 21, https://arxiv.org/abs/1607.06450.Google Scholar
• Baldacci R, Mingozzi A (2009) A unified exact method for solving different classes of vehicle routing problems. Math. Programming 120:347–380.Crossref, Google Scholar
• Baldacci R, Mingozzi A, Wolfler Calvo R (2011) An exact method for the capacitated location-routing problem. Oper. Res. 59(5):1284–1296.Link, Google Scholar
• Banerjee D, Erera AL, Toriello A (2022) Fleet sizing and service region partitioning for same-day delivery systems. Transportation Sci. 56(5):1327–1347.Link, Google Scholar
• Belenguer JM, Benavent E, Prins C, Prodhon C, Calvo RW (2011) A branch-and-cut method for the capacitated location-routing problem. Comput. Oper. Res. 38(6):931–941.Crossref, Google Scholar
• Bello I, Pham H, Le QV, Norouzi M, Bengio S (2017) Neural combinatorial optimization with reinforcement learning. 5th Internat. Conf. Learn. Representations ICLR 2017 (ICLR, Appleton, WI).Google Scholar
• Bogyrbayeva A, Yoon T, Ko H, Lim S, Yun H, Kwon C (2023) A deep reinforcement learning approach for solving the traveling salesman problem with drone. Transportation Res. Part C Emerging Tech. 148:103981.Crossref, Google Scholar
• CapGemini Research Institute (2019) The last-mile delivery challenge. Technical report, CapGemini Research Institute, Paris, France.Google Scholar
• Capital One Shopping Research (2019) Amazon logistics statistics. Technical report, Capital One Shopping Research, McLean, VI.Google Scholar
• Cappart Q, Chételat D, Khalil EB, Lodi A, Morris C, Veličković P (2023) Combinatorial optimization and reasoning with graph neural networks. J. Machine Learn. Res. 24(130):1–61.Google Scholar
• Contardo C, Martinelli R (2014) A new exact algorithm for the multi-depot vehicle routing problem under capacity and route length constraints. Discrete Optim. 12:129–146.Crossref, Google Scholar
• Contardo C, Cordeau JF, Gendron B (2014) An exact algorithm based on cut-and-column generation for the capacitated location-routing problem. INFORMS J. Comput. 26(1):88–102.Link, Google Scholar
• Cordeau JF, Gendreau M, Laporte G (1997) A tabu search heuristic for periodic and multi-depot vehicle routing problems. Networks 30(2):105–119.Crossref, Google Scholar
• Coupey J, Nicod JM, Varnier C (2023) VROOM v1.13, vehicle routing open-source optimization machine. Accessed October 1, http://vroom-project.org/.Google Scholar
• de Oliveira FB, Enayatifar R, Sadaei HJ, Guimarães FG, Potvin JY (2016) A cooperative coevolutionary algorithm for the multi-depot vehicle routing problem. Expert Systems Appl. 43:117–130.Crossref, Google Scholar
• Ellegood WA, Campbell JF, North J (2015) Continuous approximation models for mixed load school bus routing. Transportation Res. Part B Methodological 77:182–198.Crossref, Google Scholar
• Figliozzi MA (2008) Planning approximations to the average length of vehicle routing problems with varying customer demands and routing constraints. Transportation Res. Rec. 2089(1):1–8.Crossref, Google Scholar
• Franceschetti A, Jabali O, Laporte G (2017) Continuous approximation models in freight distribution management. TOP 25:413–433.Crossref, Google Scholar
• Furian N, O’Sullivan M, Walker C, Çela E (2021) A machine learning-based branch and price algorithm for a sampled vehicle routing problem. OR Spectrum 43:693–732.Crossref, Google Scholar
• Garn W (2021) Balanced dynamic multiple travelling salesmen: Algorithms and continuous approximations. Comput. Oper. Res. 136:105509.Crossref, Google Scholar
• Ghaffarinasab N, Van Woensel T, Minner S (2018) A continuous approximation approach to the planar hub location-routing problem: Modeling and solution algorithms. Comput. Oper. Res. 100:140–154.Crossref, Google Scholar
• Golden BL, Magnanti TL, Nguyen HQ (1977) Implementing vehicle routing algorithms. Networks 7(2):113–148.Crossref, Google Scholar
• He K, Zhang X, Ren S, Sun J (2016) Deep residual learning for image recognition. Proc. IEEE Conf. Comput. Vision Pattern Recognition (Las Vegas, NV), 770–778.Google Scholar
• Kim H, Park J, Kwon C (2024) A neural separation algorithm for the rounded capacity inequalities. INFORMS J. Comput., ePub ahead of print January 23, https://doi.org/10.1287/ijoc.2022.0310.Link, Google Scholar
• Kim M, Park J, Park J (2023) Learning to CROSS exchange to solve min-max vehicle routing problems. Eleventh Internat. Conf. Learn. Representations (OpenReview.net).Google Scholar
• Kool W, van Hoof H, Welling M (2019) Attention, learn to solve routing problems! 7th Internat. Conf. Learn. Representations (OpenReview.net).Google Scholar
• Kou S, Golden B, Bertazzi L (2024) An improved model for estimating optimal VRP solution values. Optim. Lett. 18:697–703.Crossref, Google Scholar
• Kwon YD, Choo J, Kim B, Yoon I, Gwon Y, Min S (2020) POMO: Policy optimization with multiple optima for reinforcement learning. Adv. Neural Inform. Processing Systems 33:21188–21198.Google Scholar
• Laporte G, Nobert Y, Taillefer S (1988) Solving a family of multi-depot vehicle routing and location-routing problems. Transportation Sci. 22(3):161–172.Link, Google Scholar
• Li S, Yan Z, Wu C (2021) Learning to delegate for large-scale vehicle routing. Adv. Neural Inform. Processing Systems 34:26198–26211.Google Scholar
• Lu H, Zhang X, Yang S (2020) A learning-based iterative method for solving vehicle routing problems. 8th Internat. Conf. Learn. Representations (OpenReview.net).Google Scholar
• Morabit M, Desaulniers G, Lodi A (2021) Machine-learning–based column selection for column generation. Transportation Sci. 55(4):815–831.Link, Google Scholar
• Nazari M, Oroojlooy A, Snyder L, Takác 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, vol. 31 (Curran Associates, Inc., Red Hook, NY), 9861–9871.Google Scholar
• Nicola D, Vetschera R, Dragomir A (2019) Total distance approximations for routing solutions. Comput. Oper. Res. 102:67–74.Crossref, Google Scholar
• Park J, Kwon C, Park J (2023) Learn to solve the min-max multiple traveling salesmen problem with reinforcement learning. Proc. 2023 Internat. Conf. Autonomous Agents Multiagent Systems (AAMAS ‘23) (International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC), 878–886.Google Scholar
• Qi M, Lin WH, Li N, Miao L (2012) A spatiotemporal partitioning approach for large-scale vehicle routing problems with time windows. Transportation Res. Part E Logist. Transportation Rev. 48(1):248–257.Crossref, Google Scholar
• Ramos TRP, Gomes MI, Póvoa APB (2020) Multi-depot vehicle routing problem: A comparative study of alternative formulations. Internat. J. Logist. Res. Appl. 23(2):103–120.Crossref, Google Scholar
• Robust F, Daganzo CF, Souleyrette RR II (1990) Implementing vehicle routing models. Transportation Res. Part B Methodological 24(4):263–286.Crossref, Google Scholar
• Saberi M, Verbas İÖ (2012) Continuous approximation model for the vehicle routing problem for emissions minimization at the strategic level. J. Transportation Engrg. 138(11):1368–1376.Crossref, Google Scholar
• Sadati MEH, Çatay B, Aksen D (2021) An efficient variable neighborhood search with tabu shaking for a class of multi-depot vehicle routing problems. Comput. Oper. Res. 133:105269.Crossref, Google Scholar
• Schneider M, Löffler M (2019) Large composite neighborhoods for the capacitated location-routing problem. Transportation Sci. 53(1):301–318.Link, Google Scholar
• Solomon MM (1987) Algorithms for the vehicle routing and scheduling problems with time window constraints. Oper. Res. 35(2):254–265.Link, Google Scholar
• Stroh AM, Erera AL, Toriello A (2022) Tactical design of same-day delivery systems. Management Sci. 68(5):3444–3463.Link, Google Scholar
• Uchoa E, Pecin D, Pessoa A, Poggi M, Vidal T, Subramanian A (2017) New benchmark instances for the capacitated vehicle routing problem. Eur. J. Oper. Res. 257(3):845–858.Crossref, Google Scholar
• Varol T, Özener OÖ, Albey E (2024) Neural network estimators for optimal tour lengths of traveling salesperson problem instances with arbitrary node distributions. Transportation Sci. 58(1):45–66.Link, Google Scholar
• Vaswani A, Shazeer N, Parmar N, Uszkoreit J, Jones L, Gomez AN, Kaiser Ł, Polosukhin I (2017) Attention is all you need. Guyon I, Von Luxburg U, Bengio S, Wallach H, Fergus R, Vishwanathan S, Garnett R, eds. Adv. Neural Inform. Processing Systems, vol. 30 (Curran Associates, Inc., Red Hook, NY), 6000–6010.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, Crainic TG, Gendreau M, Prins C (2014) Implicit depot assignments and rotations in vehicle routing heuristics. Eur. J. Oper. Res. 237(1):15–28.Crossref, Google Scholar
• Vidal T, Crainic TG, Gendreau M, Lahrichi N, Rei W (2012) A hybrid genetic algorithm for multi-depot and periodic vehicle routing problems. Oper. Res. 60(3):611–624.Link, Google Scholar
• Vinyals O, Fortunato M, Jaitly N (2015) Pointer networks. Proc. 28th Internat. Conf. Neural Inform. Processing Systems, vol. 2 (MIT Press, Cambridge, MA), 2692–2700.Google Scholar
• Wu Y, Song W, Cao Z, Zhang J, Lim A (2021) Learning improvement heuristics for solving routing problems. IEEE Trans. Neural Networks Learn. Systems 33(9):5057–5069.Crossref, Google Scholar
• Xu K, Zhang M, Li J, Du SS, Kawarabayashi K-i, Jegelka S (2021) How neural networks extrapolate: From feedforward to graph neural networks. Internat. Conf. Learn. Representations (openreview.net).Google Scholar
• Zhang K, Lin X, Li M (2023) Graph attention reinforcement learning with flexible matching policies for multi-depot vehicle routing problems. Physica A Statist. Mech. Its Appl. 611:128451.Crossref, Google Scholar
• Zong Z, Wang H, Wang J, Zheng M, Li Y (2022) RBG: Hierarchically solving large-scale routing problems in logistic systems via reinforcement learning. Proc. 28th ACM SIGKDD Conf. Knowledge Discovery Data Mining (ACM, New York), 4648–4658.Google Scholar
• Zou Y, Wu H, Yin Y, Dhamotharan L, Chen D, Tiwari AK (2022) An improved transformer model with multi-head attention and attention to attention for low-carbon multi-depot vehicle routing problem. Ann. Oper. Res. 339:517–536.Crossref, Google Scholar