A QUBO Model for the Traveling Salesman Problem with Time Windows
| Autor: | Theodore Andronikos, Georgia Theocharopoulou, Christos Papalitsas, Sofia Fanarioti, Konstantinos Giannakis |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Mathematical optimization
lcsh:T55.4-60.8 Computer science 02 engineering and technology tsp 01 natural sciences Travelling salesman problem lcsh:QA75.5-76.95 Theoretical Computer Science Time windows 0103 physical sciences 0202 electrical engineering electronic engineering information engineering lcsh:Industrial engineering. Management engineering 010306 general physics Metaheuristic metaheuristics Numerical Analysis d-wave Quantum annealing quantum annealing tsptw Computational Mathematics ishing model Computational Theory and Mathematics Obstacle 020201 artificial intelligence & image processing Quadratic unconstrained binary optimization lcsh:Electronic computers. Computer science qubo |
| Zdroj: | Algorithms, Vol 12, Iss 11, p 224 (2019) Algorithms Volume 12 Issue 11 |
| ISSN: | 1999-4893 |
| DOI: | 10.3390/a12110224 |
| Popis: | This work focuses on expressing the TSP with Time Windows (TSPTW for short) as a quadratic unconstrained binary optimization (QUBO) problem. The time windows impose time constraints that a feasible solution must satisfy. These take the form of inequality constraints, which are known to be particularly difficult to articulate within the QUBO framework. This is, we believe, the first time this major obstacle is overcome and the TSPTW is cast in the QUBO formulation. We have every reason to anticipate that this development will lead to the actual execution of small scale TSPTW instances on the D-Wave platform. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
| Nepřihlášeným uživatelům se plný text nezobrazuje | K zobrazení výsledku je třeba se přihlásit. |