Neural Combinatorial Optimization with Reinforcement Learning : Solving theVehicle Routing Problem with Time Windows
Authors: Abdelhakim Abdellaoui
Issmail El Hallaoui
Loubna Benabbou
Venue: ICLR 2022 Submitted (2022)
Keywords: rienforcement learning
neural combinatorial optimization
vehicle routing problem with time windows
attention model

Abstract: In contrast to the classical techniques for solving combinatorial optimization problems, recent advancements in reinforcement learning yield the potential to independently learn heuristics without any human interventions. In this context, the current paper aims to present a complete framework for solving the vehicle routing problem with time windows (VRPTW) relying on neural networks and reinforcement learning. Our approach is mainly based on an attention model (AM) that predicts the near-optimal distribution over different problem instances. To optimize its parameters, this model is trained in a reinforcement learning(RL) environment using a stochastic policy gradient and through a real-time evaluation of the reward, quantity to meet the problem business and logical constraints. Using synthetic data, the proposed model outperforms some existing baselines. This performance comparison was on the basis of the solution quality (total tour length) and the computation time (inference time) for small and medium-sized samples.

Under review as a conference paper at ICLR 2022
NEURAL COMBINATORIAL OPTIMIZATION WITH RE- INFORCEMENT LEARNING : SOLVING THE VEHICLE ROUTING PROBLEM WITH TIME WINDOWS
Anonymous authors Paper under double-biee blind review
ABSTRACT
contrast to the classical techniques for solving combinatorial optimization problems, recent advancements in reinforcement learning yield the potential independently learn heuristics without any human interventions. In this context, the current paper aims to present complete framework for solving the vehicle routing problem with time windows (VRPTW) relying on neural networks and reinforcement learning. Our approach is mainly based on attention model (AM) that predicts the near-optimal distribution over different problem instances. To optimize its parameters, this model is trained in reinforcement learning (RL) environment using stochastic policy gradient and through real-time evaluation of the reward quantity to meet the problem business and logical constraints. Using synthetic data, the proposed model outperforms some existing baselines. This performance comparison was on the basis of the solution quality (total tour length) and the computation time (inference time) for small and medium sized samples.
INTRODUCTION
Vehicle routing problem with time windows (VRPTW) can be defined as an extension of the well- known vehicle routing problem (VRP) in which the objective is to design network of routes to satisfy customers demands with minimal total costsGia et al.] (2012). Fach route starts from and ends the depot, and for which the total demand is strictly under the vehicle capacity. Except for the depot, all clients are visited once within the corresponding time window. Moreover, when this previous constraint is violated, penalty cost will be applied.
Plenty of research have focused on studying and solving this problem commonly referred to as NP-hard Lenstra & Kan (198I). Introducing time windows increases its computational complexity, therefore VRPTW requires more advanced techniques to get reliable solutions. The literature is full of hand-engineered heuristics that provide near-optimal solutions within practical runtime Bräasy & Gendreau (2005). In general, these classical approaches fulfill the trade-off between optimality and complexity. However, the challenge becomes greater when new problem instances are defined or new features are inserted. In this case, manual adaptation and business knowledge required to maintain the heuristic's 's efficiency.
Considering this tedious maintenance process and the huge advancement in learning methods, some works have been focusing on using RNN and RL to learn independent heuristics for solving the VRP. In this paper, are extending those works by adding the time windows constraint. Precisely, develop an end-to-end model able to provide near-optimal solutions for every problem instance. In other words, as long as the trained model receives data coming roughly from the same generating process, it yields reliable solution without the need to build another model for this specific data. The framework we propose is suitable for introducing more flexibility regarding inputs variance because of the used reinforcement learning approach. The learning process can be formulated as Markov decision process in a well-defined environment. Therefore, the optimal solution is designed following a dynamic perspective, where the policy is architected through attention model and trained to maximize the reward which corresponds to the negative tour length. Additionally, the state can be defined as the data relating each customer (cartesian coordinates, demand, service time, allowed time windows). This state clearly combines static and dynamic parameters, Its dynamic dimension reflects directly the demand change over the learning steps in manner that once client

---

