Supervised Permutation Invariant Networks for solving the CVRP with bounded fleet size
Authors: Daniela Thyssens
Jonas Falkner
Lars Schmidt-Thieme
Venue: ICLR 2022 Submitted (2022)
Keywords: Deep Learning
Combinatorial Optimization
Vehicle Routing

Abstract: Learning to solve combinatorial optimization problems, such as the vehicle routing problem, offers great computational advantages over classical operation research solvers and heuristics. The recently developed deep reinforcement learning approaches either improve an initially given solution iteratively or sequentially construct a set of individual tours. 
However, all existing learning-based approaches are not able to work for a fixed number of vehicles and thus bypass the NP-hardness of the original problem. On the other hand, this makes them less suitable for real applications, as many logistic service providers rely on solutions provided for a specific bounded fleet size and cannot accommodate short term changes to the number of vehicles.
In contrast we propose a powerful supervised deep learning framework that constructs a complete tour plan from scratch while respecting an apriori fixed number of vehicles. 
In combination with an efficient post-processing scheme, our supervised approach is not only much faster and easier to train but also achieves competitive results that incorporate the practical aspect of vehicle costs.
In thorough controlled experiments we re-evaluate and compare our method to multiple state-of-the-art approaches where we demonstrate stable performance and shed some light on existent inconsistencies in the experimentation protocols of the related work.

