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.
(pdf)


Background

Travelling 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.

Goal

Christmas 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:
  1. Closed-loop TSP
  2. Open-loop TSP
  3. Fixed-start TSP (open loop)
  4. Multiple tours k-TSP (open loop)
In the first variant, Santa needs to consider returning home as well. In all others this is not necessary (open loop). In the second variant Santa can leave from any location he wants. He travels to that place and waits for the start time. In the third variant, he leaves from his home, in Rovaniemi (first location in the dataset). In the fourth variant, the task is impossible for one Santa, so he recruits k assistants (drone Santas) who divide the tour into multiple parts that are solved by each drone separately.

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:
  1. Source code
  2. Method description
  3. 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.

Important dates:


Competition opens: 1 January 2020
Deadline for algorithm submissions: 1 December 2020 1 October 2020
Final results: 24 December 2020
Deadline for abstract submissions: 1 January 2021
Deadline for manuscript submissions: 1 February 2021
*All deadlines are at midnight, Eastern European Time

Evaluation:

All submissions will be evaluated in terms of quality, speed and simplicity. We will evaluate all methods by running them on the same Dell R920 machine with 4 x E7-4860 (total 48 cores), 1 TB, 4 TB SAS HD. A valid submission must run at most 1 hour.

Results:

Results will be published on the competition website by 24 December 2020, latest. Intermediate results can be shared by participants by uploading their solution here, however, the official results come from executing the code in our controlled environment. We will provide the following outcomes from the competition:
  • Two ranking lists: quality and speed (assuming the method terminates quickly and quality is <1% worse than that of the winner)
  • Results will be fully documented and published later as a paper
  • The winner will be invited to visit the Machine Learning group at UEF. We cover reasonable travel and accommodation expenses, and provide VIP treatment during the visit . The winner also qualifies to be an IMPIT student in case he/she pursues a MSc degree in Finland. Language proficiency will still need to be proved.

For more information contact the organizers: