GPS: A New TSP Formulation for Its Generalizations Type QUBO

Saul Gonzalez-Bermejo, Guillermo Alonso-Linaje and Parfait Atchade-Adelomou
Additional contact information
Saul Gonzalez-Bermejo: Facultad de Ciencias, Campus Miguel Delibes, Universidad de Valladolid, C/Plaza de Santa Cruz, 8, 47002 Valladolid, Spain
Guillermo Alonso-Linaje: Facultad de Ciencias, Campus Miguel Delibes, Universidad de Valladolid, C/Plaza de Santa Cruz, 8, 47002 Valladolid, Spain
Parfait Atchade-Adelomou: Research Group on Data Science for the Digital Society, La Salle, Universitat Ramon Llull, Carrer de Sant Joan de La Salle, 42, 08022 Barcelona, Spain

Mathematics, 2022, vol. 10, issue 3, 1-20

Abstract: We propose a new Quadratic Unconstrained Binary Optimization (QUBO) formulation of the Travelling Salesman Problem (TSP), with which we overcame the best formulation of the Vehicle Routing Problem (VRP) in terms of the minimum number of necessary variables. After, we will present a detailed study of the constraints subject to the new TSP model and benchmark it with MTZ and native formulations. Finally, we will test whether the correctness of the formulation by entering it into a QUBO problem solver. The solver chosen is a D-Wave_2000Q6 quantum computer simulator due to the connection between Quantum Annealing and QUBO formulations.

Keywords: quantum computing; quantum annealing; combinatorial optimization; QUBO; TSP; VRP (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2022
References: View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://www.mdpi.com/2227-7390/10/3/416/pdf (application/pdf)
https://www.mdpi.com/2227-7390/10/3/416/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:10:y:2022:i:3:p:416-:d:736786

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().