Under review as a conference paper at ICLR 2022
is visited its demand turns into zero Finally, the environment actions could be seen as the set of customers to include in the solution at each stage.
Our approach is an extension of some existing works namely: Bello et al. 2016), Nazari et al. (2018) and Kool et al. (2018). Our added value lies in generalizing those works to solve the VRPTW, one of the most common combinatorial optimization problems. This paper aims also to strengthen the use of machine learning for solving hard combinatorial problems Bengio et al. (022). Including time windows constraint increases the VRP complexity and changes the learning and optimization strategy. Consequently, it requires customization in the data generating process, and a new architecture of the reinforcement learning space, especially the environment policy and the transition function. Concretely, the complete model is made up of a neural network which receives the embedding of dynamic and static inputs. The outputs of this sub-model are processed through an attention mechanism within the reinforcement learning space to deliver at the end the near-optimal sequence.
2 APPROACH BACKGROUND
Before we deep dive in the model architecture and present its main components, we should briefly highlight some problem-related concepts. In addition to the commonly known ideas about VRP, the treated problem presents some specific assumptions. The halting condition is attained when all nodes demand are satisfied. Furthermore, the vehicle of capacity D returns to the depot to refill when its load runs out without resetting the time, Each customer has a service time s; strictly lower than the
corresponding time window range [T Tmaz] to unload its demand. We assume in our case that the time spent to go from customer i customer j is proportional to the distance dzy. In addition, define T to be the needed time to serve all clients.
In short, VRPTW can be formulated as graph G = (V, E), such that X = {xo, I1, .i...... In. is the set of vertices where Tn stands for the depot, and E = {ei = (z)) (z5,2;) E V2] is the set of edges. Besides, each 2; is associated with a tuple of features (c,, di, 8i, TW;) )) and each et is associated with a cost dij where
e; is the two dimensional coordinates of node i.
d, is the demand of node i.
s; is the service time of node i.
TW; is the time window to serve node i.
dy:: is the distance between node and node j.
The ultimate goal of solving VRP TW is to find the path (m1, "i......./] that minimizes the cost.
within the following space: 11 = { TN). Ti E {1o, To. }.
Remark: As a part of the problem setting, is important to mention that the split deliveries are not allowed, and only one vehicle drive to serve all clients.
Many research in the literature tackled the describd problem relying on hand-crafted ap- proaches Fisher (1994). Cordeau & Groupe d' d'études et de recherche en analyse des décisions (Montréal 2200).. However, in the recent few years, new dedicated branch called Neural Combinato- ral Optimization has dawned. Precisely, Vinyals et al. (2015) was the first research that presented its main foundations through a sequence to sequence model called pointer network. This latter consists of two coupled RNN, the first one is used to encode inputs to a specific representation, and the other one to decode the processed output and render it as a sequence. In addition, this work follows a supervised learning approach to train this model using labeled data for the traveling salesman problem (TSP). Even though, this study delivered promising insights about using neural networks for solving combinatorial problems, its results are strongly linked to the quality of the used labels. Furthermore it is a hard task to find enough TSP labeled data for training.
To overcome these limitations a reinforcement learning environment to train the RNN models was proposed by Bello et al.] (201)). Besides, their approach is fully supported by the fact that roughly all combinatorial problems are evaluated through specific reward policy. They provide significant results for both TSP and Knapsack problems in terms of the solution quality and the computational time.
Others attempts in the literature considered the same perspective for solving the VRP namely Nazari et al. (2088) and Peng et al. (2019). Unlike TSP, VRP includes some dynamic parameters, especially regarding node features the case of the demand which changes after visiting a particular customer. As a consequence, the major changes they proposed deal with the attention mechanism, the transition function in the decoding steps, and the embedding of both dynamic and static inputs.
2

---

