Blog of the Data Science for the Digital Society research group. Digital Society Innovation, Applied Artificial Intelligence, data analysis and smart living and business.

26 October 2021 | Posted by Editorial Team DS4DS

GPS: Improvement in the formulation of the TSP for its generalizations type QUBO

The PhD candidate Parfait Atchadé together with the authors Saúl Gonzalez and Guillermo Alonso propose a new binary formulation of the Travelling Salesman Problem (TSP), with which we overcome the best formulation of the Vehicle Route Generation Problem (VRP) in terms of number minimum of necessary variables. Furthermore, we present a detailed study of the restrictions used and compare our model (GPS) with other frequent formulations (MTZ and native formulation). Finally, we have performed a consistency and efficiency check of the proposed formulation by running it on a quantum annealing computer, D-Wave 2000Q6.

See more:


Add new comment

This question is for testing whether or not you are a human visitor and to prevent automated spam submissions.
1 + 6 =
Solve this simple math problem and enter the result. E.g. for 1+3, enter 4.