Un modelo QUBO para el problema del vendedor viajero con ventanas de tiempo
Autores: Papalitsas, Christos; Andronikos, Theodore; Giannakis, Konstantinos; Theocharopoulou, Georgia; Fanarioti, Sofia
Idioma: Inglés
Editor: MDPI
Año: 2019
Acceso abierto
Artículo científico
2019
Un modelo QUBO para el problema del vendedor viajero con ventanas de tiempo
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería de Software
Palabras clave
Expresión
TSP
Ventanas de tiempo
QUBO
Formulación
D-Wave
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 46
Citaciones: Sin citaciones
Este trabajo se centra en expresar el TSP con Ventanas de Tiempo (TSPTW en resumen) como un problema de optimización binaria no restringida cuadrática (QUBO). Las ventanas de tiempo imponen restricciones temporales que una solución factible debe cumplir. Estas toman la forma de restricciones de desigualdad, que se sabe que son particularmente difíciles de articular dentro del marco de QUBO. Creemos que esta es la primera vez que se supera este importante obstáculo y que el TSPTW se formula en QUBO. Tenemos todas las razones para anticipar que este desarrollo llevará a la ejecución real de instancias de TSPTW a pequeña escala en la plataforma de D-Wave.
Descripción
Este trabajo se centra en expresar el TSP con Ventanas de Tiempo (TSPTW en resumen) como un problema de optimización binaria no restringida cuadrática (QUBO). Las ventanas de tiempo imponen restricciones temporales que una solución factible debe cumplir. Estas toman la forma de restricciones de desigualdad, que se sabe que son particularmente difíciles de articular dentro del marco de QUBO. Creemos que esta es la primera vez que se supera este importante obstáculo y que el TSPTW se formula en QUBO. Tenemos todas las razones para anticipar que este desarrollo llevará a la ejecución real de instancias de TSPTW a pequeña escala en la plataforma de D-Wave.