Learning Improvement Heuristics for Solving Routing Problems
Open accessThe DOI matches its Crossref record; 31 of the 31 references it cites were found in a registry or an index.
Abstract
Recent studies in using deep learning (DL) to solve routing problems focus on construction heuristics, whose solutions are still far from optimality. Improvement heuristics have great potential to narrow this gap by iteratively refining a solution. However, classic improvement heuristics are all guided by handcrafted rules that may limit their performance. In this article, we propose a deep reinforcement learning framework to learn the improvement heuristics for routing problems. We design a self-attention-based deep architecture as the policy network to guide the selection of the next solution. We apply our method to two important routing problems, i.e., the traveling salesman problem (TSP) and the capacitated vehicle routing problem (CVRP). Experiments show that our method outperforms state-of-the-art DL-based approaches. The learned policies are more effective than the traditional handcrafted ones and can be further enhanced by simple diversifying strategies. Moreover, the policies generalize well to different problem sizes, initial solutions, and even real-world data set.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Deep Residual Learning for Image Recognition
He, K., Zhang, X., Ren, S., & Sun, J. (2016) · 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR) · doi:10.1109/cvpr.2016.90 · Cited by 235,474
A Comprehensive Survey on Graph Neural Networks
Wu, Z., Pan, S., Chen, F., Long, G., Zhang, C., & Yu, P. S. (2021) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2020.2978386 · Cited by 11,000 · cited 2×
“Self-attention transforms node embed-dings through message passing and aggregation among nodes [25], [30].”
BackgroundMethodEffective Approaches to Attention-based Neural Machine Translation
Luong, T., Pham, H., & Manning, C. D. (2015) · Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing · doi:10.18653/v1/d15-1166 · Cited by 8,382
Asynchronous Methods for Deep Reinforcement Learning
Mnih, V., Badia, A. P., Mirza, M., Graves, A., Lillicrap, T. P., Harley, T., Silver, D., & Kavukcuoglu, K. (2016) · arXiv · doi:10.48550/arxiv.1602.01783 · Cited by 7,132 · cited 1×
“We use n -step return for efficient reward propagation and bias-variance trade-off [34].”
Method“Neural” computation of decisions in optimization problems
Hopfield, J. J., & Tank, D. W. (1985) · Biological Cybernetics · doi:10.1007/bf00339943 · Cited by 6,031
Simple Statistical Gradient-Following Algorithms for Connectionist Reinforcement Learning
Williams, R. J. (1992) · Machine Learning · doi:10.1007/bf00992696 · Cited by 3,416
TSPLIB—A Traveling Salesman Problem Library
Reinelt, G. (1991) · ORSA Journal on Computing · doi:10.1287/ijoc.3.4.376 · Cited by 2,616
Ropke, S., & Pisinger, D. (2006) · Transportation Science · doi:10.1287/trsc.1050.0135 · Cited by 2,580
Democracy Barometer. Methodology. Version 4.
Merkel, W., Bochsler, D., Bousbah, K., Bühlmann, M., Giebler, H., Hänni, M., Heyne, L., Müller, L., Ruth, S., & Weßels, B. (2004) · Intellectum (Universidad de La Sabana) · doi:10.1007/s13398-014-0173-7.2 · Cited by 2,331
The Traveling Salesman Problem and Its Variations
(2007) · Combinatorial Optimization · doi:10.1007/b101971 · Cited by 1,392
Boehning, D., & Snyder, S. H. (2003) · Annual Review of Neuroscience · doi:10.1146/annurev.neuro.26.041002.131047 · Cited by 1,225
Vehicle Routing: Problems, Methods, and Applications, Second Edition
(2014) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611973594 · Cited by 1,131
Learning Combinatorial Optimization Algorithms over Graphs
Dai, H., Khalil, E. B., Zhang, Y., Dilkina, B., & Song, L. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1704.01665 · Cited by 1,007
An analogue approach to the travelling salesman problem using an elastic net method
Durbin, R., & Willshaw, D. (1987) · Nature · doi:10.1038/326689a0 · Cited by 797
Quantifying Generalization in Reinforcement Learning
Cobbe, K., Klimov, O., Hesse, C., Kim, T., & Schulman, J. (2018) · arXiv · doi:10.48550/arxiv.1812.02341 · Cited by 769
Tabu Search and Adaptive Memory Programming — Advances, Applications and Challenges
Glover, F. (1997) · Operations research, computer science. Interface series · doi:10.1007/978-1-4615-4102-8_1 · Cited by 560
General k-opt submoves for the Lin–Kernighan TSP heuristic
Helsgaun, K. (2009) · Mathematical Programming Computation · doi:10.1007/s12532-009-0004-6 · Cited by 414
Guided local search and its application to the traveling salesman problem
Voudouris, C., & Tsang, E. (1999) · European Journal of Operational Research · doi:10.1016/s0377-2217(98)00099-x · Cited by 409
Neural Networks for Combinatorial Optimization: A Review of More Than a Decade of Research
Smith, K. A. (1999) · INFORMS Journal on Computing · doi:10.1287/ijoc.11.1.15 · Cited by 401
Test-Time Training with Self-Supervision for Generalization under Distribution Shifts
Sun, Y., Wang, X., Liu, Z., Miller, J., Efros, A. A., & Hardt, M. (2019) · arXiv · doi:10.48550/arxiv.1909.13231 · Cited by 393 · cited 1×
“This is reasonable because in general, achieving good out-of-distribution generalization is very hard for machine learning models [41].”
BackgroundLearning Heuristics for the TSP by Policy Gradient
Deudon, M., Cournut, P., Lacoste, A., Adulyasak, Y., & Rousseau, L.-M. (2018) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-93031-2_12 · Cited by 303
Wei, L., Zhang, Z., Zhang, D., & Leung, S. C. H. (2018) · European Journal of Operational Research · doi:10.1016/j.ejor.2017.08.035 · Cited by 231
Deep Reinforcement Learning for Sequence-to-Sequence Models
Keneshloo, Y., Shi, T., Ramakrishnan, N., & Reddy, C. K. (2019) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2019.2929141 · Cited by 230
Learning the travelling salesperson problem requires rethinking generalization
Joshi, C. K., Cappart, Q., Rousseau, L.-M., & Laurent, T. (2020) · Constraints · doi:10.4230/lipics.cp.2021.33 · Cited by 202
Machine learning for combinatorial optimization: A methodological tour d'horizon
Bengio, Y., Lodi, A., & Prouvost, A. (2021) · European Journal of Operational Research · doi:10.1016/j.ejor.2020.07.063 · Cited by 195
Neural Machine Translation With GRU-Gated Attention Model
Zhang, B., Xiong, D., Xie, J., & Su, J. (2020) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2019.2957276 · Cited by 144
Solving the vehicle routing problem with adaptive memory programming methodology
Tarantilis, C. D. (2004) · Computers & Operations Research · doi:10.1016/j.cor.2004.03.005 · Cited by 142
A tabu search heuristic for the heterogeneous vehicle routing problem on a multigraph
Lai, D., Demirag, O. C., & Leung, J. M. Y. (2016) · Transportation Research Part E Logistics and Transportation Review · doi:10.1016/j.tre.2015.12.001 · Cited by 130
What makes a VRP solution good? The generation of problem-specific knowledge for heuristics
Arnold, F., & Sörensen, K. (2018) · Computers & Operations Research · doi:10.1016/j.cor.2018.02.007 · Cited by 125
A Note on Learning Algorithms for Quadratic Assignment with Graph Neural Networks.Preprint
Nowak-Vila, A., Villar, S., Bandeira, A. S., & Bruna, J. (2017) · arXiv (Cornell University) · Cited by 112
Learning the Multiple Traveling Salesmen Problem with Permutation Invariant Pooling NetworksPreprint
Kaempfer, Y., & Wolf, L. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1803.09621 · Cited by 60
Cited by
Reinforcement learning for combinatorial optimization: A survey
Mazyavkina, N., Sviridov, S., Ivanov, S., & Burnaev, E. (2021) · Computers & Operations Research · doi:10.1016/j.cor.2021.105400 · Cited by 723
Solving Vehicle Routing Problem Using Quantum Approximate Optimization Algorithm
Azad, U., Behera, B. K., Ahmed, E. A., Panigrahi, P. K., & Farouk, A. (2023) · IEEE Transactions on Intelligent Transportation Systems · doi:10.1109/tits.2022.3172241 · Cited by 149
“These include exact algorithms such as branch and bound [6], construction heuristics like Clarke and Wright saving algorithm [23], improvement heuristics [24], and meta-heuristic algorithms such as genetic algorithms [9], simulated annealing [10], Tabu search [25], dwarf mongoose optimization algorithm [26], arithmeti…”
MethodDeep Learning for Solving Loading, Packing, Routing, and Scheduling Problems
Elkefi, S., & Layeb, S. B. (2023) · Handbook of Formal Optimization · doi:10.1007/978-981-19-8851-6_16-1 · Cited by 3
Metadata
- Authors
- Wu, Y., Song, W., Cao, Z., Zhang, J., & Lim, A.
- Venue
- IEEE Transactions on Neural Networks and Learning Systems
- Published
- 2022-09
- Volume
- 33
- Issue
- 9
- Pages
- 5057-5069
- ISSN
- 2162-237X (ISSN-L)
- 2162-2388
- OpenAlex
- W3146106549
- Cited by
- 344
- References
- 31
- FWCI
- 28.01
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.