modelos de programación entera para el ruteo de vehículos
TRANSCRIPT
Modelos de Programación Entera Para el Ruteo de Vehículos:
Implementación y Análisis Computacional
Trabajo de Tesis
Presentado al
Departamento de Ingeniería Industrial
Por
Diego Alejandro Ortiz Niño
Asesor: Andrés Medaglia, Ph.D.
Para optar al título de
Ingeniero Industrial
Ingeniería Industrial
Universidad de los Andes
Enero 2005
Modelos de Programación Entera Para el Ruteo de Vehículos:
Implementación y Análisis Computacional
Aprobado por:
____________________-
_______________
Andrés Medaglia, Ph.D., Asesor
Fecha de
Aprobación:______________
III
DEDICATORIA
A mis padres por todo su apoyo y
compresión durante todos estos años.
A mis hermanos por todos estos años
que hemos compartido y todo
lo que me han enseñado.
A mis maestros especialmente a mi
profesor y asesor Andrés Medaglia
y al profesor Eliécer Gutiérrez cuyo
valioso apoyo hizo posible
la realización de este proyecto.
IV
TABLA DE CONTENIDO
DEDICATORIA ______________________________________________________III
TABLA DE CONTENIDO______________________________________________ IV
I. INTRODUCCIÓN____________________________________________________ 1
II. MODELOS DE CVRP________________________________________________ 3
2.1. Descripción del Problema (CVRP) ________________________________________________3 2.2. Modelos_____________________________________________________________________4
III. MÉTODO DE SOLUCIÓN POR BRANCH AND BOUND ________________ 11 3.1. Breve Descripción del Método __________________________________________________11 3.2. Branch and Bound en Xpress ___________________________________________________14
IV. DISEÑO DEL EXPERIMENTO COMPUTACIONAL ____________________ 18
4.1. Instancias de Prueba __________________________________________________________18 4.2. Implementación de los Algoritmos_______________________________________________19 4.3. Realización de las Pruebas______________________________________________________20 4.4. Formato de los Resultados Obtenidos_____________________________________________21
V. ANALISIS DE LOS RESULTADOS EXPERIMENTALES _________________ 24 5.1. Comparación entre los Algoritmos VRP1 y VRP4___________________________________27 5.2. Presolver Global _____________________________________________________________29 5.3. Estrategia de Selección de Nodos ________________________________________________31 5.4. Presolver Entero______________________________________________________________36 5.5. Fijación de una cota máxima para la función objetivo ________________________________38
VI. CONCLUSIONES__________________________________________________ 41
VII. INVESTIGACIÓN FUTURA________________________________________ 43
V
Apéndice A. CÓDIGO UTILIZADO ______________________________________ 45
Código VRP4 ___________________________________________________________________45 Código VRP1 ___________________________________________________________________48
Apéndice B. EJEMPLO DE UN ARCHIVO DE SOLUCIÓN__________________ 53
Apendice C. FUNCIONES DE DISTRIBUCIÓN DE PROBABILIDAD_________ 55
REFERENCIAS ______________________________________________________ 69
II.04(02).83
1
Capitulo I
INTRODUCCIÓN
El propósito de este proyecto de grado es obtener un mejor
entendimiento del comportamiento de algoritmos de programación
matemática basados en la técnica de Branch and Bound para la
solución de problemas de programación entera, específicamente
para la solución del problema de ruteo de vehículos con
capacidad definida (CVRP). Esto con el fin de aportar a la
investigación del profesor Andrés Medaglia, quien ha trabajado
en la solución eficiente del problema de ruteo de vehículos
atacándolo desde diversos frentes tales como métodos heurísticos
y meta heurísticos.
Para tal fin se uso el programa Xpress-MP y su lenguaje
algebraico para programar los algoritmos y llevar acabo el
problema planteado del cual se extrajeron los resultados que se
utilizaron posteriormente en el análisis y en la elaboración de
las conclusiones.
En este experimento computacional se tuvieron en cuenta varios
factores además del algoritmo, dentro de estos factores se
incluye el método de selección de nodo y características propias
del programa Xpress tales como el uso de algoritmos anteriores a
la optimización para simplificar el problema (presolvers) de
II.04(02).83
2
manera global y antes de solucionar cada nodo (presolvers
enteros).
El problema de ruteo de vehículos tiene su origen hace 40 años
cuando Dantzig y Ramser [7] publicaron el primer artículo sobre
el problema de ruteo de vehículos, después de esto se han hecho
numerosas investigaciones y publicado varios artículos en los
cuales se exponen diversos modelos analíticos o heurísticos, con
los cuales se busca dar solución a este problema. Existen
artículos comparativos como [5] en el cual se muestran los
resultados de un estudio comparativo entre algoritmos
heurísticos, el cual representa una base sobre la cual elaborar
un estudio comparativo de los algoritmos matemáticos.
Este trabajo presenta la siguiente estructura, en el capitulo
dos se introducen los modelos de CVRP, haciendo énfasis en los
utilizados en es trabajo. El capitulo tres presenta una
introducción al método Branch and Bound, prestando especial
atención al uso de esta técnica cuando se utiliza el programa
Xpress-MP. El capitulo cuatro muestra la metodología seguida en
cada una de las etapas del proyecto, explicando lo que se hizo y
la razón de las decisiones tomadas. En el capitulo cinco se
presenta un resumen de los resultados obtenidos, acompañados de
su análisis. Finalmente en los capítulos seis y siete se
presentan las conclusiones y recomendaciones para una
investigación futura.
II.04(02).83
3
Capitulo II
MODELOS DE CVRP
Descripción del Problema (CVRP)
El problema de ruteo de vehículos consiste en una red con nodos
de demanda y nodos de depósito, por esta red circula una flota
de vehículos los cuales se encargan de llevar los bienes de los
depósitos a los clientes empleando diversas rutas.
El problema de ruteo de vehículos con restricciones de capacidad
es un caso especial en el cual las demandas son determinísticas
e indivisibles, además, los vehículos son todos similares y se
ubican en un depósito central único. En este tipo de problema
solo existen restricciones respecto a las capacidades de carga
de los vehículos.
El objetivo del problema es minimizar el costo total de servir a
todos los clientes, empleando una función que permita optimizar
los tiempos de ruta o las distancias recorridas.
El problema puede ser descrito como un problema de grafos de la
siguiente manera:
II.04(02).83
4
G = ( N , A )
En donde N = {(0, … , n)} y A es el conjunto de arcos.
Generalmente los nodos 1, ... , n son asignados a los clientes
el nodo 0 corresponde al depósito. Cada arco tiene un costo, el
cual solo toma valores positivos y esta denotado por cij para
cada arco ( i, j ). Cada cliente posee una demanda dada por di.
Existe un grupo de K vehículos idénticos, cada uno de los cuales
posee una capacidad C. Se asume que C > di para todo i. Cada
vehículo puede recorrer como máximo una ruta.
La solución para este problema consiste en encontrar K rutas,
las cuales son circuitos simples, con el mínimo costo posible,
el cual está dado por la suma de costos de los arcos
pertenecientes a los circuitos. Las restricciones bajo las
cuales esta sujeto la solución son:
- Cada circuito visita el nodo correspondiente al depósito.
- Cada cliente es visitado únicamente por un circuito.
- La suma de las demandas de los nodos de un circuito no
supera la demanda del vehículo.
Modelos
En la literatura se han propuesto tres aproximaciones básicas al
modelaje de problemas de ruteo de vehículos [1]. La aproximación
mas utilizada es el modelo por flujo de vehículos, esta se
adapta especialmente bien cuando el costo total se puede
expresar como la suma de los costos asociados a los arcos.
Dentro de sus principales problemas se encuentra la incapacidad
de ser utilizado para similar problemas mas complejos como
II.04(02).83
5
aquellos con ventanas de tiempo u otras restricciones. La
segunda aproximación utilizada es la de modelar por flujo de
mercancías, este modelo solo ha sido usado recientemente para
obtener soluciones exactas en el problema de ruteo de vehículos.
La última aproximación utilizada es la de modelos de partición
en grupos, la cual posee un número exponencial de variables
binarias, cada una de las cuales está asociada a un circuito
factible. Esta forma de planteamiento permite adicionar nuevas
restricciones al problema lo cual representa su mayor ventaja.
En este tipo de modelo se utilizan variables binarias Xij, la
cual toma un valor de 1 si el arco (i,j) pertenece al conjunto
de arcos de la solución óptima y 0 en caso contrario.
El modelo matemático básico para la formulación de problemas de
ruteo de vehículos utilizando el método de flujo de vehículos es
el siguiente:
Modelo 1
(VRP1) [1]
∑∑∈ ∈Vi Vj
jiij xcmin
Sujeto a:
(1) ∑∈
=Vi
ijx 1 { }0\Vj∈∀
(2) ∑∈
=Vj
ijx 1 { }0\Vi∈∀
(3) ∑∈
=Vi
i Kx 0
II.04(02).83
6
(4) ∑∈
=Vj
j Kx0
(5) ∑∑∉ ∈
≥Si
ijSj
Srx )( { } 0,0\ ≠⊆∀ SVS
(6) { }1,0∈ijX Vji ∈∀ ,
K = Número de Vehículos
V = Conjunto de vértices que componen el grafo del problema
S = Subconjunto de V
r(S) = Número mínimo de vehículos requeridos para satisfacer a todos los
clientes en S
Las condiciones (1) y (2) son las condiciones de grado de los
nodos y establecen que para cada nodo entre y salga únicamente
un arco si el nodo es diferente de 0. Las condiciones (3) y (4)
establecen que el numero de arcos que salen y que llegan al nodo
0 (depósito) es igual al número de vehículos disponibles (K). La
condición (5) la cual es llamada condición de capacidad-corte
(CCCs por sus siglas en ingles capacity-cut constrains)
establece la conectividad de la solución y los requisitos de
capacidad de los vehículos, el valor de r(S) se puede reemplazar
por la cota trivial del problema, la cual es la suma de las
demandas del subgrupo S dividida entre la capacidad de los
vehículos C. La condición (6) estable que la variable Xij es una
variable binaria.
La ecuación (5) se puede formular de una manera alternativa,
aplicándole una transformación basada en las ecuaciones (1)-(4):
(7) ∑∑∈ ∈
−≤Si Sj
ji SrSx )( { } 0,0\ ≠⊆∀ SVS
Esta condición establece que por lo menos r(S) arcos abandonan
el subgrupo de clientes S, con lo cual se asegura que se cumplan
II.04(02).83
7
los requisitos de capacidad de los vehículos y de conectividad
de la solución.
El principal problema para la solución de este modelo, tanto
usando la ecuación (5) como usando la ecuación (7) consiste en
que la cardinalidad de estas restricciones crece de manera
exponencial con n, por lo que es prácticamente imposible
resolver directamente una relajación lineal del problema para un
número no trivial de nodos. Por ejemplo, para un problema con 20
nodos el número de restricciones relacionadas con la ecuación 5
sería equivalente a ∑=
⎟⎟⎠
⎞⎜⎜⎝
⎛20
1
20
i i lo cual es igual a 1.048.575
restricciones. Una manera que se ha desarrollado para
sobrellevar esta dificultad consiste en tener en cuenta solo
algunas de las restricciones e ir añadiendo las demás a medida
que se van necesitando, sin embargo este tipo de relajación es
generalmente no factible.
De manera alternativa se puede reemplazar las restricciones (5)
o (7) por una familia de restricciones equivalentes con
cardinalidad polinomial, las cuales son conocidas como
condiciones de Millar, Tucker y Zemlin [1].
(8) jijji dCCxuu −≤+− { } CddjiVji ji ≤+≠∈∀ ,0\,
(9) Cud ii ≤≤ { }0\Vi∈∀
En estas restricciones el termino ui hace referencia a la carga
que lleva acumulada el vehículo cuando al llegar al nodo i, cada
uno de estos términos esta relacionado únicamente con un
vehículo, ya que en esta formulación no es posible que dos
vehículos distintos visiten el mismo nodo al no ser que este sea
el deposito.
II.04(02).83
8
La desventaja de utilizar estas ecuaciones radica en que la
relajación lineal del problema, cuando se utilizan, es mucho más
débil que la relajación cuando se utilizan las ecuaciones (5) o
(7). El modelo 1, utilizando las condiciones de Millar, Tucker
and Zemlin, es el que en este proyecto se va a llamar VRP1 MTZ.
Los modelos anteriores son versiones para problemas asimétricos,
sin embargo, se pueden adaptar para problemas simétricos y son
de gran importancia ya que son varios los problemas en donde el
costo de transitar el arco (i,j) es similar al costo de
transitarlos en el sentido contrario (j,i), tal y como sucede en
todos los casos en donde el costo esta relacionado con la
distancia euclidiana entre los nodos. Se menciona este caso en
particular ya que las instancias de prueba utilizadas en este
proyecto presentan como costo de los arcos la distancia
euclidiana entre los nodos que une (Augerat [6]).
La versión simétrica del modelo de flujo de vehículos es la
siguiente:
Modelo 2
(VRP2) [1]
{ }∑ ∑∈ >nVi ij
ijij xc\
min
Sujeto a:
(10) ∑ ∑< >
=+ih ij
ijhi xx 2 { }0\Vi∈∀
(11) { }
∑∈
=0\
0 2Vj
j Kx
(12) ∑∑ ∑∑∈
∉< ∈
∉>
≥+Si
Shih Si
Sjij
ijhi Srxx )(2 { } 0,0\ ≠⊆∀ SVS
(13) { }1,0∈ijx { } jiVji <∈∀ ,0\,
II.04(02).83
9
(14) { }2,1,00 ∈jx { }0\Vj∈∀
Los modelos presentados anteriormente han sido usados de manera
extensiva para modelar las versiones básicas de CVRP, sin
embargo es inadecuado para versiones mas complejas. Por ejemplo,
no es posible saber de manera directa que vehículo en particular
atraviesa un arco de la solución óptima, por lo que estos
modelos no se pueden utilizar para problemas en los cuales el
costo depende del vehículo asignado a la ruta. Una manera de
solucionar esto es por medio de un tercer índice, el cual indica
de manera explicita qué vehículo atraviesa una ruta en
particular. En este modelo la variable xijk indica el numero de
veces que el vehículo k atraviesa el arco (i,j). Por esto la
complejidad del problema se aumenta hasta n2k variables binarias,
también se utiliza una variable yik la cual indica si el cliente
i fue visitado por le vehículo k, por lo cual existen otras nk
variables binarias. El modelo es el siguiente:
Modelo 3
(VRP4)[1]
∑∑ ∑∈ ∈ =Vi Vj
K
kijkji xc
1min
Sujeto a:
(15) ∑=
=K
kiky
11 { }0\Vi∈∀
(16) ∑=
=K
kk Ky
10
(17) ∑ ∑∈ ∈
==Vj Vj
ikjikijk yxx KkVi ,...,1, =∈∀
(18) ∑∈
≤Vi
iki Cyd Kk ,...,1=∀
II.04(02).83
10
(19) ∑∑∈ ∉
≥Si Sj
hkijk yx { } KkShVS ,...,1,,0\ =∈⊆∀
(20) { }1,0∈iky KkVi ,....,1, =∈∀
(21) { }1,0∈ijkx KkVji ,....,1,, =∈∀
Con este modelo también se puede utilizar una versión de las
condiciones de Millar, Tucker y Zemlin, con las cuales se
reemplazarían las restricciones (18) y (19). Estas restricciones
son las siguientes:
(20) jijkjkik dCCxuu −≤+− { }
Kk
CddjiVji ji
,...,1
,,0\,
=
≤+≠∈∀
(21) Cud iki ≤≤ { } KkVi ,...,1,0\ =∈∀
El modelo 3 con las condiciones de Millar, Tucker y Zemlin es el
que se va a llamar VRP4 MTZ en este documento, este junto con el
modelo VRP1 MTZ fueron los dos modelos implementados y
utilizados.
II.04(02).83
11
Capitulo III
MÉTODO DE SOLUCIÓN POR BRANCH AND BOUND
Breve Descripción del Método
El método de Branch and Bound (ramificación y acotamiento) es el
método mas común en los paquetes de software para la solución de
problemas de programación lineal enteros. Debido a esto es
importante entender la manera en la que trabaja este método con
el fin de adquirir un conocimiento sobre los alcances y las
implicaciones de su uso.
El método comienza hallando la solución a la relajación lineal
del problema entero, una vez obtenida esta se pueden presentar
tres casos:
- En la solución óptima encontrada las variables que
requieren ser enteras lo son, por lo que la solución
encontrada para la relajación lineal es también la solución
del problema entero.
- En la solución óptima alguna o varias de las variables que
deben ser enteras no lo son, por lo que el problema se
divide en dos nuevos problemas. Se toma alguna de las
variables que no cumplió con la restricción de ser entera
II.04(02).83
12
en la solución hallada, el valor numérico tomado por esta
variable se debe encontrar entre dos números enteros N1 y N2
(N1 < Xi < N2) por lo que uno de los dos nuevos problemas
incluye la restricción Xi < N1 y el otro la nueva
restricción Xi > N2. Este procedimiento de subdividir el
problema se conoce como ramificación (branching).
- También es posible que se encuentre el caso de que no sea
factible.
Con cada una de las ramas que van apareciendo se sigue haciendo
el mismo procedimiento, cuando se obtenga la primera solución
que cumpla las restricciones de que las variables sean enteras
se empieza a considerar el valor de la solución obtenida como
una cota (bound) inferior o superior (en el caso que se este
maximizando o minimizando), la cual se va reemplazando a medida
que se encuentren óptimos que cumplan las restricciones y sean
superiores o inferiores según sea el caso. Los criterios según
los cuales una rama llega a su fin son los siguientes:
- Se encontró una solución en donde todas las variables que
así lo requieren satisfacen la condición de ser enteras. En
este caso no vale la pena seguir subdividiendo el problema
ya que dentro de esa zona factible no se va a encontrar una
solución que supere el óptimo que ha sido obtenido ya que
al subdividir los problemas generados poseen más
restricciones que el original.
- Se encontró que no hay solución factible para el problema
planteado en esa rama.
- Se obtuvo una solución cuyo óptimo no es mejor que la cota
obtenida anteriormente, así se cumplan las restricciones de
tener variables enteras.
Los nodos que pertenecen a ramas que no han sido terminadas se
conocen como nodos activos (active nodes). Todos los nodos
II.04(02).83
13
poseen un atributo conocido como profundidad (Depth) el cual
representa el número de ramificaciones que separan el nodo madre
de ese nodo en particular.
Así como el método va definiendo cotas superiores utilizando las
soluciones enteras que se van encontrando, se utilizan las
soluciones de las relajaciones lineales para establecer cotas
mínimas (bounds), esto basado en el hecho que la solución a la
relajación lineal siempre va a ser menor o igual a la solución
del problema entero, por lo que se puede establecer que el valor
de la relajación lineal es el valor mínimo que va a tomar
cualquier solución entera que este dentro de cualquier rama de
ese nodo. La diferencia en porcentaje entre la mejor solución y
la cota inferior se conoce como gap (brecha), y se calcula de la
siguiente manera:
MayorBoundMayorBoundiónMejorSolucGAP −=
El método encuentra la solución óptima cuando el gap es igual a
cero, esto equivale a decir que la mejor solución actual es
igual a la cota inferior, por lo que esta solución va a ser
mejor a o igual que cual otra solución que se encuentre en los
nodos activos restantes.
Según [3] en el método de Branch and Bound para llegar a mejores
resultados generalmente se trabaja con un sistema LIFO (Last In
First Out), el cual significa que se trabaja con la ultima rama
encontrada hasta llegar a su fin, una vez se encuentra este, se
continua con la ultima rama hallada que no haya sido resuelta.
Este tipo de búsqueda también se conoce como de profundidad
(depth) ya que se va avanzando a través de los hijos logrando
separarse así cada vez más del nodo madre. Esto sirve para
encontrar rápidamente una solución que sirva como cota, lo cual
II.04(02).83
14
es útil ya que basados en esta se pueden descartar varias ramas
por no tener mejores óptimos que la solución ya encontrada.
Existe un caso especial de problema lineal entero en donde no es
necesario utilizar las restricciones de variables enteras ya que
se puede asegurar que la solución a la relajación lineal es una
solución entera. Esto sucede cuando la matriz de restricciones A
tiene un determinante igual a 1, 0 o -1 y el vector b esta
compuesto de valores enteros. Cuando se presentan estas
características especiales se dice que es completamente
unimodular.
El tiempo de cómputo requerido para resolver un problema entero
es considerablemente mayor al de resolver un problema continuo,
ya que como se vio anteriormente, para resolver el problema
entero es necesario resolver varios problemas continuos. Por
esta razón muchas veces se prefiere sacrificar la optimalidad
con tal de obtener una solución dentro de un rango aceptable, en
un tiempo de cómputo menor.
Branch and Bound en Xpress
Este proyecto de grado se desarrolló utilizando el programa
Xpress-MP de la compañía Dash Optimization, de este programa se
usaron tres partes fundamentales, la primera de ellas una
interfase gráfica la cual se conoce bajo el nombre de IVE
(Interactive Visual Environment); IVE es un programa ejecutable
que sirve como la entrada más intuitiva al programa. Esta
interfase gráfica sirve como vínculo entre el usuario y el
lenguaje de programación que se conoce como Mosel, el cual esta
especialmente diseñado para la solución de problemas de
optimización. En este lenguaje se escribe un código que
II.04(02).83
15
representa el problema de optimización a resolver, Mosel tiene
una librería llamada Xpress-MP (Optimizar), que sería la tercera
parte principal de Xpress; esta es la librería que contiene los
algoritmos para la solución de problemas de programación lineal,
programación lineal entera y programación cuadrática [10].
Una característica de Xpress-MP es que cuenta con la opción de
utilizar algoritmos previos a la optimización (presolver), que
haciendo uso de una serie de procedimientos [10], simplifican
el problema reduciendo las filas y columnas redundantes. El uso
de esta ayuda se hace por medio del parámetro “XPRS_PRESOLVE” el
cual puede tomar dos valores, 0 en caso que no se quiera
utilizar o 1 para que el programa lo use. Cuando se utiliza esta
ayuda el programa modifica el problema por lo que este es
distinto al problema original, es por esto que se debe estar
seguro que los resultados corresponden al problema original, ya
que algunos comandos no suministran la información
correspondiente al problema original sino del problema nuevo.
Para la solución de problemas de programación entera, Xpress-MP
utiliza la técnica de Branch and Bound, hay que tener en cuenta
que esta técnica deja bastantes aspectos a decisión de la
persona que la esté utilizando, los cuales se pueden dividir
principalmente en dos categorías, los que consideran qué nodo
escoger entre los nodos activos y los que tienen que ver con qué
variable que no cumpla la restricción de integridad tomar para
dividir el problema. Xpress-MP ofrece al usuario la libertad de
establecer estos aspectos según su criterio, aunque posee de
manera predeterminada una configuración que funciona de manera
correcta en la mayoría de los problemas [4].
En cuanto a la selección de la variable sobre la cual ramificar
Xpress-MP lo que hace primero es solucionar la relajación lineal
del problema, una vez ha hecho esto el programa ha asignado unos
pseudo costos a cada variable que no cumple la condición de ser
II.04(02).83
16
entera, este pseudo costo representa un estimado de la suma por
la cual la función objetivo va a empeorar al forzar esa variable
en especial a ser entera [4]. Por medio del parámetro
“XPRS_VARSELECTION” [4] se puede seleccionar entre varias
estrategias para seleccionar la variable a ramificar basados en
los pseudo costos encontrados, estas opciones se encuentran
especificadas en [4].
Existen varios parámetros que influyen en la selección del nodo
activo a utilizar en el siguiente paso de la técnica de Branch
and Bound. El parámetro “XPRS_NODESELECTION” [4], establece el
grupo de nodos candidatos para ser considerados en la selección
del nodo, dentro de este parámetro existen 5 opciones, las
cuales son las siguientes [4]:
1. Nodos Locales: Selecciona entre los nodos hijos o hermanos
del nodo actual si están activos, de lo contrario
selecciona entre todos los nodos activos.
2. Mejores Nodos: Selecciona entre todos los nodos activos
3. Nodos locales y Profundos: Selecciona entre los nodos hijos
o hermanos del nodo actual de ser posible, en caso
contrario selecciona entre los nodos mas profundos de todos
los nodos activos.
4. Mejores primero, locales después: Utiliza la selección por
mejores nodos durante un número definido de nodos, después
de sobrepasar este número utiliza la búsqueda local.
5. Búsqueda de profundidad: Busca entre los nodos mas
profundos de todos los nodos activos.
El número de nodos para el cual se hace búsqueda global en la
cuarta estrategia esta definido por el parámetro
“XPRS_BREADTHFIRST” [4] este esta predefinido como 10.
Una vez se tiene un grupo de nodos candidatos, para seleccionar
un nodo específico el programa utiliza la estrategia definida en
II.04(02).83
17
el parámetro “XPRS_BACKTRACK” [4] el cual posee tres opciones
distintas. En la configuración predeterminada el valor de este
parámetro es 3, con el cual elige el nodo con la mejor cota, es
decir el nodo cuya solución a la relajación lineal presente el
menor valor de la función objetivo (en caso que se este
minimizando).
Además de los parámetros mencionados anteriormente, existe la
posibilidad de activar un algoritmo previo a cada nodo del árbol
(presolver entero), con el cual se simplifica el problema antes
de intentar optimizar. El nombre del parámetro con el cual se
activa esta ayuda es “XPRS_MIPPRESOLVE” y posee las siguientes 4
opciones:
0. No ejecuta ningún algoritmo previo a la optimización
1. Fijación de costos reducidos
2. Fijación de variables
3. Fijación de variables y de costos reducidos
Otro parámetro que permite manejar Xpress en la solución de
problemas de programación entera es “XPRS_MIPABSCUTOFF” con el
cual se puede establecer una cota mínima previa a la solución
del problema ayudando así a eliminar todos los nodos que no
lleven a un valor de la función objetivo menor al del a cota.
Este es un parámetro que se podría utilizar en caso de obtener
una solución factible por medio de una heurística y desear
llegar al óptimo arrancando desde ese punto.
II.04(02).83
18
Capitulo IV
DISEÑO DEL EXPERIMENTO COMPUTACIONAL
En el diseño y ejecución del experimento se llevaron a cabo
varias acciones encaminadas a tener un experimento consistente,
concluyente y repetible. Dentro de las tareas realizadas hay
varias que se realizaron de manera simultanea, otras requerían
haber concluido tareas anteriores para poder llevarse a cabo, en
este capitulo se explica brevemente cada una de estas tareas,
dentro de las cuales se incluyen la selección de las instancias
de prueba, la implementación de los algoritmos, las ejecución de
las pruebas realizadas y finalmente la obtención de los
resultados.
Instancias de Prueba
A través de los estudios realizados se han ido estableciendo
problemas específicos que permiten comparar distintos métodos de
solución bajo una misma prueba. Estos problemas específicos que
se conocen como instancias de prueba se encuentran
principalmente en artículos técnicos publicados por personas de
gran trayectoria en la investigación de este tipo de problema.
Estas instancias se encuentran en artículos técnicos, algunos
como [11],[12],[13],[14],[15],[16] y [17] cuentan no solo con el
problema ejemplo sino también con resultados obtenidos y las
II.04(02).83
19
soluciones óptimas encontradas. La manera más practica de
encontrar estas instancias es a través de paginas de Internet
dedicadas al estudio de este tipo de problemas. En este
experimento computacional se utilizo la serie de problemas P de
Augerat (Además de la serie P existen la A y la B) [6] la cual
fue hallada en el sitio de Internet www.branchandcut.org. Se
escogió esta serie por la simplicidad de sus problemas (bajo
numero de nodos y vehículos), también por que van aumentando de
complejidad de manera progresiva. En esta serie se utilizan como
costos las distancias euclidianas entre los nodos, y la
información suministrada sobre estas se refiere a sus
coordenadas.
Implementación de los Algoritmos
Los algoritmos que se implementaron fueron VRP1 y VRP4 según la
notación dada por [1]. Este trabajo tomo como base el algoritmo
VRP4 con restricciones de Miller, Tucker y Zemlin hecho por el
profesor Eliécer Gutiérrez quien autorizo su uso. A este se le
hicieron las siguientes modificaciones:
- Se modificó la forma de lectura del archivo de datos,
haciendo posible que lea coordenadas en 2D, tal como las
presentadas por las instancias escogidas.
- Se adaptó para calcular los costos como distancias
euclidianas basadas en las coordenadas del archivo de
datos.
- Se le añadieron los comandos que permiten controlar el
presolver global, el presolver entero y la estrategia de
selección de nodos candidatos.
- Se le modificó la función “printsol”, haciendo posible que
imprima todos los datos presentados en los reportes,
II.04(02).83
20
también se le añadió una función callback que hace que se
invoque cada vez que se presenta una solución entera.
El algoritmo VRP1 se basó en este nuevo algoritmo, modificándole
las restricciones redundantes y adaptando la función de
impresión, la cual necesitó algunos cambios para que se
presentaran las soluciones de una manera correcta.
Realización de las Pruebas
Una vez implementados los algoritmos y teniendo las instancias
de prueba seleccionadas en el formato adecuado se procedió a la
ejecución de las distintas pruebas y la obtención de sus datos.
Estas pruebas fueron realizadas en un único computador el cual
se encuentra en la sala Uena de la universidad de los Andes,
este equipo posee las siguientes características físicas:
Pentium 4 de 2.40 GHZ,256 en RAM y disco de 40GB. La versión de
Xpress-Mosel en la cual se ejecutaron los programas es la 2004B
Professional. Se decidió correr todas las pruebas en un único
computador para así eliminar el error generado al utilizar
diferentes maquinas, esta decisión se baso en las dudas que
existen sobre la posibilidad de comparar los tiempos de
ejecución cuando se utilizan diferentes maquinas [5]
especialmente cuando se utiliza varios equipos en paralelo. Al
hacerlo en una sola maquina es posible comparar los tiempos
obtenidos a través de las distintas pruebas lo cual es de mayor
utilidad que simplemente considerar los resultados obtenidos por
separado.
Con cada archivo de datos se ejecutaban todas las combinaciones
posibles entre Presolver Global (2 opciones), estrategia de
selección de nodos candidatos (5 opciones) y Presolver Entero (4
Opciones), de esta manera para cada algoritmo dado un problema
se obtuvieron 40 archivos de reporte de solución. Para 4
II.04(02).83
21
problemas (P19-2, P20-2, P21-2 y P22-2) se corrieron todas las
opciones para ambos algoritmos, lo que equivale a 320 archivos
de solución. Para el problema P16-8 solo se corrió el algoritmo
VRP1, esto debido a que este mismo problema utilizando el
algoritmo VRP4 excedía las capacidades físicas del equipo. Lo
mismo sucedía para ambos algoritmos cuando se intentaron
utilizar instancias de prueba más complejas, el limite se
encontraba cuando se había pasado de un millón de nodos
aproximadamente lo cual ocurría alrededor de 3 horas después de
estar utilizando el algoritmo. En total se obtuvieron 360
archivos.
Después de analizar estos reportes y definir cual era la mejor
opción en cada uno de los parámetros estudiados se utilizó lo
encontrado para correr una instancia en particular, la P22-2 con
el algoritmo VRP1 utilizando una cota que se le suministraba por
medio del parámetro “XPRS_MIPABSCUTOFF”, esta cota se fue
variando para que representara desde un 100% del valor óptimo
hasta un 110%, con esto se pudo ver como variaba el desempeño
del algoritmo al suministrársele este tipo de dato adicional.
Formato de los Resultados Obtenidos
Los resultados obtenidos a través de este experimento
computacional quedaron consignados en archivos los cuales
presentan la siguiente notación:
ABB-C_D-E-F-G
En donde A representa el grupo al cual pertenecen las
instancias, en este caso esta letra siempre es P ya que solo se
utilizaron instancias del grupo P de Augerat. El siguiente
termino BB se refiere al numero de clientes del problema, el
II.04(02).83
22
numero de nodos es igual a este número mas uno ya que se incluye
el nodo que representa al deposito. La C muestra el número de
vehículos disponible en este problema. La letra D representa el
algoritmo utilizado, haciendo uso de la notación usada por [1],
en este proyecto como se vio en el capitulo II se trabajo con
VRP1 y VRP4. Los terminos E, F y G representan la opción
utilizada en el presolver, la estrategia de selección de nodos
candidatos y el presolver entero respectivamente, estos son
valores numéricos que se explicaron en el capitulo III.
Al ejecutar cada uno de los problemas el algoritmo generó un
reporte con terminación .sol (Ver apéndice B) en el cual están
consignadas para cada solución entera (incluyendo la óptima) la
ruta seguida por cada vehículo y los siguientes datos:
- Valor de la solución actual: Costo de la función objetivo
de la solución entera encontrada.
- Tiempo de ejecución: Calculado como el tiempo actual menos
el tiempo en el que se inicio el algoritmo, esta dado en
segundos con una precisión de +/- 0.0005 segundos.
- Gap: Diferencia en porcentaje entre la mejor solución y la
mejor cota inferior.
- Mejor cota inferior: menor valor que se sabe pueden tomar
los nodos activos restantes.
- Profundidad: Numero de ramificaciones que separan el nodo
madre del nodo de la solución encontrada.
- Número de Nodo: Número de nodos que han sido solucionados
hasta el momento de encontrar esta solución específica.
Al final del archivo se incluye además el valor de la función
objetivo en la solución óptima, y el tiempo total hasta que se
cerró el gap con lo cual se define que la ultima solución es la
óptima.
II.04(02).83
23
La recopilación de los datos más importantes de estos archivos
se hizo en forma de base de datos utilizando una hoja de cálculo
de Excel. En esta base se utiliza el termino mejor solución para
los datos obtenidos en el momento en que se encuentra la que
solución que ya se sabe es la óptima, el termino solución óptima
se utiliza para los datos conseguidos en el momento en que no
quedan más nodos activos, por lo que ya se puede definir que la
solución que se tiene es la mejor posible.
II.04(02).83
24
Capitulo V
ANALISIS DE LOS RESULTADOS EXPERIMENTALES
Los resultados obtenidos en este experimento computacional están
contenidos en 360 archivos correspondientes a los reportes
generados por el programa después de la ejecución de cada
prueba. Para poder manejar tal cantidad de información se creo
una base de datos en Excel en donde se encuentran las
características más importantes de estos archivos. Después por
medio del uso de tablas dinámicas y algunas herramientas
estadísticas básicas se realizó el análisis presentado en este
capitulo. En este se presentan y analizan los resultados
obtenidos dividiéndolos en cada uno de los parámetros que fueron
estudiados. Con el fin de poder analizar la influencia de cada
parámetro por separado sin tener en cuenta los efectos
producidos por los demás parámetros, se compararon los
resultados que eran similares en todos los parámetros
exceptuando el parámetro estudiado, por ejemplo se comparo el
tiempo de la primera solución obtenido en P-20_2_VRP-0-1-1 con
el obtenido en P-20_2_VRP-1-1-1, para así tener en cuenta solo
el efecto generado por el presolver global. Una vez se
organizaron de esa manera se utilizaron dos formas para
estandarizar los datos, la primera consistía en tomar el número
correspondiente a la opción de el parámetro estudiado con la
cual se obtuvo la mejor solución para un criterio en especial y
II.04(02).83
25
luego contar cuantas veces cada una de las opciones fue la mejor
solución, de esta forma se pudo establecer funciones muestrales
de distribución de las mejores respuestas de acuerda con la
opción escogida en ese parámetro en particular. La segunda
manera que se utilizo para hacer posible el análisis de los
datos fue encontrar razones entre los resultados del criterio a
analizar, esto es particularmente fácil para los parámetros que
solo poseen dos opciones, ya que solo se debe establecer una
comparación, por ejemplo en el caso del presolver global se
utilizo la razón entre el tiempo requerido para hallar la
solución optima utilizando el presolver sobre su equivalente sin
el presolver, con estos datos se pudo encontrar una media, una
desviación estándar y establecer un intervalo de confianza
respecto a la media de estas razones, si el numero uno se
encuentra dentro de este intervalo se podría afirmar que en
promedio no existe evidencia estadística para afirmar que los
resultados obtenidos con las distintas opciones son diferentes
con un 1-α de confianza. En los casos en los cuales hay más de dos opciones las razones se hicieron entre el mejor resultado
sobre el segundo mejor resultado y el mejor sobre el peor
resultado. Con esto se puede concluir si realmente es importante
buscar elegir la mejor opción o si estadísticamente son
indiferentes los resultados respecto a los cambios en ese
parámetro. Con los resultados obtenidos también se puede
realizar un análisis comparando cada una de las opciones contra
las demás.
Para la realización de los intervalos se utilizó el teorema del
límite central que dice que cuando el número de datos tiende a
infinito la media de un parámetro sin importar su distribución
se distribuye de manera normal con media µ y desviación estándar
σ, esto aplica incluso en el caso que se tenga solo una media. Hay que tener en cuenta que estos parámetros son poblacionales, si no se conocen se pueden reemplazar por estimadores para la
II.04(02).83
26
media y la desviación, los cuales en el caso de tener solo una
muestra se calculan utilizando la distribución muestral de los
datos con los cuales se calculo la media sobre la cual se quiere
crear el intervalo, por esto así la media se distribuya de
manera normal los estimadores usados para calcular sus
intervalos pueden ser tomados de otro tipo de distribución.
En este caso como no se contaba con los datos poblacionales se
utilizaron los parámetros de las funciones de probabilidad
muestrales que se encontraron (Apéndice C) para la construcción
de los intervalos de confianza, estos se construyeron de la
siguiente manera:
NSZX ⋅±
En donde X representa el estimador de la media calculado con los
parámetros de la distribución muestral. Z es el valor que se
utiliza debido a que la media se distribuye de manera normal, en
este caso se utiliza un valor de 1.96 lo cual equivale a una
confianza del 95%. No fue necesario utilizar una distribución t
ya que a medida que aumenta el numero de datos las diferencias
entre esta y la normal dejan de ser significativas, y el numero
de datos que se tomaron fue grande. S representa el estimador de
la desviación estándar poblacional. N es el número de datos que
se usaron.
La prueba de bondad y ajuste que se les realizo a las
distribuciones que se encontraron para las razones de los
diferentes criterios fue la Kolmogorov – Smirnov, se utilizó
esta en lugar de una Chi cuadrada debido a que eran funciones de
distribución continuas, las cuales se prueban mejor con este
estadístico. En esta prueba la hipótesis nula es que los datos
tienen una función de distribución de probabilidad específica
II.04(02).83
27
contra la cual se prueba y que es elegida por la persona que
realiza la prueba contra la alternativa que se distribuyan de
alguna otra manera. Lo que se mide para validarla o no es el
error de Tipo I el cual es rechazar Ho dado que es cierta, es
decir afirmar que se distribuye de alguna otra manera cuando
efectivamente se distribuye de la forma que se creyó en un
principio. Por esto se busca distribuciones en la cuales es poco
probable que se rechace la hipótesis nula, esto se mide a través
del P-value ya que entre mayor sea este es menos probable que se
rechace la hipótesis de que la muestra se distribuye de la forma
esperada. El termino α representa el tamaño de la zona de
rechazo del estadístico de prueba entre mayor sea mas probable
es rechazar, por eso si el P-Value es mayor a este valor lo mas
probable es que no se rechace la hipótesis nula con lo cual se
puede afirmar que no hay razones estadísticas para decir que la
muestra no se distribuye de la forma esperada.
Comparación entre los Algoritmos VRP1 y VRP4
Como se vio en el capitulo tres, la diferencia entre los
algoritmos VRP1 y VRP4 radica en la utilización de un tercer
índice para determinar exactamente que vehículo visita cada
cliente, esto para poder solucionar problemas mas complejos en
los que se requiere que un vehículo especifico visite un cliente
en especial u otras variaciones del CVRP en las cuales hay
vehículos con distintas capacidades. Al utilizar este tercer
índice se aumenta la complejidad del problema, a continuación se
presenta una tabla con las características de la matriz del
problema para cada instancia cuando se utiliza cada algoritmo.
Rows Columns
Nonzero Elements
Global Entities
P19-2_0 362 361 1656 342 P20-2_0 401 400 1843 380
VRP1
P21-2_0 442 441 2040 420
II.04(02).83
28
P22-2_0 485 484 2247 462 P19-2_1 344 360 1602 342 P20-2_1 382 399 1786 380 P21-2_1 442 440 1980 420
P22-2_1 464 483 2184 462 P19-2_0 743 760 3426 722 P20-2_0 882 840 3806 800 P21-2_0 905 924 4206 882 P22-2_0 992 1012 4626 968 P19-2_1 688 738 3276 702 P20-2_1 764 817 3648 779 P21-2_1 844 900 4040 860
VRP4
P22-2_1 928 987 4452 945
Como se puede ver al utilizar VRP4 se aumenta a aproximadamente
el doble el número de columnas, filas, elementos distintos a
cero y entidades globales. Se esperaba que por lo tanto los
tiempos para el algoritmo VRP1 fueran menores a los
correspondientes utilizando el algoritmo VRP4 y se buscaba ver
cuál era la relación entre estos. Al estudiar la razón entre los
tiempos obtenidos por medio de VRP1 divididos entre los tiempos
encontrados a través de VRP4 se obtuvo los datos contenidos en
la siguiente tabla.
Tiempo Primera Solución
Tiempo Mejor Solución
Tiempo Solución Óptima
Media 0,171 0,116 0,0873 Desviación Estándar 0,173 0,153 0,0348 Intervalo de 0,0989 0,0986 0,0818 Confianza 95% 0,2468 0,1353 0,0927
En esta se confirma lo esperado, lo tiempos son equivalentes a
menos de la mitad, y se puede afirmar con una confianza del 95%
que el tiempo que se demora en encontrar el algoritmo la
solución óptima en el VRP1 se encuentra entre un 8.18% a un
9.27% del tiempo que demora en encontrarla el algoritmo VRP4. La
razón por la cual los tiempos aumentaron mas de diez veces
cuando el tamaño de la matriz del problema solo aumenta al doble
es que este aumento en el número de variables y restricciones no
afecta solamente el tiempo que demora el algoritmo en resolver
II.04(02).83
29
las relajaciones lineales, sino que también aumenta el número de
variables a elegir cuando se está utilizando la técnica de
Branch and Bound lo que incrementa su tiempo de solución de
manera exponencial.
Presolver Global
Como se explicó anteriormente se utilizó un conteo de las veces
en las cuales para cada criterio utilizar el presolver tuvo un
mejor desempeño y se compara con el número de veces que no.
Basados en este conteo se realizo la siguiente distribución de
probabilidad muestral, en la cual se muestran los criterios
analizados.
Comparación de Desempeño cuando se Utiliza el Presolver Global
0
0,2
0,4
0,6
0,8
1
1,2
TiempoPrimera
Respuesta
TiempoMejor
Res puesta
TiempoSoluciónÓptima
Mejor Valorpara laPrimeraSolución
MayorNúmero deRespuestas
Enteras
Criterios
Por
cent
aje
de C
asos
en
los
que
es la
M
ejor
Sol
ució
n
Utilizando el presolverSin Utilizar el Presolver
Gráfico 1 Comparación de Desempeño para Presolver Global
II.04(02).83
30
En ésta se puede ver que en todos los aspectos excepto el valor
de la primera solución al utilizar el presolver se obtuvieron un
mayor número de mejores soluciones que al no utilizarlo, siendo
especialmente notoria la diferencia en el número de casos
favorables para el menor tiempo de solución óptima. Con el fin
de establecer si esta diferencia es significativa se realizó un
análisis en el cual organizaron los datos de tal manera que
quedaran parejas en las que todos los parámetros eran similares
exceptuando el correspondiente al presolver global, una vez
hecho esto se calculó la razón entre el valor del criterio
cuando no se utiliza presolver sobre el valor del mismo criterio
cuando si se utiliza. Con todas las razones halladas se calculó
una media y una desviación estándar. A estas razones se les
realizo además pruebas de bondad de ajuste para saber como se
distribuían (Apéndice C) con lo cual se calcularon intervalos de
confianza al 95% para ver si existe una diferencia en promedio
que pueda ser demostrada de manera estadística entre los
resultados obtenidos con el presolver y los que se obtuvieron
sin hacer uso de este. Estos resultados se presentan en la
siguiente tabla.
Tiempo Primera Solución
Tiempo Mejor Solución
Tiempo para definir que es Optima
Valor de la Primera Solución Primera
Media 1.44 1.57 0.913 1.0239 Desviación Estándar 3.11 3.87 0.318 0.1393 Intervalo de 1.2296 1.1520 0.8666 0.9996 Confianza 95 % 1,6503 1.6079 0.9593 1.0403
En esta encontramos que todos los intervalos de confianza al 95%
exceptuando el correspondiente al valor de la primera solución
son significativos estadísticamente. Incluso este último lo pero
con una confianza menor, de un 90%. Basados en esto y en la
distribución que se presento anteriormente se puede afirmar que
hay una diferencia significativa entre utilizar el presolver y
no utilizarlo en cuanto al tiempo que se requiere para encontrar
II.04(02).83
31
la solución óptima. Los resultados en cuanto al tiempo que
demora en encontrar la primera y la mejor solución son
contradictorios, ya que en la distribución se veía que al
utilizar el presolver se presenta un mayor número de casos
favorables en estos aspectos pero en promedio sus tiempos van a
tender a ser mas altos que los conseguidos sin utilizar el
presolver, esto se puede explicar de la siguiente manera: a
pesar de que el presolver presenta un mayor número de casos
favorables en estos la diferencia entre los valores no es tan
grande como en los casos cuando es mejor no utilizar el
presolver, por lo que unos pocos casos con una mayor diferencia
anulan a muchos con diferencias pequeñas.
Un resultado que no era esperado pero que también es
significativo aunque solo a un 90% es la diferencia entre el
valor de la primera solución cuando se usa el presolver y cuando
no se utiliza, lo raro es que en este caso las soluciones
tienden a ser un 2.4 por ciento mayores cuando se utiliza el
presolver. Si se tiene en cuenta que se esta minimizando y que
no existe una diferencia que pueda ser probada entre el tiempo
para encontrar la primera solución utilizando el presolver y
cuando no, se podría afirmar entonces que si lo que se busca es
encontrar la primera solución entera es mejor no utilizar el
presolver.
Estrategia de Selección de Nodos
El procedimiento realizado para el análisis fue similar al
utilizado en el caso del presolver global, comparando el número
de casos favorables para cada criterio según la estrategia
utilizada. Es este caso encontramos que la mayoría de los
aspectos están distribuidos de una manera muy uniforme entre
todas las estrategias exceptuando la número 2, esto hace que sea
difícil predecir cual es la mejor estrategia a seguir, ya que no
II.04(02).83
32
existen diferencias radicales entre el número de casos
favorables para cada caso, por ejemplo en esta muestra al
escoger la que se consideraría la mejor opción cuando se trata
de minimizar el tiempo en encontrar la solución óptima (la cual
sería la estrategia uno de búsqueda local) solo se esta teniendo
un 35% de posibilidades de estar tomando la mejor solución. Por
lo que siempre va ser mas probable estar tomando una estrategia
errada que una correcta.
Comparación de Desempeño dada una Estrategia de Selección de Nodos Candidatos
00,10,20,30,40,50,60,70,80,9
Búsquedade
Profundidad
Mejoresprimero,Loc alesdespués
NodosLocalesPrimero,después
profundos
Mejores Locales
Frac
ción
de
los
Cas
os T
otal
es Tiempo Primera Solución
Mejor Primera Solución
Menor Tiempo Mejor Solución
Menor Tiempo Total
Mayor Número de SolucionesEnteras
Gráfico 2 Comparación de Desempeño de una Estrategia de Selección de
Nodos Candidatos
Se pudo verificar lo propuesto por [3] quien afirmaba que por
medio de una búsqueda de profundidad se encontraba más
rápidamente una respuesta entera factible, esto se ve en el
mayor número de casos favorables presentados por la opción cinco
(búsqueda entre todos los nodos más profundos), la cual posee
casi un 45% de los casos totales.
II.04(02).83
33
Buscando si realmente había una diferencia significativa entre
los resultados alcanzados por la primera solución respecto a las
demás se realizo un análisis de las razones entre la mejor
solución sobre la peor y entre la mejor sobre la segundo mejor,
los datos que se aparecen en la siguiente tabla.
Tiempo Primera solución Valor Primera Solución
Peor Segunda Peor Segunda Media 0,0668 0,796 0,715 0,902 Desviación Estándar 0,0869 0,176 0,102 0,0639 Intervalo de 0,05537 0,7550 0,6913 0,8871 Confianza 95% 0,07832 0,8369 0,7386 0,9168
Tiempo Mejor Solución Tiempo Solución Óptima
Peor Segunda Peor Segunda Media 0,211 0,616 0,536 0,855 Desviación Estándar 0,135 0,232 0,199 0,135 Intervalo de 0,1796 0,5621 0,4896 0,8236 Confianza 95% 0,2423 0,6698 0,5823 0,8863
Los resultados mostrados en esta tabla hacen más preocupante la
falta de criterios para escoger la mejor estrategia a seguir, ya
que en todos los casos los intervalos de confianza muestran que
la mejor opción si presenta mejores valores que la segunda mejor
opción y es valores mucho mejores que la peor opción. Por
ejemplo en el caso del tiempo de solución óptima la mejor
opción representa entre un 82% a un 88% del tiempo de la segunda
mejor opción y entre un 48% a un 58% del tiempo de la peor
estrategia,
Debido a esto la mejor estrategia a seguir de no presentarse
ningún cambio es tomar la opción número uno, con la cual se
obtiene la mayor probabilidad de estar tomando la decisión
correcta y bajas posibilidades de estar tomando la peor.
II.04(02).83
34
La opción número dos es la que presenta mayores diferencias
respecto a las demás, en esta los nodos candidatos son todos los
nodos activos, lo que hace que demore mas encontrando las
soluciones, pero cuando lo hace se acerca de una vez al valor
del óptimo. Sin embargo sus tiempos son casi siempre
considerablemente mayores que los obtenidos a través de las
otras estrategias (como se puede ver en la gráfica de
distribución) y fue en menos del 5% de los casos la opción que
tomó el menor tiempo en hallar la solución óptima. Por eso es
la primera estrategia que se puede descartar en cuanto a una
estrategia de selección de nodos candidatos. Sin embargo debe
tenerse en cuenta en investigaciones futuras ya que su
comportamiento diferente la hace interesante en cuanto a
analizar su comportamiento cuando se varían otros aspectos.
Fracción Promedio del Tiempo Total que Tarda en Encontrar la Primera Solución dada Una Estrategia de Selección de Nodos
00,050,10,150,20,250,30,350,4
Búsqueda deProfundidad
Mejoresprimero,Localesdespués
Nodos LocalesPrimero,después
profundos
MejoresLocales
Gráfico 3 Fracción del tiempo que tarda en encontrar la primera
solución dada una estrategia de selección de nodos candidatos
En las demás estrategias el tiempo que se toma encontrando esta
primera solución equivale a menos del 5% del tiempo total que
demoraron en determinar el óptimo, por lo que en general se
puede esperar obtener una respuesta factible en poco tiempo. Sin
II.04(02).83
35
embargo en la mayoría de esos casos esta primera solución se
encuentra alejada de la solución óptima, por lo que de
suministrársele una cota que esté más próxima se debería mejorar
también su desempeño. En la siguiente tabla se muestra la
diferencia promedio entre la solución óptima y primera respuesta
dado una estrategia de selección de nodos candidatos
representada como fracción del valor de la solución óptima:
5 4 3 2 1 Media 0,354604976 0,33942259 0,35477536 0,068333333 0,2955773 Desviación Estándar 0,186216829 0,19008997 0,20144853 0,095077102 0,1926037
La estrategia dos también presenta un comportamiento diferente
en cuanto a la fracción del tiempo total que le toma encontrar
la mejor solución, en las otras este tiempo tiende a ser menor
al 50% del tiempo total, sin embargo en la opción dos es
superior al 70%, esto quiere decir que la estrategia dos es la
que menos tiempo requiere para terminar de acotar la solución y
definir que es óptima.
II.04(02).83
36
Fracción Promedio del Tiempo Total que Tarda en Encontrar la Mejor Solución dada Una Estrategia de Selección de Nodos
0
0,1
0,2
0,3
0,4
0,5
0,6
0,7
0,8
Búsqueda deProfundidad
Mejores primero,Locales después
Nodos LocalesPrimero,después
profundos
MejoresLocales
Gráfico 4 Fracción de tiempo que demora en encontrar la mejor solución
dada una estrategia de selección de nodos candidatos
En los otros casos el tiempo que demora en terminar de acotar es
muy significativo, esto hace que sea interesante buscar la
manera de ayudar al algoritmo a acotar de una manera más rápida
la solución, ya que con esto se podría ver reducido
significativamente el tiempo total de ejecución.
Presolver Entero
En la gráfica de distribución de probabilidad del presolver
entero se puede apreciar que la opción de fijar los costos
reducidos y las variables por medio de procesos lógicos antes de
solucionar el problema presenta una clara superioridad sobre las
demás en cuanto a poseer el menor tiempo para encontrar la
solución optima. Un 82% de los casos, seguir esta estrategia es
la mejor opción que se puede tomar, adicionalmente es la que
presenta las mayores probabilidades de obtener en un menor
II.04(02).83
37
tiempo la primera solución, la mejor solución y la que presenta
un mayor número de respuestas enteras, lo cual es conveniente ya
que a medida que se van presentando las soluciones se puede
decidir que se ha llegado a una que esta dentro del limite
aceptable y terminar la ejecución sin tener que llegar a la
optimalidad.
Comparación de Desempeño dado un Tipo de Presolver Entero
0,00%
10,00%
20,00%
30,00%
40,00%
50,00%
60,00%
70,00%
80,00%
90,00%
3 2 1 0
Opción de Presolver Entero Utilizada
Porc
enta
je S
obre
los
Caso
s To
tale
s
Menor Tiempo PrimeraSoluciónMejor Primera Solución
Menor Tiempo Mejor Soluc ión
Menor Tiempo Total
Mayor Numero de Soluc ionesEnteras
Gráfico 5 Comparación de Desempeño dado un Tipo de Presolver Entero
Basados en los intervalos de confianza se puede confirmar la
importancia de este parámetro, ya que la diferencia entre
escoger la segundo mejor opción en lugar de la mejor representa
un ahorro de alrededor del 15% en cuanto al tiempo de solución
óptima.
II.04(02).83
38
Tiempo Primera Solución Valor Primera Solución Peor Segunda Peor Segunda Promedio 0,554 0,865 0,891 0,978 Desviación Estándar 0,271 0,218 0,0876 0,0534 Intervalo de 0,5126 0,7954 0,8046 0,9345 Confianza 95% 0,6153 0,8869 0,9151 1.0101 Tiempo Mejor Solución Tiempo Solución Optima Peor Segunda Peor Segunda Promedio 0,421 0,743 0,579 0,843 Desviación Estándar 0,221 0,224 0,162 0,113 Intervalo de 0,3694 0,6907 0,5453 0,7918 Confianza 95% 0,4725 0,7952 0,6126 0,8945
Este es el parámetro que muestra un comportamiento más claro y
en cual se puede tener la mayor certeza sobre la estrategia a
seguir.
Fijación de una cota máxima para la función objetivo
Se corrió el problema correspondiente a P22-2_VRP1-1-1-3
añadiéndole una cota preestablecida la cual variaba desde
valores equivalentes a un 100% del valor óptimo del problema
hasta un 110%. Con estos resultados se comparó principalmente
los tiempos que se demoro en encontrar la mejor solución y el
tiempo que tardo en definir que era óptima al terminar de
acotarla.
Los resultados obtenidos no satisficieron la expectativas del
autor quien esperaba ver una reducción mayor en el tiempo
necesario para obtener la solución óptima ya que no solamente se
le estaba suministrando una primera solución que le ahorraría el
tiempo necesario para llegar hasta ella, sino que también el
valor de esta cotas era de muy buena calidad, siendo bastante
cercanas al óptimo. En la siguiente gráfica se ven los tiempos
que demoro en segundos para cada una de las cotas utilizadas:
II.04(02).83
39
Desempeño con el uso de una cota mínima predefinida
0102030405060708090
100
100%
101%
102%
103%
104%
105%
106%
107%
108%
109%
110%
Valor de la cota respecto al óptimo
tiem
po (s
egun
dos)
Tiempo que demoroen encontrar la mejorsoluciónTiempo que demoroen terminar de acotary definir optimalidad
El Tiempo que demora en definir optimalidad es menor en todos
los casos a el tiempo sin utilizar la cota, sin embargo se
espera que la gráfica fuera en su totalidad creciente ya que se
utilizo el mismo computador, el mismo problema y los mismos
parámetros, por lo que lo único que se esperaría influyera en la
variación sería el valor de la cota que se le estaba
suministrando. Por estas razones es bastante extraña la
presencia de estos saltos en el desempeño. Para poder comparar
mejor los resultados obtenidos en cuanto al tiempo en hallar el
óptimo respecto al la solución sin acotar se gráfico la fracción
que cada uno representa, así se pudo ver que con valores de cota
hasta un 2% representaría un ahorro de alrededor de un 23 a 30%
del tiempo, los demás valores representan ahorros menores aunque
exceptuando la cota al 103% siempre son superiores a un 10% del
tiempo.
II.04(02).83
40
Fracción del tiempo en hallar el óptimo de los algortimos acotados respecto a el
algoritmo no acotado
00,10,20,30,40,50,60,70,80,9
1
100%
101%
102%
103%
104%
105%
106%
107%
108%
109%
110%
Cota
Frac
ción
Basados en estos resultados se puede afirmar que aunque si se
presenta un beneficio al utilizar una cota este no es lo
suficientemente grande como para poder resolver problemas de
mayor complejidad por este método sin requerir mayor poder
computacional por lo que la ventaja no es tan grande como se
esperaba. Sin embargo falta estudiar mejor el comportamiento con
el uso de una cota cuando se utilizan otros parámetros y en el
caso de utilizar otros modelos matemáticos.
II.04(02).83
41
Capitulo VI
CONCLUSIONES
Basados en los análisis realizados en el capitulo anterior se
puede llegar a las siguientes conclusiones:
- El uso del presolver entero cuando se fijan tantos las
variables como los costos reducidos representa en el 82% de
los casos la mejor alternativa a escoger, por lo que es la
opción mas adecuada en cuanto a este parámetro, además es
la que presenta mayores probabilidades reencontrar la
primera respuesta en un tiempo menor, así como de poseer un
mayor numero de soluciones enteras, es importante saber
esto ya que este no es el valor predeterminado para este
parámetro por lo que si se trabaja sin hacer modificaciones
lo mas probable es que se este empleando un tiempo mayor al
necesario para encontrar la solución óptima.
- Cuando se utiliza la opción en la cual los nodos candidatos
son todos los nodos activos (opción dos) se observa un
comportamiento claramente distinto a las demás, ya que se
demora más en encontrar una primera solución y esta es
generalmente bastante cercana al valor óptimo. Es
importante ver que es la opción que presenta una mayor
fracción del tiempo total para encontrar la primera
solución y la que requiere una menor fracción para terminar
II.04(02).83
42
de acotar. Esta es también el tipo de selección de nodos
candidatos que presenta menor numero de soluciones enteras,
llegando incluso a encontrar la solución óptima en la
primera solución obtenida lo cual no resulta conveniente.
- El uso del presolver global presenta en general mejores
resultados en cuanto al tiempo que demora en obtener la
solución óptima, sin embargo no se puede concluir nada
acerca de las ventajas o desventajas en cuanto al tiempo
que demora en encontrar la primera solución o la mejor
solución. Al utilizarlo la primero respuesta que se
encuentra es estadísticamente mayor que al no hacerlo, por
lo que si se busca primeras soluciones de mayor calidad no
es recomendable utilizar esta herramienta.
- La mejor estrategia de selección de nodo a seguir si se
quiere encontrar la primera solución en el menor tiempo
posible es la búsqueda de profundidad (opción cinco), lo
cual coincide con lo encontrado en la literatura [3]
- Al utilizar una cota como máxima valor de la función
objetivo se lograron disminuir el tiempo que se requiere
para encontrar la solución óptima, sin embargo esta
disminución es en el mejor de los casos (al suministrarle
el valor óptimo) menor a un 35% del tiempo por lo que
incluso utilizando la cota no va ser factible resolver
problemas mas grandes que los resueltos, al no ser que se
posea un mayor poder de computo.
- Todos los parámetros hacen que se presenten diferencias
estadísticamente significativas en los criterios evaluados,
por lo que ninguno puede ignorarse debiendo en cambio
buscar la manera de tomar la decisión más acertada posible.
II.04(02).83
43
Capitulo VI
INVESTIGACIÓN FUTURA
Basados en los resultados obtenidos se puede apreciar que la
solución de problemas CVRP utilizando únicamente medios
analíticos esta restringida a problemas de baja complejidad y al
uso de herramientas de computo de alta potencia. Considerando
esto y el gran avance que se ha presentado en el uso de
heurísticas para la solución de este tipo de problemas el autor
considera interesante el uso combinado de estas técnicas junto
con algoritmos analíticos que reduzcan los tiempos de ejecución
y garanticen la optimalidad de la solución. Aunque ya se intento
en este trabajo utilizar una cota máxima para el óptima con
resultados no muy alentadores todavía falta investigar mas al
respecto, variando mas parámetros y realizando mas pruebas para
ver como responden los tiempos de solución. También se sugiere
investigar el posible uso de una cota mínima para el óptimo, ya
que si se obtuvo una solución que normalmente no se aleja mas de
un 5% del valor del óptimo se podría afirmar con cierta
confianza que se espera que el óptimo no este por debajo de un
90% del valor de la solución obtenida, al hacer esto e ir
acotando por ambos extremos se podría mejorar aun mas los
tiempos necesarios para encontrar el óptimo.
La investigación futura puede basarse en los resultados
obtenidos en esta investigación, sobre el comportamiento
II.04(02).83
44
presentado por los algoritmos al variar la forma como se
seleccionan los nodos candidatos, también ya no es necesario
demostrar la efectividad del presolver entero, ya que su
beneficio quedo muy bien demostrado.
Dentro de estudios posteriores se debe considerar el uso de las
herramientas suministradas por Xpress para la ejecución de
algoritmos en paralelo haciendo uso así de una mayor capacidad
de computo, ya que como se menciona en [10] esto fue diseñado
pensando especialmente en problemas de programación entera de
alguna dificultad.
Finalmente sería interesante la implementación de los otros
modelos matemáticos (modelos por flujo de mercancías y modelos
de partición en grupos) y de relajaciones del modelo por flujo
de vehículos para así comparar el desempeño de estos frente a
los modelos por flujo de vehículos y frente a las heurísticas,
para cada uno de estos modelos pueden utilizarse los mismos
criterios de comparación y variar los mismos parámetros que se
utilizaron en este trabajo, con lo cual se podría comparar de
mejor manera los resultados obtenidos..
II.04(02).83
45
Apéndice A
CÓDIGO UTILIZADO
Código VRP4 (Modificado del código hecho por el Profesor Eliécer Gutiérrez
bajo su autorización)
!Utilizando distancias Euclidianas a través de coordenadas !y restricciones de Miller, Tucker y Zemlin model "VRP4 pag.15" uses "mmxprs", "mmsystem" parameters inputFile = "P20-2.dat" !Defines the input file outputFile = "P20-2_VRP4-0-5-3.sol" !Defines the output file end-parameters declarations N: integer !Number of sites K: integer !Number of vehicles V:range !Set of sites (integers) Sites: array(V) of string !Labels for sites (strings) c: array(V,V) of real !Matrix of Costs or Distances cx: array(V) of real !Site coordinate on X-axis cy: array(V) of real !Site coordinate on Y-axis d: array(V) of real !Demands for each site C: real !Capacity constraint starttime: real Solution_time: real end-declarations
II.04(02).83
46
initializations from inputFile N K Sites cx cy d C end-initializations starttime := gettime !Asigns de current time as the starting time writeln("Number of sites: ", N) !Start writing the report writeln("Number of routes: ", K) !Filling Matrix of Cost with Euclidian distances in 2D forall(i in V, j in V) do c(i,j) := sqrt((cx(i)-cx(j))^2+(cy(i)-cy(j))^2) end-do declarations x: array(V,V,1..K) of mpvar !x(i,j,k)=1 if arc (i j) is
traversed by vehicle k y: array(V,1..K) of mpvar !y(i,k) = 1 if vehicle k serves
customer i u: array(V,1..K) of mpvar !u(i,k): Cumulated load for vehicle
k when arrives to customer i end-declarations forall(i in V, j in V, k in 1..K) create(x(i,j,k)) forall(i in V, k in 1..K) create(y(i,k)) forall(i in V, k in 1..K) create(u(i,k)) forall(i in V, j in V, k in 1..K) x(i,j,k) is_binary forall(i in V, k in 1..K) y(i,k) is_binary !CONSTRAINTS ! (1.29) Each customer is visited exactly once Notation according ! to [1] forall(i in V | i<>0) sum(k in 1..K) y(i,k) = 1 ! (1.30) K vehicles from depot sum(k in 1..K) y(0,k) = K ! (1.31) Same vehicle enters and leaves for each customer forall(i in V, k in 1..K) sum(j in V | i<>j ) x(i,j,k) = y(i,k) forall(i in V, k in 1..K) sum(j in V | i<>j ) x(j,i,k) = y(i,k)
II.04(02).83
47
! (1.37-38) Miller-Tucker-Zemlin subtour elimination & Capacity constraint forall(i in V, j in V, k in 1..K | i<>0 and i<>j ) u(i,k) - u(j,k) + C * x(i,j,k) <= C - d(j) forall(i in V, k in 1..K | i<>0 ) d(i) <= u(i,k) forall(i in V, k in 1..K | i<>0 ) u(i,k) <= C !OBJECTIVE FUNCTION ! Minimize total cost Z := sum(i in V, j in V) c(i,j)* sum(k in 1..K ) x(i,j,k) ! Write the results in the given file fopen(outputFile,F_OUTPUT) ! Everytime it finds a integer solution it ! calls the "printsol" routine setcallback(XPRS_CB_INTSOL,"printsol") ! Turns the presolve off or on setparam("XPRS_PRESOLVE", 0) ! This determines which nodes will be ! considered for solution once the current ! node has been solved setparam("XPRS_NODESELECTION", 5) ! Establishes which kind of presolve will be done after solving each ! node setparam("XPRS_MIPPRESOLVE", 3) minimize (Z) writeln("") writeln ( "Status : " , getprobstat ) writeln ( "Objective Function : " , getobjval) Solution_time := gettime - starttime writeln ( "Total Time : " , Solution_time , " seconds") ! Defines the Procedure “printsol” procedure printsol declarations objval: real Solution_time: real load : real s : boolean i: integer t: integer Solution_gap: real depth: integer node: integer bound: real
II.04(02).83
48
end-declarations depth:=getparam("XPRS_NODEDEPTH") node:=getparam("XPRS_NODES") bound:=getparam("XPRS_BESTBOUND") objval := getparam("XPRS_lpobjval") Solution_time := gettime - starttime Solution_gap := (objval-bound)*100/bound writeln("____________________________________") writeln("Solution value: ",objval) writeln("Execution Time: ",Solution_time," seconds") writeln("Gap: ",Solution_gap," %") writeln("Best Bound: ",bound) writeln("Depth: ",depth) writeln("Node: ",node) writeln("____________________________________") writeln("") writeln("Assigned Routes") writeln("") setparam("XPRS_SOLUTIONFILE",0) forall( k in 1..K ) do writeln("vehicle ",k) i:=0 s:= false load := 0 while (not s) do forall ( j in V ) do if ( getsol(x(i,j,k))=1 ) then t := j; load := load + d(j) if ( j=0 ) then s := true else writeln(j," "+load) end-if end-if end-do i:= t end-do end-do setparam("XPRS_SOLUTIONFILE",1) end-procedure
Código VRP1
! Modelo Simétrico Condiciones Millar, Tucker and Zimler ! Distancias Euclidianas model "VRP1 pags 12 and 13" uses "mmxprs", "mmsystem" parameters
II.04(02).83
49
inputFile = "P16-8.dat" outputFile = "P16-8_VRP1.sol" end-parameters declarations N: integer !Number of sites K: integer !Number of vehicles V:range !Set of sites (integers) Sites: array(V) of string !Labels for sites (strings) c: array(V,V) of real !Matrix of Costs or Distances cx: array(V) of real !Site coordinate on X-axis cy: array(V) of real !Site coordinate on Y-axis d: array(V) of real !Demands for each site C: real !Capacity constraint starttime: real Solution_time: real end-declarations initializations from inputFile N K Sites cx cy d C end-initializations starttime := gettime writeln("Number of sites: ", N) writeln("Number of routes: ", K) !Filling Matrix of costs forall(i in V, j in V) do c(i,j) := sqrt((cx(i)-cx(j))^2+(cy(i)-cy(j))^2) end-do declarations x: array(V,V) of mpvar !x(i,j)=1 if arc (i j) is traversed u: array(V) of mpvar !u(i): Cumulated load for vehicle when arrives to customer i end-declarations forall(i in V, j in V) create(x(i,j)) forall(i in V) create(u(i)) forall(i in V, j in V) x(i,j) is_binary !CONSTRAINTS ! (1.4) Only one arc arrives to each costumer notation according to [1]
II.04(02).83
50
forall(j in V | j<>0) sum(i in V | i<>j) x(i,j) = 1 ! (1.5) Only one arc leaves each costumer forall(i in V | i<>0) sum(j in V | i<>j) x(i,j) = 1 ! (1.6 and 1.7) K vehicles leaves and arrive to the depot sum(i in V | i<>0) x(0,i) = K sum(i in V | i<>0) x(i,0) = K ! (1.13-14) Miller-Tucker-Zemlin subtour elimination & Capacity constraint forall(i in V, j in V | i<>0 and i<>j ) u(i) - u(j) + C * x(i,j) <= C - d(j) forall(i in V | i<>0 ) d(i) <= u(i) forall(i in V | i<>0 ) u(i) <= C !OBJECTIVE FUNCTION ! Minimize total cost Z := sum(i in V, j in V) c(i,j)* x(i,j) ! Write the results in the given file fopen(outputFile,F_OUTPUT) ! Everytime it finds an integer solution it ! calls the "printsol" routine setcallback(XPRS_CB_INTSOL,"printsol") ! Turns the presolve off !setparam("XPRS_PRESOLVE", 0) ! This determines which nodes will be ! considered for solution once the current ! node has been solved setparam("XPRS_NODESELECTION", 1) ! Establishes which kind of presolve will be done after solving each ! node setparam("XPRS_MIPPRESOLVE", 2) minimize (Z) ! Output writeln("") writeln ( "Status : " , getprobstat ) writeln ( "Objective Function : " , getobjval) Solution_time := gettime - starttime writeln ( "Total Time : " , Solution_time , " seconds") procedure printsol declarations objval: real Solution_time: real load : real s : boolean t: integer Solution_gap: real
II.04(02).83
51
depth: integer node: integer bound: real end-declarations depth:=getparam("XPRS_NODEDEPTH") node:=getparam("XPRS_NODES") bound:=getparam("XPRS_BESTBOUND") objval := getparam("XPRS_lpobjval") Solution_time := gettime - starttime Solution_gap := (objval-bound)*100/bound writeln("____________________________________") writeln("Solution value: ",objval) writeln("Execution Time: ",Solution_time," seconds") writeln("Gap: ",Solution_gap," %") writeln("Best Bound: ",bound) writeln("Depth: ",depth) writeln("Node: ",node) writeln("____________________________________") writeln("") writeln("Assigned Routes") writeln("") setparam("XPRS_SOLUTIONFILE",0) !Routes previous:=0 memory:=0 forall( i in V | i <> 0)do if (getsol(x(0,i)) = 1) then if (i > previous) then memory := memory + 1 previous := i writeln("") writeln("Vehicle ",memory) j:=i load := d(j) s:=false while (not s)do if (j=i) then writeln(j," "+load) end-if forall (f in V) do if (getsol(x(j,f))=1) then t := f; load := load + d(f) if ( f=0 ) then s := true else writeln(f," "+load) end-if end-if end-do j := t end-do end-if end-if end-do
II.04(02).83
52
setparam("XPRS_SOLUTIONFILE",1) end-procedure
II.04(02).83
53
Apéndice B
EJEMPLO DE UN ARCHIVO DE SOLUCIÓN
Matrix: Rows (Constrains): 992 Columns (Variables): 1012 Nonzero elements: 4626 Global entities: 968 Presolved: Rows (Constrains): 928 Columns (Variables): 987 Nonzero elements: 4452 Global entities: 945 ____________________________________ Solution value: 217.87 Execution Time: 1281.82 seconds Gap: 1.63918 % Best Bound: 214.356 Depth: 36 Node: 108741 ____________________________________ Assigned Routes vehicle 1 16 12 1 19 10 27 8 55 18 72 19 78 3 94 12 108 15 119 11 126 4 149 vehicle 2
II.04(02).83
54
6 19 7 34 2 64 13 70 9 78 21 88 17 114 14 133 5 144 20 159 ____________________________________ Solution value: 217.852 Execution Time: 1385.24 seconds Gap: 1.50211 % Best Bound: 214.628 Depth: 29 Node: 138660 ____________________________________ Assigned Routes vehicle 1 16 12 1 19 10 27 8 55 18 72 19 78 3 94 12 108 15 119 11 126 4 149 vehicle 2 6 19 2 49 13 55 9 63 7 78 21 88 17 114 14 133 5 144 20 159 Status : 2 Objective Function : 217.852 Total Time : 2730.09 seconds
II.04(02).83
55
Apéndice C
FUNCIONES DE DISTRIBUCIÓN DE PROBABILIDAD
En este apéndice se recopila la información sobre la cual se baso el
autor para la creación de los intervalos de confianza mostrados en el
capitulo V, para cada conjunto de datos se muestra su distribución y el
resultado de la prueba Kolmogorov-Smirnov que ratifica el uso de la
distribución utilizada para esos datos.
Comparación Algoritmo VRP1 y VRP4
Razón entre el Tiempo que demoro el algoritmo VRP1 en encontrar la
primera solución sobre el tiempo que demoro el algoritmo VRP4 en
encontrarla bajo las mismas condiciones
Función de Distribución
Gamma (0.133, 1.3) Número de Datos : 158
Resultado de la Prueba Kolmogorov-Smirnov
II.04(02).83
56
Razón entre el Tiempo que demoro el algoritmo VRP1 en encontrar la
mejor solución sobre el tiempo que demoro el algoritmo VRP4 en
encontrarla bajo las mismas condiciones
Función de Distribución
Exponencial (0.117) Número de Datos : 156
Resultado de la Prueba kolmogorov-Smirnov
Razón entre el Tiempo que demoro el algoritmo VRP1 en terminar de
acotar y determinar optimalidad sobre el tiempo que demoro el algoritmo
VRP4 en hacerlo bajo las mismas condiciones
Función de Distribución
Normal (0.0873, 0.0347) Número de Datos : 156
Resultado de la Prueba Kolmogorov-Smirnov
II.04(02).83
57
Uso del Presolver Global
Razón entre el Tiempo que demoro el algoritmo en encontrar la primera
solución utilizando el Presolver global sobre el tiempo que demoró
cuando no se utilizó bajo las mismas condiciones
Función de Distribución
Exponencial (1.44) Número de Datos : 180
Resultado de la Prueba Kolmogorov-Smirnov
Razón entre el Tiempo valor de la función objetivo encontrado
utilizando el Presolver global sobre el valor hallado cuando no se
utilizó bajo las mismas condiciones
Función de Distribución
Normal (102, 0.139) Número de Datos : 180
II.04(02).83
58
Resultado de la Prueba Kolmogorov-Smirnov
Razón entre el Tiempo que demoro el algoritmo en encontrar la mejor
solución utilizando el Presolver global sobre el tiempo que demoró
cuando no se utilizó bajo las mismas condiciones
Función de Distribución
Lognormal (1.38, 1.56) Número de Datos : 178
Resultado de la Prueba Kolmogorov-Smirnov
Razón entre el Tiempo que demoro el algoritmo en terminar de acotar y
determinar optimalidad utilizando el Presolver global sobre el tiempo
que demoro cuando no se utilizó bajo las mismas condiciones
Función de Distribución
Normal (0.913, 0.317) Número de Datos : 178
II.04(02).83
59
Resultado de la Prueba Kolmogorov-Smirnov
II.04(02).83
60
Estrategia de Selección de Nodos
Razón entre el Tiempo que demoro la mejor estrategia en encontrar la
primera solución sobre el tiempo que demoró la peor bajo las mismas
condiciones
Función de Distribución
Gamma (0.0912, 0.733) Número de Datos : 70
Resultado de la Prueba Kolmogorov-Smirnov
Razón entre el Tiempo que demoro la mejor estrategia en encontrar la
primera solución sobre el tiempo que demoró la segunda mejor bajo las
mismas condiciones
Función de Distribución
Normal (0.796, 0.175) Número de Datos : 70
Resultado de la Prueba Kolmogorov-Smirnov
II.04(02).83
61
Razón entre el valor de la primera solución hallado por la mejor
estrategia sobre el valor encontrado por la peor bajo las mismas
condiciones
Función de Distribución
Normal (0.715, 0.101) Número de Datos : 70
Resultado de la Prueba Kolmogorov-Smirnov
Razón entre el valor de la primera solución hallado por la mejor
estrategia sobre el valor encontrado por la segunda mejor bajo las
mismas condiciones
Función de Distribución
Normal (0.902, 0.0635) Número de Datos : 70
Resultado de la Prueba Kolmogorov-Smirnov
II.04(02).83
62
Razón entre el Tiempo que demoro la mejor estrategia en encontrar la
mejor solución sobre el tiempo que demoró la peor bajo las mismas
condiciones
Función de Distribución
Normal (0.536, 0.198) Número de Datos : 70
Resultado de la Prueba Kolmogorov-Smirnov
Razón entre el Tiempo que demoro la mejor estrategia en encontrar la
mejor solución sobre el tiempo que demoró la segunda mejor bajo las
mismas condiciones
Función de Distribución
Normal (0.616, 0.23) Número de Datos : 70
II.04(02).83
63
Resultado de la Prueba Kolmogorov-Smirnov
Razón entre el Tiempo que demoro la mejor estrategia en terminar de
acotar y definir optimalidad sobre el tiempo que demoró la peor bajo
las mismas condiciones
Función de Distribución
Normal (0.536, 0.198) Número de Datos : 70
Resultado de la Prueba Kolmogorov-Smirnov
Razón entre el Tiempo que demoro la mejor estrategia en terminar de
acotar y definir optimalidad sobre el tiempo que demoró la segunda
mejor bajo las mismas condiciones
Función de Distribución
Normal (0.855, 0.134) Número de Datos : 70
II.04(02).83
64
Resultado de la Prueba Kolmogorov-Smirnov
Uso del Presolver Entero
Razón entre el Tiempo que demoró la mejor estrategia en encontrar la
primera solución sobre el tiempo que demoró la peor bajo las mismas
condiciones
Función de Distribución
Normal (0.564, 0.219) Número de Datos : 88
Resultado de la Prueba Kolmogorov-Smirnov
Razón entre el Tiempo que demoró la mejor estrategia en encontrar la
primera solución sobre el tiempo que demoró la segunda mejor bajo las
mismas condiciones
II.04(02).83
65
Función de Distribución
Beta (2.04, 0.371) Número de Datos : 88
Resultado de la Prueba Kolmogorov-Smirnov
Razón entre el valor de la primera solución hallado por la mejor
estrategia sobre el valor encontrado por la peor bajo las mismas
condiciones
Función de Distribución
Beta (1.94, 0.829) Número de Datos : 88
Resultado de la Prueba Kolmogorov-Smirnov
Razón entre el valor de la primera solución hallado por la mejor
estrategia sobre el valor encontrado por la segunda mejor bajo las
mismas condiciones
II.04(02).83
66
Función de Distribución
Beta (2.36, 0.279) Número de Datos : 88
Resultado de la Prueba Kolmogorov-Smirnov
Razón entre el tiempo que demoró la mejor estrategia en encontrar la
mejor solución sobre el tiempo que demoró la peor bajo las mismas
condiciones
Función de Distribución
Normal (0.421, 0.22) Número de Datos : 88
Resultado de la Prueba Kolmogorov-Smirnov
II.04(02).83
67
Razón entre el tiempo que demoró la mejor estrategia en encontrar la
mejor solución sobre el tiempo que demoró la segunda mejor bajo las
mismas condiciones
Función de Distribución
Normal (0.743, 0.223) Número de Datos : 88
Resultado de la Prueba Kolmogorov-Smirnov
Razón entre el tiempo que demoró la mejor estrategia en terminar de
acotar y definir optimalidad sobre el tiempo que demoró la peor bajo
las mismas condiciones
Función de Distribución
Normal (0.579, 0.161) Número de Datos : 88
Resultado de la Prueba Kolmogorov-Smirnov
II.04(02).83
68
Razón entre el tiempo que demoró la mejor estrategia en terminar de
acotar y definir optimalidad sobre el tiempo que demoró la segunda
mejor bajo las mismas condiciones
Función de Distribución
Normal (0.843, 0.113) Número de Datos : 88
Resultado de la Prueba Kolmogorov-Smirnov
II.04(02).83
69
REFERENCIAS
[1] Toth, P. y Vigo, D. (editores). The vehicle routing
problem. Society for Industrial and Applied Mathematics,
Philadelphia, E.E.U.U., 2002.
[2] Bazaraa, Mokhtar S. Programación lineal y flujo en redes.
Limusa : Grupo Noriega Editores México, Bogotá, 1999.
[3] Winston, Wayne L. Operations research : applications and
algorithms. PWS-Kent Publishing, Boston, E.E.U.U., c1991.
[4] Dash Asociates. Xpress – Optimizer Reference Manual
Release 14. NJ, USA.
[5] J.-F. Cordeau, M. Gendreau, G. Laporte, J.-Y. Potvin and
F. Semet. A Guide to Vehicle Routing Heuristics, Journal
of the Operational Research Society, 53:512-522, 2002.
[6] P. Augerat, J.M. Belenguer, E. Benavent, A. Corberán, D.
Naddef, G. Rinaldi. Computational Results with a Branch
and Cut Code for the Capacitated Vehicle Routing Problem,
Research Report 949-M, Universite Joseph Fourier,
Grenoble, France
[7] Dantzig GB and Ramser JH (1959). The truck dispatching
problem. Mngt Sci 6:80-91.
[8] Canavos, George. Probabilidad y Estadística: Aplicaciones
y Métodos. McGraw Hill, Mexico, 1988.
[9] Dash Asociates. Xpress – Mosel Language Reference Manual
Release 14. NJ, USA.
II.04(02).83
70
[10] Dash Asociates. Xpress – MP Essentials. Second Edition.
NJ, USA.
[11] S.Eilon, C.D.T.Watson-Gandy y N.Christofides
"Distribution management: mathematical modelling and
practical analysis" Griffin, London 1971.
[12] N.Christofides, A.Mingozzi, P.Toth and C.Sandi (eds)
"Combinatorial optimization", John Wiley, Chichester 1979.
[13] U. Blasum and W. Hochstattler, Application of the Branch
and Cut Method to the Vehicle Routing Problem, Zentrum fur
Angewandte Informatik Koln Technical Report zpr2000-386
(2000).
[14] R. Fukasawa, M. Poggi de Aragao, M. Reis, and E. Uchoa,
Robust Branch-and-Cut-and-Price for the Vehicle Routing
Problem, Relatorios de Pesquisa em Engenharia de Producao
RPEP Vol. 3 No. 8 (2003).
[15] J. Lysgaard, A.N. Letchford, and R.W. Eglese, A New
Branch-and-cut Algorithm for Capacitated Vehicle Routing
Problems, submitted to Mathematical Programming (2003).
[16] T.K. Ralphs, L. Kopman, W.R. Pulleyblank, and L.E.
Trotter Jr., On the Capacitated Vehicle Routing Problem,
Mathematical Programming Series B 94 (2003), 343.
[17] K.M. Wenger, Generic Cut Generation Methods for Routing
Problems, Ph.D Dissertation, Institute of Computer
Science, University of Heidelberg (2003).