Revisando el problema de contaminación y trazado de rutas

Revisando el problema de la contaminación

Revisando el problema de la contaminación

Dr. Yasel Costa, Profesor de ZLC.

Leer versión en inglés

El Problema del Viajante de Comercio “Dada una lista de ciudades y las distancias entre cada par de ciudades, ¿Cuál es la ruta más corta posible para visitar cada ciudad exactamente una vez y volver a la ciudad de origen?” es un clásico de las matemáticas, mencionado por primera vez en 1832 y estudiado seriamente durante casi cien años. La investigación sobre su variante, el Problema de Enrutamiento de Vehículos (VRP por sus siglas en inglés), cuyo objetivo es minimizar el coste total de ruta, se remonta a 1959.

Hay muchas soluciones disponibles, exactas o heurísticas. ¿Por qué, entonces, investigadores del Reino Unido, Países Bajos y Estados Unidos y yo mismo hemos retomado este tema? La respuesta corta es que el VRP clásico no responde plenamente a las necesidades y preocupaciones de los planificadores de rutas actuales. En concreto, los costes que hay que minimizar no son sólo en dinero, sino también en emisiones de gases de efecto invernadero, y estos no son una simple función de kilometraje. De ahí que se le cambie a menudo el nombre por Problema de Contaminación y Trazado de Rutas (PRP por sus siglas en inglés). Además, para ser útiles en la práctica, las soluciones al VRP/PRP deben reconocer una serie de limitaciones que a menudo se ignoran en la formulación clásica.

Entre ellas está el tiempo: la ruta debe poder completarse dentro del turno de un conductor, puede haber requisitos para que determinadas entregas se realicen en franjas horarias específicas, y la velocidad de los vehículos debe ser legal y factible (teniendo en cuenta el tráfico). La velocidad también es un factor que influye en el consumo de combustible y, por tanto, en la producción de emisiones (véase el caso de las estrategias de reducción de la velocidad, muy extendidas actualmente en logística para reducir el consumo de combustible).

Además, una solución útil para el PRP debe tener en cuenta el hecho de que, a medida que continúa la ronda de entregas, la carga transportada se hace más ligera, por lo que, si los demás factores no varían, el consumo de combustible disminuye.

También está la cuestión de la geografía. A los matemáticos les encanta modelizar sucesos que ocurren en una penillanura infinita y sin relieve, pero el mundo real tiene topografía -cuesta arriba y cuesta abajo- lo que tiene efectos significativos tanto en la velocidad como en el consumo de combustible. Aunque muchos modelos PRP incluyen en los parámetros iniciales un coeficiente para la pendiente de la carretera, esto no suele aplicarse en detalle a la metodología de la solución.

Hay otras limitaciones que pueden parecer obvias, pero que se olvidan fácilmente. Por ejemplo, el vehículo no puede cargarse por encima de su capacidad; cada ruta empieza y termina en el almacén de origen; cada cliente es visitado una única vez y exactamente por un único vehículo (¡No podemos tener fracciones de camiones en el modelo!).

Así pues, hemos abordado de nuevo el “Problema de Contaminación y Trazado de Rutas con Optimización de la Velocidad y Topografía Desigual”, que es el título de nuestro artículo en el número 164 de la revista “Computers & Operations Research”. (Visita esta página para leer el artículo completo).

Hemos adoptado dos enfoques. En ambos, tratamos de construir rutas que minimicen la suma de los costes variables de ruta (combustible, contaminación) y los costes fijos de conducción (costes del vehículo, salarios del conductor y otros), optimizando al mismo tiempo la velocidad de los vehículos para reducir emisiones/consumo de combustible sin incumplir las franjas horarias de los clientes. Al mismo tiempo, calculamos el consumo de combustible teniendo en cuenta la información real sobre el terreno (es decir, sin presuponer una pendiente constante o media en la carretera a lo largo de toda la ruta).

Los dos enfoques que exploramos son, en primer lugar, un algoritmo de “Branch and Price” que dará soluciones exactas y, en segundo lugar, un enfoque metaheurístico de “Búsqueda Tabu” para casos de escala media a grande (25, 50, incluso 100 destinos). La clave de la eficacia de ambos enfoques es nuestro novedoso algoritmo de optimización de la velocidad.

Probamos las soluciones que hemos propuesto con dos tipos de conjuntos de datos. En primer lugar, adaptamos (añadiendo información generada aleatoriamente sobre pendientes de ruta) conjuntos de datos tomados de la investigación de autores anteriores sobre VRP. En segundo lugar, creamos un conjunto de datos del mundo real basado en la red de distribución de un gran distribuidor de productos de salud y belleza (que atiende a 248 clientes en Hong Kong). Esto proporciona una buena agrupación de destinos en distritos centrales, además de otros lugares más remotos, y mucha topografía, desde pendientes moderadas hasta escarpadas.

También pudimos utilizar el conjunto de datos del mundo real para modelizar los efectos de la reducción de la carga útil en arcos (tramos de ruta) más inclinados, es decir, realizando primero el mayor número posible de entregas en zonas menos inclinadas. (Por supuesto, hay razones no relacionadas con el coste por las que los camiones muy cargados pueden no ser apropiados en las partes más escarpadas de la ruta y se trata de un aspecto que futuras investigaciones podrían integrar con nuestro modelo).

En los ensayos, nuestro enfoque “Branch and Price” encontró la solución óptima exacta en 61 de 116 casos, incluyendo todos los casos de hasta 25 clientes, la mayoría de los casos de hasta 50 clientes y muchos con hasta 100 clientes, en un tiempo razonable. El enfoque metaheurístico encontró soluciones casi óptimas para todos los casos, cada una de ellas en menos de un minuto de tiempo de cálculo. Esto sugiere que el método puede ser realmente útil para la gestión.

En términos más generales, la aplicación de nuestras soluciones al mundo real arroja una serie de ideas para la gestión. Si se tienen en cuenta las cargas útiles y las inclinaciones de arco, permite ahorrar hasta un 53% en combustible/emisiones. El ahorro puede lograrse programando los clientes “situados en la parte de arriba en la cuesta” más adelante en la ruta, cuando la carga útil se ha reducido. (Obsérvese que este ahorro se produce incluso si la ruta planificada no es la más corta posible). Mientras tanto, también hemos demostrado que, si se ignora la elevación/pendiente a la hora de planificar las rutas, es probable que las estimaciones de consumo de combustible y, por tanto, los costes económicos y de emisiones, sean muy inexactos.

 

Para más información, consulte nuestro documento (referencia anterior) o póngase en contacto con el Dr. Yasel Costa en [email protected]

×