A Learning-based Iterative Method for Solving Vehicle Routing Problems
Authors: Hao Lu
Xingwen Zhang
Shuang Yang
Venue:  (2020)
Keywords: vehicle routing
reinforcement learning
optimization
heuristics

Abstract: This paper is concerned with solving combinatorial optimization problems, in particular, the capacitated vehicle routing problems (CVRP). Classical Operations Research (OR) algorithms such as LKH3 \citep{helsgaun2017extension} are inefficient and difficult to scale to larger-size problems. Machine learning based approaches have recently shown to be promising, partly because of their efficiency (once trained, they can perform solving within minutes or even seconds). However, there is still a considerable gap between the quality of a machine learned solution and what OR methods can offer (e.g., on CVRP-100, the best result of learned solutions is between 16.10-16.80, significantly worse than LKH3's 15.65). In this paper, we present ``Learn to Improve'' (L2I), the first learning based approach for CVRP that is efficient in solving speed and at the same time outperforms OR methods. Starting with a random initial solution, L2I learns to iteratively refine the solution with an improvement operator, selected by a reinforcement learning based controller. The improvement operator is selected from a pool of powerful operators that are customized for routing problems. By combining the strengths of the two worlds, our approach achieves the new state-of-the-art results on CVRP, e.g., an average cost of 15.57 on CVRP-100.

Published as a conference paper at ICLR 2020
A LEARNING-BASED ITERATIVE METHOD FOR SOLVING VEHICLE ROUTING PROBLEMS
Hao Lu
Princeton University, Princeton, NJ 08540
(haolu)@princet.c))
Xingwen Zhang & Shuang Yang Ant Financial Services Group, San Mateo, CA 94402 [xingwen. zhang, shuang, yantgaanttinn.....
ABSTRACT
This paper is concerned with solving combinatorial optimization problems, in par- ticular, the capacitated vehicle routing problems (CVRP). Classical Operations Research (OR) algorithms such LKH3 (Helsgaun 2017) are inefficient and dif- ficult to scale to larger-size problems. Machine learning based approaches have recently shown to be promising, partly because of their efficiency (once trained, they can perform solving within minutes or even seconds). However, there is still considerable gap between the quality of a machine learned solution and what OR methods can offer (e.g., on CVRP-100, the best result of learned solutions is between
significantly worse than LKH3's 15.65). In this paper, we present "Learn to Improve" (L2I), the first learning based approach for CVRP that is efficient solving speed and the same time outperforms OR methods. Start- ing with a random initial solution, L2I learns to iteratively refine the solution with an improvement operator, selected by a reinforcement learning based controller. The improvement operator is selected from pool of powerful operators that are customized for routing problems. By combining the strengths the two worlds, our approach achieves the new state-of-the results on CVRP, e.g., average cost of 15.57 on CVRP-100.
INTRODUCTION
In this paper, focus on an important class of combinatorial optimization, vehicle routing problems (VRP), which have a wide range of applications in logistics. Capacitated vehicle routing problem (CVRP) is a basic variant of VRP. aiming to find a set of routes with minimal cost fulfill the demands of a set of customers without violating vehicle capacity constraints. The CVRP is NP hard
DDanzzig & Ramser 1959), and both exact and heuristic methods have been developed solve
Fukasawa et al.) 2006 Golden et al. 2008 Kumar & Panneerselvam 2012 Toth & Vigo 2014).
In recent years, especially after the seminal work of Pointer Networks (Vinyals et al.) 2015). re-
searchers start to develop new deep learning and reinforcement learning (RL) frameworks solve
combinatorial optimization problems (Bello et al.
2016 Mao et al. 2016: Khalil et al., 2017: Ben-
gio et al.] 2018 Kool et al., 2019; Chen & Tian 2019). For the CVRP itself, number of RL-
based methods have been proposed in the literature (Nazari et al. 2018 Kool et al.) 2019 Chen &
Tian 2019). The learning based methods are trained
huge number of problem instances, and
have been shown to be extremely fast in producing solutions of reasonably good quality. However, when tested with the same benchmark instances, these learning-based methods cannot outperform the state-of-the-art method LKH3 (Helsgaun) 2017). which is minalty-function-baseee extension of classical Lin-Kernighan heuristic (Lin & Kernighan 1973; Helsgaun 2000). For example, on CVRP with 100 customers, LKH3 is able to produce an average cost of 15,65. This line of research motivated to study framework that combines the strength of Operations Research (OR) heuris- ties with learning capabilities of machine leaming (RL in particular). Machine learning can learn
Equul contribution.

---

