Desde tiempos remotos se ha necesitado transportar bienes o personas, de manera que, utilizando la menor cantidad posible de recursos, se cumpla con la demanda prevista. Así surge el problema del agente viajero (TSP por sus siglas en inglés), que busca minimizar la distancia recorrida por un comerciante o repartidor para que pueda visitar a todos sus clientes una sola vez y regrese a su punto de partida.
El incremento de las necesidades y demandas del mercado hace inevitable modificar el planteamiento del TSP mediante variaciones de sus objetivos y restricciones. Es el caso del ruteo de vehículos (VRP por sus siglas en inglés), una generalización del TSP, pues su demanda es tan alta que es necesario tener varios repartidores. Leonard Euler resolvió el problema de los puentes de Königsberg en 1736 que buscaba encontrar una ruta para recorrer los siete puentes que atravesaban el Río Pregel, pasando por ellos una sola vez y regresando al punto de partida.
En 1832 se publica el libro “El viajante de comercio: cómo debe ser y qué debe hacer para conseguir comisiones y triunfar en el negocio” donde un comerciante alemán describe “la necesidad de encontrar buenas rutas que le permitan visitar la mayor cantidad de localidades posibles sin pasar dos veces por la misma y regresar a su lugar de partida”.
Cinco años después, Clarke and Wright plantean un algoritmo que resultó efectivo para resolver este problema en el artículo ‘Programación de vehículos desde un depósito central a una serie de puntos de entrega’.
Desde entonces fue notable la contribución de Dantzig, Fulkenson y Johnson, quienes desarrollaron un método para resolver una problemática con 49 ciudades y para finales de los años 70 e inicios de los 80, ya se manejaban instancias con 2.392 ciudades usando métodos de planos de corte, ramificación y acotación. En la actualidad, la optimización de rutas es uno de los problemas matemático-computacionales más estudiados.
En el contexto nacional, según el Balance Energético Nacional 2016, por el Ministerio Coordinador de Sectores Estratégicos (Micse), se tiene que el 86% de la energía consumida por el sector transporte la utiliza el terrestre. Es así que el Instituto Nacional de Eficiencia Energética y Energías Renovables (INER) ha desarrollado un modelo matemático de optimización de rutas para el transporte de carga pesada, tomando como base los TSP y VRP, aportando de esta manera a la eficiencia energética en este sector.