DISEÑO E IMPLEMENTACIÓN DE UNA BÚSQUEDA TABÚ PARA EL ...bibing.us.es/proyectos/abreproy/12034/fichero/proyecto+VRP+formato+_1_.pdf · deduce que el impacto medioambiental del

DISEÑO E IMPLEMENTACIÓN DE UNA BÚSQUEDA TABÚ PARA EL PROBLEMA DE RUTADO DE

VEHÍCULOS CON CRITERIOS DE SOSTENIBILIDAD

2012

Ingeniero de telecomunicación

Autor :Fernando Benavides Madrid

Tutor : Jesús Racero Moreno

2

TABLA DE CONTENIDOS

INDICE DE FIGURAS Y TABLAS ............................................................................. 5

INDICE DE TABLAS .............................................................................................. 7

RESUMEN ............................................................................................................ 9

1. INTRODUCCIÓN Y OBJETIVOS ....................................................................... 11

1.1. Introducción .............................................................................................................. 11

1.2. Objetivos................................................................................................................... 16

1.3. Estructura del documento ........................................................................................... 16

2. REVISIÓN DE LA LITERATURA ........................................................................ 19

2.1. Algoritmos ................................................................................................................. 19

2.1.1. Introducción .................................................................................................................. 19

2.1.2. Características del problema ........................................................................................... 20

2.1.3. Variantes y extensiones del VRP ...................................................................................... 21

2.1.4. Métodos de resolución exactos ........................................................................................ 24

2.1.5. Métodos de resolución Heurísticos ................................................................................... 24

2.1.6. Metaheurísticas .............................................................................................................. 31

2.2. Análisis de costes de sostenibilidad en el transporte ...................................................... 42

3. DISEÑO DE LA BÚSQUEDA TABÚ .................................................................... 45

3.1. Descripción del problema ............................................................................................ 45

3.2. Diseño de la Búsqueda Tabú ....................................................................................... 50

3.2.1. Solución inicial Mole-Jameson ......................................................................................... 50

3.2.2. Movimiento λ-opt ........................................................................................................... 55

3.2.3. Búsqueda Tabú .............................................................................................................. 56

3.2.4. Ampliaciones.................................................................................................................. 57

4. IMPLEMENTACIÓN DE CLASES ....................................................................... 65

4.1. Descripción de clases ................................................................................................. 66

4.1.1. Clase Solución ................................................................................................................ 67

4.1.2. Clase Movimiento ........................................................................................................... 80

4.1.3. Clase ListaTabu .............................................................................................................. 80

4.2. Interfaz de usuario ..................................................................................................... 81

4.2.1. Aplicación en pantalla ..................................................................................................... 81

4.2.2. Ficheros de entrada y salida ........................................................................................... 83

5. RESULTADOS ................................................................................................ 91

5.1. Reducción de los costes de la BT sobre la heurística de Mole. ........................................ 91

3

5.2. Evolución de costes según el criterio de asignación de la primera ciudad ........................ 92

5.3. Admisibilidad versus no admisibilidad ........................................................................... 94

6. CONCLUSIONES Y EXTENSIONES ................................................................... 97

6.1. Conclusiones ............................................................................................................. 97

6.2. Extensiones ............................................................................................................... 97

5

INDICE DE FIGURAS Y TABLAS

LISTA DE FIGURAS

FIGURA 1. EMISIONES DE GEI, SUSTANCIAS ACIDIFICANTES Y PRECURSORES DEL OZONO TROPOSFÉRICO PROCEDENTES DEL

TRANSPORTE (MARM) .......................................................................................................................... 11

FIGURA 2. EMISIONES TOTALES DE GEI (AEMA/MARM) ................................................................................ 13

FIGURA 3. VOLUMEN DE TRANSPORTE DE MERCANCÍAS EN UE-27. (EEA) ............................................................ 13

FIGURA 4. CONTRIBUCIÓN POR SECTORES DE TRANSPORTE A LAS EMISIONES TOTALES DE GEI EN UE. (EEA) ............... 14

FIGURA 5. EMISIONES DE GEI DE TRANSPORTE EN UE. (EEA) ............................................................................ 14

FIGURA 6. PRECIOS DE COMBUSTIBLE NOMINAL Y REAL (UE-27) ......................................................................... 15

FIGURA 7. CONTRIBUCIÓN DEL SECTOR TRANSPORTE AL TOTAL DE LAS EMISIONES DE LOS PRINCIPALES CONTAMINADORES

DE AIRE EN 2009 EN UE-32 (EEA). ......................................................................................................... 15

FIGURA 8. REPRESENTACIÓN GRÁFICA DEL PROBLEMA VRP ................................................................................ 19

FIGURA 9. DOS RUTAS ANTES Y DESPUÉS DE SER UNIDAS .................................................................................... 25

FIGURA 10. TODOS LOS 3-INTERCAMBIOS POSIBLES PARA LOS ARCOS MARCADOS ......................................... 30

FIGURA 11. FASES DE LA BÚSQUEDA TABÚ ........................................................................................... 50

FIGURA 12. DIAGRAMA DE FLUJO DEL ALGORITMO DISEÑADO EN BASE A MOLE-JAMESON ............................. 52

FIGURA 13. POSIBILIDADES DE LLEGADA DE UN VEHÍCULO R A UNA CIUDAD VK. ............................................. 53

FIGURA 14. PSEUDOCÓDIGO DE FORMACIÓN DE ELIMINACIÓN DE ARCOS EN OPERADOR Λ-INTERCAMBIO .......... 55

FIGURA 15. PSEUDOCÓDIGO DE FORMACIÓN DE MOVIMIENTOS EN BT. ...................................................... 57

FIGURA 16. BUCLE EN BT .................................................................................................................. 57

FIGURA 17. EFECTO DE LA DIVERSIFICACIÓN E INTENSIFICACIÓN EN EL ESPACIO DE SOLUCIONES ....................... 58

FIGURA 18. DIAGRAMA DE FLUJO DE LA BÚSQUEDA TABÚ ....................................................................... 60

FIGURA 19. PSEUDOCÓDIGO DE FORMACIÓN DE INSERCIONES EN BT ......................................................... 63

FIGURA 20. VENTANA PRINCIPAL DE C++BUILDER .................................................................................. 65

FIGURA 21. FICHEROS IMPLICADOS EN LAS TRES FASES DE LA APLICACIÓN .................................................... 67

FIGURA 22. RELACIÓN ENTRE FICHEROS, CLASES Y FASES DE LA APLICACIÓN ................................................. 67

FIGURA 23. COSTES CONSIDERADOS EN LA INSERCIÓN DE UNA NUEVA CIUDAD ENTRE UN PAR DE NODOS ........... 72

FIGURA 24. PSEUDOCÓDIGO DE ALGORITMO M&J ................................................................................. 73

FIGURA 25. RUTA ALEATORIA CON ELIMINACIÓN DE ARCOS PARA MOVIMIENTO 3-OPT .................................. 75

FIGURA 26. RUTA EN FORMA DE VECTOR PARA LA MANIPULACIÓN DE LOS MÉTODOS OPT ............................... 75

FIGURA 27. EVOLUCIÓN DE RECONEXIONES EN UNA RUTA EN MÉTODOS OPT ............................................... 76

FIGURA 28. PSEUDOCÓDIGO DE MÉTODO INTER_SWAPPING E INTER_SWAPPINGCONT ............................... 79

FIGURA 29. VENTANA PRINCIPAL DE LA APLICACIÓN ................................................................................ 82

FIGURA 30. RELACIÓN ENTRE FICHEROS DE ENTRADA/SALIDA, PARÁMETROS DE USUARIO Y APLICACIÓN ............ 84

FIGURA 31. ORGANIZACIÓN DE LA INFORMACIÓN EN EL FICHERO DE ENTRADA ............................................. 85

FIGURA 32. CATEGORÍAS DE LOS VEHÍCULOS EN EL FICHERO DE ENTRADA .................................................... 85

FIGURA 33. COMBUSTIBLES EN EL FICHERO DE ENTRADA .......................................................................... 85

FIGURA 34. CARACTERÍSTICAS DE LOS VEHÍCULOS EN FICHERO DE ENTRADA. ................................................ 86

FIGURA 35. CARACTERÍSTICAS DE LOS CLIENTES EN FICHERO DE ENTRADA .................................................... 86

6

FIGURA 36. GRAFO EN EL FICHERO DE ENTRADA ..................................................................................... 87

FIGURA 37. GEI EN EL FICHERO DE ENTRADA ......................................................................................... 87

FIGURA 38. CONTAMINANTES EN EL FICHERO DE ENTRADA ....................................................................... 87

FIGURA 39. ORGANIZACIÓN DE LA INFORMACIÓN EN EL FICHERO DE SALIDA ................................................. 88

FIGURA 40. ORGANIZACIÓN DE LA INFORMACIÓN PARA CADA ARCHIVO DE ENTRADA EN EL FICHERO DE SALIDA ... 88

FIGURA 41. CABECERA RESUMEN DE DATOS DE ENTRADA EN EL FICHERO DE SALIDA ....................................... 88

FIGURA 42. SOLUCIÓN INICIAL M&J Y λ-INTERCAMBIO EN EL FICHERO DE SALIDA ......................................... 89

FIGURA 43. EVOLUCIÓN DE COSTES E ITERACIONES EN BT EN EL FICHERO DE SALIDA ...................................... 89

FIGURA 44. RESUMEN DE HITOS EN BT EN EL FICHERO DE SALIDA .............................................................. 90

FIGURA 45. MEJORA DE COSTES DE TIEMPO SEGÚN EL CRITERIO DE ELECCIÓN DE LA PRIMERA CIUDAD. .............. 92

FIGURA 46. MEJOR DE COSTES DE CONTAMINACIÓN SEGÚN EL CRITERIO DE ELECCIÓN DE LA PRIMERA CIUDAD. ... 92

FIGURA 47. EVOLUCIÓN DE COSTES EN LA BÚSQUEDA TABÚ SEGÚN LA ELECCIÓN DE LA PRIMERA CIUDAD

(ESTACIONARIO). .................................................................................................................................. 93

FIGURA 48. EVOLUCIÓN DE LOS COSTES EN LA BÚSQUEDA TABÚ SEGÚN LA ELECCIÓN DE LA PRIMERA CIUDAD

(TRANSITORIO). .................................................................................................................................... 94

FIGURA 49. EVOLUCIÓN DE LOS COSTES DE CONTAMINACIÓN SEGÚN LA ADMSIBILIDAD DE LA SOLUCIÓN ........... 95

7

INDICE DE TABLAS

LISTA DE TABLAS TABLA 1. OBJETIVOS EN LA LUCHA CONTRA EL CAMBIO CLIMÁTICO (PERFIL AMBIENTAL ESPAÑA 2010, PÁG. 47, MMA) ......................... 12

TABLA 2. VARIABLES DE LA CLASE SOLUCIÓN .............................................................................................................................. 70

TABLA 3. EJEMPLO DE SOLUCIÓN CON CUATRO RUTAS ASIGNADAS POR COLORES ............................................................................... 71

TABLA 4. CONTENIDO DE RUTACTUAL PARA UNA RUTA {0-2-4-1-0} ............................................................................................... 72

TABLA 5. VARIABLES DE LA CLASE MOVIMIENTO ......................................................................................................................... 80

TABLA 6. VARIABLES DE LA CLASE LISTATABU ............................................................................................................................. 81

9

RESUMEN

En la última década, el desarrollo de normativas ambientales ha aumentado la presión sobre los productores animándolos a incluir la componente medioambiental en la toma de decisiones. La gestión integrada de la cadena de suministros se ha visto afectada en varios aspectos, tales como la ubicación, el abastecimiento de materias prima de fabricación o de la planificación del transporte. Este último punto se aborda en el documento presente, que pretende proporcionar una nueva gestión sostenible y eficiente que integre estos nuevos factores.

Este trabajo, por tanto, se centra en el análisis de los principales factores ambientales involucrados en la actividad del transporte y su integración con los costes clásicos de operación de una flota de vehículos para el desarrollo de una aplicación interactiva que resuelva el problema del enrutamiento, analizando a posteriori el efecto sobre las rutas originales.

La inclusión de este nuevo concepto ambiental al modelo clásico del enrutamiento de vehículos aporta una visión más realista del problema y pretende satisfacer las necesidades presentes y futuras en el campo del transporte en relación a un desarrollo sostenible de la actividad. En concreto, se añaden nuevos costes atendiendo a las diferentes tipologías de combustibles y normativas de emisiones a los consabidos de mantenimiento y operación, además de respetarse restricciones de carga, tiempo en ruta y de atención al cliente.

Este nuevo modelo resuelve la problemática del VRP en dos pasos: la creación de una solución inicial en base a una heurística de Mole-Jameson y su posterior optimización a través de una búsqueda tabú personalizada. Los parámetros configurables para adaptar ambos pasos, se presentan vía interfaz interactiva programada en C++, donde se modifican el tipo de función objetivo, algoritmos de selección de vehículo, inclusión de movimientos OPT, tamaños de listas tabú, admisibilidad de carga y tiempo de ejecución entre otros.

Las combinaciones posibles que se pueden generar con los parámetros descritos anteriormente son muy numerosas. De ahí, que en un último aparatado se ejecuten en la aplicación ejemplos bien conocidos de Christofides y Taillard con las combinaciones más representativas y se discuta posteriormente la repercusión que la inclusión de los costes medioambientales tiene en el diseño de rutas cuyo objetivo es el minimizar tiempo o distancia.

1. INTRODUCCIÓN Y OBJETIVOS

1.1. Introducción

En pleno siglo XXI ya pocos son los que dudan de la existencia de un cambio climático global en el planeta. En los últimos años, la investigación científica sobre el cambio climático se ha desarrollado considerablemente, y se ha confirmado que las actividades humanas, como la quema de los carburantes fósiles, son muy probablemente las responsables del cambio climático. El calentamiento del planeta ya está teniendo muchas consecuencias cuantificables y en el futuro esperan cambios de gran envergadura.

El transporte es una de las actividades humanas que aporta una cantidad considerable de los denominados gases de efecto invernadero (CO2, CFCs, CH4 y NO2 entre otros), responsables de la contención de la energía solar que devuelve de forma natural la Tierra a la atmósfera. El Acuerdo de Copenhague (2009), que toma el testigo del Protocolo de Kyoto (1997), establece un umbral en el aumento de los niveles de emisiones de GEI debido a tráfico rodado del 23% al 32% [1]. Por tanto, se deduce que el impacto medioambiental del transporte a nivel global en términos de emisiones de GEI es de casi un tercio.

En España, desde 1990-2008 el incremento del volumen total de gases de efecto invernadero en la atmósfera procedente del transporte por carretera, que representa un 65,8% del consumo energético del total del transporte [2], es del 80,4% (Figura 1). En concreto, en el año 2009 el CO2 fue supuso el 80,8% (11% menos que en el 2008) del total de las emisiones de GEI en territorio nacional, seguido por CH4 y N2O (9,9% y 7,1%).

Figura 1. Emisiones de GEI, Sustancias acidificantes y precursores del ozono troposférico procedentes del transporte (MARM)

DISEÑO E IMPLEMENTACIÓN DE UNA BÚSQUEDA TABÚ PARA EL VRP CON CRITERIOS DE SOSTENIBILIDAD

12

La creciente preocupación por disminuir estos niveles de GEI (se espera que el incremento entre 2008-2012 no supere un +37% [3]) ha supuesto la creación de distintos organismos gubernamentales (entre ellos el OMM, Observatorio de Movilidad Metropolitana) que promueven medidas (véase Tabla 1) y políticas [4] para incentivar la sostenibilidad del transporte a nivel público y privado, con el fin último de cumplir con uno de los objetivos citados en el informe para la gestión del medioambiente de la OCDE sobre la calidad del aire: “Mejorar la planificación y gestión de la calidad del aire a través de una mejor integración de las políticas de calidad del aire en la planificación a escala regional/local (en especial, la planificación del transporte); fortalecer los organismos responsables de hacer cumplir las normativas sobre calidad del aire y la capacidad a todos los niveles de gobierno”. Además se prevén “subvenciones al transporte en función de la implantación de criterios de eficiencia” que impulsen al sector público y privado a adoptar sistemas que optimicen el transporte eco-eficiente.

Tabla 1. Objetivos en la lucha contra el cambio climático (Perfil Ambiental España 2010, pág. 47, MMA)

Según los datos del Ministerio de Medio Ambiente de España de 2010 [5], España está en el camino de poder cumplir los acuerdos establecidos en El Protocolo de Kyoto y refrendados en La Cumbre de Cancún (2010) en materia de emisiones de CO2, ya que desde 2008 hasta la fecha se está experimentando una reducción sensible del volumen total de GEI emitidos a la atmósfera. Aunque bien es cierto, que uno de los factores cruciales de dicho descenso ha sido el impacto de la recesión económica sobre las actividades industriales y de transporte.

1. Introducción y objetivos

13

Figura 2. Emisiones totales de GEI (AEMA/MARM)

En la Unión Europea, en el año 2009 el transporte de mercancías por carretera congregó el 74% [6] del volumen de tráfico total, seguido por el ferrocarril (16%). Desde 1990, el primero ha experimentado un aumento del 25% tal y como se muestra en la figura siguiente:

Figura 3. Volumen de transporte de mercancías en UE-27. (EEA)

La tasa de aumento del transporte de mercancías provoca un impacto medioambiental notable. De hecho, en 2009, el transporte terrestre fue el responsable de hasta el 24 % de las emisiones de gases de efecto invernadero. El transporte por carretera supone hasta el 71% de las emisiones distribuyéndose en un 47 % las emisiones asociadas al transporte de mercancías.


14

Figura 4. Contribución por sectores de transporte a las emisiones totales de GEI en UE. (EEA)

La contaminación por efecto de la actividad humana ha hecho que la UE adopte medidas de calado. Las políticas seguidas, en la unión europea, se han centrado en dos puntos clave: la implantación de directivas asociadas al aumento de la eficiencia energética y reducción de emisiones contaminantes en vehículos (hasta un 60% menos en 2050) y el desarrollo de planes de inter-movilidad que trasvase el transporte de mercancías por carretera a otros modos como el ferrocarril o marítimo.

Figura 5. Emisiones de GEI de transporte en UE. (EEA)

Así mismo, la presión de entidades gubernamentales y los mercados energéticos ha provocado un aumento de los costes de distribución de mercancías (aumento del precio de los combustibles y tasas por contaminación). En este entorno donde los aspectos energéticos y medioambientales han cobrado mayor importancia es necesario ampliar los conceptos de gestión de flotas mediante la consideración en los costes de aspectos ambientales además de los energéticos.


15

Figura 6. Precios de combustible nominal y real (UE-27)

Figura 7. Contribución del sector transporte al total de las emisiones de los principales contaminadores de aire en 2009 en UE-32 (EEA).


16

1.2. Objetivos

El diseño de rutas eficientes es uno de los pilares en la gestión de flotas. No en vano, la determinación de las rutas u orden de reparto de los productos es fundamental en la optimización de costes. Del apartado anterior, se deriva la suma importancia de crear un modelo nuevo de gestión de flota que atienda no sólo a los criterios clásicos de minimización de distancia del rutado completo. De ahí que la motivación principal de este trabajo radique en los siguientes objetivos:

1. Análisis de la problemática ambiental asociada a las emisiones de GEI. En especial, el impacto del tráfico rodado sobre la atmósfera y cadenas de distribución.

2. Revisión del estado del arte del Vehicle Routing Problem (VRP). En concreto, las heurísticas y meta-heurísticas más extendidas dentro de este campo de investigación.

3. Integración de costes medioambientales en la resolución de asignación de rutas a flotas de vehículos. Se examina y adhiere una conversión costes ambientales/costes monetarios del en base a metodologías ya aplicadas para computarlos junto con los criterios clásicos de distancia

4. Diseño e implementación y aplicación de heurísticas y metaheurísticas. Se resuelven computacionalmente archivos con toda la información del terreno y flota de vehículos.

5. Diseño y desarrollo de un sistema de gestión y parametrización necesaria para la ejecución de las heurísticas y metaheurísticas.

6. Análisis del impacto de la internalización de costes. Se examina y discute sobre el efecto de los costes medioambientales en la configuración de las rutas.

7. Líneas abiertas y posibles extensiones. Se proponen mejoras, cambios y nuevas líneas de investigación en base a las potencialidades o dificultades encontradas en la realización del trabajo.

1.3. Estructura del documento

El documento está dividido en siete capítulos. El primer capítulo realiza una breve introducción sobre la problemática medioambiental actual: El cambio climático, las principales actividades humanas responsables de la degradación de la atmósfera, las medidas adoptadas tanto desde España como de la Unión Europea en materia políticas para un transporte más respetuoso con el medio.la penetración del transporte y su influencia en el medioambiente y, en especial, el impacto del transporte y su repercusión sobre las emisiones a la atmósfera en las dos últimas décadas.

En el capítulo 2, se desglosa la literatura que documenta y contextualiza el trabajo. Se revisan los algoritmos más comunes en el estudio VRP, introduciendo los conceptos claves y las técnicas desarrolladas en cada uno de ellos; y se introducen tanto los métodos heurísticos como los meta-heurísticos. Posteriormente, se justifica la internalización de los costes externos medioambientales y se


17

presentan las conversiones utilizadas para casar costes de distinta índole según el INFRAS, ya que se enfatiza en la necesidad de un modelo de gestión del transporte más fidedigno y representativo de la realidad.

El tercer capítulo detalla la descripción del problema, presentando todos los elementos que entran en juego, y se describe en profundidad y conceptualmente la manera de abordarlo. Se representan diagramas de flujo que ayudan a entender la filosofía de resolución y, en su caso, se exponen las modificaciones realizadas sobre el modelo matemático inicial, bien para facilitar el uso cara al usuario o bien para dotar a la aplicación de mayor selectividad y potencia en el criterio de búsqueda.

A continuación, capítulo 4, se define exhaustivamente la estructura de datos que rige la aplicación: la descripción de clases, los ficheros entrada/salida y la interfaz de usuario. Se hace especial hincapié en los miembros clave (vectores, funciones o clases) que permiten entender con mayor fluidez la ejecución del código, así como señalar las correspondencias entre los pasos descritos en los diagramas de flujo con los elementos del código.

Los resultados obtenidos de la aplicación de los algoritmos son mostrado en el capítulo 5, donde se discute la repercusión de la internalización de los costes respecto a aquellas rutas cuyo objetivo es la minimización del tiempo total de rutado, el comportamiento de la aplicación ante distintas configuraciones del problema (criterio de orden de los camiones, movimientos OPT, tamaño de listas tabú, admisibilidad de carga, posición de la inserción de ciudades, etc), las mejores selecciones de parámetros de búsqueda y posibles mejoras futuras en cuanto a la estructuración de la aplicación o enfoque del análisis de programación.

Finalmente, capítulo 8, se extraen las conclusiones a partir de los fenómenos observados en el capítulo anterior. En base a este análisis, se proponen nuevas líneas de investigación o extensiones que añadan valor a la aplicación presentada, ya sea en su vertiente gráfica o desde un punto de vista conceptual y de programación. En muchos casos, son mejoras que se han ignorado durante el desarrollo de la implementación porque no se contemplan dentro del alcance del proyecto.

Finalmente, el capítulo 9 se dedica a la enumeración de las referencias usadas en el texto y el capítulo 10 contiene una información más detallada sobre el código y ejemplos que no se han considerado tan representativos como los mostrados en el apartado 7.

2. REVISIÓN DE LA LITERATURA

2.1. Algoritmos

2.1.1. Introducción

Tradicionalmente, el problema de planificación de rutas de transporte se ha modelado mediante el conocido problema VRP (Vehicle Routing Problem). La resolución de este problema tiene como objetivo determinar las rutas en una red y asignarlas a un conjunto de vehículos minimizando la distancia recorrida y satisfaciendo la demanda de diversos clientes (Figura 8). Las variantes existentes en la formación de rutas son muy diversas y este apartado pretende enumerar quizás las más relevantes dentro de este campo.

Figura 8. Representación gráfica del problema VRP

El problema de distribuir productos desde ciertos depósitos a sus usuarios finales juega un papel central en la gestión de algunos sistemas logísticos y su adecuada planificación puede significar considerables ahorros. Esos potenciales ahorros justifican en gran medida la utilización de técnicas de Investigación Operativa como facilitadoras de la planificación, dado que se estima que los costos del transporte representan entre el 10% y el 20% del costo final de los bienes [7].

En ese sentido, las últimas cuatro décadas han visto un enorme esfuerzo por resolver estos problemas. En 1959, Dantzig y Ramser [8] realizaron por primera vez una formulación del problema para una aplicación de distribución de combustible. Cinco años más tarde, Clarke y Wright [9] propusieron el primer algoritmo que resultó efectivo para su resolución: el popular Algoritmo de Ahorros. A partir de estos trabajos, el área de Ruteo de Vehículos ha crecido de manera explosiva. Por un lado, hacia modelos que incorporen cada vez más características de la realidad, y, por otro lado, en la búsqueda de algoritmos que permitan resolver los problemas de manera eficiente.

Estos modelos y algoritmos deben su éxito, en buena parte, a la evolución de los sistemas informáticos. El crecimiento en el poder de cómputo y la baja en sus costos, ha permitido disminuir los tiempos de ejecución de los algoritmos. Por otro lado, el desarrollo de los Sistemas de Información


20

Geográfica resulta fundamental para lograr una adecuada interacción de los modelos y algoritmos con los encargados de realizar la planificación.

Pero el interés que reviste el área no es puramente práctico. Los Problemas de Ruteo de Vehículos son Problemas de Optimización Combinatoria y pertenecen, en su mayoría, a la clase NP-Hard. La motivación académica por resolverlos radica en que no es posible construir algoritmos que en tiempo polinomial resuelvan cualquier instancia del problema (a no ser que P = NP).

2.1.2. Características del problema

A grandes rasgos un Problema de Ruteo de Vehículos consiste en, dado un conjunto de clientes y depósitos dispersos geográficamente y una flota de vehículos, determinar un conjunto de rutas de costo mínimo que comiencen y terminen en los depósitos, para que los vehículos visiten a los clientes. Las características de los clientes, depósitos y vehículos, así como diferentes restricciones operativas sobre las rutas, dan lugar a diferentes variantes del problema.

� Los clientes

Cada cliente tiene cierta demanda que deberá ser satisfecha por algún vehículo. En muchos casos, la demanda es un bien que ocupa lugar en los vehículos y es usual que un mismo vehículo no pueda satisfacer la demanda de todos los clientes en una misma ruta. Un caso equivalente al anterior ocurre cuando los clientes son proveedores y lo que se desea es recoger la mercadería y transportarla hacia el depósito. También podría ocurrir que la mercadería deba ser transportada a los clientes pero no esté inicialmente en el depósito, sino distribuida en ciertos sitios proveedores. En este caso, los proveedores deben ser visitados antes que los clientes.

