vehicle routing assignment problem

Stack Exchange Network

Stack Exchange network consists of 183 Q&A communities including Stack Overflow , the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Q&A for work

Connect and share knowledge within a single location that is structured and easy to search.

Determining the problem type - Vehicle Routing - Task assignment

I want to figure out what problem I'm dealing with so I can move in the right direction of research. I'm still at the very beginning of formulating the problem. What I've done so far is figure out just enough to understand how little I know about optimization problems. So for me it is also about the bascis.

The problem is probably a combination of several.

The minimization goal: I want to minimize the total time $t$ , or the costs, for the process.

• There is one vehicle.
• The vehicle has limited capacity.
• The vehicle moves from point / node to another to complete a task. So I think that nodes are equivalent to tasks in this problem?
• There is a distance between nodes. This is part of the costs, since this means travel time.
• A task $T_n$ takes a certain amount of time $t_T$ , e.g. $t_{T_n}=3\text{minutes}$ .
• Material is consumed per task.
• The vehicle starts fully loaded and can recharge the material at any station.
• There are at least two stations.

Why I am not making progress in my research: The complexity comes from the fact that a task has to happen twice in one place. Let's call them two types of tasks, "prepare" and "finish".

• Two task types. Both have to be done per location.
• There must be a certain amount of time between "prepare" $T_{pn}$ and "finish" $T_{fn}$ , e.g. 10 minutes.
• However, only a certain amount of time may elapse, not more, e.g. $t_{max} = 30\text{minutes}$ .

I had the feeling that this is about time windows, but what I find difficult is the fact that the task must be done twice in the same place or same node, but then with the different time windows. That means there are dependencies and they specify the starting points. So the start of $T_{f1}$ will be determined by $T_{p1}$ . At the same time I do not really care when a time window starts to begin with $T_{p1}$ , work just has to be done. It is OK, when $T_{p5}$ is done before $T_{p1}$ , this is flexible. And also, when $T_{p1..7}$ have been done, $T_{f1..7}$ can be done afterwards sequentially but do not have to. Tasks just need to be fulfilled within the time frame that is made up by $T_{pn}$ .

So I think the only hard dependency is the point of time $tp$ after $T_{pn}$ has been done:

So, $T_{fn}^{tp}$ lies within $[ ( T_{pn}^{tp} + 10\text{minutes} ) , ( T_{pn}^{tp} + 30\text{minutes} ) ]$

ps. Sorry, but I am not very sure about how to express all of this in the correct mathematical way w.r.t. optimization problems, this is something I would like to catch on in the near future, as soon as I know in which direction I should head now.

So by what I know so far this is some kind of vehicle routing problem VRP with time windows TW. But TW is not very strict, so is this more about scheduling?

And when I would start to implement a solution, what tools could I use for that?

• vehicle-routing

• 1 $\begingroup$ So you want to find a single route to serve all tasks in the shortest amount of time? Then you have a resource constrained shortest path problem. That is often solved by a labeling algorithm, which is a dynamic programming approach. $\endgroup$ –  gmn Commented Sep 23, 2022 at 9:03
• $\begingroup$ Why don't you just aggregate those two tasks as one? $\endgroup$ –  overboxed Commented Sep 24, 2022 at 0:40

3 Answers 3

I think that the keyword you are looking for is "temporal constraints". Here are a few articles related to this topic:

• "Combined vehicle routing and scheduling with temporal precedence and synchronization constraints" (Bredström et Rönnqvist, 2008) DOI
• "The vehicle routing problem with time windows and temporal dependencies" (Dohn et al., 2011) DOI
• "A constraint-programming based decomposition method for the Generalised Workforce Scheduling and Routing Problem (GWSRP)" (Bourreau et al., 2020) DOI

• 1 $\begingroup$ Adding to that: "An exact solution method for a rich helicopter flight scheduling problem arising in offshore oil and gas logistics" (Nafstad et al., 2021) handles a minimum time requirement between two visits in a route in a labeling algorithm. sciencedirect.com/science/article/pii/S0305054820302756 $\endgroup$ –  gmn Commented Sep 23, 2022 at 12:09

If you want to view the problem as a VRP, it might help to clone all the nodes. Rather than having a single node $N_j$ for task $j,$ you have node $N_j^p$ for the preparation portion of the task and node $N_j^f$ for the finishing portion of the task. You will also end up cloning arcs, so that arc $(N_i, N_j)$ becomes $(N_i^h,N_j^k)$ for all combinations of $h,k\in \lbrace p,f\rbrace.$ (You may also want to include arcs $N_j^p \rightarrow N_j^f$ with distance/travel time 0 to allow the vehicle to stick around after a prep task until the time window for the finish task opens.) Preventing a visit to the finish copy of a node before the visit to the prep copy is handled by the time window constraints.

You have a vehicle routing problem (VRP) here. Because you only have one vehicle, the problem can be reduced to a traveling salesman problem (TSP). Every Vehicle routing is an assignment problem. Basically, VRP is about the combination of assignments and knapsack. You assign a vehicle for each node and a knapsack for the commodity carried for each vehicle. From your description, besides Time Windows there are two keywords that you might perhaps want do some little digging into, which are dependent VRP and Multi-Trip VRP.

For the tools, you might want to consider approximate technique (meta or heuristics) because VRP is NP-hard.

• $\begingroup$ Additional keyword: Multi-depot, Split-delivery $\endgroup$ –  overboxed Commented Sep 23, 2022 at 15:51

Your Answer

Sign up or log in, post as a guest.

Required, but never shown

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy .

Not the answer you're looking for? Browse other questions tagged scheduling vehicle-routing or ask your own question .

• Featured on Meta
• Site maintenance - Mon, Sept 16 2024, 21:00 UTC to Tue, Sept 17 2024, 2:00...
• User activation: Learnings and opportunities
• Join Stack Overflow’s CEO and me for the first Stack IRL Community Event in...

Hot Network Questions

• How many minutes the Apollo astronauts had to wait from splashdown until the first frogmen touched the CM?
• In QGIS 3, changing borders of shared polygon shapefile features
• Definition of annuity
• What would the natural diet of Bigfoot be?
• How to reply to a revise and resubmit review, saying is all good?
• How to prove that the Greek cross tiles the plane?
• What would be an appropriate translation of Solitude?
• Looking for a short story on chess, maybe published in Playboy decades ago?
• Browse a web page through SSH? (Need to access router web interface remotely, but only have SSH access to a different device on LAN)
• How to best characterize the doctrine deriving from Palsgraf?
• The meaning of an implication in an existential quantifier
• How did people know that the war against the mimics was over?
• Is it safe to use the dnd 3.5 skill system in pathfinder 1e?
• For a bike with "Forged alloy crank with 44T compact disc chainring", can the chainring be removed?
• Difference between 2 version numbers from `adb --version`
• What prevents indoor climbing gyms from making a v18 boulder even if one hasn't been found outside?
• siunitx dollar per hour broken going from SI to qty
• Creating good tabularx
• How to prevent a bash script from running repeatedly at the start of the terminal
• How can a microcontroller (such as an Arduino Uno) that requires 7-21V input voltage be powered via USB-B which can only run 5V?
• Subject verb agreement - I as well as he is/am the culprit
• "There is a bra for every ket, but there is not a ket for every bra"
• How can I send instance attributes from Geometry Nodes to Shading Editor?
• Why would the absence of Chalmers' 'consciousness' make p-zombie world 'inconceivable'?

IEEE Account

• Change Username/Password
• Update Address

Purchase Details

• Payment Options
• Order History
• View Purchased Documents

Profile Information

• Communications Preferences
• Profession and Education
• Technical Interests
• US & Canada: +1 800 678 4333
• Worldwide: +1 732 981 0060
• Contact & Support
• About IEEE Xplore
• Accessibility
• Terms of Use
• Nondiscrimination Policy
• Privacy & Opting Out of Cookies

A not-for-profit organization, IEEE is the world's largest technical professional organization dedicated to advancing technology for the benefit of humanity. © Copyright 2024 IEEE - All rights reserved. Use of this web site signifies your agreement to the terms and conditions.

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

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 Genetic Algorithm with Neural Cost Predictor (GANCP) 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 pre-trained 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 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.

Funding: This research was funded by the Korean government (MSIT) through the National Research Foundation of Korea (NRF) grant RS-2023-00259550.

Key words: multi-depot vehicle routing problem, genetic algorithm, deep learning, cost prediction

1 Introduction

Vehicle Routing Problems (VRPs) have garnered significant attention over the past few decades due to their crucial role in last-mile delivery logistics. CapGemini Research Institute ( 2019 ) reports that last-mile delivery accounts for 41% of the supply chain expenditures. As a direct extension of the Traveling Salesman Problem (TSP), the Capacitated Vehicle Routing Problem (CVRP) forms a fundamental class of VRPs and serves as the basis for addressing many last-mile delivery challenges. In many real-life routing scenarios, the VRP under consideration often includes additional constraints, parameters, or assumptions. Such problems are referred to as VRP variants or rich VRPs.

Among the many VRP variants, we focus on hierarchical VRPs (HVRPs), where the higher-level decisions impact the lower-level decisions. Examples include two widely used VRP variants called the Multi-Depot VRP (MDVRP) and the Capacitated Location Routing Problem (CLRP). In essence, the MDVRP involves the higher-level task of clustering customers with order-fulfillment centers, from which the respective demands are fulfilled. Clustering decomposes the original problem into multiple CVRPs. Evidently, the MDVRP is at least as difficult as the CVRP, and thus an 𝒩 ⁢ 𝒫 𝒩 𝒫 \mathcal{NP} caligraphic_N caligraphic_P -Hard problem. In MDVRPs, the higher-level decisions involve assigning each customer to a depot, whereas the lower-level decisions focus on routing vehicles from each depot to its assigned customers. As a generalization of the MDVRP, the CLRP requires additional higher-level decisions that determine which depots should be opened from the available candidate locations.

The main challenge in obtaining real-time solutions to combinatorial optimization (CO) problems lies in their computational complexity. Although heuristics tackle this issue for relatively small and medium-sized problems, the search space for good solutions grows exponentially with the problem size. Many logistics problems in the practical settings encompass several hundred or even thousands of customers (Qi et al., 2012 ) . The MDVRP is a fundamental optimization problem in many real-world transportation problems, including parcel delivery, waste collection, mobile healthcare routing, and field service management. Some of these routing scenarios involve solving large networks comprising thousands of locations and need to be tackled on a daily basis, such as waste collection and e-commerce order fulfillment (Arnold et al., 2019 ) . In waste collection, numerous trucks dispatched from various waste disposal plants (depots) are tasked with collecting waste from tens of thousands of customers. In 2022, a prominent e-commerce firm Amazon Logistics processed 4.79 billion U.S. delivery orders (Capital One Shopping Research, 2019 ) , equating to approximately 9,116 orders per minute. These examples underscore the magnitude and complexity of large-scale vehicle routing faced by real-world businesses and the need for fast operational decisions.

