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. Este matemático demostró que tal ruta no existía dando paso a la Teoría de Grafos, de vital importancia para la formulación de los modelos de programación lineal que representan al TSP y VRP.

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”. El libro incluye cinco rutas que atraviesan Alemania y Suiza, una de las cuales es la solución óptima al TSP.

En 1857, el matemático Hamilton inventa el ‘Juego Icosiano’ para encontrar un circuito que atraviese los veinte vértices del dodecaedro y que cada nodo sea visitado una sola vez regresando al punto de partida.

La matemática Julia Robinson hace la primera referencia al TSP en 1949, con su artículo ‘En el juego Hamiltoniano, un problema del agente viajero’.

En 1959, los matemáticos Dantzig y Ramser publicaron el artículo ‘El problema del despacho de camiones’ referente al VRP con un método de programación lineal obteniendo una solución casi óptima al problema de distribución para estaciones de carburante, con el fin de diseñar las rutas óptimas de una flota de camiones repartidores de gasolina para que se minimice la distancia recorrida y satisfaga la demanda de cada estación de servicio. 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. (O)