En otros casos la demanda no es un bien sino un servicio: el cliente simplemente debe ser visitado por el vehículo. Un mismo vehículo podría, potencialmente, visitar a todos los clientes. En otra variante del problema, cada cliente tiene una ubicación y desea ser transportado hacia otro sitio. Aquí la capacidad del vehículo impone una cota sobre la cantidad de clientes que puede alojar simultáneamente.

Es usual que cada cliente deba ser visitado exactamente una vez. Sin embargo, en ciertos casos se acepta que la demanda de un cliente sea satisfecha en momentos diferentes y por vehículos diferentes.

Los clientes podrían tener restricciones relativas su horario de servicio. Usualmente estas restricciones se expresan en forma de intervalos de tiempo (llamados ventanas de tiempo) en los que se debe llegar al cliente.

En problemas con varios vehículos diferentes podrían existir restricciones de compatibilidad entre éstos y los clientes. En estos casos, cada cliente sólo puede ser visitado por algunos de los vehículos (por ejemplo, algunos vehículos muy pesados no pueden ingresar en ciertas localidades).

� Los depósitos

2. Revisión de la literatura

21

Tanto los vehículos como las mercaderías a distribuir (si las hubiera) suelen estar ubicadas en depósitos. Usualmente se exige que cada ruta comience y finalice en un mismo depósito, aunque este podría no ser el caso en algunas aplicaciones (por ejemplo, podría ser que el viaje debiera finalizar en el domicilio del conductor del vehículo).

En los problemas con múltiples depósitos cada uno de estos tiene diferentes características, por ejemplo, su ubicación y capacidad máxima de producción. Podría ocurrir que cada depósito tenga una flota de vehículos asignada a priori o que dicha asignación sea parte de lo que se desea determinar.

Los depósitos, al igual que los clientes, podrían tener ventanas de tiempo asociadas. En algunos casos debe considerarse el tiempo necesario para cargar o preparar un vehículo antes de que comience su ruta, o el tiempo invertido en su limpieza al regresar. Incluso, por limitaciones de los propios depósitos, podría querer evitarse que demasiados vehículos estén operando en un mismo depósito a la vez (es decir, la congestión del depósito).

� Los vehículos

La capacidad de un vehículo podría tener varias dimensiones, como por ejemplo peso y volumen. Cuando en un mismo problema existen diferentes mercaderías, los vehículos podrían tener compartimentos, de modo que la capacidad del vehículo dependa de la mercadería de que se trate. En general, cada vehículo tiene asociado un costo fijo en el que se incurre al utilizarlo y un costo variable proporcional a la distancia que recorra.

Los problemas en que los atributos (capacidad, costo, etc.) son los mismos para todos los vehículos se denominan de flota homogénea, y, si hay diferencias, de flota heterogénea. La cantidad de vehículos disponibles podría ser un dato de entrada o una variable de decisión. El objetivo más usual suele ser utilizar la menor cantidad de vehículos y minimizar la distancia recorrida ocupa un segundo lugar.

Regulaciones legales podrían imponer restricciones sobre el tiempo máximo que un vehículo puede estar en circulación e incluso prohibir el pasaje de ciertos vehículos por ciertas zonas. En algunos casos se desea que la cantidad de trabajo realizado por los vehículos (usualmente el tiempo de viaje) no sea muy dispar.

En general se asume que cada vehículo recorre una sola ruta en el período de planificación, pero últimamente se han estudiado modelos en los que un mismo vehículo puede recorrer más de una ruta.

2.1.3. Variantes y extensiones del VRP

En esta sección se formulan algunos de los problemas clásicos y sus extensiones como problemas de Programación Entera. Dichas formulaciones se dan por completitud y para evitar ambigüedad en la definición, pero no se reportan en este trabajo métodos exactos de resolución.

La red de transporte por la que circulan los vehículos se modela mediante un grafo ponderado G =

(V,E,C). Los nodos del grafo representan a los clientes y depósitos. En problemas con un depósito y n


22

clientes, el nodo 0 representa al depósito y los nodos 1,…,n a los clientes. En algunos casos (en que se explicitará) se agrega una copia del depósito etiquetada con n+1 para simplificar la formulación.

Cada arco (i,j) ϵ E representa el mejor camino para ir desde el nodo i hacia el nodo j en la red de transporte y tiene asociado un costo cij y un tiempo de viaje tij. Según la estructura de los costos y los tiempos y las características de la red, el grafo puede ser simétrico o asimétrico. Puede suponerse que G es completo, pues entre todo par de lugares de una red de transporte razonable, debería existir algún camino. Sin embargo, por una cuestión de flexibilidad, los modelos serán planteados sin realizar dicha hipótesis.

Denotaremos por ∆+(i) y ∆-(i) al conjunto de nodos adyacentes e incidentes al nodo i, es decir, ∆+(i) =

{j ϵ V | (i, j) ϵ E} y ∆-(i) = {j ϵ V | (j, i) ϵ E}. De manera similar, el conjunto de arcos incidentes hacia

el exterior e interior del nodo i se definen como δ+(i) = {(i, j) ϵ E} y δ−(i) = {(j, i) ϵ E}.

� El Problema del Agente Viajero (TSP)

En el Problema del Agente Viajero (o TSP por Travelling Salesman Problem) se dispone de un solo vehículo que debe visitar a todos los clientes en una sola ruta y a costo mínimo. No suele haber un depósito (y si lo hubiera no se distingue de los clientes), no hay demanda asociada a los clientes y tampoco hay restricciones temporales.

La mayor parte de los problemas de ruteo de vehículos son generalizaciones del TSP. En ese sentido, este puede considerarse el problema de ruteo de vehículos más simple. No obstante, pertenece a la clase de problemas NP-Hard y es uno de los problemas de optimización combinatoria más clásico y difundido.

� El Problema de los m Agentes Viajeros (m-TSP)

El Problema de los m Agentes Viajeros o m-TSP es una generalización del TSP en la cual se tiene un depósito y m vehículos. El objetivo es construir exactamente m rutas, una para cada vehículo, de modo que cada cliente sea visitado una vez por uno de los vehículos. Cada ruta debe comenzar y finalizar en el depósito y puede contener a lo sumo p clientes. La formulación es la siguiente:

( , )

min∈∑ ij ij

i j E

c x

0(0)

. .+∈∆

=∑ jj

s a x m (2.1)

{ }( )

1, \ 0+∈∆

= ∀ ∈∑ ijj i

x i V (2.2)

{ }( )

1, \ 0−∈∆

= ∀ ∈∑ iji j

x j V (2.3)

1, ( , ) , 0, 0− + ≤ − ∀ ∈ ≠ ≠i j iju u px p i j E i j (2.4)


23

{ }0,1 , ( , )∈ ∀ ∈ijx i j E

{ }0, \ 0≥ ∀ ∈iu i V

El modelo es similar al segundo modelo presentado para el TSP. La restricción 1.1 indica que exactamente m vehículos salen del depósito y las 1.2 y 1.3 aseguran que cada cliente es un nodo intermedio en exactamente una ruta. Finalmente, con 1.4 se eliminan los sub-tours y se impone que en cada ruta no haya más de p clientes.

En el caso que p = n (es decir, cuando la cantidad de clientes por ruta no está acotada) el m-TSP puede formularse como un TSP con m copias del depósito tales que la distancia entre ellas es infinita. Las soluciones a ese TSP no utilizarán arcos que conectan dos copias del depósito y por lo tanto, pueden ser interpretadas como soluciones del m-TSP.

� El Problema con Capacidades (CVRP)

El VRP es una extensión del m-TSP en la cual cada cliente i ϵ V \ {0} tiene asociada una demanda di y cada vehículo tiene una capacidad C (la flota es homogénea). En este problema la cantidad de rutas no es fijada de antemano como en el TSP y en el m-TSP. En algunos casos se agrega a este problema la restricción de que ninguna ruta puede tener largo mayor que cierta cota L. Cada vehículo, además, puede recorrer a lo sumo una ruta.

Se asume en la mayoría de los casos que m es una variable de decisión que no tiene cota superior, es decir, la disponibilidad de los vehículos es ilimitada.

� El Problema con Flota Heterogénea (HF-MVRP)

En los problemas con flota heterogénea los costos y capacidades de los vehículos varían, existiendo un

conjunto T = {1,...,|T|} de tipos de vehículo. La capacidad de los vehículos k ϵ T es qk y su costo fijo (si lo tuvieran) es fk. Los costos y tiempos de viaje para cada tipo de vehículo son cij

k y tijk

respectivamente. Además, está comúnmente aceptado que los índices de los vehículos están ordenados

en forma creciente por capacidad (es decir, qk1 ≤ qk

2 para k1, k2 ϵ T, k1 < k2).

El problema correspondiente se denomina Fleet Size and Mix Vehicle Routing Problem (o FSMVRP). No sólo se deben decidir las rutas, sino la composición de la flota de vehículos a utilizar. Usualmente, al tratar con problemas de flota heterogénea, se opta por utilizar este modelo aún cuando en algunos casos no refleja la realidad.

� El Problema con Ventanas de Tiempo (VRPTW)

En esta variante del problema, además de capacidades, cada cliente i ϵ V \ {0} tiene asociada una ventana de tiempo [ei, li] que establece un horario de servicio permitido para que un vehículo llegue a él y un tiempo de servicio o demora si. Si (i, j) es un arco de la solución y ti y tj son las horas de llegada a los clientes i y j, las ventanas de tiempo implican que necesariamente debe cumplirse ti ≤ li y tj ≤ lj.


24

Por otro lado, si ti < ei, entonces el vehículo deberá esperar hasta que el cliente “abra” y necesariamente tj = ei + si + tij.

2.1.4. Métodos de resolución exactos

Dada la complejidad de los problemas, sólo las instancias con pocos clientes (hasta 50 aproximadamente) pueden ser resueltas consistentemente por métodos exactos. En este tipo de metodologías, suele resolverse alguna relajación del problema y utilizarse un esquema de ramificación y acotamiento al estilo del método Branch and Bound [10]. También se han propuesto algoritmos basados en Programación Dinámica que aceleran los cálculos mediante una relajación del espacio de estados. Por otro lado, hay diversas implementaciones del método de Generación de Columnas, que han resultado especialmente efectivas para problemas con ventanas de tiempo muy ajustados. Para un completo compendio de métodos exactos para Problemas de Ruteo de Vehículos, puede consultarse los trabajos de Laporte y Norbert [11] y de Laporte [12].

2.1.5. Métodos de resolución Heurísticos

A continuación se presentan algunas de las heurísticas clásicas más significativas para el VRP con capacidades y, en algunos casos, la restricción sobre el largo máximo de cada ruta. Estas heurísticas son procedimientos simples que realizan una exploración limitada del espacio de búsqueda y dan soluciones de calidad aceptable en tiempos de cálculo generalmente moderados. Las soluciones obtenidas con esta clase de procedimientos pueden, en general, ser mejoradas utilizando métodos de búsqueda más sofisticados, pero incurriendo en elevados tiempos de ejecución. Muchas de estas heurísticas pueden ser extendidas para manejar restricciones adicionales a las del VRP.

� El Algoritmo de Ahorros

Uno de los algoritmos más difundidos para el VRP es el Algoritmo de Ahorros de Clarke y Wright [9]. Si en una solución dos rutas diferentes (0,…, i, 0) y (0, j,…, 0) pueden ser combinadas formando una nueva ruta (0,…, i, j,…,0) como se muestra en la Figura 9, el ahorro (en distancia) obtenido por dicha unión es,

0 0= + −ij i i ijs c c c (4.5)

pues en la nueva solución los arcos (i, 0) y (0, j) no serán utilizados y se agregará el arco (i, j). En este algoritmo se parte de una solución inicial y se realizan las uniones que den mayores ahorros siempre que no violen las restricciones del problema. Existe una versión paralela en la que se trabaja sobre todas las rutas simultáneamente, y otra secuencial que construye las rutas de a una por vez.

� Heurísticas de inserción

Las heurísticas de inserción son métodos constructivos en los cuales se crea una solución mediante sucesivas inserciones de clientes en las rutas. En cada iteración se tiene una solución parcial cuyas rutas sólo visitan un subconjunto de los clientes y se selecciona un cliente no visitado para insertar en dicha solución.


25

Figura 9. Dos rutas antes y después de ser unidas

En las heurísticas de inserción secuencial sólo se considera insertar clientes en la última ruta creada. La principal desventaja de este enfoque es que los últimos clientes no visitados tienden a estar dispersos y por lo tanto las últimas rutas construidas son de costo muy elevado [13, 14]. Las heurísticas de inserción en paralelo surgen para remediar esta deficiencia, permitiendo insertar un cliente en cualquiera de las rutas de la solución. Esta distinción es similar a la hecha para las dos versiones del Algoritmo de Ahorros (ver sección anterior).

Cualquier heurística de inserción para el TSP puede ser utilizada para el VRP siempre que se verifique la factibilidad antes de realizar las inserciones. Por un compendio de heurísticas de inserción para el TSP puede consultarse el trabajo de Bodin et al. [15]. En esta sección nos ocuparemos de aquellas diseñadas explícitamente para el VRP.

• Inserción Secuencial de Mole & Jameson

En esta heurística [13] se utilizan dos medidas para decidir el próximo cliente a insertar en la solución parcial. Por un lado, para cada cliente no visitado se calcula la mejor posición para ubicarlo en la ruta actual teniendo en cuenta solamente las distancias y sin reordenar los nodos que ya están en la ruta. Se tiene una ruta (v0, v1,…., vt, vt+1) donde v0 = vt+1 = 0. Si w es un cliente no visitado, el costo de insertar w entre vi y vi+1 (0 ≤ i ≤ t) se define como

1 11 , , ,( , ) λ+ +

= + −i i i ii v w w v v vc v w c c c (4.6)

Si (v0,…., vi,w,vi+1,….,vt+1) es factible. Si no, se daría el valor ∞ a la igualdad. La mejor posición para insertar el cliente w en la ruta actual está dada por,

10 ,...,( ) arg min ( , )

== ii t

i w c v w (4.7)

Si se utilizara solamente la medida c1 para decidir el próximo cliente a insertar, es probable que los clientes lejanos al depósito no sean tenidos en cuenta sino hasta las iteraciones finales del algoritmo, es decir, cuando sean las únicas alternativas factibles. Por lo tanto, es necesario utilizar un incentivo adicional para la inserción de clientes lejanos al depósito. Se define c2(vi,w) = µc0w−c1(vi,w) para cada

i

j

i

j


26

cliente w. En cada iteración se busca el cliente que maximiza la medida c2 (llamada medida de urgencia) y se lo inserta en la posición dada por el mínimo valor de c1.

Además de las medidas anteriores, debe considerarse la factibilidad de las inserciones. Cuando ninguna inserción es factible y si aún quedan clientes sin visitar, se selecciona un cliente para comenzar una nueva ruta.

• Inserción en Paralelo de Christofides, Mingozzi y Toth

El algoritmo propuesto por Christofides, Mingozzi y Toth [16] opera en dos fases. En la primera fase se determina la cantidad de rutas a utilizar, junto con un cliente para inicializar cada una de las rutas. En la segunda fase se crean dichas rutas y se inserta el resto de los clientes en ellas.

En la primera fase del algoritmo se aplica un algoritmo de inserción secuencial para obtener rutas compactas. No se presta especial atención a la ubicación de los clientes dentro de cada ruta, pues de esta fase sólo se conservan los clientes iniciales de cada ruta y la cantidad de rutas de la solución final.

Para inicializar la k-ésima ruta se selecciona un cliente vk dentro de los no visitados. Se define el costo de insertar el cliente w en la ruta que contiene a vk como δw,vk = c0w + λcw,vk (si el cliente no puede ser insertado, la función toma el valor ∞) y se asignan clientes a la ruta comenzando por los menores

valores de δ hasta que no haya inserciones factibles, en cuyo caso se crea una nueva ruta o se termina

el algoritmo.

� Métodos Asignar Primero – Rutear Después

Los métodos asignar primero y rutear después (cluster first - route second) se ejecutan en dos fases. Primero se busca generar grupos de clientes, también llamados clusters, que estarán en una misma ruta en la solución final. Luego, para cada clúster se crea una ruta que visite a todos sus clientes. Las restricciones de capacidad son consideradas en la primera etapa, asegurando que la demanda total de cada clúster no supere la capacidad del vehículo. Por lo tanto, construir las rutas para cada clúster es un TSP que, dependiendo de la cantidad de clientes en el clúster, se puede resolver de forma exacta o aproximada.

• Heurística de Barrido o Sweep

En la heurística de barrido [17], los clusters se forman girando una semirrecta con origen en el depósito e incorporando los clientes “barridos” por dicha semirrecta hasta que se viole la restricción de capacidad. Cada clúster es luego ruteado resolviendo un TSP de forma exacta o aproximada.

Este algoritmo puede aplicarse en problemas planos, es decir, en los que cada nodo se corresponde con un punto en el plano y las distancias entre ellos se definen como la distancia euclídea. Se supone que cada cliente i está dado por sus coordenadas polares (ρi, θi) en un sistema que tiene al depósito como origen. Por la forma en que se generan los clústers, las rutas obtenidas no se superponen, lo que puede ser bueno en algunos casos.


27

El procedimiento se repite n veces, comenzando en cada ejecución por un cliente diferente. Se propone además un procedimiento para eliminar clientes de cada ruta finalizada e insertar clientes que aún no fueron visitados, en el caso que esto disminuya el costo de la ruta. Los clientes eliminados de la ruta serán barridos por alguna ruta posterior. Utilizando esta variante las rutas pueden solaparse.

• Heurística de Asignación Generalizada de Fisher y Jaikumar

Fisher y Jaikumar [18] proponen generar los clústers resolviendo un Problema de Asignación Generalizada (GAP) sobre los clientes. Primero se fijan K clientes semilla sk con k = 1,…,K sobre la base de los cuales se construirán los clústers. En una segunda fase, se decide qué clientes asignar a cada uno de los clústers de modo de no violar la capacidad del vehículo, y se resuelve el GAP correspondiente.

• Heurística de Localización de Bramel y Simchi-Levi

El planteamiento de Bramel y Simchi-Levi [19] es similar al de Fisher y Jaikumar. En ambos existe un conjunto de clientes semilla y a cada uno se le asignan algunos clientes. Sin embargo, en esta propuesta, los clientes semilla son determinados por el algoritmo resolviendo un Problema de Localización de Concentradores con Capacidades (CCLP).

El CCLP se describe a continuación. Se dispone de m posibles ubicaciones para concentradores de capacidad Qj (j = 1,…,m) y n terminales, cada uno de los cuales utiliza wi (i = 1,…, n) de la capacidad del concentrador al que se conecta. El costo por ubicar un concentrador en la ubicación j es fj y el costo

de conectar el terminal i al concentrador j es ĉij. El CCLP consiste en decidir cuáles concentradores colocar y qué terminales conectar a cada concentrador de modo que cada terminal se conecte con exactamente un concentrador, se satisfagan las restricciones de capacidad y se minimicen los costos.

El CCLP brinda un marco general para resolver Problemas de Ruteo de Vehículos, definiendo a las posibles semillas como sitios para ubicar concentradores. Dados m subconjuntos de clientes, T1,…, Tm, el costo de utilizar el subconjunto Tj en la solución es t(Tj) (el costo de un TSP óptimo sobre los clientes Tj), siempre que la demanda de los clientes de Tj no supere la capacidad del vehículo. Además,

para cualquier cliente i, el costo de agregarlo a Tj es t(Tj ∪ { i}) − t(Tj). El problema de decidir qué semillas utilizar y qué clientes conectar con qué semillas es un CCLP donde los posibles concentradores son las posibles semillas, los terminales son los clientes, los costos fijos son los costos de rutar cada semilla y los costos de conexión son los costos de inserción de clientes en las semillas.

� Método Rutear Primero – Asignar Después

En los métodos rutear primero - asignar después [20] también se procede en dos fases. Primero se calcula una ruta que visita a todos los clientes resolviendo un TSP. En general esta ruta no respeta las restricciones del problema y se particiona en varias rutas, cada una de las cuales sí es factible.

Dada r = (0, v1,…, vn, 0), la solución del TSP obtenida en la primera fase, se determina la mejor partición de r que respete la capacidad del vehículo. Este problema se puede formular como el de


28

hallar un camino mínimo en un grafo dirigido y acíclico. Para ello, se construye un grafo G = (X, V, W) donde X = {0, v1, . . . , vn}. Los arcos del G conectan todo par de clientes vi y vj con i < j y tales que la demanda total de los clientes vi+1,…,vj no supera la capacidad del vehículo: V = {(vi, vj) | i < j, Σk=i+1

j dvk ≤ Q}. Cada arco (vi, vj) se pondera con el costo de la ruta (0, vi+1,…, vj , 0), es decir

1 1

1

0, ,0 ,1

( , )+ +

−

= +

= + + ∑i j k k

j

i j v v v vk i

w v v c c c (4.8)

Un arco (vi, vj) representa la ruta (0, vi+1,..., vj, 0). Cada camino de 0 a vn en G representa una posible partición de la ruta r en rutas que respetan las restricciones de demanda. Por lo tanto, el camino de costo mínimo entre 0 y vn representa la partición de costo mínimo de la ruta original en rutas que respetan la restricción de capacidad. Como el grafo es acíclico (sólo hay arcos (vi, vj) con i < j), puede utilizarse el Algoritmo de Dijkstra para hallar dicho camino.

Aunque la ruta inicial sea la solución óptima del TSP y la partición se realice de manera óptima, las rutas obtenidas no necesariamente son una solución óptima para el problema. Por lo tanto, alcanza con que la ruta inicial se calcule en forma heurísitca, por ejemplo, mediante la aplicación de 2-opt sobre una ruta aleatoria como en el trabajo original. El algoritmo puede ejecutarse repetidas veces, partiendo de diferentes rutas iniciales.

Según la definición original, w(vi, vj) es el costo de la ruta que comienza en vi+1, sigue el orden de la ruta original y termina en vj . Esta definición puede modificarse permitiendo variar el orden de los clientes vi+1,...,vj para obtener una ruta mejor. En el artículo original se aplica el algoritmo 2-opt sobre la ruta (0, vi+1,..., vj, 0).

� Algoritmo de Pétalos

Supongamos que se dispone de un conjunto de rutas R, de modo que cada ruta r ϵ R es factible, pero cada cliente es visitado por varias de las rutas. El problema de seleccionar un subconjunto de R de costo mínimo que visite exactamente una vez a cada cliente puede formularse como un Set Partitioning Problem (SPP).

En el caso extremo de que R contenga todas las posibles rutas factibles, solucionar el SPP es equivalente a resolver el problema en forma exacta. Como la cantidad de rutas factibles es, en el caso general, exponencial en la cantidad de clientes, se suele generar solamente un subconjunto de formado por “buenas” rutas.

Cada columna del SPP representa una ruta de R. Cuando en toda columna los ceros aparecen de forma consecutiva, el problema verifica la propiedad de Columnas Circulares y el SPP correspondiente puede ser resuelto en tiempo polinomial [21]. Trasladada al problema la propiedad establece que, para determinado ordenamiento de los clientes del problema, el conjunto de clientes visitado por cada ruta forma un intervalo (que en algunos casos tiene forma de pétalo). Cuando las rutas se generan con el Algoritmo de Barrido verifican la propiedad de Columnas Circulares.


29

� Procedimientos de Búsqueda Local

Una vez que se tiene una solución para el problema, se puede intentar mejorarla mediante algún procedimiento de búsqueda local. Para cada solución s se define un conjunto de soluciones vecinas

N(s). Un procedimiento de Búsqueda Local parte de una solución s, la reemplaza por una solución s* ϵ N(s) de menor costo y repite el procedimiento hasta que la solución no pueda ser mejorada. Al terminar, se obtiene una solución localmente óptima respecto a la definición de la vecindad. Para obtener s* puede buscarse la mejor solución de N(s) (estrategia best improvement) o simplemente tomar la primera solución de N(s) que mejore el costo (estrategia first improvement).

Usualmente se define N(s) como las soluciones que pueden obtenerse aplicando a s alguna regla o procedimiento sencillo llamado movida. Las movidas para el VRP pueden clasificarse en movidas de una ruta y movidas multi-ruta. En las movidas de una ruta los clientes que se visitan en una ruta no varían luego de la aplicación del operador, lo que varía es el orden en que se realizan las visitas. En las movidas multi-ruta, además de cambios en el orden de las visitas suele modificarse el conjunto de clientes visitados en cada ruta.

• El operador λ-intercambio

Uno de los operadores de búsqueda local para una ruta más conocidos es el λ-intercambio definido por Lin [22]. Un λ-intercambio consiste en eliminar λ arcos de la solución (λ > 1) y reconectar los λ segmentos restantes. Una solución se dice λ-óptima si no puede ser mejorada utilizando λ-intercambios. Se llama λ-opt a un algoritmo de búsqueda local que utiliza λ-intercambios hasta alcanzar una solución λ-óptima.

En una ruta que visita n clientes, hay �n+1λ � maneras posibles de eliminar λ arcos y, dada una elección

de arcos a eliminar, hay 2λ−1(λ − 1)! maneras de reconectar la ruta (incluyendo la reconexión que vuelve a generar la misma ruta). Por lo tanto, la cantidad de λ-intercambios posibles es

2λ−1(λ−1)! �n+1λ �. Comprobar si una solución es λ-óptima puede hacerse en tiempo O(nλ) en el peor

caso.

Usualmente se implementan 2-intercambios y 3-intercambios. Posibles movidas de este último tipo se muestran en las Figuras 9. En general, estas movidas invierten el orden de algunas visitas. Asumiendo que las movidas no afectan la factibilidad y que los costos son simétricos, puede buscarse movidas que mejoren el costo de una ruta sin necesidad de explorar todas las posibilidades. Si no se cumplieran dichos supuestos, buscar λ-intercambios tendría un costo computacional más elevado debido a la necesidad de incorporar chequeos de factibilidad y re-calcular algunos costos. No obstante, existen métodos [23] que proponen una versión reducida de 4-opt, mitigando así el problema del costo computacional.


30

Figura 10. Todos los 3-intercambios posibles para los arcos marcados

• El algoritmo de Lin-Kernigham

