Scientia et Technica Año XXI, Vol. 21, No. 3, septiembre de 2016. Universidad Tecnológica de Pereira.

ISSN 0122-1701 225

Solución al Problema de Ruteo de Vehículos

con Capacidad Limitada (CVRP) usando una
técnica metaheurística
Solution to the Capacitated Vehicle Routing Problem (CVRP) using a
metaheuristic technique

Juan Pablo Orrego Cardozo, Daniela Ospina Toro, Eliana Mirledy Toro Ocampo
Ingeniería Industrial, Universidad Tecnológica de Pereira, Pereira, Colombia
[email protected], [email protected], [email protected]

Resumen— El problema de ruteo de vehículos (VRP) es uno de también es de gran interés por la variedad de aplicaciones que
los temas más importantes en las redes de distribución; con tiene en diversas áreas como: transporte, logística,
diversas aplicaciones en transporte, logística y comunicaciones, manufactura, militar, entre otros.
telecomunicaciones. Debido a la dificultad que implica resolver
instancias de gran tamaño con métodos exactos, la mayoría de los
El problema tradicional CVRP (por sus siglas en inglés
investigadores se han centrado en resolver problemas de la vida
real a través de técnicas metaheurísticas. En este trabajo, se Capacitated Vehicle Routing Problem ó Problema de Ruteo de
generan soluciones aproximadas para el CVRP tradicional Vehículos con Capacidad Limitada) puede ser descrito en su
usando la heurística de barrido de dos fases y resolviendo cada forma más sencilla como una flota de vehículos con
problema del agente viajero con el algoritmo genético modificado capacidades uniformes que tiene que satisfacer la demanda de
de Chu-Beasley. Se valida la metodología con casos de prueba de un grupo de clientes a través de un conjunto de rutas que
la literatura especializada. empiezan y terminan en un almacén común y que representan el
menor costo posible, así como la identificación del orden de
Palabras clave— algoritmo genético, agente viajero, heurísticas, visita a los mismos [2].
logística, metaheurísticas, problema de ruteo de vehículos.

Abstract— The Vehicle Routing Problem (VRP) is one the pivotal En la Tabla 1, se presenta una revisión del estado del arte con
topics in distribution networks. VRP has many applications on base en artículos de la literatura especializada. Dicho recorrido
transport, logistics and telecommunications. Due the difficulty in se hace desde el año de 1969, donde se aborda el tema por
solving large instances with exact methods, for solving real-life primera vez como el Problema de Despacho de Vehículos,
problems most researchers have been focused on metaheuristics. hasta el 2011. A través de los años, se generaliza como VRP.
In this work, approximate solutions to the traditional CVRP are Además, se observa que las técnicas de solución para resolver
generated using a two phase heuristic, sweep, and solving each este problema van desde las exactas exactas Branch and Bound,
traveling salesman problem with the modified genetic algorithm ramificación y corte, Branch and Cut, y el Branch and Cut and
of Chu-Beasley. The methodology is validated using benchmark
Price; hasta las aproximadas, como son las metodologías
instances from specialized literature.
heurísticas y metaheurísticas, entre las que se encuentran: las de
Key Word— genetic algorithm, heuristics, logistic, metaheuristics, agrupar primero y rutear después, ahorros, algoritmos
traveling salesman problem, vehicle routing problem. genéticos, búsqueda tabú, recocido simulado, entre otras.

Año Bibliografía Técnicas de Solución

Se consideran tres métodos de
I. INTRODUCCIÓN solución, siendo el último el de
mejores resultados: (1)
1969 [3] Aproximación de Ramificación y
Debido al gran interés científico en los problemas de ruteo de Acotamiento. (2) Aproximación de
vehículos, estos problemas han sido objeto de investigación los ahorros. (3) El método de los 3
intensiva por más de 50 años. Esto ocurre debido a que son tours óptimos.
NP-completos y porque algunas instancias de tamaño medio, no 1993 [4] Rutear primero y asignar después,
han podido ser resueltas de forma exacta [1]. Por otra parte,

Fecha de Recepción: 13 de enero de 2015

Fecha de Aceptación: 26 de septiembre de 2016
226 Scientia et Technica Año XXI, Vol. 21, No. 3, septiembre de 2016. Universidad Tecnológica de Pereira

utilizando un tour gigante generado optimización discreta de la partícula

