desarrollo e implementación de un algoritmo de...
Post on 27-Oct-2018
219 Views
Preview:
TRANSCRIPT
Proyecto Fin de Carrera
Desarrollo e implementación de un algoritmo de
optimización basado en los ritmos del flamenco para
la resolución del problema de distribución de
vehículos en rutas
Autor: María Miranda Burguete
Tutor: Pablo Cortés Achedad
Titulación: Ingeniería Industrial
Sevilla, 2015
DPTO. DE ORGANIZACIÓN INDUSTRIAL Y GESTIÓN DE EMPRESAS II
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
UNIVERSIDAD DE SEVILLA
Proyecto Fin de Carrera | María Miranda Burguete
1 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
Proyecto Fin de Carrera | María Miranda Burguete
2 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
ÍNDICE
1. INTRODUCCIÓN ........................................................................................................... 12
2. LOS RITMOS DEL FLAMENCO ................................................................................. 14
2.1. Introducción al flamenco ......................................................................................... 14
2.2. Nociones de compás y ritmo en el flamenco ........................................................ 15
2.3. Los palos del flamenco ............................................................................................ 16
2.3.1. Compases de doce tiempos ............................................................................. 17
2.3.2. Compases de cuatro tiempos .......................................................................... 19
2.4. Representaciones gráficas de los compases flamencos ....................................... 20
3. EL PROBLEMA DE ENRUTADO DE VEHÍCULOS ............................................... 23
3.1. Introducción al Problema de Enrutado de Vehículos ......................................... 23
3.1.1. Los almacenes ................................................................................................... 24
3.1.2. Los clientes ........................................................................................................ 25
3.1.3. Los vehículos ..................................................................................................... 25
3.2. Variantes del problema de enrutado de vehículos .............................................. 25
3.3. Enfoques algorítmicos para la resolución del problema de enrutado de
vehículos ................................................................................................................................ 27
3.3.1. Métodos exactos ............................................................................................... 27
3.3.2. Métodos heurísticos ......................................................................................... 28
3.3.3. Métodos Metaheurísticos ................................................................................ 29
4. CASO DE ESTUDIO ...................................................................................................... 32
4.1. Elementos que componen el problema ................................................................. 32
4.2. Características y restricciones ................................................................................. 33
4.3. Modelo Matemático ................................................................................................. 34
4.3.1. Variables del Problema .................................................................................... 34
4.3.2. Función Objetivo .............................................................................................. 36
4.3.3. Restricciones o Condiciones de Contorno .................................................... 37
4.3.4. Descripción del modelo completo.................................................................. 39
5. ALGORITMO POR RITMOS DEL FLAMENCO ..................................................... 41
5.1. Base del Algoritmo ................................................................................................... 41
5.2. Procedimiento para la determinación de la solución inicial .............................. 44
Proyecto Fin de Carrera | María Miranda Burguete
3 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
5.2.1. Determinación de la solución inicial mediante la heurística de mínima
distancia ............................................................................................................................. 45
5.2.2. Determinación de la solución inicial mediante la heurística de demanda
máxima ............................................................................................................................. 50
5.3. Operaciones ............................................................................................................... 54
5.3.1. Relocate ............................................................................................................... 55
5.3.2. Exchange ............................................................................................................. 55
5.3.3. Merge_mod.......................................................................................................... 56
5.3.4. 2-Opt* ................................................................................................................. 57
5.4. Algoritmo por Ritmos del Flamenco (ARF) .......................................................... 58
6. IMPLEMENTACIÓN DEL ARF EN CÓDIGO MATLAB ........................................ 67
6.1. Parámetros y variables ............................................................................................ 67
6.2. Archivos y funciones ............................................................................................... 69
7. RESULTADOS DE LA APLICACIÓN DEL ALGORITMO ARF .......................... 73
7.1. Implementación en una Red de Prueba ................................................................ 73
7.1.1. Solución inicial .................................................................................................. 75
7.1.2. Aplicación aislada de las operaciones de búsqueda ................................... 87
7.1.3. Aplicación del ARF particularizado a cada palo del flamenco ................ 106
7.1.4. ARF ................................................................................................................... 128
7.2. Resolución problema de enrutado de vehículos ................................................ 133
8. CONCLUSIÓN .............................................................................................................. 146
8.1. Resumen .................................................................................................................. 146
8.2. Discusión ................................................................................................................. 149
9. BIBLIOGRAFÍA ............................................................................................................ 155
Proyecto Fin de Carrera | María Miranda Burguete
4 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
LISTA DE FIGURAS
Figura 1. Representación cronotónica del Fandango. ........................................................... 21
Figura 2. Representación cronotónica de la Soleá. ............................................................... 21
Figura 3. Representación cronotónica de la Bulería. ............................................................ 21
Figura 4. Representación cronotónica de la Seguiriya. ........................................................ 22
Figura 5. Representación cronotónica de la Guajira. ........................................................... 22
Figura 6. Esquema de un caso particular del VRP [1]. ........................................................ 24
Figura 7. Variantes del VRP. ................................................................................................... 26
Figura 8. Elementos básicos que componen el VRP. ........................................................... 33
Figura 9. Detalle de la representación cronotónica. ............................................................ 41
Figura 10. Esquema resumen del proceso seguido por el ARF.......................................... 44
Figura 11. Valores de las distancias cronotónicas de los palos flamencos. ...................... 45
Figura 12. Diagrama de flujo heurística de mínima distancia. .......................................... 49
Figura 13. Diagrama de flujo heurística de demanda máxima. ......................................... 53
Figura 14. Operación Relocate. ................................................................................................ 55
Figura 15. Operación Exchange. .............................................................................................. 56
Figura 16. Operación Merge_mod. .......................................................................................... 57
Figura 17. Operación 2-Opt*. .................................................................................................. 57
Figura 18. Diagrama de flujo del ARF. .................................................................................. 64
Figura 19. Red de Prueba. ....................................................................................................... 74
Figura 20. Solución inicial por la heurística de mínima distancia sobre la Red de
Prueba. ....................................................................................................................................... 83
Figura 21. Solución inicial por la heurística de mínima distancia sobre la Red de
Prueba. Caso 2........................................................................................................................... 83
Figura 22. Solución inicial por la heurística de demanda máxima sobre la Red de
Prueba. ....................................................................................................................................... 86
Figura 23. Primer movimiento realizado por la operación Relocate sobre la solución
inicial. Aplicación aislada de la operación sobre la Red de Prueba. ................................. 88
Figura 24. Segundo movimiento realizado por la operación Relocate sobre la solución
inicial. Aplicación aislada de la operación sobre la Red de Prueba. ................................. 89
Figura 25. Grafica comparativa de la mejora porcentual del mejor movimiento de cada
operación respecto a la solución inicial sobre la Red de Prueba. .................................... 106
Figura 26. Grafica comparativa de la mejora porcentual del algoritmo particularizado
para cada palo respecto a la solución inicial en la Red de Prueba. ................................. 127
Proyecto Fin de Carrera | María Miranda Burguete
5 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
LISTA DE TABLAS
Tabla 1. Esquema del compás de la Soleá. ............................................................................................ 17
Tabla 2. Esquema del compás de la Seguiriya. ..................................................................................... 17
Tabla 3. Esquema del compás de la Seguiriya al contabilizar únicamente los acentos. .................. 18
Tabla 4. Esquema del compás más frecuente de la Bulería. ............................................................... 18
Tabla 5. Esquema del compás de la Alegría. ......................................................................................... 19
Tabla 6. Esquema del compás del Fandango en cuatro tercios. .......................................................... 19
Tabla 7. Esquema del compás de la Guajira. ........................................................................................ 19
Tabla 8. Ciclo de cuatro tiempos. .......................................................................................................... 19
Tabla 9. Esquema del compás del Tango Flamenco. ........................................................................... 20
Tabla 10. Esquema del compás de la Rumba. ....................................................................................... 20
Tabla 11. Demandas de los clientes de la Red de Prueba. .................................................................. 74
Tabla 12. Distancias de los clientes al almacén en orden de cercanía y demandas características
de la Red de Prueba. ................................................................................................................................ 75
Tabla 13. Solución inicial parcial sobre la Red de Prueba por la heurística de mínima distancia
tras añadir cuatro clientes....................................................................................................................... 76
Tabla 14. Capacidades disponibles tras asignar los cuatro primeros clientes en la solución inicial
sobre la Red de Prueba. .......................................................................................................................... 76
Tabla 15. Distancias de los clientes aún no asignados al cliente 8 en orden de cercanía y sus
demandas en la Red de Prueba. ............................................................................................................ 76
Tabla 16. Solución inicial parcial por la heurística de mínima distancia sobre la Red de Prueba
tras añadir el quinto cliente. ................................................................................................................... 77
Tabla 17. Capacidades disponibles tras asignar el quinto cliente en la solución inicial sobre la
Red de Prueba. ......................................................................................................................................... 77
Tabla 18. Distancias de los clientes aún no asignados al cliente 4 en orden de cercanía y sus
demandas en la Red de Prueba. ............................................................................................................ 77
Tabla 19. Solución inicial parcial por la heurística de mínima distancia sobre la Red de Prueba
tras añadir el sexto cliente. ..................................................................................................................... 77
Tabla 20. Capacidades disponibles tras asignar el sexto cliente en la solución inicial sobre la Red
de Prueba. ................................................................................................................................................. 77
Tabla 21. Distancias de los clientes aún no asignados al cliente 5 en orden de cercanía y sus
demandas en la Red de Prueba. ............................................................................................................ 78
Tabla 22. Solución inicial parcial por la heurística de mínima distancia sobre la Red de Prueba
tras añadir el séptimo cliente. ................................................................................................................ 78
Tabla 23. Capacidades disponibles tras asignar el séptimo cliente en la solución inicial sobre la
Red de Prueba. ......................................................................................................................................... 78
Tabla 24. Distancias de los clientes aún no asignados al cliente 11 en orden de cercanía y sus
demandas en la Red de Prueba. ............................................................................................................ 78
Tabla 25. Solución inicial parcial por la heurística de mínima distancia sobre la Red de Prueba
Proyecto Fin de Carrera | María Miranda Burguete
6 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
tras añadir el octavo cliente. ................................................................................................................... 78
Tabla 26. Solución inicial parcial por la heurística de mínima distancia sobre la Red de Prueba
tras añadir los trece primeros clientes. ................................................................................................. 79
Tabla 27. Capacidades disponibles tras asignar los primeros trece clientes a la solución inicial
sobre la Red de Prueba. .......................................................................................................................... 79
Tabla 28. Distancias de los clientes aún no asignados al cliente 2 en orden de cercanía y sus
demandas en la Red de Prueba. ............................................................................................................ 79
Tabla 29. Solución inicial por la heurística de mínima distancia sobre la Red de Prueba. ............ 79
Tabla 30. Solución inicial parcial tras asignar los doce primeros clientes a la solución inicial
sobre la Red de Prueba. Caso 2. ............................................................................................................. 80
Tabla 31. Capacidades disponibles tras asignar los primeros doce clientes a la solución inicial
sobre la Red de Prueba. Caso 2. ............................................................................................................. 80
Tabla 32. Demandas de los clientes no asignados en la Red de Prueba. Caso 2. ............................ 81
Tabla 33. Solución inicial parcial tras asignar el treceavo cliente a la solución inicial sobre la Red
de Prueba. Caso 2. ................................................................................................................................... 81
Tabla 34. Distancias de los clientes aún no asignados al cliente 12 en orden de cercanía y sus
demandas en la Red de Prueba. Caso 2. ............................................................................................... 82
Tabla 35. Solución inicial por la heurística de mínima distancia sobre la Red de Prueba. Caso 2.
.................................................................................................................................................................... 82
Tabla 36. Demandas de los clientes de la Red de Prueba en orden decreciente. ............................ 84
Tabla 37. Capacidades disponibles tras asignar el primer cliente a la solución inicial por la
heurística de demanda máxima sobre la Red de Prueba. .................................................................. 84
Tabla 38. Capacidades disponibles tras asignar los cuatro primeros clientes a la solución inicial
por la heurística de demanda máxima sobre la Red de Prueba. ....................................................... 84
Tabla 39. Solución inicial parcial sobre la Red de Prueba tras asignar los cuatro primeros clientes
por la heurística de demanda máxima. ................................................................................................ 85
Tabla 40. Solución inicial parcial sobre la Red de Prueba tras asignar los primeros doce clientes a
la solución inicial por la heurística de demanda máxima. ................................................................. 85
Tabla 41. Capacidades disponibles tras haber asignado los doce primeros clientes a la solución
inicial por la heurística de demanda máxima sobre la Red de Prueba. ........................................... 85
Tabla 42. Demandas de los tres clientes aún no asignados por la heurística de demanda máxima
en la Red de Prueba. ................................................................................................................................ 85
Tabla 43. Solución inicial por la heurística de demanda máxima sobre la Red de Prueba. .......... 86
Tabla 44. Primera solución mejorada obtenida con la operación Relocate sobre la solución inicial.
Aplicación aislada de la operación sobre la Red de Prueba. ............................................................. 89
Tabla 45. Mejor solución tras realizar todas las iteraciones de la operación Relocate sobre la
solución inicial por la heurística de mínima distancia sobre la Red de Prueba. ............................. 90
Tabla 46. Capacidades disponibles de los vehículos con la combinación de rutas de la solución
inicial sobre la Red de Prueba. ............................................................................................................... 91
Tabla 47. Rutas uno y dos de la solución inicial por la heurística de mínima distancia sobre la
Proyecto Fin de Carrera | María Miranda Burguete
7 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
Red de Prueba. ......................................................................................................................................... 91
Tabla 48. Rutas uno y dos tras la primera iteración de la operación Exchange sobre la solución
inicial. Aplicación aislada de la operación sobre la Red de Prueba. ................................................. 91
Tabla 49. Rutas uno y dos tras la segunda iteración de la operación Exchange sobre la solución
inicial. Aplicación aislada de la operación sobre la Red de Prueba. ................................................. 92
Tabla 50. Rutas uno y dos tras la tercera iteración de la operación Exchange sobre la solución
inicial. Aplicación aislada de la operación sobre la Red de Prueba. ................................................. 92
Tabla 51. Rutas uno y dos tras la cuarta iteración de la operación Exchange sobre la solución
inicial. Aplicación aislada de la operación sobre la Red de Prueba. ................................................. 92
Tabla 52. Rutas uno y dos tras la quinta iteración de la operación Exchange sobre la solución
inicial. Aplicación aislada de la operación sobre la Red de Prueba. ................................................. 93
Tabla 53. Rutas uno y dos tras la sexta iteración de la operación Exchange sobre la solución
inicial. Aplicación aislada de la operación sobre la Red de Prueba. ................................................. 93
Tabla 54. Rutas uno y dos tras la séptima iteración de la operación Exchange sobre la solución
inicial. Aplicación aislada de la operación sobre la Red de Prueba. ................................................. 93
Tabla 55. Rutas uno y dos tras la octava iteración de la operación Exchange sobre la solución
inicial. Aplicación aislada de la operación sobre la Red de Prueba. ................................................. 93
Tabla 56. Rutas uno y dos tras la última iteración de la operación Exchange sobre la solución
inicial en la que se intercambia el primer cliente de la ruta uno por un cliente de la segunda.
Aplicación aislada de la operación sobre la Red de Prueba. ............................................................. 94
Tabla 57. Rutas uno y dos tras la última iteración de la operación Exchange que relaciona estas
rutas sobre la solución inicial en la Red de Prueba. ............................................................................ 94
Tabla 58. Mejor solución obtenida tras realizar todas las iteraciones de la operación Exchange
sobre la solución inicial generada por la heurística de mínima distancia. Aplicación aislada de la
operación sobre la Red de Prueba. ........................................................................................................ 95
Tabla 59. Solución inicial por la heurística de mínima distancia sobre la Red de Prueba junto con
las demandas de los clientes y las capacidades disponibles de los vehículos. ................................ 96
Tabla 60. Demandas de los clientes de la ruta uno de la solución inicial sobre la Red de Prueba
en orden creciente. ................................................................................................................................... 96
Tabla 61. Primera iteración de la operación Merge_mod sobre la solución inicial. Aplicación
aislada de la operación sobre la Red de Prueba. ................................................................................. 97
Tabla 62. Segunda iteración de la operación Merge_mod sobre la solución inicial. Aplicación
aislada de la operación sobre la Red de Prueba. ................................................................................. 97
Tabla 63. Tercera iteración de la operación Merge_mod sobre la solución inicial. Aplicación
aislada de la operación sobre la Red de Prueba. ................................................................................. 97
Tabla 64. Cuarta iteración de la operación Merge_mod sobre la solución inicial. .......... Aplicación
aislada de la operación sobre la Red de Prueba. ................................................................................. 98
Tabla 65. Quinta iteración de la operación Merge_mod sobre la solución inicial. ......... Aplicación
aislada de la operación sobre la Red de Prueba. ................................................................................. 98
Tabla 66. Mejor solución tras realizar todas las iteraciones de la operación Merge_mod sobre la
solución inicial por la heurística de mínima distancia sobre la Red de Prueba. ............................. 98
Proyecto Fin de Carrera | María Miranda Burguete
8 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
Tabla 67. Rutas uno y dos tras la primera iteración de la operación 2-Opt* sobre la solución
inicial. Aplicación aislada de la operación sobre la Red de Prueba. ................................................. 99
Tabla 68. Rutas uno y dos tras la segunda iteración de la operación 2-Opt* sobre la solución
inicial. Aplicación aislada de la operación sobre la Red de Prueba. ................................................. 99
Tabla 69. Rutas uno y dos tras la tercera iteración de la operación 2-Opt* sobre la solución
inicial. Aplicación aislada de la operación sobre la Red de Prueba. ............................................... 100
Tabla 70. Rutas uno y dos tras la cuarta iteración de la operación 2-Opt* sobre la solución inicial.
Aplicación aislada de la operación sobre la Red de Prueba. ........................................................... 100
Tabla 71. Rutas uno y dos tras la quinta iteración de la operación 2-Opt* sobre la solución inicial.
Aplicación aislada de la operación sobre la Red de Prueba. ........................................................... 100
Tabla 72. Rutas uno y dos tras la sexta iteración de la operación 2-Opt* sobre la solución inicial.
Aplicación aislada de la operación sobre la Red de Prueba. ........................................................... 100
Tabla 73. Rutas uno y dos tras la séptima iteración de la operación 2-Opt* sobre la solución
inicial. Aplicación aislada de la operación sobre la Red de Prueba. ............................................... 101
Tabla 74. Rutas uno y dos tras la octava iteración de la operación 2-Opt* sobre la solución inicial.
Aplicación aislada de la operación sobre la Red de Prueba. ........................................................... 101
Tabla 75. Rutas uno y dos tras la novena iteración de la operación 2-Opt* sobre la solución
inicial. Aplicación aislada de la operación sobre la Red de Prueba. ............................................... 101
Tabla 76. Resumen de los movimientos posibles de la operación 2-Opt* sobre la solución inicial.
Aplicación aislada de la operación sobre la Red de Prueba. ........................................................... 102
Tabla 77. Mejor solución tras realizar todas las iteraciones de la operación 2-Opt* sobre la
solución inicial por la heurística de mínima distancia sobre la Red de Prueba. ........................... 102
Tabla 78. Tiempos de Ejecución de las Operaciones sobre la solución inicial obtenida con la
heurística de mínima distancia sobre la Red de Prueba. .................................................................. 103
Tabla 79. Distancias obtenidas con el mejor movimiento de cada operación sobre la solución
inicial obtenida con la heurística de mínima distancia sobre la Red de Prueba. .......................... 104
Tabla 80. Distancias obtenidas con el mejor movimiento de cada operación sobre la solución
inicial obtenida con la heurística de demanda máxima sobre la Red de Prueba. ......................... 105
Tabla 81. Mejor solución obtenida tras aplicar el algoritmo del Fandango sobre la solución inicial
generada por la heurística de mínima distancia sobre la Red de Prueba. ..................................... 108
Tabla 82. Primera solución mejorada obtenida tras aplicar la primera operación de la Soleá sobre
la Red de Prueba. ................................................................................................................................... 109
Tabla 83. Primera solución mejorada obtenida tras aplicar la segunda operación de la Soleá sobre
la Red de Prueba. ................................................................................................................................... 109
Tabla 84. Primera solución mejorada obtenida tras aplicar la tercera operación de la Soleá sobre
la Red de Prueba. ................................................................................................................................... 110
Tabla 85. Primera solución mejorada obtenida tras aplicar la cuarta operación de la Soleá sobre
la Red de Prueba. ................................................................................................................................... 110
Tabla 86. Primera solución mejorada obtenida tras aplicar la quinta operación de la Soleá sobre
la Red de Prueba. ................................................................................................................................... 111
Tabla 87. Primera solución mejorada obtenida tras aplicar la sexta operación de la Soleá sobre la
Proyecto Fin de Carrera | María Miranda Burguete
9 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
Red de Prueba. ....................................................................................................................................... 111
Tabla 88. Primera solución mejorada obtenida tras aplicar la primera operación de la Soleá en la
segunda iteración del palo sobre la Red de Prueba. ......................................................................... 112
Tabla 89. Primera solución mejorada obtenida tras aplicar la sexta operación de la Soleá en la
segunda iteración del palo sobre la Red de Prueba. ......................................................................... 113
Tabla 90. Distancias y tiempos de ejecución obtenidos tras aplicar diferentes números de
iteraciones del algoritmo de la Soleá sobre la Red de Prueba. ......................................................... 114
Tabla 91. Mejor solución obtenida tras aplicar el algoritmo de la Soleá sobre la solución inicial
generada por la heurística de mínima distancia sobre la Red de Prueba. ..................................... 114
Tabla 92. Primera solución mejorada obtenida tras aplicar la primera operación de la Bulería
sobre la Red de Prueba. ........................................................................................................................ 114
Tabla 93. Primera solución mejorada obtenida tras aplicar la segunda operación de la Bulería
sobre la Red de Prueba. ........................................................................................................................ 115
Tabla 94. Primera solución mejorada obtenida tras aplicar la tercera operación de la Bulería
sobre la Red de Prueba. ........................................................................................................................ 115
Tabla 95. Primera solución mejorada obtenida tras aplicar la cuarta operación de la Bulería sobre
la Red de Prueba. ................................................................................................................................... 116
Tabla 96. Primera solución mejorada obtenida tras aplicar la quinta operación de la Bulería sobre
la Red de Prueba. ................................................................................................................................... 116
Tabla 97. Primera solución mejorada obtenida tras aplicar la sexta operación de la Bulería sobre
la Red de Prueba. ................................................................................................................................... 117
Tabla 98. Distancias y tiempos de ejecución obtenidos tras aplicar diferentes números de
iteraciones del algoritmo de la Bulería sobre la Red de Prueba. ...................................................... 117
Tabla 99. Mejor solución obtenida tras aplicar el algoritmo de la Bulería sobre la solución inicial
generada por la heurística de mínima distancia sobre la Red de Prueba. ..................................... 117
Tabla 100. Primera solución mejorada obtenida tras aplicar la primera operación de la Seguiriya
sobre la Red de Prueba. ........................................................................................................................ 118
Tabla 101. Primera solución mejorada obtenida tras aplicar la segunda operación de la Seguiriya
sobre la Red de Prueba. ........................................................................................................................ 119
Tabla 102. Primera solución mejorada obtenida tras aplicar la tercera operación de la Seguiriya
sobre la Red de Prueba. ........................................................................................................................ 119
Tabla 103. Primera solución mejorada obtenida tras aplicar la quinta operación de la Seguiriya
sobre la Red de Prueba. ........................................................................................................................ 120
Tabla 104. Distancias y tiempos de ejecución obtenidos tras aplicar diferentes números de
iteraciones del algoritmo de la Seguiriya sobre la Red de Prueba. .................................................. 120
Tabla 105. Mejor solución obtenida tras aplicar el algoritmo de la Seguiriya sobre la solución
inicial generada por la heurística de mínima distancia sobre la Red de Prueba. ......................... 121
Tabla 106. Primera solución mejorada obtenida tras aplicar la primera operación de la Guajira
sobre la Red de Prueba. ........................................................................................................................ 121
Tabla 107. Primera solución mejorada obtenida tras aplicar la tercera operación de la Guajira
sobre la Red de Prueba. ........................................................................................................................ 122
Proyecto Fin de Carrera | María Miranda Burguete
10 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
Tabla 108. Primera solución mejorada obtenida tras aplicar la cuarta operación de la Guajira
sobre la Red de Prueba. ........................................................................................................................ 122
Tabla 109. Primera solución mejorada obtenida tras aplicar la quinta operación de la Guajira
sobre la Red de Prueba. ........................................................................................................................ 123
Tabla 110. Distancias y tiempos de ejecución obtenidos tras aplicar diferentes números de
iteraciones del algoritmo de la Guajira sobre la Red de Prueba. ..................................................... 123
Tabla 111. Mejor solución obtenida tras aplicar el algoritmo de la Guajira sobre la solución
inicial generada por la heurística de mínima distancia sobre la Red de Prueba. ......................... 123
Tabla 112. Tiempos de Ejecución y número de iteraciones de los algoritmos independientes de
cada palo sobre la solución inicial obtenida con la heurística de mínima distancia sobre la Red
de Prueba. ............................................................................................................................................... 124
Tabla 113. Distancias obtenidas tras aplicar los algoritmos independientes de cada palo sobre la
solución inicial obtenida con la heurística de mínima distancia sobre la Red de Prueba. .......... 125
Tabla 114. Distancias obtenidas tras aplicar los algoritmos independientes de cada palo sobre la
solución inicial obtenida con la heurística de demanda máxima sobre la Red de Prueba. ......... 126
Tabla 115. Numeración de los palos del flamenco. ........................................................................... 129
Tabla 116. Distancias obtenidas con el ARF para diferentes órdenes de los palos del flamenco
tras una iteración sobre la matriz de palos en la Red de Prueba. ................................................... 129
Tabla 117. Mejor solución obtenida tras aplicar las operaciones de la Seguiriya. ARF sobre Red
de Prueba – paso 1. ................................................................................................................................ 130
Tabla 118. Mejor solución obtenida tras aplicar las operaciones de la Guajira. ARF sobre Red de
Prueba – paso 2. ..................................................................................................................................... 131
Tabla 119. Mejor solución obtenida tras aplicar las operaciones de la Soleá. ARF sobre Red de
Prueba – paso 3. ..................................................................................................................................... 131
Tabla 120. Mejor solución obtenida tras aplicar las operaciones de la Bulería. ARF sobre Red de
Prueba – paso 4. ..................................................................................................................................... 132
Tabla 121. Tiempos de ejecución cumulativos para cada palo en una iteración del ARF sobre la
Red de Prueba. ....................................................................................................................................... 132
Tabla 122. Capacidades de los vehículos. Datos del problema a resolver [6]. .............................. 133
Tabla 123. Localización y demandas del almacén y los clientes del problema [6]. ...................... 134
Tabla 124. Solución inicial del problema [6] dada por la heurística de mínima distancia. ......... 135
Tabla 125. Solución del problema [6] obtenida con una iteración del ARF. .................................. 135
Tabla 126. Solución del problema [6] obtenida con dos iteraciones del ARF. ............................... 136
Tabla 127. Solución del problema [6] obtenida con tres iteraciones del ARF. ............................... 136
Tabla 128. Distancias recorridas y tiempos de ejecución empleados para diferentes números de
iteraciones del ARF sobre el problema [6]. ......................................................................................... 137
Tabla 129. Análisis de los resultados de distintitas iteraciones del ARF sobre el problema [6].. 137
Tabla 130. Resultados de la aplicación del ARF a las variantes resueltas en R.Grosso [6]. ......... 140
Tabla 131. Mejora en la solución de las variantes descritas en R.Grosso [6] con la aplicación del
ARF Adaptado en comparación con el ARF. ........................................................................................ 142
Proyecto Fin de Carrera | María Miranda Burguete
11 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
Tabla 132. Comparativa de los tiempos de ejecución sobre las variantes descritas en R. Grosso
[6] empleando el ARF y ARF Adaptado. .............................................................................................. 142
Tabla 133. Resultados de la aplicación del ARF Adaptado a las variantes resueltas en R. Grosso
[6]. ............................................................................................................................................................ 144
Proyecto Fin de Carrera | María Miranda Burguete
12 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
1. INTRODUCCIÓN
El flamenco es, sin lugar a dudas, el género musical más intrínsecamente ligado a la
cultura del sur de España. A pesar de la errónea imagen que muchas veces se procesa
hacia éste como género asociado al folclore, la complejidad musical del flamenco es tan
grande que lo ha convertido en uno de los géneros más estudiados desde un punto de
vista científico.
Los cambios de ritmo asociados a los distintos compases del flamenco, son estudiados
en este proyecto como herramienta para el diseño de un algoritmo de optimización.
Para verificar el correcto funcionamiento del método diseñado, se resuelve una
particularización simple del problema de enrutado de vehículos, VRP. Los resultados
que se obtienen al particularizar el método según los distintos palos del flamenco, se
usarán para comparar éstos entre sí. El funcionamiento del algoritmo completo, que
integra todos los palos de manera consecutiva, se comprobará a través de la
comparación de los resultados generados con los obtenidos utilizando un algoritmo de
búsqueda ya existente.
La elaboración del proyecto se ha llevado a cabo en diferentes fases:
1. Lectura de la bibliografía relacionada con los aspectos necesarios para el
desarrollo del proyecto:
- Los ritmos del flamenco, base del algoritmo de optimización desarrollado.
El estudio del flamenco se centra en dos aspectos principales: la variación
del ritmo en los principales compases del flamenco, y las diferentes maneras
de representarla.
- Métodos de resolución de problemas de optimización. Teoría sobre los
algoritmos de búsqueda más empleados (estado del arte).
- Estudio del problema de enrutado de vehículos en general y del problema
de enrutado de vehículos con capacidad, CVRP, en particular.
2. Definición del problema a resolver: particularización del problema de enrutado
de vehículos sobre la cual se implementa posteriormente el algoritmo
desarrollado. Definición de las características y restricciones del problema.
3. Diseño del algoritmo. Se desarrollan diferentes operaciones, las cuales son por
sí mismas algoritmos de optimización, y se aplican una tras otra en diferentes
combinaciones según la variación del ritmo en los principales palos del
flamenco. De esta manera se genera un algoritmo para resolver el VRP.
Proyecto Fin de Carrera | María Miranda Burguete
13 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
4. Implementación. Se implementa el algoritmo desarrollado en lenguaje M.
5. Aplicación del algoritmo. Resolución del problema utilizando la herramienta
Matlab. Se prueba el funcionamiento de las operaciones utilizadas resolviendo
un caso sencillo del problema. Implementando cada palo por separado se
compara la efectividad de los mismos. Finalmente se resuelve el problema
usando el algoritmo completo.
6. Análisis de resultados. Los resultados obtenidos con el algoritmo diseñado se
compraran con los proporcionados por un método de búsqueda local en un
estudio del problema llevado a cabo por Rafael Grosso, de la Universidad de
Sevilla.
Proyecto Fin de Carrera | María Miranda Burguete
14 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
2. LOS RITMOS DEL FLAMENCO
El algoritmo matemático que se desarrolla en este proyecto no puede ser comprendido
sin haber alcanzado antes unas nociones básicas sobre el estudio numérico de los
ritmos del flamenco. De igual manera, para explicar la riqueza rítmica del flamenco es
necesario adentrarse en los orígenes históricos de este género musical.
Con dicho propósito, el inicio de esta sección incluye una breve reseña histórica de la
teoría más ampliamente aceptada sobre los orígenes del flamenco. A continuación, se
introducen los conceptos musicales de ritmo y compás. Del concepto de compás
musical se derivan los palos del flamenco, introducidos en un apartado posterior que
contiene una descripción detallada de los más populares y extendidos. Finalmente, la
unión entre el análisis numérico y los palos del flamenco se produce con la
introducción del concepto de representación cronotónica, que será particularizada para
cada uno de los palos incluidos por el autor.
2.1. Introducción al flamenco
En este apartado se sentarán las bases sobre los diferentes ritmos asociados a los palos
o variedades del flamenco. Posteriormente, se empleará la variación de intensidad en
dichos ritmos como guía en la definición de un método de optimización de búsqueda
por trayectoria.
Los algoritmos de optimización de búsqueda por trayectoria constituyen un caso
particular de solución a complejos problemas que buscan alcanzar una solución
óptima. Dichos problemas presentan normalmente una naturaleza combinatoria y
aplican a problemas reales del tipo encontrar la distancia mínima entre varios puntos,
planes de mínimo coste para el reparto de mercancías, la asignación óptima de
trabajadores entre las tareas a realizar o el mejor enrutamiento de un paquete de datos
en internet, entre otros.
Estos algoritmos se utilizan cuando la aplicación de algoritmos exactos es ineficiente o
imposible para generar estimaciones de la solución óptima que pueden alcanzar
grandes resultados con mucho menor coste computacional. La búsqueda por
trayectorias se basa en la generación de una solución admisible y la exploración
multidireccional del conjunto de soluciones vecinas a la misma, que constituyen lo que
se conoce como una estructura de entorno.
Con el objetivo de mejorar dicha solución local, se producen alteraciones en la misma
que pueden incluir el cambio de la estructura de entorno e incluso, el empeoramiento
de la función objetivo en muchas ocasiones o la generación de otra solución inicial o
solución local. El algoritmo finaliza en el momento en el que se satisfacen una serie de
condiciones impuestas inicialmente o en el momento en el que el algoritmo es incapaz
Proyecto Fin de Carrera | María Miranda Burguete
15 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
de alcanzar una solución mejor que la identificada como óptimo local.
En otras palabras, un método de optimización por búsqueda de trayectorias suele
incluir:
Una solución inicial.
Un método de modificación brusca de la misma para definir una nueva
estructura de entorno.
Un procedimiento de búsqueda local dentro de la estructura de entorno.
Un criterio de detención del algoritmo para decidir a qué solución se le aplica
el método de modificación.
De acuerdo con el musicólogo Faustino Núñez [12], las primeras raíces que dan lugar
al nacimiento del flamenco se sitúan en Cádiz, El Puerto de Santa María y San
Fernando, convirtiéndose en una semilla que se desarrollará entre Madrid, Sevilla y
Cádiz a lo largo del siglo XVIII. Dichas raíces, podrían ser interpretadas como
respuesta del pueblo español a la invasión ítalo-francesa impuesta por la ocupación de
España por parte de las tropas francesas.
Como consecuencia de tal combinación de factores, el flamenco es una música que
nació como un género de ritmo libre y que se consideraba debía aprenderse por
imitación, como el lenguaje mismo. En consecuencia, a partir de esas primeras etapas el
flamenco ha crecido y evolucionado como género opuesto a la música occidental
tradicional, a base de modificaciones que los grandes cantaores han ido añadiendo a lo
largo del tiempo.
Sin embargo, lo verdaderamente fascinante del flamenco es que bajo una apariencia de
música popular, esconde una gran complejidad en los ritmos que guían su
interpretación. En las siguientes secciones se expondrá un análisis de dichos ritmos
desde un punto de vista científico, comenzando por una introducción a la terminología
más básica del flamenco.
2.2. Nociones de compás y ritmo en el flamenco
El ritmo puede definirse como la división del tiempo en pulsos de intervalos
constantes. Cuando alguno de estos pulsos se enfatiza, es decir se acentúa, de manera
regular, se origina un ciclo rítmico denominado compás. El compás es, por tanto, un
patrón de acentos que se repite periódicamente. Este último puede ser definido como
la pulsación que regula el tiempo de la ejecución musical a base de divisiones
preestablecidas.
En el flamenco, los pulsos se marcan con las palmas de manera que los acentos
Proyecto Fin de Carrera | María Miranda Burguete
16 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
corresponden con las palmas más fuertes. Frecuentemente, dichos acentos también se
marcan con los pies a través de taconeos de mayor o menor intensidad. Las palmas del
flamenco pueden al mismo tiempo clasificarse en:
Palmas vivas, de tono agudo.
Palmas sordas, de tono grave.
Por otro lado, en el flamenco el silencio cobra gran importancia puesto que el pulso
continúa aunque no se produzca sonido. De esta manera, se puede afirmar que el
flamenco iguala en cierta manera el sonido al silencio.
El patrón rítmico del flamenco es muy flexible, pudiéndose subdividir los diversos
estilos entre aquellos de métrica estructurada y métrica libre; sin embargo, una de las
características más significativas de los estilos de métrica estructurada es la rigidez en
cuanto al ajuste del compás para cada palo o variedad del mismo. A su vez, una de las
principales cualidades que diferencian al flamenco de la música tradicional occidental
es la colocación de los acentos. Ante una composición, un músico intenta
tradicionalmente localizar el uno o inicio del compás a través de un acento situado al
principio del mismo. Sin embargo, en los compases básicos del flamenco más
frecuentes, el acento se encuentra localizado al final del mismo.
Los ritmos básicos del flamenco siguen tres tipos de compás básicos:
Compás binario: el acento se produce cada dos tiempos. A diferencia de la
música tradicional, los acentos se sitúan como se muestra:
o Música tradicional: [1 2 1 2 1 2 …]
o Flamenco: [1 2 1 2 1 2 …]
Compás ternario: el acento se sitúa cada tres tiempos.
o Música tradicional: [1 2 3 1 2 3 1 2 3 …]
o Flamenco: [1 2 3 1 2 3 1 2 3 …]
Compás de amalgama: este es el compás más frecuente en el flamenco y se
construye a partir de una combinación de los dos tipos anteriores.
2.3. Los palos del flamenco
Los compases del flamenco desafían muchos de los cánones de la música occidental.
Una buena muestra de ello es la variedad y complejidad de palos del flamenco que
existen combinando los ritmos básicos de dos y tres tiempos y jugando con la
localización de los acentos.
Proyecto Fin de Carrera | María Miranda Burguete
17 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
El término palo se refiere formalmente a “cada una de las variedades tradicionales del
cante flamenco”. Éstos pueden clasificarse según diferentes criterios como el origen, la
métrica o el carácter, entre otros.
Siguiendo una clasificación según la métrica, los palos más representativos serán
descritos a continuación junto con las tablas que recogen el compás predominante de
los mismos. En estas últimas, se han representado los acentos como cruces de color rojo
mientras que los tiempos no acentuados se representan con cruces negras. Nótese que
en el caso de los pies, únicamente se representan los tiempos acentuados que son
marcados por taconeo.
2.3.1. Compases de doce tiempos
2.3.1.1. La Soleá
Éste es el compás de doce tiempos más frecuente del flamenco. Los acentos se
marcan en los tiempos 3, 6, 8, 10 y 12. Cuando los marcajes empiezan en la
letra de la Soleá, los pasos empiezan en el tiempo 12. Es muy común no marcar
los tiempos 1 y 4 ó 5 y 6. Las escobillas a menudo empiezan en el primer
tiempo del compás. En otras variantes, los acentos se marcan en 3, 7, 8 y 12 o
bien, en algunas combinaciones de zapateado se empieza en el segundo
tiempo y los tiempos 1, 4, 7 y 10 permanecen en silencio.
Tabla 1. Esquema del compás de la Soleá.
Cuenta 1 2 3 4 5 6 7 8 9 10 11 12
Palmas x x x x x x x x x x x x
Pie x x x x x
2.3.1.2. La Seguiriya
Tiene un compás de doce tiempos con la peculiaridad de que el baile
comienza en el octavo y termina en el sexto. Se acentúan los tiempos 8, 10, 12,
3 y 6. Una guía mnemotécnica para este palo es contar como “1 y 2 y 3 y a 4 y a
5”. Cada vez que aparece un acento se inicia la cuenta.
Tabla 2. Esquema del compás de la Seguiriya.
Cuenta
Soleá 8 9 10 11 12 1 2 3 4 5 6 7
Cuenta 1 2 1 2 1 2 3 1 2 3 1 2
Palmas x x x x x x x x x x x x
Pie x x x x x
Proyecto Fin de Carrera | María Miranda Burguete
18 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
Al contabilizar sólo los tiempos acentuados, el compás de doce tiempos se
transforma en un compás de cinco, de manera que los demás pulsos siguen
estando ahí aunque no se contabilicen.
Tabla 3. Esquema del compás de la Seguiriya al contabilizar únicamente los acentos.
1 2 1 2 1 2 3 1 2 3 1 2
Cuenta 1 2 3 4 5
Palmas x x x x x x x x x x x x
Pie x x x x x
2.3.1.3. La Bulería
La Bulería posee uno de los compases más flexibles entre todos los palos. Es un
compás de doce tiempos que se marca en una métrica de 6/8 (dos grupos de
tres octavas) o se divide en dos compases de seis tiempos. En la métrica de seis
por ocho los acentos se marcan en 3, 6, 8, 10 y 12 o 3, 7, 8, 10 y 12. Cuando el
compás se divide en dos de seis tiempos, como es el caso de las falsetas de la
Bulería, los acentos caen en el tercer tiempo y se empieza cada semi-compás
con acento. El compás de la Bulería se presta mucho a la improvisación del
bailaor en cuanto al marcaje de los pasos.
Tabla 4. Esquema del compás más frecuente de la Bulería.
Cuenta 1 2 3 4 5 6 7 8 9 10 11 12
Palmas x x x x x x x x x x x x
Pie x x x x x
2.3.1.4. La Alegría
Este palo presenta un compás de doce tiempos similar al de la Soleá pero con
un tiempo más rápido y animado. Los acentos se marcan en los tiempos 3, 6, 8,
10 y 12 o bien en los tiempos 3, 7, 8, 10 y 12. Los marcajes suelen realizarse de
la misma manera que en la Soleá, comenzando en el tiempo doce. Es muy
frecuente no marcar con los pasos los tiempos 4, 5 y 6 durante la letra o que se
haga una vuelta durante este periodo.
En este compás, algunos pulsos (representados en negrita en la tabla 5) se
retrasan un poco y suenan muy próximos al tiempo inmediatamente
siguiente.
Proyecto Fin de Carrera | María Miranda Burguete
19 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
Tabla 5. Esquema del compás de la Alegría.
Cuenta 1 2 3 4 5 6 7 8 9 10 11 12
Palmas x x x x x x x x x x x x
Pie x x x x x
2.3.1.5. El Fandango
El compás del Fandango es de doce tiempos pero se maneja de manera
diferente a la Soleá y la Alegría. En el Fandango los doce tiempos se dividen en
cuatro tercios con acentos en el primer tiempo o bien en dos compases de 6
tiempos con acentos en el primer y cuarto tiempo.
Tabla 6. Esquema del compás del Fandango en cuatro tercios.
Cuenta 1 2 3 4 5 6 7 8 9 10 11 12
Palmas x x x x x x x x x x x x
Pie x x x x
2.3.1.6. La Guajira
Este compás, de influencia hispanoamericana, se caracteriza por alternar un
compas de seis por ocho con uno de tres por cuatro con acentos en los tiempos
1, 4, 7, 9 y 11.
Tabla 7. Esquema del compás de la Guajira.
Cuenta 1 2 3 4 5 6 7 8 9 10 11 12
Palmas x x x x x x x x x x x x
Pie x x x x x
2.3.2. Compases de cuatro tiempos
En las tres primeras secuencias de cuatro tiempos, se toca con las palmas el
primer pulso en silencio y los tres siguientes aumentando la intensidad
progresivamente. Con el pie se marca el primer pulso de manera fuerte. Para
acabar el ciclo rítmico se toca una secuencia de cuatro tiempos en el que sólo
suenan el segundo y tercer pulso de manera fuerte con las palmas y el pie.
Tabla 8. Ciclo de cuatro tiempos.
Cuenta 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
Palmas - x x x - x x x - x x x - x x -
Pie x x x x x
Proyecto Fin de Carrera | María Miranda Burguete
20 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
2.3.2.1. El Tango
El Tango flamenco es un palo de cuatro tiempos donde los acentos se marcan
en los tiempos primero y tercero.
Tabla 9. Esquema del compás del Tango Flamenco.
2.3.2.2. La Rumba
A diferencia del Tango, en este palo de cuatro tiempos los acentos se marcan
los tiempos dos y cuatro.
Tabla 10. Esquema del compás de la Rumba.
2.4. Representaciones gráficas de los compases flamencos
Existen diversas maneras de representar el compás característico de un determinado
palo. Para este proyecto se ha considerado la representación cronotónica.
La representación cronotónica o representación de histogramas, fue propuesta en 1987 por
Kjell Gustafson [7,8], de la Universidad de Oxford, con el objetivo de representar el
ritmo del habla para el reconocimiento automático de la voz. Posteriormente,
Hofmann-Engl [10] propuso dicha representación para calcular distancias entre ritmos,
demostrando que esta distancia coincide con la percepción de similitud rítmica que
tienen las personas. Al contrario que en otras representaciones, en ésta puede
observarse el tiempo entre pulsos, tratándose por tanto de una representación
dinámica del ritmo. Para ello, se toma el tiempo entre cada dos acentos en dos
dimensiones, representando dicha distancia temporal en los ejes horizontal y vertical.
Se representa el espacio de tiempo entre acentos mediante una caja bidimensional y la
longitud temporal del intervalo en los ejes. En las figuras 1 a 5, se muestra la
representación cronotónica de los cinco palos más representativos del flamenco, las
cuales se utilizarán para el desarrollo del algoritmo de optimización.
Cuenta 1 2 3 4
Palmas x x x x
Cuenta 1 2 3 4
Palmas x x x x
Proyecto Fin de Carrera | María Miranda Burguete
21 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
Figura 1. Representación cronotónica del Fandango.
Figura 2. Representación cronotónica de la Soleá.
Figura 3. Representación cronotónica de la Bulería.
Proyecto Fin de Carrera | María Miranda Burguete
22 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
Figura 4. Representación cronotónica de la Seguiriya.
Figura 5. Representación cronotónica de la Guajira.
Proyecto Fin de Carrera | María Miranda Burguete
23 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
3. EL PROBLEMA DE ENRUTADO DE VEHÍCULOS
En el capítulo anterior se introdujo el concepto de algoritmo de optimización por
búsqueda de trayectorias y las múltiples aplicaciones del mismo. Sin embargo, el
objetivo de este proyecto se centra en su particularización para la resolución de lo que
se conoce como el Problema de Enrutado de Vehículos.
Siendo uno de los problemas más amplios dentro de la logística, el VRP puede
sintetizarse como la búsqueda de un esquema óptimo de encaminado de vehículos de
distribución de tal manera que las necesidades de demanda sean satisfechas a mínimo
coste.
En esta sección se realizará una introducción más detallada del problema de enrutado
de vehículos, los agentes del mismo y sus variantes más frecuentes. A continuación, se
introducen varios algoritmos de resolución de los mismos incluyendo métodos exactos
y de búsqueda aproximada.
3.1. Introducción al Problema de Enrutado de Vehículos
Antes de proceder a la explicación del método de optimización desarrollado durante la
elaboración de este proyecto, se va a introducir en este capítulo el VRP, problema sobre
el que se aplica dicho método.
El problema de enrutado de vehículos, más comúnmente conocido por su
denominación en inglés Vehicle Routing Problem (VRP), es uno de los problemas de
optimización más estudiados. Los costes destinados a distribuir bienes desde los
almacenes a los clientes suponen entre el 10% y el 20% del coste final de los productos,
lo cual ha supuesto un gran esfuerzo por buscar la solución más económica. El
problema fue introducido por primera vez en 1959 por Dantzig y Ramser [3], quienes
lo aplicaron a la entrega de gasolina a las estaciones de servicio. Posteriormente, en
1964, Clarke y Wright [2] propusieron una heurística que mejoraba la aproximación de
Dantzig y Ramser: el Algoritmo de Ahorros. Tras ellos, se han ido proponiendo cientos
de soluciones para las diferentes versiones del citado problema.
La base del problema de enrutado de vehículos es la obtención de un conjunto de rutas
óptimas que debe seguir una flota de vehículos para satisfacer las demandas de un
conjunto de clientes. En general, cada ruta empieza y acaba en un almacén o depósito y
debe ser recorrida por un solo vehículo, de manera que las demandas de todos los
clientes sean satisfechas, se cumplan todas las restricciones y el coste global de
transporte sea mínimo.
La red de transporte se describe a partir de un grafo. Los vértices representan la
localización de los clientes y los almacenes; y los arcos, que representan los caminos
Proyecto Fin de Carrera | María Miranda Burguete
24 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
posibles entre los diferentes clientes y depósitos, llevan un coste asociado.
La figura 6 representa la solución particular para un caso de VRP en el que se dispone
de un único almacén de suministro (representado en la parte central de la figura) y
cinco vehículos de reparto. Cada uno de los 25 clientes viene representado en este caso
por un intervalo de reparto adecuado (fracción de tiempo en la que el cliente puede
recibir la mercancía) junto con su demanda en unidades de producto.
La capacidad de cada camión es igual a 1000 unidades y junto a cada uno de ellos se
representa el número de unidades que deben repartir en la configuración de rutas
actual. En la imagen se ha omitido la localización de los clientes respecto al almacén.
Esta última podría ser especificada en coordenadas polares u ortogonales con respecto
al depósito. Cada una de las rutas puede identificarse con un color diferente.
Figura 6. Esquema de un caso particular del VRP [1].
Como complemento a lo que se ha introducido en esta sección, es necesario mencionar
que existen diferentes versiones del problema a las que se llega cuando se modifican
las características de los principales elementos que lo componen: almacenes, clientes y
vehículos.
3.1.1. Los almacenes
Los almacenes o depósitos guardan los productos a distribuir. En general, son
el punto de partida y de retorno de todos los vehículos. Los almacenes podrán
Proyecto Fin de Carrera | María Miranda Burguete
25 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
tener diferentes restricciones temporales, evitando que varios vehículos recojan
la mercancía a la vez.
3.1.2. Los clientes
Cada cliente tiene asociado una demanda. En la mayoría de los casos, la
demanda de un cliente tendrá que ser satisfecha por un solo vehículo, ya que
sólo podrá ser visitado una vez. Dicho vehículo deberá tener, por tanto, una
capacidad como mínimo de igual valor que la suma de las demandas de los
clientes que va a atender.
Las diferentes variantes del problema aparecen al cambiar ciertas
características, por ejemplo, las restricciones sobre los periodos del día durante
los cuales puede ser servido el cliente, los tiempos de carga y descarga
requeridos o el tipo de vehículo que puede atender al cliente. Así mismo, hay
veces que un cliente puede ejercer de proveedor de otros.
3.1.3. Los vehículos
Una flota de vehículos puede denominarse homogénea, si son todos iguales, o
heterogénea, en el caso de que haya diferentes tipos de vehículos.
Usualmente, cada vehículo podrá recorrer una única ruta y tendrá asociado una
determinada capacidad. El valor asociado a la capacidad representa la máxima
cantidad de bienes que el vehículo puede transportar. Como se verá más
adelante, esta característica es propia de una variante del problema
denominada Capacitated VRP o CVRP.
3.2. Variantes del problema de enrutado de vehículos
Existen diferentes versiones del VRP surgidas a partir de una serie de restricciones que
pueden añadirse al problema original.
El problema del agente viajero, en inglés Travelling Salesman Problem (TSP), es una
particularización en la cual sólo se dispone de un vehículo que tiene que visitar, en una
única ruta, a todos los clientes. En este problema no hay restricciones de tiempo ni
demanda asociada a los clientes. Además, el almacén, que no siempre existe, no se
diferencia de los clientes. Una generalización de este problema es el m-TSP, problema
de los m agentes viajeros, en el cual se tiene un almacén y m vehículos.
Las principales variantes del VRP se muestran en la figura 7. El sentido de la flecha
indica que el problema destino es una extensión del problema que se encuentra en el
Proyecto Fin de Carrera | María Miranda Burguete
26 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
origen de la misma.
Figura 7. Variantes del VRP.
Las características básicas de los problemas identificados en la figura 7 se detallan a
continuación.
- Capacitated VRP (CVRP)
Es la versión más básica del VRP. Como en el problema original, todos los
clientes tienen una demanda conocida que debe ser satisfecha. El objetivo es
minimizar el coste global para servir a todos los clientes. La particularidad del
Capacitated VRP es que se tiene una capacidad de carga, C, asociada a los
vehículos. La suma de las demandas de los clientes por los que pasa una ruta no
debe exceder la capacidad del vehículo que la recorre.
- Distance – Constrained CVRP (DCVRP)
Si se sustituye la restricción de capacidad por una restricción de tiempo, el
nuevo problema se denomina Distance – constrained VRP, en el cual cada arco
lleva asociado un determinado valor de tiempo. La suma de las longitudes de
los arcos que forman cada ruta no puede superar la longitud máxima de la ruta
correspondiente, que tendrá el mismo valor para todas las rutas en el caso de
que todos los vehículos sean iguales. Cuando el valor asociado a cada arco
representa el tiempo de viaje, puede asignarse a cada cliente un tiempo de
servicio, el cual representa el tiempo que puede estar parado el vehículo en el
lugar donde se encuentra el cliente. El tiempo de viaje total será el resultado de
sumar a la longitud del arco, la suma de las mitades de los tiempos de servicio
Proyecto Fin de Carrera | María Miranda Burguete
27 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
de los clientes de origen y destino.
Se habla de Distance – Constrained CVRP cuando se tienen a la vez las
restricciones de capacidad y de longitud máxima.
- VRP with time Windows (VRPTW)
Esta variante incorpora las ventanas temporales. En este caso, se asigna un
intervalo de tiempo a cada cliente que limita el horario en el que puede ser
servido.
- VRP with Backhauls (VRPB)
En esta variante existen dos tipos de clientes: los que requieren una entrega de
bienes y los que esperan una recogida de los mismos.
- VRP with Pickup and Delivery (VRPPD)
En esta versión del problema se realiza una recogida de bienes a ciertos clientes
y se realiza la entrega de los mismos a otros.
- VRP with Access Time Windows (VRPATW)
El VRPATW surge de añadir al VRP with Time Windows una restricción
temporal en relación con el acceso a ciertas zonas de una ciudad. En este caso,
puede ser impedido el acceso a una zona durante un determinado intervalo de
tiempo.
3.3. Enfoques algorítmicos para la resolución del problema de enrutado de vehículos
El problema de enrutado de vehículos ha sido ampliamente estudiado durante las
últimas décadas, debido a la cantidad de problemas derivados del transporte de
mercancías que están relacionados con él. Desde la primera propuesta de Dantzig y
Ramser [3], pasando por la mejora introducida por Clarke y Wright [2], han sido
numerosos los métodos propuestos para su resolución. A día de hoy, existe una gran
variedad de algoritmos para resolver este problema. Los más importantes se enuncian
a continuación, explicando brevemente aquellos con mayor relevancia.
3.3.1. Métodos exactos
Los métodos exactos se formulan como modelos de programación lineal y
llegan a una solución entera a partir de un conjunto acotado de soluciones
factibles. Estos métodos no pueden aplicarse a problemas de más de 100 clientes
Proyecto Fin de Carrera | María Miranda Burguete
28 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
a causa de la complejidad de los modelos matemáticos, por ello, su uso suele
limitarse a fines académicos. El método exacto más extendido es el de Branch
and Bound (ramificación y poda).
En este método se divide el conjunto de soluciones en subconjuntos de menor
tamaño cada vez, dentro de los cuales se determina el valor de la mejor
solución. Se asemeja a un árbol de soluciones, en el que cada nueva rama
contiene una solución posterior. Finalmente, la rama que no puede contener la
solución óptima es eliminada
3.3.2. Métodos heurísticos
Los métodos heurísticos permiten obtener buenas soluciones ahorrando en
tiempos de ejecución, en cambio, estos algoritmos no aseguran la optimalidad
de las soluciones. Debido a que en general los métodos exactos son
inadecuados, las heurísticas se utilizan habitualmente en la práctica.
Los principales atributos de las heurísticas aplicadas al VRP son la precisión,
velocidad, simplicidad y flexibilidad.
3.3.2.1. Método de los Ahorros (Clarke and Wright) [2]
Es el método heurístico más importante para el VRP. Es un método simple
que proporciona una solución aceptable en un tiempo reducido. Las
soluciones se pueden mejorar posteriormente utilizando algoritmos de mejora.
G. Clarke y J.M. Wright propusieron un algoritmo para resolver el problema
de enrutado de vehículos. La particularización del problema para la cual
diseñaron el método consta de un solo almacén central (identificado en la
localización 0), un número n de clientes con demandas conocidas y uno o más
vehículos para realizar las entregas. La solución obtenida proporciona las
rutas que deben seguir los vehículos para satisfacer las demandas de todos los
clientes, de manera que se minimice el coste global del transporte.
Para llevar a cabo el método se deben conocer los costes todos los trayectos
posibles:
: Coste de realizar el trayecto entre el almacén y el cliente j.
: Coste de realizar el trayecto desde el cliente i al cliente j. Se considera
igual al coste del trayecto desde el cliente j al cliente i.
El algoritmo empieza asignando el mismo número de rutas que de clientes, de
manera que cada ruta une el almacén con un cliente. Se calcula el coste de
Proyecto Fin de Carrera | María Miranda Burguete
29 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
transporte asociado a estas rutas.
El siguiente paso es la unión del cliente i con el cliente j, de esta manera el
vehículo irá desde el almacén al cliente i, luego a j y terminará su recorrido en
el almacén. El ahorro que supone este nuevo enlace será:
El algoritmo calcula el ahorro para cada combinación posible y los ordena de
mayor a menor.
3.3.2.2. Método del barrido
Se utilizan coordenadas polares para representar la localización de los clientes
respecto al almacén. Se barre el mapa utilizando una recta con centro de giro
en el almacén, hasta que la suma de las demandas de los clientes barridos sea
igual a la capacidad del vehículo.
Una vez dividido los clientes en subconjuntos, se utiliza un algoritmo, como el
“Método de los Ahorros”, para ordenarlos de manera que se obtenga la ruta
más cercana a la óptima.
3.3.2.3. Métodos de búsqueda local
Se parte de una solución inicial que se irá mejorando conforme avanza el
algoritmo. El procedimiento consiste en evaluar cada nueva posible solución,
avanzando en el caso de que ésta mejore la última solución almacenada. Para
evitar obtener un óptimo local, debería utilizarse un algoritmo más complejo,
que permita avanzar también hacia soluciones peores, pudiendo así explorar
nuevos caminos hasta otros óptimos diferentes al anterior.
3.3.3. Métodos Metaheurísticos
Una metaheurística es una estrategia para resolver un gran número de
problemas diferentes para los que, debido a su complejidad o por falta de
conocimientos, no existe un algoritmo fiable para su resolución. Estos métodos,
que intentan mejorar los métodos heurísticos, proporcionan resultados muy
próximos a la solución óptima para problemas de optimización combinatoria.
Su base es la observación de la naturaleza, la evolución de las especies, diversos
procesos físicos aplicados a materiales, etc.
Como principal característica de los métodos metaheurísticos cabe citar que son
algoritmos de optimización global, por lo que deben incorporar mecanismos
Proyecto Fin de Carrera | María Miranda Burguete
30 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
que eviten estancarse en óptimos locales.
A continuación, se presentan rápidamente algunas de las metaheurísticas que
con más éxito se han aplicado a los problemas de distribución de vehículos en
rutas:
3.3.3.1. Algoritmo Genético
El algoritmo Genético forma parte de los denominados algoritmos evolutivos,
propuestos por primera vez por A.S.Fraser. Se basa en la teoría de la evolución
de especies de Darwin. A diferencia de otros algoritmos que modifican una
única solución, en cada iteración genera un grupo de soluciones a partir de las
soluciones obtenidas anteriormente. El grado de mutación condiciona la
cantidad de características que las nuevas soluciones adoptarán de las
anteriores, y proporciona al algoritmo un aspecto aleatorio que resuelve el
problema de los óptimos locales.
3.3.3.2. Algoritmo de Recocido Simulado (Simulated Annealing)
Se generan las nuevas soluciones de manera aleatoria atendiendo a ciertas
reglas de probabilidad.
El algoritmo se basa en el proceso de recocido según el cual los metales se
calientan hasta altas temperaturas para luego enfriarlos lentamente.
3.3.3.3. Búsqueda Tabú
El algoritmo de Búsqueda Tabú se propone por primera vez en 1989. El
procedimiento seguido por el algoritmo consiste en la búsqueda de una
solución que mejore la función objetivo respecto a la solución actual,
almacenando en una memoria las soluciones anteriores o alguna característica
de las mismas, de manera que éstas no puedan volver a ser exploradas hasta
que pase cierto número de iteraciones.
3.3.3.4. Enjambre de partículas:
Se pretende simular la búsqueda que realizan las partículas, como
interaccionan entre ellas y como se orientan para una búsqueda eficiente.
3.3.3.5. Colonias de hormigas
Este método surge de observar como las hormigas van explorando diferentes
direcciones, dejando un rastro de feromonas a su paso, que les indica las
Proyecto Fin de Carrera | María Miranda Burguete
31 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
direcciones más interesantes para ser exploradas en proporción al nivel en que
se encuentran estas feromonas.
Proyecto Fin de Carrera | María Miranda Burguete
32 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
4. CASO DE ESTUDIO
Se introduce en este apartado el problema que se resolverá mediante el algoritmo
diseñado.
El problema de enrutado de vehículos es muy extenso y tiene multitud de variantes. Se
ha optado por plantear un problema simplificado, de manera que permita centrar la
atención del proyecto en la búsqueda y el diseño del método de optimización en sí,
dejando en un segundo plano el estudio de las versiones más complejas del VRP.
4.1. Elementos que componen el problema
Para modelar el problema es necesario el conocimiento de los distintos elementos que
intervienen en el mismo.
El VRP se modela mediante un grafo, G=(N, L), cuyos conjunto de nodos, N, y de arcos,
L, son conocidos.
- El conjunto de nodos N está compuesto por dos tipos de nodos: los
correspondientes a los clientes, que tienen un nivel de demanda positiva
conocida y se definen por n; y el nodo correspondiente al almacén, el cual se
supondrá con un nivel de oferta suficiente para satisfacer la demanda de
todos los clientes.
- Cada pareja de nodos está unida mediante un arco, de manera que el
conjunto de arcos L contiene todos los caminos posibles entre los clientes y
el almacén.
- Los costes implicados en el problema corresponden a las distancias entre los
nodos. El objetivo del problema es minimizar el coste global del transporte.
- El número de vehículos de transporte disponibles para realizar el reparto de
mercancías está definido por V.
En la figura 8 es posible identificar todos los elementos básicos que configuran el
problema. En la parte superior izquierda se representa la flota de vehículos disponibles
para realizar el reparto de mercancías, para los que se asume una determinada
capacidad (Capv). El único almacén está representado en la zona central de la figura
como un nodo de color verde, con una producción que debe igualar o superar la suma
de las demandas de los clientes a abastecer.
Los n (en este caso ocho) clientes aparecen como nodos de color azul y en su interior se
describe la demanda de cada uno de estos, diferentes entre sí. Por último, L=15 arcos
Proyecto Fin de Carrera | María Miranda Burguete
33 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
que representan las rutas existentes entre los nodos y junto a los que se representan las
distancias dij que los caracterizan.
Figura 8. Elementos básicos que componen el VRP.
4.2. Características y restricciones
El objetivo del problema es obtener el conjunto de rutas que deben seguir los vehículos
para satisfacer las demandas de todos los clientes, minimizando el coste total de
transporte.
El problema a resolver es una particularización del CVRP. Las características o
hipótesis que lo definen son las que siguen:
- La función objetivo se expresa en términos de distancia. Los costes
asociados a los arcos son expresados como la distancia entre los nodos
unidos mediante el correspondiente arco.
- Existe un único almacén con mercancía suficiente para cubrir la demanda de
todos los clientes.
Se designará el nodo correspondiente al almacén como nodo 0. El resto de
nodos, del 1 al n, representarán la localización de los distintos clientes que
componen el problema.
- Cada cliente tiene que ser visitado exactamente una vez y su demanda debe
Proyecto Fin de Carrera | María Miranda Burguete
34 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
ser completamente satisfecha por el único vehículo que lo visite.
- Los vehículos tienen una capacidad asociada, Capv, que representa la
cantidad máxima que pueden transportar. Las rutas se harán de tal manera
que la suma de las demandas de los clientes que visita un vehículo sea igual
o inferior a la capacidad de éste.
Se consideran diferentes valores de capacidad. El resto de restricciones son
las mismas para toda la flota.
- En un mismo problema, cada vehículo puede realizar una única ruta. El
número máximo de rutas que pueden recorrerse será, por tanto, igual al
número de vehículos disponibles.
- Todas las rutas empiezan y acaban en el depósito. Los vehículos parten del
almacén, reparten la mercancía a los clientes correspondientes, y regresan
de nuevo al almacén.
4.3. Modelo Matemático
Dada la diversidad de factores que pueden intervenir y modificar un VRP, existen
múltiples variantes que no son el objeto de análisis de este proyecto. Por esta misma
razón, en la literatura académica es posible identificar como diversos autores han
centrado sus esfuerzos en generar algoritmos que dan solución a problemas definidos
tras la adherencia a diversas simplificaciones.
En esta sección se incluye el modelo matemático del VRP particularizado sobre el que
se aplicará el algoritmo generado. Por tanto, se describen a continuación las variables
involucradas en el modelado matemático del mismo, las restricciones que limitan el
número de soluciones posibles y la función objetivo sobre la que se fundamenta el
proceso de optimización.
4.3.1. Variables del Problema
Las variables matemáticas necesarias para el modelado de la particularización
del VRP analizada en este documento son las siguientes.
- {N} Conjunto de nodos integrados en G. Por nodo puede entenderse la
localización física o virtual en la que un vehículo de distribución puede cargar /
tomar unidades de producto o bien descargar / entregar estas últimas. La
definición de cada nodo también es un elemento que juega un papel esencial en
la naturaleza de un VRP. En particular, en este documento se asume que un
nodo queda definido por su localización y un valor determinado de demanda.
Proyecto Fin de Carrera | María Miranda Burguete
35 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
De esta manera, se eliminan condiciones que añaden complejidad al problema
como la existencia de intervalos de disponibilidad de los nodos, la limitación de
los vehículos que pueden acceder a un nodo o la posibilidad de almacenar de
manera temporal unidades de producto en un nodo. Este conjunto puede a su
vez descomponerse en dos subconjuntos, C y A, que contienen respectivamente
los clientes que demandan productos y los almacenes desde los que se
distribuye. En este caso se ha tomado un único almacén, por lo que el conjunto
A esta contenido por un solo elemento.
Los nodos se encuentran identificados por una numeración de manera que el
nodo 0 representa el almacén y los nodos 1 a n los clientes a abastecer.
- {A} Conjunto de nodos tipo almacén o depósito dentro de N. En este caso el
nodo almacén es único y viene definido por el subíndice 0.
- {C} Conjunto de nodos clientes dentro de N.
- {Capv} Esta variable, expresada en unidades de producto a distribuir,
representa la capacidad de carga de cada uno de los vehículos de la flota de
reparto.
- {Demi} Esta variable describe la demanda de cada uno de los nodos que
constituyen el conjunto N. En el caso de los clientes la demanda toma un valor
mayor o igual que cero, mientras que los nodos almacén poseen una demanda
negativa, cuyo valor absoluto también es identificada con la variable P o
Producción del mismo. En el problema considerado, el único almacén tiene un
nivel de producción superior a la suma de las demandas asociadas a los
clientes, cuyo valor exacto se desconoce.
- {dij} Cada uno de estos valores representa la distancia física entre los nodos i y
j y define el arco lij. Las distancias se calculan aplicando trigonometría a las
ordenadas y abscisas de cada nodo con respecto al resto, es decir, la distancia
mínima entre los mismos en un plano de dos dimensiones.
- {Δ+(i)} Bajo esta denominación se hace referencia al conjunto de nodos
adyacentes al nodo i, es decir tales que:
- {Δ-(i)} Bajo esta denominación se hace referencia al conjunto de nodos
incidentes al nodo i, es decir tales que:
- {G} Por esta letra se designa al gráfico o grafo que representa el modelo
matemático del problema a resolver e incluye dos elementos esenciales: nodos y
Proyecto Fin de Carrera | María Miranda Burguete
36 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
rutas.
- {L} Conjunto de arcos incluidos en G. Como arco se entiende la vía de
comunicación entre nodos para un vehículo de transporte. Cada arco viene
acompañado por una característica que intrínsecamente afecta a la función
objetivo del problema. Dichas características pueden tener un efecto de
penalización (distancia entre dos puntos) o beneficio (admisibilidad de carga de
una ruta) sobre la función objetivo. Para el objetivo de este documento, cada
arco queda definido por los nodos que une así como por la distancia física que
un vehículo debe recorrer al cubrir dicho arco.
Enlazando con la realidad física del problema, para el propósito de este trabajo
se ha considerado que cada arco lij (que une los nodos i y j) representa el
recorrido óptimo o de mínima distancia entre todos los posibles que unen
dichos nodos. Esta afirmación se apoya en la asunción de que no existen
condiciones de tráfico que alteren la distancia característica de una ruta o la
elección de la óptima de la misma entre dos nodos.
- {lij} Arco único entre los nodos i y j. Caracterizado por la distancia
característica del mismo.
- {xij} Variable binaria refería al arco lij que toma el valor 1 si dicho arco es
recorrido por un vehículo y 0 en caso contrario.
- {V} Esta variable representa el número de vehículos disponibles en la flota de
reparto para la distribución de la mercancía. Esta flota está compuesta por
vehículos que operan simultáneamente.
- {Si} Los vectores Si definen las rutas seguidas por cada uno de los vehículos de
reparto. De esta manera, existen V vectores que corresponden a los V vehículos
de la flota. Cada vector contiene en este problema el almacén o nodo 0 seguido
del resto de clientes visitados por cada vehículo. Al final de cada vector se
incluye de nuevo el nodo 0 indicando que las rutas finalizan en el almacén.
4.3.2. Función Objetivo
La función objetivo del caso analizado en este proyecto queda definida como:
Minimizar
Al no haberse introducido ninguna restricción temporal o de coste en la
consideración de las posibles rutas para la distribución de producto, la función
Proyecto Fin de Carrera | María Miranda Burguete
37 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
objetivo es única y busca minimizar la distancia total recorrida por la flota de V
vehículos disponibles.
4.3.3. Restricciones o Condiciones de Contorno
Las restricciones de este problema son las siguientes:
Proyecto Fin de Carrera | María Miranda Burguete
38 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
A continuación se describen las implicaciones de dichas restricciones sobre el problema objeto de estudio.
(2) – Esta restricción impone que los nodos clientes deben tener una demanda positiva.
(3) – La demanda de los nodos almacén debe ser negativa e igual al valor absoluto de su producción. En este caso se ha especificado un conjunto de nodos productivos, sin embargo en la resolución posterior siempre se ha considerado un único nodo almacén definido como nodo 0. En esta restricción se impone la desigualdad ya que en ausencia de producción el problema carece de sentido matemático.
(4) – El sumatorio de la producción o el stock de los nodos almacén (o nodo único en este caso) debe ser mayor o igual a la suma de todas las demandas de los nodos clientes para poder abastecer a los mismos.
(5) – La flota de vehículos debe ser capaz de abastecer en una sola tanda de
entregas la demanda total de los clientes.
(6) y (7) – El número de rutas que parten y retornan respectivamente del nodo almacén debe ser menor o igual que el número de vehículos disponibles. Al ser este último valor fijo, se omite la necesidad de alcanzar en el problema el número de vehículos disponibles para pasar a definir cuantos de los disponibles están operativos.
(8) y (9) - Estas condiciones representan el hecho de que todos los clientes deben ser visitados por un único vehículo de reparto. Nótese como en esta condición se ha omitido el almacén, del que parten previsiblemente varias rutas.
(10) – El mínimo número de vehículos para satisfacer las condiciones del problema es igual a la unidad.
(11) – Esta condición define el carácter binario de las variables xij.
(12) – Cada vehículo debe satisfacer la demanda de los nodos que visita con un único paso por ellos. Si bien las restricciones (8) y (9) imponen que cada cliente sea visitado por un vehículo de reparto, esta condición elimina el supuesto de
Proyecto Fin de Carrera | María Miranda Burguete
39 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
que el mismo vehículo visitase a un cliente en dos ocasiones. Aunque en el contexto del ejemplo simplificado que aquí se plantea esta restricción es redundante, en el caso de que existieran otros nodos de recogida de producto seria esencial incluirla.
(13) – La capacidad de cada vehículo debe ser suficiente para abastecer a todos los nodos clientes que forman parte de la ruta asignada al mismo en un solo recorrido de la misma.
4.3.4. Descripción del modelo completo
Una vez descritos los elementos matemáticos que componen el problema objeto
de estudio en este documento, es posible formular el mismo de una manera más
académica y global, tal y como se recoge a continuación.
“Se desea generar un programa de distribución de mínima distancia capaz de
abastecer la demanda de un número n de clientes a partir del stock P disponible
en un único almacén. Para esta tarea se dispone de un numero V de vehículos
de reparto de capacidad de carga igual a Capv.
La ruta Sv asignada a cada vehículo debe partir del almacén o nodo 0 y retornar
al mismo de manera que se abastezca la demanda de cada cliente con una sola
visita. Un único vehículo debe visitar a cada cliente y su capacidad debe ser
suficiente para abastecer a todos los clientes que se le asignen en un único
recorrido.
Se conocen las demandas de cada cliente y se asume que existen lij rutas que
unen todos los nodos entre sí y con el almacén, de forma que la distancia dij que
separa a cada uno de estos nodos es también conocida. No existen restricciones
referidas al intervalo temporal de reparto o las condiciones de tráfico entre los
nodos”
Matemáticamente el problema queda formulado como:
Minimizar
Sujeto a
Proyecto Fin de Carrera | María Miranda Burguete
40 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
Proyecto Fin de Carrera | María Miranda Burguete
41 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
5. ALGORITMO POR RITMOS DEL FLAMENCO
Esta sección se centra en el diseño y definición detallada del algoritmo que se
desarrolla en este Proyecto Fin de Carrera. Con el objetivo de diferenciar este algoritmo
de aquellos existentes en la literatura académica se ha denominado al mismo como
“Algoritmo por Ritmos del Flamenco” o “ARF”. Este último será desarrollado a
continuación con atención a los siguientes aspectos.
- Fundamento matemático del algoritmo principal, así como las posibles
combinaciones de las operaciones según los ritmos del flamenco.
- La generación de la solución inicial.
- Las operaciones utilizadas.
- El algoritmo ARF.
5.1. Base del Algoritmo
La representación cronotónica de los palos del flamenco refleja el tiempo que
transcurre entre cada dos golpes fuertes del compás. Este intervalo de tiempo es
denominado distancia cronotónica, la cual, al medirse en ambos ejes x e y, se
representa mediante un bloque de forma cuadrada. Este concepto, introducido en la
sección 2.4 de este documento, sustenta la base del desarrollo del ARF como se describe
a continuación.
La representación cronotónica de un palo del flamenco, tal y como ilustran las figuras 1
a 5 del capítulo 2, genera un patrón de cuadrados de diferente lado que registran la
distancia en tiempos entre dos acentos consecutivos. Considérese el caso de la Bulería,
cuya representación cronotónica se encuentra recogida en la figura 9.
Figura 9. Detalle de la representación cronotónica.
Proyecto Fin de Carrera | María Miranda Burguete
42 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
Para este palo, los acentos se encuentran en los tiempos 2, 6, 7, 9, 11 y 12. De esta
manera, entre el inicio del compás y el primer acento existen dos tiempos, es decir, la
distancia cronotónica es igual a dos y aparece representada como un cuadrado de lado
igual a dicho valor. Si analizamos el siguiente acento, en el tiempo 6, este se encuentra
a una distancia de cuatro tiempos sobre el anterior. En esta ocasión la distancia
cronotónica es igual a cuatro y se representa con un cuadrado cuyo lado toma dicho
valor. Estos pasos se repiten hasta llegar al final del palo.
Como resultado de este análisis del palo, se puede concluir que la Bulería queda
cronotónicamente definida por el siguiente vector de distancias:
Bulería → [2 4 1 2 2 1]
Este proceso es igualmente aplicable al resto de palos del flamenco. La idea principal
que reside tras el Algoritmo por Ritmos del Flamenco consiste en leer los valores de
distancias cronotónicas asignados a un palo e identificarlos con una operación de
búsqueda local. Según se puede apreciar por simple inspección de los palos
considerados en este Proyecto Fin de Carrera, las distancias cronotónicas que
componen los distintos palos toman valores comprendidos entre 1 y 4.
La base del proceso de optimización aplicado en el ARF sostiene que a cada uno de los
cuatro valores que puede tomar la distancia cronotónica entre dos acentos de un palo
se le asigna una operación de búsqueda local. Es de gran importancia recalcar aquí el
carácter local de dichas operaciones, ya que estas últimas no buscan una modificación
del espacio de búsqueda sino una mejora local de la solución inicial.
El ARF contiene por tanto cuatro operaciones de búsqueda local. Ahora bien, dichas
operaciones deben ser asignadas a cada uno de los cuatro valores que la distancia
cronotónica puede tomar. El criterio seguido a la hora de asignar operaciones a cada
valor de la distancia cronotónica ha sido el grado de alteración sobre la solución actual.
De esta manera y como se describirá en un apartado posterior de este capítulo, valores
crecientes de la distancia cronotónica corresponden a operaciones que introducen un
mayor grado de modificación sobre la solución actual.
En este punto es necesario definir qué se entiende por el grado de alteración de la
solución actual. Las operaciones de búsqueda local analizan nuevas combinaciones o
rutas para los vehículos de reparto a base de desplazar o intercambiar clientes. En base
a esta característica, el ARF mide el grado de alteración de la solución inicial en base al
número de clientes desplazados de su posición de partida.
Sin embargo, cualquier operación local es susceptible de errar en la búsqueda de una
solución mejor que la actual, por lo que podría no desplazar ningún cliente. De ahí que
para ordenar el grado de alteración que cada operación ejerce sobre la solución actual
sea necesario referirse a la probabilidad. En otras palabras, la operación asignada a la
mayor distancia cronotónica en el ARF es aquella susceptible de desplazar un mayor
Proyecto Fin de Carrera | María Miranda Burguete
43 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
número de clientes al ejecutarse exitósamente y viceversa.
Una vez se ha definido el paso de distancia cronotónica a operación de búsqueda local,
debe aclararse el modo en el que el ARF procesa un palo del flamenco. Al ejecutar un
palo completo, el ARF recorre la representación cronotónica del mismo de inicio a fin y
ejecuta las operaciones asignadas a las distancias cronotónicas que se van obteniendo
al recorrer el palo.
Retornando al ejemplo de la Bulería, al ejecutarse este palo el ARF aplicaría las
siguientes operaciones sobre la solución actual:
1. Operación 2
2. Operación 4
3. Operación 1
4. Operación 2
5. Operación 2
6. Operación 1
Esta sucesión supone la aplicación del palo en una iteración, sin embargo, aún es
necesario definir las iteraciones deseadas para cada palo así como el modo en el que se
ejecutan las operaciones de búsqueda local. Información más detallada sobre el proceso
se incluye en secciones posteriores de este documento.
Para poder ejecutar un palo determinado y, en consecuencia, las operaciones que su
distancia cronotónica impone, es necesario que el ARF se valga de un punto de partida
o solución inicial sobre la que se realizará un proceso de optimización local. En
resumen, la figura 10 recoge los pasos ejecutados en el ARF tal y como este último ha
sido definido. Nótese como el filtro de selección de operación ha sido representado
enviando el valor 2 al algoritmo por ser ésta la primera distancia cronotónica de la
Bulería, ejemplo seguido hasta ahora como ilustración.
El mismo proceso resultaría aplicable a todos los palos considerados en este
documento. En la figura 11 se muestra la representación cronotónica de los cinco palos
más relevantes del flamenco incluyendo el valor de las distancias entre acentos. Para
los diferentes palos se obtienen las siguientes combinaciones de distancias:
- Fandango: [3 3 3 3]
- Soleá: [2 3 2 2 2 1]
- Bulería: [2 4 1 2 2 1]
Proyecto Fin de Carrera | María Miranda Burguete
44 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
- Seguiriya: [2 2 3 3 2]
- Guajira: [3 3 2 2 2]
Figura 10. Esquema resumen del proceso seguido por el ARF.
Una vez se han establecido los fundamentos del ARF y la metodología seguida al
ejecutar una iteración sobre uno de los palos, en las siguientes secciones se ofrece una
descripción más detallada de los tres componentes o módulos en los que se ha
descompuesto el algoritmo: La búsqueda de una solución inicial, las operaciones de
búsqueda local y la ejecución global del ARF.
5.2. Procedimiento para la determinación de la solución inicial
La solución inicial debe contener una serie de rutas admisibles, una por cada vehículo
disponible, mediante las cuales se satisfagan las demandas de todos los clientes de
manera que se cumplan los requisitos del problema. Las operaciones que se realizan
durante el algoritmo modifican las rutas a través de diferentes movimientos de
clientes, por lo que la generación de una solución factible inicial es condición necesaria
para comenzar las iteraciones sobre los palos.
El algoritmo ARF, al ser un método de búsqueda aleatorio, proporcionará soluciones
de calidad diferente de acuerdo con la solución inicial de partida. Dada la importancia
de esta última, en este trabajo se han propuesto dos heurísticas. Puesto que el objetivo
del problema es minimizar la distancia total recorrida, se ha diseñado una primera
heurística que asigna los clientes a las rutas según las distancias entre ellos. Como
Proyecto Fin de Carrera | María Miranda Burguete
45 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
segunda opción se plantea una heurística en la que las rutas iniciales se generan
analizando únicamente las cantidades demandadas por los clientes.
Figura 11. Valores de las distancias cronotónicas de los palos flamencos.
5.2.1. Determinación de la solución inicial mediante la heurística de mínima
distancia
Para comenzar, se crea un número de rutas vacías V igual al número de
vehículos disponibles. El proceso consiste en el llenado progresivo de las rutas,
recorriendo las mismas de manera secuencial. Empezando por la primera ruta,
se va añadiendo un cliente a cada ruta siempre que la demanda del cliente sea
como máximo igual a la capacidad disponible del vehículo correspondiente.
Analizando siempre los clientes que no han sido asignados, el cliente que se
añade a una ruta es en cada caso el más cercano al último cliente visitado por la
misma, o el más cercano al almacén en el caso de ser el primer cliente que se
añade a dicha ruta.
Proyecto Fin de Carrera | María Miranda Burguete
46 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
El siguiente ejemplo muestra el proceso de forma clara:
Se quiere repartir la mercancía desde un almacén a 4 clientes con las siguientes
demandas: 3, 5, 2, 2. Para ello se dispone de dos camiones con una capacidad igual a 7.
Las distancias entre todos los puntos se detallan en la matriz
d =
Siendo dij la distancia entre el cliente i-1 y el cliente j-1. La primera fila y columna
corresponde a la distancia entre el almacén y los clientes.
Resolución
Dist_ordenada = ( 2 5 10 16 ) que corresponde a los clientes 2, 4, 1, y 3.
La matriz de rutas queda de la siguiente manera:
Rutas=
La capacidad disponible de los vehículos tras la asignación de clientes es la capacidad
menos la demanda de los clientes correspondientes. En este momento las capacidades
disponibles de los vehículos son 2 y 5 respectivamente.
Eliminando las filas de los clientes asignados la matriz de distancias queda:
d’ =
Comenzando por la ruta 1, el cliente más próximo al 2 es el cliente 1 (la columna 3
refleja las distancias entre el cliente 2 y los clientes 1 y 3), como la demanda del cliente 1
es mayor que la capacidad disponible del vehículo asociado a la ruta 1 (dem1=3 >
cap1=2), se pasa al siguiente cliente más cercano al cliente 2, que en este caso es el único
cliente que queda, el cliente 3. Continuando este procedimiento y comprobando las
capacidades, las rutas quedan:
Rutas=
Y al haber visitado a todos los clientes, esta sería la solución inicial.
Hay casos en los que uno o varios clientes presentan una demanda
considerablemente superior al resto. Esta demanda puede tener un valor
Proyecto Fin de Carrera | María Miranda Burguete
47 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
cercano a la capacidad de los vehículos. En esta situación y debido a las
restricciones de capacidad impuestas, dichos clientes podrían no ser asignados
a ninguna ruta al finalizar el algoritmo de generación de la solución inicial.
Para evitarlo, en cada iteración se comprueba que la suma de las dos mayores
demandas de los clientes aún no asignados es inferior a la máxima de las
capacidades disponibles. En caso positivo se prosigue el algoritmo con
normalidad, en caso contrario, el cliente cuya demanda es máxima se asigna a la
ruta con menor capacidad disponible que sea capaz de cubrir la demanda del
cliente.
El proceso seguido para la obtención de la solución inicial mediante esta
heurística se representa en el diagrama de flujo de la figura 12 de manera
simplificada. Para su correcta comprensión es necesario aclarar en primer lugar
algunos términos empleados en el diagrama:
El contador Cont se emplea para confirmar que todos los clientes del
VRP han sido asignados a las rutas de los V vehículos disponibles.
La variable Rutas constituye una matriz donde se almacenan las rutas
asignadas a los V vehículos disponibles. Las filas de esta matriz se
corresponden con las variables Si definidas en el capítulo 4. El número
de columnas de esta matriz es igual al número de clientes para
garantizar las dimensiones consistentes de la misma. De esta manera,
los espacios adicionales una vez se han definidos las rutas iniciales
están completados con ceros para facilitar la programación del
algoritmo y la asignación de memoria.
El puntero i recorre las filas de la matriz Rutas para que se añadan
clientes a cada ruta de manera consecutiva en condiciones normales.
El puntero j se encarga de colocar cada cliente asignado a una ruta
inmediatamente después del último introducido. En otras palabras, este
puntero garantiza la ubicación de cada cliente en la correcta columna de
la matriz Rutas.
El puntero t se ha creado para especificar que es posible que se rompa el
orden convencional de colocación de clientes en las rutas y el algoritmo
se vea forzado a colocar a un cliente en una fila distinta a la que indica
el puntero i.
El subíndice k se ha introducido para especificar el cliente que en cada
iteración se introduce en la ruta marcada por el puntero i en la posición
indicada por el puntero j.
Cada vez que se añade un cliente a una ruta se actualiza la capacidad
Proyecto Fin de Carrera | María Miranda Burguete
48 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
del camión correspondiente. La variable cap del diagrama se refiere a
las capacidades disponibles en cada iteración.
Al asignar un cliente a una ruta, este se elimina de un vector que
contiene los clientes no asignados.
El vector demanda, dem, contiene en cada instante las demandas de los
clientes aún no asignados.
La variable n representa el número total de clientes del VRP que deben
asignarse a las V rutas para alcanzar una solución inicial admisible.
La variable d(i,j) hace referencia a la distancia entre el nodo i y el nodo j
del problema, obtenida a partir las coordenadas de los mismos.
A continuación se realiza una descripción detallada del diagrama descrito por
la figura 12 con el que se ilustra la heurística de mínima distancia para la
obtención de una solución inicial.
1) Inicio del algoritmo y lectura de los datos, que incluyen: Matriz de
coordenadas de los nodos, número de clientes y demandas de los mismos,
número de vehículos y capacidad de cada uno de éstos.
2) Inicialización del contador Cont con valor nulo así como la inicialización de
la matriz Rutas de dimensiones [V x n] con ceros.
3) Inicialización del puntero i con valor nulo.
4) El algoritmo se pregunta entonces si el último cliente introducido ha sido
colocado en la última de las rutas, es decir, si el puntero i tiene el valor V. En
caso afirmativo el algoritmo vuelve al paso 3. En caso negativo el algoritmo
continúa en el paso 5.
5) El puntero i es incrementado para asignar un cliente a la siguiente ruta o fila
de la matriz Rutas.
6) El algoritmo comprueba si el valor de la máxima capacidad restante (tras la
inclusión de clientes en las rutas) de los vehículos es mayor que la suma de
las dos demandas mayores entre los clientes sin asignar. En otras palabras,
se comprueba si el vehículo con mayor capacidad restante admite en su ruta
a los dos clientes con mayor demanda entre los que aún no han sido
asignados. En caso afirmativo, el algoritmo sigue su curso normal en el paso
8. En caso contrario, se ejecuta el paso 7.
Proyecto Fin de Carrera | María Miranda Burguete
49 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
Figura 12. Diagrama de flujo heurística de mínima distancia.
Cont ← 0
Rutaslm ← 0,
l = 1,…,V ;m = 1,…,n
Datos
max(cap) > demi + demj
i, j / demi > demj > demk,
k [1,n]/k≠i,j
Cont ← Cont + 1
Rutastj ← clientek
k / demk = max(dem);
t / capt = min(cap) & capt > demk;
j / rutastj = 0 & rutastj-1 0
Cont ← Cont + 1
Rutasij ← clientek
k / d (clientek , Rutasij-1) = min [d(cliente, Rutasij-1)]
j / rutastj = 0 & rutastj-1 0
END
SI
NO
i ← 0
START
i ← i + 1
¿Cont = n?
SI ¿i = V?
NO
NO
SI
Proyecto Fin de Carrera | María Miranda Burguete
50 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
7) El cliente k, que presenta la máxima de las demandas entre los clientes aún
no asignados, se asigna a la ruta t que presenta la mínima capacidad
disponible que puede acomodar dicho cliente sin violar las restricciones del
problema. El cliente se introduce al final de la ruta t (tal y como indica el
puntero j) y el contador Cont incrementa su valor para indicar que el cliente
ha sido introducido con éxito. La capacidad de dicho vehículo es
actualizada.
8) El algoritmo continúa con la asignación de clientes. En la ruta marcada por
el puntero i se introduce el cliente k. Este último posee, entre los clientes aún
no asignados, la distancia mínima al cliente que ocupa la última posición de
la ruta i. El cliente se introduce al final de la ruta i (tal y como indica el
puntero j) y el contador Cont incrementa su valor para indicar que el cliente
ha sido introducido con éxito. La capacidad de dicho vehículo es
actualizada.
9) El algoritmo comprueba si todos los clientes han sido asignados a las rutas,
es decir, si el contador Cont ha alcanzado el valor n. En caso negativo el
diagrama retorna al paso 4 y continua la asignación de clientes. En caso
afirmativo el algoritmo ha alcanzado una solución admisible y finaliza.
5.2.2. Determinación de la solución inicial mediante la heurística de demanda
máxima
Cuando se tiene una flota heterogénea con un rango amplio de capacidades,
que incluye clientes con una demanda mucho mayor a la del resto, un método
de asegurar una solución inicial admisible es asignar los clientes atendiendo a la
demanda de los mismos. Con este objetivo se ha desarrollado esta segunda
heurística.
Tal y como se ha visto anteriormente, la heurística de mínima distancia asigna
los clientes a las rutas de la solución inicial según su proximidad al último
cliente introducido en las rutas. Asimismo, los primeros clientes en ser
introducidos en las rutas son los más cercanos al almacén.
Ahora bien, supóngase el caso en el que existieran múltiples clientes con
demanda muy próxima a la capacidad de cada uno de los vehículos, fueran
éstos los clientes más lejanos al almacén y al resto de clientes, y la capacidad
total de la flota de vehículos fuese muy próxima a la demanda total. En tal caso,
dichos clientes podrían requerir que un vehículo los visitara en exclusividad.
Sin embargo, su localización haría que no fuera una prioridad asignar dichos
clientes a las rutas. Dado que al llegar a la asignación de dichos clientes no
existirían rutas vacías capaces de acomodarlos, el método para la determinación
Proyecto Fin de Carrera | María Miranda Burguete
51 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
de la solución inicial por la heurística de mínima distancia sería incapaz de
converger a una solución admisible. Con el objetivo de garantizar una solución
inicial admisible se ha creado esta heurística de demanda máxima.
Considérese el siguiente ejemplo sencillo para ilustrar la situación descrita:
Una empresa dispone de tres camiones para satisfacer las demandas de sus clientes. La
capacidad de los camiones es 50, 50 y 25. La matriz de distancias y las demandas de los
clientes se indican a continuación.
d =
dem = (50 7 4 45)
Aplicando el algoritmo de búsqueda por mínima distancia, las rutas quedarían de la
siguiente manera:
Rutas=
Siendo las capacidades disponibles 0, 43 y 21 respectivamente.
El cliente cuatro no se asigna a ninguna ruta al finalizar el algoritmo, siendo esta por
tanto una solución no válida. Con el objetivo de evitar esta situación, se ha desarrollado
el segundo algoritmo de generación de la solución inicial.
El proceso seguido por esta nueva heurística es muy sencillo. En primer lugar
se ordenan los clientes en orden decreciente según las demandas exigidas.
Siguiendo este orden, la asignación de clientes se realiza uno a uno, empezando
por el cliente de mayor demanda. En cada caso, la ruta elegida para recibir
dicho cliente es la correspondiente al camión con mínima capacidad disponible
capaz de satisfacer la demanda requerida.
En la figura 13 se representa el diagrama de flujo correspondiente a la heurística
de demanda máxima. Las variables empleadas en el mismo son las siguientes:
El vector CS se emplea para almacenar los n clientes del VRP en orden
decreciente por la demanda característica de los mismos.
En contador Cont se emplea para recorrer el vector CS así como
confirmar que todos los clientes del VRP han sido asignados a las rutas
Proyecto Fin de Carrera | María Miranda Burguete
52 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
de los V vehículos disponibles.
La variable Rutas constituye una matriz donde se almacenan las rutas
asignadas a los V vehículos disponibles. El tratamiento de esta variable
coincide con el empleado en la heurística de mínima distancia.
El puntero i indica la ruta en la que se introduce el siguiente cliente que
se está considerando, es decir, la fila de la matriz Rutas donde se
almacena.
El puntero j se encarga de colocar cada cliente asignado a una ruta
inmediatamente después del último introducido. En otras palabras, este
puntero garantiza la ubicación de cada cliente en la correcta columna de
la matriz Rutas.
Cada vez que se añade un cliente a una ruta, se actualiza la capacidad
del vehículo correspondiente. La variable cap del diagrama se refiere a
la capacidad disponible en cada iteración para todos los vehículos.
El vector demanda, dem, contiene las demandas de todos los clientes del
problema.
La variable n representa el número total de clientes del VRP que deben
asignarse a las V rutas para alcanzar una solución inicial admisible.
Una vez descritas las variables que configuran el diagrama de flujo, es posible
detallar la lógica desarrollada por el mismo.
1) Inicio del algoritmo. Lectura de los datos: Localización y número de
clientes, demandas correspondientes, número de vehículos y capacidad de
los mismos.
2) Inicialización del contador Cont con valor unitario así como la inicialización
de la matriz Rutas de dimensiones [v x n] con ceros.
3) Los n clientes son almacenados en el vector CS en orden decreciente de sus
demandas.
4) El cliente que ocupa la posición indicada por el contador Cont dentro del
vector CS se asigna a la posición (i, j) de la matriz Rutas. La fila de la matriz o
ruta i es aquella correspondiente al vehículo con mínima capacidad
disponible que puede acomodar a dicho cliente. El puntero j garantiza que
el cliente se añade al final de la ruta i. A continuación, la capacidad de dicho
vehículo es actualizada.
Proyecto Fin de Carrera | María Miranda Burguete
53 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
Figura 13. Diagrama de flujo heurística de demanda máxima.
5) El algoritmo comprueba si se han asignado todos los clientes a las rutas, es
decir, si el contador Cont ha alcanzado el valor n. En caso negativo, se
incrementa el valor de Cont en una unidad y el algoritmo vuelve al paso 4.
En caso afirmativo, finaliza el algoritmo habiendo alcanzado una solución
admisible.
CS ← Clientez
z =1, … n
CS \ dem[CS(1)] ≥ dem[CS(2)] ≥ dem[CS(3)]… ≥ dem[CS(n)]
Datos
Rutasij ← CS(Cont);
i / capi = min(cap) & capi > dem[CS(Cont)];
j / rutasij = 0 & rutasij-1 0
END
START
¿Cont = n? NO
SI
Cont ← 1
Rutaslm ← 0,
l = 1,…,V ;m = 1,…,n
Cont ← Cont + 1
Proyecto Fin de Carrera | María Miranda Burguete
54 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
5.3. Operaciones
Como ya se ha mencionado con anterioridad en este documento, el algoritmo de
optimización ARF se basa en la aplicación de una serie de operaciones de búsqueda
local sobre una solución inicial admisible. En la sección anterior se han descrito las
heurísticas desarrolladas para alcanzar una solución inicial admisible. Previamente al
desarrollo en profundidad del ARF, en esta sección se discutirán las operaciones de
búsqueda local empleadas por el algoritmo desarrollado en este proyecto.
Tres de estas operaciones fueron estudiadas por Ho y Haugland [9] y son aplicadas
frecuentemente en la resolución del VRP debido a su simplicidad. Estas operaciones
aparecen en el trabajo realizado por Perosio y Zunino [13], quienes extienden su
estudio desarrollando nuevas operaciones propias, una de las cuales se ha incorporado
también a este proyecto. Como se explica en el apartado del Algoritmo por Ritmos del
Flamenco, cada operación lleva asignado un número del uno al cuatro, según la
distancia cronotónica ligada a ella. Las operaciones se numeran según la magnitud del
cambio que provocan en las rutas en cada iteración en caso exitoso. Así, la operación
uno realiza estadísticamente el movimiento más pequeño y la operación cuatro
modifica de manera más brusca la solución.
Las operaciones modifican la solución almacenada en una variable, que será la solución
inicial si el algoritmo se encuentra en su primera operación. El proceso iterativo de una
operación finaliza por uno de los siguientes motivos:
- Se han realizado todos los movimientos posibles sin encontrar una solución
mejor.
- Se ha encontrado una solución que proporciona una distancia total
recorrida menor a la última almacenada.
En el primer caso, el término del vector P correspondiente a la operación que ha
fracasado toma el valor uno, indicando que no se repetirá dicha operación mientras no
se modifique la solución almacenada.
Si ocurre el segundo caso, la nueva solución se introduce en la variable sustituyendo a
la solución que contenía hasta entonces, y todos los términos del vector P se actualizan
al valor cero, ya que al haberse modificado la solución, cualquier operación podría
proporcionar una mejora sobre la misma en la siguiente iteración.
A continuación se detallan las operaciones utilizadas, las cuales aparecen según la
numeración indicada anteriormente.
Proyecto Fin de Carrera | María Miranda Burguete
55 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
5.3.1. Relocate
Sean dos rutas Rk y Rl, esta operación mueve un cliente i de la ruta Rk, detrás del
cliente j de la ruta Rl. En este caso, se permite además que el cliente i se coloque
en la primera posición de la ruta Rl, es decir, se puede agregar como primer
destino de la ruta.
Se permite que k sea igual a l de manera que se pueden realizar cambios de
orden entre clientes de la misma ruta. Debido al procedimiento empleado para
la construcción de la solución inicial, en general, se espera que ésta tenga los
clientes ordenados de manera óptima dentro de cada ruta.
La operación Relocate mueve los clientes uno a uno y realiza todos los
movimientos posibles, en otras palabras, evalúa el cambio al colocar cada
cliente de la ruta k en cada una de las posiciones de la ruta l, introduciéndolo
finalmente en la posición que minimiza la distancia total recorrida.
Cuando la ruta Rk contiene un único cliente, al aplicar la operación Relocate de
manera exitosa esta ruta queda vacía. En la figura 14 se ilustra la ejecución de
Relocate.
Figura 14. Operación Relocate.
5.3.2. Exchange
Con esta operación se intercambian un cliente i de una ruta Rk y un cliente j de
la ruta Rl. Las posiciones a las que se mueven los clientes no tienen por qué ser
Proyecto Fin de Carrera | María Miranda Burguete
56 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
las mismas que las que ocupaban los clientes con los que son intercambiados.
Es decir, esta operación intercambia dos clientes entre rutas diferentes y evalúa
el efecto de colocar cada uno de estos en todas las posiciones de su nueva ruta,
eligiendo la mejor opción. La figura 15 ilustra esta operación.
Figura 15. Operación Exchange.
5.3.3. Merge_mod
Dadas dos rutas Rk y Rl, la operación trata de introducir el mayor número
posible de clientes de Rk en Rl. En otras palabras, esta operación buscará tomar
un número determinado de clientes de una ruta y desplazarlos al final de otra
ruta.
Dadas las características de este movimiento de clientes, Merge_mod podría
asemejarse a varias operaciones Relocate ejecutadas simultáneamente con la
única diferencia de que los clientes que se mueven se añaden al final de la ruta
Rl. La figura 16 ilustra esta nueva operación gráficamente.
Proyecto Fin de Carrera | María Miranda Burguete
57 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
Figura 16. Operación Merge_mod.
5.3.4. 2-Opt*
La operación 2-Opt* intercambia los finales de dos rutas. Sea una ruta Rk y una
ruta Rl, se introduce desde el cliente i+1 hasta el último cliente de Rk detrás del
cliente j de la ruta Rl. A la misma vez se introduce desde el cliente j+1 hasta el
último cliente de Rl detrás del cliente i de Rk. En la figura 16 se muestran los
movimientos que se realizan.
Figura 17. Operación 2-Opt*.
La operación 2-Opt* se ha definido de manera que se permite:
- Introducir los clientes de la ruta Rk al inicio de la ruta Rl. En este caso, en
Proyecto Fin de Carrera | María Miranda Burguete
58 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
lugar de colocar los clientes detrás del cliente j de Rl, se introducen
inmediatamente después del almacén.
- Mover un único cliente. Esto ocurre cuando el cliente i+1 de Rk y/o el
cliente j+1 de Rl es el último cliente de dicha ruta.
- Vaciar una ruta existente introduciendo todos sus clientes en otra ruta.
5.4. Algoritmo por Ritmos del Flamenco (ARF)
Una vez se ha alcanzado una solución inicial admisible que respeta todas las
condiciones de contorno, el ARF comienza una serie de rutinas que buscan optimizar la
función objetivo. En este apartado se describe por ello la ejecución del ARF asumiendo
que el algoritmo dispone de una solución inicial. A partir de esta última, el ARF
deberá:
1. Aplicar distintas operaciones que mediante determinados cambios en las rutas
de clientes del VRP, pertenecientes al conjunto de clientes C descrito en el
capítulo 4, sobre una solución almacenada, buscan una estimación de la
solución óptima. Como ya se ha visto con anterioridad, la solución del VRP
estudiado en este proyecto consiste en una serie de rutas correspondiente a
cada uno de los vehículos de reparto disponibles en las que los clientes
aparecen en el orden en el que son visitados por estos últimos. De esta manera,
las operaciones locales de optimización realizan movimientos en el orden en el
que los clientes del VRP están ubicados dentro de su ruta, la ruta y por tanto
vehículo al que pertenecen, o ambos al mismo tiempo. En otras palabras, mover
un cliente del VRP supone cambiar el orden en el que un vehículo visita al
mismo dentro de su ruta o el vehículo que deberá atender la demanda del
mismo.
2. Evaluar el cambio introducido en la función objetivo del VRP estudiado en este
proyecto para cada candidato a nueva solución después de cada movimiento
aplicado, es decir, la distancia total recorrida por la flota de vehículos.
3. Descartar el nuevo candidato a estimación óptima si la distancia total se ve
incrementada o actualizar el nuevo conjunto de rutas si se alcanza una mejora
al disminuir la distancia total. En este punto, tanto las rutas como la distancia
total son almacenadas en sendas variables, S* y d*, que contendrán durante
todo el proceso la mejor solución hallada hasta el momento.
Las dos últimas etapas del ARF descritas sobre estas líneas corresponden al proceso
iterativo de búsqueda por trayectoria. Así, se recorren los palos consecutivamente y se
aplican las operaciones en el orden en el que aparecen en los palos.
Una vez que el algoritmo inicia la búsqueda de una solución mejorada a través de una
Proyecto Fin de Carrera | María Miranda Burguete
59 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
operación, se realizan sucesivas iteraciones de la misma hasta encontrar una solución
mejor a la última almacenada en S*. En caso de no alcanzar dicha mejora tras completar
todos los posibles movimientos, el algoritmo abandona la operación sin almacenar
ninguna nueva solución. Este proceso se repite para todas las operaciones que
constituyen el palo analizado. Llegado este punto, si se ha introducido un cambio sobre
la solución almacenada, el ARF puede aplicar un palo diferente o repetir el palo usado
con anterioridad. El modo en el que se combinan los palos dentro del ARF requiere una
explicación más detallada por lo que se ha optado por dedicar una sección completa a
este tópico posteriormente en este documento.
Volvamos por tanto a considerar la aplicación aislada de un palo del flamenco a una
solución admisible. Para llevar a cabo el proceso de búsqueda, se codifica dicho palo
como un vector de ceros y unos. Este vector tendrá doce términos, que representan los
doce tiempos del compás. Los ceros corresponden a los tiempos sin acentuar y los unos
representan los acentos fuertes.
Al codificar los palos como vectores binarios, se consiguen dos propósitos esenciales
para la programación del algoritmo de búsqueda por ARF. En primer lugar, mediante
el simple uso de un contador, la identificación de los acentos y las distancias
cronotónicas entre los mismos es inmediata. Por otro lado, es posible ensamblar los
palos que se desean ejecutar de manera ordenada en una matriz de dimensiones
conocidas en la que, al recorrer las filas, los palos son aplicados guiando la búsqueda
por trayectorias.
Una vez se ha descrito la codificación de los palos en binario y la lógica que sostiene
esta solución, a continuación se representan los vectores asociados a los cinco palos
estudiados en este proyecto.
- Fandango: [0 0 1 0 0 1 0 0 1 0 0 1]
- Soleá: [0 1 0 0 1 0 1 0 1 0 1 1]
- Bulería: [0 1 0 0 0 1 1 0 1 0 1 1]
- Seguiriya: [0 1 0 1 0 0 1 0 0 1 0 1]
- Guajira: [0 0 1 0 0 1 0 1 0 1 0 1]
Los vectores forman una matriz [M] de dimensiones 5 x 12 que incluye los palos en el
orden que se van a leer durante la aplicación del algoritmo.
Además de la descripción completa de cómo cada uno de los palos del flamenco se
traduce en operaciones locales de búsqueda por trayectoria, la aplicación del ARF
requiere definir los siguientes elementos:
Proyecto Fin de Carrera | María Miranda Burguete
60 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
a) Palos del Flamenco a aplicar durante la ejecución
b) Orden en el que dichos palos se configuran para una iteración completa, esto
dará forma a las filas de la matriz M que contiene la codificación de los palos
c) Numero de iteraciones a ejecutar, es decir, el número de veces que las filas de la
matriz de palos son recorridas por el algoritmo.
Con el propósito de ilustrar el modo en el que el ARF es ejecutado, considérese la
siguiente configuración del problema:
a) Los cinco palos serán aplicados.
b) El orden de aplicación es:
1. Fandango
2. Soleá
3. Bulería
4. Seguiriya
5. Guajira
Por lo que la matriz [M] está definida como:
c) Se realizan un total de 10 iteraciones sobre la matriz de palos.
El orden definitivo de aplicación de los palos y el motivo de elección del mismo, que se
ha obtenido a partir de un estudio realizado con Matlab, se presenta en el apartado
7.1.4.
En la figura 18, a través de un diagrama de flujo, se ha representado el proceso de
aplicación del ARF para las asunciones descritas. En adición, los siguientes párrafos
incluyen una descripción en profundidad del mismo.
Los elementos que se han utilizado para definir el diagrama de flujo del ARF son:
Tres contadores:
o Contador A: Contiene el número de veces que se ha recorrido la matriz
Proyecto Fin de Carrera | María Miranda Burguete
61 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
M con los palos a ejecutar por el algoritmo. Para los datos considerados
en el caso ilustrado por el diagrama, es posible observar como al tomar
este contador un valor igual a 10, número de iteraciones elegidas, el
algoritmo finaliza. Para elegir un valor máximo para este contador, se ha
realizado un estudio de calibración que será descrito en un apartado
posterior.
o Contadores B y C: Se utilizan para leer la matriz de los palos flamencos
M. El contador B actúa como un puntero que recorre las columnas de la
matriz, mientras C se encarga de recorrer las filas.
El contador B se reinicia al llegar a doce indicando que se ha terminado
de leer un palo. El palo correspondiente se indica mediante el contador
C, que toma valores de uno a cinco, ya que la matriz M tiene 5 filas en
este caso. Cada vez que se reinicia B (termina de leerse un palo), se
incrementa C una unidad, indicando un cambio de palo que lleva al
algoritmo a la siguiente fila de la matriz M.
Cuando el contador B tomar un valor igual a 12 siendo el valor de C
igual a 5, ambos contadores se reinician y se incrementa en uno el
contador A. En ese momento, la matriz de palos ha sido recorrida por
completo, se han ejecutado las operaciones correspondientes a los palos
que la componen de manera ordenada y comienza una nueva iteración.
Variable D: En esta variable se almacena la distancia cronotónica
correspondiente a cada uno de los acentos fuertes dentro del palo que se está
recorriendo. O lo que es lo mismo, la variable D indica la posición en que se
encuentra un uno respecto al anterior. Se inicia con valor nulo al principio de
cada palo junto con el contador B y se incrementa de forma unitaria junto con
este último hasta que se detecta un acento.
Cuando el contador B identifica un acento en la representación binaria del palo
recorrido (la fila de la matriz M), es decir, el elemento correspondiente tiene el
valor uno, la variable D contiene la distancia cronotónica correspondiente y
dicta por tanto la operación de búsqueda local a realizar. Una vez el algoritmo
ARF entra en la operación de búsqueda local, la variable D vuelve a tomar un
valor nulo.
Vector P: Tal y como se ha descrito con anterioridad, el proceso de optimización
del ARF se basa en la aplicación de cuatro operaciones o movimientos sobre la
solución admisible actual. La selección de la misma viene determinada por la
distancia cronotónica entre acentos dentro de un palo.
El vector P es un vector de cuatro términos que representan las cuatro
operaciones diseñadas. Esta variable constituye un indicador temporal del éxito
o fracaso de las operaciones en alcanzar una mejora de la solución actual. La
Proyecto Fin de Carrera | María Miranda Burguete
62 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
intervención de dicho vector en el algoritmo puede describirse de la siguiente
manera:
Si al ejecutar una operación k no se encuentra una solución mejor a la última
almacenada, el término Pk toma el valor uno, indicando fracaso en la búsqueda.
En el caso de que una operación cualquiera mejore la solución, se le asigna el
valor cero a todos los términos del vector P. Al haberse modificado la solución
almacenada, todas las operaciones son de nuevo susceptibles de encontrar una
mejora.
El efecto de los valores de este vector durante el transcurso del algoritmo
principal, consiste en evitar la repetición de movimientos que en la iteración
anterior no dieron resultados favorables. Si en el momento de aplicar una
operación i el término Pi tiene valor uno, se continúa el algoritmo sin ejecutar
dicha operación, disminuyendo considerablemente el tiempo de ejecución.
Una vez se han descrito los componentes que están incluidos en el diagrama que
ilustra el algoritmo, en las siguientes líneas se describe de forma cronológica la
ejecución del mismo.
1) Inicio del algoritmo a partir de la solución inicial admisible.
2) Inicialización de los términos del vector P a cero, pues todas las operaciones
pueden generar una mejora sobre la solución de partida.
3) Almacenamiento de las rutas S0 así como la distancia total d0 correspondientes a
la solución inicial como mejor solución obtenida hasta el momento. Estos
valores se guardan en las variables S* y d* respectivamente.
4) Inicialización a cero del contador A.
5) Lectura de la matriz de Palos M.
6) Inicio del recorrido de la matriz de palos. El contador A toma entonces el valor
correspondiente a la iteración que se realiza sobre la matriz (i.e. 1 durante la
primera iteración) y se incrementa en cada iteración.
7) Se inicializa el contador C que recorre los palos, es decir, las filas de la matriz
M.
8) Se inicializa el contador B a cero ya que el algoritmo debe iniciar el recorrido de
un palo.
9) Comienza la lectura del siguiente palo y se incrementa el contador C.
Proyecto Fin de Carrera | María Miranda Burguete
63 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
START
Pi ← 0, i = 1,2,3,4
S* ← So
d* ← do
B ← 0
C ← C+1
D ← 0
A ← 0
A ← A + 1
[M]
Leer Matriz Palos
C ← 0
B ← B + 1
D ← D + 1
¿Fuerte?
SI
NO
Proyecto Fin de Carrera | María Miranda Burguete
64 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
Figura 18. Diagrama de flujo del ARF.
¿D = 1?
¿D = 2?
2-OPT
¿PD = 1? RELOCATE
¿PD = 1? EXCHANGE
¿PD = 1? MERGE
¿A = 10?
NO
SI
SI
NO
NO
SI
SI
SI
SI
NO
NO
NO
NO
NO
NO
SI
¿B = 12?
¿C = 5?
¿D = 3?
¿PD = 1?
SI
SI
END
SI
Proyecto Fin de Carrera | María Miranda Burguete
65 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
10) La variable D, a la espera de que se detecte el siguiente acento dentro del palo
se reinicia con valor nulo.
11) Inspección del siguiente elemento binario dentro de la codificación del palo
estudiado. Se incrementan el contador B y la variable D.
12) Comprobación de acento fuerte. El algoritmo debe preguntarse si el elemento
binario dentro de la codificación del palo es igual a uno, indicando un acento. Si
la respuesta es negativa, el algoritmo debe volver al paso 11. En caso positivo la
variable D identifica la operación que debe realizarse de forma que:
D = 1 Operación RELOCATE
D = 2 Operación EXCHANGE
D = 3 Operación MERGE_MOD
D = 4 Operación 2-Opt*
Antes de entrar en la subrutina que ejecuta cada operación, el algoritmo debe
preguntarse si se ha cambiado la solución almacenada desde la última vez que
se intentó dicha operación para evitar repeticiones redundantes. En otras
palabras, el elemento del vector P correspondiente a cada operación debe ser
inspeccionado y comprobar que su valor sea distinto de la unidad.
P(1) = 1 Previene la ejecución de la operación RELOCATE
P(2) = 1 Previene la ejecución de la operación EXCHANGE
P(3) = 1 Previene la ejecución de la operación MERGE_MOD
P(4) = 1 Previene la ejecución de la operación 2-Opt*
En caso de que la operación pueda realizarse, el algoritmo procede a ejecutar el
paso 13, en caso contrario se realiza el paso 14.
13) Bloque de subrutina operación. Para cualquiera de las cuatro operaciones y tal
y como se ha descrito previamente, este bloque contiene los siguientes pasos.
a) Generación de una nueva solución candidata tras aplicar una iteración de la
operación
b) Comprobación de mejora de la solución objetivo. En caso negativo se debe
realizar una nueva iteración de la operación, volviendo al paso a). Si
adicionalmente todas las posibles iteraciones han sido realizadas sin éxito,
pasar a d). En caso de mejora sobre la solución temporal, la subrutina
ejecuta el paso c).
c) La subrutina debe actualizar la solución S* con los nuevos valores y todos
los términos del vector P con valor nulo (cualquier operación es de nuevo
Proyecto Fin de Carrera | María Miranda Burguete
66 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
susceptible de alcanzar una mejora). En este punto la subrutina ha
finalizado.
d) El algoritmo hará que el término del vector P correspondiente a dicha
operación tome el valor 1 (indicando fracaso). La subrutina se da por
finalizada.
14) El algoritmo comprueba si la lectura del palo ha finalizado, es decir, si el
contador B ha tomado un valor igual a 12. En caso negativo, el algoritmo debe
volver al paso 10 en busca del siguiente acento. Si el palo ha finalizado, el
algoritmo pasa a 15.
15) El algoritmo comprueba si el palo que ha finalizado es el último de la matriz M,
es decir, el contador C toma el valor 5. En caso negativo el algoritmo debe
volver al paso 8 para recorrer el próximo palo. En caso positivo se pasa a 16.
16) Se comprueba a continuación si la matriz de palos ha sido recorrida un total de
10 veces, es decir, si el contador A toma dicho valor. En caso negativo el
algoritmo vuelve al paso 6 para recorrer la matriz M de nuevo. En caso
afirmativo se pasa a 17.
17) Fin del algoritmo ARF y extracción de la mejor solución obtenida.
Proyecto Fin de Carrera | María Miranda Burguete
67 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
6. IMPLEMENTACIÓN DEL ARF EN CÓDIGO MATLAB
En secciones anteriores de este documento se ha llevado a cabo una descripción
genérica del VRP, permitiendo su posterior particularización y descripción matemática
en términos de una función objetivo acompañada por múltiples restricciones que
acotan las posibles soluciones al problema que se plantea. A continuación se han
descrito los algoritmos generados para las heurísticas que permiten obtener una
solución inicial admisible, las operaciones de optimización por búsqueda local de
trayectorias y se ha finalizado con el desarrollo ilustrado de un caso particular del ARF.
La aplicación del ARF a casos particulares requiere la implementación de este método
sobre un lenguaje de programación. La complejidad y el carácter combinatorio de los
problemas VRP, prácticamente impone la necesidad de utilizar máquinas con alta
capacidad de cálculo para su resolución, incluso siendo ésta por la aplicación estimada
de métodos de búsqueda. En este Proyecto Fin de Carrera, se ha optado por la
implementación del ARF en lenguaje M empleando la herramienta Matlab. El objetivo
de este capítulo es ilustrar de manera ordenada el modo en el que dicha
implementación ha sido realizada.
En primer lugar, para la materialización de las operaciones descritas en los diagramas
de flujo que se recogen en el capítulo 5, de manera que la solución final se adhiera a las
restricciones del VRP objeto de estudio, deben definirse una serie de variables con
propiedades específicas. Estas últimas se describen en la primera sección de este
capítulo.
Anteriormente en este documento, se han definido dos heurísticas para la extracción de
una solución inicial admisible, cuatro operaciones de búsqueda local sobre las que se
fundamenta el algoritmo de optimización del ARF y un bloque final que describe el
desarrollo de este último. Esto permite que la partición del código a desarrollar en
módulos lo más independientes posibles pero a la vez interconectados sea una opción
más que recomendable para facilitar la compresión del mismo al lector.
Por esta razón, el segundo apartado de este capítulo se centra en la descripción de las
funciones creadas para implementar los diversos módulos que constituyen el código
completo, así como las interacciones y transferencias de variables que se producen
entre los mismos.
6.1. Parámetros y variables
Los datos del problema son importados desde un archivo Excel y se almacenan en
diferentes tipos de parámetros.
- dem: vector de longitud n donde se guardan las demandas de los clientes,
Proyecto Fin de Carrera | María Miranda Burguete
68 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
siendo n el número total de clientes a visitar.
- cap: vector de capacidad de longitud V (número de vehículos disponible)
que contiene los valores de capacidad de los camiones.
- x e y: la posición del almacén y los clientes se toma como un conjunto de
coordenadas 2D que se almacenan en dos vectores separados, uno para cada
eje.
- distancia: las distancias entre todos los nodos se calculan a partir de las
coordenadas dadas como dato y se guardan en una matriz de dimensiones
[n+1 x n+1]. El elemento distancia (i,j) de la matriz corresponde a la distancia
que hay entre el nodo i y el nodo j.
Esta matriz es simétrica, al considerarse la distancia entre dos nodos la
misma en ambos sentidos. La diagonal principal de la matriz tiene todos sus
elementos con valor infinito.
Además de estos parámetros, durante el algoritmo se utilizan otra serie de variables.
- rutas: la solución al problema consiste en un conjunto de rutas que
minimizan la distancia total recorrida por los vehículos. El conjunto de rutas
se almacena en una matriz de tamaño v x n. De esta manera, en un principio
se construye una matriz de ceros, y se va rellenando a medida que se
asignan clientes a las rutas en el proceso de generación de la solución inicial.
- d y d_mod: en la variable d se introduce el valor de la distancia total
recorrida en el mejor de los casos obtenidos hasta el momento, y en la
variable d_mod se guarda la distancia recorrida en la iteración actual, dentro
de la función de cada operación. En cada iteración se comparan los valores
de ambas variables.
- r: se trata de una variable de salida de las funciones de las operaciones. Si
tras aplicar una operación se obtiene una mejora sobre la solución
almacenada en la variable rutas, el algoritmo se sale de la función de dicha
operación con este nuevo conjunto de rutas almacenado en r. Si por el
contrario se realizan todas las iteraciones posibles de la operación sin
conseguir mejorar la solución, la función devuelve la variable r igual a 1.
El algoritmo analiza el valor de r cada vez que termina de ejecutar una
operación. Si el valor de la variable es igual a 1, no modifica la variable
rutas. Si el valor de r es distinto de 1 indicando que la aplicación de la
operación sobre la solución almacenada ha supuesto una mejora de la
misma, esta nueva solución (contenida en r) se guarda en rutas,
sustituyendo la última solución almacenada.
- P: vector de ceros y unos de longitud igual al número de operaciones. El uso
Proyecto Fin de Carrera | María Miranda Burguete
69 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
y la finalidad del vector P se describe detalladamente en el apartado 5.4.
6.2. Archivos y funciones
Se utilizan diferentes archivos y funciones en el proceso de implementación:
- P_general:
Sintaxis: P_general.m
Definición: Este archivo ejecutable se encarga de aplicar el algoritmo ARF completo y llama a las funciones que se describen en esta sección siguiendo la lógica descrita en el capítulo 5 de este documento.
Input: Esta función no recibe ninguna variable de entrada. Sin embargo, requiere la existencia de un archivo Excel del que leerá los datos de entrada del problema, es decir, el número de vehículos disponibles, el número de clientes, la localización de los nodos, la capacidad de los vehículos y las demandas de cada uno de los clientes.
En adición, este archivo demandará al usuario la especificación de la heurística deseada para generar la solución inicial, los palos del flamenco que se desea ejecutar (codificados en binario de acuerdo a las distancias cronotónicas) así como el orden y número de iteraciones para la secuencia de palos especificada.
Output: Una vez leídos los datos iniciales completos, este archivo calcula las distancias entre todos los nodos basándose en sus localizaciones en un plano de coordenadas x e y. Cuando las distancias son conocidas, se ejecuta la heurística de solución inicial deseada.
En caso de optar por la heurística de mínima distancia y fracasar esta última en la generación de una solución inicial admisible, el archivo ejecutara la heurística de máxima demanda para garantizar la existencia de una solución inicial acorde a las restricciones del problema.
A partir de la solución inicial y la secuencia de palos deseada, el archivo ejecuta el ARF completo y proporciona al usuario la estimación de la solución óptima alcanzada junto con la distancia total recorrida por los vehículos en dicha configuración de rutas.
- Sol_inicial_r:
Sintaxis:
Function [matriz int, vector int]=sol_inicial_r(vector int, vector int, int, int, matriz int)
Proyecto Fin de Carrera | María Miranda Burguete
70 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
Function [rutas, cap]=sol_inicial_r(dem, cap, n, v, distancia)
Definición: Esta es una función que incorpora el algoritmo de generación de la solución inicial por la heurística de demanda máxima.
Input: Recibe como variables de entrada, en orden, el vector con las demandas de los clientes, la capacidad de cada uno de los vehículos, el número de clientes, el número de vehículos disponibles y la matriz de distancias entre los clientes y el almacén.
Output: Esta función proporciona, en orden, la matriz que contiene las rutas creadas por la heurística de máxima demanda y las capacidades residuales de cada uno de los vehículos.
- Sol_inicial_val:
Sintaxis:
Function [matriz int, vector int]=sol_inicial(vector int , vector int, int, int, matriz int)
Function [rutas, cap]=sol_inicial_r(dem, cap, n, v, distancia)
Definición: Esta es una función que incorpora el algoritmo de generación de la solución inicial por la heurística de mínima distancia.
Input: Ídem a la función Sol_inicial_r.
Output: Ídem a la función Sol_inicial_r.
- Calculadist:
Sintaxis:
Function [int]=calculadist(int, int, matriz int, matriz int)
Function [d]=calculadist(n, v, rutas, distancia)
Definición: Esta función calcula la distancia total recorrida por los vehículos en una configuración determinada de rutas.
Input: Como datos de entrada a la función se toman el número total de
clientes, el número de vehículos, las distancias entre todos los nodos y el
conjunto de rutas que conforman la solución que se desea evaluar.
Output: La función proporciona el valor de distancia total recorrida por la flota de vehículos.
Proyecto Fin de Carrera | María Miranda Burguete
71 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
- Opuno:
Sintaxis:
Function [matriz int, vector int, vector int]= opuno(matriz int, vector int, vector int, int, int, matriz int, vector int)
Function [r, P, cap]=opuno(rutas, dem, cap, n, v, distancia, P)
Definición: Esta función ejecuta la operación RELOCATE en busca de una mejora sobre la solución almacenada. Como ya se ha descrito con anterioridad, la función trata de encontrar una mejora aplicando el movimiento impuesto por RELOCATE. Al alcanzar una mejora, toma esta como la nueva solución y termina su ejecución. En caso de no alcanzar mejora, la función devolverá las mismas rutas recibidas como entrada.
En otras palabras, la función va realizando todos los movimientos posibles y en cada paso compara la distancia recorrida con la solución obtenida con la distancia recorrida con la solución almacenada. En el caso de que la primera sea menor, almacena esta solución en S* como la mejor solución hallada hasta el momento y sale de la función.
Input: Esta función recibe como entrada las rutas de los V vehículos
disponibles recogidas en una matriz almacenada en S*, el vector de
demandas de los clientes, el vector de capacidades residuales de cada
vehículo, el número de clientes, el número de vehículos, la matriz de
distancias entre nodos y el vector P que indica el éxito o fracaso previo
de cada operación. La función de este último vector fue definida en el
capítulo 5 de este documento.
Output: La función devuelve la matriz de rutas actualizada tras realizar los cambios si estos han sido posibles (la matriz inalterada de entrada en caso de fracaso), las capacidades residuales de los vehículos y el vector P actualizado de acuerdo con el resultado de la operación.
- Opdos:
Sintaxis:
Function [matriz int, vector int, vector int]= opdos(matriz int, vector int, vector int, int, int, matriz int, vector int)
Function [r, P, cap]=opdos(rutas, dem, cap, n, v, distancia, P)
Definición: Esta función ejecuta la operación EXCHANGE en busca de una mejora sobre la solución almacenada. La lógica aplicada para finalizar la ejecución de esta función es idéntica a lo que se ha descrito ya para la operación RELOCATE.
Proyecto Fin de Carrera | María Miranda Burguete
72 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
Input: Ídem a la función Opuno.
Output: Ídem a la función Opuno.
- Optres:
Sintaxis:
Function [matriz int, vector int, vector int]= optres(matriz int, vector int, vector int, int, int, matriz int, vector int)
Function [r, P, cap]=optres(rutas, dem, cap, n, v, distancia, P)
Definición: Esta función ejecuta la operación MERGE_MOD en busca de una mejora sobre la solución almacenada. La lógica aplicada para finalizar la ejecución de esta función es idéntica a lo que se ha descrito ya para las operaciones anteriores.
Input: Ídem a la función Opuno.
Output: Ídem a la función Opuno.
- Opcuatro:
Sintaxis:
Function [matriz int, vector int, vector int]= opcuatro(matriz int, vector int, vector int, int, int, matriz int, vector int)
Function [r, P, cap]=opcuatro(rutas, dem, cap, n, v, distancia, P)
Definición: Esta función ejecuta la operación 2-Opt* en busca de una mejora sobre la solución almacenada. La lógica aplicada para finalizar la ejecución de esta función es idéntica a lo que se ha descrito ya para las operaciones anteriores.
Input: Ídem a la función Opuno.
Output: Ídem a la función Opuno.
Proyecto Fin de Carrera | María Miranda Burguete
73 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
7. RESULTADOS DE LA APLICACIÓN DEL ALGORITMO ARF
En este capítulo se describe la aplicación del algoritmo ARF a casos particulares del
problema de enrutado de vehículos a través de dos secciones. En un primer apartado
se define una Red de Prueba aleatoria con un número reducido de nodos. El propósito
de introducir una red simplificada es describir de una manera más intuitiva el proceso
seguido por el algoritmo para alcanzar una solución inicial, así como en la aplicación
de movimientos de búsqueda local. Sobre dicha red también se realizará una discusión
del efecto que provoca la variación de diferentes parámetros del algoritmo en la
solución obtenida.
Disponer de una Red de Prueba permitirá clarificar sobre ella la metodología descrita
en el capítulo 5 de esta memoria. Así, se compararán las dos heurísticas creadas para la
generación de una solución inicial, la habilidad de cada uno de los movimientos de
búsqueda local para mejorar la solución actual en una sola iteración y la efectividad de
cada uno de los palos del flamenco considerados.
La sección dedicada a esta Red de Prueba continuará con un estudio de sensibilidad
del efecto que produce el orden en que se aplican los palos en el algoritmo ARF sobre
la solución óptima estimada. De dicho estudio se obtendrá el orden definitivo de los
palos que completa la definición del ARF, retomando la metodología desarrollada en el
capítulo 5. La sección culminará con la descripción de la solución alcanzada con la
versión final del algoritmo sobre la red simplificada.
La segunda sección de este capítulo se centrará en la resolución del problema de
enrutado de vehículos resuelto por Rafael Grosso [6].En este último trabajo se aplica un
método de búsqueda Tabú para la solución del problema, los resultados obtenidos en
R. Grosso [6] se compararán con los proporcionados por el algoritmo ARF para probar
la eficacia del método diseñado.
7.1. Implementación en una Red de Prueba
Con el objetivo de probar el correcto funcionamiento del algoritmo diseñado, en este
apartado se desarrolla la resolución de un caso simplificado del problema de enrutado
de vehículos. La red descrita permitirá además apreciar el funcionamiento del
algoritmo paso a paso a través de las diferentes iteraciones del mismo.
La red que define el problema de ejemplo está compuesta por 16 nodos,
correspondientes al almacén y a los clientes, y por los arcos que unen estos nodos. En
este problema el número de clientes, n, es por tanto igual a 15 y el número de
vehículos, V, es igual a 4. La capacidad de cada vehículo se asume igual a 100 unidades
de producto a distribuir.
Proyecto Fin de Carrera | María Miranda Burguete
74 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
En la figura 19 se muestra la representación grafica de la red que describe este
problema simplificado. Otra condición inicial esencial para este problema es que todos
los nodos están unidos por arcos que pueden recorrerse en ambos sentidos, sin
embargo, estos arcos no se han representado para dar mayor claridad al dibujo. Es
decir, es un grafo completamente conexo accediéndose desde cualquier nodo a
cualquier otro a través de un arco bidireccional.
Continuando con la descripción de la figura 19, cada nodo es identificado por un
número a la derecha del mismo. El almacén, nodo 0, se representa con un cuadrado
mientras los clientes quedan localizados por círculos de diversos colores. Situados por
debajo de cada nodo, los valores entre paréntesis representan las coordenadas (x,y) de
localización en unidades de distancia referidas al almacén , que se toma como origen
de coordenadas.
Otro elemento necesario para la definición del problema son las demandas de los
clientes, que se muestran a continuación en la tabla 11 en unidades de producto.
Tabla 11. Demandas de los clientes de la Red de Prueba.
Núm. cliente 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Demanda 10 16 21 12 10 8 19 12 16 5 6 10 28 22 25
Figura 19. Red de Prueba.
Proyecto Fin de Carrera | María Miranda Burguete
75 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
Una vez los elementos que conforman este caso simplificado han sido expuestos, los
siguientes apartados se centran en la definición de una solución inicial, la posterior
aplicación del algoritmo elaborado en este proyecto, un estudio de sensibilidad al
cambio en el orden de aplicación de los palos, la elección del orden que genera la
solución de mínima distancia y la discusión de la misma.
7.1.1. Solución inicial
La aplicación del ARF a la Red de Prueba previamente definida requiere la
obtención de una solución inicial sobre la que aplicar las iteraciones del
algoritmo.
En esta sección se va a describir paso a paso la generación de una solución
inicial mediante el uso de las dos heurísticas desarrolladas para ello y
detalladas en el capítulo 5. En primer lugar se aplicará la heurística de mínima
distancia, seguida de la heurística por demanda máxima.
7.1.1.1. Solución inicial mediante la aplicación de la heurística de mínima
distancia
Para obtener la solución inicial mediante esta heurística se deben seguir los
siguientes pasos. Primero, se calcula la distancia de todos los clientes al
almacén y se ordenan las mismas en orden creciente. Recuérdese que la
distancia entre dos nodos es la raíz cuadrada de la suma de los cuadrados de
las diferencias entre las coordenadas x e y de dichos puntos.
Tabla 12. Distancias de los clientes al almacén en orden de cercanía y demandas características de la Red de Prueba.
Núm. cliente 8 4 7 11 12 13 10 3 5 2 6 9 15 1 14
Distancia al
almacén 9.0 9.2 9.5 11.2 12.2 13.0 14.8 14.9 17.2 17.7 18.4 19.3 20.8 25.8 27.6
Demanda 12 12 19 6 10 28 5 21 10 16 8 16 25 10 22
De esta lista se toma el cliente más cercano al almacén y se asigna a la primera
ruta, siempre que la capacidad del vehículo correspondiente permita satisfacer
la demanda de dicho cliente. Puesto que en este caso se cumple la restricción
de capacidad, el cliente 8 se incorpora a la ruta número uno. De la misma
forma, los siguientes clientes de la tabla 12 se incluyen en las demás rutas,
repitiendo este proceso V veces hasta que todas las rutas posean un cliente.
Las rutas quedan hasta el momento tal y como se muestra en la tabla 13,
Proyecto Fin de Carrera | María Miranda Burguete
76 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
mientras que las capacidades residuales se incluyen en la tabla 14.
Tabla 13. Solución inicial parcial sobre la Red de Prueba por la heurística de mínima distancia tras añadir cuatro clientes.
Vehículo
1
2
3
4
Clientes
8
4
7
11
El siguiente paso es asignar a la ruta uno el cliente más cercano al último
cliente incluido en la misma, en este caso el cliente número 8. Para ello, se
obtienen las distancias entre los clientes aún no asignados y este cliente. Estas
distancias se recogen en la tabla 15, en la cual puede comprobarse que el
cliente más cercano al cliente 8 es el cliente número 13, cuya demanda queda
cubierta por la capacidad disponible asociada a la ruta uno.
Tabla 14. Capacidades disponibles tras asignar los cuatro primeros clientes en la solución inicial sobre la Red de Prueba.
Núm. ruta 1 2 3 4
Capacidad disponible 88 88 81 94
Tabla 15. Distancias de los clientes aún no asignados al cliente 8 en orden de cercanía y sus demandas en la Red de Prueba.
Núm. cliente 13 12 5 15 3 10 2 6 9 1 14
Distancia al cliente 8 5.8 10.2 14.0 17.3 19.8 23.1 25.1 27.3 27.9 33.5 34.4
Demanda 28 10 10 25 21 5 16 8 16 10 22
En la tabla 16 se muestra el estado de las rutas tras la adición del cliente
número 13 a la primera ruta, inmediatamente después del cliente 8.
En las siguientes iteraciones se repite el proceso para las rutas v=2, 3 y
finalmente 4. Las tablas 17 a 25 describen paso a paso el proceso de asignación
del siguiente cliente a cada ruta de manera que las V rutas poseen dos clientes
cada una.
Proyecto Fin de Carrera | María Miranda Burguete
77 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
Tabla 16. Solución inicial parcial por la heurística de mínima distancia sobre la Red de Prueba tras añadir el quinto cliente.
Vehículo
1
2
3
4
Clientes
8 13
4
7
11
Tabla 17. Capacidades disponibles tras asignar el quinto cliente en la solución inicial sobre la Red de Prueba.
Núm. ruta 1 2 3 4
Capacidad disponible 60 88 81 94
Tabla 18. Distancias de los clientes aún no asignados al cliente 4 en orden de cercanía y sus demandas en la Red de Prueba.
Núm. cliente 3 5 2 12 6 10 1 9 15 14
Distancia al cliente 4 8.6 9.4 15.3 19.6 20.6 21.9 23.8 25.6 27.9 35.8
Demanda 21 10 16 10 8 5 10 16 25 22
Tabla 19. Solución inicial parcial por la heurística de mínima distancia sobre la Red de Prueba tras añadir el sexto cliente.
Vehículo
1
2
3
4
Clientes
8 13
4 3
7
11
Tabla 20. Capacidades disponibles tras asignar el sexto cliente en la solución inicial sobre la Red de Prueba.
Núm. ruta 1 2 3 4
Capacidad disponible 60 67 81 94
Proyecto Fin de Carrera | María Miranda Burguete
78 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
Tabla 21. Distancias de los clientes aún no asignados al cliente 5 en orden de cercanía y sus demandas en la Red de Prueba.
Núm. cliente 6 2 10 9 1 12 5 14 15
Distancia al cliente 7 9.1 9.8 10.8 13.5 17.0 20.6 22.0 25.1 29.0
Demanda 8 16 5 16 10 10 10 22 25
Tabla 22. Solución inicial parcial por la heurística de mínima distancia sobre la Red de Prueba tras añadir el séptimo cliente.
Vehículo
1
2
3
4
Clientes
8 13
4 3
7 6
11
Tabla 23. Capacidades disponibles tras asignar el séptimo cliente en la solución inicial sobre la Red de Prueba.
Núm. ruta 1 2 3 4
Capacidad disponible 60 67 73 94
Tabla 24. Distancias de los clientes aún no asignados al cliente 11 en orden de cercanía y sus demandas en la Red de Prueba.
Núm. cliente 10 12 9 14 15 2 5 1
Distancia al cliente 11 8.6 12.0 13.3 17.2 18.4 23.4 28.3 29.7
Demanda 5 10 16 22 25 16 10 10
Tabla 25. Solución inicial parcial por la heurística de mínima distancia sobre la Red de Prueba tras añadir el octavo cliente.
Vehículo
1
2
3
4
Clientes
8 13
4 3
7 6
11 10
Proyecto Fin de Carrera | María Miranda Burguete
79 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
Una vez realizadas estas iteraciones, se vuelve a repetir el proceso
comenzando por la primera ruta. De nuevo se busca el cliente más cercano al
último cliente incluido en la ruta que aún no haya sido asignado.
Empezando por la ruta uno, se ordenan de nuevo los clientes aun no
asignados en orden creciente de distancia al cliente 13. Siguiendo el
procedimiento descrito, las últimas iteraciones son aquellas descritas en las
tablas 26 a 29.
Tabla 26. Solución inicial parcial por la heurística de mínima distancia sobre la Red de Prueba tras añadir los trece primeros clientes.
Vehículo
1
2
3
4
Clientes
8 13 12 15
4 3 2
7 6 9
11 10 14
Tabla 27. Capacidades disponibles tras asignar los primeros trece clientes a la solución inicial sobre la Red de Prueba.
Núm. ruta 1 2 3 4
Capacidad disponible 25 51 57 67
Tabla 28. Distancias de los clientes aún no asignados al cliente 2 en orden de cercanía y sus demandas en la Red de Prueba.
Núm. cliente 1 5
Distancia al cliente 2 8.5 23.1
Demanda 10 10
Tabla 29. Solución inicial por la heurística de mínima distancia sobre la Red de Prueba.
Vehículo
1
2
3
4
Clientes
8 13 12 15
4 3 2 1
7 6 9 5
11 10 14
Proyecto Fin de Carrera | María Miranda Burguete
80 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
En cada iteración del algoritmo, es decir, cada vez que se busca un nuevo
cliente para asignar a una ruta concreta, se debe analizar si alguno de los
clientes aún sin asignar tiene una demanda considerablemente grande en
relación a las capacidades disponibles de los vehículos. En caso afirmativo,
dicho cliente se incorpora a la ruta con menor capacidad disponible capaz de
cubrir su demanda.
En este caso, todos los vehículos tienen una capacidad igual a 100, valor muy
por encima de los valores de las demandas de los clientes, que oscilan entre 5
y 28 unidades. Además, la mayor parte de los clientes demandan menos de 20
unidades. Es por ello, que al aplicar el algoritmo sobre esta Red de Prueba, no
se da la situación explicada en el párrafo anterior y no es necesario corregir el
comportamiento sistemático del mismo.
Supóngase para esta misma Red de Prueba, que la demanda del cliente
número 1 tuviera un valor igual a 60. Los primeros clientes asignados por el
algoritmo de generación de solución inicial son en este caso los mismos que
los representados anteriormente. Cuando el cliente 14 se incluye en la ruta
cuarta, la capacidad disponible del cuarto vehículo, que durante todo el
proceso se ha mantenido como la máxima capacidad disponible, pasa a tener
un valor de 67 unidades. En la tablas 30 a 32 se muestran las rutas hasta el
momento, las capacidades disponibles de los vehículos y las demandas de los
clientes que aún no han sido asignados.
Tabla 30. Solución inicial parcial tras asignar los doce primeros clientes a la solución inicial sobre la Red de Prueba. Caso 2.
Vehículo
1
2
3
4
Clientes
8 13 12
4 3 2
7 6 9
11 10 14
Tabla 31. Capacidades disponibles tras asignar los primeros doce clientes a la solución inicial sobre la Red de Prueba. Caso 2.
Núm. ruta 1 2 3 4
Capacidad disponible 50 51 57 67
Proyecto Fin de Carrera | María Miranda Burguete
81 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
Tabla 32. Demandas de los clientes no asignados en la Red de Prueba. Caso 2.
Núm. cliente 1 5 15
Demanda 60 10 25
En este momento, cuando el algoritmo analiza las demandas de los clientes no
asignados antes de realizar la siguiente iteración, descubre que la demanda
del cliente 1 es considerablemente grande y debe incluir este cliente en alguna
de las rutas antes de seguir con el procedimiento nominal del algoritmo.
X = Máxima capacidad disponible = 67
Y = Segunda mayor demanda de los clientes no asignados = 25
Z = Máxima demanda de los clientes no asignados = 60
Al cumplirse la desigualdad X – Y < Z, se hace una pausa en las iteraciones y
el cliente cuya demanda es máxima se introduce en la ruta con menor
capacidad disponible capaz de satisfacer la demanda. En este caso, el cliente 1
se introduce en la cuarta ruta.
Tabla 33. Solución inicial parcial tras asignar el treceavo cliente a la solución inicial sobre la Red de Prueba. Caso 2.
Vehículo
1
2
3
4
Clientes
8 13 12
4 3 2
7 6 9
11 10 14 1
Una vez asignado el cliente conflictivo, se realiza la misma pregunta de nuevo
y se prosigue con el procedimiento sistemático.
Al no haber más clientes con grandes valores de demanda, se continúan las
iteraciones con normalidad. En el momento anterior a introducir el cliente
número 1, las iteraciones se habían parado en la primera ruta. Se busca por
tanto un cliente para incluirlo en la ruta número 1. La tabla 34 recoge las
distancias entre los clientes no asignados y el cliente número 12 en orden
creciente.
Proyecto Fin de Carrera | María Miranda Burguete
82 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
Tabla 34. Distancias de los clientes aún no asignados al cliente 12 en orden de cercanía y sus demandas en la Red de Prueba. Caso 2.
Núm. cliente 15 5
Distancia al cliente 12 8.6 24.2
Demanda 25 10
Finalmente, las rutas completas en el caso de existir el cliente conflictivo (caso
2) se muestran en la tabla 35.
Tabla 35. Solución inicial por la heurística de mínima distancia sobre la Red de Prueba. Caso 2.
Vehículo
1
2
3
4
Clientes
8 13 12 15
4 3 2 5
7 6 9
11 10 14 1
Volviendo a la Red de Prueba original, la solución inicial obtenida por la
heurística de mínima distancia se representa en la figura 20. Así mismo, en la
figura 21 es posible apreciar los cambios en las rutas iniciales que serían
causados por un incremento en la demanda del cliente 1 hasta 60 unidades.
Atendiendo a la figura 20, puede observarse que este algoritmo asigna los V
clientes más cercanos al almacén al comienzo de las V rutas, donde V es el
número total de vehículos disponibles. De igual forma, por orden de rutas,
puede observarse como se han ido añadiendo a cada ruta los clientes más
cercanos al último destino en cada paso de las iteraciones. Una consecuencia
directa de la aplicación de este método es que los clientes más alejados (1, 5, 14
y 15) del almacén son los últimos en ser asignados y cierran cada una de las
rutas iniciales.
Una vez conocida una solución admisible inicial que cumple todos los
requisitos del problema, es posible computar la distancia total recorrida por
los vehículos. Dicho valor resulta ser igual a 255.1073 unidades de distancia.
Proyecto Fin de Carrera | María Miranda Burguete
83 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
Figura 20. Solución inicial por la heurística de mínima distancia sobre la Red de Prueba.
Figura 21. Solución inicial por la heurística de mínima distancia sobre la Red de Prueba. Caso 2.
Proyecto Fin de Carrera | María Miranda Burguete
84 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
7.1.1.2. Solución inicial mediante aplicación de la heurística de demanda
máxima
La heurística de demanda máxima, asigna en cada iteración el cliente con
mayor demanda a la ruta con mínima capacidad disponible que puede cubrir
la demanda del cliente. Por tanto, el primer paso para su ejecución es ordenar
los clientes en orden decreciente de demanda. La tabla 36 recoge las demandas
en orden decreciente, así como los números de cliente asociados a éstas.
Tabla 36. Demandas de los clientes de la Red de Prueba en orden decreciente.
Núm. cliente 13 15 14 3 7 2 9 4 8 1 5 12 6 11 10
Demanda 28 25 22 21 19 16 16 12 12 10 10 10 8 6 5
En primer lugar, se asigna el cliente número 13 a la primera ruta. Como el
lector puede haber intuido en este momento, en el caso de que varias rutas
sean candidatas para incorporar el cliente a asignar, por tener la misma
capacidad disponible, éste se introduce en la primera de ellas. Igualmente,
cuando varios clientes tienen la misma demanda, el orden de asignación se
rige por el número de cliente, independientemente de su localización.
En la tabla 37 se recogen las capacidades residuales tras esta primera
asignación. El segundo cliente con mayor demanda es el cliente 15. Este se
introducirá en la primera ruta debido a que esta se convierte en la ruta con
mínima capacidad disponible tras haberle sido asignado el cliente 13.
Tabla 37. Capacidades disponibles tras asignar el primer cliente a la solución inicial por la heurística de demanda máxima sobre la Red de Prueba.
Núm. ruta 1 2 3 4
Capacidad disponible 72 100 100 100
Del mismo modo se introducen los clientes 14 y 3 en la primera ruta. Las
capacidades de los vehículos y las rutas hasta el momento se recogen en las
tablas 38 y 39.
Tabla 38. Capacidades disponibles tras asignar los cuatro primeros clientes a la solución inicial por la heurística de demanda máxima sobre la Red de Prueba.
Núm. ruta 1 2 3 4
Capacidad disponible 4 100 100 100
Proyecto Fin de Carrera | María Miranda Burguete
85 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
Tabla 39. Solución inicial parcial sobre la Red de Prueba tras asignar los cuatro primeros clientes por la heurística de demanda máxima.
El cliente no asignado con máxima demanda es ahora el cliente número 7,
cuya demanda es igual a 19 unidades. Este cliente se introduce en la segunda
ruta, seguido de los clientes 2, 9, 4, 8, 1 y 5. La capacidad del vehículo dos pasa
a tener un valor de 5 unidades y el siguiente cliente a asignar es el cliente
número 12, con una demanda de 10 unidades, por tanto, este cliente se
introduce en la ruta tres.
Las tablas 40 a 42 muestran el estado actual de la solución inicial y de los
parámetros residuales del problema.
Tabla 40. Solución inicial parcial sobre la Red de Prueba tras asignar los primeros doce clientes a la solución inicial por la heurística de demanda máxima.
Tabla 41. Capacidades disponibles tras haber asignado los doce primeros clientes a la solución inicial por la heurística de demanda máxima sobre la Red de Prueba.
Núm. ruta 1 2 3 4
Capacidad disponible 4 5 90 100
Tabla 42. Demandas de los tres clientes aún no asignados por la heurística de demanda máxima en la Red de Prueba.
Núm. cliente 6 11 10
Demanda 8 6 5
Vehículo
1
2
3
4
Clientes
13 15 14 3
Vehículo
1
2
3
4
Clientes
13 15 14 3
7 2 9 4 8 1 5
12
-
Proyecto Fin de Carrera | María Miranda Burguete
86 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
Los clientes 6 y 11 se introducen en la tercera ruta, mientras que el último
cliente, el cliente número 10, se añade a la segunda ruta, por ser la ruta con
mínima capacidad capaz de cubrir su demanda.
La solución inicial proporcionada por la heurística de demanda máxima es por
tanto la mostrada en la tabla 43 y se ilustra mediante la figura 22.
Tabla 43. Solución inicial por la heurística de demanda máxima sobre la Red de Prueba.
Figura 22. Solución inicial por la heurística de demanda máxima sobre la Red de Prueba.
La distancia total recorrida es ahora 365.3890 unidades de distancia, cuyo
valor es considerablemente mayor al alcanzado con el primer método. No
obstante, se debe tener en cuenta que esta heurística fue diseñada con el
objetivo de resolver aquellos casos para los cuales la heurística de distancia
Vehículo
1
2
3
4
Clientes
13 15 14 3
7 2 9 4 8 1 5 10
12 6 11
-
Proyecto Fin de Carrera | María Miranda Burguete
87 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
mínima no resulte válida, garantizando que se pueda alcanzar una solución
inicial también para esos casos desfavorables. Así, este resultado permite
constatar que esta heurística sacrifica la condición de distancia mínima para
asegurar la obtención de una solución admisible inicial.
Adicionalmente, esta nueva solución inicial ha generado una ruta vacía o lo
que es equivalente, un vehículo inoperativo. Dado que para los objetivos de
este trabajo no se han considerado implicaciones de coste en el número de
vehículos activos, no es preciso discutir posibles ventajas o desventajas de esta
condición, ya que la distancia a recorrer es el único criterio para la solución
deseada.
A continuación, tal y como se indica al inicio del capítulo, primero se realizará
un estudio del algoritmo ARF sobre la Red de Prueba descrita anteriormente
junto con un estudio de sensibilidad de la solución al orden de aplicación de
los palos del flamenco considerados. Una vez definido el algoritmo completo
con un orden fijo para los palos, se utilizará para resolver un problema
determinado. Mientras la heurística de mínima distancia resulte válida para
obtener una solución inicial, como en el caso de la red simplificada, será esta
heurística la que se utilizará en las sucesivas aplicaciones del ARF.
7.1.2. Aplicación aislada de las operaciones de búsqueda
La obtención de una solución inicial no solo habilita al analista para el inicio de
un proceso de optimización sino que también, partiendo de ella, permite la
comparación sobre la Red de Prueba de las operaciones que componen el
algoritmo. Por lo tanto, en este apartado se comprueba por separado la eficacia
de las operaciones y las modificaciones que estas introducen, utilizándolas por
separado como heurísticas de resolución del problema VRP de forma
independiente.
Para este estudio, se realiza con cada operación todos los posibles movimientos
y se toma aquel que produce la mayor mejora sobre la solución inicial, es decir,
se toma el mejor resultado posible con una sola iteración de cada operación.
Por tanto, en esta apartado en lugar de tomarse la primera combinación que en
cada movimiento genera una mejora sobre la solución inicial, una vez se han
revisado todas las posibles combinaciones alcanzables por medio de dicha
operación, se almacena la mejor de todas estas. Los resultados alcanzados y el
tiempo de ejecución empleado en cada una se utilizan para comparar las
operaciones entre sí.
Para la obtención de estos valores se ha empleado un equipo informático con
procesador Quad Core 2.8 GHz y 8Gb de memoria RAM, sin embargo no se ha
Proyecto Fin de Carrera | María Miranda Burguete
88 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
empleado un método de computación en paralelo dada la simplicidad de este
caso. El tiempo de ejecución contabiliza el intervalo transcurrido desde que se
inicia la primera iteración de cada operación hasta que se alcanza la
convergencia a una solución óptima para la misma.
El análisis descrito a continuación también ha sido empleado con el fin de
asegurar el correcto funcionamiento de cada una de las operaciones por
separado. La solución inicial elegida para este estudio de eficacia y
optimización ha sido la obtenida con la heurística de mínima distancia.
7.1.2.1. Relocate
La operación Relocate mueve en cada iteración un cliente para colocarlo en una
posición diferente dentro de la misma ruta o en una ruta distinta. Esta
operación prueba todas las combinaciones posibles, mostrando finalmente el
movimiento de un único cliente sobre la solución inicial. Este cambio será, de
entre todas las alternativas posibles, el que produce la mayor disminución de
la distancia total recorrida.
El proceso llevado a cabo por la operación Relocate se explica a continuación
paso a paso. Se comienza almacenando la solución inicial y la distancia total
recorrida para dicha combinación de rutas, en este caso 255.1073. El primer
movimiento que se realiza es el cambio de posición del cliente que ocupa el
primer lugar en la primera ruta a la segunda posición de la misma,
intercambiando para ello la posición de los dos primeros clientes de manera
que el segundo cliente pasa a ser el primer cliente visitado por el vehículo 1.
En la figura 23 se muestra el movimiento explicado.
Cada vez que se realiza un movimiento se recalcula la distancia total
recorrida, resultando igual a 263.2343. Al ser este valor mayor al de la última
distancia almacenada, se continúa con la siguiente iteración sin almacenar el
movimiento realizado.
Figura 23. Primer movimiento realizado por la operación Relocate sobre la solución inicial. Aplicación aislada de la operación sobre la Red de Prueba.
Seguidamente, se mueve el cliente número 8 a la tercera posición de la ruta
uno, tal y como se describe en la figura 24. La distancia recorrida es ahora
262.2343, también superior al último valor de distancia almacenado, por lo
Proyecto Fin de Carrera | María Miranda Burguete
89 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
que este movimiento se descarta.
Figura 24. Segundo movimiento realizado por la operación Relocate sobre la solución inicial. Aplicación aislada de la operación sobre la Red de Prueba.
De la misma manera se prueba mover el cliente 8 a la cuarta y última posición
de la ruta uno. Posteriormente se repite el proceso para los clientes 13, 12 y 15
sin alterar la posición del cliente 8, cuyos movimientos en la primera ruta ya
han sido estudiados.
Al colocar el cliente 12 en la última posición de la ruta uno, se obtiene una
distancia recorrida igual a 251.4342, menor a la última distancia almacenada
en la variable. Cuando esto ocurre y se produce una mejora de la solución, se
guarda esta nueva solución en la variable temporal que contiene la última
solución mejorada. En este caso, dicha variable contenía hasta el momento la
solución inicial. Las rutas quedan por tanto tal y como muestra la tabla 44.
Tabla 44. Primera solución mejorada obtenida con la operación Relocate sobre la solución inicial. Aplicación aislada de la operación sobre la Red de Prueba.
Vehículo
1
2
3
4
Clientes
8 13 15 12
4 3 2 1
7 6 9 5
11 10 14
Una vez que se terminan de mover todos los clientes que componen la
primera ruta y se han colocado en todas las posiciones posibles dentro de la
ruta, se pasa a colocar esos mismos clientes dentro de la ruta dos,
posteriormente de la ruta tres y por último se prueba cada cliente en cada
posición de la cuarta ruta.
Después de haber probado todas las posiciones posibles para los clientes de la
primera ruta, se repetiría todo el proceso para los clientes de la segunda ruta,
comenzando por el primero de ellos, es decir el cliente número 4. El último
movimiento que se realiza será por tanto el cambio de posición del cliente 14
Proyecto Fin de Carrera | María Miranda Burguete
90 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
para colocarlo en el segundo lugar de la cuarta ruta. Con este movimiento se
cierra el análisis de los movimientos de clientes de la última ruta sobre ella
misma y concluye el estudio de esta operación.
Al finalizar el algoritmo, las variables S* y d* contendrán, respectivamente, la
mejor solución obtenida y la distancia total recorrida correspondiente, que
será la mínima distancia obtenida tras realizar todas las iteraciones. La tabla 45
muestra la solución final generada aplicando el mejor movimiento de la
operación Relocate.
Tabla 45. Mejor solución tras realizar todas las iteraciones de la operación Relocate sobre la solución inicial por la heurística de mínima distancia sobre la Red de Prueba.
Vehículo
1
2
3
4
Clientes
8 13 12 15
4 5 3 2 1
7 6 9
11 10 14
El cambio respecto a la solución inicial es el movimiento del cliente 5 del final
de la tercera ruta a la segunda posición de la ruta dos. Ahora, el segundo
vehículo visitará al cliente 5, después de haber repartido al cliente 4, y
finalizará su recorrido con las visitas a los clientes 3, 2 y 1. El tercer vehículo
repartirá sólo a los clientes 7, 6 y 9.
La distancia recorrida en este caso es 238.0475 unidades, menor a la distancia
recorrida con la solución inicial. El tiempo empleado es igual a 0.03 segundos.
7.1.2.2. Exchange
Esta operación intercambia los clientes de dos rutas, pero no los coloca
necesariamente en la misma posición. Una vez se han almacenado la solución
inicial y la distancia total recorrida en las variables S* y d*, se comienzan las
iteraciones de la operación Exchange.
Las capacidades disponibles de los vehículos tras haber repartido los clientes
en las diferentes rutas formando la solución inicial se muestran en la tabla 46.
El cliente con mayor demanda es el cliente número 13, cuya demanda
asciende a 28 unidades. El segundo cliente con mayor valor de la demanda es
el cliente 15, con una demanda de 25 unidades. En cada iteración, las rutas
afectadas van a cambiar un cliente por otro.
Proyecto Fin de Carrera | María Miranda Burguete
91 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
Tabla 46. Capacidades disponibles de los vehículos con la combinación de rutas de la solución inicial sobre la Red de Prueba.
Núm. ruta 1 2 3 4
Capacidad disponible 25 41 47 67
Las rutas 2, 3 y 4 admiten cualquier cliente, al tener una capacidad mayor a la
máxima demanda. La capacidad disponible de la primera ruta es la menor, sin
embargo, esta ruta incluye a los clientes con mayor demanda, siendo capaz de
cubrir la demanda de cualquier otro cliente en caso de sustitución. Además,
hay que tener en cuenta que cuando una ruta admite un nuevo cliente,
también se desprende de uno de los clientes que poseía, aumentando su
capacidad disponible para aceptar la nueva adquisición.
Aunque el algoritmo debe comprobar en cada iteración si el intercambio
cumple las restricciones de capacidad, con las condiciones ya descritas queda
demostrado que para esta Red de Prueba en concreto, todas las iteraciones que
realiza la operación Exchange, serán admisibles.
Los pasos realizados por la operación se detallan a continuación obviando la
condición de capacidad que se aplicaría en cada iteración. Primero se
intercambia un cliente de la ruta uno con un cliente de la segunda ruta. Sean
las rutas 1 y 2 de la solución inicial las mostradas en la tabla 47, las primeras
iteraciones realizadas con la operación Exchange serían las siguientes:
Tabla 47. Rutas uno y dos de la solución inicial por la heurística de mínima distancia sobre la Red de Prueba.
Vehículo
1
2
Clientes
8 13 12 15
4 3 2 1
1ª iteración
Tabla 48. Rutas uno y dos tras la primera iteración de la operación Exchange sobre la solución inicial. Aplicación aislada de la operación sobre la Red de Prueba.
Vehículo
1
2
Clientes
4 13 12 15
8 3 2 1
Distancia total recorrida = 277.6777
Proyecto Fin de Carrera | María Miranda Burguete
92 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
2ª iteración
Tabla 49. Rutas uno y dos tras la segunda iteración de la operación Exchange sobre la solución inicial. Aplicación aislada de la operación sobre la Red de Prueba.
Vehículo
1
2
Clientes
13 4 12 15
8 3 2 1
Distancia total recorrida = 294.0340
3ª iteración
Tabla 50. Rutas uno y dos tras la tercera iteración de la operación Exchange sobre la solución inicial. Aplicación aislada de la operación sobre la Red de Prueba.
Vehículo
1
2
Clientes
13 12 4 15
8 3 2 1
Distancia total recorrida = 303.1548
4ª iteración
Tabla 51. Rutas uno y dos tras la cuarta iteración de la operación Exchange sobre la solución inicial. Aplicación aislada de la operación sobre la Red de Prueba.
Vehículo
1
2
Clientes
13 12 15 4
8 3 2 1
Distancia total recorrida = 280.5212
Para aclarar el procedimiento se designará por uno a la primera ruta y por dos
a la segunda. En estas iteraciones se ha colocado el cliente número 8 (cliente
que pertenecía a uno) en la primera posición de dos, mientras se ha desplazado
el cliente 4 (cliente que se encontraba originalmente en la primera posición de
dos) por todas las posiciones de uno. El siguiente paso es probar el cliente 3
(cliente que ocupaba la segunda posición de dos), en todas las posiciones de
uno, manteniendo de nuevo el cliente 8 en la primera posición de dos.
Proyecto Fin de Carrera | María Miranda Burguete
93 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
5ª iteración
Tabla 52. Rutas uno y dos tras la quinta iteración de la operación Exchange sobre la solución inicial. Aplicación aislada de la operación sobre la Red de Prueba.
Vehículo
1
2
Clientes
3 13 12 15
8 4 2 1
Distancia total recorrida = 290.2683
6ª iteración
Tabla 53. Rutas uno y dos tras la sexta iteración de la operación Exchange sobre la solución inicial. Aplicación aislada de la operación sobre la Red de Prueba.
Vehículo
1
2
Clientes
13 3 12 15
8 4 2 1
Distancia total recorrida = 308.1639
7ª iteración
Tabla 54. Rutas uno y dos tras la séptima iteración de la operación Exchange sobre la solución inicial. Aplicación aislada de la operación sobre la Red de Prueba.
Vehículo
1
2
Clientes
13 12 3 15
8 4 2 1
Distancia total recorrida = 316.4929
8ª iteración
Tabla 55. Rutas uno y dos tras la octava iteración de la operación Exchange sobre la solución inicial. Aplicación aislada de la operación sobre la Red de Prueba.
Vehículo
1
2
Clientes
13 12 15 3
8 4 2 1
Proyecto Fin de Carrera | María Miranda Burguete
94 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
Distancia total recorrida = 292.3199
Del mismo modo se moverán los clientes 2 y 1 por las posiciones de uno. Una
vez finalizadas estas iteraciones, el cliente 8 se desplazará a la segunda
posición de dos, y se repetirán los movimientos de los clientes 4, 3, 2 y 1 por
separado. Posteriormente se repetirá el proceso colocando el cliente número 8
en la tercera y en la cuarta posición de dos. La última iteración por la que el
cliente 8 se intercambia con uno de los clientes de dos se describe en la tabla 56.
Tabla 56. Rutas uno y dos tras la última iteración de la operación Exchange sobre la solución inicial en la que se intercambia el primer cliente de la ruta uno por un cliente de la segunda. Aplicación aislada de la operación sobre la Red de Prueba.
Vehículo
1
2
Clientes
13 12 15 1
4 3 2 8
Distancia total recorrida = 303.9510
Después de haber realizados estas iteraciones, llega el turno de intercambiar el
cliente que ocupaba la segunda posición en uno, es decir, el cliente número 13,
con los clientes de dos. Se repite el mismo proceso explicado para el cliente 8.
Seguidamente, se moverá de ruta el cliente 12 y por último el 15. La última
iteración que intercambiará los clientes de la primera y segunda ruta será, por
tanto, la descrita en la tabla 57.
Tabla 57. Rutas uno y dos tras la última iteración de la operación Exchange que relaciona estas rutas sobre la solución inicial en la Red de Prueba.
Vehículo
1
2
Clientes
8 13 12 1
4 3 2 15
Distancia total recorrida = 313.7860
Los resultados obtenidos hasta el momento surgen de intercambiar los clientes
de las dos primeras rutas. Este mismo procedimiento se repetirá para las rutas
uno y tres, uno y cuatro, y así hasta probar todas las combinaciones de rutas
posibles. En cada iteración se ha calculado la distancia total recorrida por la
Proyecto Fin de Carrera | María Miranda Burguete
95 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
solución. Esta distancia es comparada con la distancia almacenada en la
variable d*, que contiene inicialmente la distancia recorrida con la solución
inicial, y sustituye su valor en caso de ser menor. En ese caso, la solución se
almacena en la variable S*.
En la tabla 58 se muestra la mejor solución obtenida una vez estudiadas todas
las combinaciones posibles de la operación Exchange.
Tabla 58. Mejor solución obtenida tras realizar todas las iteraciones de la operación Exchange sobre la solución inicial generada por la heurística de mínima distancia. Aplicación aislada de la operación sobre la Red de Prueba.
Vehículo
1
2
3
4
Clientes
8 13 12 15
4 5 3 2
7 1 6 9
11 10 14
Se han intercambiado los clientes 1 y 5 de las rutas de las rutas dos y tres
respectivamente. Esta operación intercambia los clientes de dos rutas, pero no
necesariamente en la posición relativa a la ruta que ocupaba el cliente
originalmente. En este caso, ninguno de los clientes intercambiados pasa a
ocupar la posición abandonada por el otro en la ruta destino.
La distancia total recorrida por los vehículos es 240.7053 unidades de distancia
y el tiempo de ejecución 0.14 segundos. El tiempo empleado por esta
operación es notablemente superior al utilizado por las demás operaciones,
puesto que el número de combinaciones posibles que deben ser analizadas por
el algoritmo y descartadas es considerablemente mayor.
7.1.2.3. Merge_mod
Merge_mod introduce el máximo número de clientes de una ruta al final de
otra ruta. La solución inicial obtenida por la heurística de mínima distancia se
muestra en la tabla 59, en la cual se ha incluido la demanda de los clientes y
las capacidades disponibles de los vehículos.
Esta operación comienza introduciendo los clientes de la ruta uno en la
segunda ruta. Para asegurar que la cantidad de clientes que se añaden a la
ruta llega a ser la máxima, se introducen en primer lugar los clientes con
menor demanda. Para optimizar la operación, la distancia recorrida se calcula
Proyecto Fin de Carrera | María Miranda Burguete
96 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
cada vez que se mueve un cliente, en lugar de calcularla solamente cuando se
ha introducido el mayor número de clientes posible.
Tabla 59. Solución inicial por la heurística de mínima distancia sobre la Red de Prueba junto con las demandas de los clientes y las capacidades disponibles de los vehículos.
Clientes Capacidad Disponible
Vehículo 1
Demanda
8 13 12 15
12 28 10 25 25
Vehículo 2
Demanda
4 3 2 1
12 21 16 10 41
Vehículo 3
Demanda
7 6 9 5
19 8 16 10 47
Vehículo 4
Demanda
11 10 14
6 5 22 67
Así, la operación Merge_mod es capaz de introducir el máximo número de
clientes de una ruta en otra ruta, pero no necesariamente tiene que mover
todos estos. La mejor iteración será aquella que logre minimizar la distancia
recorrida. En otras palabras, si el movimiento que genera el mejor resultado
implica introducir menos clientes que el máximo número posible, esta
operación optará por dicha opción. El procedimiento se describe a
continuación en forma de los pasos seguidos por Merge_mod.
1. Se ordenan los clientes de la ruta uno de menor a mayor demanda.
Tabla 60. Demandas de los clientes de la ruta uno de la solución inicial sobre la Red de Prueba en orden creciente.
Núm. cliente 12 8 15 13
Demanda 10 12 25 28
2. Se asignan estos clientes a la ruta dos uno a uno, actualizando, cada vez que
se mueve un cliente, la capacidad disponible de los vehículos. En cada
iteración se calcula la distancia total recorrida, incluidas en las tablas 61 y 62.
Proyecto Fin de Carrera | María Miranda Burguete
97 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
Tabla 61. Primera iteración de la operación Merge_mod sobre la solución inicial. Aplicación aislada de la operación sobre la Red de Prueba.
Clientes Capacidad Disponible
Vehículo 1 8 13 15 35
Vehículo 2 4 3 2 1 12 31
Distancia total recorrida = 275.3702
Tabla 62. Segunda iteración de la operación Merge_mod sobre la solución inicial. Aplicación aislada de la operación sobre la Red de Prueba.
Clientes Capacidad Disponible
Vehículo 1 13 15 47
Vehículo 2 4 3 2 1 12 8 19
Distancia total recorrida = 280.5307
Después de introducir los clientes 12 y 8 en la segunda ruta, la capacidad del
vehículo impide que se añadan los clientes 13 y 15, dando fin a esta
iteración.
3. Se continúa iterando hasta completar todos los movimientos posibles de la
operación. Las iteraciones que implican el movimiento de clientes de la ruta
uno a la tercera se muestran en las tablas 63 a 65.
Tabla 63. Tercera iteración de la operación Merge_mod sobre la solución inicial. Aplicación aislada de la operación sobre la Red de Prueba.
Clientes Capacidad Disponible
Vehículo 1 8 13 15 35
Vehículo 3 7 6 9 5 12 37
Distancia total recorrida = 270.6226
Proyecto Fin de Carrera | María Miranda Burguete
98 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
Tabla 64. Cuarta iteración de la operación Merge_mod sobre la solución inicial. Aplicación aislada de la operación sobre la Red de Prueba.
Clientes Capacidad Disponible
Vehículo 1 13 15 35
Vehículo 3 7 6 9 5 12 8 25
Distancia total recorrida = 275.7831
Tabla 65. Quinta iteración de la operación Merge_mod sobre la solución inicial. Aplicación aislada de la operación sobre la Red de Prueba.
Clientes Capacidad Disponible
Vehículo 1 13 35
Vehículo 3 7 6 9 5 12 8 15 0
Distancia total recorrida = 285.0458
Las siguientes iteraciones buscarán introducir el mayor número de clientes de la
primera ruta en la última ruta. Se repite este proceso para todas las
combinaciones de rutas, almacenando en las variables S* y d* la solución y la
distancia recorrida, cuando ésta última sea menor a la última distancia que
contiene en ese momento d*. Nuevamente, se toma la mejor de las soluciones
alcanzables por esta operación. Para generar la nueva solución, mostrada en la
tabla 66, todos los clientes de la última ruta se colocan al final de la ruta dos. El
cuarto vehículo en este caso no visita a ningún cliente, quedando inoperativo.
Tabla 66. Mejor solución tras realizar todas las iteraciones de la operación Merge_mod sobre la solución inicial por la heurística de mínima distancia sobre la Red de Prueba.
Vehículo
1
2
3
4
Clientes
8 13 12 15
4 3 2 1 10 11 14
7 6 9 5
-
Proyecto Fin de Carrera | María Miranda Burguete
99 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
La aplicación de esta operación converge en una solución cuya distancia total
recorrida es igual a 244.4162 unidades. El tiempo de ejecución empleado por
Merge_mod es de 0.02 segundos.
El objetivo de la operación Merge_mod es introducir el mayor número de
clientes de una ruta en otra diferente. Para asegurar que el número de clientes
candidatos a ser traspasados es el mayor posible, los clientes de una fila se van
introduciendo en otra uno a uno, empezando por el de menor demanda y
terminando por el de demanda mayor. De esto se deduce que el orden en que
se introducen los clientes en la nueva ruta no es necesariamente el óptimo en
cuanto a distancia recorrida, teniendo que utilizar otra operación diferente si
se desea reordenar los clientes y estudiar posteriores opciones de mejora.
7.1.2.4. 2-Opt*
La operación 2-Opt* intercambia los finales de dos rutas. Por final de una ruta
puede entenderse desde ningún cliente hasta todos los clientes que forman la
misma. Teniendo en cuenta las restricciones de capacidad, las iteraciones que
generan el intercambio de clientes entre las dos primeras rutas se describen en
las tablas 67 a 75.
1ª iteración
Tabla 67. Rutas uno y dos tras la primera iteración de la operación 2-Opt* sobre la solución inicial. Aplicación aislada de la operación sobre la Red de Prueba.
Vehículo
1
2
Clientes
3 2 1
4 8 13 12 15
Distancia total recorrida = 263.7728
2ª iteración
Tabla 68. Rutas uno y dos tras la segunda iteración de la operación 2-Opt* sobre la solución inicial. Aplicación aislada de la operación sobre la Red de Prueba.
Vehículo
1
2
Clientes
8 4 3 2 1
13 12 15
Distancia total recorrida = 264.4586
Proyecto Fin de Carrera | María Miranda Burguete
100 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
3ª iteración
Tabla 69. Rutas uno y dos tras la tercera iteración de la operación 2-Opt* sobre la solución inicial. Aplicación aislada de la operación sobre la Red de Prueba.
Vehículo
1
2
Clientes
8 3 2 1
4 13 12 15
Distancia total recorrida = 277.6777
4ª iteración
Tabla 70. Rutas uno y dos tras la cuarta iteración de la operación 2-Opt* sobre la solución inicial. Aplicación aislada de la operación sobre la Red de Prueba.
Vehículo
1
2
Clientes
8 2 1
4 3 13 12 15
Distancia total recorrida = 291.5852
5ª iteración
Tabla 71. Rutas uno y dos tras la quinta iteración de la operación 2-Opt* sobre la solución inicial. Aplicación aislada de la operación sobre la Red de Prueba.
Vehículo
1
2
Clientes
8 13 4 3 2 1
12 15
Distancia total recorrida = 268.2279
6ª iteración
Tabla 72. Rutas uno y dos tras la sexta iteración de la operación 2-Opt* sobre la solución inicial. Aplicación aislada de la operación sobre la Red de Prueba.
Vehículo
1
2
Clientes
8 13 3 2 1
4 12 15
Proyecto Fin de Carrera | María Miranda Burguete
101 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
Distancia total recorrida = 284.5759
7ª iteración
Tabla 73. Rutas uno y dos tras la séptima iteración de la operación 2-Opt* sobre la solución inicial. Aplicación aislada de la operación sobre la Red de Prueba.
Vehículo
1
2
Clientes
8 13 2 1
4 3 12 15
Distancia total recorrida = 296.8553
8ª iteración
Tabla 74. Rutas uno y dos tras la octava iteración de la operación 2-Opt* sobre la solución inicial. Aplicación aislada de la operación sobre la Red de Prueba.
Vehículo
1
2
Clientes
8 13 1
4 3 2 12 15
Distancia total recorrida = 307.8119
9ª iteración
Tabla 75. Rutas uno y dos tras la novena iteración de la operación 2-Opt* sobre la solución inicial. Aplicación aislada de la operación sobre la Red de Prueba.
Vehículo
1
2
Clientes
8 13
4 3 2 1 12 15
Distancia total recorrida = 272.7659
En la tabla 76 se muestra el resumen de todos los movimientos posibles de la
operación 2-Opt*. Los movimientos intermedios que no se han mostrado y que
se incluyen resaltados en color rojo en esta tabla, no se han podido realizar
debido a las restricciones de capacidad.
Proyecto Fin de Carrera | María Miranda Burguete
102 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
Tabla 76. Resumen de los movimientos posibles de la operación 2-Opt* sobre la solución inicial. Aplicación aislada de la operación sobre la Red de Prueba.
Número de iteración Clientes transferidos de
la ruta uno a la dos
Clientes transferidos de
la ruta dos a la uno
1
-
-
-
2
3
4
-
-
5
6
7
8
9
4
4
4
4
3
3
3
3
3
2
2
2
2
2
3
2
1
0
4
3
2
1
0
4
3
2
1
0
Para completar el estudio de esta operación se continúan las iteraciones hasta
probar todas las combinaciones de rutas. La combinación de rutas para la que
se obtiene la mínima distancia recorrida se describe en la tabla 77.
Tabla 77. Mejor solución tras realizar todas las iteraciones de la operación 2-Opt* sobre la solución inicial por la heurística de mínima distancia sobre la Red de Prueba.
Vehículo
1
2
3
4
Clientes
8 13 12 15
4 3 2 1
7 6 9 11 10 14
5
En el caso de la Red de Prueba, la mejor solución que se obtiene con una sola
iteración de la operación 2-Opt* se consigue intercambiando los finales de las
Proyecto Fin de Carrera | María Miranda Burguete
103 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
rutas tres y cuatro. En concreto, todos los clientes correspondientes a la ruta
cuarta han sido asignados a la tercera ruta, y el último cliente visitado en la
ruta tercera pertenece ahora al recorrido de la cuarta ruta, que solo visita
dicho nodo.
La distancia recorrida por la nueva solución obtenida es 239.4733 unidades.
Para la ejecución de la operación se han empleado 0.02 segundos.
7.1.2.5. Análisis de resultados. Comparación de las operaciones
Una vez que se han obtenido las soluciones óptimas para un único
movimiento de cada una de las cuatro operaciones de búsqueda local
consideradas es posible comparar los resultados de las mismas.
- La tabla 78 contiene los tiempos de ejecución de cada operación con el
mismo sistema informático. Dada la variabilidad de los mismos, se han
representado con una única cifra significativa. Como se observa, la
operación Exchange resulta ser la más lenta, con un tiempo de ejecución
del orden de siete veces mayor al tiempo empleado por el resto de
operaciones.
Tabla 78. Tiempos de Ejecución de las Operaciones sobre la solución inicial obtenida con la heurística de mínima distancia sobre la Red de Prueba.
Operación Tiempo de ejecución
Relocate
Exchange
Merge_mod
2-Opt*
0.02
0.14
0.01
0.02
Este resultado está fuertemente condicionado por los principios
matemáticos de la combinatoria. Es decir, el algoritmo que debe analizar
y descartar un mayor número de posibles movimientos resultará en un
mayor tiempo de ejecución para cada iteración.
Por otro lado, la rapidez con la que las operaciones deben comprobar un
mayor número de candidatos dentro del algoritmo ARF puede verse
ayudada por técnicas de optimización en la creación del código que
ejecuta dicha operación. Por ejemplo, si dos rutas se han mantenido
Proyecto Fin de Carrera | María Miranda Burguete
104 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
inalteradas en las ultimas iteraciones, es posible eliminar las soluciones
candidatas que surgen de las interacciones entre ambas rutas.
- La función objetivo consiste en la minimización de la distancia total
recorrida. Todas las operaciones obtienen una solución que mejora la
solución inicial a partir de la realización de un único movimiento. Las
distancias que tendrían que recorrer los vehículos disponibles según las
soluciones obtenidas se recopilan en la tabla 79.
Tabla 79. Distancias obtenidas con el mejor movimiento de cada operación sobre la solución inicial obtenida con la heurística de mínima distancia sobre la Red de Prueba.
Distancia total recorrida
Solución inicial 255.1073
Relocate
Exchange
Merge_mod
2-Opt*
238.0475
240.7053
244.4162
239.4733
La operación Relocate proporciona la menor distancia total recorrida,
seguida de cerca por las operaciones 2-Opt* y Exchange. Merge_mod es la
operación con la que se obtiene la menor mejora sobre la solución inicial
por la heurística de mínima distancia. Esta operación mueve cierto
número de clientes de una ruta y los añade al final de otra ruta diferente.
Debido a las restricciones de capacidad, se limita el número de clientes a
mover impidiendo que la operación proporcione soluciones mejores.
Es necesario recalcar que se han probado todos los movimientos
posibles sobre la solución inicial uno a uno. Es decir, cada vez que se
realiza el cambio de posición de un cliente o grupo de clientes (dos
clientes o dos grupos de clientes en el caso de operaciones de
intercambio) se hace respecto a la solución inicial. Se trata, por tanto, de
una primera comparación entre las operaciones a través de la cual se
puede obtener una idea de la capacidad de mejora de cada operación.
Sin embargo, los resultados podrían variar si las operaciones se
utilizaran sobre una solución inicial diferente, al ser fuertemente
dependientes de esta última.
Proyecto Fin de Carrera | María Miranda Burguete
105 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
Con el objetivo de recalcar la importancia de las condiciones iniciales en
cada iteración de los movimientos, a continuación se repetirán los
resultados de este apartado sobre la segunda solución inicial o solución
obtenida con la heurística de demanda máxima. Las mínimas distancias
obtenidas tras probar todas las posibles combinaciones de cada
operación están recogidas en la tabla 80.
Tabla 80. Distancias obtenidas con el mejor movimiento de cada operación sobre la solución inicial obtenida con la heurística de demanda máxima sobre la Red de Prueba.
Distancia total recorrida
Solución inicial 365.3890
Relocate
Exchange
Merge_mod
2-Opt*
325.9683
316.2365
332.7426
341.3494
En esta ocasión puede apreciarse que la operación 2-Opt* produce la
peor de las soluciones. Recuérdese que esta operación intercambia los
finales de dos rutas. Al encontrarse los clientes ordenados de una
manera aleatoria debido al procedimiento de asignación en la heurística
de demanda máxima para la solución inicial, la probabilidad de que el
intercambio de varios clientes al final de dos rutas conduzca a una
mejora se ve reducida. Por otro lado, la mejora más pronunciada la
consigue la operación Exchange. El orden caótico de la solución inicial,
véase la figura 22, permite que un único intercambio de clientes
produzca una gran reducción en la distancia total recorrida. Las
operaciones Relocate y Merge_mod producen resultados intermedios entre
los extremos discutidos.
En la figura 25 puede apreciarse una comparativa de la mejora
porcentual que el mejor movimiento de cada operación produce sobre
las dos soluciones iniciales consideradas. Es posible observar como para
ambas heurísticas, diferentes operaciones producen la mayor y menor
mejora respectivamente. Este resultado confirma nuevamente el peso
que posee la solución inicial en la aplicación de operaciones de
búsqueda local.
Proyecto Fin de Carrera | María Miranda Burguete
106 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
Adicionalmente, la mejora porcentual que las operaciones Relocate,
Exchange y 2-Opt* generan con una solo movimiento es del orden del
doble para la solución inicial de demanda máxima. El objetivo de dicha
heurística de solución inicial es aportar un método robusto para alcanzar
una solución admisible y por tanto este resultado confirma que la mejora
local durante las primeras iteraciones produce un descenso más
acuciado de la distancia total recorrida por los vehículos.
Figura 25. Grafica comparativa de la mejora porcentual del mejor movimiento de cada operación respecto a la solución inicial sobre la Red de Prueba.
En el caso de la operación Merge_mod la mejora porcentual es muy
similar para ambas soluciones iniciales. Estos resultados no son
suficientemente representativos como para extraer conclusiones respecto
a este hecho, sin embargo, el espacio de candidatos estudiados por esta
operación es reducido en comparación con Relocate o Exchange, lo que
podría estar condicionando la mejora obtenida.
7.1.3. Aplicación del ARF particularizado a cada palo del flamenco
Una vez se ha completado la comparación de las operaciones de manera
aislada, esta sección se centra en la comparación de cada uno de los palos del
flamenco considerados en este proyecto y su implementación en el ARF. Con el
objetivo de aislar cada palo del flamenco, el algoritmo de optimización se
Proyecto Fin de Carrera | María Miranda Burguete
107 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
particularizará para cada palo de manera que en lugar de recorrer los palos de
manera consecutiva, se realicen sucesivas iteraciones del mismo palo.
Para cada iteración sobre el palo, la representación cronotónica determina la
operación a realizar. Una vez se inicia el estudio de las combinaciones posibles
generadas por dicha operación, la primera de las que produce una mejora sobre
la distancia total es almacenada como nueva solución optima sobre la cual
futuras operaciones serán aplicadas y el algoritmo abandona dicha operación.
Los resultados obtenidos con los diferentes compases se utilizan para clasificar
los palos en orden al grado de mejora que alcanzan. En los sucesivos apartados
se muestran las soluciones generadas utilizando como solución inicial la
proporcionada por la heurística de mínima distancia, descrita en la sección
7.1.1.1. El equipo informático y las condiciones del cálculo de tiempo requerido
por cada algoritmo no varían en esta sección respecto a las descritas en el
apartado anterior.
El proceso seguido por el algoritmo ARF se encuentra detallado en el punto 5.4.
El propósito de esta sección es estudiar los palos del flamenco de manera
aislada, utilizando en cada caso una particularización del algoritmo. Así, la
matriz M se convertirá en un vector que estará formado en cada caso por la
codificación del palo correspondiente. Como consecuencia de este cambio en el
algoritmo, el contador C, que recorría las filas de la matriz, queda inutilizado.
En los siguientes apartados se muestran los resultados obtenidos para los
distintos palos, indicando los valores que toman las variables S*, d* y P cada vez
que se ejecuta una operación. En este momento es importante insistir en que
cuando el algoritmo llama a la función que contiene una determinada
operación, esta prueba sucesivos movimientos sobre la solución almacenada en
S*, y devuelve la primera solución que minimice la distancia recorrida. En ese
momento se sale de la función y se guarda esta nueva combinación de rutas en
la variable S*, sustituyendo su anterior valor.
7.1.3.1. Fandango
La codificación de este palo indica que la única operación que se aplica al
ejecutar el algoritmo particularizado al Fandango es la operación Merge_mod.
El algoritmo ARF se inicia con los contadores A y B a cero, al igual que la
variable D. Cuando el primer acento fuerte se detecta, la variable D tiene valor
tres. Por ello, se aplica la operación tres sobre la solución inicial hasta
encontrar la primera combinación de rutas que mejore la distancia total
recorrida. Esta solución sustituye el valor almacenado en S*. Las rutas se
recogen en la tabla 81.
Proyecto Fin de Carrera | María Miranda Burguete
108 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
Tabla 81. Mejor solución obtenida tras aplicar el algoritmo del Fandango sobre la solución inicial generada por la heurística de mínima distancia sobre la Red de Prueba.
Vehículo
1
2
3
4
Clientes
8 13 12 15
4 3 2 1 10 11 14
7 6 9 5
-
La distancia recorrida es 244.4162. El vector P es un vector de ceros. La
variable D se vuelve a poner a cero y el algoritmo continúa incrementando los
valores de B y D a medida que se recorre el vector del palo. El valor de D
cuando se encuentra el siguiente acento fuerte vuelve a indicar que se ejecute
la operación tres. En este caso, se realizan todas las iteraciones posibles de la
operación sin encontrar ninguna mejora sobre la última solución almacenada.
La función que aplica la operación Merge_mod devuelve el siguiente vector P:
P = [0 0 1 0]
Al continuar el algoritmo hasta encontrar el siguiente acento fuerte, la variable
D indica que se vuelva a aplicar la operación tres. Debido a que la componente
tres del vector P contiene un uno, indicando que la solución no ha cambiado
desde la última vez que se ejecutó la operación y que ésta no logró ninguna
mejora, se evita volver a aplicar la misma. El valor de P no cambia y al ser tres
la única operación que contiene el Fandango, la mejor solución es la obtenida
con la primera aplicación de la operación.
Siguiendo la metodología del ARF, este palo equivale a aplicar sucesivamente
la operación tres. En particular, la solución generada por el palo flamenco es la
misma que la obtenida aplicando el mejor movimiento de dicha operación
(véase la sección 7.1.2.3). Nuevamente queda manifiesta la limitación que
implica usar una única operación para el proceso de mejora, tras el primer
cambio la operación es incapaz de avanzar hacia soluciones mejores.
Como consecuencia, en el caso del Fandango aumentar el número de
iteraciones del algoritmo no produce ninguna mejora en la solución. La
distancia total recorrida es por tanto 244.4162. El tiempo empleado en ejecutar
el algoritmo es 0.02 segundos.
7.1.3.2. Soleá
La Soleá tiene una codificación [0 1 0 0 1 0 1 0 1 0 1 1]. La primera distancia
cronotónica de este palo es igual a dos, por lo que el algoritmo debe aplicar
Proyecto Fin de Carrera | María Miranda Burguete
109 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
sobre la solución inicial la operación dos, Exchange. Dentro de este apartado,
los resultados de cada operación serán representados mediante una tabla
describiendo las rutas contenidas en la variable S* junto con los valores de la
distancia mínima temporal (d*) y el vector P que inhibe la realización de
operaciones redundantes innecesariamente.
De esta manera, la aplicación de la operación Exchange en primer lugar
produce las soluciones descritas en la tabla 82 y los siguientes valores de las
variables d* y P.
Tabla 82. Primera solución mejorada obtenida tras aplicar la primera operación de la Soleá sobre la Red de Prueba.
Vehículo
1
2
3
4
Clientes
8 13 12 15
5 3 2 1
4 7 6 9
11 10 14
d* = 248.8613
P = [0 0 0 0]
El algoritmo continúa y debe entonces ejecutar la operación tres. Los valores
resultantes de aplicar a continuación Merge_mod generan un desplazamiento
de todos los clientes de la ruta cuatro al final de la ruta dos, quedando la
primera de éstas completamente vacía. La tabla 83 muestra esta solución.
Tabla 83. Primera solución mejorada obtenida tras aplicar la segunda operación de la Soleá sobre la Red de Prueba.
Vehículo
1
2
3
4
Clientes
8 13 12 15
5 3 2 1 10 11 14
4 7 6 9
-
Proyecto Fin de Carrera | María Miranda Burguete
110 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
d* = 238.1702
P = [0 0 0 0]
La siguiente operación en ejecutarse es de nuevo Exchange. Esta vez se realiza
un intercambio entre las rutas dos y tres, moviendo los clientes 5 y 6.
Tabla 84. Primera solución mejorada obtenida tras aplicar la tercera operación de la Soleá sobre la Red de Prueba.
Vehículo
1
2
3
4
Clientes
8 13 12 15
3 2 1 6 10 11 14
5 4 7 9
-
d* = 231.7244
P = [0 0 0 0]
Continúa la aplicación de la Soleá con una distancia cronotónica igual a dos,
que impone de nuevo la aplicación de la operación Exchange. En este caso el
resultado produce un intercambio de los clientes 3 y 9 entre las rutas dos y
tres, cambiando además la posición de destino dentro de ambas. La tabla 85
recoge la solución descrita.
Tabla 85. Primera solución mejorada obtenida tras aplicar la cuarta operación de la Soleá sobre la Red de Prueba.
Vehículo
1
2
3
4
Clientes
8 13 12 15
2 1 6 9 10 11 14
3 5 4 7
-
d* = 219.6023
Proyecto Fin de Carrera | María Miranda Burguete
111 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
P = [0 0 0 0]
De nuevo la codificación de la Soleá revela una distancia cronotónica igual a
dos, la segunda componente del vector P es nula por lo que el algoritmo
vuelve a realizar la operación Exchange por tercera vez consecutiva. Como
resultado de esta última, los clientes 7 y 2 son intercambiados.
Tabla 86. Primera solución mejorada obtenida tras aplicar la quinta operación de la Soleá sobre la Red de Prueba.
Vehículo
1
2
3
4
Clientes
8 13 12 15
7 1 6 9 10 11 14
2 3 5 4
-
d* = 218.0986
P = [0 0 0 0]
La última operación que incorpora la Soleá es la operación uno, Relocate. El
resultado de la misma es cambiar el orden en el que el vehículo uno visita a
los clientes 12 y 15.
Tabla 87. Primera solución mejorada obtenida tras aplicar la sexta operación de la Soleá sobre la Red de Prueba.
Vehículo
1
2
3
4
Clientes
8 13 15 12
7 1 6 9 10 11 14
2 3 5 4
-
d* = 214.4254
P = [0 0 0 0]
Proyecto Fin de Carrera | María Miranda Burguete
112 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
El proceso hasta ahora descrito concluye con la mejor solución obtenida tras
realizar una sola iteración de la Soleá. Para completar el estudio de la Soleá,
basta con aumentar el número de veces que se recorre el palo. Al igual que
para el resto de los palos, se presentará en cada caso el valor límite de
iteraciones a partir del cual no se produce una mejora sobre la estimación
óptima. En este punto, debe recordarse que la validez de los resultados
obtenidos está ligada a la red de partida y a la solución inicial recogida en la
tabla 29.
Dado que la primera iteración sobre el palo se ha completado con una mejora
respecto a la solución inicial, el algoritmo procede a continuación a realizar la
segunda iteración de la Soleá, con la que se generan las siguientes soluciones.
1. Exchange
La solución obtenida tras aplicar la operación Exchange al inicio de la segunda
iteración de la Soleá se recoge en la tabla 88.
Tabla 88. Primera solución mejorada obtenida tras aplicar la primera operación de la Soleá en la segunda iteración del palo sobre la Red de Prueba.
Vehículo
1
2
3
4
Clientes
8 13 15 12
2 1 6 9 10 11 14
7 3 5 4
-
d* = 209.4573
P = [0 0 0 0]
2. Merge_mod
La aplicación de la operación Merge_mod no genera ninguna combinación de
rutas que reduzca la distancia recorrida. Por ello, la función modifica el valor
del vector P.
P = [0 0 1 0]
Esto indica que hasta que no se modifique la solución almacenada, no se
podrá aplicar de nuevo la operación tres.
Proyecto Fin de Carrera | María Miranda Burguete
113 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
3. Exchange
La operación Exchange tampoco es capaz de producir una mejora y el vector P
es actualizado.
P = [0 1 1 0]
4. Exchange
P = [0 1 1 0]
5. Exchange
P = [0 1 1 0]
6. Relocate
Por último, se ejecuta la operación Relocate obteniendo la solución mostrada en
la tabla 89.
Tabla 89. Primera solución mejorada obtenida tras aplicar la sexta operación de la Soleá en la segunda iteración del palo sobre la Red de Prueba.
Vehículo
1
2
3
4
Clientes
8 13 15 12 11
2 1 6 9 10 14
7 3 5 4
-
d* = 209.0003
P = [0 0 0 0]
El procedimiento descrito hasta ahora se repite en las sucesivas iteraciones del
algoritmo ARF particularizado para la Soleá. En la tabla 90 se recopilan los
resultados obtenidos para diferentes números de iteraciones del algoritmo.
Los datos de tiempo de ejecución son en este caso valores cumulativos.
Proyecto Fin de Carrera | María Miranda Burguete
114 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
Tabla 90. Distancias y tiempos de ejecución obtenidos tras aplicar diferentes números de iteraciones del algoritmo de la Soleá sobre la Red de Prueba.
Número de Iteraciones Distancia Recorrida Tiempo de Ejecución [s]
1 214.4254 0.32
3 198.8253 0.81
≥ 5 198.2030 1.38
En la tabla 91 se recoge la solución correspondiente al límite de las iteraciones,
es decir, la solución generada a partir de cinco iteraciones del algoritmo que
recorre el palo completo, ya que la sexta iteración no produce mejora.
Tabla 91. Mejor solución obtenida tras aplicar el algoritmo de la Soleá sobre la solución inicial generada por la heurística de mínima distancia sobre la Red de Prueba.
Vehículo
1
2
3
4
Clientes
8 13 15 12
2 1 6 9 14 10 11
7 3 5 4
-
7.1.3.3. Bulería
El compás de la Bulería se codifica como [0 1 0 0 0 1 1 0 1 0 1 1]. Dado que la
primera distancia cronotónica es igual a dos, la operación Exchange es la
primera en ejecutarse, devolviendo la solución indicada en la tabla 92.
Tabla 92. Primera solución mejorada obtenida tras aplicar la primera operación de la Bulería sobre la Red de Prueba.
Vehículo
1
2
3
4
Clientes
8 13 12 15
5 3 2 1
4 7 6 9
11 10 14
Proyecto Fin de Carrera | María Miranda Burguete
115 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
d* = 248.8613
P = [0 0 0 0]
Esta solución coincide con la primera solución obtenida con el algoritmo de la
Soleá, debido a que ambos palos comienzan por la operación Exchange.
Seguidamente la lectura de la Bulería impone la aplicación de la operación
cuatro, 2-Opt*. Como resultado de la misma se intercambian los finales de las
rutas uno y tres. La nueva solución obtenida se recoge en la tabla 93.
Tabla 93. Primera solución mejorada obtenida tras aplicar la segunda operación de la Bulería sobre la Red de Prueba.
Vehículo
1
2
3
4
Clientes
7 6 9
5 3 2 1
4 8 13 12 15
11 10 14
d* = 248.2200
P = [0 0 0 0]
A continuación este palo contiene a la operación Relocate. La ejecución de la
misma determina el desplazamiento del cliente número 6 a la última posición
de la segunda ruta como mejor movimiento posible. La tabla 94 muestra la
solución obtenida.
Tabla 94. Primera solución mejorada obtenida tras aplicar la tercera operación de la Bulería sobre la Red de Prueba.
Vehículo
1
2
3
4
Clientes
7 9
5 3 2 1 6
4 8 13 12 15
11 10 14
Proyecto Fin de Carrera | María Miranda Burguete
116 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
d* = 245.6521
P = [0 0 0 0]
Prosigue la aplicación del palo con la operación Exchange. En esta ocasión la
mejor solución se alcanza al intercambiar los clientes 7 y 10. Este movimiento
está ilustrado en la tabla 95.
Tabla 95. Primera solución mejorada obtenida tras aplicar la cuarta operación de la Bulería sobre la Red de Prueba.
Vehículo
1
2
3
4
Clientes
10 9
5 3 2 1 6
4 8 13 12 15
11 14 7
d* = 243.7997
P = [0 0 0 0]
La penúltima operación de este palo es nuevamente Exchange, que debe
ejecutarse de manera consecutiva. En esta ocasión son intercambiados los
clientes 14 y 10, como se indica en la tabla 96.
Tabla 96. Primera solución mejorada obtenida tras aplicar la quinta operación de la Bulería sobre la Red de Prueba.
Vehículo
1
2
3
4
Clientes
14 9
5 3 2 1 6
4 8 13 12 15
11 10 7
d* = 241.6894
P = [0 0 0 0]
Proyecto Fin de Carrera | María Miranda Burguete
117 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
Por último, se ejecuta la operación Relocate antes de finalizar la primera
iteración del palo. Esto produce un desplazamiento del cliente número 5,
como indica la tabla 97.
Tabla 97. Primera solución mejorada obtenida tras aplicar la sexta operación de la Bulería sobre la Red de Prueba.
Vehículo
1
2
3
4
Clientes
14 9
3 2 1 6
4 5 8 13 12 15
11 10 7
d* = 236.4187
P = [0 0 0 0]
Nuevamente se ha realizado un estudio del número de iteraciones límite del
palo sobre la solución inicial de mínima distancia que converge en una
estimación de distancia mínima. Los resultados de incrementar el número de
iteraciones se recogen en la tabla 98, donde puede observarse como la sexta
aplicación de este palo no permite mejorar la solución almacenada.
Tabla 98. Distancias y tiempos de ejecución obtenidos tras aplicar diferentes números de iteraciones del algoritmo de la Bulería sobre la Red de Prueba.
Número de Iteraciones Distancia Recorrida Tiempo de Ejecución [s]
1 236.4187 0.11
3 199.3231 0.50
≥ 5 189.2158 1.10
En la tabla 99 se describen las rutas resultantes de recorrer la Bulería durante
cinco iteraciones completas, llegando a la mejora límite que este palo alcanza.
Proyecto Fin de Carrera | María Miranda Burguete
118 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
Tabla 99. Mejor solución obtenida tras aplicar el algoritmo de la Bulería sobre la solución inicial generada por la heurística de mínima distancia sobre la Red de Prueba.
Vehículo
1
2
3
4
Clientes
8 13 15 12
4 5 3 2 1 6 7
-
11 14 9 10
7.1.3.4. Seguiriya
La codificación del compás de la Seguiriya en binario es [0 1 0 1 0 0 1 0 0 1 0 1].
Siguiendo las distancias cronotónicas de este palo, las operaciones realizadas
sobre la solución inicial y sus resultados se recogen a continuación. En primer
lugar se aplica la operación Exchange, que intercambia los clientes 4 y 5,
pertenecientes a las rutas dos y tres respectivamente. Esta solución se recoge
en la tabla 100.
Tabla 100. Primera solución mejorada obtenida tras aplicar la primera operación de la Seguiriya sobre la Red de Prueba.
Vehículo
1
2
3
4
Clientes
8 13 12 15
5 3 2 1
4 7 6 9
11 10 14
d* = 248.8613
P = [0 0 0 0]
A continuación la distancia cronotónica impone nuevamente ejecutar la
operación Exchange, que intercambia los clientes 5 y 7 tal y como ilustra la
tabla 101.
Proyecto Fin de Carrera | María Miranda Burguete
119 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
Tabla 101. Primera solución mejorada obtenida tras aplicar la segunda operación de la Seguiriya sobre la Red de Prueba.
Vehículo
1
2
3
4
Clientes
8 13 12 15
3 2 1 7
5 4 6 9
11 10 14
d* = 248.6224
P = [0 0 0 0]
El palo pasa a continuación a aplicar Merge_mod y coloca todos los clientes de
la ruta dos al final de la ruta cuatro, según indica la tabla 102.
Tabla 102. Primera solución mejorada obtenida tras aplicar la tercera operación de la Seguiriya sobre la Red de Prueba.
Vehículo
1
2
3
4
Clientes
8 13 12 15
-
5 4 6 9
11 10 14 1 2 7 3
d* = 242.9433
P = [0 0 0 0]
De manera consecutiva el palo intenta aplicar la operación Merge_mod. Sin
embargo, al aplicar de nuevo la operación tres, esta no consigue obtener una
solución mejor y el vector P se actualiza para reflejar este hecho.
P = [0 0 1 0]
Por último, para completar el palo debe aplicarse la operación Exchange. Los
clientes 5 y 14 son intercambiados y el vector P es actualizado. Como
resultado, una vez finalizada la primera iteración de la Seguiriya, la solución
Proyecto Fin de Carrera | María Miranda Burguete
120 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
obtenida es la recogida en la tabla 103.
Tabla 103. Primera solución mejorada obtenida tras aplicar la quinta operación de la Seguiriya sobre la Red de Prueba.
Vehículo
1
2
3
4
Clientes
8 13 12 15
-
4 6 9 14
11 10 1 2 7 3 5
d* = 238.2087
P = [0 0 0 0]
Para el estudio de la Seguiriya el número límite de iteraciones que converge a
la estimación de la solución óptima es igual a tres. La tabla 104 recoge los
resultados de diferentes iteraciones sobre este palo junto con el tiempo de
ejecución cumulativo. Esta columna contiene los valores desde el inicio de la
heurística de solución inicial hasta la conclusión de la iteración
correspondiente.
Tabla 104. Distancias y tiempos de ejecución obtenidos tras aplicar diferentes números de iteraciones del algoritmo de la Seguiriya sobre la Red de Prueba.
Número de Iteraciones Distancia Recorrida Tiempo de Ejecución [s]
1 238.2087 0.18
2 224.4418 0.29
≥ 3 194.4764 0.47
Por último, en la tabla 105 se recoge la estimación óptima a la que converge la
particularización del ARF para el caso exclusivo de aplicar la Seguiriya. La
distancia total recorrida es 194.4764. El tiempo empleado en la generación de
esta solución es 0.47 segundos.
Proyecto Fin de Carrera | María Miranda Burguete
121 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
Tabla 105. Mejor solución obtenida tras aplicar el algoritmo de la Seguiriya sobre la solución inicial generada por la heurística de mínima distancia sobre la Red de Prueba.
Vehículo
1
2
3
4
Clientes
8 13 12 15
-
10 9 14 11
7 6 1 2 3 4 5
7.1.3.5. Guajira
Según indica la codificación en binario de la Guajira, [0 0 1 0 0 1 0 1 0 1 0 1], la
primera operación a ejecutar es la número tres. Los resultados que se obtienen
tras aplicar la operación Merge_mod generan la asignación de todos los clientes
de la ruta cuatro al final de la dos como recoge la tabla 106.
Tabla 106. Primera solución mejorada obtenida tras aplicar la primera operación de la Guajira sobre la Red de Prueba.
Vehículo
1
2
3
4
Clientes
8 13 12 15
4 3 2 1 10 11 14
7 6 9 5
-
d* = 244.4162
P = [0 0 0 0]
A continuación debe nuevamente aplicarse la operación Merge_mod, pero
ahora sobre esta última solución. Tras realizar todos los movimientos posibles,
no se obtiene ninguna combinación de rutas que reduzca la distancia total
recorrida y el algoritmo modifica el vector P.
P = [0 0 1 0]
La lectura del palo prosigue y se aplica la operación Exchange, que intercambia
los clientes 4 y 9 reduciendo la distancia total como ilustra la tabla 107.
Proyecto Fin de Carrera | María Miranda Burguete
122 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
Tabla 107. Primera solución mejorada obtenida tras aplicar la tercera operación de la Guajira sobre la Red de Prueba.
Vehículo
1
2
3
4
Clientes
8 13 12 15
3 2 1 9 10 11 14
4 7 6 5
-
d* = 241.2494
P = [0 0 0 0]
Como dicta el algoritmo, se les ha asignado el valor cero a las componentes
del vector P tras haberse modificado la solución almacenada. Prosigue la
lectura de la Guajira y se aplica nuevamente la operación Exchange. En esta
ocasión se intercambian los clientes 3 y 6 como indica la tabla 108.
Tabla 108. Primera solución mejorada obtenida tras aplicar la cuarta operación de la Guajira sobre la Red de Prueba.
Vehículo
1
2
3
4
Clientes
8 13 12 15
2 1 6 9 10 11 14
3 4 7 5
-
d* = 233.4430
P = [0 0 0 0]
Para cerrar la ejecución de la primera iteración sobre la Guajira se ejecuta de
nuevo la operación Exchange, que en este caso intercambia los clientes 7 y 8
pertenecientes a las rutas uno y tres respectivamente, tal y como se indica en
la tabla 109.
Proyecto Fin de Carrera | María Miranda Burguete
123 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
Tabla 109. Primera solución mejorada obtenida tras aplicar la quinta operación de la Guajira sobre la Red de Prueba.
Vehículo
1
2
3
4
Clientes
7 13 12 15
2 1 6 9 10 11 14
3 4 5 8
-
d* = 231.3516
P = [0 0 0 0]
Con esta operación termina la primera iteración del algoritmo. Incrementando
el número de veces que se recorre el compás de la Guajira, se obtienen nuevas
soluciones mejoradas hasta un límite de dos iteraciones, puesto que una
tercera no produce mejora sobre la solución almacenada. Este resultado se
ilustra en la tabla 110 mientras que la tabla 111 recoge la estimación de la
solución óptima tras completar dos iteraciones de este palo.
Tabla 110. Distancias y tiempos de ejecución obtenidos tras aplicar diferentes números de iteraciones del algoritmo de la Guajira sobre la Red de Prueba.
Número de Iteraciones Distancia Recorrida Tiempo de Ejecución [s]
1 231.3516 0.19
2 211.1657 0.23
≥ 3 209.7098 0.36
Tabla 111. Mejor solución obtenida tras aplicar el algoritmo de la Guajira sobre la solución inicial generada por la heurística de mínima distancia sobre la Red de Prueba.
Vehículo
1
2
3
4
Clientes
11 12 15 13
7 2 1 6 10 9 14
3 4 5 8
-
Proyecto Fin de Carrera | María Miranda Burguete
124 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
7.1.3.6. Análisis y comparación de resultados
Los diferentes valores obtenidos tras la aplicación de los principales palos del
flamenco por separado sobre la Red de Prueba se encuentran recopilados en
las tablas 112 y 113. En éstas se incluyen los tiempos de ejecución, el número
límite de iteraciones para estimar la solución óptima y la distancia total
correspondiente a la dicha estimación para cada palo.
Como puede observarse, la Soleá, la Seguiriya y la Bulería generan los conjuntos
de rutas de mínima distancia, sin embargo, ha sido necesario realizar varias
iteraciones de cada palo para lograr dichas estimaciones del óptimo,
empleando un tiempo mayor en la obtención de estas soluciones debido a la
necesidad de inspeccionar un mayor número de candidatos.
En un lugar intermedio se encuentra la Guajira, la cual alcanza su mejor
solución tras realizar tres iteraciones sobre el palo. Si se observa el tiempo
medio de todas las operaciones por iteración, puede observarse que todos los
palos salvo el Fandango requieren aproximadamente entre 0.1 y 0.3 segundos
por iteración. Este resultado se debe a la combinación de operaciones que
existe en dichos palos mientras que el Fandango posee una única operación
que repite constantemente y cuyo éxito o fracaso determina el tiempo total de
ejecución.
Tabla 112. Tiempos de Ejecución y número de iteraciones de los algoritmos independientes de cada palo sobre la solución inicial obtenida con la heurística de mínima distancia sobre la Red de Prueba.
Tiempo de ejecución
[s]
Número de
iteraciones
Fandango
Soleá
Bulería
Seguiriya
Guajira
0.02
1.38
1.10
0.47
0.36
1
5
5
3
3
El Fandango resulta ser, en este caso, el palo que produce una menor mejora
sobre la solución inicial. Este resultado está ligado a la codificación
cronotónica de este palo. Así, aplicar el algoritmo adaptado al Fandango
Proyecto Fin de Carrera | María Miranda Burguete
125 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
equivale a ejecutar la operación tres sucesivas veces. El hecho de que este palo
se limite a una sola operación reduce las posibilidades de encontrar una
mejora drásticamente.
Como ya se ha discutido reiteradamente, los resultados recogidos en las tablas
112 y 113 están intrínsecamente ligados a la red simplificada de partida así
como al método de extracción de la solución inicial. En caso de realizar el
mismo estudio sobre una solución inicial diferente, los resultados variarán en
mayor o menor grado.
Tabla 113. Distancias obtenidas tras aplicar los algoritmos independientes de cada palo sobre la solución inicial obtenida con la heurística de mínima distancia sobre la Red de Prueba.
Distancia total recorrida
Solución inicial 255.1073
Fandango
Soleá
Bulería
Seguiriya
Guajira
244.4162
198.2030
189.2158
194.4764
209.7098
Con objeto de recalcar la importancia de esta consideración, se ha ejecutado la
versión del ARF particularizada para cada palo sobre la solución inicial
obtenida al aplicar la heurística de demanda máxima sobre la Red de Prueba.
En la tabla 114 se incluyen los valores obtenidos para la función objetivo en
dichos estudios, es decir, la distancia total recorrida por los cuatro vehículos
tras aplicar cada palo de forma iterativa un numero límite de iteraciones tal
que se produce convergencia a una única estimación de la solución óptima.
Observando los resultados sobre la solución inicial de demanda máxima se
comprueba que los palos que alcanzan un mayor grado de mejora son la Soleá
y la Bulería. El Fandango, la Seguiriya y la Guajira, palos que solo incluyen las
operaciones dos y tres (Exchange y Merge_mod), convergen a estimaciones
optimas de peor calidad.
Proyecto Fin de Carrera | María Miranda Burguete
126 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
Tabla 114. Distancias obtenidas tras aplicar los algoritmos independientes de cada palo sobre la solución inicial obtenida con la heurística de demanda máxima sobre la Red de Prueba.
Distancia total recorrida
Solución inicial 365.3890
Fandango
Soleá
Bulería
Seguiriya
Guajira
328.4780
189.2158
189.2158
239.9938
229.9473
Los resultados recogidos en la tabla 114 nuevamente se corresponden con el
valor límite tras la aplicación de un número máximo de diez iteraciones sobre
cada palo. Sin embargo, en ningún caso ha sido necesario alcanzar dicho
número de iteraciones por producirse la convergencia previamente.
Comparando las tablas 113 y 114 puede observarse como la mejor de las
estimaciones óptimas coincide para ambas soluciones iniciales. No obstante,
en el caso de la solución inicial por demanda máxima, un total de dos palos
diferentes (Soleá y Bulería) consiguen alcanzar esta solución frente a un único
palo (Bulería) en el caso de la solución inicial por distancia mínima.
Este sorprendente resultado confirma dos características muy importantes de
los métodos de búsqueda local. La primera de ellas se refiere a que la
estimación óptima no debe estar ligada a una solución inicial estructurada de
manera ordenada sino que es altamente dependiente de la capacidad de
inspección y mejora que presentan las operaciones de búsqueda local. La
segunda de ellas es que en esta ocasión no se ha permitido al algoritmo tomar
soluciones intermedias que empeoren la función objetivo respecto a la
solución anterior pero que podrían conducir a mejoras mayores al cambiar el
espacio de candidatos analizados. Al carecer de este principio, ambas
soluciones iniciales convergen a una misma distancia mínima al aplicar las
operaciones de búsqueda local.
En la figura 26 se representa gráficamente el porcentaje de distancia total
recorrida que consigue reducir cada uno de los palos aplicados a la solución
inicial para las dos opciones consideradas. Si bien los valores no resultan
próximos, si es claro observar una tendencia en los resultados. Para ambas
Proyecto Fin de Carrera | María Miranda Burguete
127 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
soluciones iniciales, tanto la Soleá como la Bulería producen mejoras notables.
Esto se debe en buena parte al contenido en operaciones de dichos palos.
Mayoritariamente constituidos por distancias cronotónicas de una y dos
unidades entre compases acentuados, en estos palos las operaciones Relocate y
Exchange, que analizan un espectro más amplio de posibles candidatos, se
suceden. Esto ayuda a producir un mayor avance en el camino hacia la
solución óptima estimada.
Por otro lado, el Fandango, palo que conduce al algoritmo a emplear
únicamente la operación Merge_mod sucesivamente, produce una mejora casi
marginal para el caso de la solución inicial de mínima distancia y mucho
menor que el resto de los palos para la solución inicial por la heurística de
demanda máxima.
En adición, los valores recogidos en la figura 26 indican que la mejora
porcentual desde la solución inicial de demanda máxima es del orden del
doble que la alcanzada para el caso de distancia mínima. Este resultado
confirma la eficacia en la búsqueda de una estimación óptima que se consigue
de la combinación de las diferentes operaciones de búsqueda local
consideradas en este proyecto. Así, la búsqueda exhaustiva de una estimación
óptima profundiza más cuanta menor es la estructuración de la solución
inicial.
Figura 26. Grafica comparativa de la mejora porcentual del algoritmo particularizado para cada palo respecto a la solución inicial en la Red de Prueba.
Proyecto Fin de Carrera | María Miranda Burguete
128 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
No debemos olvidar que esta comparativa se ha realizado utilizando la misma
red modelo y en ella únicamente se han comparado los efectos de cada palo
sobre dos soluciones iniciales diferentes. Por lo tanto la validez de estas
conclusiones puede ser fácilmente rechazada. Sin embargo, existen dos
componentes clave en la eficacia de las operaciones que aquí se han visto
claramente evidenciados.
En primer lugar, aquellas operaciones capaces de barajar un mayor número de
movimientos candidatos son más susceptibles de alcanzar una mejora. En
adición, la flexibilidad con la que una operación puede alterar la solución de
partida es clave para permitir un número elevado de iteraciones con la misma
que produzcan una mejora en la mejor solución obtenida hasta el momento.
7.1.4. ARF
Habiendo aplicado con éxito las operaciones de manera aislada y el algoritmo
particularizado para los palos contemplados, en este apartado se describe la
aplicación del algoritmo completo, ARF, sobre la Red de Prueba. El ARF recorre
los cinco palos del flamenco elegidos de manera consecutiva. Sus componentes
y el procedimiento llevado a cabo por el algoritmo se detallan en el apartado 5.4
de esta memoria, quedando pendiente la definición del orden en el que se
ejecutan los palos en el algoritmo. Por ello, en este apartado se incluye en
primer lugar un estudio realizado con Matlab para elegir el orden óptimo de
aplicación de los mismos, y una vez completada la definición del ARF con la
elección de un orden fijo, se utiliza el algoritmo para resolver la Red de Prueba.
Puesto que en este trabajo se han considerado cinco palos diferentes de
flamenco, p=5, existen 5! combinaciones validas para recorrer los mismos sin
que se produzca la repetición de ninguno de ellos. Es decir, existen 5!=120
permutaciones posibles. Cada combinación de palos da lugar a una matriz M
diferente.
Buscando la extracción de un orden de aplicación de los cinco palos
considerados dentro del ARF, se ha diseñado un algoritmo de prueba que
genera las 120 combinaciones posibles y resuelve la Red de Prueba aplicando el
ARF con cada una de ellas. En este algoritmo los palos han sido identificados
por un índice tal y como se describe en la tabla 115. Al finalizar las iteraciones,
el algoritmo proporciona el orden de los palos que ha generado la solución de
mínima distancia.
En cada caso se ha realizado una sola iteración del ARF, es decir, cada vez que
se aplica el ARF con una nueva matriz de palos M, ésta se recorre una sola vez.
Dado el número de permutaciones existentes, se ha optado por limitar el
número de veces que se recorre la matriz de palos con el objeto de evitar un
Proyecto Fin de Carrera | María Miranda Burguete
129 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
incremento excesivo del tiempo de ejecución. Para respaldar esta asunción, se
ha comprobado que debido a la simplicidad de la red considerada, un
incremento del número de iteraciones sobre la matriz M en general no produce
variaciones significativas sobre los resultados alcanzados.
Tabla 115. Numeración de los palos del flamenco.
Numeración Palo del flamenco
1
2
3
4
5
Fandango
Soleá
Bulería
Seguiriya
Guajira
La tabla 116 recoge los resultados obtenidos en el estudio. En esta tabla los
resultados de las permutaciones entre los palos se han incluido siguiendo el
orden en el que dichas permutaciones son generadas, por lo que los resultados
de la función objetivo no aparecen ordenados Nótese que muchas soluciones
no han sido incluidas por razones de claridad. Adicionalmente, los resultados
revelan que distintos órdenes de los palos proporcionan el mismo valor de
distancia mínima. De entre éstos, el algoritmo ha tomado como óptimo la
primera de las permutaciones que genera dicho resultado.
Tabla 116. Distancias obtenidas con el ARF para diferentes órdenes de los palos del flamenco tras una iteración sobre la matriz de palos en la Red de Prueba.
Número de iteración Orden de los palos Distancia total recorrida
1
2
3
4
5
…
27
…
119
120
[5 4 3 2 1]
[5 4 3 1 2]
[5 4 2 3 1]
[5 4 2 1 3]
[5 4 1 2 3]
…
[4 5 2 3 1]
…
[1 5 4 2 3]
[1 5 4 3 2]
199.5357
199.5357
201.0426
201.0426
201.0426
…
189.2158
…
189.2158
189.2158
Proyecto Fin de Carrera | María Miranda Burguete
130 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
De estos resultados se deduce que entre las permutaciones que generan la
solución de mínima distancia, la número 27 es elegida como el orden óptimo de
aplicación de los palos (sobre la red simplificada) es:
I. Seguiriya
II. Guajira
III. Soleá
IV. Bulería
V. Fandango
De igual modo, la matriz M extraída de este estudio es la siguiente:
Con el orden de aplicación de los palos elegido, el algoritmo por ritmos del
flamenco, ARF, queda completamente definido siguiendo el contenido de la
sección 5.4.
La segunda parte de este apartado se centra en aplicar el ARF sobre la Red de
Prueba. El procedimiento seguido se ilustra paso a paso a continuación.
Se comienza recorriendo la fila uno de M, correspondiente a la Seguiriya. La
variable S* contiene al inicio del algoritmo la solución inicial obtenida con la
heurística de mínima distancia. Tal y como se detalla en el apartado 7.1.3.4., la
solución obtenida después de aplicar una iteración de la Seguiriya partiendo de
la solución inicial se recoge en la tabla 117.
Tabla 117. Mejor solución obtenida tras aplicar las operaciones de la Seguiriya. ARF sobre Red de Prueba – paso 1.
Vehículo
1
2
3
4
Clientes
8 13 12 15
-
4 6 9 14
11 10 1 2 7 3 5
Proyecto Fin de Carrera | María Miranda Burguete
131 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
Siendo la distancia total recorrida igual a 238.2087. Estos valores permanecen
almacenados en las variables S* y d*, respectivamente, cuando se termina de
recorrer este palo.
En este momento se incrementa el contador C en una unidad, indicando al
algoritmo que debe leer la segunda fila de la matriz M. Tras aplicar las
operaciones correspondientes a la Guajira, se obtienen los resultados descritos
en la tabla 118.
Tabla 118. Mejor solución obtenida tras aplicar las operaciones de la Guajira. ARF sobre Red de Prueba – paso 2.
Vehículo
1
2
3
4
Clientes
13 12 15 11
-
7 6 9 14
10 1 2 3 4 5 8
d* = 224.4418
La siguiente fila de la matriz de palos corresponde a la Soleá. En la tabla 119 se
recoge la solución obtenida tras ejecutar las operaciones que integran dicho
palo, seguida de la distancia total recorrida por los vehículos.
Tabla 119. Mejor solución obtenida tras aplicar las operaciones de la Soleá. ARF sobre Red de Prueba – paso 3.
Vehículo
1
2
3
4
Clientes
8 13 15 12
-
10 9 14 11
7 6 1 2 3 4 5
d* = 190.8032
Continuando la lectura de las filas de la matriz M, se ejecutan las operaciones
de la Bulería y se genera la solución contenida en la tabla 120.
Proyecto Fin de Carrera | María Miranda Burguete
132 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
Tabla 120. Mejor solución obtenida tras aplicar las operaciones de la Bulería. ARF sobre Red de Prueba – paso 4.
Vehículo
1
2
3
4
Clientes
8 13 15 12
-
10 9 14 11
7 6 1 2 3 5 4
d* = 189.2158
Por último, se aplica el Fandango. Este palo, que equivale a aplicar cuatro veces
la operación Merge_mod, no consigue obtener una solución mejor a la última
almacenada. En consecuencia, finaliza el algoritmo sin modificarse por tanto los
valores de S* y d*.
El tiempo de ejecución empleado por Matlab en realizar una iteración del ARF
sobre la Red de Prueba es igual a 0.95 segundos. En la tabla 121 se recoge el
tiempo cumulativo desde el inicio del algoritmo completo hasta que finaliza la
ejecución de cada uno de los palos que constituyen la matriz M.
Tabla 121. Tiempos de ejecución cumulativos para cada palo en una iteración del ARF sobre la Red de Prueba.
Tiempo de ejecución acumulado [s]
Solución inicial 0.023
Soleá
Seguiriya
Guajira
Bulería
Fandango
0.200
0.307
0.637
0.940
0.945
Proyecto Fin de Carrera | María Miranda Burguete
133 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
Los resultados permiten observar que el tiempo de ejecución se distribuye de
manera heterogénea entre las operaciones. Nótese como el Fandango es
ejecutado en un intervalo de tiempo llamativamente reducido, ya que no es
capaz de generar ninguna mejora sobre la solución temporal.
Tal y como se ha descrito con anterioridad, la ejecución de cada una de las
cuatro operaciones consideradas en este proyecto conlleva el estudio de un
conjunto de soluciones candidatas diferentes. Sin embargo, la cantidad de
movimientos exitosos que cada uno de los palos completa está severamente
limitada por las condiciones de partida. Es decir, si un palo no consigue mejorar
la solución almacenada en la variable S* aplicando una determinada operación
y dicha operación constituye el inicio del palo consecutivo, la ejecución de este
último se verá acelerada por la obligación de ignorar una primera operación
que no podría introducir mejora.
7.2. Resolución problema de enrutado de vehículos
En esta sección se implementa el ARF sobre variaciones del problema de enrutado de
vehículos resuelto en R. Grosso [6]. Para la definición del problema de partida, que
mantiene las restricciones introducidas durante la particularización del VRP en este
proyecto, se ha tomado del trabajo del autor citado el número de vehículos disponibles,
así como la capacidad de cada uno de éstos, que para este problema son variables.
A continuación también se describe la ubicación de la empresa de distribución (nodo
referido hasta ahora como almacén) y la de todos los clientes, además de la demanda
de cada cliente en kilogramos de producto a distribuir. Se asume en consecuencia que
la producción del nodo almacén es suficiente para abastecer a todos los clientes que
conforman el problema. Las restricciones que aplican al conjunto de soluciones
admisibles se suponen las mismas que se han descrito y empleado sobre la Red de
Prueba simplificada. Las tablas 122 y 123 recogen los datos del problema.
Tabla 122. Capacidades de los vehículos. Datos del problema a resolver [6].
Vehículo Capacidad [kg]
1
2
3
4
3000
3000
4500
4500
Proyecto Fin de Carrera | María Miranda Burguete
134 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
Tabla 123. Localización y demandas del almacén y los clientes del problema [6].
Número de cliente Coordenda x Coordenada y Demanda [kg]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
218
159
207
126
212
125
215
126
175
218
119
180
152
188
224
210
104
116
126
119
153
184
201
125
214
129
115
188
207
358
331
392
347
394
355
389
338
363
382
340
360
349
393
370
382
354
355
335
357
351
410
370
346
371
349
341
357
406
3100
1500
1000
950
800
550
500
450
400
300
300
300
300
300
200
150
150
150
150
150
150
150
125
125
100
100
100
100
100
Almacén 132 354 -
Proyecto Fin de Carrera | María Miranda Burguete
135 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
El primer paso seguido por el ARF consiste en la extracción de una solución inicial
admisible. En este punto se da prioridad a la heurística de mínima distancia y en caso
de fracasar esta última, se aplicaría la heurística de demanda máxima. Para las
condiciones de este problema, la heurística de mínima distancia converge en una
solución admisible que se describe en la tabla 124. Siendo la distancia total recorrida
igual a 692.0219.
Tabla 124. Solución inicial del problema [6] dada por la heurística de mínima distancia.
Vehículo
1
2
3
4
Clientes
21 2 19 8 11 27 18
13 26 4 24 6 20 17 14
1 15 25 10 7 29 22
9 12 28 23 16 3 5
Capacidad disponible
200
375
50
1625
2250
A continuación se aplica el ARF recorriendo las filas de la matriz de palos M obtenida
en la sección 7.1.4 a partir de la red simplificada. En las tablas 125 a 127 se muestran las
combinaciones de rutas obtenidas para las cuatro primeras iteraciones del algoritmo
completo sobre el problema propuesto en R. Grosso [6].
1ª iteración
Tabla 125. Solución del problema [6] obtenida con una iteración del ARF.
Vehículo
1
2
3
4
Clientes
2 19 8 11 27 17 18 20
21 13 26 4 24 6
28 1 15 10 7 29 22
12 14 23 25 16 3 5 9
Capacidad disponible
50
825
50
1325
2250
Proyecto Fin de Carrera | María Miranda Burguete
136 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
2ª iteración
Tabla 126. Solución del problema [6] obtenida con dos iteraciones del ARF.
Vehículo
1
2
3
4
Clientes
2 19 8 11 27 17 18 20
21 13 26 4 24 6
12 23 3 5 7 16 9
28 1 15 25 10 29 22 14
Capacidad disponible
50
825
1225
150
2250
3ª iteración
Tabla 127. Solución del problema [6] obtenida con tres iteraciones del ARF.
Vehículo
1
2
3
4
Clientes
21 13 26 4 24 6
2 19 8 11 27 17 18 20
12 3 5 7 16 23 9
28 1 15 25 10 29 22 14
Capacidad disponible
825
50
1225
150
2250
La distancia total recorrida obtenida para cada solución y el tiempo de ejecución
empleado en cada caso se recogen en la tabla 128, que analiza el progreso del ARF.
Para la resolución de este problema se ha empleado el mismo equipo informático que
en el caso del apartado 7.1 y nuevamente se ha almacenado el tiempo de ejecución de
cada una de las iteraciones del ARF completo. Estos valores, junto con los cambios
introducidos en la función objetivo permiten evaluar la eficacia del algoritmo.
Para realizar un análisis de los resultados obtenidos se han calculado los siguientes
parámetros:
- El porcentaje de mejora en la distancia total de cada solución obtenida
respecto a la solución inicial.
- El porcentaje de mejora en la distancia total de cada solución respecto a la
Proyecto Fin de Carrera | María Miranda Burguete
137 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
solución obtenida en la iteración anterior.
- El porcentaje de incremento de tiempo que se produce al aumentar el número
de iteraciones en uno, respecto al tiempo empleado en la iteración anterior.
Tabla 128. Distancias recorridas y tiempos de ejecución empleados para diferentes números de iteraciones del ARF sobre el problema [6].
Número de iteraciones Distancia recorrida Tiempo de ejecución [s]
1
2
3
609.3138
578.3104
576.2175
2.93
15.13
19.13
Solución inicial 692.0219 0.03
Tabla 129. Análisis de los resultados de distintitas iteraciones del ARF sobre el problema [6].
Número de
iteraciones
% Mejora respecto a
la solución inicial
% Mejora respecto a
la iteración anterior
% Incremento de
tiempo
1
2
3
11.95
16.43
16.73
11.95
5.09
0.36
-
416.38
26.44
Una vez resuelto el problema genérico, se introducirán a continuación variaciones de
este último a las que se aplicará el ARF. Estas variaciones se basan en la modificación
de la capacidad de los vehículos disponibles en combinación con la penalización del
uso de los vehículos de mayor capacidad. En el contexto de un problema de
distribución complejo, esta condición correspondería con la priorización del uso de
vehículos de bajo tonelaje, cuya mayor agilidad permitiría minimizar los tiempos de
reparto.
Es fácil intuir que un camión viajará más lento cuanto mayor sea su capacidad,
ignorando consideraciones de propulsión, aerodinámica u otros. Por ello, al margen de
condiciones como costes de mantenimiento de flota, consumo de combustible o
eficiencia se asume en estos casos que para la empresa de distribución es más
beneficioso emplear los vehículos de bajo tonelaje. Bajo esta simplificación, se
Proyecto Fin de Carrera | María Miranda Burguete
138 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
incorporan nuevas condiciones al problema, de manera que la distancia virtual entre
clientes será mayor para los camiones de mayor capacidad.
En este punto es importante mencionar que el algoritmo implementado en este
proyecto usando Matlab ha debido ser adaptado para la resolución de estas variaciones
con penalización por distancia. Estas modificaciones han sido omitidas en este
apartado con objeto de centrar la atención del lector en la comparación de resultados.
Sin embargo, los algoritmos para la obtención de la solución inicial no se ven afectados
por estas penalizaciones ya que las rutas son completadas de manera independiente y
en un orden predeterminado por el algoritmo. En otros términos, las localizaciones de
clientes para la misma ruta se ven penalizadas por el mismo factor por lo que el orden
en que los clientes son seleccionados no se ve alterado.
Con el ARF adaptado para la inclusión de penalizaciones sobre los vehículos de mayor
tonelaje, se han solucionado una serie de casos particulares cuyas condiciones son
descritas a continuación. En todos los casos se han considerado vehículos con
capacidad igual a 3500 unidades (bajo tonelaje) y 4500 unidades (medio tonelaje) y se
ha variado la penalización en distancia impuesta a los vehículos de mayor capacidad.
Desde el punto de vista de la implementación del algoritmo, esto se traduce en la
utilización de una matriz de distancias modificada para los camiones de 4500 unidades
de capacidad, obtenida de la multiplicación de la matriz original por un factor m mayor
que la unidad. Las distintas variaciones o casos particulares que han sido resueltos
sobre la red de clientes descrita en la tabla 123 se caracterizan por tres elementos
diferenciadores: El valor del factor de penalización m, el criterio seguido para ordenar
los clientes y el vector de capacidad, cap. Este último define el número de vehículos
disponibles, su capacidad y el orden en el que son considerados
En la siguiente lista se describen los casos particulares resueltos mediante la
especificación del valor del factor m, el vector capacidad y el criterio de orden de los
clientes. Por defecto, dicho orden se corresponde con la numeración de la tabla 123 y se
indica exclusivamente en los casos en los que ha sido modificado, véase los casos 5 y 6.
1) m=2 cap=[4500 4500 3000 3000]
2) m=2 cap=[4500 4500 4500]
3) m=2 cap=[4500 3000 3000 3000]
4) m=1.5 cap=[4500 4500 3000 3000]
5) m=1.5 cap=[4500 4500 3000 3000]
Clientes ordenados según proximidad al depósito.
Proyecto Fin de Carrera | María Miranda Burguete
139 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
6) m=1.5 cap=[4500 4500 3000 3000]
Clientes ordenados en orden inverso por proximidad al depósito,
es decir, de mayor a menor distancia al almacén.
7) m=1.5 cap=[4500 4500 4500]
8) m=1.5 cap=[4500 3000 3000 3000]
9) m=2 cap=[3000 3000 4500 4500]
10) m=1.5 cap=[3000 3000 4500 4500]
11) m=1 cap=[3000 3000 4500 4500]
12) m=1 cap=[4500 4500 3000 3000]
La tabla 130 contiene una comparativa de los resultados obtenidos para las variaciones
de este problema mediante el ARF y el método de búsqueda local implementado en R.
Grosso [6]. Tal y como puede observarse, los resultados son muy parejos y se
encuentran en su mayoría dentro de una franja del 5% de diferencia, generando una
distancia total menor para el ARF en un total de cinco casos sobre doce resueltos en
total. En la tabla 130 se han incluido los tiempos de ejecución del ARF empleando el
equipo informático que se describe en la sección 7.1.2.
El ARF produce una mejora marginal en los casos uno, cinco, ocho y nueve, problemas
en los que se aplica penalización por distancia y combinan el mismo número de
camiones de diferente capacidad. Sin embargo, si se compara la solución del caso
cuatro con el caso diez puede extraerse una importante conclusión. Estos dos casos
particulares comparten el valor del factor m y el número de camiones de capacidad
igual a 4500 y 3500 unidades, sin embargo presentan diferente orden de dichos
vehículos dentro del vector de capacidades.
Dado que el ARF es capaz de producir una mejora en el caso cuatro pero genera una
peor solución para el caso diez, y tal y como ya se ha hecho hincapié en apartados
anteriores, este resultado confirma la elevada sensibilidad de las rutas que este
algoritmo genera respecto a variaciones en la solución inicial. Al ordenar los vehículos
de una manera diferente, el algoritmo de solución inicial genera rutas iniciales
diferentes y las operaciones de búsqueda local son incapaces de compensar por esta
condición inicial.
En los casos en los que el ARF proporciona una distancia total considerablemente
superior, los problemas dos, siete y doce, el factor de penalización m carece de efecto
sobre las condiciones del problema por tratarse de flotas de vehículos homogéneas o
Proyecto Fin de Carrera | María Miranda Burguete
140 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
por tomar dicho factor un valor unitario. Este resultado prueba el hecho de que la
penalización por capacidad puede integrarse dentro del ARF con resultados muy
satisfactorios. Además, los casos dos y doce presentan un menor número de vehículos
disponibles, lo cual reduce el espacio de candidatos analizados por las operaciones de
búsqueda local. Por otro lado, la diferencia entre los resultados de los casos once y doce
recalca de nuevo el peso del algoritmo para la solución inicial dentro del ARF.
Tabla 130. Resultados de la aplicación del ARF a las variantes resueltas en R.Grosso [6].
Caso Tiempo ejecución
ARF [s]
Distancia por
ARF
Distancia en
R.Grosso [6] % Diferencia
1 22.85 873.5 905.7 - 3.6
2 26.72 1321.9 1120.6 18.0
3 10.01 799.0 778.1 2.7
4 11.98 745.4 786.2 - 5.2
5 30.62 699.8 709.1 - 1.3
6 11.83 745.4 709.1 5.1
7 43.93 915.2 840.5 8.9
8 14.4 677.5 693.2 - 2.3
9 12.81 858.5 875.2 - 1.9
10 12.70 753.9 714.3 5.5
11 22.62 576.2 555.1 3.8
12 19.29 588.7 522.5 12.7
La inspección de los resultados recogidos en la tabla 130 podría conducir al lector hacia
un juicio negativo sobre el ARF, sin embargo estos resultados deben ser analizados de
forma crítica considerando la propia definición del algoritmo. En el apartado 7.1.4 se
optó por fijar el orden de aplicación de los palos del flamenco considerados en la
Proyecto Fin de Carrera | María Miranda Burguete
141 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
implementación del ARF. De esta manera y siguiendo el contenido de la sección 5.4 se
daba por zanjada la definición del algoritmo, dando prioridad al establecimiento de un
orden de aplicación de dichos palos optimizado mediante una red de clientes específica
sobre la repetición del costoso proceso iterativo de extracción de un orden óptimo.
Ahora bien, la elección de dicho orden se realizó sobre las premisas de mejorar el
resultado que el ARF producía para la Red de Prueba descrita en la figura 19. Esto
implica que dicho orden compromete las posibilidades de optimización del algoritmo
para su aplicación a redes de clientes que difieren de esta última.
La decisión de cerrar la definición del ARF con la inclusión de un orden de aplicación
de los palos del flamenco se tomó considerando que la aplicación de este algoritmo,
que genera una estimación de la solución óptima sobre una variante simplificada del
VRP, debía realizarse en el menor tiempo de computación posible. No obstante, en esta
sección y con motivo de explorar el potencial completo de mejora del algoritmo
introducido, se ha definido una variante del mismo, el Algoritmo por los Ritmos del
Flamenco Adaptado, en la que se intenta optimizar el orden de aplicación de los palos
considerados para cada caso particular descrito en este apartado.
Tal y como se recoge en la sección 7.1.4, a la que se refiere al lector para una
descripción completa, la elección de un orden óptimo de aplicación de los cinco palos
del flamenco considerados en este proyecto pasa por la solución de un total de ciento
veinte posibles combinaciones en las que no se repite ninguno de los palos y la elección
de aquella que genera la distancia total mínima. A diferencia del procedimiento
seguido con anterioridad, el ARF Adaptado selecciona el orden de aplicación de los
palos que produce la máxima mejora tras la ejecución de un máximo de quince
iteraciones sobre la matriz de palos o hasta la convergencia a una estimación que no
puede ser mejorada por el algoritmo.
Como consecuencia de la adición de un bucle de mejora dentro del que se engloban
múltiples iteraciones en la ejecución del ARF Adaptado, en igualdad de condiciones de
potencia computacional, este algoritmo requiere tiempos de ejecución dos órdenes de
magnitud superiores a los resultantes por el ARF, lo que supone una significativa
disminución en la eficiencia computacional del algoritmo.
En la tabla 131 se recogen los resultados obtenidos tras la aplicación del ARF Adaptado a
las doce variaciones del problema resuelto en R.Grosso [6]. En esta tabla se ha incluido
el orden de aplicación de los palos extraído del bucle de optimización así como el
grado de mejora que se consigue sobre la aplicación directa del ARF. Nótese que los
números asignados a cada uno de los palos considerados (Soleá, Bulería, etc.) siguen la
notación descrita en la tabla 115. Adicionalmente, los tiempos de ejecución empleando
el equipo informático que se describe en la sección 7.1.2 y expresados en segundos se
han incluido también en la tabla 131.
Proyecto Fin de Carrera | María Miranda Burguete
142 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
Tabla 131. Mejora en la solución de las variantes descritas en R.Grosso [6] con la aplicación del ARF Adaptado en comparación con el ARF.
Caso Orden palos Distancia por
ARF Adaptado
Distancia por
ARF % Mejora
1 [3 2 5 4 1] 832.3 873.5 4.7
2 [5 3 2 1 4] 1090.3 1321.9 17.5
3 [4 5 3 2 1] 754.9 799.0 5.5
4 [5 4 3 2 1] 699.8 745.4 6.1
5 [5 4 2 3 1] 699.8 699.8 0
6 [5 4 3 2 1] 699.8 745.4 6.1
7 [2 3 5 4 1] 821.2 915.2 10.2
8 [3 4 2 5 1] 670.1 677.5 1.1
9 [5 2 3 4 1] 848.3 858.5 1.2
10 [3 4 5 2 1] 745.4 753.9 1.1
11 [2 4 5 3 1] 555.7 576.2 3.6
12 [5 4 3 2 1] 562.7 588.7 4.4
En la totalidad de las variaciones, salvo un único caso, el ARF Adaptado consigue
mejorar la solución obtenida por el ARF. Sin embargo, el nivel de mejora es muy
reducido para justificar el acusado incremento en el tiempo de ejecución. La variación
en la que no se consigue mejora, respeta el orden respecto al fijado en el ARF. A partir
de estos resultados es posible concluir que la capacidad de optimización del ARF
presenta una gran sensibilidad a la elección de un orden de aplicación de los palos
considerados. Esta característica se debe fundamentalmente a la diferencia entre las
distintas operaciones de búsqueda local y el modo en el que cada una de éstas afecta y
predispone el espacio de candidatos estudiados por la operación que le sucede.
Proyecto Fin de Carrera | María Miranda Burguete
143 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
La observación de los resultados permite comprobar que en todas las ocasiones, a
excepción de la variación número 2, el Fandango (palo 1) ocupa la última posición en el
orden óptimo. Recuérdese que este palo está constituido exclusivamente por la
operación Merge_mod, por lo que presenta una capacidad de mejora limitada y una alta
probabilidad de no producir cambios cuando el método se aproxima a una estimación
óptima local. Así, el orden óptimo de los palos prioriza la combinación de operaciones
diferentes, lo cual produce un avance en la optimización más pronunciado.
En la tabla 132 se recogen los tiempos de ejecución de los dos algoritmos propuestos
(ARF y ARF Adaptado) para recalcar el ahorro de tiempo que supone fijar el orden de
aplicación de los palos frente a la optimización de éste para cada caso.
Tabla 132. Comparativa de los tiempos de ejecución sobre las variantes descritas en R. Grosso [6] empleando el ARF y ARF Adaptado.
Caso Tiempo ejecución ARF Tiempo de ejecución por ARF
Adaptado
1 22.85 3043.0
2 26.72 3899.9
3 10.01 2066.9
4 11.98 2202.3
5 30.62 3439.1
6 11.83 3168.5
7 43.93 5038.0
8 14.4 1745.2
9 12.81 3021.8
10 12.70 2857.8
11 22.62 2599.4
12 19.29 3190.0
Proyecto Fin de Carrera | María Miranda Burguete
144 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
Finalmente, la tabla 133 contiene una comparativa entre las soluciones generadas por el
algoritmo desarrollado en R.Grosso [6] y el ARF Adaptado. Siguiendo el patrón
observado en la tabla 130, puede observarse como este algoritmo es incapaz de
converger a la misma solución cuando el orden en el que se incluyen los vehículos en el
vector capacidad se ve modificado.
Tabla 133. Resultados de la aplicación del ARF Adaptado a las variantes resueltas en R. Grosso [6].
Caso Tiempo de ejecución
por ARF Adaptado
Distancia por
ARF Adaptado
Distancia en
R.Grosso [6] % Diferencia
1 3043.0 832.3 905.7 - 8.1
2 3899.9 1090.3 1120.6 - 2.7
3 2066.9 754.9 778.1 - 3.0
4 2202.3 699.8 786.2 - 11.0
5 3439.1 699.8 709.1 - 1.3
6 3168.5 699.8 709.1 - 1.3
7 5038.0 821.2 840.5 - 2.3
8 1745.2 670.1 693.2 - 3.3
9 3021.8 848.3 875.2 - 3.1
10 2857.8 745.4 714.3 4.4
11 2599.4 555.7 555.1 0.1
12 3190.0 562.7 522.5 7.7
Adicionalmente, los casos en los que el ARF Adaptado obtiene una mayor mejora, los
casos uno y cuatro, comparten idéntico vector capacidad mientras que en los casos en
los que existe un menor número de vehículos disponibles, problemas dos y siete, el
algoritmo produce distancias totales significativamente mayores. Sin embargo, es
Proyecto Fin de Carrera | María Miranda Burguete
145 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
difícil extraer conclusiones válidas de estos resultados ya que en el caso 12, en el que
los vehículos de mayor tonelaje toman preferencia dentro del vector capacidad, se
produce el peor resultado en comparación con el método aplicado por R. Grosso [6].
Los resultados descritos en este apartado confirman la capacidad de mejora que
presenta el ARF y que fundamentalmente viene dada por el espacio de candidatos
considerados por las operaciones de búsqueda local. Sin embargo, la selección de un
orden fijo de aplicación de los palos del flamenco con objeto de reducir el tiempo de
computación, implica que dicha capacidad de mejora se vea ligeramente acotada. El
ARF Adaptado ha sido introducido como alternativa para contrarrestar dicha limitación
sacrificando el tiempo de ejecución. Con este último algoritmo, se han alcanzado con
éxito aproximaciones a la solución óptima cuya eficacia equipara e incluso supera la de
otros métodos de optimización por búsqueda local de uso extendido.
Proyecto Fin de Carrera | María Miranda Burguete
146 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
8. CONCLUSIÓN
La última sección del documento se divide en dos apartados diferenciados. En el
primer punto se incluye una recopilación de los pasos llevados a cabo durante la
elaboración del proyecto mediante la descripción de cada una de las fases realizadas. El
segundo apartado contiene un comentario crítico sobre los métodos aplicados y los
resultados alcanzados en este proyecto, así como las limitaciones y virtudes del
algoritmo diseñado. Además, en esta sección se realizan algunas propuestas de trabajo
futuro para ampliar el campo de investigación de este trabajo.
8.1. Resumen
En este proyecto se ha desarrollado un algoritmo de optimización de búsqueda por
trayectoria basado en las representaciones cronotónicas de los compases que
identifican los principales palos del flamenco. La heurística diseñada ha sido empleada
para la resolución de una particularización simplificada del problema de enrutado de
vehículos, VRP. Esta metodología engloba la aplicación de diferentes operaciones de
búsqueda local sobre soluciones transitorias hasta la convergencia a una estimación de
la solución óptima dentro del conjunto de soluciones admisibles.
En primer lugar, se ha realizado una introducción al género musical del flamenco.
Partiendo de la definición de tiempo y compás se ha introducido el concepto de palo
flamenco y se han descrito las variantes dominantes en el arte flamenco tradicional y
contemporáneo. A continuación, se ha desarrollado el concepto de distancia
cronotónica con objeto de representar gráficamente el compás de los palos flamencos.
La sección dedicada a este género musical finaliza con una selección de los cinco palos
más influyentes del flamenco y sus respectivas representaciones cronotónicas, las
cuales han sido empleadas en la heurística desarrollada.
En el capítulo siguiente se estudia el problema resuelto en este proyecto, el VRP o
problema de enrutado de vehículos. En esta sección se definen las motivaciones y
aplicaciones que llevaron al originario planteamiento del VRP, los elementos
matemáticos imprescindibles que componen el problema y las principales variantes del
mismo, así como algunos de los métodos empleados para su resolución, que han sido
propuestos en la literatura académica por diversos autores.
Los distintos enfoques algorítmicos existentes se han agrupado en métodos exactos,
formulados como modelos de programación lineal; métodos heurísticos, que permiten
obtener soluciones adecuadas en un tiempo más reducido; y los métodos
metaheurísticos, algoritmos de optimización global basados en la observación de
procesos físicos y naturales.
Proyecto Fin de Carrera | María Miranda Burguete
147 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
La memoria continúa con la particularización del VRP que se ha empleado como caso
de estudio para evaluar el rendimiento del nuevo algoritmo basado en los compases
flamencos. Para la misma se ha simplificado del problema de enrutado de vehículos
con restricciones de capacidad, CVRP, para incluir un único depósito o almacén y
varios clientes.
Tras la descripción de los elementos constitutivos del problema planteado y de las
características y restricciones que acotan los posibles resultados, se ha trasladado la
descripción del mismo al dominio matemático, recogiendo las ecuaciones que lo
modelan. Estas últimas incluyen las variables utilizadas, la función objetivo de
minimizar la distancia total recorrida por la flota de vehículos y las restricciones del
problema. Al final de la sección, se recopilan todas estas ecuaciones que completan la
formulación matemática global del problema estudiado.
El quinto capítulo del documento desarrolla el Algoritmo por Ritmos del Flamenco,
ARF, objeto principal de este proyecto. Inicialmente, se explica la relación establecida
entre la representación cronotónica de los palos del flamenco y la heurística diseñada.
Esta representación gráfica de los palos flamencos ha sido elegida dado que permite
establecer un vínculo entre el valor de cada distancia cronotónica con una operación de
búsqueda local diferente, dando pie a la definición de una heurística a partir de las
mismas. Una vez descrita la relación entre la heurística de optimización y los ritmos
del flamenco, se describen las dos heurísticas empleadas por el ARF para la
determinación de una solución inicial admisible.
Al tratarse el ARF de un algoritmo de búsqueda local, la extracción de la solución
inicial se ha planteado como una heurística independiente que puede entenderse como
paso previo que condiciona el problema para iniciar la optimización. Las dos variantes
creadas para determinar la solución de partida han sido la heurística de mínima
distancia y la heurística de demanda máxima. La primera está orientada a optimizar la
función objetivo mientras que la segunda se ha creado para ser utilizada en aquellos
casos en que la heurística de mínima distancia no converge en una solución factible.
El ARF integra cuatro operaciones de búsqueda local diferentes, estas se han
identificado con cada uno de los cuatro valores que puede tomar la distancia
cronotónica entre dos acentos consecutivos del compás de un palo flamenco. En el
subapartado dedicado a las operaciones, se describe la lógica de asignación de cada
una de ellas a un valor determinado de distancia en función del grado de alteración
que introducen sobre la solución candidata a la que se aplican.
Adicionalmente, se han detallado los movimientos de clientes entre rutas que ejecutan
dichas operaciones en busca de una mejora en la función objetivo. El quinto capítulo de
este documento culmina con la descripción exhaustiva del Algoritmo por Ritmos del
Flamenco en función de una combinación de los cinco palos de flamenco considerados
que es tomada como única entrada al algoritmo. El proceso de optimización ha sido
Proyecto Fin de Carrera | María Miranda Burguete
148 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
ilustrado mediante un diagrama de flujo.
En la siguiente sección se introducen los parámetros y variables que se han utilizado
para la implementación en Matlab del ARF, empleando un enfoque metódico en el que
se ha buscado optimizar el tiempo de ejecución por medio de la prevención de la
ejecución de operaciones improductivas repetitivamente. En esta sección también se ha
descrito la implementación de las diferentes heurísticas de determinación de la
solución inicial admisible. Seguidamente, se incluyen las funciones y secuencias de
comandos creadas en el lenguaje de programación Matlab para modelar y resolver los
casos particulares objeto de estudio.
Con el ARF definido y empleando la implementación en Matlab, el último capítulo del
documento recopila los resultados generados por este algoritmo al ser aplicado sobre
diferentes redes particulares de CVRP y la comparación de los mismos frente a
algoritmos propuestos por otros autores dentro del mismo campo de estudio.
Este capítulo comienza con una descripción paso a paso de la implementación del
algoritmo sobre una Red de Prueba simplificada. Esta Red de Prueba ha sido empleada
como herramienta para comparar las heurísticas de solución inicial y ejemplificar la
necesidad de definir una heurística de demanda máxima que permita generar una
solución admisible en casos desfavorables para la aplicación de la heurística de
distancia mínima. Adicionalmente, la Red de Prueba ha sido empleada para comparar
la capacidad de cada una de las cuatro operaciones de búsqueda local introducidas
para avanzar hacia una estimación de una solución óptima.
Dado que el ARF debe nutrirse de codificaciones binarias de los compases de diferentes
palos del flamenco en su ejecución, la Red de Prueba ha permitido estudiar de manera
aislada el avance en la optimización que supone la aplicación sobre la misma solución
inicial de partida, del ARF particularizado a cada uno de los palos del flamenco
considerados. Este estudio ha continuado con la optimización de la secuencia en la que
dichos palos son introducidos en el desarrollo del ARF. De esta manera, se ha tomado
como orden característico de ejecución de los palos, la combinación de entre todas las
posibles que ha generado la solución de menor distancia sobre la Red de Prueba.
Una vez fijado el orden de ejecución de los cinco palos del flamenco incluidos en el
ARF, este algoritmo ha quedado definido de forma autónoma y carente de entradas
ajenas a la red de nodos que se desea optimizar. La subsección dedicada a la Red de
Prueba concluye con la aplicación del algoritmo autónomo o final sobre esta última,
incluyendo los pasos y resultados intermedios obtenidos hasta la generación de una
solución cercana a la solución óptima para diferente número de iteraciones del
algoritmo.
Con el ARF completamente definido y en el marco de comparar la eficacia del mismo
con un método de optimización por búsqueda local de naturaleza semejante, en el
último capítulo de este documento se ha aplicado el algoritmo sobre doce variantes
Proyecto Fin de Carrera | María Miranda Burguete
149 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
definidas a partir de una red de clientes común en R.Grosso [6]. Los problemas
resueltos se caracterizan por la introducción de una penalización de distancia para los
vehículos de mayor capacidad y la variación del orden en el que se define el vector que
contiene las capacidades de estos últimos.
La inclusión de una penalización por distancia ha requerido la adaptación del ARF, los
detalles de la cual se han omitido por razones de claridad, para realizar una
comparativa de resultados en igualdad de condiciones. La aplicación del ARF ha
producido estimaciones de las rutas óptimas muy próximas a los resultados recogidos
en el documento original.
Con el objetivo de explorar el potencial de mejora ofrecido por las operaciones de
búsqueda local incluidas en el ARF sacrificando el tiempo de ejecución del algoritmo,
se ha introducido el ARF Adaptado. Este nuevo algoritmo se diferencia del ARF por la
inclusión de un bucle interno de optimización del orden de aplicación de los palos del
flamenco considerados para cada uno de los problemas resueltos para el número
máximo de iteraciones permitidas sobre la matriz de palos. La inclusión de dicho bucle
ha perjudicado considerablemente el tiempo requerido para la aplicación del algoritmo
a cambio de generar una mejora marginal sobre la estimación de la solución óptima
que respalda aunque no justifica la inclusión de este grado de complejidad. El capítulo
culmina con la discusión crítica de los resultados obtenidos así como la comparativa
entre las estimaciones producidas por los distintos métodos incluidos.
8.2. Discusión
En este Proyecto Fin de Carrera se ha desarrollado un algoritmo de optimización que
genera soluciones cercanas al óptimo para un caso simplificado del problema de
enrutado de vehículos, VRP. A la hora de implementar un algoritmo basado en los
compases de los palos del flamenco, ha sido necesario tomar decisiones y descartar
alternativas que han conducido a los resultados aquí presentados. A continuación, se
ofrece un comentario crítico referido a los aspectos que constituyen el núcleo de este
proyecto con la inclusión de propuestas para trabajo futuro en esta disciplina.
Sobre la representación cronotónica:
Existen múltiples representaciones gráficas diferentes para los compases de los palos
del flamenco que no han sido incluidas en esta memoria por haber resultado
irrelevantes para el desarrollo del algoritmo. Estas últimas son empleadas con
frecuencia para comparar características rítmicas de los distintos subgéneros flamencos
y en su mayoría describen el compás de un determinado palo indicando la posición de
los acentos y los tiempos sin acentuar.
En la representación cronotónica, sin embargo, se refleja el tiempo entre acentos. Es
decir, se representa el tiempo transcurrido desde que se produce un acento hasta que
Proyecto Fin de Carrera | María Miranda Burguete
150 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
se alcanza el siguiente, denominando este intervalo distancia cronotónica. Si bien la
distancia cronotónica debe entenderse como un concepto rítmico, que describe una
sección suave en la música flamenca entre acentos consecutivos, en este proyecto se ha
tomado ventaja de que constituye una caracterización numérica de cada palo.
La sucesión de distancias cronotónicas característica de cada subgénero se ha traducido
en una serie de comandos u operaciones asociados a cada uno de los valores que toma
dicha distancia. Sin embargo, la asignación de operaciones a diferentes valores de esta
distancia no ha sido aleatoria y se ha establecido una relación entre el tiempo que
transcurre entre un cambio de ritmo y el grado de modificación producido por una
operación de búsqueda local. En otras palabras, se ha establecido una relación de
tiempo-complejidad entre distancias cronotónicas y operaciones de búsqueda local.
Hubiera sido posible en este punto enfocar la relación de una manera diferente,
considerando por ejemplo un análisis estadístico del modo en el que los valores de
distancia cronotónica se suceden, para ligar los valores más frecuentes con sucesiones
de operaciones que realizan un estudio amplio del conjunto de candidatos entorno a la
solución local.
Sobre el VRP:
El estudio del Problema de Enrutado de Vehículos, VRP, constituye un tema de
complejidad tan elevada que en muchas ocasiones es considerado una disciplina
independiente dentro del ámbito de la optimización sujeta a restricciones. En este
proyecto se ha considerado una variante simplificada del CVRP, por lo que no se han
considerado condiciones adicionales como la existencia de ventanas de tiempo en las
que los clientes pueden ser visitados, rutas prohibidas, objetivos de minimización de
coste o condiciones de tráfico de vehículos entre otros. Por ello, a pesar de haber
ofrecido una visión limitada del VRP, esta decisión ha permitido centrar el proyecto en
el desarrollo del algoritmo, partiendo de la búsqueda de un nexo de unión entre el
flamenco y los métodos de búsqueda por trayectoria.
El ARF emplea un mecanismo de búsqueda por trayectorias de soluciones admisibles
para estimar una solución cercana a la óptima partiendo de una solución inicial. Esto
implica que la extensión de este método para incluir un mayor número de restricciones
podría elevar la complejidad del algoritmo implementado, por lo que podría resultar
ventajoso considerar la exploración de soluciones no admisibles con la inclusión de
funciones de penalización a minimizar que garanticen la convergencia a una solución
admisible.
Sobre los palos del flamenco:
Se han elegido los cinco palos que se consideran más representativos del flamenco por
su importancia histórica dentro del género musical. Aumentar el número de palos
considerados por el algoritmo permitiría explorar nuevas sucesiones de operaciones de
búsqueda local. Sin embargo, esta opción ha sido descartada al existir únicamente
Proyecto Fin de Carrera | María Miranda Burguete
151 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
cuatro posibles valores de distancia cronotónica entre los acentos de los palos
flamencos. Es decir, la adición de nuevos palos seguiría limitada por la aplicación en
exclusiva de cuatro operaciones de búsqueda local.
En este proyecto se han considerado palos de doce tiempos, ya que no sólo constituyen
los palos principales, sino que dan más juego a la hora de combinar operaciones de
búsqueda. Sin embargo, la riqueza del género flamenco hace posible que se pudiera
considerar un estudio apoyado en palos de cuatro tiempos, modificando ligeramente el
algoritmo, para comparar los resultados y tiempos de ejecución con los palos de doce
tiempos.
Sobre las heurísticas de búsqueda de una solución inicial:
El proceso de obtención de la solución inicial, necesaria para comenzar las iteraciones
del ARF, se ha llevado a cabo mediante dos heurísticas distintas. La primera de éstas se
ha desarrollado atendiendo a una lógica de buscar las rutas de mínima distancia. La
segunda, de mayor robustez, evita el fracaso en la búsqueda de una solución inicial en
el caso de que las condiciones de demanda y flota fueran conflictivas. La ventaja de
haber desarrollado una segunda heurística para aquellos casos en que la primera no
produzca una solución factible, ha sido garantizar la obtención de una solución inicial,
requisito fundamental para aplicar el algoritmo adecuadamente.
Una observación clave en este proyecto ha sido la dependencia de la mejor solución
obtenida respecto a la solución de partida. Por ello, se ha dado prioridad al empleo de
la heurística de mínima distancia para la obtención de una solución inicial. Esta
dependencia podría ser contrarrestada mediante la introducción de una operación de
ruptura si la búsqueda local avanzara lentamente. Esto podría entenderse como
introducir una pausa en el algoritmo y ejecutar de nuevo una rutina de solución inicial
que desplazara el problema a un nuevo punto de partida en la optimización y generase
una solución de partida diferente a la obtenida inicialmente.
Sobre las operaciones de búsqueda local:
Se han implementado cuatro operaciones diferentes, asociadas a los cuatro valores que
puede tomar la distancia cronotónica en el compás de un palo flamenco. La elección de
estas operaciones está ligada a la diferencia entre la cantidad de clientes que cada una
de ellas es capaz de desplazar dentro de las rutas. De esta manera, es posible tener
cuatro operaciones de diferente magnitud permitiendo la asignación de cada una de
ellas a un valor de la distancia cronotónica.
En los casos estudiados, ha sido posible observar diferencias notables en la capacidad
que cada una de las operaciones introducidas posee para generar una mejora sobre la
solución inicial. Así, se puede afirmar que la operación Merge_mod, que introduce el
mayor número de clientes de una ruta al final de otra ruta, es la operación menos
susceptible de introducir un cambio sobre la solución inicial. Para entender este
fenómeno es necesario recurrir a la combinatoria, si se considera el espacio analizado
Proyecto Fin de Carrera | María Miranda Burguete
152 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
por cada una de las operaciones de búsqueda definidas, aquellas que estudian un
espectro más amplio de candidatos son aquellas que han ofrecido mayor rendimiento
al mejorar la calidad de la solución de partida.
Esta característica ha sido reforzada por los algoritmos de obtención de una solución
inicial admisible, que han sido creados de manera independiente a las operaciones y no
orientados a condicionar el problema para que determinadas operaciones alcancen un
mayor avance en la optimización. En futuros trabajos en los que se consideren
variantes de las operaciones aquí descritas, se propone modificar las operaciones
menos productivas para mejorar su rendimiento.
De esta manera, podría modificarse la operación Merge_mod para que la adición de
clientes a una ruta se realice colocando éstos en una posición óptima dentro de la
misma, en lugar de imponer su adición al final de la ruta destino. Además, para
asegurar la posibilidad de trasladar el mayor número de clientes, los candidatos se han
desplazado uno a uno, empezando por el cliente con menor demanda. En el futuro, se
podría estudiar la opción de añadir estos clientes en un orden diferente, empezando
por el cliente más alejado del resto de clientes de la ruta de origen.
Sobre el Algoritmo por Ritmos del Flamenco (ARF)
Como todo método de optimización por búsqueda de trayectoria, la capacidad del ARF
para encontrar una solución razonablemente buena dentro del conjunto de posibles
candidatos esta en gran medida condicionada por la exhaustividad con la que el
algoritmo puede analizar el conjunto de candidatos a mejor solución obtenida. En este
sentido, la implementación del ARF descrita en este proyecto presenta dos grandes
inconvenientes.
En primer lugar y como ya se ha mencionado, el algoritmo está altamente
condicionado por la solución inicial. Es decir, una vez definida esta última, el proceso
de optimización se basa en una búsqueda local centrada en la misma. Para extender el
algoritmo, tal y como se ha dicho, podría modificarse bruscamente la solución inicial
para reiniciar las iteraciones sobre esta nueva solución, ampliando así las posibilidades
de mejora
Adicionalmente, empleando los resultados sobre la Red de Prueba de todas las
combinaciones posibles de los cinco palos considerados sin repetición de los mismos,
se ha fijado un orden de aplicación de los palos dentro del ARF con el objeto de reducir
el tiempo de ejecución requerido para la extracción de una estimación cercana a la
óptima. En consecuencia, este orden distaría de alcanzar la mejor solución posible en
su aplicación sobre diferentes redes, tal y como se ha mostrado mediante la resolución
de los casos particulares de VRP incluidos en R. Grosso [6] aplicando el ARF.
En el último capítulo de este documento y con el objeto de superar esta última
limitación se ha añadido el ARF Adaptado. Éste es un algoritmo que incluye un bucle de
optimización para la selección de un orden de ejecución de los palos del flamenco que
Proyecto Fin de Carrera | María Miranda Burguete
153 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
genera una estimación de distancia total mínima sobre el número límite de iteraciones
permitidas sobre la matriz de palos. El elevado coste computacional de la inclusión de
dicho bucle, evidenciado por el incremento en los tiempos de ejecución, ha quedado
justificado por una significativa mejora de las estimaciones óptimas alcanzadas por el
algoritmo.
Sobre la implementación del ARF en Matlab:
Para la implementación del algoritmo se ha optado por el lenguaje M, utilizando la
herramienta Matlab para su ejecución. El código incluido en este proyecto presenta un
carácter altamente metódico en la implementación de las operaciones de búsqueda
local. Se podrían comparar en futuros análisis los resultados obtenidos implementando
los pasos del algoritmo en Matlab, con los obtenidos con los métodos de programación
lineal entera que resuelven las ecuaciones del modelo matemático u otros métodos de
búsqueda centrados en el análisis del gradiente de la función objetivo.
A la hora de implementar las operaciones de búsqueda, se ha introducido un vector
que previene la ejecución de operaciones que ya han demostrado no producir mejora
sobre la solución transitoria. Con esto se ha conseguido mejorar la eficiencia del
algoritmo de búsqueda, sin embargo no se han introducido condiciones para evitar el
estudio de movimientos dentro de una operación que ya han sido descartados en el
paso inmediatamente anterior. Esta técnica permitiría reducir los tiempos de ejecución
sobre redes con un gran número de nodos.
Sobre la aplicación del ARF a las variantes recogidas en R. Grosso [6]:
La efectividad del algoritmo creado en este proyecto ha sido evaluada en comparación
con los resultados expuestos en R. Grosso [6]. En esta referencia se describen una serie
de variaciones sobre un problema modelo incluyendo penalizaciones de distancia
sobre los vehículos de mayor capacidad y alteraciones en el orden de procesado de los
vehículos y clientes.
La aplicación del ARF sobre dichos problemas ha revelado que la eficacia de este
algoritmo está ligada al número de vehículos de reparto disponible. Dada la naturaleza
de las operaciones de búsqueda local introducidas, la existencia de un mayor número
de vehículos permite la exploración de un conjunto más amplio de soluciones
candidatas. De esta manera, en las variantes caracterizadas por una reducción en el
número de vehículos, el ARF converge a una distancia total significativamente más
elevada que los resultados extraídos por R. Grosso [6].
Adicionalmente, la sensibilidad de los resultados obtenidos mediante el ARF con
respecto a la solución inicial ha sido evidenciada por la convergencia a soluciones
diferentes para casos cuyo único rasgo distintivo es el orden en el que los vehículos son
almacenados en el vector de capacidades. Este resultado resalta nuevamente una
severa limitación que inherentemente afecta a las heurísticas de optimización por
Proyecto Fin de Carrera | María Miranda Burguete
154 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
búsqueda local.
La limitación de la capacidad de minimización impuesta por la elección de un orden de
ejecución de los palos de flamenco considerados dentro del ARF ha sido mitigada en la
resolución de estos problemas mediante la introducción del ARF Adaptado. Este último
algoritmo ha propiciado un marcado incremento en el tiempo de computación
requerido pero al mismo tiempo ha extendido de manera significativa la capacidad de
mejora local, minimizando la distancia total en todas aquellas variantes en las que el
orden de aplicación de los palos del flamenco ha sido variado respecto al elegido sobre
la Red de Prueba.
Proyecto Fin de Carrera | María Miranda Burguete
155 Escuela Técnica Superior de Ingeniería – Universidad de Sevilla
2015
9. BIBLIOGRAFÍA
[1] Drools Release Notes. Available: https://docs.jboss.org/drools/release/6.0.0.CR4/
droolsjbpm-introduction-docs/html/releaseNotes.html [Abril, 2015].
[2] CLARKE, G.U. and WRIGHT, J.W., 1964. Scheduling of vehicles from a central
depot to a number of delivery points. Operations research, 12(4), pp. 568-581.
[3] DANTZIG, G. and RAMSER, J., 1959. Optimum routing of gasoline delivery trucks.
Proc.Fifth World Petroleum Cong, , pp. 19.
[4] DÍAZ-BÁÑEZ, J.M., 2013. Sobre problemas de matemáticas en el estudio del cante
flamenco. Gaceta de la Real Sociedad Matemática Española, 16(3), pp. 513-542.
[5] DIAZ-BÁNEZ, J., FARIGU, G., GÓMEZ, F., RAPPAPORT, D. and TOUSSAINT,
G.T., Análisis filogenético del compás flamenco.
[6] GROSSO, R., 2014. Technical Report DOIGE2-2014-01, Universidad de Sevilla.
[7] GUSTAFSON, K., 1988. The graphical representation of rhythm. PROPH) Progress
Reports from Oxford Phonetics, 3, pp. 6-26.
[8] GUSTAFSON, K., 1987. A new method for displaying speech rhythm, with
illustrations from some Nordic languages. Nordic Prosody IV, pp. 105-114.
[9] HO, S.C. and HAUGLAND, D., 2004. A tabu search heuristic for the vehicle routing problem with time windows and split deliveries. Computers & Operations Research, 31(12), pp. 1947-1964.
[10] HOFMANN-ENGL, L., 2002. Rhythmic similarity: A theoretical and empirical
approach, Proceedings of the Seventh International Conference on Music Perception and
Cognition 2002, pp. 564-567.
[11] KEYSER, C.H., 1993. Introduction to Flamenco: Rhythmic Foundation and
Accompaniment. CH Keyser, Jr.
[12] NÚÑEZ, F., 2003. Comprende el flamenco. RGB Arte Visual.
[13] PEROSIO, L.L. and ZUNINO, C.H., 2008. Un Algoritmo Tabu Search Granular para el Problema de Ruteo de Vehículos con Ventanas de Tiempo y Entregas Parciales, Universidad de Buenos Aires.
[14] ROLDÁN CASTAÑEDA, C.Y., 2000. Estudio comparativo de diversos métodos de
solución del problema del agente viajero (PAV), Universidad de las Américas Puebla.
[15] TOTH, P. and VIGO, D., 2001. The vehicle routing problem. Society for Industrial
top related