Un problema que surge al aplicar λ-intercambios es que debe fijarse el valor de λ de antemano. El algoritmo propuesto por Lin y Kernigham [24] utiliza la idea de intercambiar un conjunto de arcos por otro, pero determinando dichos conjuntos (y su orden) dinámicamente durante la ejecución del algoritmo. Dada una ruta, la idea es determinar dos conjuntos de arcos {x1,…, xk} e {y1,…, yk} tales que su intercambio disminuya el costo de la solución. Los arcos x deben ser parte de la ruta, ambos conjuntos deben ser disjuntos y, además, eliminar los arcos x y agregar los arcos y debe formar una ruta cerrada.

Se comienza seleccionando un arco x1 = (v1, v2). Luego, se busca y2 = (v2, v3) de modo que cx1 − cy1 = cv1,v2 − cv2,v3 > 0. Al comenzar la iteración i de este proceso, se han elegido x1,…, xi−1 y y1,…, yi−1, donde xh = (v2h−1, v2h) y yh = (v2h, vvh+1).


31

Se busca ahora xi = (v2i−1, v2i), de modo que si se uniera v2i con v1 se obtendría una ruta cerrada (esto asegura que el proceso pueda finalizarse obteniendo una solución factible). Como v2i−1 fue determinado al seleccionar yi−1 y xi debe ser un arco de la ruta, existen dos opciones para v2i (el anterior a v2i−1 en la ruta y el siguiente a él), pero solo una de estas cerraría la ruta a ser unida con v1. De modo que xi queda determinada por yi−1.

Para seleccionar yi = (v2i, v2i+1) debe cumplirse yi ∉ { x1,…, xi} para que los conjuntos sean disjuntos, Σj=1

i cxj - cvj > 0 para que el intercambio no empeore la solución y, además, debe poder elegirse el siguiente xi+1. Si no es posible encontrar yi que cumpla todo lo anterior, se busca k tal que Σj=1

k cxj - cvj sea máximo y se realizan intercambios entre los arcos {x1,…, xk} y { y1,…, yk}.

• El operador Or-opt

Una versión reducida del algoritmo 3-opt es el algoritmo Or-opt [25], que consiste en eliminar una secuencia de k clientes consecutivos de la ruta y colocarlos en otra posición de la ruta, de modo que permanezcan consecutivos y en el mismo orden. Primero se realizan las movidas con k = 3, luego con k = 2 y finalmente con k = 1. Si una ruta visita n clientes existen O(n2) de estas movidas.

• Operadores de Van Breedam

Van Breedam [26] propuso dos operadores para intercambiar clientes entre un par de rutas. En el operador String Relocation, una secuencia de m nodos es transferida de una ruta a la otra manteniendo el orden en la ruta original. En el operador String Exchange una ruta envía una secuencia de m clientes a la otra y esta última envía otra secuencia de n clientes a la primera. Simbólicamente se denota con (m, 0) a cada String Relocation y con (m, n) a cada String Exchange.

• GENI y GENIUS

Las inserciones generalizadas (GENI, por GENeralized Insertions) surgen dentro de un método de solución del TSP y tienen como principal característica que la inserción de un cliente en una ruta no necesariamente ocurre entre dos nodos adyacentes, sino que se permite la inserción de un nodo en cualquier punto de la ruta y su asignación posterior entre dos clientes cualesquiera, pudiendo revertir este proceso el orden de visita a los clientes.

• Transferencias cíclicas

Las transferencias cíclicas, introducidas por Thompson y Psaraftis [27], son movidas multi-ruta que intentan eliminar clientes de una ruta y reubicarlos en otra de manera cíclica.

2.1.6. Metaheurísticas

Para obtener mejores soluciones que las heurísticas presentadas en el apartado anterior, es necesario recurrir a técnicas que realicen una mejor exploración del espacio de soluciones. Las Metaheurísticas son procedimientos genéricos de exploración del espacio de soluciones para problemas de optimización y búsqueda. Proporcionan una línea de diseño que, adaptada en cada contexto, permite


32

generar algoritmos de solución. En general, las metaheurísticas obtienen mejores resultados que las heurísticas clásicas, pero incurriendo en mayores tiempos de ejecución (que de todos modos, son inferiores a los de los algoritmos exactos).

En este apartado se presentan los resultados más significativos en la aplicación de Algoritmos de Hormigas, Búsqueda Tabú y Algoritmos Genéticos para resolver el VRP y el VRPTW. Los métodos seleccionados son representantes de tres paradigmas diferentes. Los Algoritmos de Hormigas son procedimientos basados en agentes que utilizan métodos constructivos aleatorios y cooperan entre sí compartiendo información. Los algoritmos de Búsqueda Tabú son métodos de búsqueda local que aceptan empeorar las soluciones para escapar de los óptimos locales. Los Algoritmos Genéticos se basan en mantener un conjunto de soluciones lo suficientemente diverso como para cubrir gran parte del espacio de soluciones.

� Algoritmo de Hormigas

Los Sistemas de Hormigas o Ant Systems se inspiran en la estrategia utilizada por las colonias de hormigas para buscar alimentos. Cuando una hormiga encuentra un camino hacia una fuente de alimento, deposita en el trayecto una sustancia llamada feromona. La cantidad de feromona depositada depende de la longitud del camino y de la calidad del alimento encontrado. Si una hormiga no detecta la presencia de feromona se mueve aleatoriamente; pero si percibe dicha sustancia, decidirá con alta probabilidad moverse por los trayectos con más cantidad, lo que a su vez provocará un aumento de la feromona depositada en esa zona. De este proceso emerge un comportamiento denominado autocatalítico: cuanto más hormigas sigan cierto trayecto, más atractivo este se vuelve para ellas.

En los Algoritmos de Hormigas se simula el comportamiento de una colonia de estos animales. Cada hormiga construye una solución combinando un criterio ávido que le indica qué tan bueno parece ser tomar cierta decisión, y la información histórica (bajo la forma de feromona) que le indica qué tan bueno fue tomar dicha decisión. La decisión que toma una hormiga en cada paso es elegir la próxima ciudad a visitar.

Debido a la multiplicidad de combinaciones entre todos los parámetros del algoritmo, se han desarrollado distintas alternativas al modelo base ANT-Cycle [28], las cuales se enumeran a continuación:

- Ant System con Selección Elitista. Se da mayor énfasis a la mejor solución encontrada en cada iteración

- Ant System con Selección Elitista y Ranking. Es una generalización de la anterior en la cual se va ponderando en positivo un conjunto de soluciones mejores respecto a otras.

- Ant-Q. Las feromonas que se actualizan son las pertenecientes a arcos recorridos por hormigas. Dicha actualización se produce en dos fases: una de revisión local y otra global.


33

- Ant Colony System (ACS). Modifica una de las reglas del Ant-Q, consiguiendo así una mayor precisión y refinamiento en la búsqueda.

- MAX-MIN Ant System (MMAS). Busca una mayor explotación de las soluciones encontradas y provee un mecanismo que evita la convergencia prematura.

Una de las alternativas más usadas en la mejora de resultados para problemas de tipo VRP es el Ant System Híbrido. Mientras que para los de tipo VRPTW, se elige frecuentemente el MACS (Multiple Ant Colony System).

� Búsqueda Tabú

La metaheurística de Búsqueda Tabú o Tabu Search fue propuesta por Glover [29] y tiene como principio básico realizar una búsqueda local aceptando soluciones que aumentan el costo. En la iteración t el algoritmo se mueve de la solución st a la st+1, que es la mejor dentro de un subconjunto de sus soluciones vecinas N(st). Se llama movida a la operación que se aplica a st para obtener st+1. Notar que st+1 no necesariamente es de menor costo que st y, por lo tanto, debe utilizarse algún mecanismo para que en la iteración siguiente no se vuelva a st. Una opción sería almacenar todas las soluciones por las que se va pasando, pero a un costo de almacenamiento excesivo. En lugar de eso se utiliza una memoria de corto plazo que registra algunos atributos de las soluciones ya visitadas y se evita, durante cierta cantidad de iteraciones θ, considerar soluciones que posean dichos atributos. Las soluciones prohibidas se denominan soluciones tabú y las movidas que llevan hacia soluciones tabú se llaman movidas tabú. Suele utilizarse un criterio, llamado criterio de aspiración, para aceptar soluciones aún cuando sean tabú, por ejemplo, si mejoran el costo de la mejor solución encontrada hasta el momento. Se llaman soluciones admisibles a aquellas que no son soluciones tabú y a las que pasan el criterio de aspiración (aún si son tabú). La búsqueda se realiza sobre las soluciones admisibles de la vecindad.

Como mecanismo de diversificación, es decir, para asegurar una exploración de diferentes regiones del espacio de soluciones, puede utilizarse una memoria de largo plazo que penalice las movidas realizadas con mucha frecuencia. Finalmente, también puede utilizarse algún mecanismo de intensificación, como realizar búsquedas más exhaustivas periódicamente o utilizar vecindades más grandes en algunas de las mejores soluciones encontradas.

• Búsqueda Tabú para el VRP

A continuación se enumeran los distintos métodos o algoritmos que se han desarrollado para resolver este problema:

El algoritmo de Osman [30]. Las vecinas de una solución se obtienen mediante intercambios de clientes entre pares de rutas. Si rp y rq son dos rutas diferentes de una solución, se define un λ-intercambio como el pasaje de a lo sumo λ clientes de rp a rq y a lo sumo λ clientes de rq a rp. La cantidad de clientes que cada ruta envía a la otra no necesariamente debe ser la misma, pero ambas deben ser no mayores que λ. La vecindad de una solución s, Nλ(s), consiste en todas las soluciones que se pueden obtener aplicando esta operación a cualquier par de rutas diferentes de s.


34

El costo de una movida se evalúa de manera heurística. Al eliminar un cliente vi de una ruta, ésta se reconstruye uniendo el anterior y el siguiente a vi. Al insertar un cliente en una ruta, se coloca entre dos clientes consecutivos de forma de incrementar el costo lo menos posible. Luego de realizar una movida, se aplica el algoritmo 2-opt [22] sobre cada una de las rutas implicadas. Si se realiza una movida en que las rutas rp y rq intercambian los clientes vi y vj respectivamente, entonces la movida que vuelve vi a rp y vj a rq es una movida tabú. Del mismo modo, si se realiza la movida en que la ruta rp envía el cliente vi a la ruta rq y ésta última no le envía ningún cliente, la movida inversa, en la que rq devuelve vi a rp y rp no le envía ningún cliente a rq es una movida tabú. El tiempo que una movida es considerada tabú es fijo y se determina según las características de cada problema. Se utiliza el criterio de aspiración clásico: si una solución es mejor que la mejor solución hallada hasta el momento, se acepta aunque esto implique realizar una movida tabú. Para realizar la búsqueda en la vecindad de una solución s se utilizan dos criterios. En el criterio Best Admissible (BA) se busca la mejor solución admisible en Nλ(s) y en el First Best Admissible (FBA) se selecciona la primer solución admisible Nλ(s) que mejore el costo de s (si ninguna mejora el costo se selecciona la que menos lo empeora, pero habiendo necesitado examinar todos los intercambios posibles).

El algoritmo Taburoute. Gendreau, Hertz y Laporte [31] propusieron un algoritmo de búsqueda tabú que acepta soluciones no factibles durante la búsqueda. Se consideran conjuntos de rutas que visitan exactamente una vez a cada cliente, pero se permite violar las restricciones de capacidad y de largo máximo de cada ruta. Si Q(s) mide el exceso total de capacidad de las rutas y L(s) mide el exceso total de largo de las rutas en la solución s, se utiliza como función objetivo a

'( ) ( ) ( ) ( )α β= + +c s c s Q s L s (4.9)

Siendo c(s) el costo original en el problema. Notar que si una solución s* es factible, entonces c′(s*) = c(s*). En cambio, para las soluciones no factibles se incorporan dos términos que penalizan las violaciones a las restricciones, presionando las soluciones a pertenecer a la región factible. Cada 10 iteraciones, se ajustan los parámetros α y β. Si todas las soluciones de las últimas 10 iteraciones fueron factibles respecto a la capacidad, α se divide entre 2 y si todas fueron no factibles, se multiplica por 2. Lo mismo se realiza para β pero considerando la restricción de largo máximo de la ruta.

Dada una solución se evalúa, para cada cliente v, eliminarlo de su ruta e insertarlo en otra ruta que contenga alguno de sus p vecinos más cercanos (p es un parámetro del algoritmo). Se utiliza las inserciones GENI. Si el cliente v se elimina de la ruta r, entonces volver a insertarlo en r es una movida tabú durante θ iteraciones donde θ se sortea uniformemente en U~(5, 10).

Se utilizan dos mecanismos de intensificación. Por un lado, si la mejor solución encontrada no es mejorada durante cierta cantidad de iteraciones, se amplía el tamaño de la vecindad incrementando el valor de p. Además, periódicamente se aplica el operador US para realizar una búsqueda local sobre la solución obtenida luego de la movida. Como método de diversificación se penaliza la concentración de movidas sobre los mismos clientes. Al considerar el costo de una movida en la que participa el cliente


35

v, se suma un término proporcional a la cantidad de veces que dicho cliente fue movido durante la ejecución del algoritmo.

El procedimiento de búsqueda se ejecuta varias veces partiendo de diferentes soluciones y durante pocas iteraciones; a la mejor solución obtenida en estos falsos comienzos se le aplica el algoritmo durante más iteraciones

El algoritmo de Taillard [32]. Se realiza una partición del conjunto de clientes y cada partición se resuelve como un VRP independiente de los demás mediante Tabu Search. Para problemas uniformes (en los que el depósito está aproximadamente en el centro y los clientes están regularmente distribuidos) y con coordenadas euclídeas se propone una partición basada en consideraciones geométricas. Para el resto de los problemas, se da un método de partición que utiliza árboles de cubrimiento formados por los caminos mínimos del depósito a cada cliente. Tras ciertas iteraciones se modifica la partición utilizando información sobre la mejor solución obtenida.

Se utiliza la misma definición de vecindad que en el algoritmo de Osman [30] con λ = 1. El costo de las movidas se evalúa en forma heurística: al insertar un cliente en una ruta se hace entre dos clientes consecutivos de modo de minimizar el aumento en el costo; y al eliminar un cliente de una ruta, se unen el anterior y el siguiente a él. La inversa de una movida es considerada tabú por una cantidad θ de iteraciones, donde θ se sortea uniformemente en [0.4n, 0.6n]. La movida de un mismo cliente repetidas veces es penalizada, a menos que cumpla con el criterio de aspiración, que es el usual de mejorar la mejor solución encontrada hasta el momento.

Periódicamente, cada ruta es optimizada resolviendo un TSP sobre sus clientes de forma exacta mediante el algoritmo de Volgenant y Jonker [33]. Como en los casos estudiados la cantidad de clientes por ruta es baja (siempre menor que 40), esto no representa un problema siempre que no se realice con demasiada frecuencia.

Memorias adaptativas de Rochart y Taillard. Si bien la propuesta de Rochat y Taillard [34] puede ser utilizada junto con cualquier algoritmo de búsqueda local, tiene su origen en el marco de Tabu Search. La idea sobre la que se basa es que si cierta característica aparece consistentemente en las buenas soluciones, entonces muy probablemente las soluciones que posean dicha característica serán mejores que las que no la posean. En los problemas de ruteo de vehículos, es razonable considerar a las rutas como dicha característica: si cierta ruta aparecen repetidamente en las buenas soluciones, probablemente sea bueno considerarla.

El algoritmo comienza generando un conjunto de soluciones diferentes mediante varias ejecuciones de alguna heurística no determinista de búsqueda local. Luego de esta etapa, se espera tener (aunque de manera “oculta”) toda la información necesaria para armar buenas soluciones. Dicho de otro modo, es de esperar que varias rutas muy similares a las necesarias para construir una buena solución hayan sido generadas, aunque quizás estén en soluciones diferentes. Al final de esta fase se tiene un conjunto R formado por las rutas de todas las soluciones obtenidas; si una ruta aparece en más de una solución, se


36

tiene múltiples copias de dicha ruta en R. Cada ruta se etiqueta con el valor de la solución a la que pertenece.

En una segunda fase se busca extraer rutas de R para armar una nueva solución. Para esto, se crea R′ ordenando R de manera creciente en las etiquetas y considerando solamente las primeras L rutas (considerando las rutas repetidas como rutas diferentes). Luego se selecciona una ruta de R′, donde se agrega a la solución y se eliminan de R′ todas las que contengan clientes en común con ella. El procedimiento se repite hasta que R′ se vacíe. Al finalizar podrían quedar algunos clientes sin visitar, para los que se resolverá un VRP con la heurística de búsqueda local, agregando las rutas obtenidas a la solución. Sobre esta solución se realiza una nueva búsqueda local y las rutas obtenidas se agregan al conjunto original R. Esta segunda fase de construcción y búsqueda local se puede repetir tantas veces como se quiera.

En el trabajo original se utiliza el Algoritmo de Taillard [32] como método de búsqueda local. Al finalizar el algoritmo, como método de post-optimización, se resuelve un Set Partitioning Problem con las rutas de R.

El Algoritmo de Xu y Kelly. En el algoritmo propuesto por Xu y Kelly [35] se utiliza una red de flujo para buscar intercambios de clientes entre las rutas. Dada una solución con m rutas, se construye una red con 4 niveles de arcos. En el primer nivel, se conecta el nodo fuente con un nodo por cada ruta. El flujo en estos arcos indica la cantidad de clientes eliminados de cada ruta. La oferta del nodo s está acotada superiormente por U. En el segundo nivel hay un arco entre cada ruta y los clientes que esta visita, cuya capacidad máxima es 1 y el flujo asignado indica si el cliente es eliminado de la ruta o no. Los arcos del tercer nivel unen a cada cliente con cada ruta. Su capacidad máxima es también 1 y el flujo indica si el cliente es insertado en la ruta o no. Finalmente, se conecta a cada ruta con un nodo terminal y el flujo a través de esos arcos indica la cantidad de clientes insertados en cada ruta.

Un flujo sobre esta red da una manera de reasignar a lo sumo U clientes entre las rutas, sin tener en cuenta la capacidad de los vehículos. Los vehículos sobrecargados se penalizan al definir el costo de las movidas como en Taburoute. A cada arco de los niveles 2 y 3 se asocia un costo compuesto de dos términos. Por un lado, se mide de manera aproximada el aumento en la función objetivo del problema si se realizara la eliminación o inserción asociada al arco. Además, se agrega un término para favorecer la inserción de clientes en las rutas que están muy por debajo de la capacidad del vehículo y para penalizar las inserciones en rutas muy sobrecargadas.

La vecindad utilizada en el algoritmo de Tabú Search alterna entre las movidas definidas por el flujo de costo mínimo en la red y los λ-intercambios de Osman. Se penaliza la realización repetida de movidas sobre el mismo cliente sumando al costo de las movidas, un término que mide cuántas veces se realizaron dichas movidas. Cuando se realiza una movida, la movida inversa es declarada tabú por una cantidad fija de iteraciones. Periódicamente se aplica el algoritmo 3-opt o el 2-opt sobre la ruta.

Se mantiene un conjunto con las mejores soluciones encontradas durante la búsqueda y al cabo de cierta cantidad de iteraciones, se comienza una nueva búsqueda a partir de alguna de esas soluciones.


37

Ejection Chains de Rego y Roucariol. Las Cadenas de Expulsiones (o ejection chains) fueron propuestas por Glover [36] como una técnica general para definir vecindades en un espacio de soluciones. En su versión más general, una movida consiste en seleccionar algunos elementos que cambiarán su estado o valor y, como resultado, otros elementos serán expulsados de su estado actual. En el caso de los Problemas de Ruteo de Vehículos se trata de cambiar las posiciones de algunos nodos en las rutas.

El Algoritmo Flor. En este algoritmo se utiliza una estructura llamada Flor para generar una vecindad [37]. Una flor es un conjunto de rutas y un camino que parte del depósito, tal que todos los clientes del problema son visitados exactamente una vez. Se utilizan Cadenas de Expulsiones para transformar una Flor en otra mediante ciertas transformaciones y, además, se dan reglas para crear una Flor a partir de una solución y viceversa.

Granular Tabu Search. La idea principal del algoritmo Granular Tabu Search de Toth y Vigo [38] consiste en disminuir la cantidad de arcos considerados, eliminando los que conectan nodos muy lejanos. Estos arcos tienen muy pocas posibilidades de pertenecer a una buena solución. Se define un

umbral ν y solo se permite efectuar las movidas que involucran arcos en el conjunto E′ = {( i, j) ∈ E | cij

< ν} ∪ I, donde E es el conjunto de arcos originales e I es un conjunto de arcos “importantes”, como por ejemplo, los incidentes al depósito.

DETABA. En el Algoritmo DETABA, propuesto por Barbarosoglu y Ôzgür [39], se utilizan dos tipos de movidas. Las movidas TANE seleccionan dos rutas r1 y r2 al azar y de cada una eligen un conjunto aleatorio de clientes s1 y s1. El conjunto s1 se elimina de r1 y se inserta en r2 y la operación análoga se realiza con s2. Los conjuntos s1 y s2 deben elegirse de modo que al realizar la operación anterior no se viole las restricciones del problema. Luego de eso se aplica 2-opt a r1 y r2. En las movidas TANEC el procedimiento es similar al anterior, pero se procura que los clientes de s1 y r2 sean lejanos al centroide de sus rutas respectivas y cercanos al centroide de la ruta a la que no pertenecen. Para seleccionar la movida a realizar, se genera una cantidad de movidas TANE y TANEC y se implementa la mejor que no sea tabú. Si en una movida el cliente v1 pasa de r1 a r2 y v2 pasa de r2 a r1, entonces se declara tabú el volver a colocar v1 en r1 y v2 en r2. La cantidad de iteraciones que una movida es tabú se sortea uniformemente en un intervalo.

Se utilizan falsos comienzos como en Taburoute, es decir, se ejecuta la búsqueda durante unas pocas iteraciones para generar un conjunto de soluciones iniciales. Luego se vuelve a ejecutar la búsqueda durante más iteraciones, partiendo de la mejor de esas soluciones iniciales.

• Búsqueda Tabú para el VRPTW

Unified Tabu Search. Cordeau, Laporte y Mercier, propusieron un método de Búsqueda Tabú para el VRPTW al que llamaron Unified Tabu Search [40]. Se supone que el tamaño de la flota es m, conocido de antemano. Se permite considerar soluciones no factibles y las violaciones a la capacidad, largo máximo de las rutas y ventanas de tiempo, se penaliza como en Taburoute. La actualización de las ponderaciones en los términos de dicha penalización se actualiza en cada iteración.


38

Las movidas utilizadas simplemente seleccionan un cliente, lo eliminan de su ruta y lo insertan en otra entre dos nodos consecutivos. Al eliminar un cliente de su ruta, esta se reconecta uniendo el anterior y el sucesor del cliente eliminado. Si el cliente i se elimina de la ruta r, volver a insertarlo i en r es una movida tabú por θ iteraciones.

Como método de diversificación, si colocar el cliente i en la ruta r empeora la función objetivo, se penaliza dicha movida con un término ρir que mide cuántas veces el cliente i fue insertado en r durante toda la búsqueda. Al finalizar la búsqueda, se aplica una versión de GENI para problemas con ventanas de tiempo [68] sobre la mejor solución encontrada, como método de post-optimización.

� Algoritmos Genéticos

Los Algoritmos Genéticos (AG), introducidos por Holland [41], utilizan las ideas de la evolución natural de los seres vivos para resolver problemas de optimización y búsqueda. En general, se trabaja sobre una representación de las soluciones en algún esquema de codificación (por ejemplo, vectores, matrices o árboles). El algoritmo opera sobre una población P de soluciones codificadas, llamadas

individuos. Para cada individuo i ϵ P se define una función de fitness f(i) de modo que cuanto mayor es el fitness de un individuo, mejor es la solución que este representa. En cada iteración se aplican operadores evolutivos que combinan y modifican a los individuos de la población, creando una nueva. En el esquema usual se opera en tres fases: selección, cruzamiento y mutación.

El operador de selección se encarga de elegir algunos individuos de la población que tendrán la posibilidad de reproducirse. De modo general, puede decirse que este operador genera una población intermedia (o mating pool) cuya cantidad de individuos depende de las características del operador de cruzamiento utilizado. Los operadores de selección son, en general, probabilísticos y suelen privilegiar a los individuos con mayor fitness en la población.

Una vez que se generó la población intermedia, se aplica repetidas veces el operador de cruzamiento para combinar individuos de dicha población y generar una nueva. Usualmente los operadores de cruzamiento toman dos individuos p1 y p2 llamados padres, y generan dos individuos h1 y h2 llamados hijos, mediante la aplicación de una regla probabilística. Si utiliza una codificación basada en vectores, los operadores de cruzamiento clásicos son los de n puntos, que consisten en “cortar” cada padre en n posiciones, de manera aleatoria, e intercambiar los segmentos intermedios. Por ejemplo, si p1 = 1001001101 y p2 = 1100101110, un posible resultado de un cruzamiento de dos puntos (que se da cuando los padres se cortan luego de las posiciones 3 y 6) es h1 = 1000101101 y h2 = 1101001110. El operador de cruzamiento de un punto se denomina SPX (Single Point Crossover) y el de dos puntos DPX (Double Point Crossover). Otro operador clásico es el UX (Uniform Crossover): para cada posición, con probabilidad 0.5 el hijo h1 toma el valor de dicha posición de p1 y h2 de p2 y con probabilidad 0.5 ocurre lo contrario.

Finalmente, se aplica a algunos individuos de la nueva población, un operador probabilístico de mutación que consiste en realizarle alguna modificación. En codificaciones con vectores binarios suele invertirse algunos bits o permutar los valores de dos posiciones.


39

Los operadores de cruzamiento y mutación operan sobre los individuos, es decir, sobre la codificación de las soluciones. A cada una de las poblaciones sucesivas se le llama generación. El modelo presentado no es el único modelo de evolución. Por ejemplo, en los Algoritmos Genéticos de Estado Estacionario, los individuos se generan de a uno y reemplazan (si corresponde) por el peor individuo de la población.

• Algoritmos Genéticos para el VRP

GVR. En Genetic Vehicle Representation (GVR)[42] se trabaja directamente sobre las soluciones. Para cruzar dos soluciones p1 y p2, se toma una sub-ruta r = (v1,..., vk) de p1 (al tratarse de una sub-ruta, no necesariamente se cumple que v1 = 0 y vk = 0) y se determina el cliente wj más cercano a v1 que no está en r. Si la ruta a la que pertenece w en la solución p2 es r′ = (0, w1,..., wj, wj+1,..., 0) entonces esta se reemplaza por (0,w1,...,wj,v1,...,vk,wj+1,...,0). Es decir, se inserta r en r′ a continuación de w. Si esta ruta no fuera factible, se divide en tantas rutas factibles como sea necesario. Con esto se genera un hijo, el otro hijo es una copia de p1.