por la técnica de Christofides. swarm, utilizada para la búsqueda
Relajación del CVRP a través del óptima de los vecindarios globales y
Ruteo de Vehículos Gráfico (GVRP) locales, y el recocido simulado con
1993 [5]
y además extendiendo los resultados ciertas probabilidades para evitar
poliédricos conocidos para el TSP. quedar atrapado en óptimos locales.
Se modela el VRP como un Algoritmo de búsqueda local para
problema para encontrar el costo el VRP, basado en la exploración
mínimo de un Árbol-K, con dos de vecindarios de orden
extremos K incidentes en un 2008 [13] exponencial resolviendo un
depósito, e imponiendo problema de programación lineal y
restricciones paralelas de la una heurística de refinamiento
capacidad del vehículo y que cada propuesta por Franceschi et al.
1994 [6]
cliente debe ser visitado una vez. Rutear primero y asignar después,
Estas restricciones paralelas son utilizando un tour gigante generado
dualizadas para obtener un por heurísticas de arranque y
problema Lagrangiano que provee 2009 [14] mejoradas a través de la búsqueda
los límites inferiores para ejecutar Tabú. Posteriormente la planificación
un algoritmo de Ramificación y de la flota de vehículos fue realizada
Acotamiento. mediante la técnica de scheduling.
Implementación del algoritmo Asignar primero y rutear después,
Branch-and-Cut, basado en la utilizando las heurísticas de Clark
descripción parcial poliédrica del and Wright y barrido para formar los
polígono correspondiente. Además, 2011 [15]
1998 [7] clusters, y posteriormente resolver
se centra en el diseño de cada TSP usando el algoritmo de
procedimientos de separación para cúmulo de partículas.
varias clases de desigualdades
válidas. Tabla 1: Revisión del estado del arte. [Fuente Propia]
Metodología de separación basada en
descomposición para las restricciones Por medio de la tabla 1, se plantea la necesidad de presentar una
de capacidad. Implementaciones a metodología de solución basada en la heurística constructiva de
2001 [8] barrido de dos fases; donde inicialmente se agrupen un conjunto
través de estructuras paralelas
Branch and Cut, and Price de clientes que serán satisfechos por un camión dado y luego se
SYMPHONY generen las rutas óptimas a través del Algoritmo Genético de
Chu-Beasley (AGCB) para cada vehículo Esto con el fin de
Heurística de rutear primero y
2002 [9] minimizar los costos de recorrido para todas las rutas mínimas
asignar después en grafos mixtos.
necesarias.
Discute las metaheurísticas que han
sido aplicadas para resolver el CVRP
en el tiempo: recocido simulado,
2002 [10]
recocido determinístico, búsqueda II. FORMULACIÓN MATEMÁTICA DEL PROBLEMA
tabú, algoritmos genéticos, colonias
de hormigas y redes neuronales.
Algoritmo genético híbrido, El desarrollo del CVRP, siendo el caso más general, depende
evolucionando dos poblaciones de en gran medida de la fundamentación y desarrollo de dos
2003 [11] soluciones para minimizar la problemas de optimización del tipo NP-Completo; el Bin
distancia total recorrida y utilizando Packing Problem (BPP) y el problema del agente viajero
diversos operadores genéticos. (TSP). Las principales formulaciones matemáticas utilizadas
Algoritmo genético híbrido sin para representar el VRP han sido propuestas en la literatura
delimitadores de rutas y según [16].
potencializado con operadores de
2004 [1]
búsqueda local, utilizando el El primero asociado específicamente con el CVRP determina
operador OX para la recombinación. el número mínimo de vehículos. Cada vehículo tiene
capacidad C, y son requeridos para satisfacer los n clientes,
2006 [12] Algoritmo híbrido entre el uso de la cada uno con una demanda no negativa. Esto está dado por la
Scientia et Technica Año XXI, Vol. 21, No. 3, septiembre de 2016. Universidad Tecnológica de Pereira 227

relación de la sumatoria total de las demandas ( ), sobre la Este modelo de programación lineal del tipo de formulación
capacidad de cada camión disponible (C). de flujo de vehículos de dos índices (two-index vehicle flow
formulation) utiliza , - variables binarias de para
indicar con un valor tomado de 1 si el arco (i, j) ϵ A pertenece
a la solución óptima y toma un valor de 0 en otro caso; es
El segundo caso es el de un agente viajero que debe realizar decir, toma su valor si el vehículo atraviesa o no un arco en la
un recorrido partiendo de una ciudad de origen, pasando por solución óptima. Para simplificar las notaciones, en las
cada una de las ciudades una sola vez, y regresando a la siguientes formulaciones se asume que el grafo
ciudad de origen. Todo esto minimizando los costos totales de . , / 0ó . , 2 3 es completo [16].
recorrido del viajero. Así, el modelo matemático asume la
siguiente forma [17]:
5 min
1 ∈# ∈#
,
Sujeto a: 9 :;< =:
2 1 ∀
: , 6 1 ∀ ∈ \ 0
3 1 ∀ ∈#
: , 7 1 ∀ ∈ \ 0
4 % 1; 2 & │(│ & │ │ ) 2 ∈#

