References.md

References & Useful Resources

• A general overview on VRP algorithms: Classical and modern heuristics for the vehicle routing problem

• NEO website on VRP

• VRP Slides by Massimo Paolucci.

• SP Slides by Jesper Larsen.

• Intro to reinforcement learning: Lil's log

• David Silver's reinforcement learning course in UCL

• pgrouting Github repo

• VRP Slides.

• There are 3 Github repos on TSP, which are taken from the appendix of the paper Pointer Network. 1, 2, 3.

• LKH3 Solver, which is one of powerful solvers that can be used for many variants of TSP and VRP (and applied to large size).

• TSP Concorde solver

Heuristic

• Scheduling of Vehicles from A Central Depot to A Number of Delivery Points by G. Clarke and J. W. Wright.

• A Generalized Insertion Heuristic for the Traveling Salesman Problem with Time Windows by Michel Gendreau, Alain Hertz, Gilbert Laporte and Mihnea Stan.

• New Insertion and Postoptimization Procedures for the Traveling Salesman Problem by Michel Gendreau and Alain Hertz.

• A Heuristic Algorithm for the Vehicle-Dispatch Problem by Billy E. Gillett and Leland R. Miller.

• Extensions of the Petal Method for Vehicle Routing by David M. Ryan, Curt Hjorring and Fred Glover.

• Parallel Iterative Search Methods for Vehicle Routing Problems by E. Taillard.

• Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints by Marius M. Solomon.

• An Improved Petal Heuristic for the Vehicle Routeing Problem by Jacques Renaud, Fayez F. Boctor and Gilbert Laporte.

Meta-Heuristic

• Applying the Ant System to the Vehicle Routing Problem by Brend Bullnheimer, Richard F. Hartl and Christine Strauss.

• An improved Ant System algorithm for the Vehicle Routing Problem by Bernd Bullnheimer, Richard F. Hartl and Christine Strauss.

• Ant colony optimization techniques for the vehicle routing problem by John E. Bell and Patrick R. McMullen.

• Applying Simulated Annealing Approach for Capacitated Vehicle Routing Problems by S.W. Lin, K.C. Ying, Z.J. Lee and F.H. Hsi.

• A Simulated Annealing Algorithm for The Capacitated Vehicle Routing Problem by H. Harmanani, D. Azar, N. Helal and W. Keirouz.

• Parallel simulated annealing for the vehicle routing problem with time windows by Zbigniew J. Czech and Piotr Czarna.

• Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems by Paul Shaw.

• A Parallel Hybrid Genetic Algorithm for the Vehicle Routing Problem with Time Windows by Jean Berger, Mohamed Barkaoui and Olli Bräysy.

• A Hybrid Genetic Algorithm for the Capacitated Vehicle Routing Problem by Jean Berger and Mohamed Barkaoui.

• Genetic Algorithms for the Vehicle Routing Problem with Time Windows by Olli Bräysy.

• A route-neighborhood-based metaheuristic for vehicle routing problem with time windows by Fuh-Hwa Franklin Liu, Sheng-Yuan Shen.

• Tabu Search Part I

• Tabu Search Part II

• A User's Guide to Tabu Search

• The granular Tabu Search and Its Applicatiop to the Vehicle Routing Problem by Paolo Toth and Daniele Vigo

• Tabu Search Implementation on Traveling Salesman Problem and Its Variations: A Literature Survey by Sumanta Basu.

• A Tabu Search Heuristic for the Vehicle Routing Problem by Michel Gendreau, Alain Hertz and Gilbert Laporte.

• Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem by Ibrahim Hassan Osman.

• Problistic Diversification and Intensification in Local Search for Vehicle Routing by Yves Rochat and Éric D. Taillard.

Deep Learning / Reinforcement Learning Approaches

Here is a survey on the combinatorial optimization, which is a very general topic: Machine Learning for Combinatorial Optimization: a Methodological Tour d’Horizon by Yoshua Bengio, Andrea Lodi, and Antoine Prouvost.

The following is a collection of some modern approaches on combinatorial problems mainly focusing on TSP/VRP. It turns out these DL/RL models are rather limited to solve VRP of small to medium size while solutions to larger size of VRP still depend on meta-heuristic.

• Pointer Network by Oriol Vinyals, Meire Fortunato and Navdeep Jaitly. PN is specillay designed for the combinatorial optimization. In this paper, the autohers proposed a new neural network called pointer network which outputs a permutation of the input. However, authors trained their model in a supervised way, which makes use of heuristic to get the label. The disadvantage of this is that the labels(optimal solutinos) are hard to acquire when the size of the problem is too large. Meanwhile. the quality of the model is tied to the supervised label. If the labels are not good enough, the model is not able to get better solution.

• Neural Combinatorial Optimization with Reinforcement Learning by Irwan Bello, Hieu Pham, Quoc V. Le, Mohammad Norouzi, Samy Bengio. The authors made use of reinfoecement learning based on actor-critic training along with different search strategies: sampling and active search.

• Reinforcement Learning for Solving the Vehicle Routing Problem by Mohammadreza Nazari, Afshin Oroojlooy, Martin Takac and Lawrence V. Snyder. The authors think the RNN used in original PN is not necessary since the order of the input sequence does not matter. Hence Therefore, the authors simply leave out the encoder RNN and directly use the embedded inputs instead of the RNN hidden states. On capacitated VRP, the approach outperforms classical heuristics and Google’s OR-Tools on medium-sized instances in solution quality with comparable computation time (after training). The authors also showed their approach can be applied to stochastic VRP and even more general problem of combinatorial problem.

• Attention, Learn to Sovle Routing Problem by Wouter Kool, Herke van Hoof and Max Welling. The authors propose a model based on attention layers with benefits over the PN and they show how to train the model using REINFORCE with a simple baseline based on a deterministic greedy rollout. This model has outperformed a wide range of baselines and get highly near-optimal results.

• Neural Large Neighborhood Search for the Capacitated Vehicle Routing Problem by Andre Hottung and Kevin Tierney. The authors apply DL to LNS (NLNS) and train the model based on different destroy operators and let the model learn the complex repair operator. The authors have shoen their method outperformed the two models mentioned above in batch search.

• Learning-Based Iterative Method for Solving Vehicle Routing Problems, which is still under review now.

• Learning to Perform Local Rewriting for Combinatorial Optimization by Xinyun Chen and Yuandong Tian.

• Learning Combinatorial Optimization Algorithms over Graphs by Hanjun Dai, Elias B. Khalil, Yuyu Zhang, Bistra Dilkina, Le Song.

• Learning to Solve NP-Complete Problems: A Graph Neural Network for Decision TSP by Marcelo Prates, Pedro H. C. Avelar, Henrique Lemos, Luis C. Lamb and Moshe Y. Vardi.

• An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem by Chaitanya K. Joshi, Thomas Laurent and Xavier Bresson.