Se utilizan cuatro operadores de mutación: intercambiar la posición de dos clientes en una ruta, invertir el orden de una ruta, re-insertar un cliente en una ruta diferente a la que pertenece y seleccionar una sub-ruta e insertarla en otro lugar de la solución. Los últimos dos operadores pueden generar rutas nuevas o eliminar rutas, mientras que los dos primeros mantienen la cantidad de rutas de la solución.

El Algoritmo de Baker y Ayechew. El algoritmo propuesto por Baker y Ayechew [43] se basa en la técnica de Asignar Primero - Rutear Después. Cada individuo codifica la asignación de clientes a vehículos mediante un vector que en la posición i indica el número del vehículo asignado. El índice asignado a cada cliente es tal que si la distancia entre dos clientes es pequeña, entonces sus índices serán cercanos. Esto se logra utilizando una modificación de la Heurística de Barrido para asignar índices a los clientes.

La función de fitness se calcula generando una ruta para cada vehículo que pase por todos los clientes asignados a él utilizando 2-opt y luego 3-opt. Se permite violar las restricciones del problema, penalizando dichas violaciones en la función de fitness. Se utiliza un Algoritmo de Estado Estacionario, Selección por Torneo, DPX como operador de cruzamiento y un intercambio probabilístico entre dos posiciones del vector como operador de mutación.

• Algoritmos Genéticos para el VRPTW

GIDEON. El Algoritmo GIDEON de Thangiah [44] utiliza la técnica de Asignar Primero - Rutear Después. Los clusters se generan mediante la ubicación de K “puntos semilla” en el plano. Desde el depósito se trazan semirrectas hacia cada punto semilla, definiendo sectores que dividen al conjunto de clientes en clusters. El AG se utiliza para determinar la mejor ubicación de los puntos semilla. La ubicación de un punto semilla se codifica, utilizando 5 bits. Un vector de 5K bits representa la ubicación de los K puntos semilla.


40

Para calcular el fitness de un individuo se genera una ruta para cada uno de sus clusters utilizando un algoritmo simple de inserción para el TSP. Se permite que las rutas sean no factibles. El fitness de un individuo es el costo de las rutas obtenidas para cada cluster, más términos que penalizan las violaciones a las restricciones de capacidad, largo máximo de cada ruta y ventanas de tiempo. El operador de cruzamiento utilizado es el DPX y como operador de mutación se modifican algunos bits aleatoriamente.

Al final de la ejecución del algoritmo, se realiza una búsqueda local sobre la mejor solución encontrada, utilizando los λ-intercambios definidos por Osman. Esta nueva solución es utilizada para modificar las coordenadas polares de cada cliente, de modo que los clientes consecutivos en una ruta queden consecutivos si se ordenaran por su ángulo en las nuevas coordenadas polares. Con esas nuevas coordenadas se vuelve a ejecutar el Algoritmo Genético y se sigue el proceso por algunas iteraciones.

GenSAT. En el Algoritmo GenSAT [45] simplemente se aplica un post-procesamiento a la solución obtenida mediante la ejecución de GIDEON [44]. Dicho post-procesamiento incluye la ejecución de métodos de descenso simples (First Best y Global Best) y además Simulated Annealing y Tabu Search utilizando vecindades definidas mediante 2-intercambios.

El Algoritmo de Blanton y Wainwright. En el algoritmo propuesto por Blanton y Wainwright [46] se asume que se tiene una flota fija de K vehículos. Cada individuo es una permutación del conjunto de los clientes. Para obtener el conjunto de rutas que la permutación representa, se inicializan K rutas utilizando los primeros K clientes de la permutación y el resto de los clientes son insertados secuencialmente en la ruta que genere menos incremento en el costo (siempre que la inserción sea factible). Si luego de ese proceso quedan clientes sin visitar, esto se penaliza en la función de fitness.

Se proponen dos operadores de cruzamiento llamados MX1 y MX2, que generan un solo hijo. Ambos consideran un ordenamiento global de los clientes dado por su ventana de tiempo, que expresa un orden deseable para las visitas. Si los clientes en la posición 1 de cada padre son v1 y v′1, asigna a la posición 1 del hijo el cliente (v1 o v′1) que esté antes en el orden global. Luego se intercambian las posiciones de modo que en la posición 1 de ambos padres quede en cliente elegido y se procede de la misma manera con todas las posiciones hasta procesar todos los clientes. El operador MX2 es similar, pero en lugar de intercambiar las posiciones, se elimina de ambos padres el cliente elegido.

GENEROUS. Potvin y Bengio propusieron un Algoritmo Genético llamado GENEtic ROUting System (GENEROUS) [47] en el cual los operadores evolutivos se aplican directamente sobre las soluciones factibles y no sobre una codificación de estas. Para calcular el fitness de un individuo se utiliza un esquema de Ranking Lineal. Se fija un fitness máximo fmax y un fitness mínimo fmin y se ordenan las soluciones colocando la mejor al comienzo (posición 1) y la peor al final (posición |P|). El fitness de la solución en la posición i es,

max min

max

( )( 1)

| | 1

− −−−

f f if

P (4.10)


41

es decir, a la mejor solución se le asigna fmax, a la peor fmin y al resto se le asigna valores espaciados uniformemente en ese intervalo. Se utiliza Selección Proporcional.

Se proponen dos operadores para combinar soluciones, el Sequence-Based Crossover (SBX) y en Route-Based Crossover (RBX). En el SBX, se seleccionan dos rutas r1 y r2, una ruta de cada padre, y se elimina un arco de cada una. Luego se arma una nueva ruta uniendo el segmento de r1 anterior al corte con el de r2 posterior al corte y la ruta obtenida reemplaza a r1. La solución obtenida puede contener clientes duplicados y una de las copias debe ser eliminada. Puede ocurrir, además, que algunos clientes no sean visitados; a estos se los inserta secuencialmente en la ruta que incremente menos el costo total de 50 la solución. Si ocurriera algún cliente no puede ser insertado en ninguna de las rutas manteniendo la factibilidad, la solución es descartada (pues reconstruirla implicaría utilizar un vehículo más que en los padres) y el proceso de selección y cruzamiento debe repetirse hasta tener éxito. Invirtiendo el orden en que se consideran los padres (es decir, reemplazando a r2 con la nueva ruta) puede obtenerse otra solución tentativa. El operador RBX consiste en copiar una ruta de un padre en el otro. Nuevamente, puede darse que algunos clientes estén duplicados y otros queden sin ser visitados, en cuyo caso se aplican las mismas consideraciones que para el operador SBX.

Como operadores de mutación se proponen el One-Level Exchange (1M), Two-Level Exchange (2M) y Local Search (LSM), cuyo principal objetivo es disminuir la cantidad de vehículos de la solución. En el operador 1M se selecciona una ruta r y se inserta cada uno de sus clientes vi en la ruta r i que minimice el incremento en el costo total. La selección de la ruta es sesgada hacia las rutas con menos clientes. Puede ser difícil agregar vi a r i respetando las restricciones de capacidad y las ventanas de tiempo, por lo que en el operador 2M se considera la posibilidad de reubicar algún cliente de esa ruta, para “hacer lugar” a vi. Si r i = (0,…,vj−1,vj,vj+1,…,0) y la ruta (0,…,vj−1,vi,vj+1,…,0) es factible y además vj puede ser insertado en otra ruta r′ (que no sea r, pero pudiendo ser r i), entonces el operador 2M permite insertar vi en r i y vj en r′. Finalmente, el operador LSM realiza una búsqueda local mediante el Algoritmo or-opt.

Algoritmo de Berger, Barkaoui y Bräysy. En esta propuesta [48] se utilizan dos poblaciones que evolucionan en paralelo y operan directamente sobre las soluciones. En la población P1 el objetivo es minimizar el costo total y siempre se tiene al menos una solución factible. La población P2 intenta minimizar la violación de las restricciones. Los individuos de una misma población tienen la misma cantidad de rutas; los de P1 tienen Rmin y los de P2 tienen Rmin−1, siendo Rmin la mínima cantidad de rutas para la que se ha conseguido una solución factible. Cuando se encuentra una nueva mejor solución en P2, se actualiza Rmin y ambas poblaciones. Ambas poblaciones evolucionan de la misma manera, utilizando los mismos operadores y la misma función de fitness. La única diferencia radica en la cantidad de rutas impuesta a los individuos. Se utiliza un modelo evolutivo de Estado Estacionario: una generación consiste en agregar np individuos a la población y luego eliminar los np peores individuos. Luego de que ambas poblaciones evolucionan una generación, si P2 contiene una solución factible, se copian los individuos de P2 en P1 y se aplica un operador de mutación llamado RSS_M a los individuos de P2 para reducir la cantidad de rutas en uno.


42

El Algoritmo de Zhu. En el algoritmo propuesto por Zhu [49], cada solución se representa como una permutación de los clientes. Para obtener las rutas, se agrega clientes a una ruta siguiendo el orden dado por la permutación y cuando incluir el siguiente cliente en la ruta viole las restricciones del problema, se crea una nueva. Se utiliza Selección por Torneo.

Se combinan tres operadores de cruzamiento, el PMX y dos nuevos operadores: Heuristic Crossover (HC) y Merge Crossover (MC). En el HC se selecciona un punto de corte y se elige el cliente siguiente a dicho punto en alguno de los padres (sea v dicho cliente) para comenzar la ruta. En el otro padre, se intercambian dos clientes de modo que v quede en la misma posición en ambos. Si v1 es el siguiente a v en uno de los padres y v2 es el siguiente en el otro, entonces se agrega a la ruta el más cercano a v. El proceso se repite partiendo del cliente agregado, hasta completar una ruta. El MC opera de manera similar, pero selecciona el próximo cliente de acuerdo al tiempo y no a la distancia.

Para la mutación se intercambian las posiciones de algunos clientes dentro de una misma ruta.

El Algoritmo de Tan, Lee y Ou. El algoritmo propuesto por Tan, Lee y Ou [50] puede ser considerado un método Asignar Primero - Rutear Después. Cada individuo codifica una agrupación de clientes mediante una permutación y un vector que indica cuántos clientes tiene cada cluster. Por ejemplo, el individuo (2, 4, 7, 1, 6, 5, 9, 3, 8)(3, 2, 4) representa los clusters (2, 4, 7), (1, 6) y (5, 9, 3, 8).

Para evaluar el fitness de un individuo se construye una ruta para cada cluster mediante una Heurística de Inserción Secuencial de Solomon y realizando luego una búsqueda local mediante los λ-intercambios de Osman. Se utiliza Selección por Torneo, PMX y un operador de mutación que intercambia dos elementos del primer vector.

Tunning de Parámetros de Potvin y Dubé. Potvin y Dubé [51] utilizaron un Algoritmo Genético para ajustar los parámetros de la Heurística de Inserción en Paralelo para el VRPTW de Potvin y Rousseau. Se utiliza una codificación mediante un vector binario para representar un juego de parámetros de la heurística. El fitness de un individuo se define como el costo de la solución obtenida ejecutando la heurística con el juego de parámetros que el individuo representa. Se utiliza Selección por Ranking, SPX como operador de cruzamiento y el operador de mutación modifica probabilísticamente cada bit.

2.2. Análisis de costes de sostenibilidad en el transporte

La función objetivo clásica de los problemas VRP se centra en minimizar la distancia total de todos los vehículos o el coste en el que se incurre, usualmente definido como una función lineal de la distancia. Este es un objetivo ampliamente utilizado en la literatura asociada a flotas homogéneas como se ha visto en el apartado 4.1.

Las externalidades del transporte es un coste, no percibido directamente por el usuario y que sufren terceras personas, sin compensación o pago algunos. Las externalidades más frecuentes consideradas se han centrado en congestión, ruidos, efectos barreras, impacto sobre el medio natural y finalmente la contaminación. La última década ha destacado el auge del análisis de externalidades asociadas a la


43

contaminación como consecuencia de los acuerdos de diferentes tratados que los países han firmado y trasladado a los sectores productivos de la economía.

La no consideración de los costes de las externalidades induce una mayor ineficiencia que provoca un aumento de los problemas medioambientales, seguridad y congestión. Las externalidades del transporte deben por lo tanto ser considerada e incluida como coste en el desarrollo de modelos, medidas y actuaciones. Algunos autores, como Peng Yong [52], enfocan el problema desde un punto de vista enérgetico (ahorro de combustible) y argumentan que esto redunda positivamente tanto en la salud de las personas como en el medioambiente. Es decir, el efecto colateral sobre el entorno es beneficioso, pero no es causa para alterar las rutas.

El principal problema asociado a la inclusión de las externalidades es su cuantificación y su traducción a unidades monetarias para su correcta inclusión en los modelos y procesos.

En este sentido, han sido hasta la fecha multitud los investigadores que han profundizado en la inclusión de estos costes medioambientales en los problemas clásicos de VRP, tratando de proporcionar una visión más realista y sostenible de la gestión en la cadena de mercancías. Hasta hace 10 años, el objetivo primordial en logística era alcanzar el máximo beneficio económico o mejorar el servicio al cliente. Pero en la última década, el auge en el interés por la preservación del medioambiente está jugando un papel relevante en las políticas de operación y distribución. Por tanto, es conveniente que estos factores se añadan a los objetivos económicos, para encontrar el balance perfecto entre estas dos dimensiones [53].

Algunos autores [54] centran sus investigaciones en la evaluación de los efectos externos del transporte para internalizarlos a través de impuestos. De ahí que las decisiones tales como la selección del tipo de vehículo, la programación de las entregas, la fusión de flujo de mercancías y la elección de tipo de combustible que consideran costes internos y externos ayuden a reducir el impacto en entorno sin perder competitividad con compañías rivales.

En los últimos años, otros investigadores han propuesto métodos de rutado con ventanas de tiempo que incluyen modelos de emisiones para la cadena de transporte [55]. Tienen en cuenta la cantidad de emsiones de CO2 y consumo de combustible, pero no consideran flotas de tipo heterogéneo y otras externalidades como contaminantes atmosféricos, ruido y accidentes.

No se dispone de una clasificación específica universal para ordenar las características de todos los vehículos disponibles en lo que a emisión de contaminantes se refiere, así que es frecuente acudir a organizaciones que proporcionan estimaciones de conversión entre vehículos que se amoldan a una normativa dada, como por ejemplo, el INFRAS.

En el estudio desarrollado por Eguía, Racero y Guerrero [56], se propone un modelo matemático de programación lineal que internaliza los costes externos en problemas tipo HF-VRPTW-B apoyándose en las conversiones establecidas por el INFRAS/IWW. Se evalúa la flota de vehículos y la cuantía de sus emisiones de GEI para añadirlos al modelo clásico. Finalmente, se corrobora que este nuevo


44

concepto de rutado con contaminantes modifica las rutas que minimizan distancia sin considerar factores externos.

Esta nueva percepción de la gestión de flotas de vehículos es el punto de partida del presente documento.

3. DISEÑO DE LA BÚSQUEDA TABÚ

3.1. Descripción del problema El problema que se presenta en este trabajo es una extensión del clásico CVRP (véase sección 2.1) que incluye ventanas de tiempo, flota heterogénea de vehículos con distintos tipos de combustible (HF-VRPTW) e internalización de costes medioambientales en la función objetivo. Como ya se ha descrito anteriormente, este tipo de problemas quedan definidos por tres entidades: clientes, depósitos y vehículos. Cada una de ellas está limitada por una serie de asunciones de antemano que se describen a continuación:

� Clientes

- Número total de clientes.

- Todas las distancias (km) entre ellos y al depot.

- Tiempo de desplazamiento (h) entre ellos y al depot.

- Coste del peaje (€) entre ellos y al depot.

- Demanda invariable para cualquier vehículo.

- Ventana de tiempo (límite inferior y límite superior) e invariables para cualquier vehículo.

- Tiempo de servicio invariable para cualquier vehículo.

� Vehículos de la flota

- Número total de vehículos.

- Capacidad fija para cada vehículo.

- Máximo tiempo de conducción (h) para cada vehículo. Se refiere al máximo tiempo que puede estar un vehículo en ruta, entendiéndolo como el tiempo que transcurre desde que sale del depot hasta que vuelve de nuevo a él.

- Tasa de conductor (€/h) para cada vehículo. El coste por hora de mantener al vehículo en ruta.

- Coste fijo (€) para cada vehículo. El coste en que se incurre por poner a un vehículo en ruta.

- Coste de mantenimiento (€/km) para cada vehículo. El coste por kilómetro recorrido en la ruta.

- Consumo vacío (l/100km) para cada vehículo. El consumo por litro cada 100 kilómetros.

- Consumo por tonelada (l/100km ton). El consumo por litro y por tonelada transportada cada 100 kilómetros.

- Tipo de combustible para cada vehículo. Diesel, gasolina u otro.


46

- Categoría. Se refiere a qué categoría, según la Normativa Europea de Emisiones, se adapta el vehículo para ver sus niveles de emisiones de GEI.

� Depot

- Un único depot. Es la primera y última ciudad en toda ruta de cualquier vehículo que atienda a algún cliente.

- Demanda, ventanas de servicio y tiempo de servicio de valor nulo.

La caracterización tan amplia de estas tres entidades hace necesaria la descripción matemática en aras de una compresión global y exhaustiva, pues las situaciones y casuísticas que se producen son múltiples y es, por tanto, fundamental esclarecer la actuación tomada ante cualquiera de ellas.

El HF-VRPTW se define sobre un grafo G={N,A} con N={0,1,…,t} como un conjunto de nodos, donde el nodo 0 representa el punto de partida o depósito y los nodos 1 hasta t representan los puntos de entrega, y A representa un conjunto de arcos definidos entre cualquier par de nodos. El modelo incluye un conjunto de m vehículos de diversas categorías que serán los candidatos a ser empleados como medio de transporte para satisfacer la demanda de todos los clientes procedente del nodo depósito. El diseño de las rutas por cada vehículo debe satisfacer las siguientes restricciones: Los vehículos tienen una capacidad, por tanto la carga transportada no pueden superar la capacidad, cada cliente debe ser atendido en base a ventanas de tiempo fijadas y los vehículos tienen una limitación de tiempo de funcionamiento. El modelo desarrollado sigue la siguiente anotación:

- Di: Demanda por nodo i є {1,…,t}.

- qk: Capacidad del vehículo k є {1,…,m}.

- [ei, l i]: Ventana de tiempo de servicio por nodo i.

- sik: Tiempo de servicio en el nodo i por el vehículo k.

- dij: Distancia entre el nodo i y el nodo j (i ≠ j).

- tij : Tiempo de conducción entre los nodos i y j.

- Tk: Tiempo máximo de operación para cada vehículo k.

Las variables de decisión del problema son:

- xijk: Variable binaria, será 1 si el vehículo k є {1,…,m} viaje de i a j (i ≠ j).

- yik: Instante de comienzo del servicio en el nodo i є {0,1,…,n} por el vehículo k; y0

k recoge el fin del servicio del vehículo k.

- fijk : Carga transportada del vehículo k є {1,…,m} entre los nodos i y j (i ≠ j).

Las restricciones del modelo:

3. Diseño de la búsqueda tabú

47

),...,1(11

0 mkxn

j

kj =≤∑

=

0 0

0( 1,..., ; 1,..., )= =≠ ≠

− = = =∑ ∑n n

k kij ji

j jj i j i

x x k m i n

)n,...,1i(1xm

1k

n

ij0j

kij ==∑∑

=≠=

)m,...,1k(qxDt

1i

kn

ij0j

kiji =≤∑ ∑

=≠=

∑∑∑= += =

=m

1k

n

1ti

t

1j

kij 0x

∑∑= +=

=m

1k

n

1tj

kj0 0x

)m,...,1k;ij;n,...,0j;n,...,1i()x1(Tytsy kij

kkjij

ki

ki =≠==−+≤++

)m,...,1k;n,...,1j()x1(Tyt kj0

kkjj0 ==−+≤

)m,...,1k;n,...,1i(lye ikii ==≤≤

)m,...,1k(Ty kk0 =≤

)t,...,1i(Dffm

1ki

n

ij0j

kij

m

1k

n

ij0j

kji ==−∑∑∑∑

=≠==

≠=

)n,...,1ti(Dffm

1ki

n

ij0j

kji

m

1k

n

ij0j

kij +==−∑∑∑∑

=≠==

≠=

)m,...,1k;ij;n,...,0j;t,...,0i(x)Dq(f kiji

kkij =≠==−≤

)m,...,1k;ji;n,...,0i;t,...,1j(fxD kij

kijj =≠==≤

)m,...,1k;ij;n,...,0j;n,...,1ti(fxD kij

kiji =≠=+=≤

)m,...,1k;ji;n,...,0i;n,...,1tj(x)Dq(f kijj

kkij =≠=+=−≤


48

El primer conjunto de restricciones (1) implica que no más de m vehículos parten del depósito (fleet size). A continuación se describen las ecuaciones de conservación de flujo (2) por cada nodo. La imposición de unicidad en las visitas es impuesta en las restricciones (3), los clientes sólo serán visitados una vez. El grupo de restricciones 4 y 5 aseguran que los vehículos no serán sobrecargados. Las restricciones en 6 garantizan que primero se visitan a los clientes y posteriormente a los proveedores, mientras que el grupo 7 de restricciones evita que salgan vehículos vacíos con dirección a los proveedores. Las restricciones 8 y 9 son empleadas para obtener el instante de inicio del servicio en los clientes y proveedores, así mismo son las restricciones encargadas de evitar la formación ciclos (y causantes del que el problema sea NP-Duro). La imposición de cumplimiento de las ventanas de tiempo se describe en las restricciones 10. Así mismo, se impide que la utilización o número de horas de trabajo de los conductores sea excesiva mediante la restricción 11. El balance de flujo de carga entre nodos se describe mediante las restricciones 12 y 13. Las restricciones 14-17 son empleadas para restringir la carga total de los vehículos dependiendo si llega o sale de un cliente o proveedor.

El objetivo del modelo es diseñar o proponer rutas para diferentes vehículos tal que minimice los costes internos y los costes externos. Los costes internos (IC) asociado con una ruta están compuestos por 4 elementos. Estos se corresponden a los costes del conductor (DRC), costes energéticos (ENC), costes fijos de adquisición, seguros, etc (FXC), costes de mantenimiento (MNC) y costes de peajes (TLC). Además se incluye los costes de las externalidades, estructurados en cuatros componentes tales como costes de cambio climático (CCC), costes de emisiones contaminantes (APC), costes de ruido (NSC) y coste de accidentalidad (ACC).

)()( ACCNSCAPCCCCTLCMNCFXCENCDRCECICMinimize ++++++++=+ (18)

Las ecuaciones matemáticas que sirven para expresar los costes de la función objetivo son:

km

k

k ypDRC 01∑

=

=

(3.1)

∑∑∑∑=

≠= = =

+=n

i

n

ijj

m

k

R

r

kij

kkij

kij

krr ffeuxfedfcENC0 0 1 1

)(δ

(3.2)

∑∑= =

=n

i

m

k

ki

k xfxFXC1 1

0

(3.3)

∑∑∑=

≠= =

=n

i

n

ijj

m

k

kijij

k xdmnMNC0 0 1

(3.4)


49

∑∑∑=

≠= =

=n

i

n

ijj

m

k

kijij xtlTLC

0 0 1

(3.5)

∑∑∑∑=

≠= = =

+=n

i

n

ijj

m

k

R

r

kij

kkij

kij

rCOkrCO ffeuxfedefpeCCC0 0 1 1

,22 )(δ (3.6)

∑∑∑∑∑∑=

≠= = = = =

=n

i

n

ijj

m

k

R

r

T

t

P

p

kijij

tpktkrp xdefpeAPC0 0 1 1 1 1

,γδ

(3.7)

∑∑∑=

≠= =

=n

i

n

ijj

m

k

kijij fdneNSC

0 0 1

(3.8)

∑∑∑=

≠= =

=n

i

n

ijj

m

k

kijij fdaeACC

0 0 1

(3.9)

Los datos y parámetros empleados en la definición del modelo son:

- pk: Salario del conductor k por unidad de tiempo.

- fcr: Coste o precio por unidad de combustible del tipo r.

- fek: Consumo de combustible del vehículo k en vacío.

- feuk: Consumo de combustible por unidad adicional de carga para el vehículo k.

- δkr: Igual a 1 si el vehículo k usa el combustible de tipo r.

- fxk: Coste fijo para el vehículo k.

- mnk: Coste de mantenimiento preventivo, reparaciones, desgaste de neumáticos por kilómetro para el vehículo k.

- tl ij: Coste de peajes asociado a los arcos (i,j).

- peCO2: Preci de cada unidad de CO2 emitida.

- efCO2,r: Factor de emisión, cantidad de CO2 emitida por unidad de fuel consumida.

DISEÑO E IMPLEMENTACIÓN DE UNA BÚSQUEDA

- pep: Precio por tonelada de contaminante

- efp,t: Emisiones de contaminante del tipo t.

- δkt: igual a 1 si el vehículo k

- ne: Coste de emisión de ruido por tonelada transportada y k

- ae: Coste de accidentes por tonelada cargada y k

3.2. Diseño de la Búsqueda TabúLa complejidad inherente al problema combinatorio del VRP hace imprescindible la articulación de diversos métodos, que trabajando conjuntamente, aporten un resultado satisfactorio acorde con las expectativas, más si cabe cuando no “sólo” se pretende rutar tiempo o distancia, sino que otras consideraciones internas y externas a una flota de vehículos heterogénea entran en juego.

En este sentido, y tras un análisis cuidadoso de la literatura, se ha decidido afrontar el pfases, que se desglosan en la figura 10.

Figura 11.

La primera fase, Formación Solución Inicial, proporciona, si fuera posible, una rutado admisible dentro del espacio de soluciones, pero no asegura, en ningún caso, un costahí que los dos pasos siguientes se efectúen en pos de una reducción del coste total de la solución.

En la segunda fase, Intercambio λintercambio (sección 4.1.5.) modifprimera fase.

Y por último, se realiza una Búsqueda Tabú (BT en adelante) personalizada sobre la solución calculada en los dos pasos anteriores. El mejor rutado se obtiene una vez concluido

3.2.1. Solución inicial Mole-Jameson

Esta heurística utiliza dos medidas para decidir el próximo cliente a insertar en la primer lugar, para cada cliente no visitado se calcula la mejor posición para ubicateniendo en cuenta solamente las distancias y sin reordenar los nodos que ya están en la ruta. Se tiene una ruta (v0, v1,…., vt, vt+1) donde entre vi y vi+1 (0 ≤ i ≤ t) se define como

Solución Inicial

ÚSQUEDA TABÚ PARA EL VRP CON CRITERIOS DE SOSTENIBILIDAD

50

: Precio por tonelada de contaminante p emitido.

Emisiones de contaminante del tipo p emitida por kilómetros por un vehículo de categoría

k es de la categoría t.

e ruido por tonelada transportada y kilómetro viajado

: Coste de accidentes por tonelada cargada y kilómetro viajado.

Diseño de la Búsqueda Tabú La complejidad inherente al problema combinatorio del VRP hace imprescindible la articulación de diversos métodos, que trabajando conjuntamente, aporten un resultado satisfactorio acorde con las expectativas, más si cabe cuando no “sólo” se pretende rutar un conjunto de vehículos minimizando tiempo o distancia, sino que otras consideraciones internas y externas a una flota de vehículos

En este sentido, y tras un análisis cuidadoso de la literatura, se ha decidido afrontar el pfases, que se desglosan en la figura 10.

Figura 11. Fases de la Búsqueda Tabú

La primera fase, Formación Solución Inicial, proporciona, si fuera posible, una rutado admisible dentro del espacio de soluciones, pero no asegura, en ningún caso, un coste aceptablemente bueno. De ahí que los dos pasos siguientes se efectúen en pos de una reducción del coste total de la solución.

En la segunda fase, Intercambio λ-opt, se realizan los movimientos descritos en El operador intercambio (sección 4.1.5.) modificando, si es que se halla mejora, la solución proporcionada en la

Y por último, se realiza una Búsqueda Tabú (BT en adelante) personalizada sobre la solución calculada en los dos pasos anteriores. El mejor rutado se obtiene una vez concluido

Jameson

dos medidas para decidir el próximo cliente a insertar en la para cada cliente no visitado se calcula la mejor posición para ubica

teniendo en cuenta solamente las distancias y sin reordenar los nodos que ya están en la ruta. Se tiene ) donde v0 = vt+1 = 0. Si w es un cliente no visitado, el costo de insertar

) se define como

