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

Abhay Sobhanan (), Junyoung Park (), Jinkyoo Park () and Changhyun Kwon ()
Additional contact information
Abhay Sobhanan: Department of Industrial and Management Systems Engineering, University of South Florida, Tampa, Florida 33620
Junyoung Park: Industrial and Systems Engineering, KAIST, Daejeon 34141, Republic of Korea; and OMELET, Daejeon 34141, Republic of Korea
Jinkyoo Park: Industrial and Systems Engineering, KAIST, Daejeon 34141, Republic of Korea; and OMELET, Daejeon 34141, Republic of Korea
Changhyun Kwon: Industrial and Systems Engineering, KAIST, Daejeon 34141, Republic of Korea; and OMELET, Daejeon 34141, Republic of Korea

Transportation Science, 2025, vol. 59, issue 2, 322-339

Abstract: When vehicle routing decisions are intertwined with higher-level decisions, the resulting optimization problems pose significant challenges for computation. Examples are the multi-depot vehicle routing problem (MDVRP), where customers are assigned to depots before delivery, and the capacitated location routing problem (CLRP), where the locations of depots should be determined first. A simple and straightforward approach for such hierarchical problems would be to separate the higher-level decisions from the complicated vehicle routing decisions. For each higher-level decision candidate, we may evaluate the underlying vehicle routing problems to assess the candidate. As this approach requires solving vehicle routing problems multiple times, it has been regarded as impractical in most cases. We propose a novel deep learning-based approach called the genetic algorithm with neural cost predictor to tackle the challenge and simplify algorithm developments. For each higher-level decision candidate, we predict the objective function values of the underlying vehicle routing problems using a pretrained graph neural network without actually solving the routing problems. In particular, our proposed neural network learns the objective values of the HGS-CVRP open-source package that solves capacitated vehicle routing problems. Our numerical experiments show that this simplified approach is effective and efficient in generating high-quality solutions for both MDVRP and CLRP and that it has the potential to expedite algorithm developments for complicated hierarchical problems. We provide computational results evaluated in the standard benchmark instances used in the literature.

Keywords: multi-depot vehicle routing problem; genetic algorithm; deep learning; cost prediction (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2023.0369 (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:59:y:2025:i:2:p:322-339

Access Statistics for this article

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