As another example of an HVRP, consider grocery deliveries by an organization that operates a chain of grocery stores or hypermarkets across an urban area. If a customer’s delivery demands can be satisfied from multiple stores, the company needs to decide which store fulfills the customer demand more profitably. With several incoming orders from different geographical locations and a limited number of delivery agents available at each store, the organization needs to determine the optimal assignment of each customer to a store so that the overall transportation cost is minimized. It is evident that allocating one or more customers to their nearest store, disregarding other factors such as the geographical distribution of demands and the delivery capacities, may lead to suboptimal or even infeasible solutions. Presently, a prevalent method to address such large-scale HVRPs involves a cluster first and route second approach. However, employing a fixed strategy for higher-level decisions may result in increased operational costs.

The objective function value of an MDVRP with customer-depot assignments is calculated by adding the optimal costs of all decomposed CVRPs. For problems that can be decomposed into “simpler” subproblems, a convenient solution method is to find the optimal decomposition. However, recall that an MDVRP decomposition leads to multiple CVRPs that are still 𝒩 ⁢ 𝒫 𝒩 𝒫 \mathcal{NP} caligraphic_N caligraphic_P -Hard. To evaluate a decomposition, the only requirement is the optimal routing cost of each subproblem without the need for routing decisions. In this research, we train a deep neural network (NN) model to predict the optimal cost of each CVRP instance arising from the decomposition of an HVRP, without actually solving the CVRPs. The predicted cost can be leveraged as an approximate measure of the decomposition strategy’s effectiveness. With the help of a Genetic Algorithm (GA), we improve the clustering of customers with depots. The fitness cost of an assignment is calculated from the sum of subproblems’ cost predictions and the distinctiveness of the decomposition compared to other assignments. We refer to this approach as the Genetic Algorithm with Neural Cost Predictor ( GANCP ).

\text{GANCP}^{+} GANCP start_POSTSUPERSCRIPT + end_POSTSUPERSCRIPT . We compare the test results with the performance of an open-source generic VRP solver, the Vehicle Routing Open-source Optimization Machine (VROOM) (Coupey et al., 2023 ) . In many VRP variants, VROOM is known to produce high-quality solutions that are close to the best-known solutions reported in the literature. We analyze the performance of the cost prediction model using three different train data generation procedures. We also showcase the transferability of our heuristic to instances that are different from the trained distribution and size.

\text{GANCP}^{+} GANCP start_POSTSUPERSCRIPT + end_POSTSUPERSCRIPT has the potential to tackle many challenging hierarchical VRPs that arise in the real world for the following reasons. First, the trained NN can predict the cost of each candidate quickly. The biggest challenge in the decomposition approach for hierarchical VRPs is the time to solve subproblems. In our approach, we use the neural network to quickly generate a cost prediction without solving the problem. Second, our proposed NN can learn the cost values from standard VRP solvers for a wide range of problem sizes. Fundamental building blocks in hierarchical VRPs are well-studied problems such as CVRP, for which several outstanding VRP solvers exist. Therefore, we can train the NN for each standard VRP class and use it for various HVRPs that use the same VRP class of problems as the subproblems. This can significantly reduce algorithm development time, as we can focus on handling non-standard modeling components within the GA framework without considering the routing solutions. Third, our proposed NN model can provide a robust prediction capability for the same VRP class within different problem contexts. We demonstrate the transferability of our trained NN model from the MDVRP to the CLRP by experimenting with multiple benchmark datasets.

Our goal in this paper is, therefore, to show that the proposed approach can simplify algorithm development processes for complicated hierarchical vehicle routing problems and produce quality solutions in a short amount of time rather than to develop an algorithm that can produce the best solutions and outperform all existing algorithms. We will focus on illustrating this main point throughout the paper and will use MDVRP and CLRP as examples.

The remainder of this paper is organized as follows. In Section 2 , we discuss the relevant literature on the CVRP methodologies involving reinforcement learning (RL), machine learning (ML), heuristics, and cost estimation techniques, followed by a brief review of related literature on MDVRP and CLRP. Section 3 describes the HVRPs in general and focuses on the decomposition of the MDVRP to VRPs based on the mathematical formulation. The neural network prediction model and training details are discussed in Section 4 . Section 5 explains our MDVRP solution methodology that incorporates the NN model architecture and the heuristics in detail. We discuss and evaluate the performance of the NN model using three different training procedures in Section 6 . We further demonstrate the effectiveness of our proposed heuristic on multiple MDVRP instances, including out-of-distribution and out-of-range instances. The paper finally concludes with a discussion of relevant and related research directions in optimization using supervised learning in Section 7 . In addition, we demonstrate the transferability of our approach with a simple extension of the MDVRP methodology for the CLRP in Section A.1 and examine the results of the CLRP experiments in Section A.2 .

2 Literature Review

First, we review the relevant literature on VRPs that use deep RL as a solution methodology. Subsequently, we explore the supervised learning approaches applied to VRPs. We further discuss pertinent approximation techniques utilized in the vehicle routing literature for optimal cost estimations. This is followed by a review of relevant research on solution methods for the MDVRP and the CLRP. Finally, we highlight our contributions to the existing research gap in this domain.

2.1 Deep Reinforcement Learning Approaches for VRPs

Over the past few years, deep reinforcement learning has been demonstrating notable success in solving combinatorial optimization problems, especially the TSP and the CVRP. Bello et al. ( 2017 ) introduces an effective deep RL framework to train and solve the TSP using pointer networks (Vinyals et al., 2015 ) . The problem is modeled as a Markov Decision Process and uses the pointer network for encoding the inputs, which are then learned using policy gradients. Nazari et al. ( 2018 ) extends this work for VRPs without a Recurrent Neural Network for the input encoding. Unlike Natural Language Processing, the order of the input sequence—the customer locations—can be treated independently in the VRP. While the inclusion of a pointer encoder network does not negatively impact the final accuracy, it delays learning due to added model complexity. Kool et al. ( 2019 ) yields better performance for CVRPs using an architecture for solution construction with multiple multi-head attention layers, proposed in Vaswani et al. ( 2017 ) , to capture the node dependencies, and using the REINFORCE algorithm to train the model. With consideration of symmetries in the solutions of a CO problem, Kwon et al. ( 2020 ) designs the Policy Optimization with Multiple Optima (POMO) network with a modified REINFORCE algorithm to explore the solution space more effectively. This improves the results in terms of both performance gap and inference time compared to the existing architectures. Recent studies have also addressed different VRP variants using deep RL frameworks (Bogyrbayeva et al., 2023 ; Park et al., 2023 ) . All of these approaches are end-to-end solution approaches that rely solely on neural networks to solve the problem.

Traditional end-to-end RL frameworks for CO solution construction have limitations concerning the scope and size of the problems they can effectively address. Another active research focus is on the use of RL as an enhancement heuristic for problem partitions or when an initial solution is known. Lu et al. ( 2020 ) utilize an RL agent as a heuristic controller to apply intra-route and inter-route improvement operators to an initial randomly generated solution and obtain high-quality CVRP solutions. In a similar study, Wu et al. ( 2021 ) proposes an RL model that employs a single improvement operator instead of multiple operations in combination. The authors compare operators such as 2-opt, node swap, and relocation and illustrate that 2-opt yields better results. Zong et al. ( 2022 ) proposes a Rewriting-by-Generating framework for solving large-scale VRPs hierarchically. Here, the Rewriter agent partitions the customers into independent regions, and the Generator agent solves the routing problem in each region. This method outperforms the HGS-CVRP solver by Vidal ( 2022 ) for large-scale problems, where the hyperparameters are fine-tuned for small to medium-size CVRP problems. However, RL requires higher computational time for training and inference compared to supervised machine learning and faces challenges in exploration due to the iterative nature of reinforcement learning with the environment.

2.2 Supervised Learning Approaches for VRPs

Multiple supervised learning frameworks exist for solving the VRP through the integration of exact methods, heuristics, or predictions of subproblem costs. The integration of ML with exact optimization techniques proves considerable promise and is currently a subject of active research. For example, Furian et al. ( 2021 ) solves VRPs using a branch-and-price method where ML models are used to predict the decision variables and branching scores. Another interesting study is Morabit et al. ( 2021 ) , where a Graph Neural Network (GNN) acts as a column selector to accelerate column generation for the VRP with time windows. Kim et al. ( 2024 ) further demonstrates that GNN can be leveraged to solve the separation problems in cutting plane methods, particularly for large-scale instances.

A few recent studies utilize supervised machine learning to learn potential cost improvements for a subproblem and iteratively improve the solution. Li et al. ( 2021 ) proposes a method that iteratively improves the solution to large-scale VRPs by learning to select subproblems and estimating the corresponding subsolution costs using a transformer architecture. Using a combination of the subproblem selector and cost estimation, the problem can be partitioned into smaller problems that are easily solved. Kim et al. ( 2023 ) presents a neural cross-exchange operator to solve multiple VRP variants based on cost decrement predictions and demonstrates its computational benefits against the traditional operator. In a recent study, Varol et al. ( 2024 ) proposed a neural network tour length estimator for a very large-scale Generalized TSP, incorporating instance-specific features to enhance estimation accuracy. The authors employ a similar approach to ours, integrating the neural network with a genetic algorithm in the solution framework. However, their estimator performs well only on specific problem sizes, in contrast to our NN model. The results of these studies showcase the efficacy of supervised learning in addressing large-scale routing problems. This stream of research motivates our proposed methodology.

2.3 Optimal Cost Estimations of VRPs

Numerous studies aim to accurately estimate optimal routing costs based on the topological distribution of customers, demands, and vehicle capacities. These studies typically utilize two methodologies: Continuous Approximation (CA) and Regression. CA, as an alternative to discrete models, employs smooth density functions to represent the network and is particularly effective for larger instances. CA techniques find application in estimating optimal transportation costs across various VRP variants, including emission minimization VRP (Saberi and Verbas, 2012 ) , school bus routing (Ellegood et al., 2015 ) , hub location routing problems (Ghaffarinasab et al., 2018 ) , dynamic multiple TSP (Garn, 2021 ) , and same-day delivery (Banerjee et al., 2022 ; Stroh et al., 2022 ) . A detailed review of the CA approaches used in freight distribution is available in Franceschetti et al. ( 2017 ) .

Among analytical expressions, the Daganzo-approximation (Robust et al., 1990 ) is widely recognized for estimating the optimal CVRP distance given by following the formula:

where A 𝐴 A italic_A represents the bounded area within which N 𝑁 N italic_N number of customers are distributed, k 𝑘 k italic_k is an area shape constant, and C 𝐶 C italic_C is the maximum number of customers a vehicle can serve. Figliozzi ( 2008 ) improves the accuracy of cost approximation using linear regression to calculate the optimal cost based on a few critical instance features as follows:

CA and regression models require careful adaptation for each problem type with the recognition of critical instance features. Further, they do not generalize well when confronted with varying problem sizes and data distributions. We employ a graph neural network to capture both the topological and demand features of the customers. This approach eliminates the need for focused feature engineering across different data types, enabling highly accurate predictions of optimal costs across varying problem sizes and data distributions.

2.4 Optimization Approaches for MDVRP and CLRP

Multiple studies use exact methods to solve the MDVRP, such as Laporte et al. ( 1988 ) , Contardo and Martinelli ( 2014 ) , and Baldacci and Mingozzi ( 2009 ) . Similarly, for the study of the CLRP using exact methods, one may refer to Baldacci et al. ( 2011 ) , Belenguer et al. ( 2011 ) and Contardo et al. ( 2014 ) . As a consequence of the 𝒩 ⁢ 𝒫 𝒩 𝒫 \mathcal{NP} caligraphic_N caligraphic_P -hardness of these problems, efficient heuristics are critical to the development of industrial routing solutions.