Under review as a conference paper at ICLR 2022
Taking into account the above-described evolution of neural combinatorial optimization, will present the model architecture to solve the VRPTW.
THE MODEL ARCHITECTURE
The configuration encoder-decoder has proved an important efficiency deal with many problems including VRP Sutskever et al. (2014). As shown in Figure [ the encoder receives raw data X as described section 2|nd converts a convenient representation through many layers. These useful features constructed by the encoder are grasped by the decoder to build progressively the near-optimal sequence. Concretely, the encoder gradually picks out one node to include in the sequence depending on calculated distribution for each node. Thus, one can give the joint probability of solution using the chain rule as follows:
N
Pa (T x)
II (T X, ((i-1)
(1)
Such that, 0 the estimated distribution parameters, and Mi:i-1
(Ti, nT; m. TT=
Encoder
Decoder
Stactuni feaians
Controd Fimberding
3x
hcod Attendon
Initaal Emmbeddingg
Abwnday Joode diinttuhon)
Policy Snadient
X
O
Iupt
Figure 1: The model architecture Bd-cremeev 2020
3.1 ENCODER
More precisely, the encoder incrementally gets the input sequence and transforms it into set of embeddings. For each node x, with features of dimension (d the case of VRPTW), the starting embedding 11 with dimension d' calculated via linear transformation as follows:
{
h (0) Wx; if 0 1
h Wor; + by if i =
Where W E IR' xd and E d are the learnable parameters, while Wy and by are the ones used for the of the depot. As shown in the Figure [ this set of embeddings crosses a network of layers for further updates. Each layer comprises two sublayers: self-attention sublayer and then ferw-forwar sublayer.

---

Under review as a conference paper at ICLR 2022
Self attention sublayer: is called also multi-head attention, it brings specific updates the primary embeddings Vaswani et al. (2177). Let h,4 stands for the embedding of the node in the layer / 21, Taking into account the recursive relation between layers, one can compute the multi-head attention vector M H A! following these equations Peng et al. 2019):
4am W (1-1)
(1)
W h (1-1)
(3)
(0) W n (1-1)
Fim
(1)
(
u ijm Tim jm
(4)
(1) 0 4jmm
mm
(5)
Σ y 1ym
(1)
Nmm
d ijm jm
(6)
1=0
( 11-1) A
11-1)
((--1))
W ! am
m=1
Where, W E IR
W (t) m E IRdxd' W E Rd are learnable parameters, M is the number of heads, Iim E IR is the query vector, k!! IR is the key vector, and u IR is the value vector.
(1)
Feed forward sublayer: Using the multi- attention vector, the update made up through this sublayer for each node i is computed as follows Peng et al. (2019):
(an (1-1) + MHA,") (1. (1 ,M ((1-1) (.."-"".,,,,""))) N)-
(8)
FF( (0) W. R. + (b)
(9)
h tan FF(
(10)
Such that, hi is the embedding of node i at the layer I - 1. W Rdddd' and WF E IRd xd
This computation process is replicated at each layer, consequently the final embedding vector (he (N) ,N(N) ..... A (N)) is the one obtained while ending the layer N. This output vector is considered as the main structural features for the decoder component.
3.2 DECODER
Given the structural features and the constructed solution Iii-1. another computation mechanism is applied at each decoding step to bring out a distribution over the next node to include in the sequence. Firstly. context vector is computed through the M- head attention mechanism to grant more attention to non-visited nodes and ensure respecting the constraints as well. Explicitly, a concatenation of the embedding inputs is set first through the following operator Peng et al. 2019
Peng
h- -
[he A D. if t= h N Dr if
(11)
Such that, [:] is the concatenation operator /4 stands for the mean vector of embeddings over all non-visited nodes at the decoding step t, h. denotes the embedding of the node t 1 in the partial sequence, D, is the unconsumed vehicle capacity at the step t. Finally, T, is the accumulated tour time at step t. The context vector h. is calculated via one M-head attention layer follows Peng al. 2019
Aeem = W A kym W 12 172
(12)
V/m = WV m h
4

---

Under review as a conference paper at ICLR 2022
alemmkmm Kym d3 S Dr. and Ij & #1æ-1 and Ti TW, (13)
Uoljm
00 otherwise
(cc)mm
Σn el(oiom
(14)
72
Σ
(c))m Vjm
(15)
j=0
he Σ
(())m
(16)
The equation 13 indicates that each step of decoding, masking scheme Nazari al. 2018 is applied, which means that the log probability of solution that violates the VRPTW constraints is granted with a value of this decoder, we rely on this technique to mask firstly visited nodes, secondly nodes with demand exceeding the remaining vehicle capacity, thirdly nodes with time window not including the quantity 77', which is the sum of the expected arrival time and the service time. Besides, the depot can appear many times along the path, for this reason, it is masked only when it is selected at step 1.
Remark : In a step i, is allowed mask all nodes. This can happen according to the following scenarios
If the total vehicle load is over, in this case, returns to the depot to refill.
If all nodes are visited, in a such case the vehicle returns to the depot to close the path.
If the time windows constraint is violated for all non-visited nodes, in this case, the vehicle waits the following time window continue the decoding process.
Making use of the above equations, one compute the probability of potential solution step / in this way Peng et al. (2019):
== 1hh- }
k = WK
(17)
C.tanh(g"kj) if dj S Dr, U = and 2j & Tia-1 and TPd E TW2 xc otherwise
(18)
pT x. [1
(19)
Σn e"v
At each decoding step transition function is run to update the dynamic parameters, namely: the vehicle remaining capacity, the node demand and the accumulated tour time.
Assuming that at the step / the selected node is j, therefore:
D = De d
(20)
de 0 and d+t de for i
(21)
T Ti + 8, adi
(22)
Where denotes the proportionality coefficient between distance and the needed time to reach node j from the previous one The index t is put on the above parameters to refer to the step t. Remark: 8o is the loading time when the vehicle arrives the depot.
5

---

Under review as a conference paper at ICLR 2022
3.3 TRAINING
To train the proposed model, we consider the same approach as Peng et al. (2019). Therefore, the stochastic policy π is parametrized with 0, and then optimized using a policy gradient. In principal, this latter runs iteratively to estimate the gradient of the constructed solution in order to maximize the reward. This computation process is synthesized in the well-known REINFORCE algorithm Williams (1992).
Considering space of problems with specific probability distribution. While training, the instances are built and appended to batches following the same distribution. Using the Monte-Carlo sampling rule the gradients of parameters are defined as follows:
VoJ(O))
( x,) L(m) V CooVoolgpp(1 log X,)
(23)
B
Where L(. X) is the tour length of the solution, B is the batch size, ग; andnd n. are the solutions of instance X; constructed by sample rollout and greedy rollout respectively. Explicitly the training algorithm is described through the pseudo-code in algorithm
Algorithm 1 REINFORCE algorithm
Input: number of epochs E, steps per epoch F, batch size B
Initialize parameters 0. for epoch- to E do
for step = to F do
X -RandmmInstnncee),
E 21, B}
n Sampleoollout((p
X:)), E (1, 21, 3,.., B}
" -GreedyRolloutppo
X,)),i (1,2,3,.... B}
X,) - L(x]] [x.) x Vologp(m? X,) B (I
=
0 Adam(0,go))
end for
end for
4 EXPERIMENTAL RESULTS AND DISCUSSION
To measure the performance of the proposed framework, we conduct three experiments. Each one concerns particular graph size (VRPTW 10,20.50), and comprises two stages. For the training, we relied on data we generated ourselves, explicitly the model is trained on a batch of 1000 instances and validated on batch of 500 instances. Similarly, evaluate the performance. we tested the model on generated batch of 500 instances. Besides, for The REINFORCE algorithm, we used the Adam optimizer with a learning rate of 10-4
In detail, generated instance consists of number (graph size) of nodes. Each node is associated with random coordinates in the space [o, 1] x [0, 1]. also a demand from the discrete set 1,,1, 9}. then service time selected randomly from the set {0.1, 0.2, 0.5), and finally time window chosen in the same way from {00, 5]. [5, 10). [0, 10] } as we consider the work time divided into three possible service slots. The depot's 's time window is by definition [0, 10) to enable the vehicle returning refill at any time, and its demand is always fixed at O. The vehicle allocated capacity varies depending on the graph size (D= 20 for VRPTW 10, D 30 for VRPTW 20, D 40 for VRPTW 50) )
To compute the accumulated tour time, the coefficient is thoroughly selected for each graph size enable serving clients within the total allowed time [0, 10). More precisely, in our case it should satisfy the following inequality: (v2a + 0.5)n S 10, such that
n is the corresponding graph size, 0.5 refers to the maximum service time, and v corresponds the maximum distance truck can travel between two points in a square of length 1, and 10 is the time upper bound.
These experiments are run on a GPU machine Tesla K80, using a Tensorflow environment (version 2).
To get clearer ideas about the model performance, study is led using the same common parameters (node features, coefficent a) to compare between the obtained results and those of other well-known baselines in solving VRPTW problems. On the basis of a test dataset of 500 instances generated

