Santa Claus TSP Challenge
Call for papers: Special issue and Competition
Results of the challenge are summarized in the following paper:
Solving large-scale TSP problem in 1 hour: Santa Claus Challenge 2020
R. Mariescu-Istodor and P. Fränti
Frontiers in Robotics and AI, 8, 1-20, October 2021.
BackgroundTravelling salesman problem (TSP) is a classical optimization problem that has been evolved to real-life vechile routing problems (VRP). Recent development in unmanned aerial vehicles (UAV) is bringing these problems into new dimensions.
GoalChristmas is coming and Santa Claus needs to deliver presents to the children in every family on Christmas Eve. He prepares his sledge but when the time has come, he has to proceed fast and optimize the length of his tour. He can also use helpers and divide the tour into several parts. Your task is to optimize the trip!
What is it?We organize the special issue as a challenge. We invite researchers and practitioners to help Santa and give solutions to:
- Closed-loop TSP
- Open-loop TSP
- Fixed-start TSP (open loop)
- Multiple tours k-TSP (open loop)
Competition Rules:We provide a dataset of 1,437,195 targets. Submitted algorithms must optimize this tour during the course of 1 hour. After at most 1 hour, the program must terminate and report the best result achieved thus far. All submissions should be self-documented programs in Matlab, Python, C/C++, Java or PHP to be executed on a Linux machine. Each submission must contain:
- Source code
- Method description
- Citation (in case of using existing method) or Abstract (in case of novel method)
Data:To keep the task reasonable, we limit the tour in Finland. We have constructed the dataset from OpenStreetMap buildings data. There are N=1,437,195 targets in total. Dataset is available here.
Submission system:Submit your solutions here.
All valid submissions will be evaluated after executing for 1 hour or less in case the program stops before that. If the program does not terminate after 1 hour, it will not be considered for evaluation. Based on the results, the authors of novel methods are invited to submit their final versions to the special issue. The method description serves as an Abstract of your method.
Journal submission:It is possible to submit your method only to the competition but we strongly recommend to submit also a paper to the special issue of Frontiers in Robotics and AI if the method has novelty and its performance is competitive.
All submitted papers will go through a normal review process and will be handled immediately after submission.
Publication fees are 1900$ (A-type), 875$ (B-type), and 450$ (C-type) articles.
|Competition opens:||1 January 2020|
|Deadline for algorithm submissions:||
1 December 2020
|Final results:||24 December 2020|
|Deadline for abstract submissions:||1 January 2021|
|Deadline for manuscript submissions:||1 February 2021|