Under review as a conference paper at ICLR 2022
SUPERVISED PERMUTATION INVARIANT NETWORKS FOR SOLVING THE CVRP WITH BOUNDED FLEET SIZE
Anonymous authors Paper under double-bling review
ABSTRACT
Learning to solve combinatorial optimization problems, such as the vehicle rout- ing problem, offers great computational advantages over classical operations re- search solvers and heuristics. The recently developed deep reinforcement learning approaches either improve an initially given solution iteratively or sequentially construct set of individual tours. However, most of the existing learning-basse approaches are not able work for fixed number of vehicles and thus bypass the complex assignment problem of the customers onto an apriori given number of available vehicles. On the other hand, this makes them less suitable for real applications, as many logistic service providers rely on solutions provided for a specific bounded flect size and cannot accommodate short term changes to the number of vehicles. In contrast framework that constructs a complete tour plan from scratch while respecting apriori fixed number of available vehicles. In combination with efficient post-processing scheme, our supervised approach is not only much faster and easier train but also achieves competitive results that incorporate the practical aspect of vehicle costs. In thorough controlled experiments we compare our method to multiple tate-off-hhe-rr approaches where we demonstrate stable performance, while utilizing less vehicles and shed some light on existent inconsistencies in the experimentation protocols of the related work.
propose powerful supervised deep learning
INTRODUCTION
The recent progress in deep learning approaches for solving combinatorial optimization problems (COPs) has shown that specific subclasses of these problems can now be solved efficiently through training a parameterized model on a distribution of problem instances. This has most prominently been demonstrated for the vehicle routing problem (VRP) and its variants (Kool et al. (2019): Chen Tian (2019); Xin et al. (202T). The current leading approaches model the VRP either as local search problem, where an initial solution is iteratively improved or as a sequential construction process successively adding customer nodes to individual tours until a solution achieved. Both types of approaches bypass the implicit bin bin-packing problem that assigns packages (the customers and their demands) to a pre-defined maximum number of bins (the vehicles). We show that this assignment can be learned explicitly while also minimizing the main component of the vehicle routing objective, i.e. the total tour length. Furthermore, finding tour plan for fixed fleet size constitutes an essential requirement in many practical applications. To this end, many small or medium-sized service providers cannot accommodate fleet size adjustments where they require additional drivers on short notice or where very high acquisition costs prohibit the dynamic extension of the fleet. Figure I shows the variation of fleet sizes for different problem sizes. For all problem sizes the baseline approaches (green, red, purple) employ more vehicles than our approach (blue, orange) and thereby inquire potentially more costs by requiring more vehicles. In contrast our vanilla approach (blue) guarantees to solve the respective problems with exactly the apriori available number of vehicles (4, 7, 11 for the VRP20, VRP50, VRP100 respectively) or less. Our approach of learning to construct complete, valid tour plan that assigns all vehicles a set of customers at once has so far not been applied to the VRP. We amend and extend the Permutation Invariant Pooling Model (Kaempfer & Wolf (2018) that has been applied solely to the simpler multiple Traveling Salesmen Problem (mTSP), for which also multiple tours need to be constructed, but are albeit not subject to any capacity constraints.

---

Under review as a conference paper at ICLR 2022
In this work propose end-to-end learning framework that takes customer- coooomeercoordnttss.. their associated demands and the maximal number available vehicles as inputs to output a bounded num- ber of complete tours and show that the model not only learns how optimally conjunct customers and adhere to capacity constraints, but that also outperforms the learning- learning (RI) baselines when taking into account the total routing costs. By adopting full-fledged supervised learning strategy, we contribute the first framework of this kind for the capacitated VRP that is not only faster and less cumbersome train, but also demonstrates that supervised methods are able, in particular under practical circumstances, to outperform state-of of- of-the-art art RL models.
reinforcement
300X
Gare
Gyst
7004
+000
Ter
4000
7eet 204
Flant
VRP with Customers
VRP with Customers
(c) VRP with 100 Customers
Figure 1: Histograms over the fleet sizes used for solving the VRP. Our approach (blue) is able to solve the VRP
with 20, 50, 100 customers with 4, 7 and 11 vehicles respectively, while the baseline approaches (see section 5) utilize considerably more vehicles. Our approach (orange) refers the setting of where ensure solution be found (see section 4.3)
The contributions of this work can be summarized as follows:
Tour-plan construction approach for the capacitated VRP with fixed Vehicle Costs: We propose a deep learning framework that learns to solve the NP-hard capacitated VRP and constructs complete tour-plan for an specified fleet size. In this way it ensures to solve problem for apriori fixed number of vehicles.
Supervised learning for discrete optimization: The proposed approach is the first ML-based construction approach for the VRP that relies entirely on supervised learning output feasible tours for all available vehicles.
Competitiveness: We compare our model against prominent state-of -fe---fftthhrrr- the-art deep learning and OR solvers through thorough and unified experimental evaluation protocol that ensures comparability amongst different MI-based approaches. We show that our approach delivers competitive results in comparison approaches that work only for unbounded fleet sizes and outperforms these methods when considering fixed vehicle costs.
2 RELATED WORK
Learned Construction Heuristics. The work by Vinyall et al. (2015) introducing Pointer Networks (PtrNet) revived the idea of developing end-to-end deep learning methods construct solutions for COPs, particularly for the TSP, by leveraging an encoder-decoder architecture trained in a supervised fashion. Bello al. (0166) and Khalil et al. (2017) proposed RL to train the Pointer Network for the TSP, while Nazari et al. (2018) extended the PtrNet in order to make the model invariant to the order of the input sequence and applied it the CVRP. The Atlention Model (AM) described in Kool et al. (2019) features an attention based encoder-decoder model that follows the Transformer architecture (Vaswaní et al. (2017)) output solution sequences for the TSP and two variants of the CVRP. Xin et al. (2021) extend the AM by replacing the single decoder with multiple, identical decoders with no shared parameters to improve diversity among the generated solutions. Besides these sequential approaches, "heatmap" construction approaches that learn to assign probabilities to given edges in a graph representation through supervised learning have recently been applied to routing problems. Joshi al. (2019) use Graph Convolutional Network to construct TSP tours and show that by utilizing parallelized beam search, auto auto-regressive construction approaches for the TSP can be outperformed. Kool et al. (2021) extend the proposed model by Joshi et al.) (2019) for the CVRP while creating a hybrid approach that initiates partial solutions using a heatmap representation preprocessing step, before training policy to create partial solutions and refining these through
2

---

Under review as a conference paper at ICLR 2022
dynamic programming. Kaempfer & Wolf (018) extend the learned heatmap approach to the number of tours to be constructed; their Permutation Invariant Pooling Nenwork addresses the mTSP (a TSP involving multiple tours but no additional capacity constraints), where feasible solutions are obtained via a beam search and have been proven to outperform a meta-heuristic m'TSP solver.
Learned Search Heuristics. In contrast to construction heuristics that build solutions routing problems from scratch, learned search heuristics utilize well-known local search frameworks com- monly adopted in the field of operations research (OR) learn to improve an initial given solution in an iterative fashion through RL. The NeuRewriter model (Chen & Tian (2019) learns a policy that is composed of rule-picking" and a Tregion-picking part in order to iteratively refine VRP solution and demonstrates superior performance over certain auto-regressive approaches (Nazari et al. 2018); Kool et al. (2019). Similarly, the Learning to Improve approach [L et al. (2020) learns a policy that iteratively selects local search operator to apply to the current solution and delivers new state-of-the thett results amongst existing machine learning heuristics. However, is computationally infeasible during inference in some cases taking more than thirty minutes solve a single instance, which makes this approach incomparable to most other methods. In contrast, attention
Neural Large Neighborhood Search (NLNS) (Hottung & Tierney (2020) is based mechanism and integrates learned OR- OR-typical operators into the search procedure, demonstrating fair balance between solution quality and computational efficiency, but can only be evaluated in batches of thousand instances in order to provide competitive results.
3 PROBLEM FORMULATION
This section introduces the capacitated vehicle routing problem which implicitly encompasses a bin packing problem through finding feasible assignment of customer nodes given set of vehicles. We showcase how existing ML-based approaches circumvent this property and solve a simpler variant of the problem. We then demonstrate how to cast the VRP into supervised machine learning task and finally propose an evaluation metric that respects the utilization of vehicles in terms of fixed vehicle costs.
3.1 THE CAPACITATED VEIIILE ROUTING PROBLEM
Following Baldacci et al. 2 the Capacitated Vehicle Routing Problem (CVRP) can be defined in terms of graph theoretical problem. It involves a graph G = (V, EV,E) with vertex set V = {0, N} and edge set E. Each customer E V. = (1,..., N} has demand y which needs be satisfied and each weighted edge {i.j} E E represents a non-negative travel cost dij. The vertex 0 E V represents the depot. A set M of identical (homogeneous) vehicles with same capacity Q is available at the depot. The general CVRP formulation sets forth that "all available vehicles must be used" (Baldacci et al. (2007 p. 271)) and M cannot be smaller than M corresponding to the minimal fleet size needed to solve the problem. Accordingly, the CVRP consists of finding exactly M simple cycles with minimal total cost corresponding to the sum of edges belonging to the tours substitute to the following constraints: (i) each tour starts and ends at the depot, (ii) each customer is served exactly once and (iii) the sum of customer demands on each tour cannot be larger than Q. A formal mathematical definition of the problem can be found in Appendix
Therefore the solution requires exactly M cycles to be found, which requires in turn the value of M to be set in an apriori fashion. However, already the task of finding a feasible solution with exactly M tours is NP-complete, thus many methods choose to work with an unbounded fleet size (Cordeau (et al. (2007] p. 375)) which guarantees feasible solution by simply increasing M if there are any unvisited customers left. In contrast, our method tackles the difficulty of the assignment problem by jointly learning the optimal sequence of customer nodes and the corresponding optimal allocation of customers to a fixed number of vehicles. In order to do so. we rely on generated near-optimal targets that determine Main for each problem instance in the training set.
3.2 THE VRP AS A SUPERVISED MACHINE LEARNING PROBLEM
The goal of the supervised problem is to find assignment Y that allocates optimally ordered sequences customers to vehicles. Respectively each VRP instance X which defines a single graph theoretical problem, is characterised by the following three entities:
3

---

Under review as a conference paper at ICLR 2022
A set of N customers. Each customer i {1,...,N is represented by the features x!"".
M vehicles, where each vehicle (1, M) characterised by the features xx
The depot, the 0-index of the N customers, is represented by feature vector x dep,
Consequently, a single VRP instance is represented as the set X (xdep; x x (.....) The corresponding ground truth target reflects the near-optimal tour plan and is represented by binary tensor Y MMx XN, where Y Yi.ij if the kth vehicle travels from customer node to customer node j in the solution and else YR,iJ 0.
Let X' represent the predictor space populated by VRP instances X and let y define the target space comprising a population of target instances Y. The proposed model is trained to solve the following assignment problem: Given a sample D E (X x y) from unknown distribution and loss function É ::y> xy + I, find a model ÿ X + y which minimizes the expected loss, i.c.
min (ra)m Ely. ((x))
For sampled predictor set the model 5(x) outputs stochastic adjacency tensor M that consists of the approximate probability distribution defining a tour plan.
3.3 FIXED VEHICLE COSTS
In order to highlight the importance of the assignment problem incorporated in the CVRP and the possible impact of an unlimited fleet sizes real world use cases, we introduce fixed vehicle costs in the evaluation. As mentioned above, problem instance is theoretically always "solvable" in terms of feasibilty by any method that operates on the basis of unbounded fleet sizes. Nevertheless, the increase in the number of tours is undisputedly also a cost driver besides the mere minimization of approaches that not limit the
route lengths. Thus, we compare our approach state-of-the-ar number of tours in more holistic and realistic setting via the metric that we denote Cost,;
Cost, = Σ Yuis + 1 =0 k.i.j
k
where G. the fixed cost per vehicle used, such that if a vehicle leaves the depot, we have Ya,0,0 0, else we indicate that this vehicle remains at the depot with Y kuu. the value of c, we rely on data used in the Fleet Size and Mix VRP in Golden et al. (1984) and find matching values corresponding
Concerning
the capacities used in experimental setting. To this end, incorporate fixed costs of c = 35, G = 50 and c, = 100 for the VRP with 20, 50 and 100 customers respectively summarizing Table can found in Appendix C.2 We want to note that even though the RL baselines are not specifically trained to minimize this more realistic cost function, our model neither, as will be shown section This realistic cost setting functions as mere statistical evaluation metric to showcase the implications of fixed vehicle costs.
PERMUTATION INVARIANT VRP MODEL
The proposed model outputs complete feasible tour-plan for the CVRP in the form of a stochastic adjacency tensor Y. Inspired by the Transformer-based architecture in Kaempfer & Wolf (2018) that tackles the mTSP, we extend this architecture to additionally capture vehicle capacity constraints. The framework encompasses three components: (i) an embedding layer (Encoder), (ii) information extraction mechanism (Pooling) and (iii) an output construction block (Decoder). Figure 2 displays overview of the model architecture.
4

---

Under review as a conference paper at ICLR 2022
4.1
MODEL ARCHITECTURE
Encoder
Information Extraction
Decoder
Filly
E
[Ray ; Aaa
V Ruak"
iincre Projection
Max Pooling Layer
PLegit ge
Ayap
Lx
LayerNorn
Cer; pn Jexiraatonall
layer
AuA
*
100
Come ReLA
LayesNoe
Yuu
Al c gi
Aivi
Y
Figure 2: Permutation Invariant VRP model. Framework overview.
Embedding. The three entities that make up VRP instance X are embedded separately, such that each encoding is embedded into a shared dimensional space dm by a linear projection:
W + bg for g E (dep, cus, veh}
where (1)) E Rlexdm is the initial embedding of each entity that will remain of different lengths leus N, Lveh = M, laep = 1. The separate embedding for each entity and the architecture of relevant for the operations
the network ensure that the order of the elements in the entities performed in the network, which establishes the permutation invariance.
Information Extraction. The information extraction component iteratively pools contexts across entities and linearly transforms these context vectors Cg.l...., Cggl, with the entity embeddings of the current layer hy. For each element
{1....,'g} in entity the contexts are pooled:
! g.r
pool h 9.1 :............................... ....,) (h.
g.f.
for {dep, cus, veh}
(4)
For the next layer's entity representation, the contexts and previous embeddings are linearly projected:
h ((+1) = (( (())) for g E (dep, cus, veh)
(5)
This pooling mechanism proceeds until a final representation of each entity is retrieved; dap A and h hych- These are then passed to the decoding procedure. more detailed description of the operations performed in the Pooling Layer is described in Appendix
Decoder. The decoding step in the model constructs the output tensor Y MxN'' where N' N indicates the size of the full adjacency tensor including the depot. A preliminary step consists of forming feature representation of all edges (potential paths) between all pairs of vertices in the graph, denoted as E':
F = dep cus,
(1.)
1 (T.)
E N' xdm
(6)
E' = [E E i,j 1: N']
E (R
The final construction procedure combines the edge (E') and fleet (V (1)) representations where (L)
each vehicle representation V4 hveh. M enters the combination process twice:
1. In the linear transformation with the edges E', where W, and bias b, are the learned weights and Vi is an expanded version of V& to match the dimensionality of E":
A ReLU(W, [F'; Vi] b.)

---

Under review as a conference paper at ICLR 2022
2. In scaled dot-product which returns compatibility scores for each path potentially travelled by vehicle &o to emphasize a direct interaction between vehicles and convolved edges:
V
Y = softmax
(8)
ddm
Finally a softmax applied transform the compatibility scores of vehicles and edges into probabil- ities Y M XN
4.2 SOLUTION DECODING
In order to transform the stubly-stochastic probability tensor Y into discrete tours in terms of a binary assignment, we use a greedy decoding strategy. training, a aseeudo-greddy decoding (see Appendix C.4) renders potentially infeasible solutions by transforming Y into a binary assignment tensor Y where Y = for the predicted path of vehicle & between vertices and j and 0 otherwise.
Input: Y YER TERMNN'XN' Y E (0,
(0, MX .GERM, Q'ERMUUQQE
Output: Routes Y E (0. (0.1)MMN'xX
1: for i do
2:
if QfQ'= qi < Oss then
3:
M + M +1:
> Add new tour if "guarantee solution" is set Update binary solution tensor Update capacity tensor
4:
YM.... + 0;
5:
Q'u
6:
end
7:
v v arg max (a'xxQQ2 -
D Vehicle with max capacity left b Select all possible vertices for insertion
8:
Va + argselect( (Y; > 0):
9:
Iusfor +- Valarg max (Y vo)li
Assign incoming edge of inserted customer Assign outgoing edge of inserted customer Update Solution Tensor
10:
janer + arg max "iiiiee
11:
Y
+ 0.0;
12:
Y V.eion
+ 1.0
13:
Y Viddiooo
+ 1.0
Le < Qu qi
Update v's capacity after insertion
15:
end for return Y
16:
Algorithm 1: Repair Greedy Solution. q the customer's demand vector, Q' is the vector remaining capacity for all vehicles.
During inference, the pseudo-greedy decoding is substituted by strictly greedy decoding, and thereby accepts only tour-plans, which do not violate the respective capacity constraint. This is done by tracking the remaining capacity all vehicles and masking nodes that would surpass the capacity. Any un-assigned customers violating capacity constraints in the final state of the algorithm recovered in a list U and passed input repair procedure for Y (Algorithm 1). For each unassigned customer in list U, Algorithm [ assigns customer to the vehicle with most remaining capacity and positions the missing customer between Joetore and jatur according to the distribution Y, before updating the predicted binary solution tensor Y and the remaining capacity Q' accordingly.
4.3 INFERENCE SOLUTION
Unfortunately the repair operation of Algorithm leads a situation where the resulting tours during inference are not necessarily local optima anymore. To improve these tours we add heuristic post processing procedure doing several iterations local search via the google OR-tools solver (Perron & Furnon ).19)) Given valid solution for particular number of vehicles, the solver runs (potentially lime-limited) search that improves the initial solution Y During inference, the method optionally can relax the bound on the fleet size to guarantee to find solution which important in cases where instances are particularly difficult to solve due very tight bound capacity.

---

Under review as a conference paper at ICLR 2022
This is done by initially adding artificial tour to the plan for the remaining missing customers before running the post-processing scheme. Thus, this mechanism enables our method to also solve instances it is not initially trained for to provide maximum flexibility.
4.4 TRAINING THE PERMUTATION INVARIANT VRP MODEL
In order to train our model to learn the assignment of customer nodes to the available vehicles and adhere to capacity constraints, we extend the original negative log-likelihood loss by penalty formulation (Lover) and auxiliary load loss, controlled via weights dover and Ctjoad
The model's characteristic of permutation invariance induces the necessity for the training loss to be agnostic to the vehicle-order as well the travel direction of the tours. Concerning the route-direction, we denote k,i.j = YK,i,J and E = Yyj., Therefore, the loss to be minimized is the minimum (penalized) normalized negative log-likelihood of Y with respect the sampled target Y:
((Y) := min n. bE (0.1)
You (()),
log Ya.ds + aoad Iload (Yk...) (ooad(==()))) (9)
k=1
+,==0
Lover (load FR....)
with the load of tour T Y Yk... 10,1)
N'
load(T) (T) =
Σ 1/=0
TT
(10)
and shifted quadratic emror for overloading
0, (1+9 Q)2,
if S Q
Topeer (4)
(11)
else
The calculation of the loss formulation in Equation 9 would induce considerable computational overhead, therefore a less memory-intensive formulation of the same loss implemented (see Appendix C.5). The extensions to the original Permutation Invariant Pooling Network are summarized in Appendix C.6
5 EXPERIMENTS
In the following experiments we want to showcase and validate our main contributions:
Our method works for problems with bounded fleet sizes and outperforms state-of-the-art RL models when accounting for fixed vehicle costs.
2.
Our supervised learning model is fast to train and delivers competitive results in comparison to the state-of-the-arr, while utilizing considerably less vehicles.
We consider three different problem sizes, with 20, 50 and 100 customer vertices respectively and generate solvable training instances following a rejection-sampled version of the data generating process in Kool et al.) 2019)) The near-optimal target instances are generated with google's oo-ls guided local search solver (Perron & Furnon (211)). where we set M = 4, 7, 11 and Q = 30, 40, 50 for each problem size respectively. In total we generate roughly 100,000 training samples per problem size. The hyperparameter settings are described in Appendix D.1] For the evaluation, we work with two versions of the test dataset in Kool et al. (2019), the originally provided one and a rejection sampled version of it, as technically our model is trained to solve only the instances for which the lower bound Σien q: < .MQ holds. We compare our model to recent RL methods that comprise leading autoregressive (AM (Kool al. (201)), MDAM (Xin al. (202 ) well as search based (NLNS (Hottung & Tierney (2020)) approaches. The NeurRewriter (Chen & Tian (2019)) and L2I re-evaluated due extensive training- and inference times. Details
model (Lu et al. (2020))
7

---

Under review as a conference paper at ICLR 2022
concerning the re-evaluated (and not re-evaluated baselines found in Appendix D.2 Furthermore, we revisit different published results in a per-instance re-evaluation to elevate comparability and demonstrate strengths and weaknesses of the methods. We note that most methods were originally evaluated in a per-batch fashion where they can leverage the massive parallelization capabilities of current graphical processing units, while that setting is of less practical relevance.
5.1 FIXED VEHICLE COSTS
To validate the first point of our main contribution. we evaluate the performance of different RL methods and our own model on the metric defined in Equation [] Table ! shows the results for evaluating the methods on the total tour length (Cost), as well as the measure incorporating fixed costs for each vehicle (Cost.). The results in Table shows that method outperforms state-of-the-an
Table 1: Results for different learning-basee based models on 10000 rejection sampled VRP Test. Instances. Cost including fixed vehicle costs (Cost,) ) and without (Cost) is reported. Regarding the percentage of solved instances we achieve 99%, 99.5% and 100% coverage for the problem sizes 20, 50 and 100 respectively.
VRP20
VRP50
VRPI00
Model
Cost
Cost,
t/inst
Cost
Cost,
t/inst
Cost
Cost,
t/inst
NLNS
6.22
145.0
1.21s
10.95
367.3
2.01s
17.18
913.3
3.02s
AM (greedy)
6.33
147.4
0.04s
10.90
357.0
0.12s
16.68
888,4
0.22s
AM (sampl.)
6.18
143.7
0.05s
10.54
352.2
0.19s
16.12
873.4
0.57s
MDAM (greedy)
6.21
147.3
0.46s
10.80
370.40
1.08s
16.81
961.3
2.02s
MDAM (bm30)
6.17
140.3
5.06s
10.46
351.66
9.00s
16.18
889.1
16.58s
Ours
6.16
135.5
0.05s
10.76
346.1
0.16s
16.93
859.6
0.84s
Ours
6.17
136.0
0.05s
10.77
346.1
0.16s
16.93
859.6
0.84s
(**)
With the option of guaranteed solution
RL methods the VRP with fixed vehicle costs across all sizes of the problem and even outperforms them on the plain total tour length minimization cost for the VRP with 20 customers, while delivering the shortest inference times per instance together with the AM Model. Furthermore, our method's results do not greatly differ whether we set the option of guaranteeing a solution (last row) to True versus accepting that there are unsolved samples, speaking for the strength of model for being able to solve both problems incorporated in the VRP at once, the feasible assignment problem to a particular number vehicles and the minimization of the total tour length. This is also represented in Figure [ while the amount of solutions solved with more than the apriori fixed fleet size is vanishingly small for the VRP20 and VRP50 is exactly for the VRP100. For the VRP of size 50 the RL-based methods only outperform our greedily evaluated method on the routing length minimization when employing sampling or a beam search during inference, while being worse when used greedily. Concerning the problem with 100 customers, on the vanilla total route length cost, but solves the majority of the problems with a significantly smaller fleet size, reflected by the considerably smaller total costs (Cost,). This is strongly supported by Figure I where we see that especially for the VRP with 100 customers, the RL-based methods consistently require more vehicles than needed.
method is outperformed by the RL approaches
5.2 COMPARATIVE RESULTS ON THE BENCHMARK DATASET
We want to assess the competitiveness of our method also on the literature's bench-marking test set provided in Kool et al. (2019). Technically, these instances are not all solvable by our model, as is not trained to solve problems where Σign qi S MQQ In Table 2 we therefore indicate the percentage of solved instances by our plain model in brackets. Looking at Table our method's 's performance is generally on par with or slightly better than RL-based construction methods when employing a greedy decoding. Concerning the per-instance run times, MDAM and the NLNS take orders of magnitude longer than the AM model and our method. We acknowledge that exploiting parallelism to enhance computational efficiency is a justified methodological choice, but in terms of comparability, argue for the pragmatic approach of comparing per-instance runtimes to remedy problematic comparison of models using different architectures and mini batch sizes. For completeness Table in Appendix DD3 illustrates the per-batch evaluation of the baselines. Appendix D.2 discusses
8

---

Under review as a conference paper at ICLR 2022
the discrepancies in performances of NLNS and MDAM with respect to their published results. Even though the solution quality and competitiveness of our method decrease when considering larger problem sizes, the per-instance inference time remains among the best. Nevertheless, want to emphasize that the baselines in general require more tours than our method potentially leading to higher costs when employed in real-world scenarios.
Table 2: Results for different ML and OR Models on 10000 VRP Test Instances Kool et al. 2019
VRP20
VRP50
VRPI00
Model
Cost
Cost
Cost
Gurobi
6.10
LKH3
6.14
2h
10.38
7h
15.65
13h
Cost
t/inst
Cost
t/inst
Cost
t/inst
NLNS (1-limit)
6.24
2.41s
10.96
2.41s
17.72
2.02s
AM (greedy)
6.40
0.04s
10.98
0.09s
16.80
0.17s
AM (sampl.)
6.25
0.05s
10.62
0.17s
16.20
0.51s
MDAM (greedy)
6,28
0.46s
10.88
1.10s
16.89
2.00s
MDAM (bm30)
6.15
5.06s
10.54
9.00s
16.26
16.56s
Ours
6.18
(94%*)
0.05s
10.81
(94%*)
0.16s
16.98
(98%*)
0.82s
Ours **
6.24
0.05s
10.87
0.17s
17.02
0.82s
Percentage solved instances, (**) With option guaranteed solution
5.3 TRAINING TIMES
We showcase the fast training of our model against the NeuRewriter model (Chen & Tian (019)) as a representative for RL methods. Table shows the results from runs A100-SXM4 machine with 40GB GPU RAM. To train the NeuRewriter for the VRP50 and VRPI00 with the proposed batch size of 64, 40GB GPU RAM are not sufficient. Instead, used a batch size of 32 and 16 respectively, where the total runtime estimated for completing 10 epochs. Accounting for our dataset generation, note that with Xeon Gold 6230 CPU cores, takes roughly 11 days generate one dataset. That said, we emphasize that the OR Tools is straightforwardly parallelizable (emberrassingly parallel!), such that doubling the amount of cores, roughly halves the runtime.
Table 3: Training Times Epoch and Total Train Time of NeuRewriter (Chen & Tian 2019) and our Model
VRP20
VRP50
VRP100
t/epoch
t/epoch
t/epoch
t
NeuRewriter
15h
6d
> 31h
13d
36h
> 15d
Ours
4m
5.4m
4.5h
1.5d
6 CONCLUSION AND FUTURE WORK
With the proposed supervised approach for solving the VRP. we investigate a new road to tackle routing problems with machine learning that comes with the benefit of being fast to train and which is able to produce feasible solutions for apriori fixed fleet size. We show that our model is able to jointly learn to solve the VRP assignment problem and the route length minimization. Our work focuses on and showcases practical aspects for solving the VRP that are important for decision makers in the planning industry and shows that our method outperforms existing models when accounting for fixed vehicle costs. In future work, we aim to alleviate the computational shorteomings of the train loss calculation, such that the model's fast training capability can be extended to problems with larger fleet sizes.

---

Under review as a conference paper at ICLR 2022
7 REPRODUCIBILITY STATEMENT
Considering the current pace at which new approaches and methods are emerging, not only but also for the research area of learning based combinatorial optimization, fast and easy access to source codes with rigorous documentation needs to be established in order to ensure comparability and verified state-of-the-ard
To this end, we will provide the code for our fast supervised learning method on a github repository, which will be publicly available. During the review process, the code will be made available to he reviewers. On a broader scope, since the findings in this paper comprise not only results, but also those of re-evaluated existing approaches in the field, we plan to develop benchmark suite on learning- aaaning-based routing methods for which the re-evaluations and produced codes will build the basis for.
REFERENCES
Roberto Baldacci, Paolo Toth, and Daniele Vigo, Recent advances vehicle routing exact algorithms. 4OR, 5(4):269-296 2007.
Irwan Bello, Hieu Pham, Quoe V Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforcement learning. arXiv preprint arXiv:1611.09940 2016.
Xinyun Chen and Yuandong Tian. Learning to perform local rewriting for combinatorial optimization. In Advances in Neural Information Processing Systems, pp. 6278-678722 6289,,29,440 2019.
Jean-François Cordeau, Gilbert Laporte, Martin WP Savelsbergh, and Daniele Vigo. Vehicle routing. Hlnndbooks in operations research and management science, 14:367-428, 2007.
Bruce Golden, Arjang Assad, Larry Levy, and Filip Gheysens. The fleet size and mix vehicle routing problem. Computers Operations Research, 11(1):99-6,, 1984.
André Hottung and Kevin Tierney. Neural large neighborhood search for the capacitated vehicle routing problem. In ECAI 2020, pp. 443-450. IOS Press, 2020.
Chaitanya K Joshi, Thomas Laurent, and Xavier Bresson. An efficient graph convolutional network technique for the travelling salesman problem. arXiv preprint wrXiv:1906.01227, 2019.
Yoav Kaempfer and Lior Wolf. Learning the multiple traveling salesmen problem with permutation invariant pooling networks. arXiv preprint arXiv: 09621, 2018.
Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. Advances in Neural Information Processing Systems, pp. 2017.
Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint arXiv:1412.69880 2014.
Wouter Kool, Herke van Hoof, and Max Welling. Attention, learn to solve routing problems! In International Conference Learning Representutions, 2019,
Wouter Kool, Herke van Hoof, Joaquim Gromicho, and Max Welling. Deep policy dynamic program- ming for vehicle routing problems. arXiv preprini 1rXiv:2102.11756 2021.
Gilbert Laporte, Yves Nobert, and Martin Desrochers. Optimal routing under capacity and distance restrictions. Operations research, 33(5): 1050-1330 1985.
Hao Lu, Xingwen Zhang, and Shuang Yang. learning-based iterative method for solving vehicle routing problems. In International Conference Learning Representations, 2020. URL https:
//openreview. net. fttee///foommmddddeeee
Mohammadreza Nazari, Afshin Oroojlooy, Lawrence Snyder, and Martin Takác. Reinforcement learning for solving the vehicle routing problem. In Advances in Neural Information Processing Systems, pp. 9839-9849, 2018.
10

---

Under review as a conference paper at ICLR 2022
Laurent Perron and Vincent Furnon. Or-tools, 2019. URL [tt_:ttt/////eeelpasss.ooo//
com/opt imtiiiitionn
Eduardo Uchoa, Diego Pecin, Artur Pessoa, Marcus Poggi. Thibaut Vidal, and Anand Subramanian. New benchmark instances for the capacitated vehicle routing problem. European Journal of Operational Research, 257(3):845-58)) 2017.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pp. 5998-6008. 2017.
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. In Advances in neural information processing systems, pp. 2692-2700, 2015.
Liang Xin, Wen Song, Zhiguang Cao, and Jie Zhang. Multi-decoder attention model with embedding glimpse for solving vehicle routing problems. In Proceedings of 35th AAAI Conference on Artificial Intelligence, 2021.
A FORMAL DEFINITIONS
A.1 MATHEMATICAL FORMULATION OF THE CVRP
Following the notation in section 3.1 of the paper, the CVRP can be formalized the following two-index vehicle flow formulation, first introduced by Laporte et al. (1985):
Given binary decision variable Fij taking either value of or 0 V(i,j} E ((0,5) i V.)
where Σi = 1 if the path {i.j} is traversed and Toj = 2 a tour including the customer j is selected in the solution, solve the following integer program:
min
Σ dijTij
(12a)
(iJEE
s.t.
Σ
Fij Tif= = (Ah E Vo)
(12b)
(i.))
Σ
Fiy 2 2(q(S)/QI (VSE
(12c)
((())
Σ Doj 2M
(12d)
JEV.
Tij E [0,1] (V(i,) E E (10,5) i vV))
(12e)
Toj E (0, (V(0,j),jE V.))
(12f)
where subset of customers is denoted by S Ve, 8(S) = [i,j} E E: 5.j S or S.j e
the cutset defined by S and y {S: S S C Va, |S] 2 2).
Equations 12b) lists the degree constraints. Equation 12c) indicates that for any subset S of
customers, excluding the depot, at least [q) vehicles enter and leave it. Constraint (12d) ensures that M vehicles leave and return to the depot. Equations 12eb and (12 constitute the integrality constraints.
A.2 BIN PACKING PROBLEM
The Bin Packing Problem can be formulated in words as follows:
Given a set of n items {1...., n), where wy is the weight of the item j E {1...., n) and bins, each with capacity C. Assign each item to one bin that:
The total weight of items in each bin does not exceed C
11

---

Under review as a conference paper at ICLR 2022
The total number of utilized bins is minimized.
In mathematical terms, this results in solving the following minimization problem, where Taj {0, 1] equal if item j assigned bin and 2 E {0, 1) is equal to bin is used:
min
2/
(13a)
s.t.
Σ Wjzij S Czi i= I,...,
(13b)
Σ Pij =1, j 1 ,...,
(13c)
2ij E {0,1) i= 1=.....,
(13d)
2, E {0,1} i= 1=1....,
(13e)
B ABLATIONS
This section demonstrates that the changes in our approach and notably to the loss structure of the approach. compared to the original model in Kaempfer & Wolf 2018). are improving the model's performance and efficiency. The results summarized in Table 2 and are retrieved form an evaluation on the rejection sampled Kool et al. Dataset with the option of guaranteed solution.
B.1 ADDITIONAL LOss STRUCTURES
This section demonstrates that the additional loss structures (Penalty and auxiliary Load Loss) imposed on the pure assignment Loss help reduce the capacity violation during training and guide the model towards better performance. The right hand side of Figure shows that with the two additional loss structures, the model achieves an average capacity violation of 0.017 per vehicle, while the model, when trained with the plain assignment loss, still exhibit an average capacity violation of 0.021 and even starts increasing again after 40 epochs. While an average capacity violation of 0.017 per vehicle, still means that the model cannot control the capacity constraint to a hundred percent, this still significantly helps the Repair Algorithm to generate feasible solutions.
and Voliation Losa ever Eaceta
Capabcile over Epecto Truining
sity
0626
Pask
Loss
VRP20
Cost
Cost,
Plain
6.19
135,9
Penalty
6.18
135.8
25
Ours 6.17
135.5
Figure 3 Table Ablation on the different Loss Structures Imposed on Model.
The left sub-figure illustrates the train (solid line) and validation (dashed line) losses over epochs across the three loss configurations for the VRP with 20 customers; "Plain", i.e. no additional loss structures (green), "Penalty" (blue) and both "Penalty" and Load Loss structures (red). The right sub-figure displays the average capacity constraint violation vehicles as training proceeds. Table
The loss functions the left hand side of Figure show that the losses including the auxiliary loss structures are overall higher, but can exhibit a higher delta between starting losses and final losses, which translates in better performance illustrated in Table 5.
12

---

Under review as a conference paper at ICLR 2022
B.2 SOFT-ASSIGN LAYER
In this section we want to demonstrate the empirical findings that a simple Sofumax Normalization function competitive the SoftAssign Score Normalization Algorithm by Kaempfer Wolf
(2018).
Table 5: Comparison of Score Normalization Techniques
Score Normalization
VRP20
VRP50
Cost
Cost,
t/inst
Cost
Cost,
t/inst
SoftAssign
6.23
135.5
0.057s
10.85
346.3
0.241s
Softmax
6.17
135.5
0.050s
10.77
346.1
0.170s
B.3 GENERALIZATION
This section documents how the supervised VRP models trained on graph sizes of 20, 50 and 100 generalize to the respective other problem sizes, as well as to more realistic problem instances (Uchoal00) 00) published in Kool al. (202T) that are generated for graph-sizes of 100 following the data distribution documented in Uchoa et al. (2017). The underlying dataset in Table 6 is the rejection-sampled version of the dataset used Kool et al. (2019).
Table 6: Generalization Ability of the Permutation Invariant VRP Model
Training Distribution
VRP20
VRP50
VRP100
Uchoa100
Cost
Cost,
Cost
Cost,
Cost
Cost,
Cost
Cost.
VRP20
6.16
135.5
11.06
344.8
17.33
858.2
19.68
904.1
VRP50
6.28
136.3
10.76
346.1
16.85
860.2
19.41
897.5
VRP100
6.31
136.0
11.04
345.5
16.93
859.6
19.42
896.6
Table 6 shows that in general and as expected, the models trained on particular distribution perform best with regards to the objective cost, when tested on the same distribution.
B.4 TARGET SOLUTIONS
In this section we provide additional head-to-head comparative results against the underlying target- generating method OR Tools (Perron & Furnon (2019)). The results are generated on the rejection sampled version of the Test-set used in Kool et (2019). We compare the OR- To-Tosls method with results that guarantee solution be found and set the search limit for OR-Tools Guided Local Search (GLS) to 10 seconds.
It is worth mentioning that with the indicated setting of the GLS, for 18, 7 and of the test instance, for the VRP20, VRP50 and VRPI00 no solution could be found.
Table 7: Comparison to Target-generating Method OR- OR-Tools rejection-samples datasets
VRP20
VRP50
VRP100
Cost
Cost,
t/ t/inst
Cost
Cost,
t/inst
Cost
Cost,
t/inst
Ours
6.17
135,5
0.05s
10.77
346.1
0.16s
16.93
859.6
0.84s
OR-Tools
6.06
1
8.00s
10.64
345.6
10.00s
16.40
855.3
12.00s
13

---

Under review as a conference paper at ICLR 2022
B.5 EFFECTIVENESS POST-PROCESSING
The Table compares the effects of post-processing both our model and the AM baseline model. The AM model is chosen as for this baseline, the resulting tours for each of the test instances can be easily retrieved and hence the postprocessing scheme be on top of those initially retrieved tours. However, we note that the additional post-processing procedure took an additional 3.5 minutes for the VRP20, 20 minutes for the VRP50 and hour for the VRPI00 in terms of runtime.
Table 8: Comparison of models with and without Postprocessing
Method
VRP20
VRP50
VRPI00
Cost
Cost,
Cost
Cost,
Cost
Cost,
Without Postprocessing
Ours AM (greedy)
6.52
141.0
12.28
360.0
23.89
893.0
6.33
147.4
10.90
357.0
16.68
888.4
With Postprocessing
Ours AM (greedy)
6.17
135.5
10.77
346.1
16.93
859.6
6.17
140.9
10.62
347.0
16.68
859.0
B.6 DECODING PROCEDURE COMPARISON TO KAEMPFER & WOLF (2018)
The most effective methodological contribution is the decoding process of solutions. In this section, we provide comparative results to the original decoding procedure in Kaempfer & Wolf (2018). Kaempfer & Wolf (2018) employ the "SoftAssign" normalization (mentioned in sub-section B.2) to obtain the probability distribution of tours and decode the discrete tours by Backtracking or "Beam Search" procedure. In contrast the Beam Search procedure we decode the solution greedily followed by repair operation and final postprocessing scheme.
Table shows that the Beams Search decoding in Kaempfer & Woll (2118), even though originally employed to solve the mTSP, is not capable of finding valid VRP solutions reliably. A simple greedy decoding followed by the proposed repair procedure increases the percentage of solved instances already by roughly 30%.
Table 9: Comparison of the original (mTSP) Decoding procedure in Kaempfer & Wolf 2018) (SoftAssign + Beam Search) and our algorithmic repaired greedy decoding (Repaired Greedy + Postprocessing) for the VRP with 20 nodes. "Beam Search 20" and "Beam Search 200" refer the size of the heam, which is equal to 20 and 200 respectively. The test dataset evaluated on, the eejection-samplee VRP20 dataset.
Decoding Procedure
Cost
Percentage solved
Time
SoftAssign + Beam Search 20
7.42
42.34%
11min 15min
SoftAssign + Beam Search 200
7.25
69.00%
Repaired Greedy Repaired Greedy + Postproc.
6.52
99%
8.0min
6.17
99 %
8.3min
C METHODOLOGICAL DETAILS
C.I ENTITY ENCODING
VRP instance X, which defines a single graph theoretical problem, is characterised by the following three entities:
14

---

Under review as a conference paper at ICLR 2022
A set of N customers. Each customer i, E {1,...,] NY has demand qi be satisfied and is represented by a feature vector x; which consists its two-dimensional coordinates and the normalized demand q.QQ.
A collection of M vehicles, each vehicle k E f1.... M) disposing a capacity Q and characterised by the features x The corresponding feature vector incorporates local (1/k) and global (k) numbering. capacity Q and the aggregated load that must be distributed.
The depot node at the O-index the N customer vertices which is represented by a feature vector x comprising the depot coordinates well as centrality measure indicating the relative positioning of the depot w.r.t. the customer locations.
C.2 VEHICLE COSTS
Concerning the vehicle costs, Table 10 summarizes the different fixed costs, while accounting for the different vehicles capacities.
Table 10: Fixed Vehicle Costs
Problem Size (N)
Vehicle
Capacity (Q)
Cost (c,)
20
30
35
50
40
50
100
C
50
80
In real-world use cases it is indeed justified that larger vehicles, disposing more capacity, also inquire more costs if we assume that not only buying or leasing these vehicles plays a role, but also the required space (e.g. adequate garage) maintenance costs.
C.3 LEAVE-ONE-OUT POOLING
The max-pooling operation on the hand enforces the interaction of learnable information between entities and on the other hand mitigates self- pooling, i.e, each entity element's 's context vector consists only of other inter- and intra-group information, but its own information. When the contexts be pooled for element r E (1...., (g) stem from its own entity, the leave-one-out pooling is performed the Max Pooling Layer:
( 9i
phol(h (1) 9.1 g.r-11 g.r41
1,000
(1)
)gd,)) for E (dep, cus, veh)
(14)
are pooled from another entity of (g) ......,))))) When on the other hand, the contexts for element r (1...., that does not belong to, regular pooling is performed:
of 3 = pool
(1 (.,)) for g E (dep, cus, veh}
(15)
C.4 PSEUDO-GREEDY DECODING
The pseudo-greedy decoding described section 4.2 transforms the doubly-stochastic probability tensor Y into binary assignment tensor Y from which the predicted vehicle loads (required for the train loss) can be deduced. Algorithm below shows the decoding procedure.
15

---

Under review as a conference paper at ICLR 2022
Input: Y RM
Output: Y E (0. 1)MxX'X'
1: Y + +00 [0)MXN'N XN
Initialize Y Create copy of Y for masking P. Assign "Erom-depot" customer for vehicle Fill Y with the assigned start path b Mask assigned path for all vehicles
2: F copyyY);
3: for l M do
4: Rourr <- arg max Y Y.:
5:
Y, +- 1.0;
6:
Y Kaddaa -00
7:
while toum # 0
8:
Enest c arg max YE (ooomn))
Select cutgeing node from derr b Fill Y with the assigned path D Mask assigned path for all vehicles Reset "to depot" paths to original probabilities
9:
Yi Ykikmm
1.0;
10:
Y
Safta -00
11:
Y 1.,0 :..0
12:
Rcurr <- Peest
b Reset index
13:
end while
14:
end for
return Y
Algorithm 2: secudo-greedy Decoding
First the predicted binary assignment is initialised and copy of the original probability tensor is created that can be used to mask the already visited customer nodes across vehicles and outgoing flows. After the starting customer of a vehicle is determined (feur) and stored the output tensor Y we loop through vehicle k's path until the reset current vertex is again the depot, i.e. éeur = This is successively done for all vehicles and in batches of training instances, such that the algorithm proceeds reasonably fast.
C.5 TRAIN LOSS
N
Lk
min (0011)
log YE.R Y + O L (load Y
(16)
In second step, after the optimal route direction has been determined, the vehicle permutation that renders the minimal loss is determined:
L min
LR,T(K) + Oltoad Y) -load Y (.)....))
(17)
C.6 DELINEATION FROM THE PERMUTATION INVARIANT POOLING NETWORK
There five main components of the original Permutation Invariant Pooling Network that were extended considerably;
The encodings extentended; The customer entity is complemented by their demands, the depot encoding captures now the relative centrality of its location and the fleet encoding is enriched by the total demand be distributed.
Priming weights for the depot and customer groups in the pooling mechanism have been extended to incorporate outer sum of demands in conjunction with the distance matrix to reflect that not only locations but also the demands of customers plays role.
Most changes were introduced in the decoding process. Instead of layering two simple ID convolutions, we introduce an attention dot product enhance the interaction of each vehicle and the edges to be allocated.
The SoftAssign layers introduced by Kaempfer & Wolf (018) seemed to be not as expres- sive initially intended. Empirically we show in the experiments that even though the SoftAssign layers are technically effective, the same result can be achieved with a simple softmax normalization instead.
16