---

Under review as a conference paper at ICLR 2022
Table 1: Comparison results for VRPTW the basis of the average tour length test dataset.
METHOD
VRPTW10
VRPTW20
VRPTW50
OR-Tools
4.75
6.26
10.78
LKH-3
4.84
6.37
11.03
RNN-RL
4.78
6.21
10.96
Table 2: Average inference runtime (seconds) for different methods on the test dataset.
METHOD
VRPTW10
VRPTW20
VRPTW50
OR-Tools 0.04
0.15
0.59
LKH-3
0.07
0.23
0.72
RNN-RL
4.78
6.21
10.96
RNN-RL
0.04
0.13
0.66
considering the same distribution the training for each graph size, the comparison results summarized in Table This latter indicates that in terms of the average tour length, the proposed approach clearly outperforms the LKH-3 solver for graph sizes, and provides better results as well in comparison to Google's OR-Tools, especially for small sizes.
Regarding the average runtime as shown Table 2 we can conclude that our method is slightly close to Google's ' OR-Tools and doing better than LKH-3 for different sizes.
According to these results, one can view that using this combination of machine learning and reinforcement learning is maintaining good results for different instance sizes. Such performance is mainly due to the greedy decoding procedure, which aims at constructing the solution incrementally and simultancously reducing the input instance for the next step.
CONCLUSION
The current work constitutes an extension of the previously mentioned works by including the time windows constraint. Merging neural networks with reinforcement learning proved one more time its efficiency for solving this VRP variant. Even though, we integrate the changes required by a such constraint, especially in the data generating process and in the encoding and decoding procedure the model proves good learning and generalization performance.
The significant results and the ficxibility of this method strongly encourage conducting future attempts to include further constraints, particularly multi-depot and heterogeneous flect and even pick-up and delivery concept.
Considering all these constraints could be tine-consuming at the training phase, for this reason, one can incorporate local search
notions build end-to-end framework for solving all VRP variants.
REFERENCES
Bd-eremeev. Dynamic attention model for vehicle routing problems. https://qithub: com/ de-eeeeevvv//eeeeeeeeeeeeee /B////ADM-//PPPP wwt.-/RR//bo////// http://lb//mmttt//cccrresee
architecture cdr
ww..ng.git 2020.
Irwan Bello, Hieu Pham, Quoc V Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforcement learning. arXiv preprint arXiv: 161 1.09940, 2016.
Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: A methodological tour d'horizon. European Journal of Operational Research. 290(2):405 421, 2021.
Olli Bräysy and Michel Gendreau. Vehicle routing problem with time windows, part ii: Metaheuristics. Transportation science,
2005.
7