, : !; #$! 8 C D,
∈#
Donde V es el conjunto de ciudades (vértices), A el conjunto 9 D,
C
de caminos (arcos) y U ᴄ+ V. El conjunto de restricciones (2)
∈#
indica que se puede llegar a una ciudad dada desde una sola
ciudad anterior y el conjunto (3) de restricciones indica que a 10 %F ∀ ̅ \ 0 , J ∅,
partir de una ciudad se puede pasar a una única ciudad. ∉G ∈G
El conjunto (4) de restricciones evita el surgimiento de 11 ∈ 0, 1 ∀ , ∈ .
subtours [17].
Donde:
Posterior a la conceptualización teórica y matemática de - C , M , . . . , N es el conjunto de vértices del
ambos problemas base para el desarrollo del CVRP, es posible gráfico, donde C corresponde al almacén.
presentar la principal formulación matemática usada para - C es la matriz de distancias o costos entre los
modelar dicho problema, llamado modelo de flujo de clientes y .
vehículos (Vehicle Flow Model). - K es el número de vehículos de capacidad C,
necesarios para cargar toda la demanda.
Los modelos de este tipo usan variables enteras, asociadas a - S es un subconjunto de vértices del grafo donde
cada arco o extremo del grafo, el cual cuenta el número de ̅ \ 0 .
veces que el arco o extremo es atravesado por un vehículo. - r(S) es el número mínimo de vehículos necesarios
Siendo este el modelo más usado para las formulaciones para servir a todos los clientes en S.
básicas del VRP, generalmente es utilizado para los casos en
los cuales el costo de una solución puede ser expresada como Las restricciones de grado de entrada y de salida (6) y (7),
la suma de los costos asociados a los arcos, y cuando las imponen que exactamente un arco entra y otro sale de cada
restricciones más relevantes conciernen la transición directa vértice asociado a un cliente, para satisfacer que todos los
entre los clientes y la ruta, por lo tanto, este puede ser clientes sean visitados una vez. Además, las restricciones (8)
modelado efectivamente a través de una definición apropiada y (9) imponen los requerimientos para el vértice depósito; es
del conjunto de arcos y sus costos. Por otra parte, existen decir, los mismos vehículos que salen del depósito, regresan
casos muy prácticos en los cuales estos modelos no deberían al depósito. Finalmente, la restricción de corte de capacidad
ser utilizados, como: cuando el costo de una solución depende (10) satisface tanto la conectividad de la solución y las no
de la secuencia total de los vértices, o del tipo de vehículo violaciones de la capacidad C de cada vehículo. Dicha
asignado a la ruta. restricción resta aún válida si el r(S) es reemplazado por el
valor solución trivial del BPP mencionado anteriormente.
228 Scientia et Technica Año XXI, Vol. 21, No. 3, septiembre de 2016. Universidad Tecnológica de Pereira

III. TÉCNICAS DE SOLUCIÓN rutear después, o los de rutear primero y asignar después.
[18], [19].

Entre las técnicas de solución aproximadas para el CVRP,

