PathGame
Crowdsourcing Time-Constrained Human Solutions
for the Travelling Salesperson Problem

Slavisa Dumnic^*

Djordjije Dupljanin^*

Vladimir Bozovic⁺

Dubravko Culibrk^*

^*University of Novi Sad, Serbia
⁺University of Podgorica, Montenegro

[Paper]

[Play]

[Code+Data]

Pathgame focuses on the closed-form Manhattan block distance variant of the TSP.

Human strategies for solving the Travelling Salesperson Problem (TSP) continue to draw the attention of the researcher community, both to further our understanding of human decision making and as an inspiration for the design of automated solvers. Online games represent an efficient way of collecting large amounts of human solutions to the TSP and PathGame is a game focusing on non-Euclidean closed-form TSP. To capture the instinctive decision-making process of the users, PathGame requires users to solve the problem as quickly as possible, while still favouring more efficient tours. In the initial study presented here, we have used PathGame to collect a data set of over 16,000 tours, containing over 22,000,000 destinations. Our analysis of the data revealed new insights related to ways in which humans solve TSP and the time it takes them when forced to solve TSPs of large complexity quickly.

Data + Code

[GitHub]

Acknowledgements

This work was supported in part by by the Ministry of Education, Science and Technology Development of the Republic of Serbia and the Ministry of Science of Montenegro, through the bilateral project “Information system to support collaborative courier services in urban areas”. This webpage template was borrowed from some colorful folks.