Published as a conference paper at ICLR 2020
to solve class of problem instances fast, when test instances generated from the same distri- bution as training instances. Classical approaches like search algorithms are effective but may need heavy computation, which is time-consuming. Our research interest is in fusing the strengths of these two worlds. Another related line of research is hyper-heuristicr which is "a search method or learning mechanism for selecting generating heuristics to solve computational search problems" (Burke et al., 2013). Instead of developing high-level methodology without the need of knowing the details of low-level heuristics, we are primarily interested in a closely integrated system that best utilizes the strength of OR operators and learning capability.
Our Contributions. Instead of directly constructing solution from the problem instance GGrves it al. 2014], SStskkver et al.) [014] Vinyals et al. 2015), we propose a framework that iteratively searches among solutions, until a certain termination condition is satisfied. Our main contributions are as follows:
We present a learning- based algorithm for solving CVRP, achieving new state-of-the-aat re- sults. The recent line of works using RL to solve CVRP shows the potential of machine learning algorithms. They can solve CVRP faster, but cannot beat classical OR solvers like LKH3 in term of solution quality. Our algorithm is the first machine learning framework that outperforms LKH3 on CVRP.
We propose a novel hierarchical framework. Instead of putting operators in one action pool, we separate heuristic operators into two classes, namely improvement operators and perturbation operators. At each state, we choose the class first and then choose operators within the class. Learning from the current solution is made easier by focusing RL on the improvement operators only.
We propose an ensemble method, which trains several RL policies the same time, but with different state input features. The ensemble method is shown to produce superior results than individual policies with equivalent amount of computation.
Related Work. In recent years, there have been many studies using deep learning and RL to solve combinatorial optimization problems (Smith) 1999 Mao et al.] 2016 Lodi & Zarpellon] 2017]
Veličković et al. 2017: Lombardi & Milano 2018 Bengio et al. 2018). Routing problems, es-
pecially traveling salesman problems (TSP) and VRP, have been explored by sequence of works
(Vinyals et al. 2015 Bello et al., 2016: Khalil et al., 2017 Li al. 2018 Deudon et al.] 2018 Kaempfer & Wolf 2018) et al. [
Kool et al. 2019 Chen & Tian 2019). Most of these works, with the exception of Chen & Tian (2019), follow end-to-end approach, which is directly constructing a solution from scratch. |Vinyals et al. (2015) first introduce the Pointer Network, in- models, to solve TSP. They use an attention model to learn the order of different nodes in a supervised fashion. Later [ello et al. (2016) develop an RL algorithm to train the Pointer Network. Their framework learns the optimal policy from problem instances and needs no supervised solutions. Nazari et al. (2018) improve the Pointer Network with a new design, mak- ing the model invariant with respect the input sequence, and extend it to solve VRP. Kool et al. 2019) propose a model based on attention layers, and an RI. algorithm to train this model with simple but effective baseline. Chen & Tian (2019) propose a NeuRewriter model for VRP They define rewriting rule set and train two policy networks, a region- srgion-iccking policy and a rule-picking policy, to obtain the next state. Given an initial solution, their goal is to find a sequence of steps towards the solution with minimal cost.
spired by requence-to-sequenee
1.1 NOTATIONS
In CVRP, there is depot and set of N customers. Each customer i, {1,..., NN. has a demand d, to be satisfied. A vehicle, which always starts at and ends at the depot, can serve set of customers as long as the total customer demand does not exceed the capacity of the vehicle. The traveling cost Gjj is the cost of vehicle going from node i to j. with i E 10.1.... N) (where the depot is denoted by node 0 for convenience). The objective is to find a routing plan with minimal cost that serves all customers without violating vehicle capacity constraints. Figure [ gives an illustration of CVRP, while a mathematical formulation given the Appendix.
2

---

Published as a conference paper at ICLR 2020
Route. A route is sequence of nodes visited order, with the de- pot (node 0) as the starting and end- ing node. For example, [0, 1, 3, 4, 0] is traveling plan that starts the depot, visits node 1, and 4 sequen- tially, and returns to the depot.
Customer
Depot
Depol
Operator
Solution. A solution is set of routes such that each customer is visited exactly once, and the total demand along each route less than the ve- hicle capacity.
Figure 1: An illustration of CVRP. Here we provide prob- lem instance. The red one is a sample route, and three routes consist of solution for this problem instance. After apply- ing an operator, current solution changes to a new solution with dashed lines replaced by blue lines.
Operator. An operator is mapping from one solution to another. In this paper, instead of directly constructing a solution from scratch, we improve or perturb the solution iteratively us- ing operators.
2 LEARN TO IMPROVE
In this section we formally introduce our "Learn to Improve" (L2I) framework, including main components the system as well as the design intuitions behind individual components. Figure 2 illustrates the overall framework. As mentioned previously, the framework is iterative in nature, that is, we always start with a feasible solution, continuously improving the solution or perturbing it. Along the way, all constraints remain satisfied. By always maintaining the feasibility of the solution, we are exploring the space of feasi- ble solutions and any of them found by our search process could poten- tially be good solution. After T (a parameter set in advance) steps the algorithm stops, and we choose the one with the minimum traveling cost as our final solution. Our framework has few distinct components (e.g., how improve the solution, when and how to perturb it), which could be rule-based, learned by machine learn- ing or mixed, and thus allows to experiment with different ways of in- tegrating machine learning and OR, some which could lead to superior methods either in terms of better lution quality or in terms of computa- tional efficiency. It is worthwhile to point out that, contrast to the work of Chen Tian (2019), the solu- tion space we explore is much larger since we are employing rich set of improvement and perturbation opera- tors.
Improvement controller
Perturbation
controller
select
controller
select
Improvement
update
update
Perturbation operators
Solution
operators
iniliate
Problem
instance
Figure Our hierarchy framework. Given a problem in- stance, our algorithm first generates feasible solution. Then it iteratively updates the solution with an improvement operator selected by an RL-based controller or with per- turbation operator chosen by a rule-based controller. After certain number of steps, we choose the best one among all visited solutions.
For this research work, we implemented and experimented with number of design choices, and ended up with a method that is both computationally efficient and able to produce state-of-the-an results. The details of the main components of method recent solutions, our method uses a threshold- based rule to decide whether we should continue to improve the current solution, should perturb it and restart with the perturbed solution. If it decides
follows. Given history of most

---

Published as a conference paper at ICLR 2020
that the current solution could still be improved, it will use RL-based controller choose one of the improvement operators, and try to improve the solution with the chosen operator. We have rich set of improvement operators (the list of improvement operators and their details given in the Appendix), where intra-route ones attempt to reduce the cost of current solution by moving customers different positions in individual routes, while inter-route ones attempt reduce the cost by moving customers among different routes. Given that the improvement operators are of distinct characteristics, not straightforward know in advance which operators are most effective for the problem under investigation. It is also difficult to know a pre-defined ordering of the operators that is best for the problem. Thus, an RL-based controller is a good choice to learn the set of improvement operators that is more effective for the problem (or more specifically, the problem and the data distribution from which the training and test instances are sampled). As will be shown in Section 3 our RL model is able to differentiate more useful improvement operators from less useful ones for CVRP, as well as generate an implicit ordering on how the operators will be applied.
On the other hand, upon reaching local minimum the perturbation controller randomly chooses perturbation operator that destroys (completely or partially) and reconstructs a number of routes to generate new starting solution (Table the Appendix gives the list of perturbation operators and their details). Specifically, if no cost reduction has been made for L improvement steps, we perturb the solution and restart the improvement iteration (where for ease of explanation a maximum con- secutive sequence of improvement operators applied before perturbation is called an improvement iteration). As a perturbation changes the solution quite dramatically (by producing substantially different solution that is usually worse than the current one), we found that it is useful to start a new improvement iteration with reasonably good starting point (e.g. by filtering out the restarting solutions that are significantly worse than current solution or currently best solution). It is clear that we purposely separate improvement operators from perturbation ones, and an alternative design would be to mix them all together and have single controller deciding which operator to apply next. However, the improvement operators are of different nature from the perturbation ones, and their impacts are different since the perturbation operators have long- lasting effect by affecting an entire improvement iteration. Our experience also suggests that learning is made casier by focusing RL on the improvement operators only. Lastly, it is worthwhile to point out that although the rule- based perturbation controller is shown to be effective, we do not rule out the possibility that it can also be learning-based. based.
The framework described above provides a way of combining the strength of OR operators, which powerful since they are custom-made for routing problems, with learning capabilities of RL, which is flexible and can be adapted to a given problem and its associated data distribution. Hav- ing described our overall framework, we are now ready to present the details of the improvement controller and operators.
2.1 IMPROVEMENT CONTROLLER AND OPERATORS
The improvement controller starts with an initial solution, which is either constructed randomly (for the first improvement iteration] 2 or produced by a perturbation operator (for subsequent iterations), and then tries to improve it, i.e., reducing the total traveling distance without violating any con- straints, by selectively applying an improvement operator in Table For the RL model, the set of improvement operators constitute most are computationally light. With the current state as input, a neural network produces a vector of action probabilities, and the weights of the network are trained with policy gradient. Figure 6 illustrates the components of our RL model, and their details are given as follows.
action space. These operators change the solution locally and
2.1.1 STATES
Each state includes features from the problem instance, the solution and the running history. Station- ary features, such as the location and demand of each customer, are considered as since they invariant across solutions. Solution-specific features are based on the current travel- ing plan. For example, given a solution, for each customer we compute its neighboring nodes that visited before and afterwards, as well as the relevant distances. Following Ödling (011)), the
OOter construction heuristics, such as the Clarke-Wright algorithm Clarke & Wright 1964) can also be
used.
4

