Aplicación de algoritmos exactos y heurísticos al problema del viajante visible en la red logística de Amazon en Sevilla

Abstract

El problema del viajante es, desde hace muchas décadas, uno de los problemas de optimización más estudiados, a pesar de la aparente simplicidad de su enunciado. En este trabajo, se presenta aplicado a una cuestión de actualidad, la necesidad de las empresas de logística de optimizar sus rutas de reparto, máxime ante el aumento de pedidos online como consecuencia de la pandemia de COVID-19. Para ello, se presentará la red logística de Amazon en Sevilla, estudiando el caso en que un vehículo debe visitar cada uno de los pueblos seleccionados de un determinado distrito de la provincia una única vez, siendo su origen y final el centro logístico de la empresa en Dos Hermanas. Este procedimiento se aplicará de manera individual a los distritos Sur y Oeste (Aljarafe), y de manera conjunta a la comarca Noreste, permitiendo así observar la diferencia de comportamiento con conjuntos de mayor tamaño y, por tanto, con mayores distancias entre ellos. Pudiendo ser atacado por diferentes líneas, en este análisis se optará por comparar los resultados de aplicar algoritmos aproximados y metaheurísticos, por el método del vecino más próximo y colonia de hormigas, respectivamente.

The travelling salesman problem has been, for many decades, one of the most studied optimization problems, despite the apparent simplicity of its statement. In this work, it is presented applied to one current issue, the need of logistics companies to optimize their delivery routes, especially given the increase of online orders as a result of the COVID-19 pandemic. To this end, Amazon’s logistics network in Seville will be presented, studying the scenario in which a vehicle must visit each of the selected towns in a given district only once, starting and ending at the company’s logistics center in Dos Hermanas. This procedure will be applied individually to districts South and West (Aljarafe), and jointly to Northeast region, thus allowing to observe the difference in behavior with larger sets and, therefore, with greater distances between them. Having the possibility of attacking the problem through different approaches, in this analysis results of applying approximation and metaheuristic algorithms will be compared, using the nearest neighbor and ant colony optimization, respectively.