The first AI4TSP competition: Learning to solve stochastic routing problems

Yingqian Zhang (Corresponding author), Laurens Bliek, Paulo da Costa, Reza Refaei Afshar, Robbert Reijnen, Tom Catshoek, Daniël Vos, Sicco Verwer, Fynn Schmitt-Ulms, André Hottung, Tapan Shah, Meinolf Sellmann, Kevin Tierney, Carl Perreault-Lafleur, Caroline Leboeuf, Federico Bobbio, Justine Pepin, Warley Almeida Silva, Ricardo Gama, Hugo L. FernandesMartin Zaefferer, Manuel López-Ibáñez, Ekhine Irurozki

Research output: Contribution to journalArticleAcademicpeer-review

3 Citations (Scopus)
39 Downloads (Pure)

Abstract

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 an orienteering problem with stochastic weights and time windows (OPSWTW). It focused on two learning approaches: surrogate-based optimization and deep reinforcement learning. In this paper, we describe the problem, the competition setup, and 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 learning-based methods. The instances and code for the competition are available at https://github.com/paulorocosta/ai-for-tsp-competition.

Original languageEnglish
Article number103918
Number of pages18
JournalArtificial Intelligence
Volume319
DOIs
Publication statusPublished - Jun 2023

Bibliographical note

Funding Information:
The organizers would like to thank Ortec and Vanderlande for sponsoring the prize money.

Publisher Copyright:
© 2023 The Author(s)

Keywords

  • AI for TSP competition
  • Deep reinforcement learning
  • Routing problem
  • Stochastic combinatorial optimization
  • Surrogate-based optimization
  • Travelling salesman problem

Fingerprint

Dive into the research topics of 'The first AI4TSP competition: Learning to solve stochastic routing problems'. Together they form a unique fingerprint.

Cite this