Intercambio λ-opt

Búsqueda tabú

CON CRITERIOS DE SOSTENIBILIDAD

emitida por kilómetros por un vehículo de categoría

viajado.

La complejidad inherente al problema combinatorio del VRP hace imprescindible la articulación de diversos métodos, que trabajando conjuntamente, aporten un resultado satisfactorio acorde con las

un conjunto de vehículos minimizando tiempo o distancia, sino que otras consideraciones internas y externas a una flota de vehículos

En este sentido, y tras un análisis cuidadoso de la literatura, se ha decidido afrontar el problema en tres

La primera fase, Formación Solución Inicial, proporciona, si fuera posible, una rutado admisible e aceptablemente bueno. De

ahí que los dos pasos siguientes se efectúen en pos de una reducción del coste total de la solución.

opt, se realizan los movimientos descritos en El operador λ-icando, si es que se halla mejora, la solución proporcionada en la

Y por último, se realiza una Búsqueda Tabú (BT en adelante) personalizada sobre la solución calculada en los dos pasos anteriores. El mejor rutado se obtiene una vez concluido este paso.

dos medidas para decidir el próximo cliente a insertar en la ruta actual. En para cada cliente no visitado se calcula la mejor posición para ubicarlo en la ruta actual

teniendo en cuenta solamente las distancias y sin reordenar los nodos que ya están en la ruta. Se tiene es un cliente no visitado, el costo de insertar w

Búsqueda


51

1 11 , , ,( , ) λ

+ += + −

i i i ii v w w v v vc v w c c c (5.6)

Si (v0,…., vi,w,vi+1,….,vt+1) es factible. Si no, se daría el valor ∞ a la igualdad. La mejor posición para insertar el cliente w en la ruta actual está dada por,

10 ,...,

( ) arg min ( , )=

= ii ti w c v w (4.7)

Si se utilizara solamente la medida c1 para decidir el próximo cliente a insertar, es probable que los clientes lejanos al depósito no sean tenidos en cuenta sino hasta las iteraciones finales del algoritmo, es decir, cuando sean las únicas alternativas factibles. Por lo tanto, es necesario utilizar un incentivo adicional para la inserción de clientes lejanos al depósito. Se define c2(vi,w) = µc0w−c1(vi,w) para cada cliente w. En cada iteración se busca el cliente que maximiza la medida c2 (llamada medida de urgencia) y se lo inserta en la posición dada por el mínimo valor de c1.

Además de las medidas anteriores, debe considerarse la factibilidad de las inserciones. Cuando ninguna inserción es factible y si aún quedan clientes sin visitar, se selecciona un cliente para comenzar una nueva ruta.

Esta definición se ciñe a unas características de clientes, depots y flota muy básicas. De ahí que deba generalizarse y adaptarse a la variedad de datos y parámetros cuando se quiere ampliar el objetivo de minimizar la distancia a otros con criterios eco-eficientes. Es decir, hay que diseñar una serie de modificaciones y módulos o conceptos extras sobre el algoritmo original para que permitan hacer uso de él sin perder su filosofía. Se necesitan añadir las características de los vehículos de la flota disponible, la definición en distancias, tiempos y peajes de todos los arcos que unen a los clientes, y los contaminantes.

Para ello, aquí se desglosa el nuevo procedimiento matemático, la lógica en bloques y modificaciones de otra índole realizadas en los distintos pasos para adaptar el objetivo original de minimizar la distancia en otro que contenga los costes por contaminación.

A grandes rasgos, el nuevo modelo se resume en el esquema de bloques de la figura 11. Los distintos pasos que se muestra en dicha figura se detallan a continuación:

• Ordenar la flota. Este paso inicial ordena los vehículos disponibles de la flota según su capacidad, listándose de mayor a menor o viceversa.

• Calcular todos los costes tras insertar w en todas las posiciones. En principio, para realizar estos cálculos bastaría con aplicar la definición dada por la ecuación 2.1 sin embargo la internalización de los aspectos medioambientales y las ventanas de tiempo de los clientes obligan a redefinir la dicha ecuación en otra (ecuación 2.2). Estos cambios producirán efectos de calado pues las consideraciones que se toman en la conversión de distintas medidas en euros


52

Figura 12. Diagrama de flujo del algoritmo diseñado en base a Mole-Jameson

provocan que no siempre las ciudades más cercanas a un nodo dado sea las más convenientes de elegir, ya que su coste puede ser mayor que otra que, a priori, no está tan cerca geográficamente hablando.


53

Esto se debe a que en el coste total se computan tanto costes internos como costes externos. Es decir, la primera modificación importante surge de la disgregación del coste en dos sumandos (cint + cext) y de la dependencia con el camión elegido (r).

1 int( , , ) ( , , ) ( , , )= +i i ext ic v w r c v w r c v w r

Para entender el funcionamiento interno de cint y cext es esencial aclarar cómo intervienen las entidades básicas con las que opera el algoritmo adaptado y que influyen decisivamente en el criterio de selección de la ciudad w. Se podrían resumir en cuatro: tiempo entre ciudades, ventanas de tiempo, costes internos y costes externos.

Tiempo entre ciudades. Hablar de tiempo o distancia, si se asume un desplazamiento a una velocidad constante determinada, es válido igualmente. En este caso, se usa el tiempo directamente para que no sea necesaria la adición de un factor de velocidad en la ruta para compatibilizarlo con las medidas de tiempo usadas en las ventanas de tiempo.

Ventanas de tiempo. Una ventana de tiempo se define como un intervalo en el que el cliente exige la llegada del vehículo para ser atendido. Matemáticamente, se expresa como [ek,lk] para cada cliente vk. Esta ventana influye decisivamente en el criterio de elección, pues redefine la “cercanía” o “lejanía” entre un par de ciudades. De ahí que el tiempo empleado en desplazarse de un nodo k a k+1 a otro se calcule como:

, 1 1 , 1m ax( , )+ + += + + −k k k k k k k kt e b s t b

Donde bk es el instante de atención al vehículo cuando visita a vk. El valor de bk depende del instante de llegada a vk, cuyas posibilidades son las tres que su muestran en la gráfica siguiente:

Figura 13. Posibilidades de llegada de un vehículo r a una ciudad vk.

La línea de llegada roja simboliza todos aquellos casos en que los vehículos llegan a la ciudad vk con un tiempo total de llegada menor que (tllegada < ek). La verde representa a los casos en que llegan entre ek y lk (ek ≤ tllegada ≤ lk). Y en último lugar, aquellos en los que el vehículo llega después de lk (tllegada > lk). El valor de bk se define como bk=ek si tllegada<ek, y bk=tllegada e.o.c.

Estas tres casuísticas afectan directamente al valor del coste entre el nodo vk y vk-1. Tanto para la línea roja como para la verde, la inserción de vk es posible. No así con el caso de la línea azul, que no puede ser admitido porque está violando la condición de cumplimiento de ventana de tiempo. Por tanto, y tal y como establece el algoritmo original, el coste desde vk-1 a vk tomaría el valor c1(vk,w) = ∞ (o desconsiderado por otros medios).

lk ek


54

Las ventanas de tiempo no sólo afectan a la admisibilidad de una inserción sino que también cambian el concepto de cercanía entre dos nodos vk y vk+1. Es posible que cuando se tienen dos ciudades candidatas (va y vb) para insertar entre dos ciudades (vk y vk+1) suceda lo siguiente: Que aún estando la ciudad va muy cerca en tiempo, su ventana ea sea tan elevada que otra ciudad vb, a priori más lejana, esté “más cerca” porque su ventana eb es menor, siendo esta última la elegida por el algoritmo. Matemáticamente se resumiría afirmado que t(vk, va) < t(vk, vb), y ea >> eb (los tiempos de servicio, sa y sb se consideran despreciables).

En la práctica, esto se traduce en que en la función objetivo los tiempos muertos que emplean los vehículos para que el cliente les atienda incurren en costes que empeoran el coste de la ruta.

Gastos internos. Se definen por la cuádrupla {coste fijo del vehículo (fxr), coste de mantenimiento (mnr), coste del peaje (tl ij) en el arco (i,j), salario del conductor (pr)}. Es evidente que existe una dependencia directa de estos gastos con el kilometraje recorrido, el tiempo empleado y el camión elegido. Los factores que intervienen en la concreción de la próxima ciudad en la ruta ya no se limitan a criterios geográficos, sino que hay parámetros propios del camión elegido que pesan en la decisión final. La cuádrupla queda definida de la siguiente manera:

int , ,( , , ) = + + +i i

r r ri ij v w v wc v w r fx tl p t mn d

La obtención de la distancia en el arco (vi,w) es sencilla y directa, pues nunca depende del punto de referencia que se use sin embargo, no ocurre lo mismo con los el tiempo, en los que hay que fijar los puntos iniciales y finales. En este trabajo, el tiempo entre dos arcos se define de la siguiente manera:

, ,max( , )= + + −i

i i i i

vv w w v v w vt e b s t b

Gastos externos. Intervienen más factores que en el caso anterior, aunque ninguno de ellos con dependencia temporal. Estos son: ae, coste de accidentes, ne, coste de emisión de ruido, efp,t, emisiones de contaminante del tipo por vehículo de categoría t, pep, precio de contaminante p emitido, efCO2,r factor de emisión de CO2, peCO2, precio de CO2, Los gastos externos entre un arco (vi,w) definidos se calculan de la siguiente manera:

2 2,,

1

( , , ) (1 ) ( )i

k k PijCOk CO r r k p p

ext i v w ij ij ijkp

feu fc v w r d fe pe ef fx d f ne ae d pe ef

fe =

= + + + + ∑ (1.1)

No tienen ningún tipo de dependencia temporal, pero sí una muy fuerte tanto con la distancia recorrida como con la carga que el camión debe transportar entre un par de nodos.

• Comprobar la admisibilidad de w en todas las posiciones En este paso, se tiene toda la información de los costes cuando se inserta una ciudad en todas las posiciones posibles de una ruta. Por “todas las posiciones posibles” se entiende lo siguiente: sea la ruta {0-6-5-0} una ruta en una iteración i para un camión r. Entonces las combinaciones posibles para insertar un nodo candidato pueden ser {0-w-6-5-0}, {0-6-w-5-0} y {0-6-5-w-0}.


55

Existen dos condiciones que toda ruta debe cumplir para ser admisible:

1. Que el tiempo de llegada a todos los clientes atendidos no exceda ninguna de los límites superiores de las ventanas de tiempo.

2. Que el tiempo total recorrido en la ruta no sea mayor que el máximo tiempo de operación de cada vehículo.

Si se cumplen ambas, la ciudad es candidata a ser insertada en la ruta actual.

• Elegir ciudad y posición con menor coste Del paso anterior, se elige para cada ciudad la posición en la ruta cuyo coste es menor. Y gracias a la ecuación c2(vi,w) = µc0w−c1(vi,w), se elige la ciudad, entre las elegidas justo antes, que ofrece el coste menor de todas, es decir, el que maximiza c2.

• Actualiza ruta Se inserta en la ruta que hasta el momento se había asignado a un camión, la nueva ciudad encontrada en el paso anterior.

3.2.2. Movimiento λ-opt

El movimiento λ-opt, formalmente conocido como operador λ-intercambio, es un algoritmo de búsqueda local que elimina λ arcos (λ>1) y reconecta los λ segmentos restantes. Las posibilidades que ofrece el diseño que se presenta en este documento son λ = {0,2,3}. Con λ = 3, el algoritmo, implícitamente, también realiza las posibles reconexiones que se darían con λ = 2, así que suele ser la opción más elegida. En caso de λ = 0, esta heurística se obvia y se ejecuta la Búsqueda Tabú.

El algoritmo de Mole & Jameson, a pesar de proporcionar una solución correcta, puede que no establezca el mejor orden posible de entre las ciudades que elige. La aplicación de un movimiento opt explora la mejor combinación de visita a los clientes atendidos en una ruta cuando se eliminan λ arcos (contabilizar todos las posiciones posibles es demasiado caro computacionalmente hablando).

En caso de solicitar la ejecución de este operador, siempre se aplicará dentro del algoritmo de M&J tras conformar definitivamente una ruta. Opera de la siguiente manera:

Paso 1. Verifica que el número de ciudades en la ruta es mayor que dos (el depot no se incluye).

Paso 2. En caso de λ = 2, se elige la siguiente combinación de par de arcos (no contiguos). Si λ = 3, los arcos sí pueden ser contiguos. Una vez elegidos, se eliminan de la ruta.

Figura 14. Pseudocódigo de formación de eliminación de arcos en operador λ-intercambio

Desde pri_arco=1,…,n_arcos-2

Desde seg_arco=pri_arco+2,…n_arcos

Elimina (pri_arco,seg_arco)


56

Paso 3. Se comprueba la admisibilidad en términos de ventanas de tiempo y máximo tiempo en ruta permitido para cada una de las rutas anteriores, tanto en un orden de visita (en el sentido de las agujas del reloj) como el contrario (véase figura 13).

Paso 4. Se chequea si el mejor coste hallado en el paso 3 es el mejor hasta el momento. Se actualiza el mejor coste y movimiento si así fuera.

Paso 5. Si quedan combinaciones de arcos por eliminar vuelta al paso 5. Si no, se modifica la ruta de partida (la hallada por M&J) en caso de que el coste se haya mejorado y finaliza el algoritmo.

3.2.3. Búsqueda Tabú

El diseño de la Búsqueda Tabú (BT) de tres listas que se presenta en este trabajo es en esencia una fusión de las tácticas definidas en el algoritmo de Osman y Taburoute más una serie de ampliaciones en forma de métodos de intensificación y diversificación que se adaptan a las características del problema VRP: memoriza “estados” de soluciones, inserta o intercambia ciudades según el número de iteraciones sin mejorar e incorpora la capacidad de aceptar soluciones no válidas con la intención de hallar soluciones admisibles tras un conjunto de movidas indeterminado.

La BT posee una terminología muy específica que cada autor redefine en base a criterios propios como, por ejemplo, la definición de movimiento tabú. Puesto que la riqueza de acepciones es extensa, se presenta a continuación el modelo completo para evitar comprensiones erróneas.

La BT entra en juego cuando ya se ha resuelto el problema VRP (M&J más movimiento opt) y se posee pues una solución admisible en la que se asignan grupos de ciudades en orden a distintos vehículos de la flota. Este conjunto de rutas se recogen en R = {r1,…,rh}. Cada ruta, r i, está compuesta, a su vez, por un conjunto finito de ciudades V = {v1,…,vn}. La BT realiza intercambios para rebajar el coste de la solución.

En un intercambio es un movimiento en el que intervienen un par de ciudades, vi y vj, (i≠j) que

pertenecen, respectivamente, a un par de rutas, rq y rp, (q≠p). El intercambio se define como el movimiento de vi a rp y de vj a rq. Dicho intercambio garantiza que las nuevas posiciones de vi y vj son las que resultan en un menor coste de rp y rq, respetando las ventanas de tiempo y el máximo tiempo de operación del vehículo asignado a ambas rutas. Estos intercambios tienen una notación propia en este trabajo, representada mediante {vi,rq,vj,rp}, aunque las inserciones también la usan. Los movimientos se realizan sobre una solución, es decir, el conjunto de rutas asignadas a la flota que ha resuelto el problema HF-VRPTW.

Existen dos movimientos denominados mejor movimiento y movimiento parcial que aseguran el mejor coste posible en un alcance determinado. Para conocer el rango de actuación, es necesario describir todas las combinaciones de pares rutas-ciudades que realiza la BT. Se articulan de la siguiente manera:


57

Figura 15. Pseudocódigo de formación de movimientos en BT.

El movimiento parcial se define como aquel que, fijados los valores {vi,rq,vj,rp}, encuentra las posiciones de las ciudades vi en rp y de vj en rq cuyo coste es menor. Y mejor movimiento contiene el movimiento una vez que han sido exploradas todas las rutas con todas las combinaciones posibles entre ciudades. Cada vez que se realiza este proceso completo, es decir, que se ha recorrido la solución al completo se dice que el algoritmo ha terminado una iteración.

Tras cada iteración, la BT modifica siempre la solución con la información en mejor movimiento y lo almacena en una lista tabú cuyo tamaño ha sido declarado previamente. Si el coste total de la solución ha sido mejorado respecto a las anteriores, este mejor movimiento junto con su coste se guarda en otra entidad denominada mejor movimiento absoluto.

Cuando se realizan los movimientos parciales, la BT comprueba en primer lugar que el movimiento parcial no es movimiento tabú. Se interpreta que un movimiento es tabú cuando en un movimiento al menos una de las ciudades implicadas (vi ó vj) ya ha sido previamente intercambiada o insertada. De esta forma tal vez se limita en exceso la movilidad de los nodos, pero si se considerara la pareja de ciudades y no las ciudades en sí, el algoritmo puede caer en bucles indeseados y dejar de explorar el espacio de soluciones. En un caso sencillo, si se tienen dos rutas con dos ciudades cada una, R = {{0-1-2-0}, {0-3-4-0}}, podría darse la siguiente consecución de intercambios:

Figura 16. Bucle en BT

Si un movimiento es tabú y su coste es superior al mejor coste hallado en todas las iteraciones, entonces se descarta. Si, por el contrario, es tabú y su coste es inferior al mejor coste hallada anteriormente entonces se acepta y se guarda en mejor movimiento. Esto es lo que se llama criterio de aspiración.

A grandes rasgos, este es el funcionamiento general de la BT para una solución de partida. Sin embargo, es necesario ampliar los métodos de búsqueda para escudriñar con aún más detalle el espacio de soluciones.

3.2.4. Ampliaciones

En el apartado 5.2.3., se ha planteado el funcionamiento de una BT que posee una sola lista tabú y no contempla mecanismos de diversificación e inadmisibilidad. Sin embargo, la BT que se implementa en este trabajo tiene tres listas que trabajan en paralelo y ofrece la posibilidad de aceptar soluciones no admisibles así como desplazarse en el espacio de soluciones gracias a un método de diversificación por inserción de ciudades entre rutas.

{0,1,1,3}�{0,3,1,4}�{0,4,1,1}

Desde rq=1,…,rq=h Desde rp=1,…,rp=t, t≠h Desde vi=1,…,vi=l Desde vj=1,…,vj=m, m≠l Movimiento (vi,rq,vj,rp,)


58

De las tres listas, una de ellas contiene las inserciones tabú y se llama inser. Una inserción se define como el movimiento admisible en el que se extrae una ciudad vi de una ruta rq y se inserta en rp, pero, al contrario que en un intercambio, ninguna ciudad de rp se transfiere a rq. Tras una efectuar una inserción, la solución siempre es admisible (respeta todas las restricciones del VRP). Queda representado por la cuádrupla {vi,rq,vj,rp}, y la casilla de la ciudad correspondiente a la ruta de donde no se extrae ninguna adquiere el valor -1. Por ejemplo, {1,-1,3,4} indicaría que se extrae la ciudad 4 de la ruta 3 y se inserta en la ruta 1. Las inserciones son los movimientos que proveen a esta BT de un mecanismo de diversificación

La intensificación, por el contrario, se efectúa solo con intercambios de dos tipos: admisibles y no admisibles. Dentro del contexto de BT, se define un intercambio como admisible si tras desplazar el par de ciudades a sus rutas de destino, la demanda total de los clientes en todas y cada una de las rutas de la solución no excede la capacidad de los vehículos que las atienden. Ambos intercambios, tanto si son admisibles como no admisibles siempre respetan las restricciones de las ventanas de tiempo y del máximo tiempo en ruta de los vehículos. Existe una lista tabú para cada tipo de intercambio, llamadas inter y NAinter (No Admisible).

La diversificación e intensificación interactúan por medio de las tres listas tabú: inser, inter y NAinter. El paso de un método a otro queda definido por una serie de parámetros que puede amoldarse a cada problema VRP.

Gráficamente, el significado pasar de un método a otro es bastante intuitivo. Cuando se ejecuta un proceso de diversificación se está dando un salto en el espacio de soluciones en busca de nuevos mínimos, pues se supone que ya no es posible hallar mejores rutas en la zona anterior. Tras realizar este salto, se explora minuciosamente el espacio próximo al punto actual para encontrar valles (puntos de menor coste que sus vecinos). Este fenómeno se puede observar en la figura 13.

Cada segmento rojo simboliza el desplazamiento en el espacio de soluciones tras una iteración (puede ser para mejorar o empeorar el coste). El conjunto de segmentos rojos se produce mientras que el algoritmo se encuentra en una fase de intensificación. Después de un cierto número de iteraciones sin hallar un mejor resultado, la BT modifica la solución actual con una inserción, que se representa como un salto en el espacio (línea azul). Esta es la consecución de pasos que efectúa la BT desde un punto de vista gráfico.

Figura 17. Efecto de la diversificación e intensificación en el espacio de soluciones


59

Desde un punto de vista más analítico y formal, estos fenómenos gráficos descritos en la figura 17 tienen su origen en una interacción entre las 3 listas tabú, que queda definida en el siguiente diagrama de flujo.


60

Figura 18. Diagrama de flujo de la Búsqueda Tabú


61

En el diagrama puede verse como se ha incluido la posibilidad de admitir soluciones no admisibles. En el caso que se descarte esta opción, el algoritmo operaría de forma semejante, aunque, como es obvio, ignoraría dichas soluciones.

Aquellas instrucciones que no se describen con una asignación o comparación sencilla, poseen un funcionamiento interno que merece mostrarse en detalle. Punto por punto, estas son las principales características:

• INICIO La BT parte de la solución inicial calculada por el algoritmo M&J y mejorada, después, por el λ-intercambio. Se heredan pues todos los datos de los que se disponía en pasos anteriores.

• Buscar Mejor_NAIntercambio y Mejor_Intercambio Este paso es el responsable de examinar todos los intercambios posibles entre las ciudades a las que se le ha asignado un vehículo para su abastecimiento. Se asume que la posibilidad de considerar soluciones no admisibles es aceptada. De lo contrario, habría que tomar la misma definición que se va a mostrar, pero obviando aquellas partes en las que las soluciones no admisibles entren en juego.

En este punto de la BT ya se ha obtenido una solución (solución_inter). Sobre ella se aplicará el método de intensificación con el objetivo de refinar los resultados de partida (rebajar el coste de solución_inter). Se opera de la siguiente manera:

Paso 1. Se examinan todas las combinaciones posibles entre ciudades. Es decir, se forman todos los movimientos mostrados en la figura 15.

Paso 2. Desde el punto de vista de la carga, se cataloga el movimiento como admisible o no admisible (NA). Esto quiere decir que se comprueba, primero, que al extraer la ciudad vi e insertarla en rp, la demanda total de rp no excede la capacidad del vehículo que la atiende. Y, segundo, se verifica que al extraer la ciudad vj e insertarla en rq, la demanda total de rq no excede la capacidad del vehículo que la abastece. De cumplirse ambos puntos, el movimiento se clasifica como admisible, y sólo con que uno de ellos no se cumpla, el movimiento se declara inadmisible. Obsérvese que las comprobaciones son a posteriori, es decir, que si por cualquier motivo se parte de una solución sobrecargada pero al hacer el intercambio, todas y cada una de las rutas de solución_inter se reconfiguran y sus demandas pueden ser atendidas por sus respectivos vehículos, el movimiento se considerará admisible. Este último caso rara vez se produce, pues en un intercambio intervienen sólo dos rutas. De ahí que si cualquier otra ruta está sobrecargada, es imposible hacer admisible el movimiento.

Paso 3. Se elige la mejor posición de vi como de vj en sus nuevas rutas respectivas, acotando previamente los puntos posibles de inserción mediante una verificación por el límite superior de la ventana de tiempo. De esta manera, la BT ahorra tiempo computacional, al no comprobar todas y cada una de las posiciones en la nueva ruta.

En un intercambio {vi,rq,vj,rp}, la forma en la que se insertan ambas ciudades en sus nuevas rutas es idéntica, así que se estudia el caso en el que vi pasa a rp.


62

1. Se localiza el punto de salida de vj. 2. Se sitúa a vi en la posición k-ésima de la ruta. 3. Las ciudades que quedan entre la posición k y la vacante dejada por vj, se desplazan en sentido

desde la posición k a vj. 4. Dependiendo de la posición relativa k respecto a la posición libre de vj, se considera que la

inserción de vi es factible o no. El criterio queda definido en las ecuaciones que siguen.

( )

( 1)

( )

( )

( )

( )

, ( )

, ( )

, ( )

i pos k

i pos k

pos k i

v v pos k j

v v pos k j

v v pos k j

e l siv pos v

e l siv pos v

e l siv pos v+

≤ <

≤ =

≤ >

(1.2)

