Modelación matemática del problema de ruteo de vehículos con restricciones de múltiples depósitos, flota heterogénea de vehículos y ventanas de tiempos 

Abstract

In the present work we propose a mathematical method of mixed integer linear programming (MIP) to solve a vehicle routing problem with constrains of multiples depots, heterogeneous fleet of vehicles and time windows programmed in GAMS, a General Algebraic modeling Software. One of the difficulties presented in approximated methods proposed to solve vehicle routing problems is that the quality of their solutions is not always known and they often are only applicable to solve the specific problems for which they were designed. The presented model not only is capable to solve problems such MDHVRPTW to which it was originally designed but it’s also capable to solve less constrained problems like VRPTW, HVRPTW and MDVRPTW. Another valuable contribution of the presented model is that the model can work as a pattern to prove the quality of the solutions of the approximated methods. The model solve to optimality benchmark problems of 5 and 10 nodes and generates solutions near to optimality with a gap of less than 3% to 15 and 20 nodes problems.

En el presente trabajo se propone un método matemático de programación entera mixta (MIP) para solucionar un problema de ruteo de vehículos con restricciones de múltiples depósitos, flota heterogénea de vehículos y ventanas de tiempo codificado en GAMS, un software de modelación algebraica general. Una de las dificultades que presentan los métodos aproximados para solucionar problemas de ruteo de vehículos es que no siempre se conoce que tan buenas son las soluciones que generan y adicionalmente por lo general solo aplican para resolver el problema específico para el cual fueron diseñados. El modelo presentado no solamente soluciona problemas del tipo MDHVRPTW para el cual fue diseñado sino también es capaz de solucionar problemas con menos restricciones como los VRPTW, HVRPTW y MDVRPTW. Otro aporte valioso del modelo presentado es que sirve de patrón para probar la calidad de las soluciones generadas por métodos aproximados. El modelo resuelve de forma óptima instancias de referencia de 5 y10 nodos y da soluciones muy cercanas al óptimo con una diferencia de menos del 3% para instancias de 15 y 20 nodos.