The First AI4TSP Competition: Learning to Solve Stochastic Routing Problems
Not on the map. Why?
Abstract (arXiv)
This paper reports on the first international competition on AI for the traveling salesman problem (TSP) at the International Joint Conference on Artificial Intelligence 2021 (IJCAI-21). The TSP is one of the classical combinatorial optimization problems, with many variants inspired by real-world applications. This first competition asked the participants to develop algorithms to solve a time-dependent orienteering problem with stochastic weights and time windows (TD-OPSWTW). It focused on two types of learning approaches: surrogate-based optimization and deep reinforcement learning. In this paper, we describe the problem, the setup of the competition, the winning methods, and give an overview of the results. The winning methods described in this work have advanced the state-of-the-art in using AI for stochastic routing problems. Overall, by organizing this competition we have introduced routing problems as an interesting problem setting for AI researchers. The simulator of the problem has been made open-source and can be used by other researchers as a benchmark for new AI methods.
Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 25 of its 56 references that are in the map. First posted on arXiv 25 Jan 2022.
Builds on
25 of 56 references.
References · 25
- 2015Pointer Networkscited by 882
- 2018Attention, Learn to Solve Routing Problems!cited by 646
- 2018Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizoncited by 612
- 2016Neural Combinatorial Optimization with Reinforcement Learningcited by 600
- 2020POMO: Policy Optimization with Multiple Optima for Reinforcement Learningcited by 341
- 2018Reinforcement Learning for Solving the Vehicle Routing Problemcited by 327
- 2019An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problemcited by 265
- 2018Learning to Perform Local Rewriting for Combinatorial Optimizationcited by 183
- 2019Learning Improvement Heuristics for Solving Routing Problemscited by 162
- 2020Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instancescited by 161
- 2019Neural Large Neighborhood Search for the Capacitated Vehicle Routing Problemcited by 117
- 2021Learning to Delegate for Large-scale Vehicle Routingcited by 108
13 more
- 2021NeuroLKH: Combining Deep Learning Model with Lin-Kernighan-Helsgaun Heuristic for Solving the Traveling Salesman Problemcited by 102
- 2020Learning 2-opt Heuristics for the Traveling Salesman Problem via Deep Reinforcement Learningcited by 100
- 2021Efficient Active Search for Combinatorial Optimization Problemscited by 99
- 2021Deep Policy Dynamic Programming for Vehicle Routing Problemscited by 94
- 2021Learning Collaborative Policies to Solve NP-hard Routing Problemscited by 86
- 2019Combinatorial Optimization by Graph Pointer Networks and Hierarchical Reinforcement Learningcited by 78
- 2020Combining Reinforcement Learning and Constraint Programming for Combinatorial Optimizationcited by 63
- 2020Reinforcement Learning with Combinatorial Actions: An Application to Vehicle Routingcited by 61
- 2020Learn to Design the Heuristics for Vehicle Routing Problemcited by 24
- 2020Continuous surrogate-based optimization algorithms are well-suited for expensive discrete problemscited by 8
- 2020A Reinforcement Learning Approach to the Orienteering Problem with Time Windowscited by 8
- 2019Black-box Combinatorial Optimization using Models with Integer-valued Minimacited by 5
- 2020Surrogate Assisted Optimisation for Travelling Thief Problemscited by 3
Built on by
Citing papers per year: 2022: 2; 2023: 0; 2024: 1.
3 papers.