Nótese que este criterio simplemente restringe el número de posiciones y sólo asegura que al posicionar vi en k, las ciudades desde k+1 hasta el depot puedan ser atendidas. Sin embargo, puede darse el caso en el que una ciudad situada desde k-1 hasta el depot tenga un valor et > lvi, con t={k-1,k-2,…,0}, inhabilitando así la posición de vi en k. No obstante, en el paso siguiente este caso y otros inadmisibles se descartan.

Paso 4. Posteriormente se determinan, con total certeza, las posiciones admisibles de vi e vj por ventana de tiempo y máximo tiempo en ruta del vehículo y, de entre ellas, se elige la que redunda en un menor coste. Se computa el coste total de solución_inter con este movimiento {vi,rq,vj,rp} y se compara con mejor_intercambio en el caso de movimientos admisibles y con mejor_NAintercambio en el caso de los no admisibles, actualizándolos en caso de mejora y de no ser tabú (a no ser que cumplan el criterio de aspiración). A la hora de determinar si un intercambio es tabú, ya sea admisible o no admisible, se compara con los registrados hasta dicha iteración en ambas listas, para evitar que la BT entre en un bucle “cruzado”. Vuelta al paso 1.

• Modificar Solución_Inter con Mejor_(NA)Intercambio. Actualiza (NA)Inter Se aplica definitivamente el mejor intercambio a solución_inter y se registra en su respectiva lista tabú (NAinter si el mejor fue mejor_intercambio o inter si el mejor fue mejor_NAintercambio). Si no hubo mejora respecto al mejor resultado admisible registrado hasta dicha iteración, se incrementa max_sin_mejora.

• Inicializar listas NAinter e Inter Se borran todos los intercambios y mejores movimientos registrados durante las iteraciones anteriores, ya que se considera que tras la inserción el cambio en la solución es radical y, por tanto, hay que refinar las nuevas búsquedas de mínimos sin tener ningún tipo de memoria.

• Buscar Mejor Inserción Se procede de manera similar a lo descrito en Buscar Mejor_NAIntercambio y Mejor_Intercambio, sin embargo, existen ciertas diferencias pues la búsqueda en este caso sólo posee una lista tabú y los movimientos desempeñados son exclusivamente inserciones. Al tratarse de inserciones, sólo se consideran aquellas que son admisibles en carga y tiempo (ventanas y tiempo máximo en ruta). Una


63

inserción se considera admisible si y sólo si tras efectuarse dicho movimiento la solución al completo es admisible.

Este módulo siempre parte de la solución guardada en Solución_Inser y sobre ella efectúa la siguiente BT:

Paso 1. Se establecen todas las posibles inserciones de una ciudad en el resto de rutas disponibles, de forma que:

Figura 19. Pseudocódigo de formación de inserciones en BT

Paso 2. Del movimiento propuesto en Paso 1, {vi,rq,vj,rp}, se extraen {vi,rq,-1,rp} y { -1,rq,vj,rp} que representan respectivamente la inserción de vi en rp y la de vj en rq. Se comprueban que dichas inserciones no violen la restricción de carga en la ruta de destino. Si alguna de ellas la cumple, se prosigue en el paso 3, si, por el contrario, ninguna de las dos la satisface se vuelve al paso 1. Obsérvese que en este caso, al contrario de lo que sucede en Buscar mejor_NAintercambio y mejor_intercambio, no hace falta comprobar que la solución al completo sea admisible, pues todas las rutas de solucion_Inser siempre lo son, así que basta con chequear la ruta destino (la ruta de partida tendrá menos carga después de la inserción).

Paso 3. Se dirime cuál(es) de las dos inserciones posibles, {vi,rq,-1,rp} y { -1,rq,vj,rp}, son admisibles. A continuación, se elige la mejor posición de vi en rp y/o de vj en rq, acotando previamente los puntos posibles de inserción mediante una verificación por el límite superior de la ventana de tiempo. De esta manera, la BT ahorra tiempo computacional, al no comprobar todas y cada una de las posiciones en la nueva ruta.

En una inserción {vi,rq,-1,rp}, la forma en la que se inserta vi en rp viene determinada por los siguientes pasos:

1. Se sitúa a vi en la posición k-ésima de rp 2. Las ciudades de rp que quedan entre la posición k y el depot (considerado como punto final de

la ruta, no punto inicial) se desplazan hacia este último. 3. Se considera como posiciones posibles de vi a rp aquellas que cumplen la condición:

( )i pos kv ve l≤ (1.3)

Nótese que este criterio simplemente restringe el número de posiciones y sólo asegura que al posicionar vi en k, las ciudades desde k+1 hasta el depot puedan ser atendidas. Sin embargo, puede darse el caso en el que una ciudad situada desde k-1 hasta el depot tenga un valor et > lvi, con t={k-1,k-2,…,0}, inhabilitando así la posición de vi en k. No obstante, en el paso siguiente este caso y otros inadmisibles se descartan.

Desde rq=1,…,rq=h Desde rp=1,…,rp=t, t≠h Desde vi=1,…,vi=l Desde vj=1,…,vj=m, m≠l Movimiento (vi,rq,-1,rp)

Movimiento (-1,rq,vj,rp)


64

Paso 4. Se determinan, con total certeza, las posiciones admisibles de vi e vj por ventana de tiempo y máximo tiempo en ruta del vehículo y, de entre ellas, se elige la que redunda en un menor coste. Se computa el coste total de solución_Inser con estas inserciones, {vi,rq,-1,rp} y { -1,rq,vj,rp}, y se compara con mejor_insercion, actualizándola en caso de mejora y de no ser tabú (a no ser que cumpla el criterio de aspiración).

4. IMPLEMENTACIÓN

En el apartado anterior se introdujo la resolución del problema VRP y el desarrollo de la sistemática de la Búsqueda Tabú a través de diagramas de flujo y operaciones lógicas de alto nivel. En este nuevo punto, se pretende dar forma y concretar la estrategia desde un punto de vista de programación, incluyendo así la extensa implementación de todos los pasos, su agrupación en archivos, clases, bloques y funciones, la interacción entre ellos y la estructura de datos en general. En resumen, se presenta la traducción de algoritmos y mecánicas matemáticas a un entorno de programación en alto nivel, como es el lenguaje C++.

Todo el código que recoge la Búsqueda Tabú está escrito en C++Builder, un entorno de desarrollo de aplicaciones en C++ para Windows propiedad de la empresa Borland. C++Builder tiene un diseño sencillo y fácil de usar que permite desarrollar programas con interfaz gráfica de forma cómoda y rápidamente. Para este trabajo, en concreto, se usa la versión 5.0.

Figura 20. Ventana principal de C++Builder

Desde un punto de vista funcional, la aplicación desarrollada puede entenderse como una caja negra que realiza tres pasos secuencialmente:

1. Lee un fichero de entrada con todos los datos que definen el problema VRP bajo estudio (flota, clientes, distancias, tiempos, etc) más una serie de parámetros de entrada definidos por el usuario (función objetivo, tipos de algoritmo, tiempo de ejecución, etc).

2. Analiza los parámetros y ejecuta el algoritmo M&J, movimiento opt y Búsqueda Tabú según los datos de entrada.


66

3. Genera un fichero de salida que presenta la mejor solución al VRP bajo estudio, así como los hitos más importantes durante la ejecución.

Estos tres puntos se detallan a lo largo de esta sexta sección. El apartado 6.1. se orienta a detallar la funcionalidad del código al completo, mientras que en el apartado 6.2. se muestra la interfaz gráfica, los parámetros disponibles y el formato de los archivos de entrada y salida

4.1. Descripción de clases En este apartado se especifica la estructuración del código y la funcionalidad de los archivos que lo componen. Las funciones, variables y datos más relevantes se relacionan con los pasos más importantes en la resolución del problema VRP, de cara a una mejor compresión y modificación futura del código.

Como se ha mencionado anteriormente, el código al completo está escrito en C++, si bien es cierto que gran cantidad del código utiliza la sintaxis propia de C por razones de facilidad y rapidez en la implementación.

El programa completo se divide en nueve ficheros:

- PrincipalCONT.cpp. Contiene las referencias a los objetos gráficos (los que se muestran al usuario) de la aplicación. Además en él se traspasan los datos del problema VRP a una clase definida en heurCONT.cpp.

- Estructura_datos.cpp. Proporciona un compendio de clases que aglutinan todos los datos del problema VRP: clientes, flota y la estructura de arcos entre clientes. La clase más importante se denomina Parametros_problema, cuyos métodos son usados en PrincipalCONT.cpp para copiar los datos del problema VRP.

- Tiempos_cpu.cpp. Únicamente se usa dentro de heurCONT.cpp para controlar el tiempo de simulación total.

- Lectura_datos.cpp

- Interfaz_opt.cpp. Se usan métodos de impresión en archivo para representar. - Gen_modelo.cpp

- Gen_problemas.cpp

- Importar.cpp

- heurCONT.cpp. Almacena las clases Solución, Movimiento y ListaTabu. En él se recogen todas las instrucciones desde la copia de datos del problema VRP hasta el fichero de salida con los mejores resultados.

Los ficheros están orientados a desempeñar tres labores fundamentalmente (ya sea individualmente o en grupo): lectura de fichero de entrada más parámetros de usuario, ejecución de algoritmos y volcado de resultados en fichero de salida. En la figura 16, se muestran qué ficheros se asocian a estas labores.

Si ya en la sección 5 se presentaron los algoritmos desde una perspectiva lógica y secuencial mediante diagrama de flujos, ahora se pretende describir qué entidades son las responsables de acatar cada conjunto de instrucciones. Para ello, se usan tres clases distintas: Solución, Movimiento y ListaTabu.

Figura 21.

De estas tres clases, la más extensa y compleja es Movimiento se utiliza en la parte de la implementación dedicada a la BT y define qué tipo de movimiento se realiza y sobrecarga algunos operadores, y propias de este tipo de búsqueda, proporcionando métodos relativos a su movimientos tabú. En la figura 17 se presenta la relación entre fases de la aplicación, clases y ficheros.

Figura 22.

4.1.1. Clase Solución

Esta clase congrega casi la totalidad de las variables, constantes y métodos del problema. No en vano, casi toda la aplicación corre sobre ella, pues ofrece los métodos de M&J, del operador así como de la BT.

Las variables declaradas en Solución se resumen en la siguiente tabla:

Nombre Tipo

Numero_camiones Int

Numero_nodos Int

Numero_combustibles Int

Numero_contaminantes Int

Numero_categoria Int

Lambda Float

Captura de datos de entrada + parámetros

de usuario

•principalCONT.cpp

•estructura_datos.cpp

67

Ficheros implicados en las tres fases de la aplicación

De estas tres clases, la más extensa y compleja es Solución, que contiene el grueso del código. se utiliza en la parte de la implementación dedicada a la BT y define qué tipo de

movimiento se realiza y sobrecarga algunos operadores, y ListaTabu hace referencia a las listas propias de este tipo de búsqueda, proporcionando métodos relativos a su actualización y búsqueda de movimientos tabú. En la figura 17 se presenta la relación entre fases de la aplicación, clases y ficheros.

Relación entre ficheros, clases y fases de la aplicación

Esta clase congrega casi la totalidad de las variables, constantes y métodos del problema. No en vano, casi toda la aplicación corre sobre ella, pues ofrece los métodos de M&J, del operador

ción se resumen en la siguiente tabla:

Contenido

Número de vehículos de la flota

Número de clientes del problema

Número de combustibles disponibles para la flota

Número de contaminantes (normalmente 3)

Número de categorías de vehículos disponibles en la flota

Valor de lambda en la ecuación (XXX)

Ejecución de algoritmos (M&J, λ-opt,BT)

•heurCONT.cpp

•tiempos_cpu.cpp

Volcado en fichero de

4.Implementación

tres fases de la aplicación

, que contiene el grueso del código. se utiliza en la parte de la implementación dedicada a la BT y define qué tipo de

hace referencia a las listas actualización y búsqueda de

movimientos tabú. En la figura 17 se presenta la relación entre fases de la aplicación, clases y ficheros.

Relación entre ficheros, clases y fases de la aplicación

Esta clase congrega casi la totalidad de las variables, constantes y métodos del problema. No en vano, casi toda la aplicación corre sobre ella, pues ofrece los métodos de M&J, del operador λ-intermcabio,

Número de combustibles disponibles para la flota

Número de contaminantes (normalmente 3)

Número de categorías de vehículos disponibles en la flota

Valor de lambda en la ecuación (XXX)

Volcado en fichero de salida

•heurCONT.cpp


68

Un Float Valor de un en la ecuación (XXX)

Coste_ruido Float Coste del ruido ambiental generado por un vehículo

Coste_acc Float Coste de siniestralidad de un vehículo

Coste Float Coste total de la solución

Coste_mejor2opt Float Coste de la mejor ruta en un intercambio opt (2 y 3 opt)

Mejor_ruta2opt Int* Ruta con mejor coste tras todas las combinaciones opt. La posición inicial y final del vector no se ocupa con el depot, pues se sobreentiende que es tanto el origen como fin de la ruta. Por ejemplo: {2-5-7}

Ciudades Int* El índice del vector representa el número de la ciudad. De valor “1” si ha sido visitada, “0” si aún no lo ha sido.

Flota Int* El índice del vector representa la posición del camión en el fichero de entrada. Valor “1” si el vehículo aún no ha sido usado, y “0” si ya ha sido usado

Capacidad float* Almacena la capacidad de los vehículos de la flota. El índice del vector representa la posición del camión en el fichero de entrada.

Demanda float* Almacena la demanda de los nodos del grafo. El índice del vector representa el número de ciudad. El depot es la posición por defecto y demanda[0]=0

Max_t_cond float* Almacena el máximo tiempo del vehículo en ruta. El índice del vector representa la posición del camión en el fichero de entrada.

Tasa_cond float* Almacena el coste del conductor por unidad de tiempo en ruta (€/h). El índice del vector representa la posición del camión en el fichero de entrada.

Coste_fijo float* Almacena el coste fijo de un vehículo por ser usado (€). El índice del vector representa la posición del camión en el fichero de entrada.

Coste_mto float* Almacena el coste de mantenimiento de un vehículo por unidad de longitud (€/km). El índice del vector representa la posición del camión en el fichero de entrada.

Consumo_vac float* Almacena el consumo en vacío de un vehículo por unidad de longitud (l/100km). El índice del vector representa la posición del camión en el fichero de entrada.

Consumo_ton float* Almacena el consumo por tonelada y litro de un vehículo por unidad de longitud (l/100km ton). El índice del vector representa la posición del camión en el fichero de entrada.

Emisiones_CO2kgud float* Almacena la cantidad de CO2 emitida por unidad de fuel consumida (KgCO2/l). El índice del vector representa la

4.Implementación

69

posición del camión en el fichero de entrada.

Coste_gei float* Almacena el precio de cada unidad de CO2 emitida (€/tonCO2). El índice del vector representa la posición del camión en el fichero de entrada.

Coste_tipo_fuel Float * Almacena el precio de cada unidad de combustible (€/l). El índice del vector representa la posición del camión en el fichero de entrada.

Categoria_camion int* Almacena la categoría del vehículo. El índice del vector representa la posición del camión en el fichero de entrada.

Emisiones_cont Float** Almacena la emisión de contaminante de tipo i emitida por km por un vehículo de categoría j, siendo emisiones_cont[i][j].

Coste_cont Float* Almacena el precio por tonelada de contaminante emitido. El índice del vector representa el tipo de contaminante.

Vent_minima Float* Almacena los valores ek de las ciudades. El índice del vector representa el número de la ciudad (ek[0]=0).

Vent_maxima Float* Almacena los valores lk de las ciudades. El índice del vector representa el número de la ciudad (lk[0]=0).

Tiempo_servicio Float* Almacena los valores sk de las ciudades. El índice del vector representa el número de la ciudad (sk[0]=0).

Minimo Float* Vector de tamaño 2. Minimo[0] contiene la ciudad con mejor coste desde el depot y mínimo[1] contiene el coste de desplazarse hasta dicha ciudad.

Camión_elegido Int* Usado en otros algoritmos. No relevante para este trabajo.

Orden_camion Int* Almacena en el índice i-ésimo, la posición del vehículo en el fichero de entrada que por capacidad (de mayor a menor, o de menor a mayor) es el i-ésimo.

Orden_ciudad Int* Usado en otros algoritmos. No relevante para este trabajo.

Vec_ciudades Int* Almacena en la posición i una ciudad perteneciente a una solución (leáse Formato de solución)

Vec_camiones Int* Almacena en la posición i la cantidad de ciudades que visita que un camión perteneciente a una solución (leáse Formato de solución)