las más frecuentemente utilizadas son las heurísticas y 3. Heurísticas de mejora iterativa
metaheurísticas, con las cuales se pueden obtener buenas
soluciones en tiempos de cómputo razonables. Por otra Una vez que se tiene una solución para un problema VRP, se
parte, aun cuando la característica de este problema es NP- puede intentar mejorar mediante algún procedimiento de
completo, diversas técnicas exactas han sido exploradas búsqueda local. Para cada solución O se define un conjunto
satisfactoriamente a través del tiempo, logrando avances y de soluciones vecinas P O . Un procedimiento de búsqueda
mejoras en cuanto a tiempos de cómputo para obtener las local parte de una solución O la reemplaza por una solución
soluciones óptimas a los problemas tratados. A O Q P O de menor costo y repite el procedimiento hasta que
continuación, se relacionan diversas metodologías de la solución no pueda ser mejorada. Al terminar, se obtiene una
solución. solución localmente óptima respecto a la definición de la
A. Técnicas exactas (PLE) vecindad. [18], [21]. Entre ellas se encuentran: R –
intercambio, el operador or-opt, operadores string exchange y
Los algoritmos exactos son aquellos que siempre producen string relocation, GENI y GENIUS, transferencias cíclicas,
una solución óptima. Dichas técnicas no son adecuadas en intercambios r-opt, mecanismos unstringing y stringing (US)
aplicaciones que requieren soluciones rápidas o que tratan [2].
de resolver instancias de problemas muy grandes. Debido a
la naturaleza NP del problema VRP, la búsqueda exhaustiva C. Técnicas metaheurísticas
de estas técnicas no resulta eficiente computacionalmente
[18]. Entre las que se encuentran: Branch & Bound, Branch El énfasis en las técnicas metaheurísticas está en realizar una
& Cut, Branch & Cut & Price y la programación dinámica. exploración profunda de las regiones más prometedoras del
[6], [7], [19]. espacio solución. La calidad de las soluciones producidas por
estos métodos es mucho mejor que la obtenida por las
B. Técnicas heurísticas heurísticas clásicas, aunque su tiempo de cómputo es por lo
general mucho mayor. Existen dos tipos principales de
Las técnicas denominadas como heurísticas, realizan una familias de técnicas heurísticas avanzadas (metaheurísticas),
exploración relativamente limitada en el espacio de que son, las basadas en métodos de búsqueda local, y las que
búsqueda y comúnmente producen soluciones de buena explotan las poblaciones de soluciones
calidad dentro de tiempos de cómputo razonables. En un
macro-nivel, las heurísticas para el VRP están divididas I. Métodos de búsqueda local
entre 3 tipos.
Su principio de funcionamiento de base parte del hecho que
1. Heurísticas constructivas hay una solución inicial realizable y a esta se le aplican una
serie de modificaciones locales a la solución. Entre tanto,
Las ideas detrás de la mayor parte de este tipo de heurísticas dichas modificaciones mejoren el objetivo del problema en
se encuentran muy bien documentadas en [18], [19], [20]. estudio. Entre los principales métodos de búsqueda local se
Entre estas se encuentran frecuentemente el método del encuentran: búsqueda local simple, búsqueda local múltiple,
ahorro o Clark & Wright, el vecino más cercano (aleatorio o recocido simulado, Búsqueda de Vecindario Variable (VNS),
no), inserción menos costosa, inserción del más lejano, Búsqueda de Vecindario Variable Descendente (VND),
algoritmo goloso, entre otras. métodos de búsqueda con tabúes (simples y probabilísticos)
[22].
2. Heurísticas de dos fases
II. Métodos de exploración poblacional
Estas técnicas, parten de un problema y una solución “vacía”
para que a partir de ella se pueda construir una solución Entre los principales métodos basados en manejo de
factible, pero que casi nunca resulta óptima. Para la poblaciones se encuentran: algoritmos genéticos (variación
obtención de la solución, las heurísticas de dos fases dividen Chu-Beasley), algoritmos meméticos, optimización mediante
al problema de VRP en dos etapas: una de asignación de cúmulo de partículas (Swarm), optimización por colonia de
clientes a vehículos y otra para la determinación del orden hormigas [22].
de visita a dichos clientes. Existen luego dos grandes grupos
de solución, y a los cuales pertenecen diversos métodos
específicos; dichos grupos son los de agrupar primero y
Scientia et Technica Año XXI, Vol. 21, No. 3, septiembre de 2016. Universidad Tecnológica de Pereira 229

IV. PLANTEAMIENTO DEL PROBLEMA

B. Implementación de la fase 2

La metodología de solución implementada para el desarrollo n esta segunda, se optimiza la ruta de cada camión por cluster
del trabajo actual es la de dos fases, mencionada de forma separada. Esto se hace resolviendo un problema del
anteriormente. Es decir, está guiada inicialmente por la agente viajero TSP, implementando un AGCB [23] y
aplicación de la heurística de barrido o sweep [18], [19] potencializándolo con la calibración de parámetros para éste
generando los clusters de afectación por vehículo, y luego la tipo de códigos de manejos poblacionales propuesto por [1] y
solución a cada uno como un problema de agente viajero con algunas claves parciales aleatorias para algoritmos
(TSP) a través del AGCB. A continuación, se hace referencia genéticos “Biased Random-Key Genetic Algorithms”
a cada una de las fases y posterior análisis detallado de cada propuestas por [24].
una de ellas.
1. Codificación
Fase 1: Creación de los clusters de afectación para cada uno
de los vehículos, dependiendo de su capacidad y ubicación de Cada vector representa la solución óptima del recorrido del
los clientes respecto al depósito. vehículo para el cluster 1, … , y finalmente cada
Fase 2: Se da solución a cada cluster establecido en la etapa elemento “gen” del vector representará el orden secuencial en
anterior, implementando el AGCB adaptado a un problema de que serán visitados cada uno de los clientes de dicho
optimización del agente viajero simétrico. agrupamiento. El tamaño de cada solución depende del
número de clientes pertenecientes a cada grupo, limitado por
la demanda de los mismos y la capacidad del vehículo.
CLIENTE