---

Published as a conference paper at ICLR 2020
running history includes the actions that recently taken well their effects. For example, ar-h. I h S H, is the action taken h steps before current step f, and its effect et-b is +1 the action led to reduction of total distance, -1 otherwise. A complete description of state features is given in Table 4 where i= and it denote the node visited before and after node i, v i & N, in the solution, respectively.
2.1.2 ACTIONS
The actions can be classified into two classes, intra-route operators and inter-route operators. An intra-route operator attempts to reduce traveling distance an individual route, while inter-route operators aim at reducing total traveling distance by moving customers between more than one route. The details of the operators are given in Table It is worthwhile to point out that the same operator with different parameters are considered different actions. For example, Symmetric-exchange(2 with m = 1, 2,3 3 are considered as three distinct actions. For given problem (or even solution), the same operator with different parameters may perform differently and thus it is appropriate treat them as separate actions and let the RL model learn how to best use them.
2.1.3 POLICY NETWORK
We use the well-known REINFORCE algorithm (Williams
1992) to update the gradient
vgJ(O)s) Ex-pe(lle ((L())s) b(s) ) Vo log (x{(s)]
policy network outputs a list of action probabilities, one for each action described. As illustrated in Figure o problem- and solution-speciff input features are transformed into an embedding of length D (we use D = 64), which is fed into an attention network (Vaswani et al.) 2017) (we use attention layer with 8 heads and 64 output units). The output of the attention network is concatenated with a sequence of recent actions and their effects (when H >> 0). Lastly, the concatenated values fed into a network of two fully connected layers, where the first layer uses 64 units and a Relu activation function and the second layer uses Softmax, producing |A] action probabilities where A is the set of actions.
of policy with a baseline function b(s). Given state as described in Section 2.1.1
2.1.4 REWARDS
We have experimented with number of reward designs, two of which are producing satisfactory results as well as distinct patterns of operator sequences. The first reward function (denoted by RF1) focuses on the intermediate impact of the improvement operators. Specifically, the reward is +1 if the operator improves the current solution, -1 otherwise. The second reward function (denoted by RF2) advantage-bass based. The total distance achieved for the problem instance during the first improve- baseline. For each subsequent iteration, all operators applied during this
ment iteration is taken iteration received a reward equal to the difference between the distance achieved during the iteration and the baseline. We observed that an operator is often able achieve large distance reduction for a freshly perturbed solution, while it becomes harder and harder to do so in later improvement steps. In particular, the likelihood of distance reduction well the magnitude of such reduction, both decrease as the iteration proceeds. Therefore, it seemed unfair to give early improvement operators larger reward. The observation suggested that operators used in the same improvement iteration should be rewarded equally and there would be no discounting (or equivalently, the discount factor y is 1).
To conclude the methodology section, we restart the improvement iteration until reaching maxi- mum number of rollout (either improvement or perturbation) steps. Following a common practice of encouraging exploration, we use e-greedy (Sutton & Barto 2018) such that with probability of 0.05 the RL controller will choose random improvement action. Lastly, we also experimented with ensembling by training 6 different policies with H 2...... 6 (while keeping other components of the policy network identical). Ensembling facilitates learning of a diverse set policies, as well reducing wall-clock running time.
5

