Taxonomía de los problemas de ruteo de vehículos

Abstract

El problema de enrutamiento o ruteo de vehículos (VRP, vehicle routing problem) data del año de 1959 y fue introducido por Dantzig y Ramser, quienes describieron una aplicación real de la entrega de gasolina a las estaciones de servicio y propusieron una formulación matemática (Arias, 2015). En las últimas décadas se ha aumentado la preocupación por determinar cuáles son las formas más eficientes de transportar cargas o personas de un lugar a otro, con el mínimo costo de combustible, desgaste e impacto al medio ambiente. Existen en la actualidad miles de estudios sobre ruteo de vehículos, todos ellos con variantes del VRP; es+ por eso que se encuentra la necesidad de caracterizar cada una de estas, clasificándolas en este documento para generar un estado del arte para los posteriores investigadores y que se tome esta referencia, con información clara y ordenada sobre los problemas de ruteo de vehículos, en adelante VRP, y sus variantes metaheurísticas. "Debido a que estos problemas son considerados difíciles de resolver y dentro de la optimización combinatoria son conocidos como problemas NP-Hard o de explosión combinatoria, pues no se obtiene una solución de manera eficiente; así mismo dentro de la teoría de la complejidad computacional pertenecen a la clase NP-Completos, lo que indica que no se puede garantizar encontrar la mejor solución en un tiempo de cómputo razonable…"(Arias, 2015).