Cordeau et al. ( 1997 ) proposes a notable Tabu Search (TS) heuristic to solve the MDVRP, the Periodic VRP, and the Periodic TSP. A few years later, genetic algorithms emerged as one of the most effective heuristics for vehicle routing. Vidal et al. ( 2012 ) proposes a fast and efficient hybrid genetic algorithm that solves the MDVRP and the Periodic VRP. The algorithm differentiates neighboring solutions using a diversity factor in the fitness cost. In addition, a pool of infeasible solutions is preserved for diversification and better search space. Vidal et al. ( 2014 ) further improves the results where the depot, vehicle, and first customer visited on each route are optimally determined using a dynamic programming methodology. Sadati et al. ( 2021 ) presents a Variable Neighborhood Search algorithm that solves the MDVRP variants with a tabu-shaking mechanism to improve the search trajectory. End-to-end RL frameworks for MDVRP are presented in Zou et al. ( 2022 ) based on an improved transformer model and in Zhang et al. ( 2023 ) using Graph Attention Networks.

One of the most effective existing algorithms for solving the large-scale CLRP is by Schneider and Löffler ( 2019 ) , which explores multiple depot configurations using a Tree-Based Search Algorithm (TBSA). For a given configuration, an MDVRP is solved at the routing phase using a granular tabu search. The paper also discusses different variants of the algorithm with trade-offs in computational time and solution quality. More recently, Akpunar and Akpinar ( 2021 ) proposed a hybrid adaptive large neighborhood search method that demonstrates improved benchmark performance in a few CLRP benchmark instances.

\text{GANCP}^{+} GANCP start_POSTSUPERSCRIPT + end_POSTSUPERSCRIPT heuristic is empowered with a supervised learning model for cost estimation, which requires less training time and is, more importantly, applicable to distinct and large problem sizes, producing near-optimal results. To the best of our knowledge, this paper is the first to address solving large-scale hierarchical VRPs using a deep learning architecture to evaluate the subproblem decompositions.

3 Hierarchical Vehicle Routing Problems

Hierarchical vehicle routing problems (HVRPs) involve decisions made at multiple levels, often executed sequentially, to obtain an optimal routing solution. In a large or complex HVRP, decisions made at higher levels can decompose the problem into smaller subproblems. A good solution strategy involves identifying effective higher-level decisions that optimize the objective function while considering the original problem constraints. Higher-level decisions influence subsequent decisions, solution quality, and the optimal objective cost of the original problem. Lower-level decisions include detailed vehicle routing and schedule plans to complete deliveries or services designated to each vehicle.

As the HVRPs require decisions in addition to and including vehicle routing, it is computationally challenging to solve such problems in many real-life scenarios. This paper examines two prevalent HVRP variants: the MDVRP and the CLRP, with the latter analyzed in the Appendix. Due to the complexity of the HVRPs, multiple techniques and their combination are often used to solve large instances. A straightforward approach is to focus on the method to find effective higher-level decisions and solve the corresponding subproblems using an existing efficient algorithm or a proven solver. The higher-level decisions decompose the MDVRPs and the CLRPs into subsequent CVRPs, where the total solution cost of the subproblems determines the quality of the higher-level decisions. Since the CVRPs are well-researched, we focus on a heuristic method to find the higher-level decisions for the HVRPs.

In the remainder of this section, we first discuss the arc-based flow formulation of the MDVRP to ensure mathematical clarity. Following this, we demonstrate how employing a decomposition approach yields CVRP subproblems that reduce the complexity of the original problem. Later, we provide a discussion regarding the generalizability of the hierarchical decomposition approach for solving HVRPs.

3.1 Multi-Depot Vehicle Routing Problem

Consider a complete and undirected graph 𝒢 = ( 𝒱 , ℰ ) 𝒢 𝒱 ℰ \mathcal{G}=(\mathcal{V},\mathcal{E}) caligraphic_G = ( caligraphic_V , caligraphic_E ) , where 𝒱 𝒱 \mathcal{V} caligraphic_V represents the set of all nodes and ℰ ℰ \mathcal{E} caligraphic_E denotes the set of all edges connecting nodes in 𝒱 𝒱 \mathcal{V} caligraphic_V . Let 𝒟 ⊂ 𝒱 𝒟 𝒱 \mathcal{D}\subset\mathcal{V} caligraphic_D ⊂ caligraphic_V be the set of depots, and 𝒞 ⊂ 𝒱 𝒞 𝒱 \mathcal{C}\subset\mathcal{V} caligraphic_C ⊂ caligraphic_V be the set of customers, such that 𝒱 = 𝒟 ∪ 𝒞 𝒱 𝒟 𝒞 \mathcal{V}=\mathcal{D}\cup\mathcal{C} caligraphic_V = caligraphic_D ∪ caligraphic_C . Furthermore, let 𝒦 d subscript 𝒦 𝑑 \mathcal{K}_{d} caligraphic_K start_POSTSUBSCRIPT italic_d end_POSTSUBSCRIPT be the set of vehicles available for order-fulfillment at depot d ∈ 𝒟 𝑑 𝒟 d\in\mathcal{D} italic_d ∈ caligraphic_D , and 𝒦 = ∑ d ∈ 𝒟 𝒦 d 𝒦 subscript 𝑑 𝒟 subscript 𝒦 𝑑 \mathcal{K}=\sum_{d\in\mathcal{D}}\mathcal{K}_{d} caligraphic_K = ∑ start_POSTSUBSCRIPT italic_d ∈ caligraphic_D end_POSTSUBSCRIPT caligraphic_K start_POSTSUBSCRIPT italic_d end_POSTSUBSCRIPT is the set of all vehicles. Each vehicle k ∈ 𝒦 𝑘 𝒦 k\in\mathcal{K} italic_k ∈ caligraphic_K has a capacity Q k subscript 𝑄 𝑘 Q_{k} italic_Q start_POSTSUBSCRIPT italic_k end_POSTSUBSCRIPT , and customer i ∈ 𝒞 𝑖 𝒞 i\in\mathcal{C} italic_i ∈ caligraphic_C has a positive demand q i subscript 𝑞 𝑖 q_{i} italic_q start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT such that q i ≤ Q min subscript 𝑞 𝑖 subscript 𝑄 min q_{i}\leq Q_{\text{min}} italic_q start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ≤ italic_Q start_POSTSUBSCRIPT min end_POSTSUBSCRIPT , where Q min subscript 𝑄 min Q_{\text{min}} italic_Q start_POSTSUBSCRIPT min end_POSTSUBSCRIPT is the minimum vehicle capacity among the fleet of vehicles. Note that a vehicle that starts from a depot must return to the same depot after completing its route.

We examine the mathematical model for MDVRP, originally proposed by Golden et al. ( 1977 ) and later improved by Ramos et al. ( 2020 ) through the distinct partitioning of vehicles among depots. Let the binary integer decision variable x i ⁢ j ⁢ k subscript 𝑥 𝑖 𝑗 𝑘 x_{ijk} italic_x start_POSTSUBSCRIPT italic_i italic_j italic_k end_POSTSUBSCRIPT equal 1 if vehicle k 𝑘 k italic_k traverses the edge ( i , j ) 𝑖 𝑗 (i,j) ( italic_i , italic_j ) in a feasible solution, and 0 otherwise. The traversal cost for the edge ( i , j ) 𝑖 𝑗 (i,j) ( italic_i , italic_j ) is denoted as c i ⁢ j subscript 𝑐 𝑖 𝑗 c_{ij} italic_c start_POSTSUBSCRIPT italic_i italic_j end_POSTSUBSCRIPT . The problem is then formulated as follows:

The objective function ( 3 ) minimizes the total routing cost for vehicles across all depots. Constraints ( 4 ) ensures that each customer is visited exactly once in the optimal solution. Flow conservation is enforced using constraints ( 5 ), while constraints ( 6 ) ensure that the total demand fulfilled by a vehicle does not exceed its capacity. Additionally, constraints ( 7 ) indicate that each vehicle belonging to a depot is utilized for routing at most once. Subtour elimination constraints are presented in ( 8 ). Constraints ( 9 ) prevent direct tours between depots, and constraints ( 10 ) distinctly partition the vehicles between depots. Our MDVRP formulation captures the fundamental aspects of vehicle routing with multiple depots and excludes additional constraints such as service times, depot capacities, and vehicle opening costs.

Next, we examine the decomposition of the MDVRP model in ( 3 )–( 11 ) into subproblems. As evident from the formulation, vehicles are distinctly categorized based on their assigned depots, and inter-depot routes are strictly prohibited. Thus, once customers are assigned to the depots, the problem decomposes into | 𝒟 | 𝒟 |\mathcal{D}| | caligraphic_D | distinct CVRP subproblems. Let 𝒞 P = { 𝒞 1 , 𝒞 2 , … , 𝒞 | 𝒟 | } superscript 𝒞 𝑃 subscript 𝒞 1 subscript 𝒞 2 … subscript 𝒞 𝒟 \mathcal{C}^{P}=\{\mathcal{C}_{1},\mathcal{C}_{2},\dots,\mathcal{C}_{|\mathcal% {D}|}\} caligraphic_C start_POSTSUPERSCRIPT italic_P end_POSTSUPERSCRIPT = { caligraphic_C start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT , caligraphic_C start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT , … , caligraphic_C start_POSTSUBSCRIPT | caligraphic_D | end_POSTSUBSCRIPT } be a partition of 𝒞 𝒞 \mathcal{C} caligraphic_C such that 𝒞 = 𝒞 1 ∪ 𝒞 2 ∪ ⋯ ∪ 𝒞 | 𝒟 | 𝒞 subscript 𝒞 1 subscript 𝒞 2 ⋯ subscript 𝒞 𝒟 \mathcal{C}=\mathcal{C}_{1}\cup\mathcal{C}_{2}\cup\cdots\cup\mathcal{C}_{|% \mathcal{D}|} caligraphic_C = caligraphic_C start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT ∪ caligraphic_C start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT ∪ ⋯ ∪ caligraphic_C start_POSTSUBSCRIPT | caligraphic_D | end_POSTSUBSCRIPT and 𝒞 i ∩ 𝒞 j = ∅ subscript 𝒞 𝑖 subscript 𝒞 𝑗 \mathcal{C}_{i}\cap\mathcal{C}_{j}=\emptyset caligraphic_C start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ∩ caligraphic_C start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT = ∅ for 1 ≤ i < j ≤ | 𝒟 | 1 𝑖 𝑗 𝒟 1\leq i<j\leq|\mathcal{D}| 1 ≤ italic_i < italic_j ≤ | caligraphic_D | . Additionally, we assume that each depot serves at least one customer, i.e., | 𝒞 d | ≥ 1 , ∀ d ∈ 𝒟 formulae-sequence subscript 𝒞 𝑑 1 for-all 𝑑 𝒟 |\mathcal{C}_{d}|\geq 1,\forall d\in\mathcal{D} | caligraphic_C start_POSTSUBSCRIPT italic_d end_POSTSUBSCRIPT | ≥ 1 , ∀ italic_d ∈ caligraphic_D . The partition 𝒞 P superscript 𝒞 𝑃 \mathcal{C}^{P} caligraphic_C start_POSTSUPERSCRIPT italic_P end_POSTSUPERSCRIPT represents the distinct assignment of | 𝒞 | 𝒞 |\mathcal{C}| | caligraphic_C | customers among | 𝒟 | 𝒟 |\mathcal{D}| | caligraphic_D | depots. We assume that the partition is ordered so that 𝒞 d subscript 𝒞 𝑑 \mathcal{C}_{d} caligraphic_C start_POSTSUBSCRIPT italic_d end_POSTSUBSCRIPT is served by depot d 𝑑 d italic_d .