---

Published as a conference paper at ICLR 2020
3 EXPERIMENTS AND ANALYSES
In this section, we present our experiment results. First we introduce a detailed setup of CVRP and hyper-parameters used. Then we compare our performance with prior neural network approaches, i.e. Nazari et al. (2018), Kool et al. (2019), Chen & Tian (2019), and classic state-of-the-ar heuristic algorithm. At last we provide detailed analysis our frameworl
We follow the same settings as previous works (Nazari et al. 2018 Kool et a 2019 Chen & Tian 2019) for CVRP. We consider three sub-problems with number of customers N 20, 50, 100, respectively. The location (I,, yr) of cach customer, as well as of the depot, is uniformly sampled from unit square (specifically, 2; and yi are uniformly distributed in the interval [0, 1), respectively), and the traveling cost between two locations Gij simply the corresponding Euclidean distance. The demand d, of each customer is uniformly sampled from the discrete set {1, ,.,....9.. 9). The capacity of vehicle is 20, 30, 40 for N 20, 50, 100, respectively. After L 6 consecutive step of no improvement, we perturb the solution. To train the policy network, we
Setup and hyper-parametert
of 0.001. Unless otherwise stated, for problem instance and a given policy we randomly initiate feasible solution, and then iteratively update the solution T 40000 times following the policy. In the following section we will discuss the performance of a policy with different rollout steps (recall that rollout step is either an improvement step or a perturbation one). We choose the best one among solution for a given problem instance. In the ensemble model we use different number of historical actions and effects to train a set of diverse policies (recall the policy network in Figure and for any problem instance we choose the best solution produced by these policies. Unless otherwise stated, all reported metrics, such as the final traveling cost and the running time, are always computed as the average over 2000 random samples. Lastly, method was implemented in Python, and the experiments were run computer nodes, each with a single Nvidia Tesla T4 GPU.
ADAM with learning
40000 visited solutions as the final
3.1 PERFORMANCE COMPARISON
In Table we compare the performance of our algorithm with prior neural network approaches mentioned above, Google OR-tools (Google 2019), and classic state-of-the-art heuristic algorithm LKH3 (Helsgaun) 2017). Our ensemble method chose the solution with minimum traveling cost among those produced by Policy (with S h S 6). As shown in Table [ our algorithm out- performs the prior approaches in terms of average traveling cost. In particular, the average distance achieved by our algorithm significantly shorter than prior neural network approaches. Thus, our algorithm is producing ttateoof-the-are results for CVRP, and is the first learning-based framework that outperforms the well-known classic heuristic algorithm.
Table 1: Comparison of our experiment results with those reported in the literature
N = 20
= 50
N
100
Obj.
Obj.
Obj.
Google OR Tools
6.43
11.31
17.16
Nazari al. 2018
6.40
11.15
16.96
AM greedy KKool ct al.
2019
6.40
10.98
16,80
AM sampling Kool
2019
6,25
10.62
16.23
Chen & Tian 2019
6.16
10.51
16.10
LKH (Hllsgaun) 2017
6.14
10.38
15.65
1.21
6.12
10.35
15.57
3.2 ANALYSIS OF THE ENSEMBLE METHOD
Recall that we train different policies with E (1. 6). To illustrate the motivation of the ensemble method, we randomly pick 10 problem instances and show the traveling cost under different policies for these problem instances in Table 2 We can see that Policy did the best for
"oode will he available githuh..co/rlop///2 upon approval of the company.

---

Published as a conference paper at ICLR 2020
the first problem instance, but it performed the worst for the second one. Furthermore, there is clear winning policy, which is the reason we propose an ensemble method.
Table 2: Motivating examples: traveling cost under different policies for random problem instances
Problem instances
2
4
5
6
7
8
9
10
Policy I
18.65
16.67
15.41
15.11
16.69
14.97
16.88
16.37
13.72
13.56
Policy 2
18.86
16.61
15.39
15.10
16.55
14.75
16.73
16.39
13.77
15.56
Policy 3
18.81
16.63
15.43
15.06
16.82
14.72
16.70
16.37
13.73
15.79
Policy 4
18.90
16.60
15.37
15.04
16.66
14.93
16.83
16.32
13.70
15.62
Policy 5
18.73
16.56
15,43
15.12
16.66
15.09
16.80
16.53
13.72
15.56
Policy 6
18.92
16.60
15.43
15.09
16.73
14.65
16.59
16.55
13.73
15.56
4156
438
15
2014
Trosel
22:40
6.35
612
13:
3GS0
Rellout steps
(a) CVRP-20
(b) CVRP-50
Travelinggoo
155
044
154
(c) CVRP-100
(d) CVRP-100
Figure 3: Average traveling cost of different policies with different rollout steps
In Figure 3]), (b) and (c), plot the average traveling cost over 2000 problem instances for CVRP with N = 20, 50, 100, respectively. It is worthwhile to point out that the same hyper-parameters are used for different N values. The top blue line is for random policy, the bottom red line for our ensemble method, and lines in between are for Policy 1, ..... 6. The plots show that, regardless of the number of rollout steps, our trained RL policies consistently outperform the random policy. Figure[fc shows that the gap between the random policy and the ensemble method first increases, peaks about 5000 rollout steps, and then gets smaller and smaller. maximum gap fast, which will be helpful when computational time is limited. Lastly, in Figure we show three policies, the random policy, the ensemble method, and the best RL policy (Policy 3), for CVRP-100. To match the performance of the random policy with 40000 rollout steps, the ensemble method would take 2500 rollout steps, while takes 5000 rollout steps to match Policy with 40000 rollout steps. The outperformance of the ensemble method becomes
encouraging that we get the
obvious when N = 20, 50. These analysis shows that naively increasing rollout steps policy provides less marginal gains than ensembling diverse set of policies.
7

---

Published as a conference paper at ICLR 2020
Table 3: Improvement operators mostly used
Class
Name
Details
Remove two edges and reconnect their endpoints
2-Opt
Intra-route
Move a customer in the route to
Relocate(1)
new location
Cross(2)
Exchange the tails of two routes
Exchange segments of length m
Inter-route
Symmetric-exchanee(()
(m = 1) between two routes Move a segment of length
Relocate(2)
( (m = 1) from a route to another
3.3 ANALYSIS OF OPERATOR USAGES
As we mentioned before, the RL model is able to differentiate more useful improvement operators from less useful ones for CVRP. In our experiments, we count the usage of different operators for different policies as training epochs grow, When the myopic reward function RFI in Section 2.1144 is used, our experimental results show that the policy converges to use a fixed subset of improvement operators (for detailed operators, see Table 33. This subset of operators policies when we use RF2. However, the pattern of operator usages varies among the policies. For example, Figure 4 () and (b) illustrate different patterns of operator usages for Policy I and Policy 2, respectively.
also preferred by all
1000
3000
600
600
2000
Opochs
Epochs
Policy
(b) Policy
Figure 4: Pattern of operator usages as training epoch grows
3.4 ANALYSIS OF PERTURBATION MAGNITUDE
From our experimental study we also observed that the solution quality is sensitive to the magnitude of perturbation. To illustrate the impact of perturba- tion, in Figure 5 we plot the performance of two run configurations, one with hundom-permute ap- plied to all routes (called Random- -eriooteeettmttall)) while the other with Random-pennt candom-permute applied two routes only (called Random- Random-permuit permute-2). As seen from Fig- ure
significantly outperformed Random--ermute-all, Intuitively, when the magni- tude of perturbation is too large, the resulting solu- tion generally becomes much worse and it will take our algorithm a large number of improvement steps to remedy the deterioration.
cutstaga
Figure 5: Impact of perturbation magnitude
8

---

Published as a conference paper at ICLR 2020
4 CONCLUSION
In this paper we propose "Learn to Improve" for solving VRP, which starts with an initial solution and iteratively updates the solution with an improvement operator selected by RL-based controller or with a perturbation operator chosen by rule-based controller. We also propose ensemble method that trains several RL policies and chooses the best solution produced by the policies. Our method achieved new state-of-the-an results for CVRP instances.
Our work provides a way of combining the strength of OR with learning capabilities of RI.. For future work, we would like apply the solution framework to solve other variants of the VRP, such as vehicle routing problems with time windows (VRPTW), as well as other combinatorial problems, such maximum independent set problems and graph coloring problems. Furthermore, interesting to investigate whether allowing temporary constraint violations in our framework will help improve solution quality not.
ACKNOWLEDGEMENT
We would like to thank our colleagues at Ant Financial, Wei Yan and Junping Zhao, for allocating GPU resources needed for the computational experiments.
REFERENCES
Irwan Bello, Hieu Pham, Quoe V. Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforcement learning, 16Xiv:161..09400 2016.
Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimiza- tion: methodological tour d'horizon. 1rXiiv:811.0611 2018.
Edmund K. Burke, Michel Gendreau, Matthew R. Hyde, Graham Kendall, Gabriela Ochoa, Ender Özcan, and Rong Qu. elyper-heuiistie: a survey of the state of the art. Journal of the Operational Research Society, 64: 64:169551725 1724, 2013.
Xinyun Chen and Yuandong Tian. Learning to perform local rewriting for combinatorial optimiza- tion. arXiv: 180.00033 2019.
G. Clarke and J. W. Wright. Scheduling of vehicles from central depot number of delivery points. Operations Research, 12:568-581, 1964.
G. B. Dantzig and H. Ramser. The truck dispatching problem. Management Science, 6(1):80-91, 1959.
Michel Deudon, Pierre Cournut, Alexandre Lacoste, Yossiri Adulyasak, and Louis-Martin Rousseau. Learning heuristics for the TSP by policy gradient. In International Conference on the Integration of Constraint Programming. Artificial Intelligence, and Operations Research, pp- 170-181. Springer, 2018
Ricardo Fukasawa, Humberto Longo, Jens Lysgaard, Marcus Poggi de Aragão, Marcelo Reis, Ed- uardo Uchoa, and Renato F Werneck. Robust branch-and-cut-an--rriie for the capacitated vehicle routing problem. Mathematical Programming. 106(3):491-511, 2006.
Bruce L.
Golden, Subramanian Raghavan, and Edward A. Wasil. The vehicle routing problem: latest advances and new challenges. Springer Science Business Media, 2008
Google. OR-tools, Google optimization tools, 2019. URL http:://daveooeerss.ooog.
com/ htnn/oppimization
Alex Graves, Greg Wayne, and Ivo Danihelka. Neural turing machines. arXh::440.54011200
Keld Helsgaun. An effective implementation of the Lin-Kernighan traveling salesman heuristic. European Journal of Operational Research, 126: 106-130, 2000.

---

Published as a conference paper at ICLR 2020
Keld Helsgaun. An extension of the Jin-KKenighhn-Hellsee TSP solver for constrained traveling salesman and vehicle routing problems. Technical report, Roskilde University, 2017.
Yoav Kaempfer and Lior Wolf. Learning the multiple traveling salesmen problem with permutation invariant pooling networks. /tti:/8003.9922 2018
Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial op- timization algorithms over graphs. Advances Neural Information Processing Systems, pp- 0348-6358, 2017.
Wouter Kool, Herke van Hoof, and Max Welling. Attention, learn to solve routing problems! In International Conference on Learning Representations, 2019.
Suresh Nanda Kumar and Ramasamy Panneerselvam. A survey on the vehicle routing problem and its variants. Intelligent Information Management, 4:66-74, 2012.
Zhuwen Li, Qifeng Chen, and Vladlen Koltun. Combinatorial optimization with graph convolutional networks and guided tree search. In Advances in Neural Information Processing Systems, pp. 539-548, 2018.
S. Lin and B. W. Kernighan. An effective heuristic algorithm for the traveling-salesmar problem. Operations Research, 21:498-516, 1973.
Andrea Lodi and Giulia Zarpellon. On learning and branching: a survey. Top, 25(2):207-236, 2017.
Michele Lombardi and Michela Milano. Boosting combinatorial problem modeling with machine learning. arXiv: 05517, 2018.
Hongzi Mao, Mohammad Alizadeh, Ishai Menache, and Srikanth Kandula. Resource management with deep reinforcement learning. In The 15th ACM Workshop on Hot Topics in Networks, pp- 50-56. ACM, 2016
Mohammadreza
Nazari, Afshin Oroojlooy, Lawrence Snyder, and Martin Takáe. Reinforcement learning for solving the vehicle routing problem. In Advances in Neural Information Processing Systems, pp. 9839-9849 2018.
David Ödling. A metaheuristic for vehicle routing problems based on reinforcement learning. Mas- ter's thesis, KTH Royal Institute of Technology, School of Engineering Science, 2018.
Kate A. Smith. Neural networks for combinatorial optimization: a review of more than a decade of research. INFORMS Journal on Computing, 11(1):15-34, 1999.
Ilya Sutskever, Oriol Vinyals, and Quoe V. Le. Sequence to sequence learning with neural networks. In Advances in neural information processing systems, pp. 3104-3112, 2014.
Richard S. Sutton and Andrew G. Barto. Reinforcement learning: an introduction. MIT Press, edition, 2018.
Paolo Toth and Daniele Vigo. Models, relaxations and exact approaches for the capacitated vehicle routing problem. Discrete Applied Mathematics, 123:487-512, 2002.
Paolo Toth and Daniele Vigo. Vehicle routing: problems, methods, and applications. SIAM. 2014.
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:845-8555 2017.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz. Kaiser, and Illia Polosukhin. Attention is all you need. Advances in Neural Informa- tion Processing Systems, pp. 6000-6010, 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv:/710) 10903, 2017.
10

---

Published as a conference paper at ICLR 2020
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. In Advances in Neural Information Processing Systems, pp. 2692-2700, 2015.
J J Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine learning, 8(3-4):229-256, 1992.
A AN INTEGER PROGRAMMIN FORMULATION OF THE CVRP
Formally, there is depot and of N customers in the CVRP. Each customer i, {1, (I....,NN N). has a demand de to be satisfied. A vehicle, which always starts at and ends at the depot, can serve set of customers as long as the total customer demand does exceed the capacity of the vehicle C. The traveling cost Ci is the cost of a vehicle going from node to j. with i, E V = {0, ......... N} (where the depot is denoted by node for convenience). The objective is to find routing plan with minimal cost that serves all customers without violating vehicle capacity constraints. An integer programming formulation of the CVRP (Toth & Vigo 2002) given below.
min
Ci.
8EV
JEV
s.t.
Tíj = 1, Vj E EVjEVE (0)
NEV
Σ Fi 1, E V (0)
(2)
.EV
Σ 31,0
Σ 20.J K,
(4)
JEV
4, 0j + Criy 50 C'--0 -d., dj, Vi,j E V \ (0), i s.t. d, + d3 S
(5)
d 4 S C, Vie EVI (0),
Jig E (0, VijVV,
where K is the number of vehicles available (w.l.o.g., it is assumed that K N for the CVRP we consider). Constraints ① and 2 specify that each customer is visited exactly once, while constraints (3) and (4) specify the and out degree of the depot, respectively. Constraints (5) and (6) impose the vehicle capacity requirements.
Table 4: State features
Type
Name
Details
G
Demand of customer
C
Free capacity of the route containing customer
(II, M/
Location of customer
(x4-- 10--3/-7
Location of node visited before i
Problem- and solution-specific
(Ie+t Me+)
Location of node visited after i
d
Distance from à to
dg,11
Distance from i to i+
dy-
Distance from i- to +
History-related
Ge-h
Action taken steps before
6t-h
Effect of 0z-A
B DETAILS OF STATES AND OPERATORS
We list the details of our state features in Table and of operators in Table 5 and
11

---

Published as a conference paper at ICLR 2020
Table 5: Improvement operators
Class
Name
Details
Remove two edges and reconnect their endpoints
2-Opt
Intra-route
Symmetrri-exchangee()
Exchange two customers in the route
Move a customer in the route to
Relocate(1)
new location
Cross(2)
Exchange the tails two routes
Reverse one of two routes and then
Reverse-cross(2)
exchange their tails
Exchange segments of length
Symmetrric-xxhange(()
( (m 1, 2, between two routes
Inter-route
Exchange segments of length and (m = 1, 2, 3, n = 1, 2, 3, m n)
Asymmetri--xxcanne((
between two routes
Move segment of length m
Relocate(2)
( (m = 1, 2, 3) from route to another Exchange cyclically one customer between three routes
Cyclic-exchange(3)
Table Perturbation operators
Class
Name
Details
Randomly destroy m routes and re-construct routes by visiting affected customers in random order
Random-permute
Inter-route perturbation
Random-exchange((2
Randomly exchange pairs of nearby customers between two routes
Exchange cyclically customers between multiple routes
Cyclic-exchange
C POLICY NETWORK
Figure shows the structure of our policy network.
D RESULTS ON TSP
To quickly produce results for the TSP, we slightly modified our code for the CVRP by always using the first point in a TSP input as the depot the CVRP formulation and enforcing that there is exactly route in solution. The capacity of any point is naturally assumed to be zero. Lastly, we implemented a simple perturbation operator by randomly permuting 20 points for TSP-50 and TSP-100 (10 points for TSP20). Figure shows the trends of individual polices, ensemble one, for TSP-100. Again we observe that the ensemble method out-performed individual policies, while producing total distance slightly above the optimal value of 7.76 reported in the literature. The results for TSP-20 and TSP-50 are similar and thus omitted.
well as the
E SCALABILITY ANALYSIS
We also tested our method on larger CVRP instances, CVRP-200 and CVRP-100d using the same experimental settings CVRP-100 (e.g. the capacity of vehicle is fixed at 50). The results are
It is worthwhile point out that CVRP-1000 results are averaged over 200, instead of 2000, instances, simply due to time limit.
12

---

Published as a conference paper at ICLR 2020
Action probabilities
MLP
MLP
History actions and effects
Embedding after attention
+
Attention network
Current solution
+
Embedding
Instance information
Embedded state
Figure 6: Policy network. The dash-line box is the state embedding part of policy network, which contains problem- and colution-specinee input features, an attention network, and sequence of historical actions and effects. The concatenated values are fed into a network of two fully connected layers, producing vector of action probabilities.
188
78
Traveligg
LSH5
220
Ro
Figure 7: Results for TSP-100
given Figure & which shows that our ensemble method scales well as the number of customers increases. In particular, the running time of our method increases less dramatically than LKH3.
13

---

Published as a conference paper at ICLR 2020
Traeeling Cost
Time (mins)
18
7M
1000
Figure 8: Traveling cost and average computation time as the number of customers increases
F SENSITIVITY ANALYSIS
1956
186
1.40
1.4
4.96
outstopo
Robloct Cteps
(a) Depot positioning
(b) Customer positioning
Figure 9: CVRP-100 results under different data distributions by Policy 3
Traeleg.oo
0200
1.5
follout Atpp
Halbou, Aapp
(a) Tested on CVRP-20 with different models
(b) Tested on CVRP-50 with different models
Figure 10: Generalization results using Policy 3
Following the same protocol of data generation in Uchoa et al. (2017) (the authors of the paper were the creators and owners of the CVRPLib website"). we tested our method for four additional scenarios, namely, central depot positioning, eccentric depot positioning, clustered customer po- sitioning, and random-clustered customer positioning. It is worthwhile to point out that the data distribution used in our initial paper corresponds random depot and random customer position- ing. Figure () (a) shows the impact of depot positioning (while using random customer positioning), and (b) shows the effect of customer positioning (while using random depot positioning). To make results from different data distributions comparable, we normalized the distance by the minimal dis- tance achieved for each data distribution (denoted by "Ratio" as in the Figure), respectively. The plots show that our method works across different data distributions, and the decreasing trends of distance look similar.
m..
hhtt:///vrp-galgoss. inf www.aloo....uuu..oooooo.. httpeeriio.briddx.ppppeee
14

---

Published as a conference paper at ICLR 2020
Furthermore, we also used the model trained for CVRP-100 to solve CVRP-50 and CVRP-20. Sim- ilarly, we also tested trained CVRP-50 model for CVRP-20. Figure I0 shows that current imple- mentation of our method can be applied to problems of different sizes.
15


Reviews:
[{"review_id": "SkeKKnRaKB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "EDIT: I have read the responses and increased my rating to Weak Accept.\n\nThe paper proposes an algorithm for the Capacitated Vehicle Routing problem that starts with a random solution and then iteratively improves it by using a learned policy to select an improvement operator to apply to the current solution. Once the solution stops improving for a number of steps, a perturbation is applied to the solution, and the iterations continue by applying improvement operators selected by the learned policy. The problem is posed as a sequential decision problem, and the policy is learned using reinforcement learning. Results on synthetic instances of size 20, 50, and 100 show that the approach is able to achieve better objective value than relevant baselines and faster running time than the LKH algorithm.\n\nPros:\n- Better objective value than baselines and running time than LKH is an impressive result.\n\n- Paper is clearly written and easy to follow. CVRP and other background information is sufficient to fully understand the paper.\n\n\nCons:\n- The proposed approach has the benefit of using a handcrafted pool of improvement operators that other learning-based approaches don’t have. This makes the comparison to previous learning approaches unfair, and the observed improvements may simply be due to the extra information that the approach gets in the form of the operator pool.\n\n- The evaluation should be expanded to larger instances and existing benchmarks such as CVRPLib (which contains larger instances as well) to understand scalability and generalization to different instance distributions. For example, would the same improvement operator pool suffice for a completely different distribution of instances?\n\n\nAdditional comments:\n- Typically when using RL for learning a local search policy, the reward is defined as the change in objective after applying a local move such that the sum of rewards and the initial objective value gives the actual objective value and the policy will be learning to optimize the objective function. In this paper the reward definitions RF1 and RF2 don’t have this property, which suggests that the policy is not being trained to directly optimize the CVRP objective function. Is there an explanation for why it still works?\n\n- It would be useful to explore how well the self-attention network architecture scales to larger problems (e.g., > 1000 customers), and whether using a graph neural network instead results in better or worse results.\n\n- Typo: “significantly worse then”\n\n- Typo: “their would be no discounting”\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "SJxSed6qdB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a framework combining RL and OR for solving the capacitated vehicle routing problem (CVRP). The main idea is to train an RL-based controller for choosing the OR operations necessary for improving & reinitializing the solution. Additionally, an ensemble method for diversifying the solution is proposed. The proposed method is shown to empirically outperform the existing OR method LKH3 for solving CVRP. \n\nOverall, this paper provides a solid contribution by proposing a new learning-based algorithm that beats conventional solver, which is quite hard to achieve. The writing is clear and easy to read. The reference and related works look complete to my knowledge. \n\nOne weakness of the paper is the lack of experiments. Since the paper focuses on the CVRP problems, it would have been nice to compare with the LKH3 on larger graphs, e.g., the case when N > 100. One could also verify the scalability of the algorithm by examining larger-scale benchmarks and compare with heuristics faster than LKH3, e.g., see [1]. I think this is crucial for demonstrating the applicability of the algorithm to real-world problems.\n\n[1] Uchoa et al., New benchmark instances for the Capacitated Vehicle Routing Problem, EJOR 2017", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "N/A"}, "extra_text": {}}, {"review_id": "B1x_eK-RYB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Using a combination of RL-based solution as a warm start, this paper shows that by adding more improvement and perturbations, the quality of the solutions for capacitated VRP can be further improved. The numerical experiments show that with these extensions, the proposed mechanism is able to perform better than the SOTA LKH3 OR-based method in a shorter amount of time. I find the paper novel and interesting, but I have a few suggestions to further improve it:\n\n1) Most of the mentioned operators are also valid for TSP. To provide a baseline for further research, I am expecting to see the performance of the proposed approach in TSP as well. \n2) I hope that you make your code and saved models publicly available for future researchers since it might not be easy to replicate your numbers.\n3) Maybe in future research, the ensemble idea can be tested for making the solution independent of problem size. This is an important possible extension.\n4) That would be great if you could add a section for sensitivity analysis. How the model trained for VRP100 is working for say, VRP200, or VRP50?\n\nMinor: \n1) It worths mentioning how e-greedy that is primarily used in value-based methods is incorporated in policy gradient exploration.\n2) Page 7, it should be \"Figure 3(a), (b), ...\"\n3) Table 3 and Table 5 overlap. Maybe, it is better to merge them together. \n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review:    The paper proposed the use of a combination of RL-based iterative improvement operator to refine the solution progressively for the capacitated vehicle routing problem. It has been shown to outperform both classical non-learning based and SOTA learning based methods. The idea is novel and the results are impressive, the presentation is clear. Also the authors addressed the concern of lacking justification on larger tasks by including an appendix of additional experiments. 
Decision: Accept (Poster)