Mejora de las modelizaciones QUBO del problema del viajante y enrutamiento de vehículos para su resolución mediante Quantum Annealing

Abstract

El objetivo de este TFG consiste en construir una función con ciertas propiedades, de manera que mediante la herramienta denominada Quantum Annealing (atemperamiento cuántico) se resuelva el siguiente problema propuesto por la empresa Lighthouse Disruptive Innovation Group LLC. Supongamos que tenemos un almacén donde están localizados un número N de pedidos. Contamos con Q robots que van a ser los encargados de coger los pedidos y llevarlos al punto desde donde van a ser distribuidos. En el artículo qRobot: A Quantum computing approach in mobile robot order picking and batching problem solver optimization [2], desarrollado entre otros por Parfait Atchadé (empresa Lighthouse e investigador de la universidad Ramon Llull) y Guillermo Alonso (UVa), se dan todos los detalles acerca del problema y su resolución cuando se busca minimizar la distancia total que recorren los robots. El propósito de este TFG será resolver el problema consistente en minimizar el tiempo que tardan los robots en recoger todos los pedidos o, lo que es equivalente, minimizar el máximo de las distancias que recorre cada robot. Aparte de la modelización y del código (en Python) necesarios para resolver el problema, lo extenso del trabajo será un desarrollo sobre en qué consiste el algoritmo Quantum Annealing, centrándonos en exponer las matemáticas que ayudan a entender cómo realizar buenas modelizaciones.