RUTA = 2 10 8 3 6 12 17 SECUENCIA

ORDEN DE VISITA A CLIENTES

Figura 2. Esquema de codificación.

2. Población inicial

Un total de 30 individuos en la población inicial. 7 generados a

través de heurísticas constructivas (Clark & Wright, vecino más
cercano aleatorio y algoritmo goloso). Y los 13 restantes
generados de forma aleatoria.

3. Selección y recombinación
Figura 1. Implementación fase 1. [Fuente Propia].
En la figura 3 se esquematiza el proceso de selección para éste
A. Implementación de la fase 1 problema, donde la población es dividida en dos grupos, un
pequeño grupo de individuos élite TU , que son aquellos 7 que
En la figura 1, se puede observar de forma gráfica la tienen los mejores valores de función objetivo, y otro conjunto
metodología de agrupamiento de los clientes, que se hace por de individuos no-élite, siendo estos los faltantes de la relación
medio de sus ángulos respecto a una recta arbitraria y la suma entre T ) TU . Ahora bien, el elemento padre es seleccionado de
de sus demandas hasta que se llena el camión, evaluando de la partición de soluciones élite de la generación actual, y el otro
forma iterativa las posibilidades de incluir clientes posteriores de la partición no-élite, ambas selecciones de forma aleatoria.
al que viola la restricción de capacidad inmediatamente. Estos son los únicos dos elementos que compartirán material
Cuando un cliente de los posteriores evaluados es agregado genético en la siguiente etapa para dar paso a un nuevo
sin violar la restricción de capacidad, aquel que es ignorado, elemento en la generación k+1.
vuelve a quedar de primero en la lista y así se comienza
nuevamente el proceso de agrupamiento, hasta utilizar todos Posterior a la selección, se inicia otra etapa del proceso
los camiones. Durante el transcurso del procedimiento, se denominada recombinación, es aquí donde se genera el
generan diversos cambios de la recta arbitraria de arranque intercambio de material genético entre los dos padres
para explorar aún más el espacio de soluciones y generar seleccionados, el de la población élite y no-élite para este caso.
diferentes clusters en cada iteración par a mayor diversidad.
230 Scientia et Technica Año XXI, Vol. 21, No. 3, septiembre de 2016. Universidad Tecnológica de Pereira

Generación K Generación K+1

Selección
Aleatoria
Soluciones Élite Padre Élite Soluciones Élite
Recombinación
Padres

Soluciones No-Élite Soluciones No-Élite Figura 5. Proceso de mutación.

Selección
Aleatoria
Padre No-Élite
5. Modificación de la población

Para éste código, sólo se cambia un individuo de la población

Figura 3. Esquema de selección. Adaptado de [24]. en cada ciclo generacional. Además, no se permiten
infactibilidades en las soluciones. Finalmente, el descendiente
En esta metodología implementada, Recombinación debe sustituir al elemento de la población de peor calidad
Parametrizada Uniforme [25], se establece TU 0.7 como la siempre y cuando éste sea de mejor calidad que el peor de la
probabilidad que tiene un hijo de adquirir el material genético población actual y completamente diferente.
proveniente de las componentes del vector de su padre élite. Por
tanto, se genera un vector aleatorio, que indicará el gen nuevo C. RESULTADOS
del hijo que información tendrá y de qué padre. Es decir, si un
gen del vector aleatorio posee un valor inferior a TU , el hijo La codificación y ejecución del algoritmo propuesto se realizó
adquiere el material genético del padre 1 en la posición en el lenguaje de programación Matlab. Se cuantificó para 4
evaluada, ó del padre 2 en caso contrario. tipos de instancias de diferentes autores [3],[6],[26],[27] se
calcularon elementos de comparación como el GAP promedio y
En caso de haber repetición de los elementos que ya están el GAP mínimo -donde ambos son la diferencia porcentual con
incluidos en la solución en curso, se dejan dichos genes vacíos, el promedio de las 10 corridas calculadas a través de la
y al final se completan de forma trivial con el cliente no visitado metodología propuesta- y el otro respecto al mejor valor
más cercano al cliente inmediatamente anterior. En la figura encontrado en las 10 corridas en cuanto a la evaluación de la
4,se presenta un ejemplo sencillo de dicho procedimiento. función objetivo de las soluciones finales.

Las codificaciones de las instancias se presentan de la siguiente