Let 𝒱 d = { d } ∪ 𝒞 d , ∀ d ∈ 𝒟 formulae-sequence subscript 𝒱 𝑑 𝑑 subscript 𝒞 𝑑 for-all 𝑑 𝒟 \mathcal{V}_{d}=\{d\}\cup\mathcal{C}_{d},\forall d\in\mathcal{D} caligraphic_V start_POSTSUBSCRIPT italic_d end_POSTSUBSCRIPT = { italic_d } ∪ caligraphic_C start_POSTSUBSCRIPT italic_d end_POSTSUBSCRIPT , ∀ italic_d ∈ caligraphic_D . With a partition 𝒞 P superscript 𝒞 𝑃 \mathcal{C}^{P} caligraphic_C start_POSTSUPERSCRIPT italic_P end_POSTSUPERSCRIPT , the original problem reduces to | 𝒟 | 𝒟 |\mathcal{D}| | caligraphic_D | CVRPs, and a subproblem d ∈ 𝒟 𝑑 𝒟 d\in\mathcal{D} italic_d ∈ caligraphic_D is represented as follows:

The subproblem formulation ( 12 )–( 18 ) for depot d 𝑑 d italic_d , obtained after decomposition, represents the well-known CVRP three-index flow formulation. By partitioning customers across different depots, the complexity of the original problem was significantly reduced due to the decrease in the number of feasible solutions. The quality of a decomposition strategy can be estimated based on the sum of the optimal routing costs of its subproblems. However, examining multiple partitions by solving all subproblems further increases computational difficulty. In this study, we introduce an approach to finding good higher-level decisions using a simple heuristic and machine learning. Note that a random partition 𝒞 P superscript 𝒞 𝑃 \mathcal{C}^{P} caligraphic_C start_POSTSUPERSCRIPT italic_P end_POSTSUPERSCRIPT may violate the vehicle capacity and fleet number constraints for one or more depots. Therefore, efforts must be made to carefully avoid any such infeasibility when possible. For instance, an undesirable partition occurs when the total demand of customers assigned to a depot surpasses the total vehicle capacity available at that depot. However, detecting feasibility based on higher-level decisions can be challenging and may only become apparent during subproblem resolution. A similar decomposition methodology can be constructed for the CLRP, which incorporates additional factors such as depot capacities, depot costs, and vehicle opening costs to evaluate the decomposition, along with the total cost of subproblems.

3.2 General Discussion

Although this is a direct decomposition approach, there has been limited research on related methodologies due to the challenge of evaluating multiple decomposition strategies by addressing several subproblems. Our solution to this issue involves training a supervised learning network to predict the optimal routing cost of a CVRP based on the input graph structure. Since the neural network is trained only to predict the near-optimal cost rather than finding the actual routing solution, we benefit from significant computational advantages. Consequently, to evaluate higher-level decisions, we need P ⁢ ( 𝐱 ) 𝑃 𝐱 P(\mathbf{x}) italic_P ( bold_x ) and do not directly require 𝐱 ∈ 𝐗 𝐱 𝐗 \mathbf{x}\in\mathbf{X} bold_x ∈ bold_X . The next section discusses the neural network architecture used to approximate the optimal cost of a subproblem.

4 Learning to predict CVRP Costs

Each route must start and end at the depot.

Each customer must belong to exactly one route.

The total demand of customers assigned to a route must not exceed the vehicle capacity Q 𝑄 Q italic_Q .

We assume homogeneity in the vehicle capacities and do not impose an upper bound on the number of vehicles. In the following section, we describe our cost prediction approach for CVRPs using a graph neural network (GNN). Using supervised learning, GNN is trained to predict the optimal CVRP cost estimated by the HGS-CVRP solver. An overview of the prediction model is presented in Figure 1 .

4.1 Cost Prediction using Graph Neural Network

KNN Graph Construction

We transform an input CVRP instance 𝒢 𝒢 \mathcal{G} caligraphic_G into a graph-structured data 𝒢 knn subscript 𝒢 knn \mathcal{G}_{\text{knn}} caligraphic_G start_POSTSUBSCRIPT knn end_POSTSUBSCRIPT to better represent the node-level and edge-level features for effectively training the GNN. Here, 𝒢 knn subscript 𝒢 knn \mathcal{G}_{\text{knn}} caligraphic_G start_POSTSUBSCRIPT knn end_POSTSUBSCRIPT is a graph transformation of 𝒢 𝒢 \mathcal{G} caligraphic_G constructed using the k-nearest neighbor (KNN) method. During the KNN graph construction, each node is connected to its k 𝑘 k italic_k nearest neighbors based on the Euclidean distances. The node features 𝐔 𝐔 \mathbf{U} bold_U consists of two components: normalized node coordinates and normalized demand. The normalized node coordinates of 𝒢 knn subscript 𝒢 knn \mathcal{G}_{\text{knn}} caligraphic_G start_POSTSUBSCRIPT knn end_POSTSUBSCRIPT are computed by translating the node coordinates to ensure they are positive. This is achieved by adding the absolute value of the minimum coordinate values and then dividing them by the maximum coordinate value. The normalized demand is defined as the ratio of the demand q i subscript 𝑞 𝑖 q_{i} italic_q start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT to the vehicle capacity Q 𝑄 Q italic_Q .

Graph Neural Network Architecture

The cost prediction GNN f 𝜽 subscript 𝑓 𝜽 f_{\bm{\theta}} italic_f start_POSTSUBSCRIPT bold_italic_θ end_POSTSUBSCRIPT with parameters 𝜽 𝜽 {\bm{\theta}} bold_italic_θ predicts the optimal cost of 𝒢 𝒢 \mathcal{G} caligraphic_G as v ^ ^ 𝑣 \hat{v} over^ start_ARG italic_v end_ARG . Our GNN architecture comprises the encoder, which consists of a stack of self-attention blocks (Vaswani et al., 2017 ) , and the decoder, a linear layer followed by the graph readout module. f 𝜽 subscript 𝑓 𝜽 f_{{\bm{\theta}}} italic_f start_POSTSUBSCRIPT bold_italic_θ end_POSTSUBSCRIPT predicts the cost as follows:

where Encoder ⁢ ( ⋅ ) Encoder ⋅ \texttt{Encoder}(\cdot) Encoder ( ⋅ ) and Decoder ⁢ ( ⋅ ) Decoder ⋅ \texttt{Decoder}(\cdot) Decoder ( ⋅ ) are described in the following paragraphs.

𝑁 1 ℎ \mathbf{U^{\prime}}\in\mathbb{R}^{(N+1)\times h} bold_U start_POSTSUPERSCRIPT ′ end_POSTSUPERSCRIPT ∈ blackboard_R start_POSTSUPERSCRIPT ( italic_N + 1 ) × italic_h end_POSTSUPERSCRIPT , where h ℎ h italic_h denotes the hidden node feature dimension. This transformation is achieved through a series of operations. First, a linear embedding layer is applied to match the input node feature dimension d ~ ~ 𝑑 \tilde{d} over~ start_ARG italic_d end_ARG to h ℎ h italic_h . Then, multiple self-attention blocks are employed to learn the attention scores with respect to the extracted node features. Each self-attention block consists of two steps: MHA ⁢ ( ⋅ ) MHA ⋅ \texttt{MHA}(\cdot) MHA ( ⋅ ) and FeedForward ⁢ ( ⋅ ) FeedForward ⋅ \texttt{FeedForward}(\cdot) FeedForward ( ⋅ ) . The Multi-Head Attention (MHA) mechanism divides the input into multiple heads and computes the attention for each head simultaneously. Each head may prioritize different aspects of the input data, leading to focused learning and improved accuracy.

The use of MHA in the graph encoder exhibits multiple benefits over other architectures such as Multilayer Perceptron (MLP). Firstly, MHA handles an arbitrary number of input nodes within a single model. In contrast, traditional networks such as MLP are incapable of handling variable-length data and this limits the generalizability of learning to predict a general VRP instance. Another significant advantage of MHA is its representational capability for complex graph data. By dynamically adjusting the strength of relationships among nodes based on their features, MHA can disregard the correlations between the nodes that do not impact the CVRP cost prediction. On the contrary, the prediction accuracy of conventional GNN architectures like Graph Convolutional Networks and Graph Attention Networks relies on the design of the input graph structure. The dynamic edge weight allocation of MHA mitigates the errors arising from suboptimal graph designs. Furthermore, MHA offers higher computational efficiency with matrix multiplication on modern computing frameworks compared to the message-passing frameworks in traditional GNNs, leading to faster training and inference.

If head i subscript head 𝑖 \text{head}_{i} head start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT denotes the attention applied to 𝐔 𝐔 \mathbf{U} bold_U for i ∈ { 1 , 2 , … , H } 𝑖 1 2 … 𝐻 i\in\{1,2,\dots,H\} italic_i ∈ { 1 , 2 , … , italic_H } , and for a learnable parameter 𝐖 𝐎 ∈ ℝ H × h superscript 𝐖 𝐎 superscript ℝ 𝐻 ℎ \mathbf{W^{O}}\in\mathbb{R}^{H\times h} bold_W start_POSTSUPERSCRIPT bold_O end_POSTSUPERSCRIPT ∈ blackboard_R start_POSTSUPERSCRIPT italic_H × italic_h end_POSTSUPERSCRIPT , the MHA ⁢ ( ⋅ ) MHA ⋅ \texttt{MHA}(\cdot) MHA ( ⋅ ) step is defined as follows:

where the Attention ⁢ ( ⋅ ) Attention ⋅ \texttt{Attention}(\cdot) Attention ( ⋅ ) transformation is applied to each node u i subscript 𝑢 𝑖 u_{i} italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT in 𝐔 𝐔 \mathbf{U} bold_U to compute the updated node feature u i ′ subscript superscript 𝑢 ′ 𝑖 u^{\prime}_{i} italic_u start_POSTSUPERSCRIPT ′ end_POSTSUPERSCRIPT start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT , given by

where 𝐖 𝐐 superscript 𝐖 𝐐 \mathbf{W^{Q}} bold_W start_POSTSUPERSCRIPT bold_Q end_POSTSUPERSCRIPT , 𝐖 𝐊 superscript 𝐖 𝐊 \mathbf{W^{K}} bold_W start_POSTSUPERSCRIPT bold_K end_POSTSUPERSCRIPT , and 𝐖 𝐕 ∈ ℝ h × h superscript 𝐖 𝐕 superscript ℝ ℎ ℎ \mathbf{W^{V}}\in\mathbb{R}^{h\times h} bold_W start_POSTSUPERSCRIPT bold_V end_POSTSUPERSCRIPT ∈ blackboard_R start_POSTSUPERSCRIPT italic_h × italic_h end_POSTSUPERSCRIPT are the learnable parameters, 𝒩 ⁢ ( i ) 𝒩 𝑖 \mathcal{N}(i) caligraphic_N ( italic_i ) represents the set of neighbors of node i 𝑖 i italic_i , and softmax denotes the softmax function applied over j ∈ 𝒩 ⁢ ( i ) 𝑗 𝒩 𝑖 j\in\mathcal{N}(i) italic_j ∈ caligraphic_N ( italic_i ) . After the Multi-Head Attention (MHA) step, the updated node features 𝐔 ′ superscript 𝐔 ′ \mathbf{U^{\prime}} bold_U start_POSTSUPERSCRIPT ′ end_POSTSUPERSCRIPT are obtained. The attention mechanism is applied to the neighbors of each node, and the attention weights are computed based on the similarity between the node features. This approach allows the encoder to capture the local relationships between the nodes.