Vec_punteros Int* Almacena en la posición i la índice de comienzo de la ruta de un camión en vec_ciudades ((leáse Formato de solución).

Nodoselec Int* Similar a int* ciudades

Rutactual Int* Almacena en la posición i-ésima el posición de visita de la ruta que se está construyendo (M&J). El índice i

representa el número de la ciudad. Rutactual[0]=1


70

siempre, pues todos los camiones salen del depot.

Decisión Int* Almacena en la posición i, la mejor posición de la ciudad i en la ruta actual.

Distancias Float** Almacena la distancia desde la ciudad i a la j. distancias[i][j].

Tiempos Float** Almacena el tiempo empleado en ir desde la ciudad i a la j. tiempos[i][j].

Peajes Float** Almacena el coste del peaje desde la ciudad i a la j. peajes[i][j].

Matriz_costes Float** Matriz de dimensión [(numero_nodos+1),5] que contiene los cálculos de costes de M&J. Delante descrito

C11 Float** Almacena en el índice i-ésimo el coste

c1(vi,w)=cvi,w+cw,v+1-λcvi,vi+1 de la ciudad i al ser insertada

en la ruta actual.

C12 Float**

C1w Float**

C2w Float**

Iw Float** Almacena en la posición i el menor valor de C1[i][j] para todo j. iw[i][j] (el índice j es irrelevante)

Bjprov Float** Irrelevante.

Rutasbj Float** Almacena el instante de atención de la ciudad i al vehículo cuando se coloca en la posición j de la ruta actual. Rutasbj[i][j]

rutasTWadm bool** Almacena si la posición j de la ciudad i en la ruta actual es válida. rutasTWadm[i][j]

Bj Float* Almacena en la posición i-ésima el tiempo de atención de la ciudad i-ésima al vehículo

Veloc Float Almacena la velocidad media de la flota para recorrer las rutas. Se usa sólo si la función objetivo es tiempo.

Div_max_t_cond Float Almacena el valor por el que se dividen todos los máximos tiempos en ruta de los vehículos

Div_t_entre_nodos Float Almacena el valor por el que se dividen todos los tiempos entre ciudades.

Tabla 2. Variables de la clase Solución

De entre todas las variables descritas, cabe profundizar en la estructura de las que representan el núcleo principal del algoritmo M&J y/o se usan frecuentemente en la BT.

• Formato de la solución: Vec_ciudades, Vec_camiones, Vec_punteros Una solución queda definida perfectamente mediante la interpretación de estos tres vectores. Vec_ciudades contiene todas las ciudades del grafo ordenadas de izquierda a derecha por orden de

4.Implementación

71

visita. Vec_camiones indica el número de ciudades que atiende el camión i. Y la posición i de vec_punteros señala la posición en vec_ciudades donde se sitúa la ruta asignada al camión i.

Vec_ciudades 8 4 12 7 11 2 3 13 6 16 1 10 15 5 14 9

Vec_camiones 3 3 6 4

Vec_punteros 4 13 7 0

Tabla 3. Ejemplo de Solución con cuatro rutas asignadas por colores

Los pasos que deben seguirse para interpretar correctamente el formato de la solución son los siguientes:

1. Se identifica el índice i de vec_punteros como el camión i en el fichero de entrada de datos.

2. El valor de vec_punteros[i] indica el índice de comienzo en vec_ciudades.

3. El valor de vec_camiones[i] indica el número de ciudades atendidas

Por tanto, si se observa la tabla 3, se puede afirmar que el camión 3 (recuérdese que los índices de los vectores empiezan con valor cero) atiende 4 ciudades (ruta azul). En concreto sigue el orden {0-8-4-12-7-0}. La omisión del valor 0 (depot) en vec_ciudades deriva de la consideración de que esta ciudad siempre se encuentra al inicio y final de cualquier ruta.

• Matriz_costes Dentro del algoritmo M&J este es el bloque que aporta toda la información relativa a los costes entre los nodos ya establecidos dentro de una ruta y los candidatos. Posee, conceptualmente, cinco columnas, y en cada una de ellas se realizan cálculos de costes internos y externos entre un par de nodos fijos (vi, vi+1) más una tercera ciudad candidata a insertarse (w), como puede verse en la figura 18. Las filas que se rellenan son aquellas que pertenecen a las ciudades aún no visitadas.

Cada columna almacena uno de estos costes:

1. ci,w. Coste entre la ciudad vi y w. 2. cw,i+1. Coste entre la ciudad w y vi+1. 3. ci,i+1 . Coste entre la ciudad vi y vi+1. 4. bw,i+1. Coste desde el inicio de la ruta hasta la ciudad vi+1 considerando la inserción de w. 5. bi+1. Coste desde el inicio de la ruta hasta la ciudad vi+1.


72

Figura 23. Costes considerados en la inserción de una nueva ciudad entre un par de nodos

• Rutactual Es un vector de suma importancia pues contiene las ciudades que se van añadiendo progresivamente a una ruta en concreto. A pesar de que la forma de guardarla no es muy intuitiva, resulta muy eficaz en términos de programación. Para un problema con 6 nodos (más el depot), en el que la ruta que se le está asignando a un vehículo es {0-2-4-1-0}, rutactual toma los siguientes valores:

Índice Valor

0 1

1 4

2 2

3 0

4 3

5 0

6 0

Tabla 4. Contenido de rutactual para una ruta {0-2-4-1-0}

Métodos de Solución

La clase solución atesora la mayor cantidad de funciones de todo el código. En ella se ejecutan todas las instrucciones para realizar las tareas más complejas de la aplicación.

Este apartado no pretende hacer una descripción de todas de ellas, pero sí asociar los métodos más significativos que se relacionan de una manera directa con pasos claves en las tres grandes tareas de la aplicación: desarrollo de M&J, movimientos opt y Búsqueda Tabú. De hecho, dentro del código, pueden hallarse las funciones divididas con ese mismo criterio.

Funciones M&J

vi

vi+1

w

ci,w cw,i+1

ci,i+1

bi+1

bw,i+1

4.Implementación

73

En el apartado 5 se presentó el diagrama de flujo que recogía los pasos esenciales del algoritmo M&J. Dentro de la clase solución existen métodos específicamente diseñados para cumplir con las tareas de cada bloque. Sin embargo, el primer paso que se desarrolla aquí y que no aparece en el diagrama surge como consecuencia de que la aplicación debe dirimir en primera instancia qué función objetivo se persigue (existe la posibilidad de “tiempo” o “contaminación”) y con qué algoritmo se desea buscar la solución inicial (propio o con orden de la capacidad de los camiones). Los métodos, según su tarea, pueden clasificarse en varios grupos:

Elección de función objetivo y algoritmo.

1. AlgoritmoMoleJamesonTWCapacidad.

2. AlgoritmoMoleJamesonTWCapacidadCONT

Ambos métodos realizan la heurística de M&J, salvo que en el primer caso se intenta minimizar la distancia y en el segundo la suma de costes internos y externos de la función. Por ello, la descripción de su operativa se puede ver sobre un mismo pseudocódigo:

Figura 24. Pseudocódigo de algoritmo M&J

Ordenar la flota

1. OrdenarFlota. Realiza la clasificación de los camiones según capacidad, ya sea de mayor a menor o viceversa.

Ordenar la flota Mientras queden camiones y haya ciudades por visitar Mientras no haya ciudad admisible y queden camiones Busca ciudad y camión con menor coste Si todos camiones usados y no hay ciudad por visitar Fin algoritmo Elige camión y ciudad Actualiza carga Si quedan ciudades por visitar Si existe camión que satisfaga demanda Mientras camión satisfaga demanda o rutas sean admisibles (while end2) Para cada arco de la ruta Para toda ciudad no visitada Forma Matriz Costes Chequea admisibilidad de ciudades insertadas en arco de la ruta Elige mejor ciudad y posición en ruta Si existe tal ciudad Si nueva carga es admisible Actualiza carga y ruta Si no Fin de ruta Mejora con mov OPT Actualiza Coste solución Si no Fin de ruta Mejora con mov OPT Actualiza Coste solución Si no Fin algoritmo Si no Fin de ruta Mejora con mov OPT Actualiza Coste solución Fin algoritmo


74

Elegir camión admisible y ciudad con menor coste

1. BuscaMinimo. Elige la primera ciudad a visitar cuando se inicia una nueva ruta. Ofrece seis variantes, divididas en dos grupos de tres según la función objetivo que se desee. Para contaminación se puede hallar la ciudad con mayor o menor coste o a mayor distancia. Y para tiempo, se puede elegir la ciudad más cercana o lejana o aquella con un límite superior de ventana de tiempo más restrictiva (menor).

2. TodosCamionesUsados. Chequea si toda la flota ha sido utilizada.

3. CiudadVisitada. Comprueba si queda alguna ciudad por atender.

Calcular todos costes tras insertar w en todas posiciones

1. CosteFxij. Halla los costes internos o fijos desde un par de nodos cualesquiera de rutactual. Puede indicarse que entre ese par de nodos quiere insertarse una nueva ciudad o no.

2. CosteCO2ij. Computa los costes por contaminación desde un par de nodos cualesquiera de rutactual. Puede indicarse que entre ese par de nodos quiere insertarse una nueva ciudad o no.

3. CosteFxHastaCiudad. Calcula los costes fijos desde el depot hasta una ciudad de rutactual. Puede indicarse que realice el cálculo insertando previamente una ciudad en algún punto de rutactual.

4. CosteCO2HastaCiudad. Calcula los costes por contaminación desde el depot hasta una ciudad de rutactual. Puede indicarse que realice el cálculo insertando previamente una ciudad en algún punto de rutactual.

Comprobar admisibilidad de w en todas posiciones

1. RutasAdmisiblesCO2. Comprueba si la inserción de un nodo en una posición determinada dentro de rutactual es posible desde el punto de vista de ventanas de tiempo y máximo tiempo en ruta

Elegir ciudad y posición con menor coste

1. Forma_iwTW.

2. Forma_C2wTWCO2.

ActualizaRuta

1. ActualizaRutactual. Inserta una ciudad en una posición indicada por el vector decision en rutactual

2. Forma_bjCO2. Actualiza los momentos de llegada a cada ciudad del vector rutactual

3. Inicializa_rutasTWadm. Inicializa la matriz que comprueba la admisibilidad de las rutas

4.Implementación

75

4. ReseteaRutactual. Hace un reset de rutactual

5. Resetea_bj. Pone los tiempos de instante de llegada a las ciudades a cero

6. GeneraSolucionRutaCO2.

FuncionesOPT

Son métodos que operan con una ruta proporcionada por M&J y realizan todas las posibles eliminaciones de arcos (en grupos de 2 ó 3) y sus correspondientes reconexiones. La ruta se transfiere en forma de vector a las funciones y los movimientos opt se realizan concatenando secuencias de traslación e inversión de grupos de ciudades delimitados por pivotes.

Estos tres nuevos conceptos son fácilmente identificables mediante un ejemplo de intercambio 3-opt (incluye implícitamente los 2-opt) sobre una ruta aleatoria. Sea pues una ruta r = {2-7-5-3-6-1-4} con la eliminación de arcos que se muestra en la figura 19.

Figura 25. Ruta aleatoria con eliminación de arcos para movimiento 3-opt

Un pivote se define como la ciudad en un arco inconexo que se encuentra más alejada del depot recorriendo la ruta en sentido horario. Para esta r, los pivotes son {5,6,4}. Vectorialmente, los pivotes dividen la ruta en 4 zonas de distintas. Dos de ellas, las más cercanas al depot, tanto por el punto de salida como por el de regreso, permanecen inalterables durante las reconexiones mientras que las dos centrales son las que sufren las traslaciones e inversiones.

2 7 5 3 6 1 4

(p) (p) (p)

Figura 26. Ruta en forma de vector para la manipulación de los métodos opt

Los métodos de reconexión de arcos prueban primero realizan las inversiones posibles para cada grupo de ciudades entre dos pivotes (grupo azul y amarillo). Tras lo cual, efectúan una traslación entre los dos grupos a lo que sigue de nuevo la última inversión. Estas operaciones se resumen en la siguiente figura:


76

2 7 5 3 6 1 4

Inversiones

2 7 5 3 1 6 4

2 7 3 5 6 1 4

2 7 3 5 1 6 4

Traslación

2 7 1 6 5 3 4

Inversiones

2 7 1 6 3 5 4

2 7 6 1 5 3 4

2 7 6 1 3 5 4

Tabla 5. Evolución de reconexiones en una ruta en métodos opt

Según su funcionalidad, los métodos disponibles para llevar a cabo el algoritmo λ-intercambio son:

Efectuar traslaciones e inversiones

1. InvertirRuta. Efectúa inversiones 2-opt, comprueba la admisibilidad por ventanas de tiempo y máximo tiempo de la ruta tanto en un sentido de viaje como el contrario, y calcula el coste total (en tiempo) de la ruta.

2. InvertirRutaCO2 . Como la anterior, pero los cálculos de costes los realiza no por tiempo sino por contaminación.

3. InvertirRuta3CO2. Ordena todos los movimientos 3-opt calculando los costes internos y externos.

4. InvertirRuta2mod. Tiene la misma funcionalidad que InvertirRuta con campos adicionales para impresión de rutas en fichero de salida.

5. InvertirRuta2modCO2. Igual que InvertirRuta2mod pero calculando los costes internos y externos

6. Shift. Realiza las traslaciones y calcula el coste de la ruta en unidades temporales

7. ShiftCO2. Realiza las traslaciones y calcula el coste como la suma de costes internos y externos

Comprobar admisibilidad de la ruta tanto en sentido horario como antihorario

4.Implementación

77

1. AdmisibilidadTW. Dada una ruta, halla la admisibilidad por tiempo de la misma y calcula su coste en horas.

2. AdmisibilidadTWinv. Dada una ruta, halla la admisibilidad por tiempo de la misma en sentido contrario y calcula su coste en horas.

3. AdmisibilidadTWCO2. Dada una ruta, halla la admisibilidad por tiempo de la misma y calcula su coste como la suma de los costes internos y externos.

4. AdmisibilidadTWinvCO2. Dada una ruta, halla la admisibilidad por tiempo de la misma en sentido contrario y calcula su coste como la suma de los costes internos y externos.

Funciones BT

La finalidad de todos los métodos relativos a la BT es realizar a partir de una solución inicial descrita en las variables vec_camiones, vec_ciudades y vec_punteros, junto con los parámetros introducidos por el usuario (tiempo de simulación, tamaño de listas tabú, admisibilidad de soluciones no permitidas y número de iteraciones sin mejora) todas las instrucciones contenidas en el diagrama de flujo visto en la figura 14.

Según la función objetivo, la Búsqueda Tabú parte del método BúsquedaTabu o BusquedaTabuCONT. La primera asume que se debe minimizar el tiempo total recorrido por la flota, mientras que la segunda persigue la minimización de costes tanto internos como externos.

El núcleo principal de la BT, ya se elija una función objetivo y otra, gira fundamentalmente en torno a un par de funciones, Admisible_Carga, que dirime si dado un par de rutas y ciudades el movimiento es válido según la carga (las condiciones temporales se siguen satisfaciend), e Inter_swapping, que se encarga de distinguir si un movimiento es inserción o intercambio y devuelve el mejor de los resultados según se le pase uno u otro. El código restante está diseñado para ir actualizando los mejores movimientos, listas tabú, soluciones y pasar de intensificación a diversificación según los resultados que proporcionen las dos funciones anteriores.

Atendiendo a su funcionalidad, los métodos se pueden clasificar en:

Elección de rutas y ciudades

1. Set_solucion_inicial. Se copia la solución de partida M&J en otra estructura de datos.

2. Genera_rutas_tabu. Devuelve un par de rutas descritas por unos valores introducidos en la llamda a la función.

3. PosicionRuta. Devuelve la posición exacta de comienzo de la ruta que se encuentra en la solución en el momento de la llamada.

4. ResetLocalizador. Resetea los valores que definen la posición de cada ruta.


78

Decidir admisibilidad de movimiento

1. Admisible_Carga. Indica si, al producirse el movimiento propuesto, la solución se vuelve admisible o inadmisible

2. Limite_por_ventana. Acota el conjunto de posiciones de una ciudad extraída a una ruta de recepción

3. AdmisibilidadTW_ruta. Decide si la ruta que se le pasa es admisible tanto por ventanas de tiempo como tiempo máximo en ruta.

4. RutadoAdmisibleInsercion. Esta función es la encargada de decidir si un movimiento de tipo inserción provoca que la solución sea en su conjunto admisible o no. Es siempre llamada desde Admisible_Carga.

5. RutadoAdmisibleIntercambio. Esta función es la encargada de decidir si un movimiento de tipo intercambio provoca que la solución sea en su conjunto admisible o no. Es siempre llamada desde Admisible_Carga.

Decidir mejor movimiento

1. Inter_swappingCONT.

2. Inter_swapping.

Ambas funciones son parte importante de la BT pues, definidas las cuatro entidades que intervienen en un movimiento ({vi,rq,vj,rp}), indica la mejor localización de las ciudades en sus rutas destino, ya se trate de un intercambio o inserción y ya sea este admisible o no admisible. La primera calcula los costes como la suma de los internos más los externos y la segunda hace lo propio con el tiempo total recorrido. Como el proceso no se desarrolla de forma trivial, a continuación se presenta el pseudocódigo que lo hace posible.

4.Implementación

79

Figura 27. Pseudocódigo de método Inter_Swapping e Inter_SwappingCONT

Actualizar soluciones

1. EligeMejorSolucion. Dirime el mejor coste existente entre los siguientes tres movimiento: mejor intercambio, mejor inserción de vi y mejor inserción de vj

2. ActualizaEnrutado. Actualiza la solución elegida con el movimiento que se le pasa.

3. CosteRutadoCONT. Calcula el coste total de la solución que se desee. El coste entendido como la suma de los costes internos y externos.

4. CosteRutado. Calcula el coste total de la solución que se desee. El coste entendido como la suma de los costes internos y externos.

5. GuardaRutado. Guarda una solución en los tres vectores que se indican.

6. Imprime_Solucion_Tabu. Vuelca en el fichero de salida el resumen de los hitos más importantes ocurridos durante la ejecución de la BT.

7. CosteTrasInsercion. Calcula el coste total (en horas) del rutado, de aplicarse la inserción indicada en la solución

8. CosteTrasInsercionCONT. Calcula el coste total (suma de externos más internos) del rutado, de aplicarse la inserción indicada en la solución

Forma rutas rq y rp Guarda coste de rq y rp Acota posiciones del movimiento de vi y vj Si (es intercambio) y [(llamada desde admisible y admisible) o (llamada desde no admisible y no admisible)] Si hay posiciones en ruta destino Para cada posición en ruta destino Forma ruta con nueva ciudad Calcula coste ruta nueva Si ruta admisible por tiempo Guarda intercambio Actualiza mejor intercambio Si (es inserción) Forma rutas rq y rp Guarda coste de rq y rp Acota posiciones de la inserción en ri y rq Si hay posiciones en ruta destino Para cada posición en ruta destino Forma ruta con nueva ciudad Calcula coste ruta nueva Si ruta admisible por tiempo Guarda intercambio Actualiza mejor intercambio Si existe intercambio Calcular coste con mejor intercambio Si existe inserción y inserción habilitada Calcular coste con mejor inserción Elige mejor inserción o intercambio Libera variables


80

4.1.2. Clase Movimiento

Es una clase de extensión reducida que proporciona un formato específico para definir tanto a los intercambios como inserciones que se producen durante la BT. Da información acerca de las rutas involucradas, las ciudades, sus posiciones y los costes parciales y totales del rutado.

Las variables declaradas en Movimiento se resumen en la siguiente tabla:

Nombre Tipo Contenido

V_i Int Ciudad vi del movimiento

R_i Int Ruta de la que se extrae vi

V_j Int Ciudad vj del movimiento

R_j Int Ruta de la que se extrae vj

Pos_virj Int Posición que ocupa vi en la ruta r j

Pos_vjri Int Posición que ocupa vj en la ruta r i

C_i Float Coste de r i después del movimiento

C_j Float Coste de la r j después del movimiento

C_preinsercion Float Irrelevante

C_postinsercion Float Coste de la solución de efectuarse el movimiento Tabla 6. Variables de la clase Movimiento

Los métodos pertenecientes a esta clase son:

1. Existe. Indica si el movimiento que se chequea contiene algún movimiento.

2. EsInsercion. Se toma por defecto que los movimientos son intercambios. Este método dictamina si un movimiento es de tipo inserción.

3. Sobrecarga de operador “=”. Asigna todas las variables descritas en la tabla XXX

4. Sobrecarga de operador “==”. Esta función es la que se usa para establecer bajo qué condiciones se considera un movimiento tabú.

4.1.3. Clase ListaTabu

Esta clase está diseñada para gestionar los datos contenidos dentro de una lista tabú que a su vez se compone múltiples objetos pertenecientes a la clase Movimiento.

A continuación se muestran en una tabla las variables que componen la clase ListaTabu.

Nombre Tipo Contenido

Índice Int Almacena la posición del próximo movimiento a insertar

Lista_mov Movimiento* Almacena los movimientos efectuados en una lista tabú

N_elementos Int Almacena la longitud máxima de la lista tabú

Primera_vuelta Bool “True” si aún no se ha sobreescrito un movimiento. “False” de lo contrario

4.Implementación

81

Sin_movimientos Bool “True” si la lista está vacía. “False” de lo contrario Tabla 7. Variables de la clase ListaTabu

Los métodos descritos en ListaTabu son muy limitados, aunque permiten realizar las operaciones propias de una lista: inicialización, actualización de movimientos y comprobación de la existencia de algún movimiento tabú entre los miembros de una lista. Sus nombres hacen referencia al funcionamiento de cada uno de ellos:

1. Actualiza_nElementos. Fija el tamaño de la lista tabú

2. Inicializa. Actualiza las variables y reserva memoria para todos los objetos Movimiento.

3. ActualizaLista. Introduce el movimiento en la lista

4. EsMovimientoTabu. Comprueba en todas las posiciones de la lista si existe algún movimiento tabú.

4.2. Interfaz de usuario La aplicación se desarrolla bajo un lenguaje de programación con un entorno visual que permite que el usuario se desenvuelva fácilmente con su interfaz y, de este modo, interactuar de forma sencilla con las opciones disponibles para ejecutar una Búsqueda Tabú personalizada.

En esencia, el programa busca en el explorador de archivos los ficheros de entrada con una extensión determinada (.vrp). Dichos ficheros contienen un formato exclusivo en el que se aporta la toda la información relativa a la flota, combustibles, clientes, depot y el grafo sobre el que discurrirán las rutas. Tras la ejecución de estos ficheros, la aplicación genera un único archivo (.txt) que sintetiza los resultados e indica los hitos más importantes ocurridos durante la ejecución de los algoritmos. Este archivo, además, posee un formato de salida propio bastante intuitivo.

En la sección 4.2.1., se pretende familiarizar al lector con la interfaz gráfica de la aplicación, describiendo los elementos que aparecen sobre la pantalla. Mientras que en la 4.2.2., se detallan los formatos de los ficheros de entrada y de salida.

4.2.1. Aplicación en pantalla

La aplicación consta de una única pantalla dividida en cuatro regiones como muestra la figura 29:


82

Figura 28. Ventana principal de la aplicación

En la parte superior se encuentra el explorador de archivos al que se le indica donde se encuentran los ficheros de entrada. Para que la aplicación los reconozca, Estos ficheros deben guardarse con una extensión .vrp. La aplicación ejecutará todos los archivos .vrp que contenga el directorio por el orden en el que se listan en la caja.

En la parte izquierda, se encuentran los parámetros relativos al algoritmo Mole&Jameson:

- Función Objetivo. Los valores que puede tomar son Tiempo o Contaminación. - Algoritmo. Presenta dos posibilidades usando siempre la heurística de M&J: ordenar las

capacidades de las flotas de mayor a menor o de menor a mayor. - Criterio primera ciudad. Contiene los tres tipos de criterios para las dos funciones objetivos, lo

que suma un total de seis posibilidades. Para contaminación ofrece la posibilidad de encontrar la ciudad más lejana y la de mayor o menor coste. Y para tiempo, puede elegirse entre la más lejana o cercana o aquella que posee un límite superior de ventana de tiempo más restrictivo.

- Movimiento opt. Este campo se destina a definir la cantidad de arcos que queremos reconectar por cada ruta formada por M&J. Con valor 0, no se realizaría ningún proceso extra a M&J pero si se elige 2 o 3, el movimiento opt se lleva a cabo.

- Lambda. El valor introducido se computará en la ecuación XXX - Nu. El valor introducido se computará en la ecuación XXX. - Veloc media. Significa velocidad media de la flota. En el caso de que se elija como función

obejtivo Contaminación el valor de este campo es irrelevante y no se tiene en cuenta. Sin

4.Implementación

83

embargo, cuando se elige tiempo y se introduce el valor uno en este campo, la aplicación tomará los tiempos entre arcos directamente del fichero de entrada, mientras que si se introduce un valor distinto de 1, se tomarán las distancias entre arcos y se dividirá cada uno de ellos por la velocidad media introducía. Es decir, se estará asumiendo una velocidad media para todo el conjunto de la flota.

En la columna intermedia, se introducen los valores y criterios relativos a la BT:

- Lista Tamaño Inter. Número de movimientos tabú para la lista de intercambio (tanto admisible como no admisible).

- Lista Tamaño Inter. Número de movimientos tabú para la lista de inserción. - Inserción en iteración. Indica el número de iteraciones sin mejorar la mejor solución admisible

que el algoritmo debe esperar antes de hacer una inserción. - Permitir no admisibilidad. Hace referencia a si deben incluirse los intercambios no admisibles

en la BT (valor sí) o no (valor no). - Tiempo de ejecución. Se refiere al tiempo máximo de ejecución para cada archivo

seleccionado. Por último en la parte derecha, existen dos pequeños campos destinados a definir el valor de un par de parámetros que afectan a la adquisición de datos de entrada. En algunos casos, se ha detectado que el formato de los fichero de entrada contempla unos valores de máximo tiempo en ruta y tiempo entre rutas que no se corresponden mínimamente a los casos prácticos, siendo muy elevados. De ahí, que sea necesario dividir estos tiempos para dotar al problema de realismo:

- Divisor de max tiempo en ruta. Valor que divide el tiempo máximo que un conductor puede estar en ruta y la tasa que se le paga por hora de servicio.

- Divisor de tiempos entre ciudades. Valor que divide el tiempo entre un par de nodos, las ventanas máximas y mínimas de los nodos y sus tiempos de servicio. Se da esta opción por posibles desproporcionalidades en el fichero de entrada.

4.2.2. Ficheros de entrada y salida

Desde un punto de vista de diagrama de bloques, la aplicación se comporta como una caja negra que captura los ficheros de entrada dentro de un mismo directorio más una serie de datos proporcionados por el usuario y genera un fichero de salida con los sucesos más relevantes acaecidos durante la resolución del VRP así como el mejor conjunto de rutas encontradas. Esta relación queda gráficamente constatada en la figura siguiente:


84

Figura 29. Relación entre ficheros de entrada/salida, parámetros de usuario y aplicación

Los parámetros de usuario son proporcionados a través de la interfaz de usuario en el momento de ejecutar la aplicación, sin embargo los ficheros de entrada se encuentran previamente alojados en el equipo. Tanto este fichero como el de salida poseen un formato propio que recoge toda la información necesaria.

En el caso del fichero de entrada, se enumeran todos los datos necesarios para definir el problema VRP completamente: los combustibles (precios, emisiones, tipos, etc), la tipología de la flota (categoría, capacidad máxima, tiempo máximo en ruta, coste mantenimiento, etc), los clientes (ventanas de tiempo y demanda), contaminantes (emisiones según categoría del vehículo, costes, etc) y el grafo (distancias entre clientes, peajes, etc).

En el fichero de salida, bajo el nombre de SolucionRuteo.txt, se recogen todas las soluciones de la batería de ficheros de entrada. Para cada uno de estos últimos, se representa la solución inicial de M&J con las rutas modificadas por el operador λ-intercambio, y la evolución de los costes tras los intercambios e inserciones llevadas a cabo por la BT. Al final de la misma, se hace un pequeño resumen de la búsqueda y se presenta la mejor solución encontrada.

• Formato de fichero de entrada. El fichero de entrada es un documento en texto plano bajo la extensión .vrp. La información se organiza en grupos temáticos línea a línea, indicando con la primera de ellas el número de elementos de ese grupo. Dichos grupos siempre se organizan de la misma forma, por lo que se conoce de antemano la información que se está recopilando en cada línea. Si esta empieza por el símbolo “/” quiere decir que está comentada y, por tanto, se obvia.

La información dentro de un fichero .vrp se clasifica como indica la figura siguiente:

APLICACIÓN

Fichero de

salida (.txt)

Parámetros de

usuario

Fichero de

entrada (.vrp)

4.Implementación

85

Figura 30. Organización de la información en el fichero de entrada

Con estos datos se conforma perfectamente la definición de un problema HF-VRPTW con costes externos por contaminación. Para ver cómo se organizan esos grupos línea a línea se examina a continuación un archivo vrp cualquiera.

Categorías de los vehículos.

Esta parte define la tipología de los vehículos disponibles en la flota.

Figura 31. Categorías de los vehículos en el fichero de entrada

En este caso, se observa que en la flota sólo existe un tipo de camión. Es rígido y su peso oscila de 12 a 14 toneladas. Las emisiones de cada tipo de contaminante del vehículo se encuentran en la norma Euro II.

Combustibles

Se especifica el número de combustibles usados, coste y emisiones de CO2.

Figura 32. Combustibles en el fichero de entrada

Contaminantes

Gases efecto invernadero

Grafo

Características de los clientes

Características de los vehículos

Combustibles

Categoría de los vehículos

///Numero de Combustibles 1 ///Para cada combustible ///Nombre Unidad Coste(€/unidad) Emisiones_CO2(kg/unidad) ///DIESEL Litros 1 1 0.9009 2.6700

///Numero de Categorias 1 ///Para cada categoria ///Nombre ///Rigid_12-14_t_HD_Euro_II


86

En este caso toda la flota utiliza diesel, con un coste de 0.9009 € y un tasa de emisión de 2.67 kgCO2/l

Características de los vehículos

Contiene por línea la toda la información de cada vehículo de la flota.

Figura 33. Características de los vehículos en fichero de entrada.

En este caso, solo se ha ofrecido la información de los dos primeros vehículos, pero habría un total de 75 líneas como índica número de vehículos. En cada línea, los números se corresponden sucesivamente con: capacidad, máximo tiempo de conducción, tasa del conductor, coste fijo, coste de mantenimiento, consumo vacío, consumo por tonelada de carga, tipo de fuel usado (se corresponde con el campo nombre menos uno especificado en combustibles) y categoría

Características de los clientes

Proporciona los siguientes datos

Figura 34. Características de los clientes en fichero de entrada

La primera línea no comentada almacena los valores de demanda, ek y lk respectivamente. Después se ofrece la posibilidad de añadir un tiempo de servicio para cada vehículo, aunque el diseño sólo acepta uno para cada cliente, independientemente del vehículo que la atienda.

Grafo

Esta parte del archivo suele ser la más extensa ya que aporta la información arco a arco de todo el grafo. Los datos se despliegan en cinco columnas distintas que hacen referencia al nodo de partida, nodo de llegada, distancia, tiempo y peaje entre ellos.

///Numero de arcos 10100 ///Para cada arco ///Origen Destino Distancia (km) Tiempo(h) Peaje(Euros) 0 1 27.7308 27.7308 0.0000 0 2 20.6155 20.6155 0.0000 0 3 29.0689 29.0689 0.0000 0 4 25.6125 25.6125 0.0000

///Para cada nodo ///1 Demanda(ton) Ventana_min(h) Ventana_max(h) 26.0000 0.0000 9999999.0000 ///Tiempo de servicio_veh1 (h)...Tiempo de servicio_vehn (h) 90.0000 90.0000 90.0000

///Numero de vehiculos 75 ///Para cada vehiculo ///Capacidad(ton) Maximo_tiempo_conduccion(h) Tasa_conductor(€/h) Coste_fijo(€) Coste_mto(€/km) Consumo_vacio(l/100km) Consumo_ton(l/ton.100km) Tipo_fuel Categoria 140.0000 28.0000 19.8900 42.6500 0.0590 1.0500 17.5000 0 0 140.0000 28.0000 19.8900 42.6500 0.0590 1.0500 17.5000 0 0

4.Implementación

87

Figura 35. Grafo en el fichero de entrada

Gases efecto invernadero

Se indican tanto el número de distintos gases de efecto invernadero así como su coste por tonelada y emisión por kilogramo de combustible quemado

Figura 36. GEI en el fichero de entrada

Contaminantes

La última sección del fichero de entrada indica los costes por tonelada de cada gas contaminante y la relación entre este y las distintas categorías de los camiones usados.

Figura 37. Contaminantes en el fichero de entrada

• Formato fichero de salida El fichero de salida es un archivo en texto plano bajo la extensión .txt que recoge la información más relevante producida en las distintas fases de resolución del problema VRP: creación de la solución

inicial, mejora con λ-intercambio y la Búsqueda Tabú. Se crea dentro del mismo directorio donde se seleccionaron los ficheros de entrada y su nombre es SoluciónRuteo.txt. Si dentro de dicho directorio

///Numero de Contaminantes 3 ///Para contaminante ///Nox ///Coste(€/ton) 3439.8000 ///Emisiones por categoria (gr/km) 5.5000 2.6500 3.8300 529.2000 ///NMVOC ///Coste(€/ton) 0.2070 ///Emisiones por categoria (gr/km) 0.0080 0.0100 76337.1016 0.1040 ///PM ///Coste(€/ton) 0.0161 ///Emisiones por categoria (gr/km) 0.0239 0.0239 0.0239 0.0239 ///Coste_Ruido(€/1000ton-km) Coste_Accidentes(€/1000ton-km) 6.4827 6.3504

///Numero de GEI 1 ///Para cada GEI ///CO2 ///Coste(€/ton) 25.0000 ///Emisiones por tipo combustible (kg/unidad) 2.6700


88

se hallara más de un fichero .vrp, entonces no se crea un fichero de salida por fichero de entrada, sino que sus respectivas resoluciones se separan dentro del mismo archivo SolucionRuteo.txt.

La información que contiene el fichero de salida se divide, en primera instancia, mediante el siguiente esquema:

Figura 38. Organización de la información en el fichero de salida

Cada solución de archivo, a su vez, almacena los siguientes datos:

Figura 39. Organización de la información para cada archivo de entrada en el fichero de salida

Dentro estos cinco grupos, existe una notación y disposición específica de los datos. A continuación se presenta esta estructura de datos junto con ejemplos de archivos reales.

Cabecera resumen de datos de entrada.

Las primeras líneas del archivo de entrada muestran el tipo de algoritmo elegido para la solución inicial, el movimiento opt y la función objetivo que se pretende minimizar bajo el siguiente formato:

Figura 40. Cabecera resumen de datos de entrada en el fichero de salida

El campo algoritmo_de_entrada indica qué tipo de algoritmo encuentra la solución inicial y cómo

ordena la flota. El número de arcos reconectados durante la aplicación del operador λ-intercambio viene determinado por valor_de_lambda. Y función objetivo muestra si se desea minimizar los costes por contaminación o bien por tiempo total recorrido por la flota.

Solución inicial M&J y λ-intercambio

Cabecera resumen de

datos de entrada

Solución inicial M&J

y λ-intercambio

Evolución de costes e iteraciones

en BT

Resumen de hitos en

BT

Mejor solución

[algoritmo_de_entrada] Movimiento: [valor_de_lambda] FO: [función_objetivo]

4.Implementación

89

Esta parte de SolucionRuteo contiene el rutado propuesto por el algoritmo elegido para determinar la solución de partida. El formato en que se presenta es el que sigue:

Figura 41. Solución inicial M&J y λλλλ-intercambio en el fichero de salida

En primer lugar, siempre se hace referencia al fichero de entrada, ya que es posible que en el directorio se halle más de un problema VRP que desee resolverse. Las palabras Cam, Cap y Ruta, significan respectivamente, camión, capacidad y ruta.

Cada línea después de este apartado contiene la asignación de ciudades a cada vehículo:

- numero_n. Este número señala el camión del fichero de entrada al que se le está asignando la ruta. Es decir, si valiera 5, esto quiero decir que el quinto camión mostrado en el fichero de entrada es el que se está usando.

- capacidad_n. Es la capacidad del vehículo de numero_n. - ruta_n. De izquierda a derecha, indica las ciudades que debe recorrer el vehículo

- ruta_mejorada_n. En caso de que se eligiera un valor para el operador λ-intercambio mayor que cero y que, tras la revisión de la ruta con este, se encontrara una solución, entonces aquí se mostraría la ruta que tiene el menor coste. Además entre paréntesis se indicaría el ahorro en coste respecto a la ruta propuesta por M&J.

- coste_acumulado. Este valor contiene el coste de las rutas predecesoras más la ruta que se analiza en la línea donde se imprime. Da idea de qué rutas inciden en un mayor coste.

Evolución de costes e iteraciones en BT.

Suele ser el apartado más extenso del archivo de salida, ya que es proporcional al número de iteraciones que realizan. Por cada iteración se produce una línea tipo, que queda identificada de la siguiente forma:

Figura 42. Evolución de costes e iteraciones en BT en el fichero de salida

Estas etiquetas proporcionan la siguiente información:

- inserción. Se imprime {INS} si el movimiento que se muestra inmediatamente después es una inserción. Si se trata de un intercambio, este campo queda en blanco.

- n_iteraciones. Muestra el total de las iteraciones que ha realizado la BT, computando la suma de inserciones e intercambios totales.

[inserción] Iteración: [n_iteraciones](/t)[banderas][tipo_mejor_movimiento][coste][aspiracion] [mejor_movimiento]

-------------------------- [nombre_fichero_de_entrada] -------------------------- Cam Cap Ruta [numero_1] [capacidad_1] [ruta_1] [ruta_mejorada_1][coste_acumulado] [numero_2] [capacidad_2] [ruta_2] [ruta_mejorada_2] [coste_acumulado] … [numero_n] [capacidad_n] [ruta_n] [ruta_mejorada_n] [coste_acumulado] Coste: [coste_total]


90

- banderas. Si mediante el movimiento que sigue, se ha mejorado el coste de la mejor solución hasta el momento (ya sea a través del paso por soluciones admisibles o no), se imprime “(<-)”.

- tipo_mejor_movimiento. Si el mejor_movimiento es no admisible se imprime “(NA)”. En caso de ser admisible, no se imprime nada.

- coste. Muestra el coste total de la solución tras actualizar el rutado con mejor_movimiento. - aspiración. Si mejor_movimiento se ha elegido mediante el criterio de aspiración, entonces se

imprime “(ASP)” - mejor_movimiento. Muestra el mejor movimiento hallada durante la iteración y el formato en

que se imprime es el mismo que el definido en este documento {vi,rq,vj,rp}. Si se satisface la condición de fin de BT por la imposibilidad de hallar vecindad de inserciones, entonces se imprime: “no quedan rutas admisibles, fin búsqueda tabú”. En caso de que sea porque se supera el tiempo de simulación, no se detalla nada. De esta forma termina esta parte del archivo de entrada

Resumen de hitos en BT.

Una vez que la BT ha finalizado el proceso de búsqueda de soluciones, se imprime un pequeño resumen con los siguientes datos:

- Tiempo empleado (minutos) por la BT para realizar todas las iteraciones - Iteración en la que se alcanzó la solución admisible con el menor coste de todas. - Tamaño de las listas para los intercambios - Coste de la solución inicial y coste de la solución final. La mejora, si la hubiera, se expresa en

tantos por cien.

Figura 43. Resumen de hitos en BT en el fichero de salida

Mejor solución.

A continuación, se imprime la mejor solución admisible hallada durante la BT, con el mismo formato

que la mostrada en el apartado Solución inicial M&J y λ-intercambio a excepción de las etiquetas ruta_mejorada_n, ruta_mejorada_n y coste_acumulado. Asimismo, tampoco se hace referencia al coste total tras el rutado, pues ya se hace en la cabecera que precede a este campo.

FIN BÚSQUEDA TABÚ Tiempo empleado (min): [tiempo_empleado] Mejor solucion en iteracion: [iteración] Tamaño lista: [tamaño] Coste de partida: [coste_inicial] Coste (Mejora%): [coste_mejor_solucion] [mejora_coste]

5. RESULTADOS

El gran contenido de información sobre los clientes, flotas, grafos y tablas de conversión junto a la variedad de parámetros de entrada que ofrece la aplicación para personalizar su resolución impiden que pueda hacerse un estudio en términos absolutos sobre la eficacia de la Búsqueda Tabú para cualquier caso que se presente. Es decir, algunos problemas pueden mostrar una mejoría sustancial en los costes totales del rutado, mientras que en otros puede darse de forma leve.

Por ello, lo que se pretende mediante este quinto capítulo es ilustrar de qué forma actúa cada una de las posibilidades que ofrece la aplicación y cómo la Búsqueda Tabú evoluciona según la elección que se haga de las mismas.

La batería de problemas bajo prueba es una adaptación (ficheros vrp) de los casos propuestos por Liu Shen, si bien cuando es necesario se concreta el problema en concreto que se resuelve. Estos problemas se caracterizan porque la flota es heterogénea y todos los clientes tienen tanto ventanas de tiempo como de servicio, lo que dificulta sobremanera el hallazgo de soluciones mejores a la inicial.

5.1. Reducción de los costes de la BT sobre la heurística de Mole.

Como se explicó en el apartado 3, el problema VRP se resuelve en tres fases: 1) la heurística de Mole propone una solución inicial, 2) cada una de esas rutas es mejorada por el operador λ-intercambio y 3) se realiza la Búsqueda Tabú.

