Modelos reales de problemas simultáneos de rutas y planificaciónequilibrio entre prioridades del cliente y reducciones de costes

Resumen

En este trabajo se ha desarrollado una metodología ad hoc basada en búsqueda tabú para la resolución de un problema multiobjetivo en el contexto del PVRP (Periodic Vehicle Routing Problem). El problema consiste en diseñar las rutas diarias de una empresa a lo largo de un horizonte de planificación y la asignación de los calendarios de visita a sus clientes. Cuando una empresa solicita que se racionalice su planificación de entrega de productos/servicios a clientes a lo largo de un horizonte temporal, normalmente se requiere la reducción de los costes de las operaciones (coste de las rutas). Sin embargo, se ha observado que esta nueva planificación suele ser significativamente diferente de la empleada hasta ese momento. Este hecho, no suele ser bien recibido por los clientes ya que supone la modificación de sus hábitos o costumbres. Por consiguiente, al plantear el problema debemos considerar, además de la reducción de los costes, la repercusión de los cambios realizados o la minimización de éstos. Por tanto, el problema, así planteado, es claramente biobjetivo: reducción de los costes y reducción de las modificaciones sobre los calendarios actuales de los clientes. En este trabajo se resuelve un problema real propuesto por una empresa de Análisis Químicos de Salamanca. Esta empresa está interesada en la planificación de los calendarios de visita a sus clientes tratando de respetar sus prioridades y el diseño de las rutas diarias. Una de las principales aportaciones es que se ha 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. Este hecho sólo ha sido tratado 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: 1) la proximidad de los puntos eficientes; y 2) la solución que minimiza la distancia L¿ normalizada y/o ponderada al punto ideal es también eficiente. La estrategia MOAMP 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ú, es decir, algoritmos que utilizan como solución inicial, la solución final resultante de la ejecución anterior. Primero, usa las funciones objetivo originales y después funciones mixtas que son combinaciones ponderadas de las funciones originales. Para terminar, en la tercera fase se 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: 1) Una estrategia de búsqueda local rápida para acelerar el algoritmo de búsqueda local para el diseño de las rutas diarias; 2) La modificación del conjunto de soluciones no dominadas mediante el uso de movimientos por índices que aceleran toda la estrategia MOAMP. Con estos métodos se consiguen reducciones considerables sobre los tiempos de computación. Finalmente, con el fin de examinar la `bondad¿ de los resultados obtenidos por el procedimiento diseñado para la resolución de este problema, se comparan los mismos con una adaptación del conocido algoritmo 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.