manera; X-NYY-KZ. Donde, X es igual a una inicial que indica
el autor de la instancia. YY es el número de nodos del sistema;
es decir, el número de clientes + 1. Finalmente, Z es el número
de vehículos a utilizar. Salvo para las instancias de
Christofides, Mingozzi y Toth (CMT) [26] cuya codificación es
independiente a las características del problema.
El valor BKS.FO indica el valor de la función objetivo de la
mejor solución encontrada hasta el momento. En tanto que las
instancias que presenten un * en la casilla OPT (*), esto indica
Figura 4. Proceso de recombinación. que ese BKS es el óptimo global de la instancia encontrado a
través de alguna técnica exacta de solución.
4. Mutación
Según las tablas 2–5, se reporta la ventaja que tiene la
En cada iteración, se realiza después de la recombinación un metodología propuesta para dar solución aproximada a las
proceso de mutación simple a un elemento aleatorio de toda la instancias seleccionadas de Christofides y Eilon. Estas
población de la solución en curso. Esta mutación es un instancias tienen GAPs para las instancias pequeñas entre 4% -
intercambio de posición o swap de dos elementos aleatorios de 10%, y para las grandes entre 5% - 12% ambas en el mejor de
un cromosoma. Esto utilizado como un mecanismo de los casos. Además, se obtuvieron buenos resultados al trabajar
perturbación, con el fin de explorar mejor el espacio de con las instancias de CMT, vrpnc 1 y vrpnc 4, ambas con un
soluciones y escapar de óptimos locales. GAP menor al 10%.
Scientia et Technica Año XXI, Vol. 21, No. 3, septiembre de 2016. Universidad Tecnológica de Pereira 231

# GAP.
OPT BKS. Tipo GAP.
Por otra parte, para el benckmark realizado a los casos de Nombre
(*) FO
Itera-
Medida
Promedio Min
Min
Pro-
ciones medio
prueba propuestos por Augerat et al., se observa la necesidad de F-N45-
realizar movimientos inter-rutas e intra-rutas para poder escapar K4 * 724 3000 F.O 900.65 889.94 23% 24%
de óptimos locales y poder explorar aún más el espacio de F-N45-
K4 * 724 3000 Tiempo 55.58 54.01
soluciones. Para instancias de tamaños similares, se tienen F-N72-
GAPs muy distantes, como es el caso de las instancias A-N48- K4 * 237 5000 F.O 325.51 315.35 33% 37%
F-N72-
K7 (4% GAP) y B-N44-K7 (18% GAP). K4 * 237 5000 Tiempo 120.77 119.75
F-N135-
Caso similar ocurre con las tres instancias propuestas por K7 * 1162 5000 F.O 1489.44 1454.94 25% 28%
F-N135-
Fisher, donde para los tres casos, la diferencia promedio con las K7 * 1162 5000 Tiempo 3530.37 350.25
BKS está por encima del 20%.

OPT BKS.
#
Tipo GAP.
GAP. Tabla 5. Resultados de Christofides y Eilon[3]
Nombre Itera- Promedio Min Pro-
(*) FO Medida Min
ciones medio #
A-N48- OP Itera- Tipo
K7 * 1073 1500 F.O 1119.07 1119.07 4% 4% Nombr T BKS cione Medid Promedi GAP. GAP.Pro
A-N48- e (*) . FO s a o Min Min - medio
K7 * 1073 1500 Tiempo 42.42 42.21 E-
A-N46- N101- 1203.0 12.00
K7 * 914 1500 F.O 999.01 999.74 9% 9% K14 * 1071 3000 F.O 1204.34 1 % 12.00%
A-N46- E-
K7 * 914 1500 Tiempo 48.44 48.23 N101-
B-N44- K14 * 1071 3000 Tiempo 311.46 303.45
K7 * 909 1500 F.O 1074.93 1074.30 18% 18% E-
B-N44- N101-
K7 * 909 1500 Tiempo 34.12 33.96 K8 * 815 3000 F.O 888.56 880.56 8.00% 9.00%
A-N62- E-
K8 * 1288 2000 F.O 1536.83 1536.70 19% 19% N101-
A-N62- K8 * 815 3000 Tiempo 205.43 203.06
K8 * 1288 2000 Tiempo 69.34 68.97 E-N76-
B-N57- K10 * 830 2000 F.O 871.06 870.15 5.00% 5.00%
K9 * 1598 2000 F.O 1764.20 1764.20 10% 10% E-N76-
B-N57- K10 * 830 2000 Tiempo 112.65 109.40
K9 * 1598 2000 Tiempo 71.60 64.20 E-N51-
A-N80- K5 * 521 2000 F.O 571.41 566.36 9.00% 10.00%
K10 * 1763 3000 F.O 2106.54 2105.80 19% 19% E-N51-
A-N80- K5 * 521 2000 Tiempo 56.78 55.17
K10 * 1763 3000 Tiempo 165.56 161.24 E-N33-
B-N78- K4 * 835 2000 F.O 875.59 872.16 4.00% 5.00%
K10 * 1221 3000 F.O 1331.52 1327.50 9% 9% E-N33-
B-N78- K4 * 835 2000 Tiempo 28.14 25.43
K10 * 1221 3000 Tiempo 161.96 161.12 E-N23- 10.00
K3 * 569 3000 F.O 647.55 623.70 % 14.00%
E-N23-
Tabla 2. Casos de prueba Augerat et al.[27] K3 * 569 3000 Tiempo 18.80 15.75