Este primer ensayo consiste en cuantificar la reducción de los costes entre el paso 2 y el 3 en un total de 120 ejemplos (Liu Shen). Se necesita escalar el valor de las ventanas de tiempo, pues de lo contrario sería imposible enrutar la mayoría de los ejemplos. El valor de los parámetros que se usa es:

- Función objetivo: Contaminación

- Orden de flota: De menor a mayor capacidad

- Movimiento opt: 3-opt

- Criterio de primera ciudad: Coste máximo

- Lambda, nu y velociad media: 1.

- Tamaño Lista Intercambio: 1000

- Tamaño Lista Inserción: 100

- Inserción en iteración: 1000

- Permitir no admisibilidad: No

- Tiempo simulación: 12 minutos

- Max tiempo en ruta: 1


92

- Máximo tiempo entre nodos: 60

5.2. Evolución de costes según el criterio de asignación de la primera ciudad

En el proceso de génesis de una ruta nueva, es imprescindible indicar el criterio con el que se desea que se elija la primera ciudad y a partir de esa primera ciudad, se determinan el resto en concordancia con lo descrito en la heurística de Mole Jameson.

Este factor, afecta de manera decisiva en el coste inicial del rutado como indican las siguientes figuras.

Figura 44. Mejora de costes de tiempo según el criterio de elección de la primera ciudad.

Figura 45. Mejor de costes de contaminación según el criterio de elección de la primera ciudad.

El problema resuelto en los seis casos es el C101A de Liu Shen. Los resultados desvelan que el criterio de elección de la primera ciudad que da mejores costes tras la Búsqueda Tabú es el de coste o tiempo

268,6 270,3289,4

236,6 244,6 248,6

0

50

100

150

200

250

300

Tiempo Máximo Tiempo Mínimo Ventana Max Mínima

Tie

mp

o t

ota

l ru

tad

o (

h)

Mejora de costes de tiempo según elección de la primera ciudad

Coste M&J

Coste BT

22700,521628,2

24681,6

18367,2 18981,7 19342,2

0

5000

10000

15000

20000

25000

Coste Máximo Coste Mínimo Tiempo Máximo

Co

ste

to

tal r

uta

do

(€

)

Mejora de costes de contaminación según elección de la primera ciudad

Coste M&J

Coste BT

5.Resultados

93

máximo, ya sea para el caso de tiempo (la ciudad más lejana) o de contaminación (la que supone un mayor esfuerzo económico). No obstante, la Búsqueda Tabú palía significativamente esta descompensación inicial, ya que la solución de partida para el caso de minimizar tiempo con el criterio de la ciudad más lejana se mejora un 11,94%, mientras que para la peor elección (la ciudad con la ventana más restrictiva) la mejora es de un 14,08%. Este efecto también se observa en el caso de la contaminación en el que las mejoras para el mejor y peor caso de elección de primera ciudad son respectivamente un 19,09% y 21,63%. Las menores reducciones de costes entre la solución inicial y la final se producen siempre cuando se elige el tiempo mínimo, 9,49% para el tiempo y un 12,24% para la contaminación.

El comportamiento de la Búsqueda Tabú para cada una de estas soluciones de partida es distinto según se elija una u otra, si bien es cierto que tienen a dar resultados mejorados. Para el caso de contaminación, se ha extraído la evolución de los costes iteración a iteración.

Figura 46. Evolución de costes en la Búsqueda Tabú según la elección de la primera ciudad (estacionario).

El primer fenómeno que destaca en la sección de cada una de las líneas. Estos saltos corresponden a la transición entre una etapa de intensificación y otra de diversificación. Es decir, la BT para de intercambiar ciudades entre rutas para insertar una ciudad de una ruta en otra. Para coste mínimo se realiza una inserción, para tiempo máximo seis inserciones y para coste máximo un total de dos.

La solución inicial con coste mínimo lleva a una localizar el punto de partida en el espacio de soluciones en una región de pocos valles. El ascenso del coste justo después de la inserción se produce con mucha rapidez. En el otro extremo, se encuentra la solución de partida con coste máximo, que parece desplazarse en una zona de valles, ya que una vez realizadas las inserciones, los intercambios no mejoran en mucho los costes, pero tampoco los empeoran demasiado.

15000

17000

19000

21000

23000

25000

27000

29000

31000

33000

Co

ste

(€

)

Iteración BT

Evolución de costes en BT según la elección de la primera ciudad

Coste Máximo

Tiempo Máximo

Coste Mínimo


94

En un punto intermedio entre estos dos casos se halla el caso de tiempo máximo. Las oscilaciones de los costes, a excepción del último tramo, guardan cierta similitud, por lo que la Búsqueda Tabú parece estar circundando zonas próximas entre sí o de igual “orografía”.

En la figura anterior puede verse la convergencia de la BT, sin embargo no se tiene información de los instantes iniciales, es decir, del estado transitorio. Por ello, en la figura que se muestra a continuación, se ilustran las primeras iteraciones de la BT para cada caso:

Figura 47. Evolución de los costes en la Búsqueda Tabú según la elección de la primera ciudad (transitorio).

MaxCoste: 152

Min Coste: 1015

Max tiempo: 4278

Como se aprecia en la figura, los costes suelen bajar significativamente desde las primeras iteraciones. A pesar de que las mejores soluciones se encuentran en la iteraciones 152, 1015 y 4278 para coste máximo, coste mínimo y tiempo máximo respectivamente, las primeras soluciones que la BT halla suelen acercarse al valor estimado final.

5.3. Admisibilidad versus no admisibilidad

Uno de los mecanismos de valor añadido al algoritmo radica en la admisión de soluciones no admisibles desde el punto de vista de la carga (no así de las ventanas de tiempo) en pleno proceso de intensificación, es decir, mientras se producen única y exclusivamente intercambios.

Para comprobar la utilidad de este mecanismo, se solucionó el problema del fichero de Liu Shen C101A con los siguientes parámetros:

15000

17000

19000

21000

23000

25000

27000

0 50 100 150 200 250 300

Co

ste

(€

)

Iteración BT

Evolución de costes en BT según la elección de la primera ciudad

Coste Máximo

Tiempo Máximo

Coste Mínimo

5.Resultados

95

- Función objetivo: Contaminación

- Orden de flota: De menor a mayor capacidad

- Movimiento opt: 3-opt

- Criterio de primera ciudad: Coste máximo

- Lambda, nu y velociad media: 1.

- Tamaño Lista Intercambio: 40

- Tamaño Lista Inserción: 20

- Inserción en iteración: 100

- Permitir no admisibilidad: Sí/No

- Tiempo simulación: 12 minutos

- Max tiempo en ruta: 1

- Máximo tiempo entre nodos: 60

Figura 48. Evolución de los costes de contaminación según la admsibilidad de la solución

En relación a los resultados cuando se elige aceptar soluciones no admisibles durante el intercambio, pueden verse que se produce una sola inserción (sobre la iteración 100) y que desde ese punto la caída de los costes es muy pronunciada. Sin embargo, sucede que la mayoría de esos costes pertenecen a

15000

16000

17000

18000

19000

20000

21000

22000

23000

24000

0 50 100 150 200 250 298 348 396 446 494 544

Co

ste

(€

)

Iteración BT

Evolución de costes según admsibilidad de la solución

Admisible

No admisible


96

soluciones no admisibles. Y es que cuando un intercambio no admisible se elige como mejor movimiento y se aplica, al menos una de las rutas está sobrecargada.

Si en la siguiente iteración sucede lo mismo, ya serían de una a cuatro rutas sobrecargadas y así sucesivamente. De este modo, es muy complicado que en sucesivos intercambios, un movimiento, que sólo incumbe a un par de rutas pueda ajustar las demandas con las capacidades de todas aquellas que han sido sobrecargadas y, además, mejorar los costes admisibles anteriores. Son condiciones demasiado duras. Así que por norma general, cuando se tolera la sobrecarga, las soluciones admisibles suelen darse en las dos primeras iteraciones tras la inserción.

No obstante, parece que liberar al modelo matemático de la restricción de capacidad no produce una reducción muy notable en los costes, ya que la diferencia entre la mejor solución admisible y la no admisible es de unos 400€ (veáse la proximidad de las líneas).

En cuanto a la solución que no permite soluciones no admisibles, cabe destacar la prontitud con la que los costes se estabilizan, pues a partir de la iteración 150 no se producen cambios bruscos, incluso después de realizarse las tres inserciones.

6. CONCLUSIONES Y EXTENSIONES

6.1. Conclusiones La problemática del cambio climático y los efectos negativos de las emisiones de un sector como el transporte en auge, instigan a encontrar un punto de encuentro entre ambos. En este sentido, este trabajo se ha dirigido a casar ambas premisas sin perder un ápice de realismo en el problema de distribución y gestión de flotas de vehículos.

Para ello, se ha realizado una revisión de la literatura dividida en dos partes. La primera ha descrito los distintos algoritmos desarrollados hasta la fecha que pretenden dar una solución al problema de ruteo bien desde una perspectiva matemática basada en la experiencia (heurísticas) o desde una estrategia general de actuación (metaheurística) La segunda ha revisado los artículos y propuestas hasta la fecha que añaden conceptos de eco-eficiencia a la resolución del VRP.

La necesidad de crear en un modelo metaheurístico completo que integre este impacto medioambiental del transporte en el entorno, ha llevado al diseño e implementación de una Búsqueda Tabú que considere la diversidad de clientes, flotas de vehículos, geografía del terreno y la repercusión de los costes por contaminación dentro del objetivo de minimizar los costes.

Los cambios sobre el modelo de partida de una Búsqueda Tabú que resuelva el problema VRP de flota heterogénea y clientes con ventanas de tiempo han sido notables. Se han redefinido las funciones objetivo clásicas de distancia y/o tiempo, por otras que dividen los costes como la suma de aquellos propios de una flota de vehículos (coste de mantenimiento, coste de combustible, conductores, coste por carga etc) más otros medioambientales (emisiones por carga, por tipo de categoría de vehículo, ruido, siniestralidad etc).

Este nuevo modelo de la función objetivo ha demostrado que la modificación de las rutas que perseguían minimizar el tiempo total es un hecho. La asignación de clientes a la flota cuando se quieren reducir los costes por contaminación no guarda relación alguna con la temporal, demostrando así que la configuración de rutas clásicas no favorece el respeto al medioambiente. Además se ha comprobado que la elección de la primera ciudad de cada ruta condiciona el resultado final, ya que no tiene en cuenta la distribución de clientes en el espacio.

También se han agregado nuevas estrategias para la Búsqueda Tabú que pretenden explorar detalladamente el espacio de soluciones. Se ha diseñado un método de intensificación que permite la sobrecarga de rutas momentánea para poder hallar mejores soluciones admisibles. Asimismo, se ha demostrado que crear un método de diversificación que permite insertar ciudades de unas rutas a otras cuando no se consigue mejorar el coste durante un tiempo dado es efectivo y reduce el coste global en determinados casos.

6.2. Extensiones Las principales extensiones asociadas al proyecto residen en la mejora de las estrategias implementadas en pos de una reducción de los costes. Sin bien es cierto que el tiempo de convergencia


98

de la Búsqueda Tabú es relativamente rápido (15 minutos en problemas de 200 nodos), se necesitaría flexibilizar algunas restricciones como la definición de movimiento tabú. Actualmente no se permite mover una ciudad cuando ya se ha intercambiado o insertado ya que se detectaron bucles durante el desarrollo. También podría permitirse la extensión de rutas, es decir, permitir el uso de otros vehículos de la flota, pues por el momento sólo se permite reducir el número de rutas. Asimismo podría mejorarse la manera en la que se computan las rutas mono-nodo para que el camión no tuviera que esperar en exceso en destino. En cuanto a la clasificación de los intercambios no admisibles, podría establecerse una cierta tolerancia de tal forma que las rutas sólo se sobrecargaran un tanto por ciento, haciendo el regreso a la admisibilidad más probable.

Además, se propone como extensión la comparación con otras metaheurísticas (Algoritmos de hormigas) bajo las mismas restricciones y haciendo un estudio en cuanto a la relación tiempo de convergencia-costes entre otros.

7. BIBLIOGRAFÍA

[1] Ministerio de Agricultura, Alimentación y Medio Ambiente de España, 2008. .Emisión de contaminantes a la

atmósfera procedentes del transporte. Banco público de indicadores ambientales del Ministerio de Medio

Ambiente y Medio Rural y Marino.

[2] Ministerio de Agricultura, Alimentación y Medio Ambiente de España, 2008. OCDE. Análisis de los Resultados

Medioambientales.

[3] Ministerio de Agricultura, Alimentación y Medio Ambiente de España, 2005. Plan Nacional de Mejora de la

Calidad del Aire.

[4] Ministerio de Agricultura, Alimentación y Medio Ambiente de España, 2010. Perfil Ambiental de España. Informa

basado en indicadores 2010. Nipo: 770-11-221-7, Capítulo: Aire. Edicion en Español.

[5] European Environment Agency, 2010. Laying the foundations for greener transport. TERM 2011: transport

indicators tracking progress towards environmental targets in Europe. EEA Report, No 7/2011, pag 17. ISSN

1725-9177.

[6] Toth, P., Vigo, D., 2000: An Overview of Vehicle Routing Problems. Monographs on Discrete Mathematics and

Applications. In: The Vehicle Routing Problem. SIAM 1-26.

[7] Dantzig, G., Ramser, J., 1959: The truck dispatching problem. Management Science 6 80-91

[8] Clarke, G., Wright, W., 1954: Scheduling of vehicles from a central depot to a number of delivery points.

Operations Research 2 393-410

[9] Nemhauser, G., Wolsey, L., 1988: Integer and Combinatorial Optimization. John Wiley & Sons.

[10] Laporte, G., Nobert, Y., 1987: Exact algorithms for the vehicle routing problem. Annals of Discrete Mathematics

31 147-184

[11] Laporte, G., 1992: The vehicle routing problem: an overview of exact and approximate algorithms. European

Journal of Operational Research 59 Pag 345-358.

[12] Mole, R.H., Jameson, S.R., 1976: A sequential route-building algorithm employing a generalised saving criterion.

Operational Research Quarterly 27 Pag 503-511

[13] Potvin, J.Y., Rousseau, J.M., 1993: A parallel route building algorithm for the vehicle routing and scheduling

problem with time windows. European Journal of Operational Research 66 Pag 331-340

[14] Bodin, L., Golden, B., Assad, A., Ball, M., 1983: Routing and scheduling of vehicles and crews – the state of the art.

Computers & Operations Research 10 63-211.

[15] Christofides, N., Mingozzi, A., Toth, P., 1979: The Vehicle Routing Problem. In: Combinatorial Optimization. Wiley,

Chichester Pag 315-338. Ref 24.

[16] Wren, A., 1971: Computers in transport planning and operation. Ian Allan Ref 25,26,27

[17] Fisher, M., Jaikumar, R., 1981: A generalized assigment heuristic for the vehicle routing problem. Networks 11

109-124 Ref 28

[18] Bramel, J.: Simchi-Levi, D., 1995: A location based heuristic for genreal routing problems. Operation Research 43

649-660 Ref 29


100

[19] Beasley, J., 1983: Route first – cluster second methods for vehicle routing. Omega 11 403-408 Ref 30

[20] Boctor, F., Renard, J., 2000: The column-circular, subsets-selection problema: complexity and solutions.

Computers & Operations Research 27 383-398. Ref 32

[21] Lin, S.: Computer solutions of the travelling salesman problem. Bell System Technical Journal 44 2245-2269 Ref 16

[22] Renaud, J., Boctor, F., Laporte, G., 1973: A fast composite heuristic for the symmetric travelling salesman

problem. Operations Research 498-516 Ref 37

[23] Lin, S., Kernighan, B., 1973: An effective heuristic algorithm for the travelling salesman problem. Operations

Research 498-516 Ref 38

[24] Or, I., 1976: Travelling salesman-type combinatorial optimization problems and their relation to the logistics of

regional blood banking Ref 39

[25] Breedam, A.V., 1995: Improvement heuristics for the vehicle routing problem based on simulated annealing.

European Journal of Operational Research 86 480-490. Ref 40

[26] Thompson, P., Psaraftis, H., 1993: Cyclic transfer algorithms for multivehicle routing and scheduling problems.

Operations Research 41 935-946 Ref 42

[27] Colorni, A., Dorigo, M., Maniezzo, V., 1991: Distributed optimization by ant colonies. Proceeding of the European

Conference on Artificial Life, Elsevier, Amsterdam (1991) 134-142 Ref 45

[28] Glover, F., 1986: Future paths for integer programming and links to artificial intelligence. Computers &


[29] Osman, I., 1993: Metastrategy simulated annealing and tabu search algorithms fot the VRP. Annals of Operations

Research 41 421-451. Ref 56

[30] Gendreau, M., Hertz, A., Laporte, G., 1994: A tabu search heuristic for the vehicle routing problema. Management

Science 40 1276-1290 Ref 57

[31] Taillard, E.D., 1993: Parallel iterative search methods for vehicle routing problems. Network 23 661-673. Ref 58

[32] Volgenat, T., Jonker, R., 1983: The symmetric travelling salesman problem and edge exchanges in minimal 1-tree.

European Journal of Operation Research 394-403 Ref 59

[33] Rochat, Y., Taillard, E., 1995: Probalistic diversification and intensification in local search for vehicle routing.

Journal of Heuristics 1 147-167 Ref 60

[34] Xu, J., Kelly, J., 1996: A network-flow based tabu search for the vehicle routing problema. Transportation Science

30 379-393 Ref 61

[35] Glover, F., 1991: Multilevel tabu search and embedded search neighborhoods for the travelling salesman

problema. Technical report, Graduate School of Bussiness and Administration, University of Colorado Ref 62

[36] Rego, C., 1998: A subpath ejection method for the vehicle routing problem. Management Science 44 1447-1459

Ref 64

[37] Toth, P., Vigo, D., 2003: The granular tabu search and its application to the vehicle-routing problem. INFORMS

Journal on Computing 15 333-346.

5.Resultados

101

[38] Barbarosoglu, G., Ozgur, D., 1999: A tabu search algorithm fot the vehicle routing problema. Computers &


[39] Cordeau, F., Laporte, G., Mercier, A., 2001: A unified tabu search heuristic for VRP with time Windows. Journal of

operational research society 52 928-936 Ref 67

[40] Holland, J., 1975: Adaptation in Natural and artificial systems. The University of Michigan Press Ref 69

[41] Francisco Pereira, Jorge Tavares, P.M.E.C., 2002: A new genetic representation for the vehicle routing problem. In:

Proceedings of the 13th. Conference on Artificial Intelligence and Cognitive Science (AICS) 95-102 Ref 71

[42] Baker, B., Ayechew, M., 2003: A genetic algorithm for the vehicle routing problema. Computers & Operational

Research 30 787-800 Ref 72.

[43] Thangiah, S., 1995: Vehicle Routing with Time Windows using Genetic Algorithms. In: Application Handbook of

Genetic Algorithms: New Frontiers, Volume II. CRC Press 253-277 Ref 73

[44] Thangiah, S., Osman, I., Sun, T., 1994: Hybrid genetic algorithm, simulated annealing and tabu search methods

for vehicle routing problems with time windows. Technical Report SRU-CpSc-TR-94-27, Computer Science

Department, Slippery Rock University Ref 74

[45] Blanton, J., Wainwright, R., 1993: Multiple vehicle routing with time and capacity constrains using gentic

algorithms. In: Proceedings of the 5th International Conference on Genetic Algorithms 452-459. Ref 75

[46] Potvin, J.Y., Bengio, S., 1996: The vehicle routing problema with time Windows – part II. Genetic search. INFORMS

Journal on Computing 8 165-172. Ref 76

[47] Berger, J., Barkaoui, M., Bräysy, O., 2003: A route-directed hybrid genetic approach for the vehicle routing

problem with the time windows. INFOR 41 179-194 Ref 78

[48] Zhu, K., 2000: A new genetic algorithm for VRPTW. Presented at IC-AI 2000, Las Vegas, USA Ref 79

[49] Kay Chen Tan, Loo Hay Lee, Ke Ou, 2001: Hybrid genetic algorithms in solving vehicle routing problems with the

time windows. Asia-Pacific Journal of Operational Research 18 121-130. Ref 80

[50] Potvin, J.Y., Dubé, D., 1994: Improving a vehicle routing heuristic through genetic search. In: International

Conference on Evolutionary Computation 194-199 REf 81

[51] Yong, P., 2009: Research on a Vehicle Routing Schedule to Reduce Fuel Consumption. Measuring Technology and

Mechatronics Automation. ICMTMA ’09. International Conference Vol: 3, 825-827.

[52] Dyckhoff, H., Lackes, R. & Reese, J., 2004: Supply Chain Management and Reverse Logistics. Springer.

[53] Bickel, P., Friedrich, R., Link, H., Stewart, L. & Nash, C., 2006: Introducing environmental externalities into

transport pricing: measurement and implications. Transport Reviews, 26(4): 389–415.

[54] Bektas, T. & Laporte, G., 2011: The Pollution-Routing Problem. Transportation Research Part B,

doi:10.1016/j.trb.2011.02.004.

[55] Eguia, I., Racero, J., Guerrero F.: Evaluating Vehicle Routing Problems with Sustainability Costs

Documents

DISEÑO E IMPLEMENTACIÓN DE UNA BÚSQUEDA TABÚ PARA EL ...bibing.us.es/proyectos/abreproy/12034/fichero/proyecto+VRP+formato+_1_.pdf · deduce que el impacto medioambiental del