---

Under review as a conference paper at ICLR 2022
Lastly amended the loss for training the model in order to train the model also to learn feasible assignments of customers on to the tours.
D EXPERIMENT DETAILS
D.1 HYPERPARAMETERS
The embedding size dm the hidden dimension of the shared fully-connected layer and the number of pooling layers I. is set to 256, 1024 and 8 respectively for the problem sizes of 20 and 50, due to GPU memory constraints we dm 128 for the problem size of 100. The model is trained in roughly 60 epochs with batch size of 128, 64 and 64 for the problem sizes 20, 50 and 100 respectively, using the Adam Optimizer (Kingma & Ba (2014) with learning rate of 10-4.
D.2 NOTE ON BASELINE RE-EVALUATION
We want to note some particularities across the re-evaluations to accompany the findings in Table 2. First we note that the MDAM Model (Xin et al. (202T)) did not yield the same performances when evaluated in batches of thousand instances and in single-instance based setting. This is due to the fact that the authors decided to evaluate their model in "training" mode during inference and consequently carried over batch-wise normalization effect Albeit, this might signal wanted transductive effects during inference, we found it more appropriate to document the results without transduction effects, as also the incorporation of these effects were not states in the publication. Concerning the NeuRewriter model (Chen & Tian (019)) we only provide published results without the per-instance re-evaluation in Table[1] because even though we retrained the model according to the information in their supplementary materials, we were not able to reproduce the published results in a tractable amount of time. In order to re-evaluate the NLNS (Hottung & Tierney (2020)) and reproduce the published results, a GPU-backed machine with least 10 processing cores was needed (as was indicated and confirmed by the authors). For the per- per-instance evaluations, we employed the batch-evaluation version of NLNS while setting the batch size 2. The provided single instance evaluation method in Hottung & Tierney (2020) would require 191 seconds per instance, which again would be intractable to reproduce for the given test set of 10,000 instances. The 1.21 approach (Lu et al. (020)) was not considered in this comparison as a single instance for the VRP100 requires 24 minutes (Tesla T4), which would lead
total runtime of more than 160 days for the complete test set. Generally, the re-evaluation of the baseline models and the evaluation of our own approach were done on Tesla P100 or V100 machine (except for the NLNS approach, since we required 10 processing cores we re-evaluated this method on an A 100 machine).
'The code is open source and the deliberate training mode setting is to be found in the file scarch.py: http://tth...mlllaiiiidddd//a/aa
17

---

Under review as a conference paper at ICLR 2022
D.3 FULL RESULTS ON BENCHMARK DATASET
Table 11: Results different RL OR Models on 10000 VRP Test Instances Kool al. (2019 constitute those that were published and also reproducible during our re-evaluation.
Italic values
VRP20
VRP50
VRPI00
Model
Cost
t
Cost
Cost
f
Gurobi
6.10
LKH3
6.14
2h
10.38
7h
15.65
13h
Batch Evaluation
Cost
t
Cost
t
Cost
NeuRewriter
/6
22m
10.51
35m
10
66m
NLNS
6.19
7m
10.54
24m
15.99
1h
AM (greedy)
6.40
1s
10.98
3s
16.80
8s
AM (sampl.)
6.25
8m
10.62
29m
16.20
2h
MDAM (greedy)
6.28
7s
10.88
33s
16.89
1m
MDAM (bm30)
6.15
3m
10.54
16.26
31m
Single Instance Evaluation
Cost
t/inst
Cost
t/inst
Cost
t/inst
NLNS (1-limit)
6.24
2.41s
10.96
2.41s
17.72
2.02s
AM (greedy)
6.40
0.04s
10.98
0.09s
16.80
0.17s
AM (sampl.)
6.25
0.05s
10.62
0.17s
16.20
0.51s
MDAM (greedy)
6.28
0.46s
10.88
1.10s
16.89
2.00s
MDAM (bm30)
6.15
5.06s
10.54
9.00s
16.26
16.56s
Ours
6.18
(94%*)
0.05s
10.81
(94%*)
0.16s
16.98
(98%**
0.82s
tu
6.24
0.05s
10.87
0.17s
17.02
0.82s
Percentage solved instances. (**) With the option of guaranteed solution
D.4 EVALUATION ON MORE REALISTIC TEST INSTANCES
In this section, we provide generalization results for the test set provided in Kool al. (202T). We compare the LKH method and DPDP (Kool et al.) (2021)) to the generalization results that were achieved after training our model on uniformly-distrin -ittrmmyyydistruueeed data of graph size only.
Table 12 shows that, even though our approach is trained on uniformly distributed VRP50 data, yields competitive results on the 10000 out of sample instances while being among the fastest methods.
Table 12: Comparison DPDP Kool et al. (022)) and LKH for the VRP with 100 nodes 10000 instances generated following the data generation process described Dchoa (017). ). values the Table, except for "Ours", refer to the published results in Kool et al, (2021)
Method
Cost
Time (1 GPU)
LKH
18133
25H59M
DPDP 10K
18415
2H34M
DPDP 100K
18253
5H58M
DPDP 1M
18168
48H37M
Ours
19412
2H38M
18


