Problema de Ruteo de Vehículos

Vista previa del material en texto

ug~ 
-..~· 'f TECNOLÓGICO 
DE M ONTEf~REY.~, 
Campus Ciudad de México 
Escuela de Diseño, Ingeniería y Arquitectura 
Maestría en Ciencias con especialidad en Ingeniería Industrial 
"Alternativa Heurística de Método de Centro de Masas para el 
Problema de Ruteo de Vehículos" 
Autor: 
José Luis Flores Flores 
Director de la tesis: 
Dr. Manuel Alvarez Madrigal 
• 
Noviembre 2013 
Biblioteca 
Campla Ciudad dlt lMDCFJ 
Aítornativa Heurística de Método de Centro de Masas par~ el Prnbiema de Ruteo de Vehículos 
, 
Indice 
l. Agradecimientos .......................... 11 ........................................................... ............. 3 
1. Introducción ........................................................................................................ 5 
1.1. El problema de ruteo de vehículos . ...... .. ....... ... .... ........ .. .... .. .... .......... ...... ... ...... .. ..... ......... 5 
1.2. Soluciones al VRP .. .... ... ...... ..... .. ... ... ...... ....... ....... .... .... ... .... .. ..... ... ... .. ..... .... ...... ..... ........... 6 
2. Soluciones Tradicionales al VRP ....................................................................... 9 
2.1. Atributos deseables para el funcionamiento de un algoritmo de VRP ...... ..... ... .. ..... .. ..... .. . 9 
2.2. Heurísticos y Metaheurísticos en la solución del VRP . ........ ....... .............. ..... .......... ....... 13 
2.3. El problema de inicialización en VRP ..... ... .... ..... ...... ......... ..... ..... ...... ... ..... .... .. .. ... ...... ..... 29 
2.4. Hipótesis ................... .............. .. ..... ... ............. .. .... ....... ... ............. ... -... .. ..... ... ... ... ...... ... .... . 31 
2.5. Objetivos de la tesis ... .. .... ....... .......... .......... .......... ...... ........ ......... .... .. ...... .. ............ ......... 31 
3. Método propuesto de inicialización para VRP ................................................ 33 
3.1. Método de Inicialización por Centros de Masa .... .. ............... ........ ....... ...... .... .. ......... ... .... 33 
3.2. Las soluciones iniciaies aleatorias contra el método de "Centros de Masa" ........... .. ..... .47 
4. Comparación del Método .................................................................................. 50 
4.1. Aplicación del método de "Centro de Masas" a un problema más complejo .... ...... ......... 50 
4.2. Comparación del método de "Centro de Masas" con la solución del VRP Solver ... ....... . 55 
4.3 . Comparación de la solución de un algoritmo de VRP con y sin la iteración inicial del 
método propuesto ................... ............... ...... ......... ........ .. .. ..... .... .. ..... .. ... .. ........ ... ... ......... .. .... .... 56 
5. Conclusiones ...................... ,11 ••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••• " ••••••••••••• 59 
Ei. E;Jillli<>{JrélfÍél ........................................................................•............................... '5:3 
2 
Alternativa Heurística de Método de Centro de Masas para el P;obloma de Ruteo de Vehículos 
1.- Introducción 
4 
Método de centros de masa para inicialización del problema de ruteo de vehículos 
1. Introducción 
1.1. El problema die ruteo de vehículos. 
El Problema de Ruteo de Vehículos (VRP por sus siglas en in~¡lés) es un problema de 
optimización combinatoria y programación entera donde se busca servir a un número de 
clientes con una flota determinada de vehículos. Propuesto por Dantzing y Ramser [1] en 
1959, el VRP tiene gran relevancia en los campos de transporte, distribución y logística. 
Frecuentemente el VRP se contextualiza en la entrega de bienes localizados en un almacén 
central hacia clientes que han levantado órdenes para tales recursos. Implícita está la meta de 
minimizar los costos de distribución de los bienes. 
El problema consiste en diseñar un conjunto de entregas o una colección de rutas cada 
vez que una ruta empiece y termine en un depósito del material a repartir. En la solución del 
problema, cada cliente se visita exactamente una vez por un vehículo; la demanda total de 
cada ruta no excederá una cantidad Q de material; la duración total del recorrido de cada ruta 
(tiempos de viaje y de servicio) no deberá exceder un límite disponible O y la distancia total (o 
costo) de la ruta deberá se:r mínima. Las cantidades (Q, O) dependerán de :a flota de 
vehículos; las demandas dependerán de los clientes y el material en existencia en cada uno 
de los depósitos con que se cuenta. 
Hasta el momento se han estudiado muchas variaciones al problema, por ejemplo: la 
flota de vehículos puede ser heterogénea, los vehículos pueden recoger o entregar en la 
misma ruta, algunos vehículos pueden estar deshabilitados para visitar ciertos puntos, unos 
clientes requieren varias visitas dentro de una ventana de tiempo, pueden existir varios 
depósitos, las entregas pueden repartirse entre diversos vehículos, etc.[2]. 
Una buena cantidad de métodos han sido desarrollados para encontrar las mejores 
soluciones para el problema, pero aunque es factible para los problemas pequeños, encontrar 
una función mínima para problemas mayores la complejidad incrementa substancialmente a 
cada nodo nuevo que se agrega [2]: 
5 
Alternativa Heurística de Método de Centro de Masas para el Prnblerna de Ruteo de Vehículos 
• 4 locaciones tienen 24 posibles soluciones 
• 5 locaciones tienen ·120 posibles soluciones 
• 6 locaciones tienen 720 posibles soluciones 
• Y así sucesivamente. 
N locaciones tienen N x (N-1) x (N-2) x ... 3 x 2 x 1 soluciones[2]. Esto es conocido como 
una dependencia factorial. Para un vehículo de entrega que deba hacer, por ejemplo entre 80 
ó 100 entregas en un día, el número de rutas posibles es demasiado grande y nos da una 
idea de lo complejo que puede llegar a ser un problema cotidiano. 
1.2. Soluciones al VRP 
Con base en lo anterior, el clásico Problema de Ruteo de Vehículos puede ser definido 
de la siguiente manera: Sea G(V,A) una gráfica donde V={vO, v1, .. . , v} es un grupo de vértices, 
y A= {(vi, j) : vi, Vj E V, i J} es un grupo de arcos. El vértice vO representa un depósito, mientras 
que los vértices remanentes corresponden a clientes. Con A se asocia la matriz de costos (cij) 
y la matriz de tiempos (tij). Sí estas matrices son simétricas, como comúnmente pasa, 
entonces el estándar para definir el VRP es en una gráfica unidireccional G = (V, E), donde E 
= {(vi, vj) : vi, vj E V, i < j es un juego de esquinas[3]. Cada cliente tiene una demanda no-
negativa qi y un tiempo de servicio ti. Una flota de vehículos idénticos m con capacidad Q está 
basada en el depósito. El número de vehículos es conocido o tratado como una variable de 
decisión. El VRP consiste en diseñar un conjunto de m entregas o una colección de rutas tal 
que cada ruta empiece y termine en el depósito, pues el cliente es visitado exactamente una 
vez por un mismo vehículo. La demanda total de cada ruta no excede Q, la duración total de 
cada recorrido (incluyendo el viaje y los tiempos de servicio) no excede el límite presente O, y 
el costo total de la ruta es minimizado. Una variable común es donde una ventana de tiempo 
[a, b1] es impuesta en la visita de cada cliente. Se han propuesto otras variaciones que han 
sido estudiadas; la flota de vehículos puede ser heterogénea [4], los vehículos pueden ya sea 
recoger o entregar en la misma ruta [5], algunos vehículos puedes estar deshabilitados para 
visitar algunos puntos [6], quizás unos clientes requerirán varias visitas dentro de un periodo 
dado [7]. pueden existir más de un depósito [7]; las entregas pueden repartirse entre varios 
vehículos[8], etc. 
6 
Alternativa Heurístjca de Método de Centro de Masas para el Problema de Ruteo de Vehículos 
Dado que las soluciones exactas son más difíciles de encontrar entre mayor sea el 
número de puntos de entrega, los métodosheurísticos son muy utilizados en la práctica. 
Dichos métodos han provisto soluciones aceptadas durante los últimos 50 años [2]. En los 
prime~os métodos heurísticos, se puso mucho énfasis en la velocidad de cálculo para obtener 
una solución factible. Un ejemplo de esta clase de métodos son; el algoritmo de Fisher y 
Jaikumar [9], el algoritmo de barrido [1 O] y el heurístico de ahorro Clarke y Wright [11] que se 
suman a los algoritmos metaheurísticos, los cuales, en problemas de optimización sirven para 
designar un método que mejora un problema por medio de una mejora iterativa a una solución 
propuesta con respecto a una medida dada de calidad. Los metaheurísticos hacen muy pocas 
o ninguna suposición acerca del problema que será optimizado y puede buscar en espacios 
muy grandes candidatos a solución. Sin embargo los metaheurísticos no garanti.zan que la 
solución óptima será encontrada. Muchos metaheurísticos implementan optimizaciones 
estocásticas; esto es propuestas aleatorias a una solución. Los metaheurísticos se enfocan 
más en la flexibilidad de la metodología para poder abordar problemas con un gran número de 
variantes y condiciones especiales, además de ser rápidos y eficientes desde el punto de vista 
computacional, pero no son sencillos operacionalmente y requieren del apoyo de 
computadoras para poder efectuar todas las opera'ciones implicadas. Los metaheurísticos más 
conocidos son; Búsqueda Tabú, Recocido Simulado y Algoritmos Evolutivos. Mucho del 
software comercial y varios programas hechos de manera artesanal que utilizan los 
responsables del ruteo están programados con algoritmos obsoletos que dan soluciones de 
baja calidad lo que provoca que exploten las capacidades interactivas del software para 
desarrollar mejoras manuales. Esto requiere que él personal tenga mucha experiencia y 
capacitación en este tipo de problemas [2]. 
Se busca en el presente trabajo comprobar que, un método simple que pueda 
calcularse incluso de manera manual y que aporta soluciones factibles cercanas al óptimo, 
apoyaría bien la adopción masiva de este tipo de técnicas de optimización en la pequeña y 
mediana empresa. Además de que podría proporcionar un método alternativo para calcular la 
solución factible inicial para alguno de los algoritmos mencionados con anterioridad. El 
resultado obtenido deberá ser mejor que una selección aleatoria. 
7 
Alternativa Heurística de Método de Centro de Masas para el Problema de Ruteo de Vehículos 
2.- Soluciones Tradicionales al Vl~P 
8 
Alternativa Heuristica de Método de Centro de Masas para el Problema de Ruteo de Vehículos 
2. Soluciones Tradicionales al VRP 
2.1. Atributos deseables para el funcionamiento de un algoritmo de 
VRP 
Para esta tesis se utiiizarán cuatro atributos esenciales como referencia para evaluar el 
desempeño de algunos algoritmos que pretenden dar solución a los problemas de ruteo de 
vehículos; estos atributos son: Exactitud (y precisión), Velocidad, Simplicidad y Flexibilidad [2]. 
Exactitud (y precisión). 
Mide el grado de desviación entre la solución de un algoritmo del resultado óptimo al 
problema planteado. Ya que el resultado óptimo es desconocido y, la posibilidad de 
encontrarlo se hace más difícil entre más complejo sea el problema, las comparaciones se 
hacen basadas en valores óptimos conocidos. Como se señala en Barr [12] el análisis de los 
resultados producto de los algoritmos de VRP está lleno de dificultades: 
• El cambio en la selección de cualquiera de estos factores tiene repercusiones en la 
evaluación del algoritmo. Los autores comúnmente reportan resultados obtenidos para 
la mejor combinación de parámetros algorítmicos, o la mejor cantidad de iteraciones 
bajo ciertas condiciones de inicialización (para lo cual no existe una metodología 
,· 
estructurada y es lo que se tratará de comprobar en esta tesis). 
• No todos los autores usan las mismas convenciones que, pueden derivar en una amplia 
gama de resultados[13]. 
• Las pruebas frecuentemente se llevan a cabo redondeando valores después de ciertas 
posiciones en los decimales, por ejemplo a 5 decimales [2]. 
• Algunas iteraciones son llevadas a cabo con números definidos como punto flotante, 
sin redondeo o truncamiento, usando tantos dígitos como la computadora lo permita. 
Cuando el redondeo o el truncamiento ocurre, es común que la computadora recalcule 
la solución final usando más dígitos después del punto decimal y se presenta el 
resultado final con uno o dos dígitos después del punto. 
9 
Alternativa Heurística de Método de Centro de Masas para el Problema de Ruteo de Vehículos 
Para ilustrar esto, considérese la primera instancia del punto de referencia del VRP resuelto 
por Christofides, Mingozzi y Toth [14]. el mismo algoritmo de Búsqueda Tabú (Tabu route) 
reporta un costo de $524.61 sí los cálculos son realizados redondeando los costos a 5 dígitos 
(esto, , por cierto es un óptimo comprobado [16]), un costo de 521 sí los decimales se 
redondean hacía arriba o hacia abajo al entero más cercano, y un costo de 508 sí se truncan 
los costos de los enteros que son usados. En los casos con restricciones en la duración de las 
rutas, usar precisión insuficiente puede llevar a una solución no práctica en tiempos de viaje 
que son proporcionales a las distancias. 
Otro factor relac:onado a la exactitud es la consistencia. Como regla, los usuarios 
prefieren un algoritmo que demuestre un desempeño continuo que con variaciones, esto es, 
que algunas veces dé resultados mejores que en otras. De la misma manera, que se 
desempeñe bien la mayoría del tiempo y en algunas ocasiones, por muy contadas que sean 
su desempeño sea pobre y produzca soluciones fácilmente perfectibles por inspección visual. 
Tales soluciones son suficientes para desacreditar un algoritmo. Finalmente, el algoritmo debe 
llegar a una solución lo más r;3pidamente posible, y entonces mostrar soluciones buenas cuya 
calidad se pueda mejorar a través de la ejecución de algoritmos hasta la solución final, 
posiblemente después de consumir varios ciclos de procesamiento en computadora. Esto da 
una buena idea de que tanto esfuerzo adicional valdrá la pena invertir para mejorar la solución 
obtenida en las primeras iteraciones [2]. 
Velocidad. 
La importancia de la velocidad en los problemas de ruteo depende del nivel de 
planeación al cual el problema es resuelto y el grado de exactitud que requiere. En un 
extremo, las aplicaciones de tiempo real tales como los servicios de recepción y entrega 
inmediata [17] o re-disposición de rutas de ambulancias [18] requieren una acción rápida casi 
instantánea. Por ejemplo describe un papel crucial que juega la computación en paralelo en 
determinar que una estrategia de re-disposición de ambulancias debe determinarse cada 3 
minutos en promedio [18]. En el otro extremo, en planeación a largo plazo las decisiones se 
hacen dentro de marcos de duración de varios meses, como la planeación de flotas, en donde 
tiene mucho sentido invertir una buena cantidad de tiempo en ciclos de computadora, 
10 
Alternativa Heurística de Método de Centro de Masas para el Problema ele Ruteo de Vehículos 
particularmente si grandes sumas de dinero están en riesgo. La mayoría de las aplicaciones 
caen en alguno de estos dos extremos. No parece irracional invertir 1 O ó 20 minutos de 
recursos en un problema que se debe resolver diariamente. Sistemas interactivos deben. por 
su pu~sto, reaccionar mucho más rápido. El factor velocidad no es siempre puesto en la 
perspectiva correcta. Por ejemplo, la mayoría de los usuarios de VRP preferirían un algoritmo 
que sea 97.62% exacto y que corra 3.48 min a uno que es 94.15% exacto pero requiere sólo 
0.26 minutos para que el_ ordenador utilizado de una solución[19]. El reporte preciso de 
iteraciones requeridas por una computadora para llegar a una solución aceptable es otro tema 
delicado en la literatura científica,particularmente en el caso de corridas múltiples o sí se 
utilizan computadoras en paralelo. Al igual que en la exactitud, no existen estándares 
reglamentados para los investigadores de VRP en cuanto a la medición de velocidad se 
refiere. 
Simplicidad 
Varios algoritmos para VRP rara vez son llevados a la práctica debido a que son 
demasiado complicados o difíciles de implementar en un código. Mientras que es poco realista 
esperar que, artículos científicos que provean una descripción de un minuto para cada detalle 
del algoritmo, den suficientE~ información como para permitir qu13 un programador con 
habilidades y experiencia razonables pueda transformarlo en código [2]. Adicionalmente, los 
algoritmos deberían ser lo suficientemente robustos para asegurar que trabajen de manera 
adecuada, aún sí no se implementa cada detalle del mismo en el código. Muchas 
descripciones de algoritmos fallan en proveer muy poco o demasiados detalles. Una razón de 
porque el algoritmo de Clarke y Wright[11] es tan popular entre los programadores es que sus 
principios básicos son muy sencillos y es muy fácil de implementar en un código 
(sorprendentemente, la descripción original de dicho algoritmo era tan simple que podía haber 
parecido torpe y hasta debajo de los estándares actuales para publicación de artículos, no 
obstante su sencillez y efectividad se hicieron notar) . Códigos simples, preferentemente cortos 
y auto-contenidos, tienen mejores probabilidades de ser adoptados, aunque un mínimo de 
complejidad es esperada para lograr buenos resultados. Los al~¡oritmos que contienen 
demasiados parámetros son difíciles de entender y difíciles de implementar. Este problema 
prevalece en casi todos los algoritmos desarrollados para meta heurísticos en los pasados 1 O 
11 
Alternativa Heurística de Método de Centro de Masas para ei Problema de Huteo de Vehículos 
años[2]. En su búsqueda para mejores soluciones, los investigadores han incrementado el 
número de parámetros contenidos en sus algoritmos más allá de lo que parece ser razonable, 
particularmente en vista del hecho que relativamente nuevas instancias son usadas en las 
prueb~s. Golden [20] levantó una alerta hacia este problema. No sólo el número de 
parámetros en el algoritmo debería de estar limitado, sino que también debe hacer sentido al 
usuario final. Entonces, un parámetro que controla el número de iteraciones consecutivas sin 
mejora en una búsqueda local de un algoritmo es fácil de entender, mientras que un límite del 
número de ejecuciones para procesos internos no tiene significado para la mayoría de los 
usuarios. 
Existen dos maneras para facilitar la proliferación de parámetros: 
• Fijarlos o estandarizarlos con base en pruebas previas, especialmente sí en las mismas 
evaluaciones el algoritmo es insensible a dichos parámetros. 
• Hacer uso de los parámetros auto-ajustables durante el curso del algoritmo [13]. 
Flexibilidad. 
Un buen algoritmo para el VRP debe ser lo suficientemente flexible como para 
acomodar varias restricciones, mismas que se encuentran en la mayoría de las aplicaciones 
de la vida real. Mientras que la mayoría de la literatura de VRP se enfoca en la capacidad y, 
algunas veces en las restricciones de la longitud de la ruta, frecuentemente se pueden 
apreciar cambios que se logran hacer para lidiar con restricciones adicionales, pero esto no 
siempre es posible y, el desempeño puede deteriorarse significativamente como resultado. J-F 
Cordeau, M. Gendreau, G. Laporte, J-Y Potvin, F. Semet [7, 13} sugieren que una manera de 
medir la eficiencia de manejar restricciones adicionales en un proceso de búsqueda local es a 
través del uso de dos objetivos. El primero, F(x), calcula el costo de ruteo de la solución x. el 
segundo, F'(X), es la suma de F(x) y la falta ponderada de los términos asociados a la 
violación de cada restricción adicional. Por ejemplo, sí Q(x) y D(x) son las violaciones de la 
capacidad y la duración de la ruta asociadas con la solución x, entonces F'(x) debe definirse 
como F'(x)=F(x)+ + aQ(x)+ pD(x), donde Cx y f¡ son parámetros de faltas positivas auto-
ajustables. Inicialmente se fijan con valor igual a 1; estos parámetros se incrementan o 
decrementan de manera periódica a través de la búsqueda de acuerdo a sí en soluciones 
12 
Alternativa Heurística de Método de Centro de Masas para el Problema de Ruteo de Vehículos 
previas, fueron factibles o no factibles. Esta manera de proceder significa que la búsqueda 
probablemente evolucionará a través de una mezcla de soluciones factibles y no factibles, 
reduciendo las condiciones que pudieran permitir que una solución se encuentre atrapada en 
un mínimo local. Otra ventaja algorítmica de este método es que la búsqueda puede operar 
con movimientos relativamente simples, tales como quitar un cliente de su ruta actual e 
insertarlo en una ruta diferente. Cuando la factibilidad debe mantenerse a todo costo, tales 
movimientos simples tienden a no trabajar con las restricciones adicionales que están muy 
aiustadas, y operaciones más complejas y tardadas deben visualizarse, como las cadenas de 
ejecución o en un sentido, la flexibilidad algorítmica es en parte alcanzada a través de la 
simplicidad del diseño[2]. Esta es la única característica que no será evaluada en el presente 
trabajo. 
2,2. Heurísticos y Metaheurísticos en la solución del VRP. 
Heurísticos 
Varios Heurísticos han sido diseñados para resolver el problema de ruteo de 
vehículos[21], para dar una idea de su funcionamiento en general sólo nos concentraremos en 
los mejor conocidos: 
• El algoritmo Clarke y Wright[11 ] 
• El algoritmo de "barrido"[33] 
• El algoritmo de Fisher y Jaikumar [9]. 
Se seleccionaron éstos debido, en parte por su popularidad y también porque pueden operar 
en una amplia gama de principios. 
El algoritmo Clarke y Wright 
13 
Alternativa Heurística de Método de Centro de Masas para el Probíema de Ruteo de Vehículos 
El algoritmo de ahorro desarrollado por Clarke y Wright en 1964 [11] es una excelente 
opción desde el punto de vista de velocidad y simplicidad, y esta es probablemente una razón 
por la cual es ampliamente utilizado en programas comerciales de ruteo de vehículos. 
El algoritmo resulta de un arreglo hipotético de lugares Sn (donde n es el número de 
destinos), los cuales son suministrados desde un centro de distribución DCx de acuerdo con la 
figura 1. El plan inicial de transportes, el cual es gradualmente mejorado, se basa en la 
entrega individual a cada destino Sn. Se marca la distancia a cada destino desde el centro de 
distribución como dxj, el valor inicial del transporte en unidades es z1 ..... n y es calculado 
usando la fórmula: 
n 
Z1 = 2 '\°' d · , .. . ,n L XJ 
j=l 
Figura 1: Arreglo de rutas para el Algoritmo de Clarke-Wright (Elaboración propia) 
La maximización de ahorros se alcanza sí, · los destinos individuales son agrupados 
gradualmente con el criterio de crear círculos. Sí, por ejemplo, reemplazamos los primeros dos 
círculos por uno sólo (figura 2) y marcamos la distancia entre ei espacio S1 y S2 como d12, 
obtendremos un ahorro de u12 por la cantidad de: 
U12=2 dx1+2dxr(dx1+dx2+dx12) = dx1+dxrdx12 
Alternativa Heurística de Método de Centro de Masas para el Problema de Huteo de Vehículos 
Z12=2 dx1+2dx2 Z12= dx1+dx2 + d12 
Fi~Jura 2.-Agrupando para n=2 [22] 
Sí generalizamos, podemos expresar el total de ahorros como : 
U1 , ... ,n= (dx1+2x2-dx12)+ ... + dxn-1+dxn-dn-1n =u12 + U23 + Un-1n 
El objetivo es maximizar los ahorros u, ..... n· La versión simple del algoritmo de ahorro Clarke y 
Wright se puede resumir en 2 pasos[22]: 
1.- Calcular los ahorros U¡¡ 
2.- Seleccionar los máximos ahorros (uq) sí la conexión es posible. Por ejemplo sí: 
a) El círculo no ha sido cerrado prematuramente 
b) Otros requisitos no son cumplidos, como requerimientos de capacidad. 
Dado que, el heurístico de ahorro Clarke y Wright [11]es uno de más conocidos y 
permanece entre los primeros lugares de utilización, no obstante al~¡unos problemas que 
puede presentar. Está basado en la noción de ahorro. Inicialmente, una solución factible 
consiste en "n" rutas hacia adelante y de regreso entre el almacén y el Cliente. En cualquier 
iteración dada, dos rutas (v, ... vi, vO) y (vO, vj, .. , vO) se combinan en una sola ruta (vO, ... , vi, 
v .... , vO) donde quiera que esto sea factible, genera un ahorro Sij = C¡o + CoJ - Cij. En la versión 
en paralelo del algoritmo, la combinación que resulta en el mayor ahorro es siempre 
implementada, mientras que las versiones secuenciales mantienen expandiendo la misma ruta 
hasta que deja de ser factible. En la práctica, la versión en paralelo es mucho mejor. Es 
común aplicar un paso de post--optimización a la solución final. Este a¡goritmo alcanza altos 
niveles de simplicidad y velocidad. No contiene parámetros y es fácil de programar. Según 
pruebas comparativas es medianamente exacto. La mejor implementación (la versión paralela 
seguida del paso de post-optimización) tiene una desviación promedio de 6. 71 % de la mejor 
solución identificada por Taillard[23] y Rochat y Taillard[24]. Adicionalmente, varios 
investigadores han observado que la solución es algunas veces de menor calidad y 
15 
Alternativa Heurística de Método de Centro de Masas para el Problema de Huteo de Vehículos 
frecuentemente contiene al menos una ruta circunferencial. La falta de flexibilidad es, 
probablemente su peor característica. 
Mientras que restricciones adicionales pueden, en princ1p10 ser incorporadas en el 
algoritmo CW, este usualment,e resulta en una rápida deterioración de la calidad de la 
solución. Esto puede ser explicado por el hecho que el algoritmo está basado en un principio 
de mecanismos glotones o avaros y no contiene mecanismos para deshacer la fusión de rutas 
no satisfactorias generadas en las primeras iteraciones del algoritmo codificado. 
Solomon [25] reporta una variante del algoritmo CW en donde los ahorros son 
adaptados para manejar ventanas de tiempo, pero los resultados son decepcionantes. 
Muchas mejoras al algoritmo CW han sido propuestas. Gaskell[26] y Yellow[27] han sugerido 
ahorros generalizados de forma c'=c¡o+co-ACij para ayudar a producir rutas más compactas, 
donde A es un parámetro positivo. Otras mejoras se relacionan con el uso de estructuras de 
datos complejas y estrategias der ordenamiento[28, 29] para mejorar el manejo de ahorros. S!n 
embargo, dados los niveles presentes de tecnología en computación y la velocidad de 
respuesta del algoritmo CW, para instancias medianas, las últimas mejoras se hacen 
irrelevantes. Otra línea de investigación en los algoritmos CW se ha concentrado en la 
optimización de la fusión de rutas a través del uso de algoritmos combinatorios. Los primeros 
resultados basados en esta idea fueron producidos por Desrochers y Verhoog[30] y Altinkeme 
y Gavish[31] . La mejor y más reciente implementación de la de Wark y Holt[32] que 
frecuentemente obtiene mejoras significativas sobre la implementación original del algoritmo 
CW, pero a expensas de un gran incremento de ciclos computacionales. En resumen, estas 
mejoras realizadas al algoritmo le restan a las dos mejores características del mismo; 
simplicidad y velocidad, es difícil de implementar y no hace nada para mejorar la falta de 
flexibilidad del algoritmo original. Mientras que la aplicación repetitiva de los algoritmos 
basados en combinaciones da como resultado unp mayor exactitud, esta técnica puede limitar 
el potencial debido a su complejidad y bajos niveies de flexibilidad[2] . 
Algoritmo de barrido. 
16 
Alternativa Heurística de Método de Centro de Masas para ei Problmna de Ruteo de Vehículos 
Esta solución se le atribuye a Gillett y Miller[33] aunque su p1-inc1p10 básico puede 
rastrearse hasta Wren[34) y Wren y Holliday[35]. Se aplica a instancias planas del VRP. Rutas 
factibles son creadas rotando un rayo centrado en el depósito y, gradualmente incluyendo a 
los Cllentes en el vehículo una v,gz que la capacidad o la restricción de la longitud de la ruta es 
alcanzada. Una nueva ruta es entonces iniciada y el proceso se repite hasta que el plano 
entero ha sido "barrido". Típicamente se aplica una optimización de 3 pasos, En las instancias 
CTM[19J la implementación de este algoritmo tiene una desviación promedio de 7 .09% de la 
mejor solución conocida. Los tiempos de cálculo promedio en computadora son de 105 
segundos. Este algoritmo es bastante simple, pero no se muestra superíor al algoritmo Clarke 
y Wright[11] en cuanto a rapidez y precisión se refiere. También habría que agregar que es 
más bien inflexible. Aquí también se puede apreciar al naturaleza ambiciosa del mecanismo 
de barrido[33) lo que hace difícil acomodar restricciones adicionales. En particular, el algoritmo 
no se acomoda bien a instancias definidas en un ambiente urbano con diseños de calles 
entrelazadas (en red) . Un número de heurísticos generan rutas para vehículos factibles 
(llamados "pétalos" para este contexto) y detem1inan la mejor combinación a través de la 
solución de un juego de problemas particionados. Algunos ejemplos de este enfoque son los 
algoritmos de un "pétalo" de Foster y Ryan[36] y Tyan[37] y los heurísticos de dos "pétalos" de 
Renaud[19] donde, adicionalmente a rutas individuales, trayectos de dos vehículos también 
son generadas. Estas extensiones proveen una mayor exactitud con respecto al algoritmo de 
barrido básico. En términos de velocidad, se pueden también hacer mejoras. No obstante 
estas extensiones hacen más complejo el algoritmo generando una gran cantidad de "pétalos" 
que son difíciles de manejar y fijan pasos particionados que se deben ejecutar. En cuanto a 
Flexibilidad se refiere, los algoritmos de "pétalos" pueden acomodar una amplia variedad de 
restricciones, pero esto repercute en la simplicidad . De hecho, este sencillo algoritmo puede 
verse como una versión truncada de generación de columnas que es conocido por producir 
resultados con alta calidad en problemas con muchas restricciones a expensas de la 
simplicidad. 
El Algoritmo de Fisher y Jaikumar. 
17 
Alternativa Heurística de Método de Centro de Masas para el Problema de Ruteo de Vehículos 
Esta propuesta de solución es un proceso de dos fases en donde un grupo factible de 
clientes es creado como primera instancia resolviendo un problema de designación 
generalizado, y una ruta del vehículo es determinada para cada grupo por medio de un 
algoritmo s_olución para el problema del agente viajero[38) Para fom1ular el problema de 
designación generalizado, es necesario determinar primeramente una semilla para cada ruta 
de donde la distancia de cada cliente es calculada. Dado que el problema de designación 
generalizado es NP-Hard, usualmente se soluciona por medios de la técnica de relajación de 
Langrage. Aunque los resultados reportados son buenos para este algoritmo, algunos 
problemas se han presentado en su desempeño. El algoritmo original[38] provee valores de 
soluciones enteras sin tener una regla de redondeo o de truncamiento de decimales y la 
solución no puede ser verificada, lo que hace que la evaluación del algoritmo sea difícil. 
Algunos experimentos computacionales[2] sugieren que el algoritmo de Fisher y Jaikumar [38) 
no es simple de programar y su velocidad está altamente relacionada con la selección de 
semillas así como la implementación de un proceso de Lagrange. Se ha encontrado que 
dichas semillas son seleccionadas como en Fisher[39) y los pasos Langragianos programados 
como fueron recomendados por Fisher[40) tienen entonces una convergencia que 
frecuentemente es pobre y muchas iteraciones pueden ser necesarias para alcanzar una 
solución satisfactoria y, _aun cuando la precisión puede ser baja, varias iteraciones pueden ser 
necesarias para alcanzar una solución que valgala pena implementar y con una baja 
precisión. La flexibilidad es problemática también, mientras que, en principio es fácil manejar 
las restricciones de capacidad, la referencia original no contiene indicaciones respecto al 
tratamiento de las restricciones en la duración de la ruta, aunqu,~ seis instancias que 
involucran tales restricciones se resuelven repetidamente. No se ve un mecanismo fácil en el 
cual incorporar estas y otras restricciones dentro del Algoritmo. Bramel y Simichi-Levi[41] 
optimizaron la selección de semillas en el algoritmo de Fisher y Jaikumar[38] resolviendo un 
problema de capacidad local. Sus resultados obtienen sólo el 3.29% de desviación del mejor 
resultado obtenido. 
Metaheurísticos 
18 
Alternativa Heurística de Método de Centro de Masas para el Problema de Ruteo de Vehículos 
En problemas de optimización, en este caso para problemas de ruteo, los algoritmos 
metaheurísticos sirven para designar un método que optim:za un p::-cblema por medio de una 
mejora iterativa a una solución propuesta con respecto a una medida dada de calidad. Los 
metaheurísticos hacen muy pocas o ninguna asunción acerca del problema que será 
optimizado y puede buscar en espacios muy grandes candidatos a solución. Sin embargo los 
metaheurísticos no garantizan que la respuesta óptima será encontrada. Muchos 
metaheurísticos implementan optimizaciones estocásticas, esto es, propuestas aleatorias a 
una solución[2]. 
Desde la década de los 80's los algoritmos metaheurísticos[42] se desarrollaron para 
resolver problemas conocidos como de difícil optimización, tan bien como fuera posible. Esto 
permitió el desarrollo de los metaheurísticos o meta-heurísticos, que incluyen en particular 5: 
Búsqueda Tabú[13], Recocido Simulado[43], Algoritmos Evolutivos o Genéticos [44], los 
Algoritmos de Colonia de Hormigas[45] y Redes Neuronales [46]. De estos 5, sólo se 
considerarán debido a sus resultados en la solución de VRP; la búsqueda Tabú, Recocido 
Simulado y algoritmos Genéticos ya que son los que mejor desempeño han mostrado para la 
propuesta de soluciones óptimas para el VRP. Las respuestas propuestas están basadas en 
un grupo común de principios, lo que los hace posibles de diseñar algoritmos de solución; las 
diferentes reagrupaciones de estos principios nos lleva a tener una gran variedad de 
metaheurísticos. 
Búsqueda Tabú: 
El método de la Búsqueda Tabú utiliza algunas ideas de sentido común (que no es tan común 
como quisiéramos) para permitir que el proceso escape de un óptimo local. 
Cualquier aplicación de la Búsqueda Tabú incluye, como subrutina, un procedimiento 
de búsqueda local que se antoja apropiado para el problema que se esté dirigiendo (Un 
procedimiento de búsqueda local opera igual que un procedimiento de mejora local, excepto 
que puede no requerir que cada nueva solución propuesta sea mejor que la anterior). El 
proceso empieza usando este proceso como procedimiento de mejora local de manera regular 
(aceptando una sola mejora en la solución en cada iteración) para encontrar el óptimo local. 
19 
Alternativa Heurística de Método de Centro de Masas para el Probiema de Ruteo de Vehículos 
Una estrategia clave de la Búsqueda Tabú es que continua con la búsqueda al permitir 
movimientos de no mejora para las mejores soluciones en el vecindario del óptimo local. 
Usando la analogía de la escalada de una colina, este proceso es, algunas veces 
referiqo co.r.no al enfoque de ascenso pronunciado/descenso suave debido a que cada 
iteración selección el movimiento disponible que impulsa más hacia arriba (refiriéndonos a la 
metáfora de subir una colina), o, cuando no se encuentra disponible un movimiento hacia 
arriba, selecciona el movimiento que menos me haga bajar (o perder lo ya ganado). Sí todo va 
bien, el proceso seguirá un patrón cómo el mostrado en la figura 1 donde el mínimo local es 
dejado atrás con el fin de escalar aun óptimo global. 
.... 
Iteraciones 
Figura 1: Patrón de iteraciones en la Búsqueda Tabú [47] 
El riesgo de tomar este enfoque es que, después de moverse de un óptimo local, el 
proceso regresará al mismo. Para evitar esto, la Búsqueda Tabú prohíbe temporalmente 
movimientos que nos podrían hacer regresar a la solución recientemente visitada. Una lista 
de registros tabú de estos movimientos prohibidos, que son referidos como movimientos Tabú. 
La única excepción es que el movimiento prohibido sea de hecho mejor que la mejor solución 
encontrada hasta ese momento. 
Este uso de una memoria de guía para buscar usando la lista tabú para registrar la 
historia reciente de la búsqueda es una característica distintiva de la Búsqueda Tabú. Esta 
característica tiene sus raíc13s en el campo de la inteligencia artificial. 
20 
Alternativa Heurística de Método de Centro de Masas para el Problema de Ruleo de Vehí~ulos 
La Búsqueda Tabú también incorpora algunos conceptos avanzados. Uno es 
intensificación, que involucra explorar una porción de la región factible más a detalle que lo 
usual después de que ha sido identificada una porción prometedora que contiene un buen 
juego ,de sqluciones. La memoria a largo plazo es usada para ayudar a implementar ambos 
conceptos. 
Recocido Simulado. 
Cómo se mencionó anteriormente, la Búsqueda Tabú se orienta en "escalar" la colina 
más alta en el ángulo más agudo hasta que alcanza la cima y despues empieza a escalar 
colina a bajo hasta encontrar la siguiente pendiente hacia arriba y llegar a la siguiente cima, 
que sería la siguiente solución óptima local. El problema es que requiere muco tiempo 
(iteraciones) en encontrar cada solución óptima local hasta encontrar · una solución óptima 
global. 
A diferencia de la Búsqueda Tabú, la técnica del recocido simulado, se enfoca en una 
sóla búsqueda por la soluGión global óptima. Dado que la colina más alta puede estar en 
cualquier lugar de la re.gión de factibilidad, el enfasis inicial en tomar pasos en direcciones 
aleatorias (escepto para rechazar algunas, pero no todos los pasoso que generen soluciones 
menos óptimas que las anteriores) con el fin de explorar la mayor cantidad posible de la región 
de factibilidad como sea posible.Debido a que la mayoría de los pasos aceptados son cuesta 
arriba, la búsqueda eventualmente tenderá a aquellas partes de la región de factibilidad que 
contengan las "cimas" más altas. 
Para ser más específicos, cada iteración del proceso de búsqueda del Recocido 
Simulado se mue-Je del intento de solución corriente a un vecino inmediato en el vecidario 
local de esta solución, al igual de la Búsqueda Tabú. Sin embargo la direfencia de entre 
ambas técnicas radica en como un vecino inmediato es seleccionado para el siguiente intento 
de solución. Por ejemplo, supongamos que: 
Zc= valor para la función objetivo del intento de solución corriente. 
Zn= valor de la función objetivo para el canidato corriente para el siguiente intento de solución 
21 
Alternativa Heurística de Método de Centro de Masas para el Problema de Ruteo de Vehículos 
T= un parámetro que mide la tendiencia a aceptar a que el candidato corriente se aplique en 
la siguietne iteración sí este candidato no muestra una mejora con respecto a la solución 
precedente. 
La regla para seleccióna cual vecino inmediato estará en el siguiente intento de 
solución es el siguiente: 
Regla de selección ele movimiento: Entre todos los vecinos inmediatos del intento de 
solución corriente. seleccione uno aleatoriamente para que se convierta en el candidato 
corriente al siguiente intento de solución. Asuma que el objetivo es la maximización de la 
función objetivo, acepte o rechaze esta candidato para el siguiente intento de solución como 
sigue: 
Sí Zn >= Zc, Siempre se aceptará este candidato 
Sí Zn < Zc, Acepte el candidato con la siguiente probabilidad: 
Probabilidad {aceptación}=ex donde 
Zn- Zc, 
x=---
T 
( Sí el objetivo es minimización, se invierten Zn y Zc, en la fórmulaanterior) Sí este candidato 
es rechazado, repita este proceso con un vecino inmediato del inümto de solución corriente. 
(sí no quedan vecinos remanente, el algoritmo termina). 
Sí el candidato corriente bajo consideración es mejor que el intento de solución 
corriente, siempre será aceptado para el siguiente intento de solución. Sí es peor, la 
probabilidad de aceptación depende en cuanto peor sea (así como del tamaño de T). La tabla 
1 muestra en ejemplo de estos valores de probabilidad, cuyo rango va desde una probabilidad 
alta cuando el candidato corriente es casi igual al intento de solución corriente hasta una muy 
pequeña probabilidad cuando el candidato es mucho peor. 
22 
Alternativa Heurística de Método de Centro de Masas para el Problema de Ruteo de Vehículos 
Zn- Zc, Probabilidad de 
~= 
T Aceptación = e X 
-0.01 0.99 
-0.1 0.905 
-0.025 0.779 
-0.5 0.607 
-1 0.368 
-2 0.135 
-3 o.os 
-4 0.018 
-5 0.007 
Tabla 1: Valores de probabilidad del intento de solución corriente [4 7] 
En otras palabras, la regla para la selección de movimiento usualmente aceptará un 
paso que puede representar un pequeño retroceso respecto a la solución anterior. 
Empezando con un valor relativamente grande de T ( como el RBcocido Simulado lo hace) 
hace que la probabilidad de aceptación sea relativamente grande, lo que permite que la 
búsqueda se de casi en forma aleatoria. Gradualmente un decremento en T mientras que la 
búsqueda continua 9_radualmente decrementa la probabilidad de aceptación, lo cual 
incrementa el enfasis en seguir sólo "cuesta arriba". Así que la selección de valores de Ta lo 
largo del tiempo contrla el grado de aleatoriedad del proceso para permitir pasos "cuesta 
abajo". 
Este componente aleatorio, no presente en la Búsqueda Tabú básica, provee mayor 
flexibilidad para moverse hacia otra parte de la región de factibilidad con la esperanza de 
encontrar una mejor solución a la anterior. 
El método usual para implementar la selección de la regla de selección de movimiento 
para determinar sí un paso hacia abajo en particular será aceptado, es comparar un número 
aleatorio entre O y 1 a la probabilidad de aceptación. Tal número aleatorio puede ser 
visualizado como una observación aleatoria de una distribución uniforme entre O y 1. 
Sí (Número aleatorio)<Probabilidad (aceptación), acepte el paso hacia atrás, de cualquier otra 
forma, rechace. 
23 
Alternativa Heurística de Método de Centro de Masas para el Problema de Ruteo de Vehículos 
¿Porqué el Recocido Simulado utiliza una fórmula particular para la Probabilidad de 
aceptación? La razón radica en que el método esta basado en la analogía del proceso de 
recocido físico. Este proceso inicialmente involucra la fundición un metal o un vidrio a altas 
temp~raturªs y despupes enfirarlo lentamente hasta que alcanza un estado estable de baja 
energía con las propiedades físicas deseadas. A cualquier temperatura T dada durante este 
proceso, el nuvel de energía de los átomos en la substancia está flucutando pero con una 
tendenciaa decrecer. Un modelo matemático de como los niveles de energía fluctúan asume 
que los cambios ocurren de manera aleatoria excepto en algunos donde el incremento en Tes 
permitido. En particular, la probabilidad de aceptar un incremento cuando la temperatura T 
tiene la misma forma que la probabilidad de aceptación en las reglas de selección de 
movimiento del Recocido Simulado. 
La analogía para un problema de optimización en la forma de minimización es que el 
nivel de energía de la substancia en el estado corriente del sistema corresponde al valor de la 
función objetivoa la solución corriente factible del problema. El objetivo de que una substancia 
alcance el estado estable con un nivel de energía que es tan pequeño como sea posible, 
corresponde a haber obtenido una solución factiblecon un valor de la dución objetivo que sea 
tan pequeño como sea posible. 
Justo como en un proceso físico de recocido, una pregunta clave cuando se designa un 
algoritmo de Recocido Simulado para un problema de optimización, es selecciónar una 
programación adecuada de las temperaturas a usar. (Debido a la analogía con el proceso 
físico de recocido, nos referiremos en adelante a la T como la temperatura). Esta 
programación necesita especificar el valor inicial y relativament,~ grande de T así como los 
valores subsecuentes que progresivamente iran reduciendo su valor. También es necesario 
especificar cuantas iteraciones deberán realizarse en cada valor de T. La selección de estos 
parámetros para ajustarse al problema bajo consideración es un factor clave en la efectividad 
del algoritmo. Algunos experimentos preliminares pueden s,~r usados para guiar esta 
selección de parámetros del algoritmo. 
Algoritmos Genéticos 
En el campo de ciendas computacionales, un algoritmo i~enético es una búsqueda 
metaheurística que copia el proceso de selección natural aplicando técnicas como: herencia, 
24 
Alternativa Heurística de Método de Centro de Masas para el Problema de Ruteo de Vehículos 
mutación, selección y cruce. Este metaheurístico es usado rutinariamente para generar 
soluciones útiles para la optimización y problemas de búsqueda. Los algoritmos genéticos 
pertenecen a un grupo mayor denominado algoritmos evolutivos. 
En un algoritmo genético[47], una población o candidato a solución de optimización para un 
problema es "evolucionado" a mejores soluciones. Cada candidato a solución tiene un grupo 
de propiedades que pued1~ "mutarse" y "Alterarse". La evolución usualmente empieza de una 
población de individuos aleatoriamente generada, y es un proceso iterativo, con la población 
de cada iteración llamada generación. En cada generación, la "aptitud" de cada individuo en la 
población es evaluado; la "aptitud" (refiriéndose al término de selección natural: "sobrevivencia 
del más apto") es generalmente el valor de la función objetivo en el problema de optimización 
a ser resuelto. Los individuos son estocásticamente seleccionados de la población corriente, y 
cada "genoma" del individuo modificado para formar una nueva generación. La nueva 
generación es un candidato a solución y es entonces usada en la siguiente iteración del 
algoritmo. Comúnmente, el algoritmo termina cuando se cumple con un determinado criterio, 
que toma en cuenta la calidad a priori de la solución obtenida, y el número de "generaciones". 
Durante cada generación, una sucesión de operadores es aplicada a los individuos de 
la población para generar una nueva población para la siguiente generación. Cuando uno o 
más individuos son usados por un operador se les llama "padres". Los individuos originados 
por la aplicación de dichos operadores son llamados "críos" ó "hijos". Esto significa que, 
cuando dos operadores se aplican sucesivamente, los "críos" generados por uno pueden 
convertirse en los "padres de otros"[47]. 
Algunas limitaciones de los métodos metaheurísticos radican en el conocimiento del 
problema por la persona que hace el planteamiento y los criterios de convergencia. Esto 
puede . llevar, como se mencionó antes, a que se . encuentre una solución que no 
necesariamente sea la óptima o que el algoritmo no converja en nuestros parámetros por las 
restricciones que se pudieran haber planteado, de forma errónea. al principio del problema así 
como la solución inicial 
25 
Altern.;liva Heuríst:ca de Método de Cent;o de Masas para ul h.:>biema de Rute-o de Vehículos 
Comparación de Metaheurísticos con los Heurísticos clásicos. 
Los algoritmos metaheurísticos comparados con los heurísticos clásicos demuestran 
una búsqueda con más detalle en el espacio de solución permitiendo algunas veces 
' -
movimientos inferiores y, algunas veces no factibles, así como la reicombinación de soluciones 
para crear otras nuevas. Está área de investigación ha expmimentado un crecimiento 
formidable durante los pasados í O años y ha producido algunosde los más eficientes y 
flexibles heurísticos[2]. Es justo decir que, no obstante las ganancias en la calidad de las 
soluciones obtenidas con estos heurísticos se han hecho, frecuentemente a expensas de 
•, 
velocidad y simplicidad, aunque no es el caso en algunas de las más recientes 
implementaciones. La década pasada ha sido muy rica en el diseño y prueba de algoritmos, 
algunas ideas prometedoras no se han traducido en algoritmos igualmente buenos, mientras 
otras han soportado la prueba del tiempo. La búsqueda Tabú (TS)[13] es claramente uno de 
los mejores metaheurísticos para el VRP. Por mucho, la mejor implementación para el VRP 
domina otros procesos de búsqueda tales como el Recocido Simulado[43], algoritmos 
genéticos[44], sistemas de colonias de hormigas[45], y redes neuronales[46] . La idea detrás 
de la búsqueda Tabú es lle?var a cabo una investigación local a través del movimiento, en una 
iteración t, de una solución xt hacia la mejor respuesta x1+1 en su vecindario. Desde que se 
mueve de Xt a X1+1 puede causar que la función objetivo se deteriore, un mecanismo anticíclico 
es puesto en marcha, nombrando cualquier solución que posea algún atributo de x, es 
declarado prohibido o tabú, para un número de iteraciones. Así, e11 efecto el mejor vecindario 
x1+1 de x es solamente seleccionado sí no es tabú o sí claramente no se ciclará la solución . 
Varios mecanismos adicionales tales como; la diversificación e intensificación han sido 
implementados por una gran variedad de investigadores. Desde luego, no todos los 
heurísticos de búsqueda Tabú para el VRP han sido igualmente exitosos. La primera 
identificación conocida por Willard[48] no hizo uso de una estructura de vecindario lo 
suficientemente poderosa para permitir la identificación de soluciones de alta calidad. En 
contraste, varias implementaciones que le siguieron contenían demasiados dispositivos y 
parámetros definidos por el usuario. Ha existido una tendencia en años recientes hacia 
implementaciones más esbeltas. 
26 
_1:1 __ A_l_te_rn_a_ti-va_H_e_u-rís_t __ ic_ª_ªe_M-ét-od_o_d_e_C_e_nt-ro_d_e_M_a_sas para el Problema ele Ruteo de Veh¡::ulos 
Otro de los metaheurísticos utilizados es el Recocido Simu!ado[43], el cual nace de las 
estructuras complejas del espacio de configuración para un problema de optimización difícil 
inspirGdo en las analogías con fenómenos físicos, que lideraban 3 investigadores de la 
comuridad_ de IBM - S. Kirkpatrick, C.D. Gelatt and M.P. Vecchi - quienes propusieron en 
1982 y publicaron en 1983 un nuevo método iterativo: La técnica del Recocido Simulado, 
puede evitar un mínimo local. Un trabajo similar, desarrollado de forma independiente al 
mismo tiempo por V. Cerny[Cerny, 1985],fue publicado en 1985. 
Desde su descubrimiento, el método del Recocido Simulado ha probado su efectividad 
en varios campos tales corno el diseño de circuitos eléctricos, el procesamiento de imágenes y 
el VRP. Por otro lado se ha encontrado demasiado ambicioso o incapaz de resolver ciertos 
problemas de optimización combinatoria, que puedan ser resueltos con algunos heurísticos 
específicos. 
La Búsqueda Tabú que se enfoca en "escalar" la colina más alta en el ángulo más 
agudo hasta que alcanza la cima y después empieza a escalar colina a bajo hasta encontrar 
la siguiente pendiente hacia arriba y llegar a la siguiente cima, que sería la siguiente solución 
óptima local. El problema es que requiere mucho tiempo (iteraciones) en encontrar cada 
solución óptima local hasta encontrar una solución óptima global. 
A diferencia de la Búsqueda Tabú, la técnica del recocido simulado, se enfoca en una 
sóla búsqueda por la solución global óptima. Dado que la colina más alta puede estar en 
cualquier lugar de la región de factibilidad, el enfasis inicial en tomar pasos en direcciones 
aleatorias (excepto para rechazar algunas, pero no todos los pasos que generen soluciones 
menos óptimas que las anteriores) con el fin de explorar la mayor cantidad posible de la región 
de factibilidad como sea posible.Debido a que la mayoría de los pasos aceptados son cuesta 
arriba, la búsqueda eventualmente tenderá a aquellas partes de la región de factibilidad que 
contengan las "cimas" r,ás altas. 
Para ser más específicos, cada iteración del proceso de búsqueda del Recocido 
Simulado se mueve del intento de solución corriente a un vecino inmediato en el vecidario 
local de esta solución, al igual de la Búsqueda Tabú. Sin embaqJo la diferencia entre ambas 
27 
Alternativa Heurística de Método de Centro de Mas.¡s para el Prob'.ema de Rutco de Vehículos 
técnicas radica en cómo un vecino inmediato es seleccionado para el siguiente intento de 
solución. -
, Just~ como en un proceso físico de recocido, una pregunta clave cuando se designa un 
algoritmo de Recocido Simulado para un problema de optimización, es selecciónar una 
programación adecuada de las temperaturas a usar. (Debido a la analogía con el proceso 
físico de recocido, nos referiremos en adelante a la T como la temperatura). Esta 
programación necesita especificar el valor inicial y relativamente grande de T así como los 
valores subsecuentes que progresivamente irán reduciendo su valor. También es necesario 
especificar cuantas iteraciones deberán realizarse en cada valor de T. La selección de estos 
parámetros para ajustarse al problema bajo consideración es un factor clave en la efectividad 
del algoritmo. Algunos experimentos prelimi~ares pueden ser usados para _ guiar esta 
selección de parámetros del algoritmo. 
De lo anterior podemos concluir esta parte que ningún heurístico clásico tiene una 
buena calificación en precisión y flexibilidad. En esta categoría, el celebrado heurístico de 
Clarke y Wright tiene al menos la ventaja de ser rápido y simp!e para implementar, lo cual lo 
hace uno de los algoritmos más recurrentes para la solución de VRPs y es el que se estará 
utilizando para soportar la hipótesis en este trabajo. No obstante lo anterior, en el contexto del 
VRP se debe planear a largo plazo ya que graneles sumas de dinero están en riesgo. Vale la 
pena invertir tiempo y recursos en un método que desempeñe una exploración más extensiva, 
sencilla y eficiente y que se ajuste a mejores niveles en cuanto a Precisión, Flexibilidad, 
Simplicidad y Velocidad. 
Por otro lado, los metaheurísticos son, en general, un tipo de método de solución general 
que orquesta la interacción entre procedimientos de mejora local y estrategias de alto nivel 
para crear un proceso que es capaz de escapar del óptimo local y desempeñar una búsqueda 
robusta en una región factible. 
Las soluciones usadas para obtener los mejores resultados cuando se tratan de resolver 
VRP, los Heurísticos y Metaheurísticos son los algoritmos que hasta ahora, mejor cumplen los 
4 factores que se plantarori anteriormente (exactitud, simplicidad, velocidad y flexibilidad). 
28 
Alternativa Heurística de Método de Centro de Masas para el Problema de Ruteo de Vehículos 
2.3. El problema de inicialización en VRP 
El principio de un algoritmo de "mejora iterativa" consiste en que: uno empieza con una 
configuración inicial, la cual, casi siempre se hace de manera aleatoria, sin reglas y, por 
consecuencia no es la más adecuada, por ejemplo, en el caso de la colocación de los 
componentes de un circuito electrónico, y puede ser determinada por un diseñador o una 
persona que necesariamente debe contar con conocimiento del algoritmo que va a resolver la 
trayectoria más pequeña así como de las limitaciones inherentes al producto o servicio que se 
está ejecutando. Una modificación elemental es entonces probada y frecuentemente se le 
conoce como "movimiento" (por ejemplo, 2 componentes elegidos al azar son permutados o 
uno de ellos es cambiado de lugar), y los valores de la función objetivo son comparados, antes 
y después de la modificación. Sí el cambio nos lleva a una reducción en la función objetivo, esaceptado, y la configuración obtenida es un "vecino" de la precedente, y es usada como punto 
de partida para la siguiente prueba. En caso contrario, uno regresa a la configuración anterior, 
antes de hacer el siguiente intento. El proceso se hace iterativo hasta que cualquier 
modificación resulta peor. 
Función 
Objetivo 
Configuración 
Figura 2. Representación gráfica de óptimos locales en la solución del VRP [47] 
La figura 1 nos muestra que este algoritmo de mejora iterativa[4 7] (método clásico o 
método descendente) no nos lleva, en general, al óptimo global, sólo a un mínimo local que 
constituye la mejor solución tomando en cuenta las asunciones iniciales. 
Para mejorar la efectividad del método, uno puede, desde luego, aplicarlo varias veces 
en condiciones iniciales arbitrarias y quedarse con la mejor scludón de mejor mínimo local 
29 
Alternativa Heurística de Método de Centro de Ma::.as par;~ e: Problema de Ruteo de Vehículos 
obtenido. Sin embargo, este procedimiento apreciablemente incrementa el tiempo de 
procesamiento del algoritmo en una computadora, y puede no encontrar la configuración 
óptima. La aplicación repetida del método descendente no garantiza su determinación y es 
particularm!3nte inefectivo cuando el número de mínimos locales crece exponencialmente con 
el tamaño del problema. 
Por otro lado, para brincar este obstáculo del mínimo local, otra idea que ha 
demostrado ser muy rentable, tanto que es el corazón de los metaheurísticos basados en el 
vecindario (Recocido Simulado y Búsqueda Tabú[47]): es una cuestión de autorización, de 
tiempo en tiempo, los movimientos de incremento, en otras palabras aceptar una degradación 
temporal de la situación, durante un cambio en la configuración corriente, este es el caso sí 
uno pasa de en a en' (corno se muestra en la figura de arriba). Un mecanismo para controlar 
:as degradaciones, específico a cada metaheurístico, hace posiole que se eviten las 
divergencias del proceso. En consecuencia se hace posible trascender la trampa del mínimo 
local para explorar otro valle más "Prometedor". Los metaheurísticos "distribuidos" (tales como 
algoritmos evolutivos) también tienen mecanismos que les permites partir de una solución 
particular fuera de un "pozo" en una solución particular de la función objetivo. Estos 
mecanismos, (como la mutación en algoritmos evolutivos) afecta la solución a mano, en este 
caso, para asistir a los mecanismos colectivos para evitar los mínimos locales, que representa 
un control paralelo en un juego de "población" de soluciones[49]. 
El iniciar con una solución aleatoria genera dos riesgos importantes; a) qué tome más 
tiempo (número de iteraciones) en llegar a una solución óptima ya que se parta de un óptimo 
local y b) que se aleje al algoritmo de la "mejor" solución. Esto afecta las consideraciones de 
exactitud y velocidad. Al día de hoy no se ha desarrollado, dentro de la investigación de 
artículos y libros que se realizó, una metodología estructurada para la solución inicial de 
ningún algoritmo diseñado para dar una solución al VRP. 
En la mayoría de los casos la solución inicial es !a secuencia de bs puntos y, en el 
caso de algoritmos genéticos se propone un generador aleatorio r;ara la solución inicial. Esto 
ha hecho que todos los estudios y metodologías . se enfoquen en la resolución de problemas 
sin la definición de un punto inicial y sin el análisis de que tanta pueáe esto influir en los 
30 
Alternativa Heurística de Método de Centro de Masas para el Problema de Ruteo de Vehículos 
resultados de un algoritmo de VRP[50] y su influencia en los 4 factores que hemos definido 
para caracterizar un algoritmo[2]. 
2.4. _ Hipótesis 
• Se puede crear una alternativa heurística lo suficientemente sencilla y fácil de 
implementar con resultados aceptables. 
• Generar una propuesta inicial más eficiente que las generadas de manera aleatoria, 
deberá reducir si!~nificativamente el número de iteraciones en un algoritmo 
metaheurístico. 
• Empezar un algoritmo metaheurístico -con una propuesta inicial estructurada debe 
propiciar que el _algoritmo llegue a soluciones más óptimas. 
2.5. Objetivos de la tesis 
Desarrollar un algoritmo de fácil ejecución para obtener una solución factible al 
problema de VRP. El método desarrollado debe ser lo suficientemente preciso y simple para 
que, aún que no garantice un resultado óptimo comparado con otros métodos, sea una 
alternativa lo suficientemente eficaz para que pueda ser implementada sin necesidad de 
realizar grandes inversiones en hardware y software. 
31 
Alternativa Heurística de Método de Centro de Masas para el Probiema de Ruteo de Vehículos 
3.- Métode> propuesto de inicializ:ación para VRP 
32 
Alternativa Heurís;tica de Método de Centro de Masas para el Problema de Ruteo de Vehículos 
3. Método propuesto de inicialización para VRP 
(Este material fue aceptado para su publicación el 24 de Agosto del 2013 como: "Alternativa 
Heurística MCM para el Problema de Ruteo de Vehículos", Revista INGE CUC, Universidad 
Je la Costa, Volumen 9 Nº2) 
3.1. Método de Inicialización por Centros de Masa 
El método propuesto tiene un enfoque a la solución del VRP a través de la optimización 
de lo general a lo particular, referenciándose al principio mecánico de "centros de masas" el 
cual se define como el punto geométrico que dinámicamente se comporta como si en él 
estuviera aplicada la resultante de las fuerzas externas al si~.tema[51]. Normalmente se 
abrevia como centro de masas. 
A continuación se presenta el algoritmo de MCM para obtener una solución factible 
para un VRP simple, con un depósito, y un vehículo. Aunque aquí se presenta la versión más 
simple del algoritmo, es relativamente fácil de ajustar para una flota heterogénea de vehículos 
y con varios depósitos. y no necesito de ser codificado, por io que todos los cálculos en los 
ejemplos de aplicación fueron 1echos a mano. Lo cual ilustra la facilidad del método. 
Descripción 
El método se basa en el concepto físico donde en un sistema de masas puntuales[51] 
el centro de masa es el punto donde, a efectos inerciales, se supone está concentrada toda la 
masa del sistema. Al llevar esto a la resolución de un problema de VRP, se busca lograr una 
solución inicial optimizando de lo general a lo particular, esto es; se segmenta el problema en 
4 cuadrantes y se calcula su centro de masa, donde las reglas del método nos permiten 
obtener una secuencia inicial, posteriormente, cada cuadrante se divide así mismo en 4 y se 
aplica el mismo método para los centros de masa de cada cuadrante, y así sucesivamente 
hasta que la división es tal que, en cada cuadrante sólo hay un destino del VRP[52]. 
33 
ho. Alternativa Heurblica ce r.,;i~todo de Címüo áe Masas ¡:.ara .,: Problema de Ruteo de Vehíc~los 
AA~-· 
1e 1 ¡· ---, 1 Q • ,;;,¡ 1 =1:;-
1 
G • 1 • 
• • o 
• 
• • 1 
Figura 3. Ejemplo de la división iterativa en cuadrantes (,elaboíación propia) 
En la figura 3 se puede observar que, la secuencia de cada uno de los cuadrantes así 
como la división de los puntos que va a incluir, se realiza mediante el cálculo de centros de 
masa. Los pasos son los :siguientes 
Paso 1. Al conjunto de vértices por visitar X; = {(x1;, y2¡) i:=1,2, .. n} se subdivide en 4 
cuadrantes arbitrarios V1, V2, V3, V4. 
X y 
Cuadrante 1: - , -
2 2 
y 
Cuadrante 2: X . -
2 
Cuadrante 3: X, Y 
X 
Cuadrante 4: -, Y 
2 
Paso 2. Si 4 cuadrantes son suficiente resolución para el problema, ir a 4) y proceda a 
calcular la secuencia de visitas a cada uno de los cuadrantes (cada uno puede contener 
varios vértices). (El proceso más exacto implica que quedará solo un punto por cada 
subdivisión, la ventaja del algoritmo es que le permite discriminar por grupo de puntos) 
Paso 3. Si requiere más cuadrantes (mayor resolución) sub-divida cada cuadrante, en tantos 
sub-cuadrantes V¡ cómo se requiera (i=·t, 2, ... m en tola~) 
Paso4. Etiquete con letras en orden alfabético (A, B, C y D) los 4 cuadrantes, empezando por 
aquel que contiene el punto inicial (y final) de la ruta y se siga la numeración en dirección 
contraria a las manecillas del reloj. (Esta nomenclatura no significa que será la secuencia de la 
inicialización final). 
34 
Alternativa Heurística de Método d~ Centro de Masas para el Problema de Ruteo de Vehículos 
El punto inicial-final: P1 ,N tiene coordenadas (x,'V): 
X Y X Y 
Sí x<=- y !p<=-; entonces el cuadrante: -, - será nombrado cuadrante A 
,2 - 2 2 2 
X y y 
Sí - <=x<=X y !p<=-; entonces el cuadrante: X, - será nombrado cuadrante A 
2 2 2 
X y 
Sí - <=x<=X y- <=!p<=Y; entonces el cuadrante: X, Y será nombrado cuadrante A 
2 2 
X Y X 
Sí x<=- y- <=!p<=Y; entonces el cuadrante: - , Y será nombrado cuadrante A 
2 2 2 
La secuencia continuará en dirección contraria a las manecillas del reloj. 
Sea B' el cuadrante adyacente sobre el eje Y candidato a nombrarse B 
Sea B" el cuadrante adyaGente sobre el eje X candidato a nombrarse B 
Entonces: 
Sí CMB'(X, Y)-CMA(X, Y)< CMB'(X, Y)-CMA(X, Y) entonces B' será nombrado cuadrante B 
Sí CMB'(X, Y)-CMA(X, Y)> CMB'(X, Y)-CMA(X, Y) entonces B" será nombrado cuadrante B 
Sí CMB'(X, Y)-CMA(X, Y) == CMB'(X, Y)-CMA(X, Y) entonces el cuadrante que se encuentre en 
dirección contraria a las manecillas del reloj será nombrado cuadrante B. 
El cuadrante C será el adyacente al cuadrante nombrado 8, y el cuadrante O será el 
cuadrante restante. 
Paso 5. Calcule el centro de masas de CM; (i=1, .. . , m) para cada cuadrante V¡, donde m es el 
número total de sub-cuadrantes. Utilice sólo los puntos que no se encuentren sobre las 
divisiones de los sub-cuadrantes V¡. 
X y 
Para el cuadrante - , - la posición del Centro de Masas CMa será: 
2 2 
(L~1 Xi) (Lf:1 Yi) X Y , Siempre que (x;< ·-, y;<-) 
xnQ ynQ 2 2 
Para el cuadrante X, Y/2 la posición de/ Centro de Masas CMa será: 
1 
(Lf:1 Xi) (Lf:1 Yi) ·. X Y , Siempre que (- < X;, y;< - ) 
xnQ ynQ 2 2 
Sí el cuadrante: X, Y la posición del Centro de Masas CMa será: 
35 
Alternativa Heurística de Método de Centro de Masas para el Problema de Ruteo de Vehículos 
(L!1 J~i) (L!1 Yi) X Y , Siempre que ( - < X;, - < y;) 
xnQ ynQ 2 2 
Sí el cuadrante: X/2, la posición del Centro de Masas CMa será: 
(Lf:1 Xi) (Lf:1 Yi) X Y --------""-- , Siempre que (x;< ~-, -<y;) 
xnQ ynQ 2 2 
Si no hay vértices sobre las sub-divisiones vaya al Paso 8. 
Paso 6. Si hay puntos sobre las divisiones de los sub-cuadrantes, defina la pertenencia de 
estos vértices Xj a los sub-cuadrantes V¡ calculando las distancias dij rectilíneas del vértice Xj 
al CM; para los cuadrantes i que tengan su frontera sobre X¡. Asigne el punto X¡ al V¡ con la 
mínima distancia. Si hay empates asigne al Vi con menor dispersión interna y si el empate 
persiste asigne a cualquiera de ellos. Si el cuadrante i est~ vacío utiiice el centro geométrico 
del cuadrante en lugar del CM;. 
(Xi) [ X Y] , ·(Xi) [ X Y] , Sí - E X· < - y· < - O - E X· > - y· < - O Yi l 2 I l 2 Yi i 2 I i 2 
(;:) E [ Xi > : , Yi Y] , (Xi) [ X Y] > - O - E X· < - y· > -2 Yi i 2 I l 2 
entonces: 
Sí 
1 
[( CMs (X2 - xl)) + ( CM5 (Y2 - y¡) )]2 < 
1 
[( CMs+1 (X2 - x¡)) + ( CMs+i (Y2 - y¡) )J2 
Entonces (X¡,y¡} pertenecerá al punto s, de lo contrario pertenecerá al punto s+1. Una vez 
íeasignados los puntos se procederá a recalcular los nuevos centros de masa para los 
cuadrantes usando todos los puntos que le fueron asignados a dicho cuadrante. 
36 
Alternativa Heurística de Método de Centro de Masas para el Problema de Ruteo de Vehículos 
Paso 7. Recalcule los centros de masa como se definió en el paso 5 CM; para i=1,2, .. , m, 
incluyendo en cada subco~junto i los puntos asignados en el Paso 6. 
Paso 8. lni_cie la secuencia de visita (ruta) en el punto inicial A con CM; (i=A) y conecte a Vi 
(i=A) con el Vk adyacente con el CMk más cercano, usando la distancia rectilínea entre los dos 
centros de masa. Los Vi adyacentes serán los que comparten más de un punto en su frontera 
(una arista de los sub-cuadrantes). A y k se consideran conectados (A-k) y k se elimina de la 
lista de puntos por conectar, k es el punto extremo de la trayectoria. 
n=2 
n tiene incrementos iguales a n=n*2 
Repetir desde SCY = 1 hasta n 
Repetir desde SCX = 1 hasta n 
(Lf:1 Xi) (Lf:1 Yi) El CMQileración= , 
xnQ ynQ 
Siempre que: 
((SCX-l)X)< X·< ((SCX)X) ((SCY-l)Y)< . <((SCY)Y) 
2n 1 2n ' 2n Yi 2n 
(SCX)X (SCY)Y 
Sí Xi = , Yi == se tomará la distancia al centroide más cercano de 
2n 2n 
cualquiera de los subcuadrantes adyacentes y se volverá a calcular el centroide de dicho 
subcuadrante con el nuevo valor. 
Paso 9. Empezando una nueva conexión iniciando ahora en k CM; (i=k) y conecte a Vk con el 
vk· adyacente que tenga ·~I CMk' más cercano a CMk, usando la distancia rectilínea entre los 
dos centros de masas. A y k se consideran conectados (A-k-k') y ahora k' será el punto 
extremo de la trayectoria y se quita de la lista de vértices por conectar. 
Paso 10. Repita el Paso ~I ahora con k' como extremo y conectando al siguiente vértice hasta 
que termine con todos los m-1 vértices y tenga que regresar a A. 
37 
A_ AJWmativa Heu,ística de Mótodo ci• Cont<o de Masas p,"c< ei Prnble~a de Ruteo de Vehóculos 
Para comprobar el método, se resolvió el siguiente problema con sólo 16 puntos. 
Siguiendo el método se obtiene: 
Dado el problema mostrado en la figura 4: 
Figura 4. Ejemplo para demostrar el método. (Elaboración Propia) 
En este problema plantea el salir del punto 1, recorrer las 15 ciudades representadas 
por puntos y regresar al inicio recorriendo la menor distancia posible. 
Paso 1. Al conjunto de vértices por visitar X;= {(x1;, y2J i=1,2, .. n} s.e subdivide en 4 cuadrantes 
arbitrarios V1, V2, V3, V4. 
38 ' 
Alternativa Heurística de Método de Centro de Masas para el Problema da Ruteo de Vehículos 
Figura 5. División en cuadrantes, primera iteración. [52] 
Paso 2. Si 4 cuadrantes es suficiente resolución para el problema, pase a 4) y proceda a 
calcular la secuencia de visitas a cada uno de los cuadrantes (cada uno puede contener 
varios vértices) . 
Paso 3. Si requiere más cuadrantes (mayor resolución) sub-divida cada cuadrante, en tantos 
sub-cuadrantes V¡ cómo se requiera (i=1, 2, ... m en total) 
Paso 4.- Etiquete con letras en orden alfabético (A, B, C y D) los 4 cuadrantes, empezando 
por aquel que contiene el punto inicial (y final) de la ruta y se siga la numeración en dirección 
contraria a las manecillas del reloj. (Esta nomenclatura no significa que será la secuencia de la 
inicialización final). 
39 
Alt8mMiVII Heuristlca de Método de Centro de M8sas para el Problema de Ruteo de Vehfculoe 
2 
e 14 
Figura 6. Secuenciación de cuadrantes, denotando el punto inicial y final en el círculo rojo. 
(Elaboración Propia) 
Paso 5. Calcule el centro de masas de CM¡ (i=1, ... , m) para cada cuadrante V¡, donde m es el 
número total de sub-cuadrantes. Utilice sólo los puntos que no se encuentren sobre las 
divisiones de los sub-cuadrantes V¡. 
Si no hay vértices sobre las sub-<livisiones vaya a Paso 8. 
Punto 1 
Punto 10 
Punto 11 
Punto 12 
Media 
Punto 6 
Punto 7 
Punto 8 
Media 
Cuadrante A 
1 9 
10 10 
11 12 
12 14 
11.25 8.5 
Cuadrante 8 
A1t8matiYa Heurlstlca de Método de Centro de Masas pera el Problema de Ruteo de Vehlculos 
Cuadrante C 
Punto 3 4 2 
Media 4 2 
Cuadrante D 
Punto 2 9 4 
Punto 14 14 4 
Punto 15 12 4 
Media 11.66 4 
Tabla 2. Coordenadas de los puntos en el cuadrante A, B, C y D así como sus centros de 
masas (media). (Elaboración propia) 
Paso 6. Si hay puntos sobre las divisiones de los sutH:uadrantes, defina la pertenencia de 
estos vértices X; a los sutH:uadrantes Vi calculando las distancias d;¡ rectilíneas del vértice X; 
al CM; para los cuadrantes i que tengan su frontera sobre X;. Asigne el punto X; al Vi con la 
minima distancia. Si hay empates asigne al Vi con menor dispersióninterna y, sí el empate 
persiste asigne el punto al cuadrante que siga en la secuencia a cualquiera de ellos. Si el 
cuadrante i está vacio utilice el centro geométrico del cuadrante en lugar del CM;. 
8 11 
12 
14 
Figura . os que no se han 
41 
-
Alt8matlva Heur1dca de IIModo de Centro de Masa para el Problema de Rutao de Vehicutos 
Finalmente los puntos quedan definidos de la siguiente manera: 
Cuadrante A Cuadrante B 
1 
9 
10 
11 
12 
4 
5 
6 
7 
8 
Cuadrante C 
3 
Cuadrante D 
2 
13 
14 
15 
16 
Tabla 3.-Asignación de puntos a un cuadrante en particular (Elaboración propia) 
Paso 7. Recalcule los centros de masas CM¡ para i=1,2, .. , m, incluyendo en cada 
subconjunto i los puntos asignados en el Paso 6. 
Paso 8. Inicie la secuencia de visita (ruta) en el punto inicial A con CM¡ (i=A) y conecte a Vi 
(i=A) con el Vk adyacente con el CMk más cercano, usando la distancia rectillnea entre los dos 
centros de masa. Los Vi adyacentes serán los que comparten más de un punto en su frontera 
(una arista de los sub-cuadrantes). A y k se consideran conectados (A-k) y k se elimina de la 
lista de puntos por conectar, k es el punto extremo de la trayectoria. (A-D-C-8-A) 
14 
3 • 
Figura 7: Centros de masas para la secuencia, el centro de masas que esté más cercano al 
centro de masas de A será el siguiente en la secuencia. (Elaboración propia) 
Alternativa Heurística de Método de Centro de Masas para el Problema de Ruteo de Vehículos 
Repertir desde Paso 1 al 9 .- A su vez los cuadrantes de definidos se dividE:n quedando corno 
en la figura Se repiten las instrucciones del paso 1 al 4, comenzando con el cálculo del centro 
de masa de cada subcuadrante. Se enumeran los cuadrantes, para simplificar sólo se 
nume¡arán,aquellos que contengan puntos o la posibilidad de que un punto de sea asignado, 
por ejemplo los 2 cuadrantes adyacentes al punto 3: 
84 A3 
12 
81 A2 
C4 03 
C1 C2 01 D2 
Figura 8: Centros de masas para lo3 sub-cuadrantes definidos. [52] 
Paso 5 y 6.- Se asignan a un solo cuadrante los puntos que están en medio de 2, sólo se 
asignarán aquellos que hayan quedado entre 2 cuadrantes de la nueva división, por ejemplo 
el punto 16 que se definió para el cuadrante O, quedará en el cuadrante 01, por otro lado, el 
punto 15 deberá definirse, usando las mismas reglas de media aritmética y desviación 
estándar, entre el cuadrante 01 y el 02. 
43 
AltBmativa Heuriatica de Método de Centro de Masas para el Problema de Rutlto de Vehfcutoa 
84 A3 
12 
81 A2 
C4 D3 
C1 3 C2 D1 
Figura 9: Medición de la distancia de un punto no definido al Centro de Masas más cercano. 
(Elaboración propia) 
Paso 7. Recalculando los centros de masas CM; para i=1,2, .. , m, incluyendo en cada 
subconjunto i los puntos asignados en el Paso 6. 
Paso 8. Inicie la secuencia de visita (ruta) en el punto inicial A con CM; (i=A) y conecte a V¡ 
(i=A) con el Vk adyacente con el CMk más cercano, usando la distancia rectilinea entre los dos 
centros de masa. 
A1: 1,9, 10 81:4,5,6 C1:3 01: NA 
A2.: 12 82:7 C2: NA 02: NA 
A3: 11 E\,3: 8 C3: NA 03: 13,14,15 
A4:NA 84: NA C4: NA 04: 2, 16 
Tabla 4: Clasificación de destinos por su~uadrante 
Alternativa Heuristica de llilDdo dlt Centro de -- pma el Problema de Rutao de Vehlculoe 
Paso 8 (segunda iteración).- Se calcula la secuencia en base a la cercanía de los centros de 
masas y queda como sigue: A1-A4-A3-A2-D3-D2-D1-D4-C1-B1-B4-B3-B2-A1 
B4 
81 
C4 
C1 D2 
Figura 1 O: Comparación de la distancia enbe centros de masas para definir la secuencia del 
sub-cuadrante 
Repetir desde el paso 1 al 9 (tercera iteración}.- Una vez más, se dividen en sub cuadrantes 
llegando a puntos individuales. 
1144 1143 A34 A33 
Figura 11: División en sub-cuadrantes con puntos individuales [52] 
Paso 8 y 9.- La secuencia final queda, en base a la secuencia anterior: 
45 
A 1-A4-A3-A2-03-02-D1-04-C1-81-84-83-82-A 1 
Figura 12: rep.esc:11ación de la secuencia ópli1.a (aaboración propia) 
Fmamente, el orden de los puntos sigue la sealellcia de los aJadrantes definidos al igual que 
en los anteriores con la convención de iniciar con la esquina i1ferior izquierda de cada sub 
cuadrante, quedando la soluci6n propuesla de la siguiente fonna: 
F1gura10. Solución propuesta. [52] 
... ,.._ ltlullllllca d9 MIS i1D d9 C..S.Vd9 ...._ pma el Pnlrl a d9 Rullo d9 v.nclculm 
3.2. Las soluciones iniciales alaallDrias conba el método de "Centros 
de Masa" 
Para comparar la efectividad del método de inicialización propuesto co11ba las 
inicializaciones aleatorias se llevaron a cabo 40 corridas aleatol ias del problema anterior con 
16 puntos para obtener una media y una desviación estándar de las distancias obtenidas, que 
permitiera g,aficar una dislri>uc:i6n normal y. posteriormente ver en qué punto de la 
distmución quedaba la distam de la solución propuesta: a lo que se obtuvo una álStribución 
normal con media mwsbal de: 128.8 y una desviación estándar muestral de 16.53. 
Gtaficalldo dicha disbi>uci6n utAn·-..do Minitab se obtuvo el l'esllllado mosbado en la figura 
12: 
s , ... a rr 
• 1 ,.....,T .. ~ ·~ R.J2 i ....... a5ZZ .... DLm 
sm.. J6Jlt o 
Y.-.at :a31 
Ul 
~ -G.8l9N1 ::, --- OJm&l!J o.. • .. E ...... - a •o.- ... ;;:: ..... 01.9 
~ :11110..- 1JUII ...... -- Q) 911,C~..._. .. .._ ..... e 
ID.4t DU6 o 
1 911,C........_.. ........ ~ 
Q1 i lllLDI JlUS "'O .. c-......,.. .. sm. ,.. 
.... : 77 7 ... o.n 2UI ~~~~ 
V1 
1 .:j :9 
~ 
~ 
-..,~--.,,~--.,,~._-,~--.-,~--.-,~---,---' 
ms S1111 ms ... ms ma IIID 
-
En la figwa 12 pleCle apreciarse que es una disbi»uci6n normal usaldo la prueba de 
nonnaidad de Anderson-Oa•U:531 adicionando 1as dislancias de 1a solución por e1 mélodo 
de cenbos de masa que da una distancia de 62 y la solución obtenida por un prog1ana de 
oplii,Minoón de VRP llamado VRP Solver (VRP Solver v1.3. L.awrence V. Snyder. L..ehigh 
Universily. 2004) que ejecuta el algüiib,iu de Clarke-Wrighl(11) que arroja una distancia de 58 
~ 
.. .. 
·~ •• 
i 
Alternativa Heurtstlca de Método de Centro ele Masas para el Problema de Ruteo de Vehículos 
se obtiene una distribución no normal donde los dos últimos puntos están a más de 3 
desviaciones estándar de la media lo que haría casi imposible que esa solución se generara 
de manera aleatoria como se muestra en la figura 12. Además la solución por centro de 
masas está a sólo 0.24 desviaciones estándar de la solución óptima propuesta por el 
algoritmo de Clarke-Wright[11] lo que por sí misma la solución por centro de masas para un 
problema de 16 puntos podría considerarse una solución posible. 
Clarke-
Wright 
Figura 12: Distribución estadística de soluciones. (Elaboración propia) 
• 
48 
Alternativa Heurfotica de Método de C.:intro de Masas par~ el Probluma de Ruteo do Vehículos 
4.- Comparación del Método 
49 
Alternativa Heurística de Mttúdo 1:fo Centro de Masas para el Problem;1 1fo Rut~o de \hdiiculos 
4. Comparación de~I l\t1étodo 
4.1. Aplicación del método de "Centro de Masas" a un problema rnás 
complejo 
Se generaron de manera aieatoria 100 puntos: 
Etiqueta xlv 
1 6 11 
Etiqueta X y 
34 95 15 
~~-
~-, 
~queta X y I 
67 f 71 92 I . 
2 18 13 35 85 25 68 89 79 
3 25 7 36 90 21 69 79 94 
4 12 21 37 67 44 70 85 93 
5 23 17 38 80 32 71 1 58 
,--
6 15 25 39 84 31 72 3 58 
7 1 ,40 --
8 38 9 
9 8 l 40 
40 85 31 
>---
41 74 45 
42 81 44 
73 14 55 o-----f 74 6 66 
75 n 54 ,___ ,--
10 46 4 43 89 41 76 l8 58 
11 17 35 44 89 48 77 25 53 ~-
12 13 39 45 97 47 78 11 69 
13 48 5 46 54 59 79 7 74 
14 45 15 47 51 65 80 24 60 
15 32 28 48 66 52 81 23 62 
16 40 23 49 53 70 82 10 78 
>---
17 34 32 so 62 62 83 32 59 
,-
18 47 29 51 61 71 84 20 71 
19 50 30 52 50 87 85 10 87 
20 36 45 53 53 89 86 3 95 
21 44 41 54 80 63 87 33 67 
22 47 46 55 67 81 88 35 68 
23, 56 10 56 77 72 89 22 82 
r--
24 ,56 19 57 72 77 90 38 68 
25 60 17 58 96 56 91 9 97 
26 71 11 59 98 55 92 18 93 
r-
2i' 69 15 60 61 93 93 47 65 --t--
28