# GAP.
Nombre
OPT BKS.
Itera-
Tipo
Promedio Min
GAP.
Pro- III. CONCLUSIONES
(*) FO Medida Min
ciones medio

vrpc1 * 524.61 2000 F.O 571.64 569.08 8% 9%

vrpc1 * 524.61 2000 Tiempo 55.41 55.11

◦ Se desarrolló una metodología de solución de dos fases
para el CVRP. Basada en la implementación de la
vrpc4 1028.4 3000 F.O 1136.28 1120.27 9% 10% heurística constructiva de barrido para la generación de los
vrpc4 1028.4 3000 Tiempo 349.52 346.48 clusters, y el AGCB para dar solución a la ruta óptima de
vrpc11 1042.1 3000 F.O 1295.57 1285.12 23% 24% cada camión dentro del mismo.
vrpc11 1042.1 3000 Tiempo 180.67 179.78
◦ El AGCB potencializado desarrollado en el trabajo actual
vrpc12 819.56 3000 F.O 1014.23 1011.52 23% 24%
presenta resultados satisfactorios en tiempos de cómputo
vrpc12 819.56 3000 Tiempo 174.13 173.61 razonables para algunas instancias trabajadas.

Tabla 3. Resultados casos de prueba de Fisher [6] ◦ Se evidenció que no solamente el tamaño de las instancias
y la cantidad de vehículos, son las que determinan la
Tabla 4. Resultados casos de prueba CMT [26]
232 Scientia et Technica Año XXI, Vol. 21, No. 3, septiembre de 2016. Universidad Tecnológica de Pereira

complejidad del problema, sino la topología misma de la [7]. Augerat, P., Belenguer, J.M., Benavent, E.,
red. Corberan, A., Naddef, D., Rinaldi, G., 1998.
Computational Results with a Branch and Cut Code
◦ Las utilizaciones de heurísticas constructivas para generar for the Capacitated Vehicle Routing Problem.
soluciones básicas factibles de inicio se muestran como Research Report 949-M, Université Joseph Fourier,
una ventaja tanto computacional como en resultados, ya Grenoble, France
que se garantiza tener individuos de buena calidad desde
el inicio del algoritmo. [8]. T. K. Ralphs, L. Kopman, W. R. Pulleyblank, Jr. L.
E. Trotter. “On the Capacitated Vehicle Routing
RECOMENDACIONES Problem”. Mathematical Programming Series. B 94,
343. 2001.
◦ Incluir estrategias de búsqueda local y de vecindario, para
realizar movimientos intra-ruta e inter-ruta. Debido a que
la propuesta actual no permite intercambio de información [9]. J. C. Angel, D. Soler, A. Hervas. “The capacitated
entre los clusters, este aspecto origina respuestas atrapadas general routing problem on mixed graphs”. Revista
en óptimos locales. investigación operacional, volume 23, No. 1. 2002.

