GPS: A New TSP Formulation for Its Generalizations Type QUBO
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...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2022-01-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/10/3/416 |
| _version_ | 1827660028356591616 |
|---|---|
| author | Saul Gonzalez-Bermejo Guillermo Alonso-Linaje Parfait Atchade-Adelomou |
| author_facet | Saul Gonzalez-Bermejo Guillermo Alonso-Linaje Parfait Atchade-Adelomou |
| author_sort | Saul Gonzalez-Bermejo |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-09T23:32:28Z |
| format | Article |
| id | doaj.art-bd22b81bfdff4036b3937113859883c6 |
| institution | Directory Open Access Journal |
| issn | 2227-7390 |
| language | English |
| last_indexed | 2024-03-09T23:32:28Z |
| publishDate | 2022-01-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj.art-bd22b81bfdff4036b3937113859883c62023-11-23T17:07:11ZengMDPI AGMathematics2227-73902022-01-0110341610.3390/math10030416GPS: A New TSP Formulation for Its Generalizations Type QUBOSaul Gonzalez-Bermejo0Guillermo Alonso-Linaje1Parfait Atchade-Adelomou2Facultad de Ciencias, Campus Miguel Delibes, Universidad de Valladolid, C/Plaza de Santa Cruz, 8, 47002 Valladolid, SpainFacultad de Ciencias, Campus Miguel Delibes, Universidad de Valladolid, C/Plaza de Santa Cruz, 8, 47002 Valladolid, SpainResearch Group on Data Science for the Digital Society, La Salle, Universitat Ramon Llull, Carrer de Sant Joan de La Salle, 42, 08022 Barcelona, SpainWe 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.https://www.mdpi.com/2227-7390/10/3/416quantum computingquantum annealingcombinatorial optimizationQUBOTSPVRP |
| spellingShingle | Saul Gonzalez-Bermejo Guillermo Alonso-Linaje Parfait Atchade-Adelomou GPS: A New TSP Formulation for Its Generalizations Type QUBO Mathematics quantum computing quantum annealing combinatorial optimization QUBO TSP VRP |
| title | GPS: A New TSP Formulation for Its Generalizations Type QUBO |
| title_full | GPS: A New TSP Formulation for Its Generalizations Type QUBO |
| title_fullStr | GPS: A New TSP Formulation for Its Generalizations Type QUBO |
| title_full_unstemmed | GPS: A New TSP Formulation for Its Generalizations Type QUBO |
| title_short | GPS: A New TSP Formulation for Its Generalizations Type QUBO |
| title_sort | gps a new tsp formulation for its generalizations type qubo |
| topic | quantum computing quantum annealing combinatorial optimization QUBO TSP VRP |
| url | https://www.mdpi.com/2227-7390/10/3/416 |
| work_keys_str_mv | AT saulgonzalezbermejo gpsanewtspformulationforitsgeneralizationstypequbo AT guillermoalonsolinaje gpsanewtspformulationforitsgeneralizationstypequbo AT parfaitatchadeadelomou gpsanewtspformulationforitsgeneralizationstypequbo |