After accounting for the local relationships between the nodes, Encoder ⁢ ( ⋅ ) Encoder ⋅ \texttt{Encoder}(\cdot) Encoder ( ⋅ ) applies FeedForward ⁢ ( ⋅ ) FeedForward ⋅ \texttt{FeedForward}(\cdot) FeedForward ( ⋅ ) to process nodes independently. The FeedForward ⁢ ( ⋅ ) FeedForward ⋅ \texttt{FeedForward}(\cdot) FeedForward ( ⋅ ) operator is a multilayer perceptron model applied to each node feature. The updated node features 𝐔 ′ superscript 𝐔 ′ \mathbf{U^{\prime}} bold_U start_POSTSUPERSCRIPT ′ end_POSTSUPERSCRIPT are computed using the normalization layers LayerNorm ⁢ ( ⋅ ) LayerNorm ⋅ \texttt{LayerNorm}(\cdot) LayerNorm ( ⋅ ) (Ba et al., 2016 ) and residual connections (He et al., 2016 ) , which are applied to enhance the trainability of the deep models. To summarize, Encoder ⁢ ( ⋅ ) Encoder ⋅ \texttt{Encoder}(\cdot) Encoder ( ⋅ ) consists of the following sequential steps:

The Decoder ⁢ ( ⋅ ) Decoder ⋅ \texttt{Decoder}(\cdot) Decoder ( ⋅ ) operator subsequently transforms the latent vectors 𝐔 ′ superscript 𝐔 ′ \mathbf{U^{\prime}} bold_U start_POSTSUPERSCRIPT ′ end_POSTSUPERSCRIPT into the predicted optimal cost v ^ ^ 𝑣 \hat{v} over^ start_ARG italic_v end_ARG . This transformation involves a linear layer to project the latent vectors into a lower-dimensional space, followed by a graph readout module to aggregate the graph information. Decoder ⁢ ( ⋅ ) Decoder ⋅ \texttt{Decoder}(\cdot) Decoder ( ⋅ ) is defined as follows:

where 𝒱 𝒱 \mathcal{V} caligraphic_V represents the set of nodes in 𝒢 knn subscript 𝒢 knn \mathcal{G}_{\text{knn}} caligraphic_G start_POSTSUBSCRIPT knn end_POSTSUBSCRIPT , 𝟏 | 𝒱 | = ( 1 , 1 , … , 1 ) ∈ ℝ 1 × | 𝒱 | subscript 1 𝒱 1 1 … 1 superscript ℝ 1 𝒱 \mathbf{1}_{|\mathcal{V}|}=(1,1,\dots,1)\in\mathbb{R}^{1\times|\mathcal{V}|} bold_1 start_POSTSUBSCRIPT | caligraphic_V | end_POSTSUBSCRIPT = ( 1 , 1 , … , 1 ) ∈ blackboard_R start_POSTSUPERSCRIPT 1 × | caligraphic_V | end_POSTSUPERSCRIPT , and 𝐖 ∈ ℝ h × 1 𝐖 superscript ℝ ℎ 1 \mathbf{W}\in\mathbb{R}^{h\times 1} bold_W ∈ blackboard_R start_POSTSUPERSCRIPT italic_h × 1 end_POSTSUPERSCRIPT and 𝐛 ∈ ℝ | 𝒱 | × 1 𝐛 superscript ℝ 𝒱 1 \mathbf{b}\in\mathbb{R}^{|\mathcal{V}|\times 1} bold_b ∈ blackboard_R start_POSTSUPERSCRIPT | caligraphic_V | × 1 end_POSTSUPERSCRIPT are the scalar projection parameters. The graph readout module calculates a weighted average of the transformed latent vectors to produce a scalar output. This approach allows the decoder to capture the global relationships between the nodes.

4.2 Training

Existing CVRP benchmark datasets are insufficient in quantity to train this model, and thus, based on the problem requirements, CVRP instances need to be generated and solved to optimality (or near-optimality) to form the training data. An effective and widely used heuristic method for this problem is the Hybrid Genetic Search (HGS) for CVRP by Vidal ( 2022 ) , which has an open-source implementation. HGS-CVRP solver remains a top-performing metaheuristic in terms of methodological simplicity, solution quality, and convergence speed. We utilize a key feature of this solver by setting a time limit to compute the near-optimal routing costs for the train data, especially for larger instances.

Due to input data normalization, the final cost from average pooling needs to be rescaled by a corresponding factor to obtain the final cost prediction of the CVRP instance. We use the simple yet effective mean squared error as our loss function ( 19 ).

5 Solution Methodology for MDVRP

In this section, we propose our solution methodology to solve large-scale MDVRPs that involve the decomposition of the original problem into different CVRP subproblems. This approach aims to determine the optimal decomposition of the MDVRP into subsequent subproblems, where each CVRP instance corresponds to a depot of the main problem. Using an effective decomposition strategy, the desired CVRP subproblems can be obtained and solved using any existing method or solver. As CVRPs have been extensively studied, we do not attempt to develop a novel method for solving them. Instead, we utilize a well-established and validated heuristic solver to arrive at the final solution. An evaluation of all possible decomposition strategies could be computationally intractable. Therefore, we first select a set of random customer assignment strategies and improve them iteratively with a simplified genetic algorithm. Note that evaluating each MDVRP decomposition in the GA with an existing VRP solver is computationally expensive, and it defeats our goal of solving MDVRPs more effectively than the existing methods in the literature. With a supervised deep learning model, we predict the optimal routing cost of a CVRP instance almost instantly without actually solving it.

\text{GANCP}^{+} GANCP start_POSTSUPERSCRIPT + end_POSTSUPERSCRIPT heuristic, such as the genetic algorithm, fitness estimation, and obtaining a final routing solution.

5.1 Genetic Algorithm for MDVRP decomposition

As an evolutionary approach, GAs represent possible solutions as a set of chromosomes that evolve towards optimality through a process of parent selection, crossover, and mutation over multiple generations. To apply GA, each chromosome is encoded as a string of data. We represent each individual as an N 𝑁 N italic_N -length chromosome of depot allocations that corresponds to customers i ∈ { 1 , 2 , … , N } 𝑖 1 2 … 𝑁 i\in\{1,2,\dots,N\} italic_i ∈ { 1 , 2 , … , italic_N } , as depicted in Figure 3 . The customer indices with the same depot allocation d 𝑑 d italic_d are selected to form the CVRP with depot d 𝑑 d italic_d .

Algorithm 1 gives a comprehensive overview of our method, and it begins with the generation of an initial population that consists of multiple MDVRP decompositions. Random assignments of customers to depots generate a diverse initial population, and it ensures that the population starts at a high level of diversity, leading to a larger solution search space over time. Besides this rule, we also initialize two or three potential solutions based on the input graph structure. Our study found that a combination of targeted and random assignments in the initial population results in faster algorithm convergence. One effective targeted assignment strategy is the nearest depot assignment (NDA), where the customers are allocated to their nearest depot. The second strategy is to allocate each customer to the closest neighbor’s nearest depot. These initial assignment rules have been discussed in de Oliveira et al. ( 2016 ) . Additionally, we initialize a chromosome where customers are allocated to their second nearest depot for problems with more than two depots. Targeted assignments serve as an effective initial solution to problems involving uniform customer distribution in a region. Metaheuristics can improve such initial solutions and achieve near-optimal results.

During the solution search, the genetic algorithm may encounter infeasible candidates. While all the infeasible candidates cannot be determined during the cost prediction phase of our heuristic, we can detect candidates with a high degree of infeasibility. For example, a VRP is evidently infeasible if the total demand exceeds the total vehicle capacity. Such individuals are repaired by selecting a random customer from the infeasible CVRP and reassigning them to a depot that can fulfill the corresponding demand, as detailed in Algorithm 2 .

The next generation of the population is propagated using multiple iterations. At each iteration, two distinct parents are selected from the current solution pool based on fitness scores using a K 𝐾 K italic_K tournament selection method. As larger tournament sets select better chromosomes but require more computation and may result in premature convergence, we use the binary tournament selection procedure. To generate children, uniform crossover operations are performed over the selected parents by randomly selecting offspring genes from the corresponding genes of the parents. Our simple chromosome representation requires minimal information about the routing solution, so more sophisticated crossover operations are not necessary. The population size is maintained in the range [ P L , P H ] subscript 𝑃 𝐿 subscript 𝑃 𝐻 [P_{L},P_{H}] [ italic_P start_POSTSUBSCRIPT italic_L end_POSTSUBSCRIPT , italic_P start_POSTSUBSCRIPT italic_H end_POSTSUBSCRIPT ] . Mutations are performed once crossover operations have generated P L subscript 𝑃 𝐿 P_{L} italic_P start_POSTSUBSCRIPT italic_L end_POSTSUBSCRIPT chromosomes for the next generation.

Mutations include the random reset of a customer’s depot called FLIP , and the SWAP operation in which two selected customers’ depots are interchanged. Based on their fitness score, chromosomes in the first tertile are selected for mutation. Approximately 5 % percent 5 5\% 5 % of all customers undergo a mutation, resulting in either a FLIP or SWAP operation with a probability of p m subscript 𝑝 𝑚 p_{m} italic_p start_POSTSUBSCRIPT italic_m end_POSTSUBSCRIPT or 1 − p m 1 subscript 𝑝 𝑚 1-p_{m} 1 - italic_p start_POSTSUBSCRIPT italic_m end_POSTSUBSCRIPT , respectively. Additional targeted mutations are also carried out over 5 % percent 5 5\% 5 % of the child population using a binary tournament selection process. As part of targeted mutations, 10 % percent 10 10\% 10 % of the customers are randomly selected, and the depot allocations of these individuals are copied from one of the elite individuals within the initial population of targeted assignments.

5.2 NN Estimation and Fitness function