◦ Implementar la generación de clusters aleatorios para [10]. M. Gendreau, G. Laporte, J-Y. Potvin.
explorar aún mejor el espacio de soluciones del problema. “Metaheuristics for the capacitated VRP”. The
vehicle routing problem, volume 9 of SIAM
◦ Desarrollar la metodología de solución en el lenguaje de monographs on discrete mathematics and
programación C++. Esto con el fin de lograr mayor applications, chapter 6. 2002.
eficiencia en los tiempos de ejecución.
[11]. J. Berger, M. Barkaoui. “A hybrid genetic
algorithm for the capacitated vehicle routing
REFERENCIAS problem”. Genetic and evolutionary computation –
GECCO, volume 1, pages 646-656. 2003.
[1]. C. Prins. “A simple and effective evolutionary
algorithm for the vehicle routing problem”. [12]. A-L. Chen, G-K. Yang, Z-M. Wu. “Hybrid
Computers & Operations Research, volume 31, issue discrete particle swarm optimization algorithm for
12, pages 1985-2002. 2004. capacitated vehicle routing problem”. Journal of
Zhejiang University SCIENCE A, volume 7, issue 4,
[2]. M. Gendreau, T. Vidal, T. G. Crainic, C. Prins. pages 607-614. 2006.
“Heuristics for multi-attribute vehicle routing
problems: A survey and synthesis”. CIRRELT. 2012. [13]. P. Toth, A. Tramontani. “An integer linear
programming local search for capacitated vehicle
[3]. N. Christofides, S. Eilon. “An Algorithm for the routing problems”. The vehicle routing problem:
Vehicle Dispatching Problem”. Operational Latest advances and new challenges, volume 2,
Research Quarterly. Volume 20, pages 309-318. pages 275-295. 2008.
1969.
[14]. J. M. Daza, J. R. Montoya, F. Narducci.
[4]. J. Klaus. “Bounds for the general capacitated routing “Resolución del problema de enrutamiento de
problem”. Networks, volume 23, issue 3, pages 165- vehículos con limitaciones de capacidad utilizando
173. 1993. un procedimiento metaheurístico de dos fases”.
Revista EIA, No. 12, páginas 23-38. 2009.
[5]. G. Cornuejols, F. Harche. “Polyhedral study of the
capacitated vehicle routing problem”. Mathematical [15]. S. R. Venkatesan, D. Logendran, D.
Programming, volume 60, issue 1-3, pages 21-52. Chandramohan. “Optimization of capacitated vehicle
1993. routing problem using PSO”. International Journal
of Engineering Science and Technology, volume 3,
[6]. M. Fisher. “Optimal Solution of Vehicle Routing number 10, pages 7469-7477. 2011.
Problems Using Minimum k-Trees”. Operations
Research. Volume 42, no. 4, pages 626-642. 1994. [16]. P. Toth, D. Vigo. “An Overview of Vehicle
Routing Problems, Monographs on Discrete
Scientia et Technica Año XXI, Vol. 21, No. 3, septiembre de 2016. Universidad Tecnológica de Pereira 233

Mathematics and Applications”. In: The Vehicle

Routing Problem. SIAM, 2000, pp. 1-26. 2000.

[17]. R. Gallego, A. Escobar, E. Toro. “Técnicas

metaheurísticas de optimización”. Universidad
Tecnológica de Pereira. Textos Universitarios,
ISBN: 978-958-722-007-0, Ed. 2. 2008.

[18]. J. Corona. “Hiperheurísticas a través de

programación genética para la resolución de
problemas de ruteo de vehículos”. Tesis MSc.
Ciencias en sistemas inteligentes, Instituto
Tecnológico y de Estudios Superiores de Monterrey,
Monterrey, México. 2005.

[19]. B. E. Gillet, L. R. Miller. “A Heuristic

Algorithm for the Vehicle Dispatch Problem”.
Operations Research. Volume 22, pages 340-349.
1974.

[20]. A. Martel. “Le pilotage des flux”.

CENTOR, Université Laval. DF-3.4.1. 2003.

[21]. M. Gendreau, A. Langevin, J. M. Frayret.

“Notes du cours” « Réseaux Logistiques », séance
6 : Planification du transport par camions. École
Polytechnique de Montréal. 2013.

[22]. A. Duarte. “Metaheurísticas”. Librería-

Editorial Dykinson. Volumen 22 de Ciencias
Experimentales y Tecnología. 2007.

[23]. P. C. Chu, J. E Beasley. “A Genetic

Algorithm for the Generalized Assignment Problem”.
Computers & Operations Research. Volume 24,
issue 1, pages 17-23. 1997.

[24]. M. Resende. “BiasedRandom-Key Genetic

Algorithms With Applications In
Telecommunications”. AT&T Labs Research
Technical Report. Pages 1-6. 2011.

[25]. W. M. Spears, K. A. De Jong. “On The

Virtues of Parameterized Uniform Crossover”.
Proceedings of the Fourth International Conference
on Genetic Algorithms, eds. R. Belew and L. Booker,
San Mateo, CA: Morgan Kaufmann, 230-236. 1991.

[26]. N. Christofides, A. Mingozzi, P. Toth. “The

Vehicle Routing Problem”. In: Combinatorial
Optimization (N. Christofides, A. Mingozzi,
P. Toth and C. Sandi, editors). Chichester: John
Wiley & Sons Ltd. Pages 315-338. 1979.