Modelos para optimizar rutas de transporte
JPA/DICYT El Departamento de Economía Aplicada de la Universidad de Burgos estudia modelos para optimizar rutas de transporte. Los resultados de estas investigaciones se plasman en una tesis doctoral de Amaya Martínez Puras, que ha sido dirigida por el profesor Joaquín Antonio Pacheco Bonrostro y que su autora defenderá el próximo jueves.
En este trabajo se ha desarrollado una metodología ad hoc basada en búsqueda tabú para la resolución de un problema bi-objetivo en el contexto del PVRP (Periodic Vehicle Routing Problem). El problema consiste en diseñar las rutas diarias de una empresa de Análisis Químicos de Salamanca a lo largo de un horizonte de planificación y la asignación de los calendarios de visita a sus clientes. El objetivo del problema es doble: reducción de los costes y reducción de las modificaciones sobre los calendarios actuales de los clientes, según la información de la Universidad de Burgos recogida por DiCYT.
Una de las principales aportaciones de este trabajo es que se han considerado como un nuevo objetivo las preferencias y costumbres adquiridas por los clientes con el fin de garantizar la calidad del servicio y mantener buenas relaciones con ellos. Esta consideración sólo había sido tratada en el trabajo de Gulczynski et al. (2011). Estos autores plantean las diferencias en las asignaciones de calendarios a clientes como restricciones y no como un nuevo objetivo.
Desde el punto de vista metodológico, la estrategia empleada para la resolución de este nuevo modelo es una adaptación del procedimiento MOAMP (MultiObjective Adaptative Memory Procedure) para problemas multiobjetivo. MOAMP se basa en dos principios y se desarrolla en tres fases. En las dos primeras fases crea una aproximación a la curva de eficiencia enlazando la ejecución de una serie de procedimientos de búsqueda tabú. Primero, usa las funciones objetivo originales y después funciones mixtas que son combinaciones ponderadas de las funciones originales. En la tercera fase realiza una exploración vecinal en torno a las soluciones no dominadas obtenidas hasta ese momento.
Para acelerar algunos procedimientos se utilizan dos métodos de aceleración: búsqueda local rápida y movimientos por índices. Estos métodos consiguen reducciones considerables en los tiempos de computación.
Finalmente, con el fin de examinar la ‘bondad’ de los resultados obtenidos por el procedimiento diseñado, se comparan los mismos con una adaptación de NSGA II (Non- Dominated Sorting Genetic Algorithm). Para este propósito se generan una serie de instancias seudo reales de distintos tamaños con las que se realizan pruebas computacionales.
La conclusión final es que con la estrategia MOAMP se obtienen curvas de eficiencia más densas y con un mayor número de soluciones que las obtenidas con NSGA II. Además, las soluciones obtenidas con NSGA II son dominadas por soluciones MOAMP. Por consiguiente, se puede concluir que el diseño de estrategias basadas en MOAMP y adaptadas al problema produce mejores resultados, aunque también conlleva un trabajo adicional de diseño e implementación.