A candidate solution generated by the GA should be evaluated using a measure of fitness to guide the population toward the direction of minimum cost. In the MDVRP, the solution cost is simply the sum of the optimal routing costs for its CVRP subproblems. These costs are predicted using the NN prediction model trained with parameters 𝜽 𝜽 {\bm{\theta}} bold_italic_θ . Although our objective is to minimize the routing cost of the main problem, the application of the MDVRP cost directly as a measure of fitness may lead to premature convergence. With a score for the diversity of a solution in the population, in addition to the predicted cost, which measures solution quality, the GA expands its search space and often overcomes local optima. Hence, the fitness of an individual can be determined using the predicted MDVRP cost ( 21 ) and the diversity factor ( 20 ). The diversity factor of a chromosome is measured as the mean Hamming distance of the individual from the rest of the population, as shown in ( 20 ). The fitness score fit ⁢ ( I ) fit 𝐼 \text{fit}(I) fit ( italic_I ) ( 22 ) for a chromosome I 𝐼 I italic_I is calculated as the weighted sum of normalized solution cost C ~ ~ 𝐶 \tilde{C} over~ start_ARG italic_C end_ARG , normalized diversity factor δ ~ ~ 𝛿 \tilde{\delta} over~ start_ARG italic_δ end_ARG , and a penalty for the extent of approximate vehicle capacity violations. Note that l d subscript 𝑙 𝑑 l_{d} italic_l start_POSTSUBSCRIPT italic_d end_POSTSUBSCRIPT , m d subscript 𝑚 𝑑 m_{d} italic_m start_POSTSUBSCRIPT italic_d end_POSTSUBSCRIPT , and Q 𝑄 Q italic_Q represent the total demand, the number of available vehicles, and homogeneous vehicle capacity at the depot d 𝑑 d italic_d , respectively.

Newly generated chromosomes from crossovers and mutations are evaluated in batches to find the MDVRP cost predictions, and duplicate solutions are eliminated before the batch processing. When the CVRP subproblems from multiple chromosomes are processed together with the NN model, the computational time reduces significantly. Following this, fitness scores are calculated for the new generation. According to the fitness scores, a group of P H subscript 𝑃 𝐻 P_{H} italic_P start_POSTSUBSCRIPT italic_H end_POSTSUBSCRIPT individuals are selected and represent the next generation. To prevent wide divergences from our objective, the top 1 % percent 1 1\% 1 % of individuals from each generation is preserved for the subsequent generation. This process is repeated until there is no improvement over multiple generations or up to the desired number of generations.

5.3 Determining the final solution by HGS-CVRP

\text{GANCP}^{+} GANCP start_POSTSUPERSCRIPT + end_POSTSUPERSCRIPT .

6 Computational Study for MDVRP

\text{GANCP}^{+} GANCP start_POSTSUPERSCRIPT + end_POSTSUPERSCRIPT is adapted to minimize the number of Python calls by employing batch estimation of VRP costs. Our code is publicly available at https://github.com/abhaysobhanan/GANCP .

6.1 NN Training

A common approach for training the proposed NN on CVRP data is to randomly distribute customers across a grid. However, we demonstrate that this method is inadequate for accurately predicting the subproblems arising from optimal MDVRP decompositions. To address this, we conduct three distinct training sessions on the proposed NN, each utilizing a different data generation technique, referred to as a phase. In Phase I, the VRP instances are generated following the rules of Uchoa et al. ( 2017 ) with randomly placed depots and customers, where coordinates are integers from a grid of size [ 0 , 1000 ] × [ 0 , 1000 ] 0 1000 0 1000 [0,1000]\times[0,1000] [ 0 , 1000 ] × [ 0 , 1000 ] and demands are integers in the range [ 1 , 100 ] 1 100 [1,100] [ 1 , 100 ] . Phase I follows the common approach discussed above and is effective for estimating the cost of randomly allocating customers to depots. The learning curves for both the training and validation data are illustrated in Figure 4 . While this trained model provides good cost estimates for the initial MDVRP solutions, the prediction error increases significantly as the GA propagates toward optimality. Figure 5 depicts the testing accuracy of Phase-I with an average mean absolute percentage error (MAPE) of 1.06 % percent 1.06 1.06\% 1.06 % , and shows that our NN model outperforms ( 1 ) and ( 2 ) significantly. We choose C = 6.52 𝐶 6.52 C=6.52 italic_C = 6.52 in ( 1 ) to minimize the average error across the test data. Similarly, the regression parameters in ( 2 ) are obtained using the same train data in Phase I.

In Phase II, the VRP subproblem instances are generated from random MDVRP instances to incorporate the near-optimal cases seen during our methodology. 80 % percent 80 80\% 80 % of the training data is generated using the two targeted assignment rules, out of which in 70 % percent 70 70\% 70 % of the instances, exceptions are made to the targeted assignments by randomly reallocating up to 10 % percent 10 10\% 10 % of the customers. The remaining 20 % percent 20 20\% 20 % of the instances follow Phase I data generation. Phase II involves targeted train data based on a partial understanding of our real data distribution. As a result of comparing multiple assignments, MDVRP solutions are better represented, and cost prediction errors are reduced towards optimal decompositions.

In the final training phase, i.e., Phase III, we generate train/validation data in four steps using random MDVRP instances in conjunction with GANCP . In the first step, the NN prediction model is initialized with randomized parameters 𝜽 𝜽 {\bm{\theta}} bold_italic_θ . For an input CVRP, this untrained model is incapable of a fair cost prediction and provides any real number as the output based on 𝜽 𝜽 {\bm{\theta}} bold_italic_θ . Therefore, the final solutions from GANCP are random assignments. Multiple MDVRP instances are utilized to generate CVRP subproblems. After each step, the VRP subproblems generated based on the existing 𝜽 𝜽 {\bm{\theta}} bold_italic_θ are evaluated with the HGS-CVRP solver. This serves as the train data for the NN model, and the parameter values are updated. In the next step, the improved NN model parameters are used in GANCP with random MDVRP instances to generate the new VRP decompositions. This process of NN parameter estimation using partial train data is repeated until the NN model is trained in the fourth step. For each MDVRP evaluation, the top 2 2 2 2 solutions using GANCP are selected to produce the corresponding CVRP subproblems. Each step contributes to the generation of 1 / 4 1 4 1/4 1 / 4 -th of the total train/validation data. At each step, the generated data is used for training in combination with data from previous steps, if applicable. This enhances the capability of the NN model to evaluate the CVRP instances arising from various assignment patterns observed during our heuristic.

6.2 Test instances

\text{GANCP}^{+} GANCP start_POSTSUPERSCRIPT + end_POSTSUPERSCRIPT methodology, 150 150 150 150 MDVRP Test (T) instances are generated in the range N ∈ [ 100 , 1500 ] 𝑁 100 1500 N\in[100,1500] italic_N ∈ [ 100 , 1500 ] and D ∈ [ 2 , 10 ] 𝐷 2 10 D\in[2,10] italic_D ∈ [ 2 , 10 ] . The number of depots for each problem is chosen so that the approximate CVRP subproblem size falls within the range of trained data, i.e., N D ∈ [ 50 , 500 ] 𝑁 𝐷 50 500 \frac{N}{D}\in[50,500] divide start_ARG italic_N end_ARG start_ARG italic_D end_ARG ∈ [ 50 , 500 ] . Instances are generated based on random customer and depot positioning in a grid of size [ 0 , 1000 ] × [ 0 , 1000 ] 0 1000 0 1000 [0,1000]\times[0,1000] [ 0 , 1000 ] × [ 0 , 1000 ] , while demands are integers in the range of [ 1 , 100 ] 1 100 [1,100] [ 1 , 100 ] . The NN models from each phase undergo testing using 20,000 random CVRP instances, and the results are summarized in Table  1 for different problem sizes. The performance gap g H = Predicted Cost − HGS Cost HGS Cost × 100 subscript 𝑔 𝐻 Predicted Cost HGS Cost HGS Cost 100 g_{H}=\frac{\text{Predicted Cost}-\text{HGS Cost}}{\text{HGS Cost}}\times 100 italic_g start_POSTSUBSCRIPT italic_H end_POSTSUBSCRIPT = divide start_ARG Predicted Cost - HGS Cost end_ARG start_ARG HGS Cost end_ARG × 100 is calculated in comparison to the HGS-CVRP solver, and the absolute values | g H | subscript 𝑔 𝐻 |g_{H}| | italic_g start_POSTSUBSCRIPT italic_H end_POSTSUBSCRIPT | are reported to consider both overestimation and underestimation.

\text{GANCP}^{+} GANCP start_POSTSUPERSCRIPT + end_POSTSUPERSCRIPT obtains a better quality solution compared to the benchmark solver. The details regarding the experiments on T instances and the benchmark solver will be discussed subsequently. While Phase I demonstrates strong performance for random CVRP data, the training falls short in incorporating VRPs that arise from the near-optimal MDVRP decompositions. Given that Phase III excels for our MDVRP heuristic, the remaining experiments will focus on the NN model formed using the Phase III parameters, unless stated otherwise. Note that in the event of limited training time availability, Phase II can be used to obtain satisfactory results.

Algorithm Settings

The computational requirements of the HGS-CVRP solver increase as the size of the problem increases. The time limits for the HGS-CVRP solver based on approximate subproblem size, shown in Table 3 , are used to ensure better routing solutions for the top candidates obtained from GANCP . Additionally, the number of CVRP instances that can be processed by the NN model in a batch depends on the memory limitations of the computer. On the specified computer, the batch processing is executed in units as specified in Table 3 to avoid memory overflows.

Benchmark Algorithm

\text{GANCP}^{+} GANCP start_POSTSUPERSCRIPT + end_POSTSUPERSCRIPT performs relatively poorly for the out-of-distribution Cordeau et al. ( 1997 ) instances, with a maximum gap of 4.61 % percent 4.61 4.61\% 4.61 % . The best-known results are also compared with an open-source solver VROOM (Coupey et al., 2023 ) on the same machine running Ubuntu 22.04.1, and the results indicate that VROOM is a competitive solver for the MDVRP instances and yields high-quality solutions within a short time frame. To ensure that the comparison between the benchmark MDVRP solver and the use of our NN model on a GPU is fair, we run VROOM using 16 CPU threads on the same machine for all future experiments. Through the use of multiple CPU threads, we improve the benchmark solver’s computational speed.

\text{GANCP}^{+} GANCP start_POSTSUPERSCRIPT + end_POSTSUPERSCRIPT consistently outperformed NDA with a gap of -1.77%. In the K-Means-10 approach, customers are grouped into D 𝐷 D italic_D clusters based on randomized centroids. After forming the clusters, each one is assigned distinctly to a depot based on the Euclidean distance between the centroids and the depots. This process is repeated 10 times, and the best cost and total time are reported.

\text{GANCP}^{+} GANCP start_POSTSUPERSCRIPT + end_POSTSUPERSCRIPT is 11.4 times faster than VROOM, with an observed performance gap of − 0.39 % percent 0.39 -0.39\% - 0.39 % . With a shorter time limit, VROOM often produces the same solutions as the full run but fails to improve the earlier solutions. NDA yields good quality solutions for the T instances, sometimes even better than VROOM. This is because VROOM, like most solvers, is tailored for medium-sized problems. This is evident from Table 4 and the smallest problem size considered in Table 5 , where the NDA exhibits relatively poor performance. Our GANCP+ framework outperforms NDA without imposing a significant computational time requirement, as compared to VROOM, even for large instances that follow a uniform distribution and seldom exhibit infeasibility issues with the NDA. Note that employing a random clustering approach such as K-Means-10 may result in low-quality solutions.

\text{GANCP}^{+} GANCP start_POSTSUPERSCRIPT + end_POSTSUPERSCRIPT can be enhanced by directly incorporating the NDA solution, if feasible, as a top solution of GANCP. In the subsequent sections, we demonstrate the robustness of our method against data variations, in comparison to VROOM. Additionally, we showcase the transferability of our trained NN model to the CLRP in the appendix.

6.3 Out-of-range Data