Reviews:
[{"review_id": "uTROB-BbpvB", "reviewer": "Reviewer_DMGQ", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n1. This paper considers CVRPs with fleet size constraints and vehicle costs, which have not been studied by learning-based methods before. The proposed supervised learning model provides comparable results for standard CVRP and outperforms other learning-based methods accounting for fixed vehicle costs.\n\n2. The model requires less training time when compared with other RL-based algorithms.\n\n3. The model designs a special architecture to handle the permutation-invariant structure of CVRP, which is novel and insightful.\n\nWeaknesses:\n1. The whole framework is based on supervised learning, which requires a bunch of training data. For large-size CVRP, it is hard and time-consuming to get a near-optimal solution. The experiment results do not provide evidence that this model has any generalizability to large-scale problems, which could be a weakness of this paper.\n\n2. The original definition of loss in equation (9) looks very computational-heavy, as it requires to compare every permutation, which the authors also mention it 'The calculation of the loss formulation in Equation 9 would induce considerable computational overhead, therefore a less memory-intensive formulation of the same loss is implemented (see Appendix C.5)'. However, it is unclear to me why the old loss function can be replaced with the new one. I cannot find any proof or explanation. I would expect the authors to provide more details. \n\nSome comments:\n1. For training time comparison, I think the authors should also include the time of generating training sets for your supervised learning model, as other RL-based algorithms do not need. \n\n2. Some equations' are not very clear. For example, in equation (9), I cannot find the definition of $b_k$, I guess $b=b_k$. In equation (16), $b_k$ is defined, but I cannot find it in the equation.", "summary_of_the_paper": "This paper proposes a supervised learning approach with a permutation invariant network to solve the Capacitated Vehicle Routing Problem (CVRP). Instead of assuming an unbounded fleet size, this model focuses on tackling the difficulty of constructing a complete tour plan with a specified fleet size and vehicle costs. The whole framework consists of an encoder, an information extractor, and a decoder. To guarantee the permutation invariance, the authors employ a separate embedding for each entity of the input with linear projection and design a permutation-invariant loss. The experiment results show that the proposed method works well for bounded fleet sizes CVRP and outperforms state-of-the-art RL models when considering fixed vehicle costs. Compared with other state-of-the-art algorithms, this supervised learning-based model is faster to train and provides competitive solutions with fewer vehicles.", "summary_of_the_review": "My decision is weak reject. \n\nThe paper proposes a supervised learning algorithm to solve CVRPs with fleet size constraints and vehicle costs. The authors design a novel permutation invariant network to deal with the combinatorial structure. The experiment results show that the model has comparable performance for standard CVRP and outperforms other learning-based methods accounting for fixed vehicle costs.\n\nHowever, my major concern is the generalization ability of this model. For large-scale CVRP (for example N > 500), simple google’s OR-Tools usually cannot provide near-optimal solutions, while LKH3 is very time-consuming. Therefore, generating a training set will be a big problem. I would change my mind if authors could come up with some ideas to improve or solve this problem. \n\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "QHW-aSSnPFc", "reviewer": "Reviewer_e8jg", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "##########################################################################\n\n Pros:\n\n-The goal of this paper, which is to develop an ML-based approach to the CVRP, is of significant practical interest and appears to be the first to do so.\n\n-The claim of achieving competitive results to baselines that do not guarantee a fixed fleet size is supported by the experiments.\n\n-The unique benefit of the approach, which is that it requires fewer vehicles albeit at slightly longer tour lengths, is validated by the results (particularly, in Table 1). However, it is unclear why Cost_v is not shown in Table 2.\n\n##########################################################################\n\nCons: \n\n-The main contribution appears to be a formulation of the CVRP as a supervised ML problem. I don’t think this is motivated very well. Supervised learning requires a dataset of solved instances of the problem. This becomes prohibitively expensive to acquire for non-trivial problem sizes. To my understanding, this is why RL approaches have garnered most of the attention from this community up to now. Perhaps the authors can provide a convincing argument in support of pursuing supervised ML approaches in the rebuttal.\n\n-I understand that at a high level the technical contribution is a deep learning architecture that can output a tour plan for a fixed fleet size and given CVRP problem instance, but I don’t know exactly what the novel technical component is. From my current understanding, a previous architecture used for the mTSP problem is being repurposed with slight modification. But it is not clear what these modifications are exactly based on the current presentation of the method, which is a bit difficult to parse, and it is hard to therefore assess this contribution. Other aspects of this framework, including the solution decoding algorithm, inference solution post-processing, memory-efficient loss, and auxiliary losses, seem to be ad-hoc with unclear novelty.\n\n-In Section 2, the related methods are described but they are not contrasted with the contributions made by this paper.\n\n-The ability of the model to generalize to out-of-distribution problem instances of the same size, and to problem instances of larger sizes than was trained on, is not explored in the experiments. This is a crucial aspect to test since it is necessary for real-world application.\n\n-Realistic test instances were proposed in Uchoa et al., and the models in this work should evaluate on them.\n\n-It is not clear why DPDP from Kool et al. 2021 is not included as a baseline.\n\n-The claim that RL methods are cumbersome to train is not well supported in general. Indeed, the AM baseline is an RL method that achieves both slightly better tour lengths while being comparably efficient as the proposed method (Table 2). (Granted, it cannot solve the problems with fixed fleet size.)\n\n-Please provide confidence intervals or std. dev. across multiple runs for the main quantitative results (Tables 1 and 2). \n \nReferences:\n\n-Uchoa, Eduardo, et al. \"New benchmark instances for the capacitated vehicle routing problem.\" European Journal of Operational Research 257.3 (2017): 845-858.\n\n#########################################################################\n\nSuggestions for improvement: \n \n-Figure 2 could use a more detailed caption with each high-level module explained. The content under “Encoder”, “Information Extraction” and “Decoder” in the text should match the figure. \n\n-Please define the sizes of vectors and shapes of matrices when introducing variables. \n\n-Clarify along what dimensions that softmaxes are applied in Equation 8 and to transform the compatibility scores of vehicles and edges.\n\n-Prefer providing a text-based description of the (pseudo-)greedy decoding algorithm (Section 4.2) and deferring the pseudocode to the appendix. Also, the “pseudo” aspect of the decoding isn’t explained.\n\n-Based on the ablation study in Appendix B1 for the auxiliary losses, it doesn’t seem like there is a significant difference in Cost/Cost_v performance. Therefore, it could help to simplify the presentation to remove the auxiliary losses from the model.\n \n", "summary_of_the_paper": "This paper is the first to address the capacitated vehicle routing problem with a hybrid machine learning (ML) and algorithmic solution. They demonstrate that their approach is able to find good tour lengths for fixed fleet sizes. Solving the VRP with fixed fleet sizes is well motivated by the limitations faced by service providers.\n", "summary_of_the_review": "I currently am recommending a borderline rejection for this paper. I believe the work is important since it is the first to propose a deep learning solution for the VRP with fixed fleet size. However, I have concerns related to the underlying motivation for the proposed supervised deep learning approach, the validity of a few of the claims and contributions, and have made significant suggestions to strengthen the experiments section. Altogether, this makes me feel the paper is not yet ready for publication. I welcome a response from the authors, particularly pertaining to my concerns related to the motivation and contributions.\n\n================================================================================================\n\nUpdate after rebuttal: While some of the minor concerns I raised were addressed by the paper revisions, the major concerns about the use of SL, the claim of superiority of the proposed end-to-end SL approach compared to RL approaches (particularly with regards to the efficiency experiment shown in Table 3), and the lack of clarity with respect to the precise technical contributions were not addressed. Therefore, I am maintaining my initial score of 5.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "JGqzzgm9XfV", "reviewer": "Reviewer_gFqt", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "One strength of this paper is that it identifies the common limitation of existing approaches in the literature: that they do not actually solve CVRP with hard constraints on the fleet size. Authors provide good explanation of why this violation is problematic for practical applications. Authors also propose a cost function that is motivated by prior work, which would facilitate future research.\n\nAlso, a good range of reinforcement learning baselines are considered in this work. This helps readers to understand the practical utility of the proposed method against alternatives.\n\nHowever, I am not sure the proposed method is an effective way to impose fleet size constraint. The proposed model isn't really guaranteed to produce feasible solutions. In fact, a heuristic repair procedure is applied to meet the constraint, and then another heuristic post-processing with OR tools is used to improve the quality of the solution. It isn't clear to me why these methods are not applicable to existing approaches. In that sense, authors' modeling contribution seems to be orthogonal to the problem of enforcing the fleet size constraint. Also, the experiment section does not clearly describe the contribution of these heuristic post-processing steps. Ablation studies on these components would be desirable. In addition, the post-processing step in Section 4.3 is not described in detail.\n\nThe main experiment in Section 5.1 doesn't include the expert policy (Google's OR Tools) as a baseline. I think it is necessary, because it helps practitioners to understand in which situations they should be using conventional optimizers like OR Tools vs. ML methods, including the proposed one. I also believe the comparison of training time is not really fair- it is quite straightforward that an imitation learning algorithm is faster and easier to train. However, authors do not discuss the fact that their imitation learning method requires the expert policy to train, which is a dependency RL methods don't require.\n\nImitation learning.\n\nEffect of each component is unclear.", "summary_of_the_paper": "Authors tackle the problem of solving a capacitated vehicle routing problem (CVRP) when the cost of introducing an additional vehicle is introduced. Authors propose to use imitation learning with behavior cloning, and uses Google OR Tools as the expert policy. Then, the proposed model extract features with multiple layers of attention and make conditionally independent predictions across the adjacency matrix. It is nontrivial to extract the feasible solution from the probabilistic predictions, so greedy decoding, repair procedure, and post-processing with OR tools is employed.", "summary_of_the_review": "Authors have done a great job identifying a critical missing piece in the existing ML methods for CVRP. However, the proposed method relies on heavy heuristic engineering to enforce the constraint, and authors' modeling contributions seem orthogonal to the main problem (bounded fleet size) they are solving.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "GklMKppe5g3", "reviewer": "Reviewer_hmYm", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is clearly written, and nicely introduces the reader to the bounded CVRP problem. It provides ample details inits annex to help the interested reader dig further in the work. Last but not least, it improves quality of results compared to previous solutions while providing similar search time.\n\nMy main criticism is with regards to the evaluation. Since the technical solution is derived from the work of Kaempfer and Wolf, I would have liked to see the authors compare their solution against that of Kaempfer and Wolf both on the mTSP problem that Kaempfer and Wolf used in their paper and on the CVRP problem tackled in this paper.\nFurthermore, since the authors introduce several refinements to the permutation invariant pooling network architecture, I would have liked to see a complete ablation study to get a sense of how much refinement helped. The paper only provides evidence that using softmax instead of softassign helps in table 5. In particular, I am curious to see how much of the improvement they get comes from the post processing step as opposed from the learnt representation.\nAdditionally, it would have been useful to see the optimal solution in the evaluation table. The authors were able to generate optimal solutions to build their training set, they should have also generated these solutions for their test set. This would have given us a sense of the significance of their improvement in QoR which is currently hard to evaluate since the baseline they used were designed to tackle a slightly different problem.\nThe author also claims outstanding training time compared to NeuRewriter. I am wondering why they didn't compare their training times against these of the baselines they used in table 1. Furthermore, they should explicitly state how time consuming was the generation of their large training set. ", "summary_of_the_paper": "The paper demonstrate how to encode the CVRP with fixed fleet size into a set of input features that can be processed using a neural network derived from the permutation invariant pooling network architecture from Kaempfer and Wolf. They train the neural network using the Kaempfer and Wolf loss extended to penalize infeasible solutions. Lastly, unlike Kaempter and Wolf who use a beam search to convert the predictions made by the neural network into actual solutions, they use a greedy approach complemented by an OR solver to locally improve the solutions. ", "summary_of_the_review": "The paper propose incremental improvements to improve the work of Kaempfer and Wolf and adapt it to tackle the CVRP with bounded fleet size problem. The evaluation of this works needs improvement to trully demonstrate the value of each of these improvements.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper formulates and solves a capacitated vehicle routing problem (CVRP) in the presence of costs for deploying additional vehicles: a mixture of supervised learning, algorithms, and OR techniques is used. In particular, a mix of greedy decoding, repairing of the solution, and post-processing with OR tools is used to extract a feasible solution from the probabilistic prediction. 

The paper makes a good case that existing methods do not solve the CVRP with a hard constraint on the fleet size.  On the other hand, there is a strong dependence on heuristic improvements: e.g., a strongly dependence on the post-processing, and an additional repair procedure for the decoding process. The authors are encouraged to investigate how such improvements would work with existing approaches: i.e., how novel the new model’s contributions are.
Decision: Reject