Resumen de Matheurísticas para resolver el problema de ruteo de vehículos con ventanas de tiempo

Edwin Montes Orozco, Román Anselmo Mora Gutiérrez, Bibiana Obregón Quintana, Sergio Gerardo de los Cobos Silva, Eric Alfredo Rincón García, Miguel Ángel Gutiérrez Andrade, Pedro Lara Velázquez

• español

  En este trabajo, se presentan dos técnicas matheurísticas basadas en dos técnicas heurísticas: Sistema de hormigas (AS), método de composición musical (MMC) y dos métodos exactos: Algoritmo primal-dual (PDA) y algoritmo simplex dual (DSA). Estas técnicas se denotan como DS-ASPDA y DS-MMC-AS y se caracterizan por aprovechar la información de la estructura y características del modelo matemático para el problema de ruteo de vehículos con ventanas de tiempo (VRP-TW). Con el objetivo de caracterizar el comportamiento de las técnicas propuestas en este trabajo, se utilizaron 29 instancias de prueba para el VRP-TW. Los resultados numéricos, muestran que DS-AS-PDA y DS-MMC-AS presentan un comportamiento robusto y son capaces de generar las mejores soluciones reportadas en la literatura con un número menor de llamadas a la función objetivo para diversos tamaños de instancias.

• English

  In this work, we present two matheuristic techniques based on twoheuristic techniques: Ant system (AS), method of musical composition(MMC) and two exact methods: Primal-dual algorithm (PDA) and dualsimplex algorithm (DSA). These techniques are denoted as DS-AS-PDAand DS-MMC-AS and are characterized by taking advantage of the in-formation of the structure and characteristics of the mathematical modelfor the vehicle routing problem with time windows (VRP-TW). In orderto characterize the behavior of the techniques proposed in this work, weuse 29 test instances for the VRP-TW. The numerical results show thatDS-AS-PDA and DS-MMC-AS exhibit robust behavior and are capableof generating the best solutions reported in the literature with a smallernumber of calls to the objective function.