We further evaluate the predictive accuracy of our method for MDVRP instances with approximate subproblem sizes that fall outside the range of the trained data. A summary of the results from 50 randomly generated Out-of-range (O) instances with N D ∉ [ 50 , 500 ] 𝑁 𝐷 50 500 \frac{N}{D}\notin[50,500] divide start_ARG italic_N end_ARG start_ARG italic_D end_ARG ∉ [ 50 , 500 ] is presented in Table 7 . The results indicate that our method outperforms VROOM for problems with N ∈ [ 101 , 250 ] 𝑁 101 250 N\in[101,250] italic_N ∈ [ 101 , 250 ] . This is likely due to the model’s exposure to some out-of-range VRP instances during the stepwise training procedure and its ability to learn from them. Our method fails to outperform VROOM for relatively smaller and larger problems in the O instances dataset. Nevertheless, the results can be considered satisfactory due to the relatively small positive gap.

6.4 Out-of-distribution data

The robustness of our method in association with the trained NN model is tested for multiple combinations of coordinates and demand distributions. Uchoa et al. ( 2017 ) uses similar customer positioning and demand distributions to generate a class of VRP benchmark instances. The positioning of customers is determined using three different rules, namely Random (R), Clustered (C), and Random-Clustered (RC), as described in Solomon ( 1987 ) VRPTW instances. In C, a few randomly positioned customers s ∈ UD ⁢ [ 3 , 8 ] 𝑠 UD 3 8 s\in\text{UD}[3,8] italic_s ∈ UD [ 3 , 8 ] act as cluster seeds to attract N − s 𝑁 𝑠 N-s italic_N - italic_s customers with an exponential decay. In RC, half of the customers are randomly positioned, and the remaining are clustered as in C. Two different types of demand distributions such as Unitary (U), where each demand is equal to 1, and Quadrant-Dependent (Q), where demand belongs to UD ⁢ [ 1 , 50 ] UD 1 50 \text{UD}[1,50] UD [ 1 , 50 ] for even quadrant and UD ⁢ [ 51 , 100 ] UD 51 100 \text{UD}[51,100] UD [ 51 , 100 ] for odd quadrant customers, respectively, are considered for evaluation. Our T instances were generated using R customer positioning within the grid and demand from UD ⁢ [ 1 , 100 ] UD 1 100 \text{UD}[1,100] UD [ 1 , 100 ] . Depots are assumed to take a random position on the grid in all cases. Using the above rules, eight classes of out-of-distribution MDVRP instances are generated, as shown in Table 8 .

\text{GANCP}^{+} GANCP start_POSTSUPERSCRIPT + end_POSTSUPERSCRIPT for the eight instance classes, each of different distributions, can be found in Table 9 . Given that our NN model is trained over uniform distributions, the results for out-of-distribution instances are satisfactory, despite the positive performance gap compared to the solver in some cases. A noticeable difference is observed for D4 instances, where customer positioning and demand distribution resemble our T instances with minor modifications. Here, the average result of our heuristics in 10 runs outperforms VROOM. Similarly, the maximum deviation from optimality is visible for instances in class D5 where customer locations are purely clustered, and all demands are assumed to be unitary. Moreover, we still retain a considerable computational advantage for out-of-distribution data, while maintaining the ability to achieve satisfactory results.

\text{GANCP}^{+} GANCP start_POSTSUPERSCRIPT + end_POSTSUPERSCRIPT decreases compared to Table 9 . However, fine-tuning the NN model with partial train data leads to improvements in multiple distribution classes. Remarkably, in all cases, the best cost from 10 experiments improved in comparison to the experiments with pretrained NN parameters. This underscores the potential to enhance the average performance accuracy of our solution framework by incorporating additional data, in the event of a change in data trend.

7 Conclusions

\text{GANCP}^{+} GANCP start_POSTSUPERSCRIPT + end_POSTSUPERSCRIPT . Numerical experiments show that our approach is effective in obtaining good solutions for large-scale data with significant computational advantages in comparison to VROOM, an effective open-source generic VRP solver. We further benchmark our results using simple decision rules that decompose the problem into CVRP subproblems and also discuss the drawbacks of employing such strategies in practice. The accuracy of the prediction model depends on the similarity of training and testing data distributions and problem size. Our experiments on out-of-distribution and out-of-range instances show that the results are satisfactory for practical execution with a significant advantage in computational time. A direct extension of this work is to consider route duration constraints for the MDVRP. Additionally, a supervised learning model can be developed to more accurately detect infeasible solutions, thereby enhancing the performance of our heuristic. The idea of subproblem cost prediction is a promising research direction and can be extended to multiple optimization problems such as the Orienteering Problem, Prize-Collecting VRP, Periodic VRP, VRP with time windows, Split Delivery VRP, and CLRP. We verify this idea by using the existing trained NN model to evaluate the CLRP benchmark datasets. It further validates the transferability of our heuristic and pre-trained NN model for a more generalized hierarchical VRP and still leads to satisfactory results.

Acknowledgement

This research was supported by the Korean government (MSIT) through the National Research Foundation of Korea (NRF) grant RS-2023-00259550. Disclaimer: Any opinions, findings, conclusions, or recommendations expressed in this material are those of the authors.

