The First AI4TSP Competition: Learning to Solve Stochastic Routing Problems
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.
Code (1)
Tasks
Combinatorial OptimizationDeep Reinforcement LearningTraveling Salesman ProblemSimilar Papers 제목 키워드 기반
Combinatorial Optimization enriched Machine Learning to solve the Dynamic Vehicle Routing Problem with Time Windows
With the rise of e-commerce and increasing customer requirements, logistics service providers face a new complexity in their daily planning, mainly due to efficiently handling same day deliveries. Existing multi-stage st…
Combinatorial OptimizationStochastic OptimizationGamifying the Vehicle Routing Problem with Stochastic Requests
Do you remember your first video game console? We remember ours. Decades ago, they provided hours of entertainment. Now, we have repurposed them to solve dynamic and stochastic optimization problems. With deep reinforcem…
Atari GamesDecision MakingDecision Making Under UncertaintyDeep Reinforcement Learning+5TSS GAZ PTP: Towards Improving Gumbel AlphaZero with Two-stage Self-play for Multi-constrained Electric Vehicle Routing Problems
Recently, Gumbel AlphaZero~(GAZ) was proposed to solve classic combinatorial optimization problems such as TSP and JSSP by creating a carefully designed competition model~(consisting of a learning player and a competitor…
Combinatorial OptimizationDeep Reinforcement LearningOnline Control of Adaptive Large Neighborhood Search using Deep Reinforcement Learning
The Adaptive Large Neighborhood Search (ALNS) algorithm has shown considerable success in solving combinatorial optimization problems (COPs). Nonetheless, the performance of ALNS relies on the proper configuration of its…
Bayesian OptimizationCombinatorial OptimizationDeep Reinforcement Learningreinforcement-learning+1The Machine Learning for Combinatorial Optimization Competition (ML4CO): Results and Insights
Combinatorial optimization is a well-established area in operations research and computer science. Until recently, its methods have focused on solving problem instances in isolation, ignoring that they often stem from re…
BIG-bench Machine LearningCombinatorial Optimization