---

Under review as a conference paper at ICLR 2022
Nicos Christofides. Corst-case analysis of new heuristic for the travelling salesman problem. Technical report, Carnegie- Univ Pittsburgh Pa Management Sciences Research Group, 1976.
Jean-Francois Cordeau and Québec) Groupe d' é'éuddes et de recherche en analyse des décisions (Montréal. The VRP with time windows. 2000.
Dingzhu and Panos Pardalos. Handbook of combinatorial optimization, volume 4. Springer Science & Business Media, 1998.
Marshall Fisher. Optimal solution vehicle routing problems using minimum k-trees, Operations research, 42(())6226666 642, 1994.
Xiaobing Gan, Yan Wang, Shuhai Li, and Ben Niu. Vehicle routing problem with time windows and simultaneous delivery and pick-up service based mepso. Matherattical Problems in Engineering, 2012, 2012.
google.
https::/github...... http:://p//////hhaoooooooooooooa
2018
Keld Helsgaun. effective implementation of the lin kernighnn traveling salesman heuristic. European Journal of Operational Research, 106-130,, 2000.
Scott Kirkpatrick, Daniel Gelatt, and Mario P Vecchi. Optimization by simulated annealing. science, 220(4598):671-688 1983.
Wouter Kool, Herke Van Hoof, and Max Welling. Attention, learn solve routing problems! arXiv preprint arXiv:1803.08477 2018.
Jan Karel Lenstra and AHG Rinnooy Kan. Complexity of vehicle routing and scheduling problems. Networks, 11(2):22-222) 1981.
A Möbius, B Freisleben, Merz, and M Schreiber. Combinatorial optimization by iterative partial transcription. Physical Review E, 59(4):4667, 1999.
Mohammadreza Nazari, Afshin Oroojlooy, Lawrence V Snyder, and Martin Takáč. Reinforcement learning for solving the vehicle routing problem. arXiv preprint 1802.00400 2018.
Bo Peng, Jiahai Wang, and Zizhen Zhang. A deep reinforcement learning algorithm using dy- namic attention model for vehicle routing problems. In International Symposium on Intelligence Computation and Applications, pp. 636-650. Springer, 2019.
Ilya Sutskever, Oriol Vinyals, and Quoc V Le. Sequence to sequence learning with neural networks. arXiv preprint arXiv: 1409::/4009325555 2014.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. arXiv preprint 1xXv:1700603762.. 2017.
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. arXiv:1506.03114, 2015.
Pointer networks.
arXiv preprint
Ronald J Williams.
Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine learning, 8(3-4)2229-22 256, 1992.
Anthony Wren and Alan Holliday. Computer scheduling of vehicles from one or more depots to a
number of delivery points. Journal of the Operational Research Society, 23(3):333-344 344, 1972.
A APPENDIX
In this section, provide description of the baseline used for the comparison, namely: LKH-3 and Google's Or-tools. They are neol- and spurcs solvers dedicated to VRP variants and other combinatorial optimization problems.
8