• Akkerman and Mes (2022) Akkerman, F., M. Mes. 2022. Distance approximation to support customer selection in vehicle routing problems. Annals of Operations Research 1–29.
• Akpunar and Akpinar (2021) Akpunar, Ö. Ş., Ş. Akpinar. 2021. A hybrid adaptive large neighbourhood search algorithm for the capacitated location routing problem. Expert Systems with Applications 168 114304.
• Arnold et al. (2019) Arnold, F., M. Gendreau, K. Sörensen. 2019. Efficiently solving very large-scale routing problems. Computers & operations research 107 32–42.
• Ba et al. (2016) Ba, J. L., J. R. Kiros, G. E. Hinton. 2016. Layer normalization. Advances in NIPS 2016 Deep Learning Symposium . (p. arXiv preprint arXiv:1607.06450).
• Baldacci and Mingozzi (2009) Baldacci, R., A. Mingozzi. 2009. A unified exact method for solving different classes of vehicle routing problems. Mathematical Programming 120 347–380.
• Baldacci et al. (2011) Baldacci, R., A. Mingozzi, R. Wolfler Calvo. 2011. An exact method for the capacitated location-routing problem. Operations Research 59 (5) 1284–1296.
• Banerjee et al. (2022) Banerjee, D., A. L. Erera, A. Toriello. 2022. Fleet sizing and service region partitioning for same-day delivery systems. Transportation Science 56 (5) 1327–1347.
• Barreto (2004) Barreto, S. d. S. 2004. Análise e modelização de problemas de localização-distribuição [analysis and modelling of location-routing problems]. Unpublished doctoral dissertation, University of Aveiro, Campus Universitário de Santiago 3810–193.
• Belenguer et al. (2011) Belenguer, J.-M., E. Benavent, C. Prins, C. Prodhon, R. W. Calvo. 2011. A branch-and-cut method for the capacitated location-routing problem. Computers & Operations Research 38 (6) 931–941.
• Bello et al. (2017) Bello, I., H. Pham, Q. V. Le, M. Norouzi, S. Bengio. 2017. Neural combinatorial optimization with reinforcement learning. 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Workshop Track Proceedings . OpenReview.net. URL https://openreview.net/forum?id=Bk9mxlSFx .
• Bogyrbayeva et al. (2023) Bogyrbayeva, A., T. Yoon, H. Ko, S. Lim, H. Yun, C. Kwon. 2023. A deep reinforcement learning approach for solving the traveling salesman problem with drone. Transportation Research Part C: Emerging Technologies 148 103981.
• CapGemini Research Institute (2019) CapGemini Research Institute. 2019. The last-mile delivery challenge. Tech. rep., CapGemini Research Institute.
• Capital One Shopping Research (2019) Capital One Shopping Research. 2019. Amazon logistics statistics. Tech. rep., Capital One Shopping Research.
• Cappart et al. (2023) Cappart, Q., D. Chételat, E. B. Khalil, A. Lodi, C. Morris, P. Veličković. 2023. Combinatorial optimization and reasoning with graph neural networks. Journal of Machine Learning Research 24 (130) 1–61.
• Contardo et al. (2014) Contardo, C., J.-F. Cordeau, B. Gendron. 2014. An exact algorithm based on cut-and-column generation for the capacitated location-routing problem. INFORMS Journal on Computing 26 (1) 88–102.
• Contardo and Martinelli (2014) Contardo, C., R. Martinelli. 2014. A new exact algorithm for the multi-depot vehicle routing problem under capacity and route length constraints. Discrete Optimization 12 129–146.
• Cordeau et al. (1997) Cordeau, J.-F., M. Gendreau, G. Laporte. 1997. A tabu search heuristic for periodic and multi-depot vehicle routing problems. Networks: An International Journal 30 (2) 105–119.
• Coupey et al. (2023) Coupey, J., J.-M. Nicod, C. Varnier. 2023. VROOM v1.13, Vehicle Routing Open-source Optimization Machine. http://vroom-project.org/ (Last Accessed: October 1, 2023).
• de Oliveira et al. (2016) de Oliveira, F. B., R. Enayatifar, H. J. Sadaei, F. G. Guimarães, J.-Y. Potvin. 2016. A cooperative coevolutionary algorithm for the multi-depot vehicle routing problem. Expert Systems with Applications 43 117–130.
• Ellegood et al. (2015) Ellegood, W. A., J. F. Campbell, J. North. 2015. Continuous approximation models for mixed load school bus routing. Transportation Research Part B: Methodological 77 182–198.
• Figliozzi (2008) Figliozzi, M. A. 2008. Planning approximations to the average length of vehicle routing problems with varying customer demands and routing constraints. Transportation Research Record 2089 (1) 1–8.
• Franceschetti et al. (2017) Franceschetti, A., O. Jabali, G. Laporte. 2017. Continuous approximation models in freight distribution management. Top 25 413–433.
• Furian et al. (2021) Furian, N., M. O’Sullivan, C. Walker, E. Çela. 2021. A machine learning-based branch and price algorithm for a sampled vehicle routing problem. OR Spectrum 43 693–732.
• Garn (2021) Garn, W. 2021. Balanced dynamic multiple travelling salesmen: Algorithms and continuous approximations. Computers & Operations Research 136 105509.
• Ghaffarinasab et al. (2018) Ghaffarinasab, N., T. Van Woensel, S. Minner. 2018. A continuous approximation approach to the planar hub location-routing problem: Modeling and solution algorithms. Computers & Operations Research 100 140–154.
• Golden et al. (1977) Golden, B. L., T. L. Magnanti, H. Q. Nguyen. 1977. Implementing vehicle routing algorithms. Networks 7 (2) 113–148.
• He et al. (2016) He, K., X. Zhang, S. Ren, J. Sun. 2016. Deep residual learning for image recognition. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition . 770–778.
• Kim et al. (2024) Kim, H., J. Park, C. Kwon. 2024. A neural separation algorithm for the rounded capacity inequalities. INFORMS Journal on Computing .
• Kim et al. (2023) Kim, M., J. Park, J. Park. 2023. Learning to CROSS exchange to solve min-max vehicle routing problems. The Eleventh International Conference on Learning Representations . URL https://openreview.net/forum?id=ZcnzsHC10Y .
• Kool et al. (2019) Kool, W., H. van Hoof, M. Welling. 2019. Attention, learn to solve routing problems! International Conference on Learning Representations . URL https://openreview.net/forum?id=ByxBFsRqYm .
• Kou et al. (2023) Kou, S., B. Golden, L. Bertazzi. 2023. An improved model for estimating optimal vrp solution values. Optimization Letters 1–7.
• Kwon et al. (2020) Kwon, Y.-D., J. Choo, B. Kim, I. Yoon, Y. Gwon, S. Min. 2020. Pomo: Policy optimization with multiple optima for reinforcement learning. Advances in Neural Information Processing Systems 33 21188–21198.
• Laporte et al. (1986) Laporte, G., Y. Nobert, D. Arpin. 1986. An exact algorithm for solving a capacitated location-routing problem. Annals of Operations Research 6 291–310.
• Laporte et al. (1988) Laporte, G., Y. Nobert, S. Taillefer. 1988. Solving a family of multi-depot vehicle routing and location-routing problems. Transportation Science 22 (3) 161–172.
• Li et al. (2021) Li, S., Z. Yan, C. Wu. 2021. Learning to delegate for large-scale vehicle routing. Advances in Neural Information Processing Systems 34 26198–26211.
• Lu et al. (2020) Lu, H., X. Zhang, S. Yang. 2020. A learning-based iterative method for solving vehicle routing problems. International Conference on Learning Representations . URL https://openreview.net/forum?id=BJe1334YDH .
• Morabit et al. (2021) Morabit, M., G. Desaulniers, A. Lodi. 2021. Machine-learning–based column selection for column generation. Transportation Science 55 (4) 815–831.
• Nazari et al. (2018) Nazari, M., A. Oroojlooy, L. Snyder, M. Takác. 2018. Reinforcement learning for solving the vehicle routing problem. Advances in Neural Information Processing Systems 31 .
• Nicola et al. (2019) Nicola, D., R. Vetschera, A. Dragomir. 2019. Total distance approximations for routing solutions. Computers & Operations Research 102 67–74.
• Park et al. (2023) Park, J., C. Kwon, J. Park. 2023. Learn to solve the min-max multiple traveling salesmen problem with reinforcement learning. Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems (AAMAS ‘23) . 878–886.
• Qi et al. (2012) Qi, M., W.-H. Lin, N. Li, L. Miao. 2012. A spatiotemporal partitioning approach for large-scale vehicle routing problems with time windows. Transportation Research Part E: Logistics and Transportation Review 48 (1) 248–257.
• Ramos et al. (2020) Ramos, T. R. P., M. I. Gomes, A. P. B. Póvoa. 2020. Multi-depot vehicle routing problem: a comparative study of alternative formulations. International Journal of Logistics Research and Applications 23 (2) 103–120.
• Robust et al. (1990) Robust, F., C. F. Daganzo, R. R. Souleyrette II. 1990. Implementing vehicle routing models. Transportation Research Part B: Methodological 24 (4) 263–286.
• Saberi and Verbas (2012) Saberi, M., İ. Ö. Verbas. 2012. Continuous approximation model for the vehicle routing problem for emissions minimization at the strategic level. Journal of Transportation Engineering 138 (11) 1368–1376.
• Sadati et al. (2021) Sadati, M. E. H., B. Çatay, D. Aksen. 2021. An efficient variable neighborhood search with tabu shaking for a class of multi-depot vehicle routing problems. Computers & Operations Research 133 105269.
• Schneider and Löffler (2019) Schneider, M., M. Löffler. 2019. Large composite neighborhoods for the capacitated location-routing problem. Transportation Science 53 (1) 301–318.
• Solomon (1987) Solomon, M. M. 1987. Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research 35 (2) 254–265.
• Stroh et al. (2022) Stroh, A. M., A. L. Erera, A. Toriello. 2022. Tactical design of same-day delivery systems. Management Science 68 (5) 3444–3463.
• Tuzun and Burke (1999) Tuzun, D., L. I. Burke. 1999. A two-phase tabu search approach to the location routing problem. European Journal of Operational Research 116 (1) 87–99.
• Uchoa et al. (2017) Uchoa, E., D. Pecin, A. Pessoa, M. Poggi, T. Vidal, A. Subramanian. 2017. New benchmark instances for the capacitated vehicle routing problem. European Journal of Operational Research 257 (3) 845–858.
• Varol et al. (2024) Varol, T., O. Ö. Özener, E. Albey. 2024. Neural network estimators for optimal tour lengths of traveling salesperson problem instances with arbitrary node distributions. Transportation Science 58 (1) 45–66.
• Vaswani et al. (2017) Vaswani, A., N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser, I. Polosukhin. 2017. Attention is all you need. Advances in Neural Information Processing Systems 30 .
• Vidal (2022) Vidal, T. 2022. Hybrid genetic search for the CVRP: Open-source implementation and SWAP* neighborhood. Computers & Operations Research 140 105643.
• Vidal et al. (2012) Vidal, T., T. G. Crainic, M. Gendreau, N. Lahrichi, W. Rei. 2012. A hybrid genetic algorithm for multidepot and periodic vehicle routing problems. Operations Research 60 (3) 611–624.
• Vidal et al. (2014) Vidal, T., T. G. Crainic, M. Gendreau, C. Prins. 2014. Implicit depot assignments and rotations in vehicle routing heuristics. European Journal of Operational Research 237 (1) 15–28.
• Vinyals et al. (2015) Vinyals, O., M. Fortunato, N. Jaitly. 2015. Pointer networks. Proceedings of the 28th International Conference on Neural Information Processing Systems-Volume 2 . 2692–2700.
• Wu et al. (2021) Wu, Y., W. Song, Z. Cao, J. Zhang, A. Lim. 2021. Learning improvement heuristics for solving routing problems. IEEE Transactions on Neural Networks and Learning Systems 33 (9) 5057–5069.
• Xu et al. (2020) Xu, K., M. Zhang, J. Li, S. S. Du, K.-i. Kawarabayashi, S. Jegelka. 2020. How neural networks extrapolate: From feedforward to graph neural networks. arXiv preprint arXiv:2009.11848 .
• Zhang et al. (2023) Zhang, K., X. Lin, M. Li. 2023. Graph attention reinforcement learning with flexible matching policies for multi-depot vehicle routing problems. Physica A: Statistical Mechanics and its Applications 128451.
• Zong et al. (2022) Zong, Z., H. Wang, J. Wang, M. Zheng, Y. Li. 2022. Rbg: Hierarchically solving large-scale routing problems in logistic systems via reinforcement learning. Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining . 4648–4658.
• Zou et al. (2022) Zou, Y., H. Wu, Y. Yin, L. Dhamotharan, D. Chen, A. K. Tiwari. 2022. An improved transformer model with multi-head attention and attention to attention for low-carbon multi-depot vehicle routing problem. Annals of Operations Research 1–20.

Appendix A Capacitated Location Routing Problem

We choose the Capacitated Location Routing Problem (CLRP) as an example to demonstrate the applicability of our decomposition heuristic with subproblem cost predictions to other HVRPs. CLRP is a three-level hierarchical optimization problem. It involves opening depots, assigning customers to the opened depots, and making vehicle routing decisions to minimize overall operational costs while fulfilling all customer demands. One can refer to Laporte et al. ( 1986 ) for a mathematical formulation of the CLRP. We consider CLRP instances where the depots and vehicles are capacitated, and opening a depot or a route (vehicle) results in depot/vehicle opening costs. After selecting the depots to open from a set of candidate locations, the CLRP reduces into a variant of the MDVRP. Here, the main difference in the MDVRP variant from our T instances lies in the capacitated depots and the ability to add multiple routes (i.e., utilize more vehicles), each incurring an opening cost.

A.1 Solution Methodology

Since CLRP is a generalization of the MDVRP with additional upper level decisions, the solution methodology for MDVRP can be easily extended to this problem. Our GA for CLRP is extended by modifying the MDVRP chromosome representation to include both depot opening and customer assignment decisions, as shown in Figure 6 . A depot-opening chromosome is a binary vector that indicates whether a depot is open or closed, while the customer allocation chromosome represents the active depot assigned to a customer. For an allocation to be valid, the corresponding depot must be open. Following the GA methodology for MDVRP, each parent is selected using binary tournament selection, and crossovers are applied to the customer allocation chromosome. After determining all customer assignments for a child, only the depots corresponding to the allocated customers are opened on the depot chromosome. A similar approach can be utilized to determine the solution representation after mutations on the customer allocation chromosome. In each generation of the GA, a mutation of targeted customer assignments is performed to the nearest depot or the nearest neighbor’s nearest depot. This applies to approximately 10 % percent 10 10\% 10 % of the candidates determined by tournament selection from the population. Note that since this experiment is a proof of concept for our hierarchical problem-solving approach, we do not explore advanced location searches or mutations.

While the vehicles are capacitated in a CLRP, there is no restriction on the number of vehicles that can be utilized from a depot. Consequently, infeasibility in a CLRP solution may stem not from the vehicle capacity constraints but rather from depot capacity constraints. Similar to the MDVRP methodology, infeasible candidates are repaired with a probability by random assignment to available and open depots. During the initial population generation, we ensure that the open depots can satisfy the total demand for all customers. Each CLRP chromosome is identical to an MDVRP solution once the locations to be opened are determined. CVRP subproblems arising from the solution decompositions can be passed to the NN model in batches to obtain cost predictions. To assess the quality of a CLRP chromosome, subproblem routing costs and diversity scores alone are insufficient. Depot opening costs, an approximate estimate of vehicle opening costs (based on a lower bound on the number of vehicles), total routing cost, and solution diversity are all taken into consideration.

Our computational study focuses on the transferability of the GANCP framework and NN model from MDVRP to the CLRP. Therefore, we use the NN parameter weights from Phase III experiments in determining the solutions to CLRP benchmark datasets. This ensures that our approach is applicable to CLRP without requiring computational effort in training a problem-specific NN model.

A.2 Computational Study for CLRP

Our modified genetic algorithm for CLRP is carried out by using the same set of trained parameters θ 𝜃 \theta italic_θ as in the MDVRP experiments. Note that some local searches, such as random mutations, are not considered in this evaluation of CLRP benchmark datasets. We focus on our main goal of verifying the applicability of decomposition evaluation through cost prediction and therefore do not investigate additional solution improvement strategies for the CLRP. We analyze the performance of our modified heuristic in two popular CLRP benchmark sets, Tuzun and Burke ( 1999 ) and Barreto ( 2004 ) . Tuzun and Burke ( 1999 ) contains 36 36 36 36 instances with N ∈ { 100 , 150 , 200 } 𝑁 100 150 200 N\in\{100,150,200\} italic_N ∈ { 100 , 150 , 200 } customers, D ∈ { 10 , 20 } 𝐷 10 20 D\in\{10,20\} italic_D ∈ { 10 , 20 } uncapacitated depots and capacitated vehicles. Customers are distributed in varying densities, and the clusters are sized differently in these instances. Barreto ( 2004 ) instances are derived from the CVRP instances with up to 150 150 150 150 customers and 10 10 10 10 depots. The route (vehicle) opening costs are ignored in these instances.

\text{GANCP}^{+} GANCP start_POSTSUPERSCRIPT + end_POSTSUPERSCRIPT achieves proven optimal solutions in a few instances.

Appendix B Detailed Results of Computational Experiments