Desarrollo y Codificación de un Modelo Matemático para la Optimización de un Problema de Ruteo de Vehículos con Múltiples Depósitos (Development and Codification of a Mathematical Model for the Optimization of a Vehicle Routing Problem with Multiple Deposits)
Julián López Franco
Nilson Herazo Padilla
Abstract
This paper presents the development and codification of a strict Mixed Integer Linear Programming formulation, based on the Dondo and Cerdá approach, for the optimization of the multiple depots, heterogeneous fleet and time windows VRP. The aim of this mathematical approach is to evaluate the performance of future works based on heuristic and meta-heuristic algorithms for the MD-VRP, measured as optimality gap capability. In this work, many known instances up to 20 clients are solved to optimality in a time range of 0,5 to 3.000 seconds, comparing different branch and bound strategies.
In Spanish:
Este artículo presenta el desarrollo y codificación de una estricta formulación matemática de Programación Lineal Entera Mixta, basada en el modelo propuesto por Dondo y Cerdá, para la optimización de un VRP con múltiples depósitos, flota heterogénea y ventanas de tiempo. El objetivo del desarrollo matemático completo, a pesar de su complejidad computacional para la resolución del mismo, es la evaluación del desempeño para trabajos futuros basados en procedimientos heurísticos y meta-heurísticos para el MD-VRP, en cuanto a su capacidad para generar soluciones muy cercanas al óptimo global. En este trabajo se resuelven a nivel óptimo instancias conocidas de hasta 20 clientes en tiempos entre 0,5 a 3.000 segundos, comparando diferentes estrategias de ramificación y acotamiento.