---

Under review as a conference paper at ICLR 2022
A.1
GOOGLE OR-TOOLS
Google Optimization Tools (OR-Tools) (2018) is an open-source solver, commonly known as one among the most performing implementations for solving combinatorial optimization problems. Concretely, provides an adapted constraint programming interface for solving several mixed-integer linear programming problems. Technically, solving this wide range of variants through OR-tools based on a mixture of heuristics and metaheuristics, firstly for finding a starting solution (Christofides' heuristic Christofides) (1976), Sweep heuristic Wren & Holliday (1972) and secondly to avoid saddle points while searching for the near-optimal solution (Tabu Search Du & Pardalos (1998) and Simulated Annealing Kirkpatrick et al. (1983)).
A.2 LK-3
LKH is open-source solver and direct implementation of the LinnKhnng heuristic Helsgaun (2000) for solving the constrained traveling salesman problem and vehicle routing problems. Over the last decade, many works have been conducted build additional features and produce high performing versions. The recent advancements are related to the following concepts:
Partitioning:
It paves the way to tackle medium and large-sized problems through partitioning to small instances. Each sub instance is solved individually and its solution is used to improve the global solution.
Tour merging:
This concept consists of merging two or even more tours produced for an instance to get the best solution.
Iterative partial transcription:
It aims interchanging parts of two solutions given instance problem get a common best solution. This procedure can be summarized through the algorithm of Möbius et al. (999).


Reviews:
[{"review_id": "rwLfZ8CzFd", "reviewer": "Reviewer_CMcJ", "summary": "", "questions": "", "limitations": "", "rating": 3, "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 \n- The goals and approach of the paper are clearly motivated and outlined\n\nWeaknesses \n- The writing should be improved overall. Issues throughout include grammar, misuse of commas, capitalization (as in reference to algorithm 1 on page 6), technical details left out, poor formatting. \n- There seems to be a lack of novelty in the modeling approach: the same training schemes, DNN model, etc have been developed before, in papers that are cited by this one. \n- The results are rather limited and do not seem to show a clear advantage over standard techniques.\n\nSome sentences have unclear meaning, e.g.:\nPage 1 - ‘a manual adaptation and business knowledge are needed…”\n            - ‘its dynamic dimension reflects directly the demand change over the learning steps…”\nPage 2 - ‘Before we deep dive in the model architecture and present its main components, we should briefly highlight some problem-related concepts’   -  the narration is too casual\nPage 5 - Equation 13 label is cut off - means that violation is given -infinity in what sense? A large floating point number?\nPage 6 - Training:\n\t       Sample rollout and greedy rollout - are these ever defined? What is the baseline function used in the REINFORCE algorithm?\nPage 7 - Google OR-Tools baseline - what are the details of the implementation? Is it the CP-Sat solver? A specialized solver?\n            - What is the meaning of the numbers in Table 1? Is lower better?\n\t    - Why does RNN-RL appear twice in Table 2 with different results?\n\t    - Is OR-tools called with a solver timeout? Or it is allowed to run to completion?\n\t    - The results for RNN-RL are very similar to OR-tools. Can you highlight what is thew advantage of your method?\n\nGeneral questions:\n- Because the solution is built incrementally, is it possible to take an action that leads to no further feasible actions? (Assuming that feasible solutions require every demand to be met - this isn’t made clear in the VRPTW description). This case is different from those in the remark on page 5 - what is done in this case?\n- Generally, does the masking scheme guarantee solutions to be feasible? Is this discussed in the paper?\n- What is the novelty of the approach? The network architecture, training scheme, masking, input representation, etc have all been studied before.", "summary_of_the_paper": "This paper proposes a Neural Combinatorial Optimization approach to solving the Vehicle Routing Problem with Time Windows. It uses a policy gradient method to optimize an attention model, paired with a masking scheme that prevents unwanted actions during the policy rollout. Performance is compared with OR-Tools and LKH-3 solvers.\n", "summary_of_the_review": "See strengths and weaknesses described in the Main review.", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "r9bBYgy2qOq", "reviewer": "Reviewer_RKZQ", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "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 idea of the masking and the multi-head attentions are not novel and they have used earlier on similar problems. \n\nMy main concern is the lack of relevant benchmarks. CVRPTW with the size that is considered in the paper can be solved to optimality, see [1]. This exact algorithm can solve small size problems, like yours, in a few minutes. So, you need to provide the exact baseline instead of only comparing it with LKH3. Besides, there are several papers out there which deal with the same problem by RL. For example, [2] follows a similar masking scheme and compare their results with the optimal solution, obtained by Gurobi, on problems of size 20, 50, and 100. A similar problem is studied by [3, 4, 5, 6]. Also, the result of [7], which got online a few days ago is interesting. They obtain the results which are as good as LKH3 on CVRPTW of size up to 300. \nConsidering the mentioned paper, I do not think the paper at the current shape is ready for acceptance at ICLR. Once you provide larger problems along with the recent benchmarks, the true value of the algorithm will be revealed. \n\n\nminor comment:\nIn table 2, there is a wrong row for RNN-RL. \n\n\n[1] Pessoa, Artur, Ruslan Sadykov, Eduardo Uchoa, and François Vanderbeck. \"A generic exact solver for vehicle routing and related problems.\" Mathematical Programming 183, no. 1 (2020): 483-523.\n[2] Zhao, J., Mao, M., Zhao, X., & Zou, J. (2020). A hybrid of deep reinforcement learning and local search for the vehicle routing problems. IEEE Transactions on Intelligent Transportation Systems.\n[3] Zhang, K., He, F., Zhang, Z., Lin, X., & Li, M. (2020). Multi-vehicle routing problems with soft time windows: A multi-agent reinforcement learning approach. Transportation Research Part C: Emerging Technologies, 121, 102861.\n[4] Lin, B., Ghaddar, B., & Nathwani, J. (2021). Deep Reinforcement Learning for the Electric Vehicle Routing Problem With Time Windows. IEEE Transactions on Intelligent Transportation Systems.\n[5] Sultana, N. N., Baniwal, V., Basumatary, A., Mittal, P., Ghosh, S., & Khadilkar, H. (2021). Fast Approximate Solutions using Reinforcement Learning for Dynamic Capacitated Vehicle Routing with Time Windows. arXiv preprint arXiv:2102.12088.\n[6] Wang, Y., Sun, S., & Li, W. Hierarchical Reinforcement Learning for Vehicle Routing Problems with Time Windows.\n[7] Xin, L., Song, W., Cao, Z., & Zhang, J. (2021). NeuroLKH: Combining Deep Learning Model with Lin-Kernighan-Helsgaun Heuristic for Solving the Traveling Salesman Problem. arXiv preprint arXiv:2110.07983.", "summary_of_the_paper": "An RL algorithm is proposed to solve CVRPTW with the multi-head attention and masking mechanism. The algorithm is tested on problems with 10, 20, and 50 customers, and is compared with Google OR-Tools and LKH3. \n", "summary_of_the_review": "The numerical experiments do not support the claims of the paper and the recent papers and algorithms need to be added in the literature review and the benchmark list. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "ne_cgHF5lsB", "reviewer": "Reviewer_kWGX", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "Solving combinatorial problems using machine learning and RL is an interesting and on-going research topic. A few recent works have solve typical OR problems like VRP using RL. This paper extends those ideas to solve VRP problem with additional time windows constraints. The attention based encoder decoder model is a good contribution to model domain constraints for VRPTW problems. However, I have some reservations regarding the novelty of the paper. First, the encoder-decoder model is a simple extension from Peng et. al., 2019. Second, solving VRPTW problem is not entirely novel (as claimed in the paper); e.g., see [1]. Lastly, I think the empirical results are still premature. Although a wide range of large-scale VRP problem instances are available publicly, the authors experimented with a synthetic dataset and compare their approach with simple heuristic methods. To validate the efficiency of the proposed approach, it should be compared with state-of-the-art VRPTW solvers. The presentation of the paper could be improved as well (specially section 3.3 and section 4).\n\n[1] Joe, W. and Lau, H.C., 2020. Deep reinforcement learning approach to solve dynamic vehicle routing problem with stochastic customers. In Proceedings of the International Conference on Automated Planning and Scheduling (Vol. 30, pp. 394-402).", "summary_of_the_paper": "The paper proposed to solve a vehicle routing problem with time windows using neural network and reinforcement learning framework. An attention based encoder-decoder model is used to predict the distribution over problem instances while satisfying the problem constraints. Then a RL framework is  trained to optimize the model parameter. Experimental results on a synthetic dataset demonstrate that the proposed framework performs at par with traditional combinatorial problem solvers like Google OR tools and LKH heuristic.", "summary_of_the_review": "The paper shows hope for using ML and RL techniques to solve complex combinatorial problems like VRPTW. The proposed attention based encoder-decoder architecture is a good contribution that shows how to handle domain constraints of VRPTW problems. Having said that I think the paper is still premature in terms of both technical and empirical novelty. The technical contributions are incremental and its performance is not validated against state-of-the-art methods. The empirical evaluation is also not detailed enough to validate the efficacy of proposed method.", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "8qXgMcMRhHw", "reviewer": "Reviewer_wGHF", "summary": "", "questions": "", "limitations": "", "rating": 1, "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: \n-- The problem of VRPTW is interesting and important\n\n-- The discussion of related work is OK.\n\n\nWeaknesses:\n1) The paper seems to be a purely applied paper. All the techniques used in this paper seem to come from previous works, without many new technical insights. For example, \n-- Figure 1 was from Bd-eremeev (2020) WITHOUT a change\n\n-- Equations (3) to (19) are ALL from Peng et al. 2019. \n\n-- The training algorithm (REINFORCE) is not new either\n\nTherefore, it provides little technical contribution to the neural combinatorial optimization literature. \n\n2) The paper does not do a good job in describing the VRPTW, especially \n\n-- what is the main difference between VRPTW and VRP? It is not clearly stated. Perhaps you could first describe the VRP, and then elaborate on the VRPTW and emphasize the TW part.\n\n-- it said that VRPTW brings more complexity and is more challenging, but how exactly is it bringing more challenges? Perhaps the authors could do a complexity analysis to concretely show it. Otherwise, it is very hard to evaluate the difficulty of the new problem and thus it's hard to evaluate the contribution of this paper (from an application point of view).\n\n3) The baselines are weak. The paper claims to be a neural combinatorial optimization, but there are no neural combinatorial optimization methods as baselines?\n\n4) The writing of the paper is quite bad and not polished. For example,\n\n-- Table 2, the 3rd row is a duplicate of the 3rd row of Table 1\n\n-- There should be a space between text and reference\n\n-- The second paragraph of Section 2: E or X -> be consistent\n\n-- VRP TW or VRPTW -> be consistent\n\n-- The reference [Cordeau & Groupe d’´etudes et de recherche en analyse des d´ecisions] is apparently off\n", "summary_of_the_paper": "This paper applied the approach in Peng et al. 2019 for vehicle routing problem to a more complex variant called vehicle routing problem with time window. ", "summary_of_the_review": "The paper, in my opinion, is a purely applied paper with almost no change in the method proposed by Peng et al. 2019. Most of the technical contents are copied and pasted from Peng et al. 2019. It's clearly a rejection.", "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": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers unanimously think the paper has lack of novelty, its contributions are quite limited, and is not ready for publication.
Decision: Reject