View
231
Download
1
Category
Preview:
DESCRIPTION
DEMANDA VARIABLE
Citation preview
UNIVERSIDAD DE CHILE
FACULTAD DE CIENCIAS FSICAS Y MATEMTICAS
DEPARTAMENTO DE INGENIERA MATEMTICA
FORMULACIN Y SOLUCIN DE UN PROBLEMA DE RUTEO DE
VEHCULOS CON DEMANDA VARIABLE EN TIEMPO REAL,
TRASBORDOS Y VENTANAS DE TIEMPO
CLAUDIO ANDRS CONTARDO VERA
2005
UNIVERSIDAD DE CHILE
FACULTAD DE CIENCIAS FSICAS Y MATEMTICAS
DEPARTAMENTO DE INGENIERA MATEMTICA
FORMULACIN Y SOLUCIN DE UN PROBLEMA DE RUTEO DE VEHCULOS CON
DEMANDA VARIABLE EN TIEMPO REAL, TRASBORDOS Y VENTANAS DE TIEMPO
CLAUDIO ANDRS CONTARDO VERA
COMISIN EXAMINADORA CALIFICACIONES
NOTA(no) (Letras) FIRMA
PROFESOR GUA
SR. CRISTIN CORTS : .......... ........................................ ....................
PROFESOR CO-GUA
SR. MARTN MATAMALA : .......... ........................................ ....................
PROFESOR INTEGRANTE
SR. ROBERTO COMINETTI : .......... ........................................ ....................
PROFESOR INVITADO
SR. JUAN CARLOS MUOZ : .......... ........................................ ....................
NOTA FINAL EXAMEN DE TTULO : .......... ........................................ ....................
MEMORIA PARA OPTAR AL TTULO DE
INGENIERO CIVIL MATEMTICO
SANTIAGO DE CHILE
JUNIO 2005
RESUMEN DE LA MEMORIA
PARA OPTAR AL TTULO DE
INGENIERO CIVIL MATEMTICO
POR: CLAUDIO CONTARDO VERA.
FECHA: 06 DE JUNIO DE 2005
PROF. GUA: SR. CRISTIN CORTS CARRILLO.
RESUMEN
El objetivo de esta memoria es introducir el concepto de trasbordo al Problema de Recoger
y Dejar Pasajeros, tanto en su formulacin como en algoritmos que lo resuelvan. Este intento
por introducir tal concepto es porque genera una gran flexibilidad en los sistemas de recoger y
dejar pasajeros, cuestin esencial al momento de evaluar un sistema de alta demanda en el que
la rigidez de un sistema sin trasbordos hace poco viable la existencia de tal sistema.
La metodologa usada durante esta memoria es la de adaptar resultados ya descritos por
otros investigadores para sistemas sin trasbordos.
Se har una formulacin detallada del problema de recoger y dejar pasajeros con trasbordos
y ventanas de tiempo. Para ello se han considerado las diversas formulaciones de este problema
en ausencia de trasbordos, y se propone una que junto con introducir el concepto de trasbordo,
generaliza el Problema de Recoger y Dejar Pasajeros. Se presenta una formulacin lineal del
problema y se demuestran propiedades que explican por qu esta formulacin modela de buena
forma el problema en cuestin.
A continuacin se presentan soluciones exactas al problema basadas en el Principio de
Programacin Dinmica y en la Descomposicin de Benders para problemas semi-enteros.
Finalmente se presentan algoritmos heursticos de solucin al problema con demanda es-
ttica, trasbordos y ventanas de tiempo, para culminar con la extensin al caso de demanda
variable en tiempo real, trasbordos y ventanas de tiempo. Se presentan resultados numricos
que muestran las propiedades, ventajas y desventajas de cada uno de los algoritmos.
Agradecimientos
Detrs de esta memoria no hay tan solo un ao y algo ms de trabajo, que es lo que ha
demorado este documento en tomar su forma final. Hay muchas personas, y todas de ellas han
dado lo mejor de s durante mucho tiempo para que esto as sea. Es por eso que me atrevo
a decir que detrs de esta memoria hay varios cientos de aos, muchos kilos de amor, otros
tantos metros de cario y muchos, pero muchos, pascales de comprensin. En estas lneas
quisiera agradecer a una pequea parte de las personas que han participado en mi vida, y por
qu no decirlo, en esta memoria.
A mis padres Ricardo y Liliana, quienes han dedicado los ltimos 26 aos de su vida a
criarme, entregndome valores slidos y principios fundamentales que debieran regir la vida
de cualquier persona de bien.
A mis abuelos Gloria, lvaro, Gladys y Segundo, quienes han dedicado los ltimos 26 aos
de su vida a malcriarme. La suerte de pocos he tenido de poder compartir con ellos cosas tan
lindas y trascendentales en mi vida.
A Vanessa, en quien pude encontrar comprensin incondicional, muchas veces injustificada
de mi parte. Con ella conoc el significado de la palabra amor, y ella conmigo conoci el de la
palabra paciencia.
A mis hermanos Sebastin y Cristbal, quienes me han dado su amor fraternal y han sido
blanco constante de mis descargas emocionales sintetizadas en un buen coscacho o algo por el
estilo.
A mis profesores guas, Cristin y Martn, por sus sabios consejos, gracias a los cuales esta
memoria tom la forma que ahora puede verse. A los profesores de la comisin, Roberto y Juan
Carlos, por dedicar parte importante de su tiempo a escucharme y orientarme en el desarrollo
de esta investigacin.
A mi ta Marta quien ha sido parte importantsima en mi nutricin y flojera. Sin ella hubiese
tenido que ordenar mi pieza y prepararme el almuerzo todos los das.
A Tommy, la bola de pelos que me espera cada da en la casa sin esperar nada de mi parte.
Su amor incondicional, solo comparable al de un buen amigo.
A mis compaeros y amigos con quienes compart mis ltimos aos de estudio. Solo por
nombrar algunos: Pechu, Guatn Sport, Rojo, Pablo Miranda, Cristin Navas, Rodrigo Escu-
dero.
A Conicyt, por su financiamiento a travs del Proyecto Fondecyt 1030700. A la Iniciativa
Cientfica Milenio a travs de sus proyectos en Sistemas Complejos de Ingeniera e Informa-
cin y Aleatoriedad.
Y por ltimo, a mi mismo por ser como soy.
A mi tata lvaro.
ndice General
1 Introduccin 5
1.1 Descripcin del Problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2 Motivacin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3 Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2 Revisin Bibliogrfica 11
2.1 Problemas de Ruteo de Vehculos . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.1.1 Mtodos de Solucin Propuestos . . . . . . . . . . . . . . . . . . . . . 13
2.2 Problema de Recoger y Dejar Pasajeros . . . . . . . . . . . . . . . . . . . . . 17
2.2.1 Mtodos de Solucin Propuestos . . . . . . . . . . . . . . . . . . . . . 19
2.3 Incorporacin de Trasbordos . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3 Formulacin del PDPT 23
3.1 Formulacin Caso Esttico . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.2 Variantes y situaciones especiales . . . . . . . . . . . . . . . . . . . . . . . . 35
3.2.1 Considerar mltiples pasadas por un mismo trasbordo . . . . . . . . . 35
3.2.2 Ventanas de Tiempo . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.2.3 Extensin al Caso Dinmico . . . . . . . . . . . . . . . . . . . . . . . 37
4 Mtodos de Solucin para el PDPT 38
4.1 Mtodos Exactos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
1
NDICE GENERAL 2
4.1.1 Programacin Dinmica . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.1.2 Cortes Combinatoriales de Benders . . . . . . . . . . . . . . . . . . . 48
4.2 Mtodos Heursticos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.2.1 Ventanas de Tiempo y/o Tiempos de Espera y de Viaje . . . . . . . . . 54
4.2.2 Distancia Recorrida por los Vehculos . . . . . . . . . . . . . . . . . . 69
4.2.3 Complementacin con Otros Mtodos . . . . . . . . . . . . . . . . . . 71
4.2.4 Demanda Dinmica . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
5 Resultados 73
5.1 Pruebas de Velocidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
5.2 Pruebas de Calidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
6 Conclusiones e Investigacin Futura 80
A Consideraciones sobre Teora de Grafos 88
A.1 Definiciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
A.2 Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
B Descomposicin de Benders 93
Lista de Figuras
1.1 Ilustracin de Rutas con y sin trasbordo . . . . . . . . . . . . . . . . . . . . . 6
1.2 Red de Ejemplo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.3 Rutas ptimas sin y con trasbordo . . . . . . . . . . . . . . . . . . . . . . . . 9
3.1 Modelacin de un Trasbordo . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4.1 Transiciones posibles de la variable zi . . . . . . . . . . . . . . . . . . . . . . 46
4.2 Rutina de Corte de Rutas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
5.1 Tiempos de CPU para instancias pequeas . . . . . . . . . . . . . . . . . . . . 76
3
Lista de Tablas
5.1 Tiempos de CPU promedios para instancias pequeas . . . . . . . . . . . . . . 75
5.2 Gap Promedios de CCB y HI . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
5.3 Comparativa de la calidad de las soluciones . . . . . . . . . . . . . . . . . . . 78
5.4 Costos promedio entregados por los mtodos HI y Prueba . . . . . . . . . . . 79
4
Captulo 1
Introduccin
5
CAPTULO 1. INTRODUCCIN 6
1.1 Descripcin del Problema
Una empresa de transporte de pasajeros consta de una flota predefinida de m vehculos con
capacidad para Q pasajeros cada uno. As mismo, existe una demanda ubicada en distintos
puntos de la ciudad que desea viajar, cada uno, desde un punto de origen a un punto de destino.
La pregunta que cabe hacerse entonces es, Cul es la manera ptima de rutear los vehculos
con el fin de satisfacer toda la demanda de clientes minimizando cierta funcin objetivo?.
El problema antes descrito es conocido como el Problema de Recoger y Dejar Pasajeros
que ha sido bastante estudiado y para el cual existe gran cantidad de literatura, ya sea para
formularlo como para resolverlo.
Si ahora existen puntos de la ciudad en los cuales los vehculos pueden interactuar entre
ellos traspasndose pasajeros unos a otros (es decir, nodos de transferencia de pasajeros), y
se quiere resolver el mismo problema planteado antes pero con la libertad de permitir a los
vehculos interactuar en los nodos de trasbordo, Se podran obtener mejores soluciones que si
no se considerara esta posibilidad?.
La respuesta a priori debera ser S, ya que una solucin factible para el problema sin
trasbordo es tambin factible para el problema con trasbordos, y por lo tanto se incrementa el
conjunto de soluciones factibles.
R1
R2
(a) Rutas de vehculos SIN trasbordo
T
R1
R2
(b) Rutas de vehculos CON trasbordo
Figura 1.1: Ilustracin de Rutas con y sin trasbordo
Ahora bien, ha quedado claro el concepto de trasbordo, como un nodo especial donde los
vehculos interactan entre s intercambiando pasajeros, sin embargo no hemos dicho nada
CAPTULO 1. INTRODUCCIN 7
acerca de la demanda o de las posibles caractersticas de la funcin objetivo. Para el conoci-
miento de la demanda existen bsicamente dos opciones:
1. Demanda conocida, a la cual llamaremos esttica (porque no vara durante el tiempo en
que el despachador decide el ruteo o durante la evolucin misma del sistema)
2. Demanda variable, aquella que puede variar ya sea durante el tiempo en el cual el despa-
chador decide las rutas o durante el trascurso del ruteo mismo de los vehculos
Ambos casos son igualmente interesantes pues ambas situaciones ocurren en la realidad.
En este estudio se proponen maneras de resolver ambas instancias del problema.
Tambin aparece el concepto de ventanas de tiempo, que corresponde a una restriccin
temporal en la cual los clientes deciden a priori (y por lo tanto es una informacin del sistema)
intervalos de tiempo en los cuales desean ser atendidos. En esta memoria se proponen 2 formas
de incorporar estas restricciones temporales y se analizan sus ventajas y desventajas.
1.2 Motivacin
A continuacin se detalla la notacin que ser utilizada a lo largo del captulo. Ms adelante
esta notacin podr variar segn sean las necesidades y complejidades del problema particular.
Los vehculos se denotarn con la letra k indexados por algn subndice, luego el vehculo
1 ser identificado como k1 y as sucesivamente. Cada vehculo tendr asociado un depot dk j R2. Los clientes se notarn por i y sus nodos origen/destino vendrn dados por el par (i+, i)
donde cada componente tambin es un vector de R2. El trasbordo vendr etiquetado como T .
Sea entonces la siguiente instancia del problema:
2 Vehculos, con depots en las siguientes posiciones
dk1 =(831270
) dk2 =
(274106
)
CAPTULO 1. INTRODUCCIN 8
5 Clientes, con nodos origen/destino definidos por
(1+,1) =((910
775
),(702115
)) (2+,2) =
((541208
),(55894
)) (3+,3) =
((411755
),(916650
)) (4+,4) =
((769542
),( 97767
)) (5+,5) =
(( 236
),(97114
)) 1 Trasbordo, con nodos entrada y salida en
T =(589397
)La ciudad es representada por un cuadrado de 1000x1000 Unidades de Distancia2 [UD2],
como se puede ver en la Figura 1.2.
T
dk2
1+
3
4+
3+4
2+51
2
5+
(0,0)
dk1
Figura 1.2: Red de Ejemplo
Se desea minimizar la distancia (euclidiana) total recorrida por los vehculos desde que
salen del depot hasta que atienden al ltimo nodo.
CAPTULO 1. INTRODUCCIN 9
La Figura 1.3 muestra las rutas ptimas sin y con uso del trasbordo. La optimalidad de estas
rutas puede ser verificada enumerando todas las rutas factibles y quedndose con las de menor
costo.
T
dk1
1+
4+
3+4
2+51
2
5+
(0,0)
dk2
3
(a) Rutas ptimas sin trasbordo
T
dk2
1+
3
4+
3+4
2+51
2
5+
(0,0)
dk1
(b) Rutas ptimas con trasbordo
Figura 1.3: Rutas ptimas sin y con trasbordo
Considerando la funcin objetivo antes descrita, los costos obtenidos para ambas soluciones
son de 3885 [UD] para aquella que no hace uso del trasbordo y de 3796 [UD] para aquella que
s lo hace.
Con esto se evidencia que en este caso existe una ganancia REAL al incorporar la opcin
de hacer trasbordo por parte de los vehculos.
Una vez que se ha comprendido la necesidad de incorporar trasbordos al sistema, obtenien-
do una flexibilidad del mismo que permite potencialmente obtener soluciones de mejor calidad
que para el problema sin trasbordos, es que surgen inmediatamente las preguntas: Cmo for-
mular matemticamente este problema?, Cmo encontrar soluciones al problema de manera
eficiente?
Responder estas preguntas resulta algo no trivial, y contestando a esta necesidad es que
CAPTULO 1. INTRODUCCIN 10
aparece este trabajo de investigacin.
1.3 Objetivos
El objetivo central de esta memoria es presentar un nuevo concepto en sistemas de ruteo de
vehculos puerta a puerta, generalizando el problema de Recoger y Dejar Pasajeros a un nue-
vo problema donde se incorporen trasbordos. Para alcanzar este objetivo de manera clara y
contundente debemos ser capaces de:
1. Entender los alcances y limitaciones del estado del arte en la materia. Para ello se da
cuenta de una vasta revisin bibliogrfica donde se muestra el desarrollo del Problema
de Recoger y Dejar Pasajeros clsico.
2. Formular rigurosamente el Problema de Recoger y Dejar Pasajeros con Trasbordos.
3. Proponer mtodos de solucin del Problema de Recoger y Dejar Pasajeros con Trasbor-
dosy aplicarlos. Comparar los resultados con los obtenidos para el Problema de Recoger
y Dejar Pasajeros clsico.
4. Dar resultados que muestren las ventajas y limitaciones de la formulacin y mtodos de
solucin. Analizar los resultados obtenidos.
5. Concluir segn los resultados obtenidos y proponer otras posibles metodologas que no
han sido implementadas en esta memoria y que podran ser un aporte al conocimiento
del problema
Captulo 2
Revisin Bibliogrfica
11
CAPTULO 2. REVISIN BIBLIOGRFICA 12
Esta revisin bibliogrfica se divide en tres secciones: En la primera seccin se hace refe-
rencia a lo existente en la literatura acerca de Problemas de Ruteo de Vehculos, mencionando
tanto el tipo de problemas que se ha atacado, como sus formulaciones y soluciones propues-
tas por los distintos autores. En la segunda seccin se centrar el anlisis en el Problema de
Recoger y Dejar Pasajeros, se muestran tanto las formulaciones existentes como los distintos
mtodos de solucin propuestos por los autores. Finalmente, se da una breve descripcin de c-
mo antes se ha enfrentado la incorporacin de trasbordos en sistemas de transporte de pasajeros
puerta a puerta.
2.1 Problemas de Ruteo de Vehculos
Para comenzar con esta revisin, es necesario remontarse al ao 1956 cuando Flood (1956)
plantea el Problema del Vendedor Viajero (TSP).
El problema se puede plantear como sigue:
Un vendedor (viajero por cierto) necesita visitar n puntos de la ciudad, sin importar el
orden en que lo haga, cada uno exactamente una vez y en el menor tiempo posible.
En el contexto de lo que se ver ms adelante, podramos decir que el vendedor viajero es
asociable a un operador de un servicio puerta a puerta que debe atender a la demanda ubicada
en la posicin de cada uno de los n nodos que debe visitar.
Luego de la aparicin de el problema del vendedor viajero y de su formulacin, aparece el
Problema de Ruteo de Vehculos (VRP), que es una generalizacin del TSP, y que se enuncia
como sigue:
Se cuenta con una flota de m vehculos cada uno con capacidad Q, y se necesita despachar
carga a n puntos de la ciudad partiendo cada vehculo desde algn depot. Cada uno de los
puntos i tiene asociada una demanda di que debe ser satisfecha por uno y solo uno de los
vehculos.
Dentro de los VRP existen diversas variaciones al modelo original, por ejemplo el Problema
CAPTULO 2. REVISIN BIBLIOGRFICA 13
de Ruteo de Vehculos con Ventanas de Tiempo (VRPTW) en que a cada nodo de demanda i se
le asocia un par de valores (li,ui) que representan un intervalo de tiempo dentro del cual debe
ser atendido el nodo i. Est el Problema de Ruteo de Vehculos con Carga/Descarga (VRPB) en
el cual la demanda se puede dividir en 2 conjuntos B y L, el primero de los nodos de oferta y el
segundo de nodos demanda. cada nodo debe ser visitado una sola vez y por tan solo un vehculo
y se debe satisfacer toda la oferta/demanda de los nodos. Por ltimo tenemos al Problema de
Recoger y Dejar Pasajeros (PDP) en el cual cada cliente i tiene asociado un par origen/destino
(i+, i) donde debe ser recogido/entregado respectivamente. El detalle de estos problemas se
encuentra con mayor profundidad descrito en Toth y Vigo (2002).
2.1.1 Mtodos de Solucin Propuestos
Para resolver distintas instancias del VRP, VRPTW y VRPB se han desarrollado varios algo-
ritmos, que se pueden dividir en mtodos exactos y mtodos aproximados.
Mtodos Exactos
Dentro de los mtodos exactos para resolver el VRP, destacan los algoritmos del tipo Ra-
mificacin y Acotamiento (R&A), Ramificacin y Corte (R&C) y Particin de Conjuntos -
Generacin de Columnas (PC-GC).
Dentro de los algoritmos de tipo R&A, destacan los trabajos de Laporte, Mercure y Nobert
(1986); Fischetti, Toth y Vigo (1994); Fisher (1994). La idea de estos trabajos es la de dar
cotas inferiores a las soluciones de los respectivos problemas, por medio de relajaciones de
las variables enteras o eliminacin de algunas restricciones. Con estas relajaciones se llega a
problemas conocidos en la literatura con soluciones rpidas y que representan cotas para el
valor del problema original.
Laporte et al. (1986) transforma el problema VRP original en un Problema de Transporte
(para el caso asimtrico) o en un Problema de Asignacin (para el caso simtrico) mediante la
relajacin de las variables enteras y la eliminacin de las restricciones de capacidad. Lamen-
CAPTULO 2. REVISIN BIBLIOGRFICA 14
tablemente las cotas obtenidas mediante esta relajacin son muy pobres, obteniendo un gap
promedio entre la cota y la solucin ptima del problema cercana al 9% para el caso asim-
trico y sobre un 30% para el caso simtrico (ver Toth y Vigo 2002). La complejidad de los
mtodos son O(|V |3) y O(|V |2|E|) respectivamente, donde G = (V,E) es el grafo que modelala instancia del problema.
Fischetti et al. (1994) propone dos procedimientos aditivos para calcular cotas inferiores.
Los procedimientos son aditivos en el sentido de que se para la iteracin i-sima se usa como
entrada la salida de la iteracin (i1)-sima y prueba en ambos casos que la suma de las cotasobtenidas son cotas inferiores del VRP. Para uno de los procedimientos se prueba que la cota
obtenida domina a la cota de Laporte et al. (1986), pero se debe pagar un costo computacional
alto (en ambos casos O(n4)). Toth y Vigo (2002) muestra que las cotas obtenidas con este
mtodo son mejores que las obtenidas usando los mtodos de Laporte et al. (1986) tanto para
el caso simtrico como para el asimtrico.
Tanto en los trabajos de Laporte como de Fischetti, las cotas son aplicadas al comienzo del
algoritmo de R&A, y se proponen distintas estrategias de ramificacin.
Los algoritmos de tipo R&C proponen la agregacin de nuevos cortes o desigualdades
vlidas al poltopo factible de soluciones del problema. Las desigualdades propuestas en su
mayora son adaptaciones de cortes vlidos para el TSP simtrico (STSP) (ver Cornujols,
Fonlupt y Naddef 1985; Naddef y Rinaldi 1993). Toth y Vigo (2002) muestran con detalle como
estas desigualdades se pueden aplicar al VRP. Estas desigualdades han mostrado tener bastante
xito en la resolucin de problemas, pero lamentablemente dependen mucho de la estructura
particular del VRP. Otro problema que se ha encontrado es que muchas de las desigualdades
vlidas para este problema son deducibles a partir de la solucin de problemas tan complejos
como el original y se ha necesitado desarrollar heursticas que permitan encontrar cortes de
manera rpida.
Los algoritmos de tipo Particin de Conjuntos - Generacin de Columnas se basan en el
mtodo de descomposicin de Dantzig-Wolfe (Dantzig y Wolfe 1960). La idea clave consiste
CAPTULO 2. REVISIN BIBLIOGRFICA 15
en enumerar todas las rutas factibles para todos los vehculos y resolver el problema de set-
covering asociado. Lamentablemente, como la cantidad factible de rutas es exponencial en el
nmero de nodos es inviable computacionalmente resolver directamente este problema.
Una tcnica para resolverlo consiste en enumerar un set ms pequeo de rutas factibles y
resolver el problema relajado para ese set de rutas ms pequeo. Como una solucin ptima de
este problema no necesariamente es solucin ptima del problema original (el relajado con la
enumeracin de todas las rutas) se usa una tcnica para encontrar rutas que no est consideradas
en el subconjunto de rutas inicial y que bajen el costo de la solucin. Lamentablemente, el
algoritmo para encontrar dichas rutas tambin es difcil computacionalmente (requiere resolver
el TSP eficientemente). Agarwal, Marthur y Salkin (1989); Desrochers, Desrosiers y Solomon
(1992); Bixby, Coullard y Simchi-Levi (1997) desarrollan distintas tcnicas para resolver el
problema de encontrar nuevas rutas.
Otra visin es la de intentar resolver directamente el problema de set-covering mediante
tcnicas de ramificacin y corte (ver Padberg y Rinaldi 1991; Hoffman y Padberg 1993). La
limitacin de estos mtodos es que encuentran la mejor solucin para un set determinado de
rutas elegido a priori, sin embargo no asegura optimalidad en el sentido de encontrar el mnimo
para el set completo de rutas factibles.
Finalmente, Desrochers et al. (1992) resuelven el problema mediante un mtodo de rami-
ficacin y precio en el cual en cada nodo del rbol de bsqueda se generan nuevas columnas y
se agregan al problema. Este mtodo a diferencia de los anteriores asegura optimalidad de las
soluciones.
Mtodos Aproximados
Los mtodos aproximados pueden dividirse en dos grandes grupos. Los mtodos heursticos y
los meta-heursticos. De los primeros podemos mencionar los mtodos de ahorro de tiempo y
los mtodos de insercin, principalmente.
En los mtodos de ahorro de tiempo estn los trabajos de Clarke y Wright (1964); Des-
CAPTULO 2. REVISIN BIBLIOGRFICA 16
rochers y Verhoog (1989); Wark y Holt (1994). Estos mtodos buscan mezclar rutas con un
criterio de pegado entre ellas.
Por ejemplo, Clarke y Wright (1964) computan los ahorros de tiempo de mezclar dos rutas
si se pegan formando una nica ruta. Partiendo con rutas que inicialmente contienen tan solo
un nodo se mezclan rutas hasta que ya no exista forma de ahorrar tiempo mezclando un par de
ellas.
Los mtodos de insercin en cambio, parten con rutas inicialmente vacas (o que contienen
un nico nodo) e iterativamente evalan la mejor forma de insertar un nodo en alguna ruta, y
se quedan con el par (nodo,ruta) que representa la mejor insercin. Dentro de estas heurs-
ticas tenemos los trabajos de Mole y Jameson (1976); Christofides, Mingozzi y Toth (1979);
Solomon (1987).
Dentro de los mtodos metaheursticos estn Recocido Simulado, Recocido Determins-
tico, Bsqueda Tab, Algoritmos Genticos, etc. (ver Toth y Vigo 2002). A diferencia de los
mtodos heursticos clsicos, en un mtodo metaheurstico el algoritmo puede considerar pasar
de una solucin xt a otra xt+1 cuyo costo sea mayor.
Los mtodos de Recocido Simulado funcionan de la siguiente manera:
Durante la iteracin t, se tiene una solucin xt de costo c(xt). Dentro de una vecindadN (xt)
se elige aleatoriamente un miembro x N (xt) de costo c(x). Si c(x)< c(xt) entonces se hacext+1 = x. En caso contrario
xt+1 =
x, con probabilidad pt ,xt , con probabilidad 1 pt . (2.1)donde pt en general es una funcin decreciente en t a valores en [0,1]. En la forma que tenga
pt y el como se definen las vecindades N (x) se encuentran los distintos mtodos propuestos
en la literatura (ver Robust, Daganzo y Souleyrette 1990; Alfa, Heragu y Chen 1991; Osman
1993).
Cuando la aceptacin de una nueva solucin viene dada por un criterio determinstico se
CAPTULO 2. REVISIN BIBLIOGRFICA 17
llama Recocido Determinstico.
Los mtodos de tipo Bsqueda Tab son similares a Recocido Simulado con la diferencia
de que la movida se realiza al mejor vecino x de una solucin xt . Para evitar ciclos se prohbe
que una misma solucin sea revisada ms de una vez durante un cierto nmero de iteraciones.
Uno de los trabajos ms recientes en el tema es el de Barbarosoglu y Ozgur (1999).
2.2 Problema de Recoger y Dejar Pasajeros
El Problema de Recoger y Dejar Pasajeros (PDP) se plantea como una especificacin del VRP.
En este problema se cuenta con una flota de m vehculos y de n clientes. Cada cliente i tiene
asociado un par de nodos (i+, i) que en adelante llamaremos nodos origen y destino del cliente
i, respectivamente. Cada cliente i debe ser recogido en su origen i+ por algn vehculo y luego
ese mismo vehculo1 debe ir a dejarlo a su lugar de destino. El problema se puede plantear
como minimizar cierta cantidad (distancia recorrida por los vehculos, tiempos de viaje/espera
de los clientes, etc.) sujeto a satisfacer la demanda de los n clientes.
Savelsbergh y Sol (1995) formula matemticamente el PDP como un Mixed Integer Pro-
gramming (MIP), como puede verse en la pgina 18.
1Es una de las restricciones que se relajan en la formulacin del Problema de Recoger y Dejar Pasajeros conTrasbordos
CAPTULO 2. REVISIN BIBLIOGRFICA 18
mnx
f (x) (2.2)
s. a. (2.3)
kM
zki = 1 i C (2.4)
jVW
xkl j = jVW
xkjl = zki i C, l {i+, i},k M (2.5)
jV{k}
xkk+ j = 1 k M (2.6)
jV{k+}
xkik = 1 k M (2.7)
Dk+ = 0 k M (2.8)
Di+ 6 Di i C (2.9)
xki j = 1 Di+ ti j 6 D j (i, j) E,k M (2.10)
yk+ = 0 k M (2.11)
yl 6 kM
Qkzki i C, l {i+, i} (2.12)
xki j = 1 yi+qi = y j (i, j) E,k M (2.13)
xki j {0,1} (i, j) E,k M (2.14)
zki {0,1} i C,k M (2.15)
Di,yi > 0 i V (2.16)
Para representar el problema se usan cuatro tipos de variables: xki j con (i, j) E,k Mdonde E es el conjunto de nodos del grafo y M el conjunto de vehculos. Estas variables son
binarias e iguales a 1 si el vehculo k usa el arco (i, j), 0 en caso contrario. zki igual a 1 si
el cliente i C es asignado al vehculo k, 0 en caso contrario. Di con i V variable realrepresentando el tiempo en que el nodo i es atendido. yi variable real representando la carga del
vehculo que atiende al nodo i al llegar a l. Se tienen constantes ti j representando el tiempo de
viaje entre i y j, qi representando la carga (o cantidad de pasajeros) asociados al cliente i y Qk
CAPTULO 2. REVISIN BIBLIOGRFICA 19
la capacidad del vehculo k.
La restriccin (2.4) asegura de que cada cliente sea asociado a un nico vehculo. La restric-
cin (2.5) se preocupa que un nico vehculo pase por los nodos origen/destino de un cliente,
y que tal vehculo sea el que tiene asociado a tal cliente. Las restricciones (2.6)-(2.7) ase-
guran que todo vehculo sale de su depot origen y llega a su depot destino. Las restricciones
(2.8)-(2.10) relacionan los viajes de los vehculos con la precedencia en tiempo de los nodos vi-
sitados por cada uno. Las restricciones (2.11)-(2.13) relacionan los viajes con la carga/descarga
de los vehculos. Las restricciones (2.14)-(2.16) determinan la naturaleza entera o real de las
variables.
Las restricciones definidas por una proposicin lgica p q pueden escribirse usando elmtodo Big-M.
2.2.1 Mtodos de Solucin Propuestos
Al igual que en la seccin anterior, los mtodos existentes en la literatura son tanto exactos y
aproximados.
Mtodos Exactos
Psaraftis (1980, 1983); Desrosiers, Dumas y Soumis (1986) plantean algoritmos de progra-
macin dinmica para resolver el Problema de Recoger y Dejar Pasajeros. Psaraftis (1983);
Desrosiers et al. (1986) resuelven minimizando la distancia total recorrida por los vehculos
considerando ventanas de tiempo duras, mientras que Psaraftis (1980) considera la insatisfac-
cin a los usuarios sin ventanas de tiempo. Estos algoritmos definen estados del sistema y las
funciones costo de la transicin para pasar de un estado a otro.
Por ejemplo Psaraftis (1983) resuelve el Problema de Recoger y Dejar Pasajeros con Ven-
tanas de Tiempo para 1 vehculo con ventanas de tiempo duras y resuelve para la distancia re-
corrida por los vehculos. Para ello define los estados del sistema como la posicin del vehculo
L y los estados de los clientes ki (1 si aun estn esperando, 2 si estn sobre el vehculo y 3 si
CAPTULO 2. REVISIN BIBLIOGRFICA 20
ya han sido entregados en su destino). define las transiciones como los posibles lugares L a los
cuales se puede ir desde L ya sea para ir a buscar a un cliente que an no ha sido recogido o
para ir a dejar a un cliente a bordo.
Desrosiers et al. (1986) tambin resuelven el Problema de Recoger y Dejar Pasajeros para
1 vehculo. Definen los estados como (S, i) y dicen que tal estado es factible si existe una ruta
que pase por todos los nodos en S y termine en i. Basado en esta definicin, proponen una
tcnica para reducir el espacio de los estados factibles. Son capaces de resolver instancias de
hasta 40 clientes.
Dumas, Desrosiers y Soumis (1991) proponen un mtodo de generacin de columnas para
resolver el Problema de Recoger y Dejar Pasajeros con Ventanas de Tiempo, usando la descom-
posicin de Dantzig-Wolfe. Lo que hacen en trminos generales es definir las columnas como
rutas de vehculos. Se reporta en Toth y Vigo (2002) que son capaces de resolver instancias de
hasta 50 clientes.
Ruland y Rodin (1997) formulan el Problema de Recoger y Dejar Pasajeros como un MIP
y estudian la estructura poliedral del poltopo que se define. Dan como resultado 4 tipos de
desigualdades vlidas para el Problema de Recoger y Dejar Pasajeros basndose en el TSP
con restricciones de precedencia. Mediante el mtodo de ramificacin y corte que proponen
son capaces de resolver instancias de hasta 15 clientes.
Lu y Dessouky (2004) en el trabajo ms reciente que se reporta en la literatura para resolver
el Problema de Recoger y Dejar Pasajeros con Ventanas de Tiempo, formulan el problema mul-
tivehculo con ventanas de tiempo blandas como un MIP y proponen 4 tipo de desigualdades
vlidas para el problema, proponen tambin un mtodo para la ramificacin de las variables
0-1, todo esto enmarcado en la resolucin por medio de un mtodo de ramificacin y corte.
Logran resolver instancias de hasta 17 clientes en un tiempo de 3 horas.
Mtodos Aproximados
Sexton y Bodin (1985a,b) proponen un mtodo heurstico basado en la descomposicin de
CAPTULO 2. REVISIN BIBLIOGRFICA 21
Benders Benders (1962) del Problema de Recoger y Dejar Pasajeros. Ellos minimizan la de-
sutilidad de los pasajeros y descomponen el problema en un problema de ruteo con variables
binarias y en cada subproblema resuelven un problema de scheduling.
Jaw, Odoni, Psaraftis y Wilson (1986) resuelven el Problema de Recoger y Dejar Pasajeros
con Ventanas de Tiempo (duras) mediante una heurstica de insercin. En el problema que
ellos resuelven, un cliente especifica una hora deseada para su recogida o dejada (pero no para
ambas), una ventana temporal que acota la llegada a tal nodo, y el tiempo de viaje es acotado
como funcin del tiempo de viaje directo desde el origen hacia el destino. En este contexto, las
ventanas que consideran son duras, y cualquier insercin que no satisfaga estas condiciones se
considera infactible.
Cullen, Jarvis y Ratliff (1981) por primera vez introducen el concepto de cluster para el
Problema de Recoger y Dejar Pasajeros, o ventana espacial donde clientes cercanos se asocian
a un mismo cluster y se limita su atencin a un subconjunto de vehculos determinado para
atender tal cluster. El gran problema que presentan los clusters es que un mismo cliente cuyo
par origen/destino est distanciado debera estar en 1 solo cluster. Recogiendo esta inquietud
Dumas, Desrosiers y Soumis (1989) propone la incorporacin demini-clusters donde un cluster
representa una regin asimilable a un segmento de ruta.
2.3 Incorporacin de Trasbordos
La inclusin de trasbordos en operaciones de este tipo ha sido tratada en la literatura con an-
terioridad. Sorprendentemente, no existe una formulacin estricta del Problema de Recoger y
Dejar Pasajeros con Trasbordos basndose en el problema original sin trasbordos, ms bien
se proponen formas de operacin a priori, y se optimizan etapas del viaje, o bien, se optimiza
la operacin dentro de zonas alimentadoras, y se coordina la operacin en los trasbordos con
lneas troncales de ruta fija. Podemos encontrar muchos trabajos donde se trata la operacin
eficiente de los nodos de trasbordo. Corts y Jayakrishnan (2005) hacen una completa revisin
CAPTULO 2. REVISIN BIBLIOGRFICA 22
de la operacin en trasbordos y proponen un mtodo heurstico para optimizar la asignacin
vehculo-pasajero en los puntos de trasbordos, esencialmente para problemas dinmicos con
decisiones tomadas en tiempo real. Recientemente, los trabajos de Malucelli, Nonato y Pa-
llottino (1999) y Crainic, Malucelli y Nonato (2001), proponen y formulan la operacin de
sistemas ms flexibles basados en servicios alimentadores conectados con lneas troncales, ba-
sndose en las ideas de Schneider y Smith (1981). Horn (2002b,a) proponen una interesante
heurstica para resolver problemas con trasbordo, pero entre diferentes modos.
Captulo 3
Formulacin del Problema de Recoger y
Dejar Pasajeros con Trasbordos
23
CAPTULO 3. FORMULACIN DEL PDPT 24
3.1 Formulacin Caso Esttico
En el Problema de Recoger y Dejar Pasajeros se cuenta con una flota de vehculos y un con-
junto de clientes definidos a priori, y cada uno de esos clientes han especificado un origen y un
destino para su viaje. Se pueden distinguir los siguientes conjuntos
N = {1, . . . ,n} Conjunto de Nodos asociados a Clientes
M = {1, . . . ,m} Conjunto de Vehculos
M+ = {1, . . . ,m+} Depots Origen de Vehculos
M = {1, . . . ,m} Depots Destino de Vehculos
C = {1, . . . ,nC} Conjunto de Clientes
(PDP1)
Existen tambin funciones + :C N y :C N inyectivas, tales que
i. C+C =
ii. C+C = N
A cada i C se le asocia i+ como el nodo origen del cliente i, y i como su nodo destino.Para cada k M, existen funciones + :MM+, :MM, y se dice que k+,k son
los depot origen y destino respectivamente del vehculo k.
A partir de lo anterior se puede considerar el siguiente grafo G = (V ,E ) definido como
V = NM+M
E = {(i, j) : i M+, j C+}{(i, j) : i, j N, i 6= j}{(i, j) : i C, j M}
El problema de encontrar rutas Rk, k M tales que se pasen a recoger todos los clientesy luego se pasen a dejar, es conocido como Problema de Recoger y Dejar Pasajeros. Este
CAPTULO 3. FORMULACIN DEL PDPT 25
problema al ser formulado exige que un vehculo que vaya a buscar a un cliente i C a suorigen i+ deba luego ir a dejarlo a su lugar de destino i.
Si a los conjuntos anteriormente definidos se agrega
T = {1, . . .nT} Conjunto de Trasbordos (3.1)
y a cada r T se le asocia un par de nodos (e(r),s(r)) y se puede definir el grafoG= (V,E)como
V =V e(T ) s(T )
E =E {(i,e(r)) : r T, i M+N}{(e(r),s(r)) : r T}
{(s(r), j) : j NM}{(s(r),e(t)) : r, t T, r 6= t}
La razn por la cual se debe definir para cada trasbordo r T el par de nodos e(r),s(r)(ver Figura 3.1) es porque en un trasbordo cada vehculo realiza 2 tipos de acciones: En primer
lugar deja pasajeros (para que otros vehculos se los lleven) y en segundo lugar, en una etapa
posterior, recoge pasajeros. Para poder diferenciar estas acciones llevadas a cabo dentro del
trasbordo por la totalidad de los vehculos y saber quin se baja de tal o cual vehculo y quin
se sube a tal o cual otro, es que se necesita dividir el trasbordo real en 2 nodos dentro del
modelo que se propone.
Finalmente, se suponen conocidos los costos de usar los distintos arcos de la red, denotados
por (ti j)(i, j)E . Se supone que los costos ti j son tales que en el grafo no existen ciclos de tiempo
01.
Se define entonces el Problema de Recoger y Dejar Pasajeros con Trasbordos como el
problema de encontrar rutas Rk en el grafo G = (V,E) tales que se pase a buscar a todos los
pasajeros a su lugar de origen y luego a dejar a su lugar de destino.
1En general, casi todos los ti j son mayores que 0, pues incluso entre nodos cuyo costo de viaje sea 0, existeun costo (en tiempo) de realizar alguna accin en el nodo i. Si an persisten ciclos de largo 0, stos se puedeneliminar usando restricciones de eliminacin de subtours
CAPTULO 3. FORMULACIN DEL PDPT 26
La formulacin que se presentar en esta memoria puede escribirse como un Problema de
Programacin Entera Mixta de la forma
mn f (x,D,z) (3.2)
s.a.
Ax6 a (3.3)
Bx+CD6 b (3.4)
Ex+Fz6 c (3.5)
GD+Hz6 d (3.6)
x {0,1}n (3.7)
D,z> 0 (3.8)
Las variables x definen el conjunto de rutas de los |M| vehculos, como en el problemade recoger y dejar pasajeros clsico (Savelsbergh y Sol 1995). Las variables D entregan la
informacin temporal, asociadas al momento en que los nodos son visitados. Estas variables
son tpicas tambin en la formulacin del problema de recoger y dejar pasajeros clsico. En esta
formulacin sin embargo, se agregan las variables z que entregan informacin respecto de la
carga de los vehculos y su identificacin en trminos de pasajeros. Estas variables no aparecen
en el problema de recoger y dejar pasajeros tradicional, y bsicamente se justifican dado que en
el caso con trasbordos es relevante saber qu clientes estn sobre los vehculos al momento de
llegar al trasbordo para poder realizar el intercambio. La forma en que se relacionan estos tipos
r
(a) Trasbordo Real
te(r)s(r)e(r) s(r)
(b) Trasbordo Modelado
Figura 3.1: Modelacin de un Trasbordo
CAPTULO 3. FORMULACIN DEL PDPT 27
de variables se puede resumir en las restricciones (3.3) a (3.6). En adelante, describiremos e
interpretaremos los distintos tipos de relaciones que aparecen aqu, dando argumentos tambin
para construir las posibles representaciones de dependiendo del tipo de objetivo que se quiera
optimizar.
La formulacin propuesta deber satisfacer las siguientes propiedades
a) Para cada vehculo k M existe una ruta Rk que parte en k+, termina en k y no contieneciclos.
b) Todos los nodos en N son visitados por algn vehculo.
c) El nodo origen de un cliente siempre es visitado antes que su nodo de destino.
d) Si un cliente hace trasbordo en r T , digamos del vehculo k1 al k2, entonces el vehculok2 deja el trasbordo despus de que k1 haya llegado.
Las condiciones (a)-(d) son bsicas y fundamentales en la definicin operativa del proble-
ma, y por eso se debe ser cuidadoso en formular las restricciones apropiadas para representar-
las.
Se define la variable binaria xki j que vale 1 si el vehculo k M usa el arco (i, j) E, 0 encaso contrario. El siguiente conjunto de restricciones define k pseudo-rutas de vehculos, cada
una de ellas comenzando en el depot origen del vehculo correspondiente, y terminando en el
depot destino del vehculo.
CAPTULO 3. FORMULACIN DEL PDPT 28
{i|(k+,i)E}
xkk+i = 1 k M (3.9)
{i|(i,k)E}
xkik = 1 k M (3.10)
mM+
{iV :(m,i)E}
xkmi 6 1 k M (3.11)
{ j|(i, j)E}
xki j { j|( j,i)E}
xkji = 0 i N, k M (3.12)
{i|(i,e(r))E}
xkie(r) = xke(r)s(r) r T, k M (3.13)
{ j|(s(r), j)E}
xks(r) j = xke(r)s(r) r T, k M (3.14)
Las ecuaciones (3.9) y (3.10) aseguran que cada vehculo salga de su respectivo depot
origen y llegue a su respectivo depot destino. La ecuacin (3.11) asegura que un vehculo no
pueda comenzar dos rutas desde depot distintos. La ecuacin (3.12) es de conservacin de
flujo en los nodos de N. Las ecuaciones (3.13) y (3.14) muestran la conservacin de flujo en
los nodos de trasbordo. En conjunto estas restricciones definen para cada vehculo k M, rutasque parten en k+, terminan en k y (eventualmente) contienen ciclos. Para formalizar esto
ltimo es necesaria la siguiente proposicin
Proposicin 3.1.1. Sea (xki j)kM(i, j)E satisfaciendo las restricciones (3.9)-(3.14). Sea E
k = {(i, j)E : xki j = 1} el conjunto de arcos que usa el vehculo k, y Gk = G[Ek] el grafo inducido2 poresos arcos. Entonces Gk contiene una ruta de k+ a k.
Demostracin. Por conveniencia notacional definamos V k :=V (Gk).
SeaMk+ =M+V k,Mk =MV k, Nk =V k\(M+M). Probemos que para dichos con-juntos se cumplen las propiedades (A.2)-(A.4) de la pgina 90. Con esto ms la Proposicin
A.2.2 se concluye el resultado.
Sea v Mk+, es decir d+Gk(v) > 0 o bien dGk(v) > 0, y como dG (v) = 0 se tiene (A.2). Sea
2ver definicin en pgina 89.
CAPTULO 3. FORMULACIN DEL PDPT 29
w Mk, es decir d+Gk(w) > 0 o bien dGk(w) > 0, y como d+G (w) = 0 se tiene (A.3). La pro-piedad (A.4) se tiene por la conservacin de flujo en los nodos de Ne(T ) s(T ) dada por lasrestricciones (3.12)-(3.14). Las restricciones (3.9) y (3.10) implican que k+ Mk+, k Mk.Luego la Proposicin A.2.2 dice que existe (al menos) una ruta de k+ a Mk y una de Mk+ a
k. Si no existiera una ruta de k+ a k en este grafo Gk, entonces se tendra que la ruta deMk+
a k parte en otro nodo k+ 6= k+, con lo que se violara la restriccin (3.11).
El conjunto de restricciones antes descrito no asegura que se cumpla la propiedad (b). Para
ello agregamos las siguientes restricciones
kM
{ j|( j,i)E}
xkji = 1 i C (3.15)
kM
{ j|(i+, j)E}
xki+ j = 1 i C (3.16)
La ecuacin (3.15) obliga a que exactamente 1 vehculo pase por el nodo destino del cliente
i, mientras que la ecuacin (3.16) obliga a que se haga lo mismo con su nodo de origen. Ac
tenemos la primera gran diferencia con el problema de recoger y dejar pasajeros clsico, en
el cual un mismo vehculo debe atender tanto al nodo origen como al nodo de destino de un
cliente. En esta nueva formulacin, el par origen-destino de un cliente puede ser atendido por
dos vehculos distintos. Las ecuaciones (3.9) a (3.16) representan en detalle la relacin entre
variables x, tal como se muestra genricamente en ecuacin (3.3).
Las restricciones (3.9)-(3.16) generan para cada vehculo k M una ruta Rk que une los pa-res k+,k + ciclos simples3. Para formalizar esta aseveracin se tiene la siguiente proposicin
Proposicin 3.1.2. Sea (xki j)kM(i, j)E satisfaciendo las restricciones (3.9)-(3.14). Sea k M. En-
tonces el grafo Gk (definido en la proposicin anterior) est compuesto por una ruta de k+ a
k + ciclos simples.
3Para la definicin de ciclo simple ver pgina 90.
CAPTULO 3. FORMULACIN DEL PDPT 30
Demostracin. En efecto, sabemos de la proposicin anterior que se satisfacen las propiedades
(A.2) y (A.3). De las restricciones (3.15) y (3.16) se tiene que d+Gk(v) = dGk(v) = 1 v Nk,
con lo que se satisface la propiedad (A.5). Luego por la Proposicin A.2.3 se tiene que 1)
Todo camino de Mk+ a Mk es simple, 2) Todo nodo que no est en algn camino de Mk+ a
Mk pertenece a un ciclo simple, y 3) Todo camino de Mk+ a Mk no admite bifurcaciones.
Consideremos todos los caminos (simples) que van de Mk+ a Mk. En primer lugar veamos
que hay un nico camino de k+ a k. En efecto, por la restriccin (3.11) necesariamente si
tiene que el nuevo camino debe comenzar con el mismo arco que el otro camino. Como los
caminos no admiten bifurcaciones (arcos que salgan de algn nodo del camino hacia otro lado)
luego tal camino termina en k. AdemsMk+ = {k+} tambin por la restriccin (3.11). Sea uncamino de k+ a Mk. Tal camino parte con el mismo arco que el camino de k+ a k, y como
no se admiten bifurcaciones entonces tal camino termina en Mk, por lo que se concluye que
Mk = {k} (pues para todo k Mk existe un camino que parte en k+ y llega a l). Todoslos dems nodos estn en ciclos simples, con lo que se concluye la proposicin.
Para poder eliminar los ciclos y poder asegurar el cumplimiento de la propiedad (a) defini-
mos el siguiente conjunto de variables reales positivas
Di: Tiempo en que es atendido el nodo i NDke(r): Tiempo en que el vehculo k M llega al trasbordo r T .
Dks(r): Tiempo en que el vehculo k M sale del trasbordo r T .
CAPTULO 3. FORMULACIN DEL PDPT 31
Y se imponen las siguientes restricciones
xkk+i+ = 1 tk+i+ 6 Di+ k M,i C (3.17)
xkk+e(r) = 1 tk+e(r) 6 Dke(r) k M,i C (3.18)
xki j = 1 Di+ ti j 6 D j k M,i, j N (3.19)
xkie(r) = 1 Di+ tie(r) 6 Dke(r) k M,i N,r T (3.20)
xke(r)s(r) = 1 Dke(r)+ te(r)s(r) 6 Dks(r) k M,r T (3.21)
xks(r) j = 1 Dks(r)+ ts(r) j 6 D j k M, j N,r T (3.22)
xks(r)e(t) = 1 Dks(r)+ ts(r)e(t) 6 Dke(t) k M,r T,t T\{r} (3.23)
Estas restricciones eliminan los ciclos de largo positivo, pues en caso de que exista alguno
Ck = (c1, . . . ,cn = c1) en el grafo Gk, entonces 1) si c1 N Ck Dc1 < Dcn; 2) si c1 (e(T ) (T ))Ck Dkc1 < Dkcn .
Las restricciones que hay hasta ahora aseguran que efectivamente existan k M rutas Rkque parten en k+, terminan en k, y en conjunto pasan por todos los nodos de N, con lo cual se
cumplen las propiedades (a) y (b).
Para poder satisfacer las propiedades (c) y (d) se necesita definir variables adicionales. Las
variables que se proponen para poder completar la formulacin representan la carga dentro de
los vehculos, llevando la historia de qu clientes van en qu vehculos mientras estos ltimos
hacen su ruta.
zkij : 1 si el cliente i C est en el vehculo k M cuando ste llega al nodo j V . En casocontrario vale 0.
Las restricciones que se agregan son
CAPTULO 3. FORMULACIN DEL PDPT 32
zkik+ = zkik = 0 k M, i C (3.24)
xkl j = 1 zkil = zkij i C, (l, j) E\{(e(r),s(r))|r T} tq l 6= i+, i (3.25)
xki+ j = 1 zkij = 1 i C, j tq (i+, j) E (3.26)
xki j = 1 zkij = 0 i C, j tq (i, j) E (3.27)
kM
zkie(r) kM
zkis(r) = 0 r T, i C (3.28)
rT
kM
zkie(r) 6 1 i C (3.29)
{l|(l, j)E}
xkl j = 0iC
zkij 6 0 k M, j V\{k+,k} (3.30)
La restriccin (3.24) asegura que los vehculos parten y terminan vacos en sus depot origen
y destino. La restriccin (3.25) dice que los clientes no se suben ni se bajan en un nodo, si no
es ni su nodo origen ni su nodo destino. La restriccin (3.26) (resp.(3.27)) establece que los
clientes se suben (resp. bajan) al (resp. del) vehculo que pasa por el nodo origen (resp. destino).
La restriccin (3.28) asegura que los clientes que llegan al trasbordo en algn vehculo deban
luego dejarlo en algn otro (eventualmente el mismo). La restriccin (3.29) permite que cada
cliente pueda hacer trasbordo a lo ms una vez4. Finalmente la restriccin (3.30) seala que si
es igual a 1 entonces el vehculo k pasa por el nodo .
Como consecuencia de lo anterior, si tanto el origen como el destino de un cliente i estn
en la ruta del vehculo k, entonces el nodo i+ siempre es visitado antes que i. En efecto,
consideremos al vehculo que recoge al cliente i, y supongamos que visita el nodo i antes de
visitar i+. Al no poder pasar nuevamente por el nodo i por la restriccin (3.15) entonces el
vehculo termina su ruta con el cliente i en su interior, lo que es imposible por la restriccin
(3.24). Para el caso en que el cliente hace trasbordo necesitamos que se satisfaga la propiedad
(d).
4Esta restriccin puede escribirse ms generalmente como rT kM zkie(r) 6 L, donde L es el nmero mximode veces que un cliente puede trasbordar. En sistemas reales se usa L = 1 para poder ofrecer un buen nivel deservicio a los pasajeros.
CAPTULO 3. FORMULACIN DEL PDPT 33
Adems, notar que como consecuencia de la forma en que se ligan las variables x con z,
estas ltimas pueden relajarse para restringirlas en el intervalo [0,1].
Con las restricciones antes descritas no se satisface necesariamente la propiedad (d), luego
se agrega la siguiente restriccin (restriccin (3.6) en el problema sinttico)
zkie(r)+ zvis(r) = 2 Dke(r)+6 Dvs(r) r T,k,v M,i C (3.31)
donde > 0 es una constante que representa el tiempo que los pasajeros necesitan para
abordar un nuevo vehculo luego de haber llegado al trasbordo. La lectura de esta restriccin
es exactamente lo que en palabras se pide para cumplir la propiedad (d).
Faltara ver que se cumpla la propiedad (c) en el caso general en que los nodos origen y
destino de un cliente estn en rutas distintas. Supongamos que el nodo i+ est en la ruta del
vehculo k e i est en la ruta del vehculo l. Por las restricciones (3.25) y (3.26) para todos los
nodos j siguientes a i+ se tiene zkij = 1 a menos que antes el vehculo pase por un trasbordo.
Si nunca pasa por un trasbordo, entonces el vehculo termina su ruta con el cliente i en su
interior lo que no es posible por la restriccin (3.24). Luego el vehculo pasa por el trasbordo
y el cliente es recogido por algn vehculo que sale del trasbordo con el cliente i en su interior.
Este vehculo debe ser l pues en caso contrario el vehculo debe volver a pasar a un trasbordo,
para que el vehculo l recoja al cliente i, lo que es imposible por la restriccin (3.29). Luego es
el vehculo l el que recoge al cliente i, e i est en la ruta del vehculo l despus del trasbordo,
pues si as no fuera, entonces el vehculo l llega a su depot destino con el cliente i en su interior
lo que es imposible por la restriccin (3.24). Las restricciones (3.17)-(3.23) y (3.31) aseguran
que Di+ < Di .
Hasta ahora, si se tiene una tupla (x,D,z) que satisfaga (3.9)-(3.31), se pueden identificar
|M| rutas que en su totalidad satisfacen las condiciones (a)-(d), con lo que el Problema deRecoger y Dejar Pasajeros con Trasbordos puede considerarse formulado exitosamente, sin
embargo hay restricciones adicionales que se deben agregar con el fin de representar de mejor
CAPTULO 3. FORMULACIN DEL PDPT 34
manera el sistema. Una de ellas es la restriccin de capacidad, que se escribe
iC
zkij 6 Qk k M, j V (3.32)
donde Qk es la capacidad del vehculo k.
de este modo, se ha logrado formular exitosamente el Problema de Recoger y Dejar Pa-
sajeros con Trasbordos como en (3.1), con la salvedad de que nada se ha dicho acerca de
f (x,D,z).
Con las variables del problema, es directo plantear dos tipos de funciones objetivos clsicas
en cualquier Problema de Recoger y Dejar Pasajeros, como son la distancia total recorrida por
los vehculos (DRV), el tiempo de espera de los clientes (TEC) y el tiempo de viaje de los
clientes (TVC).
kM
(i, j)E
ti jxki j (DRV)
iC
Di+ (TEC)
iC
(DiDi+) (TVC)
Estas cantidades, si bien son las ms usadas en la literatura, no son las nicas que pueden
escribirse en trminos de las variables del problema. La informacin entregada por las variables
z permite incluir cantidades relacionadas a ocupacin de los vehculos, nmero de paradas he-
chas por los vehculos y los clientes, por nombrar algunas. A continuacin se muestran algunas
cantidades que pueden ser incluidas en el problema mediante restricciones lineales.
CAPTULO 3. FORMULACIN DEL PDPT 35
jV
zkij : # de paradas que hace el vehculo k con el cliente i en su interior. (3.33)
kM
zkij : # de vehculos que llegan al nodo j con el cliente i en su interior. (3.34)
iC
zkij : # de clientes que llegan al nodo j en el vehculo k. (3.35)
jVkM
zkij : # total de paradas que hace el cliente i. (3.36)
jViC
zkij : # total de carga asignada al vehculo k. (3.37)
iCkM
zkij : # total de clientes que llegan al nodo j. (3.38)
3.2 Variantes y situaciones especiales
Hasta ahora, el problema que hemos resuelto permite una flexibilidad total del sistema. Sin em-
bargo, preguntas como cmo considerar la inclusin de ventanas de tiempo?, cmo permitir
que un trasbordo pueda ser usado ms de una vez por cada vehculo? son preguntas que vale la
pena hacerse y a las cuales damos una alternativa de respuesta en esta seccin.
3.2.1 Considerar mltiples pasadas por un mismo trasbordo
Hasta el momento la formulacin solo permite que cada vehculo pase a lo ms una vez por un
trasbordo. Esta restriccin debiera ser relajada si queremos flexibilizar el sistema permitiendo
que sea una variable de decisin el nmero de veces que un vehculo debe pasar por un mismo
trasbordo.
Supongamos que permitiremos a los vehculos pasar un mximo de MT veces por un mis-
mo trasbordo.
Para cada r T definimos nodos e(r1), . . . ,e(rMT ), s(r1), . . . ,s(rMT ), y permitimos los ar-cos (e(ri),s(ri))i = 1, . . . ,MT , (s(ri),e(r j)) j 6= i. Adems si en el problema original existe el
CAPTULO 3. FORMULACIN DEL PDPT 36
arco ( j,e(r)) en el nuevo grafo agregamos los arcos ( j,e(ri)) para i = 1, . . . ,MT , y para cada
arco (s(r), j) agregamos los arcos (s(ri), j) para i= 1, . . . ,MT .
De esta forma hemos conseguido permitir que cada vehculo pase a lo ms un nmero MT
de veces por cada trasbordo r T .
3.2.2 Ventanas de Tiempo
Puede ocurrir que los clientes tengan asociados intervalos de tiempo deseados en los cuales
un vehculo puede pasar a buscarlos y/o a dejarlos a su lugar de origen o destino. En trminos
de las variables del problema, esto puede escribirse como que las siguientes restricciones son
vlidas
li 6 Di 6 ui (3.39)
Esencialmente existen 2 formas en que se puede agregar dicha restriccin
Como restricciones DURAS , es decir no se permite bajo ningn caso que los nodos sean
visitados fuera de las ventanas de tiempo definidas a priori. Se agregan las restricciones
(3.39) a la formulacin i N
Como restricciones BLANDAS , es decir, se permite la violacin de las ventanas de tiempo
pero se penalizan dichas violaciones en la funcin objetivo. Ms precisamente, se definen
nuevas variables i,i, i N y se agregan restricciones
i > Diui i N (3.40)
i > liDi i N (3.41)
i,i > 0 i N (3.42)
CAPTULO 3. FORMULACIN DEL PDPT 37
y a la funcin objetivo se agregan penalidades de la forma
iN
(Uii+Lii) (3.43)
de forma de intentar minimizar la violacin de las ventanas de tiempo.
La gran ventaja que tienen las restricciones blandas por sobre las duras, es que se gana
factibilidad en el problema con un pequeo trade-off que significa agregar nuevas variables
(variables reales).
3.2.3 Extensin al Caso Dinmico
Sean R1, . . . ,Rm rutas representando la solucin de una instancia del Problema de Recoger y
Dejar Pasajeros con Trasbordos para conjuntos C,N,M,T , y funciones e,s,+,. Sea G =(V,E) el grafo que representa la red del problema.
En cierto instante surge la necesidad de atender un nuevo cliente n+1. Se agrega entonces
un par de nodos (n+1)+,(n+1) al conjunto N inicial y con ello se considera el grafo G =
(V ,E) que es la extensin del grafo G cuando se agregan estos dos nodos.
Se tiene que en el instante en que se debe decidir cmo atender la llamada, los vehculos se
han ruteado de tal manera de que algunas variables xki j, Di, Dkie(r), D
kis(r), z
kij ya se han seteado
sin posibilidad de poder ser re-decididas.
La solucin del nuevo problema ser equivalente a resolver el problema modificado en el
nuevo grafo G .
Sin embargo, sta no es la nica forma de resolver el Problema de Recoger y Dejar Pasa-
jeros con Trasbordos con demanda dinmica, y es tan difcil de hacerlo como lo es resolver el
problema esttico. En la seccin 4.2 se presentan mtodos heursticos de insercin que permi-
ten resolver este problema de manera eficiente.
Captulo 4
Mtodos de Solucin Para el Problema de
Recoger y Dejar Pasajeros con Trasbordos
38
CAPTULO 4. MTODOS DE SOLUCIN PARA EL PDPT 39
4.1 Mtodos Exactos
4.1.1 Programacin Dinmica
En esta seccin se introduce un algoritmo de solucin para el Problema de Recoger y Dejar
Pasajeros con Trasbordos basado en el principio de programacin dinmica. Otras implemen-
taciones del algoritmo de Programacin Dinmica para resolver el Problema de Recoger y
Dejar Pasajeros y el Problema de Recoger y Dejar Pasajeros con Ventanas de Tiempo son las
desarrolladas por Psaraftis (1980, 1983) y Desrosiers et al. (1986).
Sea C el conjunto de clientes y V el conjunto de nodos de la red. Sea M el conjunto de
vehculos y T el conjunto de trasbordos. Se denotan c= |C|, n= |V |, m= |M| y r = |T |.Se definen Lk como la posicin de un vehculo k en un instante dado, zi la posicin del
cliente i en el sistema. Ms precisamente, definimos Lk,zi como sigue
Lk =
0 si vehculo k est en el depot
j [1,c] si vehculo k est en el origen del cliente jj [c+1,2c] si vehculo k est en el destino del cliente j cj [2c+1,2c+ r] si vehculo k est en e( j2c) y lleg vacoj [2c+ r+1,2c+2r] si vehculo k est en e( j2c r) y lleg con pasajerosj [2c+2r+1,2c+3r] si vehculo k est en s( j2(c+ r))
(4.1)
zi =
0 Si cliente i no ha sido ido a buscar
j [1,m] Si cliente i est en vehculo j y NO ha hecho trasbordoj [m+1,2m] Si cliente i est en vehculo jm y YA hizo trasbordoj [2m+1,2m+ r] Si cliente i est en trasbordo j2m2m+ r+1 Si cliente i ya fue pasado a dejar a su destino
(4.2)
Para cada par i, j [0,2c+3r] se asume conocido el tiempo de viaje para ir del nodo i a j,y se denota ti j, que es tal que t2c+i, j = t2c+r+i, j para todo i [1,r], j [0,2c+3r].
CAPTULO 4. MTODOS DE SOLUCIN PARA EL PDPT 40
Se define S el conjunto de todos los estados. Diremos que S S si
S= (L1, . . . ,Lm,z) (4.3)
con Lk {0, . . .2c+3r}, para k [1,m], y z {0, . . . ,2m+ r+1}c
Sea ahora z {0, . . . ,2m+ r+1}c. Se define qk(z) como la carga sobre el vehculo k en uninstante dado, en el cual los clientes estn en posiciones dadas por z. Ms precisamente
qk(z) = |{i [1,c] : zi {k,k+m}}| (4.4)
Sea S = {S : S = (L1, . . . ,Lm,z)} el conjunto de estados. Para cada S S se definen losestados siguientes de S como (S).
Hay que definir (S), a partir de un S S dado. La idea es definir para un estado S querepresenta las posiciones de todos los vehculos y clientes en el sistema en un instante dado,
todos los posibles estados que se pueden alcanzar con el movimiento de uno de los vehculos,
manteniendo todos los otros inmviles. Se denota por Xk(S) todos los posibles valores de
Lk [0,m+ 2c+ 2r] que son factibles de ser alcanzados a partir de S cuando se mueve elvehculo k. Para ser ms precisos Xk(S) tiene la siguiente forma
Xk(S) =
{0 : si zi = 2m+ r+1 i [1,c]}S
{16 i6 c : zi = 0, si qk(z)6 Qk1}S
{c+16 i6 2c : zic {k,k+m}}S
{2c+16 i6 2c+ r : si qk(z) = 0 y z j 6= k+m 06 j6 c}S
{2c+ r+16 i6 2c+2r : si qk(z) 6= 0 y z j 6= k+m 06 j6 c}
si Lk / [2c+1,2c+2r]
{2r+Lk si i [1,c] tq zi [2m+1,2m+ r]} si Lk [2c+1,2c+ r]
{r+Lk} si Lk [2c+ r+1,2c+2r]
(4.5)
Sea S = (L1, . . . ,Lk, . . . ,Lm,z), y sea S = (L1, . . . ,Lk, . . . ,Lm,z) un estado alcanzado al
mover el vehculo k. Notemos que la forma que adquiera el estado S depende solo de z y Lk.
CAPTULO 4. MTODOS DE SOLUCIN PARA EL PDPT 41
Para los distintos valores de Lk Xk(S) hay que ver cmo varan las posiciones de los clientes.Hay que considerar los clientes que se bajan de los vehculos y los que se suben, tanto para los
nodos asociados a orgenes y destinos, como para los de trasbordo. De esta forma, los valores
que tomen los distintos zi dados Lk,zi vienen dados por las relaciones
1. Lk = 0
zi = zi i [1,c] (4.6)
2. Lk [1,c]
zi =
k si i= Lk
zi (4.7)
3. Lk [c+1,2c]
zi =
2m+ r+1 si i= Lk c
zi (4.8)
4. Lk [2c+1,2c+2r]
zi =
2m+Lk2c si zi = k
zi si Lk [2c+1,2c+ r] (4.9)
z j =
2m+Lk2c r si zi = k
zi si Lk [2c+ r+1,2c+2r] (4.10)
El caso Lk [2c+ 2r+ 1,2c+ 3r] se detalla aparte pues en tal caso, cuando un vehculosale del trasbordo, debido a que tiene capacidad finita, si existen ms pasajeros que la ca-
pacidad del vehculo, entonces se debe elegir cules clientes subir al vehculo y cules no.
Adems, se impone la restriccin de que si el vehculo lleg vaco al trasbordo entonces al
CAPTULO 4. MTODOS DE SOLUCIN PARA EL PDPT 42
salir deber hacerlo al menos con un pasajero. Esto se hace para evitar la posibilidad de que
los vehculos pasen a un trasbordo sin hacer nada relevante1. Para ser ms exactos, cuando
Lk = 2c+2r+ j el conjunto de posibles estados siguientes se puede definir como sigue
Sea A= {i [1,c] : zi = 2m+Lk2c2r}, y sean B = {B A : |B|6Qk}, C = {C A :16 |C|6 Qk}.
1. Si Lk [2c+ r+1,2c+2r]Para cada B B habr un estado en que las variables cambian como sigue:
zi =
k+m si i Bzi (4.11)Notar que /0 B , y luego es explcita la existencia de un estado siguiente en que elvehculo sale del trasbordo vaco.
2. Si Lk [2c+1,2c+ r]Para cadaC C habr un estado en que las variables cambian como sigue:
zi =
k+m si i Czi (4.12)Notar que en este caso no se permite que el vehculo salga vaco del trasbordo, puesto
que lleg vaco.
As, se puede construir para cada S S , el conjunto (S) = {S : S S} de todos losestados alcanzables desde S al mover uno (y solo uno) de los vehculos.
Sea S S . Se define la funcin vS : (S){1, . . . ,m} como
vS(S) = k si S = (L1, . . . ,Lk, . . . ,Lm,z) (4.13)
que dados S,S, entrega el nmero del vehculo que se movi en esa transicin.
1Esto evita que se produzcan ciclos de estados, pues se obliga a cambiar el estado de al menos un cliente encada transicin de un estado a otro
CAPTULO 4. MTODOS DE SOLUCIN PARA EL PDPT 43
Notaremos Dk para k {1, . . . ,m} el tiempo acumulado de viaje del vehculo k y wi parai {1, . . . ,c} el tiempo de llegada del cliente i a algn trasbordo en caso de que est ah, queser -1 en caso de que el cliente no est en ningn trasbordo.
Sea ahora una tripleta (S,D,w), y sea S (S). Veamos cmo construir (D,w) de maneranica a partir de (S,D,w) y S, manteniendo la propiedad de seguir representando tiempos
acumulados de viaje (para el caso de D) y tiempo de llegada al trasbordo (para el caso de w).
Sea S v1S {k}, es decir S = (L1, . . . ,Lk, . . . ,Lm,z) un estado siguiente a S producto dehaber movido el vehculo k. Dependiendo de los valores que tomen Lk,Lk ser como se definan
D y w.
1. Lk [0,2c]
D j =
Dk+ tLkLk si j = kD j (4.14)w j = w j j = 1, . . . ,c (4.15)
2. Lk [2c+1,2c+2r]
D j =
Dk+ tLkLk si j = kD j (4.16)w j =
Dk si z j = k
w j (4.17)
3. Lk [2c+2r+1,2c+3r]
D j =
max{Dk+ tLkLk ,{wl : zl = m+ k}} si j = k
D j (4.18)
w j =
1 si z j = m+ k
w j (4.19)
CAPTULO 4. MTODOS DE SOLUCIN PARA EL PDPT 44
Lo anterior motiva que definamos, dado un estado S S , y tiempos de viaje acumulados yde llegada a trasbordo (D,w) una funcin u(S,D,w) : (S) (R+)m({1}R+)c como sigue
u(S,D,w)(S) = (D1, . . . ,Dk, . . . ,Dm,w) si S v1S {k} (4.20)
Definicin 4.1.1. Diremos que una tripleta (S,D,w) es siguiente a (S,D,w) si
i. S (S)
ii. (D,w) = u(S,D,w)(S)
y lo denotaremos (S,D,w) (S,D,w)
Se desea minimizar una combinacin lineal entre tiempos de viaje y tiempos de espera de
los clientes2.
Para un par de tripletas (S,D,w), (S,D,w) tales que (S,D,w) (S,D,w) se define lafuncin de transicin para pasar de (S,D,w) a (S,D,w) como
P(S,D,w)(S,D,w) =(1)
m
k=1
Dk(1(Lk,Lk))[c+1,2c](Lk)+
(21)m
k=1
Dk(1(Lk,Lk))[1,c](Lk)(4.21)
Y entonces para una tripleta (S,D,w) se define su funcin de rendimiento como
V (S,D,w) =mn{P(S,D,w)(S
,D,w)+V (S,D,w) : S (S),(D,w) = u(S,D,w)(S)}
(4.22)
= mnS(S)
{P(S,D,w)(S
,u(S,D,w)(S))+V (S,u(S,D,w)(S))}
(4.23)
2En trminos de las variables D del captulo 3 se puede escribir como iCDi+ +(1)iC [Di Di+ ],o de manera equivalente (1)iCDi +(21)iCDi+ .
CAPTULO 4. MTODOS DE SOLUCIN PARA EL PDPT 45
Se Introducen condiciones de borde para D Rm+ dadas por
V((0)m,(2m+ r+1)c, D,(1)c
)= 0 (4.24)
y si S S es tal que (S) = entonces V (S,D,w) = +, D Rm+,w ({1}R+)c.
El problema de encontrar las rutas factibles que minimicen la ponderacin entre tiempo de
espera y tiempo de viaje se reduce a encontrar
V((L0k)
mk=1,(z
0i )
ci=1,(D
0k)
mk=1,(w
0i )
ci=1)
(4.25)
Donde L0k = 0 k, z0i = 0 i, D0k = 0 k, y w0i =1 i.
Complejidad del Algoritmo
Para implementar computacionalmente este algoritmo, se necesita guardar en memoria un total
de
(2c+3r+1)m (2m+ r+2)c (4.26)
estados S S . Adems se debe guardar para cada uno de los estados, punteros indicando losposibles estados siguientes a S, es decir (S). Lamentablemente la naturaleza continua de las
variables Dk,wi hace que la cantidad real de estados sea mucho mayor a la cantidad antes men-
cionada. Por esto ltimo es que no se puede dar una mejor estimacin del orden del algoritmo,
sin embargo se sabe que ser al menos de orden cuadrtico en el nmero de estados antes
calculado. Los resultados mostrados en el captulo 5 muestran que la complejidad del mtodo
crece muy rpidamente.
Finitud del Algoritmo
Para que este algoritmo sea aplicable necesitamos al menos garantizar la finitud del mismo.
Para ello basta con probar la siguiente proposicin
CAPTULO 4. MTODOS DE SOLUCIN PARA EL PDPT 46
Proposicin 4.1.2. Sea S S ,S (S), y sean (D,w),(D,w) tales que (D,w)= u(S,D,w)(S).Entonces salvo que todos los clientes hayan sido atendidos (es decir que zi = 2m+ r+ 1i)existe i {1, . . . ,c} tal que zi 6= zi. Adems en una secuencia de estados
(S j,D j,w j
)nj=1 tales
que (S j,D j,w j) (S j+1,D j+1,w j+1) se tiene i {1, . . . ,c} una vez que un cliente cambiade un estado zi a otro zi no podr volver ms a zi.
Demostracin. La primera parte es directa de la definicin de z de 4.6 a 4.12.
Para la segunda parte, notemos que el grafo de la Figura 4.1 representa todas las posibles
transiciones (obviando la transicin identidad) de una variable zi para i {1, . . . ,c} al pasar deun estado S a otro S (S)Basta con ver que este grafo no admite ciclos para concluir con el resultado.
{2m+1, . . . ,2m+ r}2m+ r+1
0
{1, . . . ,m}
{m+1, . . . ,2m}
Figura 4.1: Transiciones posibles de la variable zi
Corolario 4.1.3. El algoritmo de Programacin Dinmica termina en un nmero finito de
pasos
Demostracin. Si no fuera as, se tendra o que bien en alguna transicin no se producen cam-
bios en ninguna variable zi o bien si ocurre un cambio se llega a un estado anterior. Cualquiera
de los dos casos est descartado por la Proposicin 4.1.2
CAPTULO 4. MTODOS DE SOLUCIN PARA EL PDPT 47
Extensin al Caso Dinmico
Si en algn momento aparece la necesidad de atender un nuevo cliente |C|+ 1, y se sabe elestado del sistema en el momento actual, digamos que el sistema se encuentra en un estado
(L0,z0,D0,w0), se agrega entonces una nueva componente a z0,w0 y se resuelve
V (L0,z0,0,D0,w0,1) (4.27)
que es la solucin ptima al problema partiendo desde (L0,z0,D0,w0).
Construccin de Rutas ptimas
Una vez que el algoritmo termina, la pregunta obvia es, Cul es la solucin del problema? o
de manera equivalente, Cmo construyo las rutas ptimas?.
Lamentablemente no se tiene una respuesta a esta interrogante, o ms bien, la respuesta
a esa pregunta depende de cmo se guarde el conjunto de estados del sistema. De la manera
que se ha propuesto en esta memoria, que es la construccin en tiempo real de los estados (por
causa de la componente real que poseen), el algoritmo descrito no puede resolverse como un
problema de rutas mnimas en el cual se guarde el conjunto de predecesores de cada estado,
pues para poder hacer esto se necesita conocer a priori el conjunto de estados. Conocer a
priori el conjunto completo de estados (S,D,w) computacionalmente produce un crecimiento
exponencial en la cantidad de recursos de memoria para almacenar todos los estados.
CAPTULO 4. MTODOS DE SOLUCIN PARA EL PDPT 48
4.1.2 Cortes Combinatoriales de Benders
En esta seccin se presenta un algoritmo basado en una variacin del algoritmo de descom-
posicin de Benders (Benders 1962), presentado por Codato y Fischetti (2004), y cuyo gran
aporte est en el hecho de que logra explotar la estructura de problemas basados en variables
01 ligados con variables reales por medio de restricciones del tipo Big-M.Sea el problema de minimizacin
(P)
mnx,y
ctx+dty
s.a. Ax6 b
y B(x)
Cy6 e
x {0,1}n
y> 0
Inicialmente se supone que d= 0,c 6= 0. Siguiendo el mismo desarrollo del captulo anterioreste problema se puede escribir de manera equivalente como
(P) mnx{ctx+mn
y{0ty : y B(x),Cy6 e,y> 0} : Ax6 b,x {0,1}n}
Luego para x conocido, se puede definir (Px) como el siguiente problema
(Px)
mny
0ty
s.a. y B(x)
Cy6 e
y> 0
(Px) no es ms que el problema de decidir si el conjunto {y : y B(x),Cy 6 e,y > 0} esfactible o no.
Si las restricciones y B(x) pueden ser descritas por condiciones de la forma
CAPTULO 4. MTODOS DE SOLUCIN PARA EL PDPT 49
x j(i) = 0jbi jy j 6 fi i I0 (4.28)
x j(i) = 1jbi jy j 6 fi i I1 (4.29)
cuando x es fijo, entonces tan solo algunas restricciones de las anteriores se activan y luego el
problema (Px) puede escribirse como
(Fx)
mny
0ty
s.a. jbi jy j 6 fi i Ix
Cy6 e
y> 0
donde Ix = {i I0 : x j(i) = 0}{i I1 : x j(i) = 1}.Se Define entonces el problema maestro
(M)
mnx,y
ctx
s.a. Ax6 b
x {0,1}n
que en caso de ser infactible, entonces el problema completo tambin lo es. En cambio, si x
es una solucin ptima de (M) y (Fx) tiene solucin y, entonces (x,y) es solucin ptima
del problema completo. Finalmente, si x es una solucin ptima de (M) y (Fx) es infactible,
entonces existe un subconjunto de restricciones (minimal) de (Fx) que se estn violando, y por
lo tanto algunos xj(i) deben cambiar de valor. Ms especficamente, se agrega el siguiente corte
al problema (M)
iSI0Ix
x j(i)+ iSI1Ix
(1 x j(i))> 1 (CCB)
Donde S son los ndices de un conjunto infactible minimal de (Fx).
CAPTULO 4. MTODOS DE SOLUCIN PARA EL PDPT 50
Conjunto Minimal de Restricciones Infactibles
Sea x una solucin de (M) tal que (Fx) es infactible. Sea el problema dual de (Fx)
(DFx)
maxu,v
zx(u,v) = iIx
fiui+iH
eivi
s.a. iI
bi jui+iH
ci jvi 6 0 j
u,v6 0
Si (Fx) es infactible, entonces (DFx) es infactible o no acotado, sin embargo la infac-
tibilidad de (DFx) es imposible pues u = v = 0 es una solucin factible, y por lo tanto la
infactibilidad de (Fx) se traduce en el no acotamiento de (DFx).
Ntese que, si (u,v) es factible para (DFx) y tal que zx(u,v) = 1, entonces (u,v)
es tambin factible y zx(u,v) = zx(u,v), y por lo tanto (u,v) es un rayo de no aco-
tamiento del problema. Sin perder generalidad se puede entonces encontrar un rayo particular
de no acotamiento, por ejemplo (u,v) tal que zx(u,v) = 1. Luego el problema que se resuelve
es el siguiente
(DFx)
maxu,v
gtu+htv
s.a. iIx
fiui+iH
eivi = 1
iI
bi jui+iH
ci jvi 6 0 j
u,v6 0
donde g,h son los pesos que se les da a las restricciones en (DFx). El valor que tomen es
arbitrario y pueden ser usadas para manipular el soporte de las variables duales (y por tanto las
restricciones que van a formar los conjuntos de restricciones infactibles).
La siguiente propiedad es vlida
Proposicin 4.1.4. Sea (u,v) solucin de (DFx). Entonces las filas de (Fx) indexadas por
IIS= {i : ui 6= 0 vi 6= 0} forman un conjunto de restricciones infactibles de (Fx).
CAPTULO 4. MTODOS DE SOLUCIN PARA EL PDPT 51
Demostracin. Si el conjunto de restricciones indexadas por IIS fuese factible, existe un y> 0
tal que
jbi jyj 6 fi i Ix IIS (4.30)
jci jyj 6 ei i H IIS (4.31)
Multiplicando 4.30 por ui y 4.31 por vi y sumando queda que
jyj
(
iIxIISui bi j+
iHIISvi ci j
)>
iIxIISui fi+
iHIISvi ei = 1 (4.32)
y como todos los yj son positivos (> 0) queda que al menos para algn j debe tenerse que
iIxIIS
ui bi j+ iHIIS
vi ci j > 0 (4.33)
lo que es una contradiccin.
Lamentablemente esta proposicin no entrega minimalidad del conjunto de restricciones
violadas.
Para resolver el caso c = 0,d 6= 0, se deben manejar variables globales UB, > 0. Inicial-menteUB=+. Al sub-problema se le debe agregar la siguiente restriccin
dty6UB (4.34)
Para una solucin factible x de (M), si (Fx) es factible (o equivalentemente su dual modi-
ficado es infactible), significa que se ha encontrado una nueva solucin al problema (x,y) tal
que dty 6UB .Para el Problema de Recoger y Dejar Pasajeros con Trasbordos, una funcin objetivo ser
de la forma g(D,z) que debe agregarse al subproblema como
g(D,z)6UB (4.35)
Adicionalmente se pueden agregar restricciones asociadas a ventanas de tiempo (duras y
blandas).
CAPTULO 4. MTODOS DE SOLUCIN PARA EL PDPT 52
Cabe sealar, que el problema maestro en este caso se transforma en un problema de facti-
bilidad, es decir la ramificacin no considera la mejora de ninguna funcin objetivo.
Algoritmo de Ramificacin y Corte
Lo anterior motiva naturalmente a resolver el problema maestro (M) por medio del mtodo de
ramificacin y acotamiento.
En cada nodo del rbol de ramificacin del problema (M) considerar las variables x que
toman valores en {0,1}, y construir el problema (Fx). Si (Fx) es factible, seguir la rami-ficacin (y hacer UB dty, en caso que corresponda). En caso contrario, resolver (DFx)y agregar el corte (CCB) asociado a las variables x j(i) que intervienen en las restricciones
asociadas a las variables duales encontradas.
Para el caso c= 0,d 6= 0 el algoritmo termina cuando (M) se vuelve infactible.
Implementacin del Algoritmo de Ramificacin y Corte
En el marco del desarrollo de la seccin anterior, la funcin objetivo slo puede depender de
las variables binarias o de las variables reales.
Por ejemplo, si se considera una funcin objetivo de la forma
f (x)+ g(D,z), = 0. (4.36)
entonces se resuelve el siguiente problema a variables enteras
mnx
f (x) (4.37)
s.a. x satisface (3.9)-(3.16) (4.38)
Y se usa el dual del siguiente problema (con x fijo) para generar los cortes que se introducen al
CAPTULO 4. MTODOS DE SOLUCIN PARA EL PDPT 53
problema maestro.
mnD,z
0t (Dz
)(4.39)
s.a.
x,D satisfacen (3.17)-(3.23) (4.40)
x,z satisfacen (3.24)-(3.30) (4.41)
D,z satisfacen (3.31) (4.42)
z satisface (3.10) (4.43)
D> 0 (4.44)
z [0,1]|V ||M||C| (4.45)
Adicionalmente se agrega 4.35 en caso de que > 0.
CAPTULO 4. MTODOS DE SOLUCIN PARA EL PDPT 54
4.2 Mtodos Heursticos
En esta seccin se presentan dos heursticas de insercin para resolver el Problema de Recoger
y Dejar Pasajeros con Trasbordos en el caso particular en que se tiene tan solo 1 trasbordo y
los vehculos pueden pasar no ms de una vez por l.
El primero de ellos est esencialmente diseado para cuando la funcin objetivo depende
de los tiempos en que los nodos son visitados (por ejemplo, cuando se desea minimizar tiempos
de espera, de viaje, ventanas de tiempo, etc.). Usa dos mtodos (corte de rutas y reinsercin de
clientes) para buscar soluciones que mejoren alguna solucin previamente construida.
El segundo algoritmo en cambio, comienza con rutas vacas, inicialmente solo conteniendo
trasbordos e iterativamente se van insertando los clientes en las rutas. Este mtodo est espe-
cialmente diseado para funciones objetivo que no dependen del momento en que se atienden
los nodos, como por ejemplo, cuando se quiere minimizar la distancia total recorrida por los
vehculos.
El segundo mtodo se ve muy natural en su implementacin, y entonces cabe hacerse la
pregunta de por qu no usar tal mtodo para funciones objetivo como tiempos de espera o
tiempos de viaje. La razn es que el mtodo en tal caso siempre entrega como solucin, un
conjunto de rutas que no hace trasbordo. Cualquier solucin que considere el paso efectivo
por un trasbordo (es decir, que los vehculos pasen a los trasbordos y que adems lleguen con
clientes que cambien de vehculo) nunca son consideradas.
4.2.1 Ventanas de Tiempo y/o Tiempos de Espera y de Viaje
En lo siguiente se presenta un mtodo heurstico principalmente orientado a resolver el Proble-
ma de Recoger y Dejar Pasajeros con Trasbordos para cuando la funcin objetivo depende de
los tiempos en que los nodos son atendidos (tiempos de espera, tiempos de viaje, violacin de
ventanas de tiempo, etc.). ste es un algoritmo de insercin que re-optimiza rutas anteriormente
construidas.
CAPTULO 4. MTODOS DE SOLUCIN PARA EL PDPT 55
En primer lugar, se presenta un mdulo de optimizacin local de rutas. Como su nombre lo
indica, este mdulo busca, a partir de rutas R1, . . . ,Rm, algunas de las cuales tienen al trasbordo
incorporado, reoptimizar estas rutas favoreciendo el uso del trasbordo. En caso de no encontrar
una solucin mejor que la inicial, el optimizador tiene la opcin de quedarse ya sea con esa
solucin o con la mejor de las encontradas por el algoritmo.
El mdulo de optimizacin local de rutas es utilizado luego en la heurstica. Si R1, . . . ,Rm
son rutas que no hacen trasbordo, se consideran todas las inserciones de trasbordos convenien-
tes de analizar. En ellas, una vez insertados los trasbordos, se aplican los mtodos de corte de
rutas y reinsercin de clientes.
Mdulo de optimizacin local de rutas
Sean rutas R1, . . . ,Rl que hacen trasbordo. Se quiere reoptimizar el uso del trasbordo, permi-
tiendo que los vehculos que pasan al trasbordo intercambien pasajeros y, alternativamente,
rehagan sus rutas. Para fijar ideas, por ejemplo cuando 2 vehculos hacen trasbordo pero nin-
gn cliente se cambia de vehculo, el uso del trasbordo no tiene sentido, y entonces se debe
aplicar alguna estrategia que use el trasbordo para encontrar soluciones mejores.
El procedimiento propuesto se divide en 2 etapas que se aplican de manera secuencial:
Corte Las rutas se cortan en el punto de trasbordo. Los clientes eliminados de las rutas, segn
si se elimin tanto en su origen y destino como slo en su destino se guardan en listasU1
yU2.
Insercin Los nodos eliminados en la etapa de corte se reinsertan en las rutas.
Definicin 4.2.1. Sea Rk una ruta del vehculo k que hace trasbordo. Se define la porcin post-
trasbordo de la ruta Rk como Rfk , que comienza en el trasbordo y termina en el depot destino
del vehculo k. De igual modo se define la porcin pre-trasbordo de la ruta Rk como Rik, que
comienza en el depot origen del vehculo k y termina en el trasbordo.
CAPTULO 4. MTODOS DE SOLUCIN PARA EL PDPT 56
La Figura 4.2 ilustra el proceso de corte de rutas cuando son dos los vehculos que hacen
trasbordo.
4
8
1+
2+8+ 10+
97
24+
10
3
R2
5
R1
5+ 6+
k+1
k+2
6
k111+
3+
9+
7+
12
111
13
12+
13+
k2
(a) Rutas Iniciales antes de aplicar Corte
U2 = {1,4,6,7,8,9} Clientes con solo destino en R f1,2
8
1+
2+8+ 10+
97
24+
10
3
R2
5
R1
5+ 6+
k+1
k+2
6
k111+
3+
9+
7+
12
111
13
12+
13+
k2
4
U1 = {10,11,12,13} Clientes con origen y destino en R f1,2
(b) Rutas Finales despus de aplicar Corte
Figura 4.2: Rutina de Corte de Rutas
CAPTULO 4. MTODOS DE SOLUCIN PARA EL PDPT 57
La rutina CortarRutas se detalla a continuacin
Procedure CortarRutasInput: R1, . . . ,RlOutput:U1,U2begin4.1.1
U1 /04.1.2U2 /04.1.3for i C do4.1.4
for j 1 to l do4.1.5if i+ and i R fj then4.1.6
U1U1{i}4.1.7Borrar i+, i de R fj4.1.8
else if i+ Rij and i R fj then4.1.9U2U2{i}4.1.10Borrar i de R fj4.1.11
end4.1.12
Luego de aplicar el algoritmo de corte de rutas, comienza la etapa de Insercin de clientes.
Lo que se hace es, mediante un proceso iterativo, buscar la mejor insercin para un cliente que
se ve afectado por el trasbordo, es decir aquellos que estn enU1U2.El algoritmo propuesto se detalla a continuacin
Procedure InsercinInput: R1, . . . ,Rl ,U1,U2Output: S1, . . . ,Sl . Rutas de vehculos haciendo trasbordoStep 14.2.1
// Inicializar Output
Si Rii4.2.2whileU1U2 6= /0 do4.2.3
Sacar i deU1U24.2.4if i estaba en U1 then4.2.5
InsertarOD(i,S1, . . . ,Sl ,U1,U2)4.2.6else4.2.7
InsertarD(i,S1, . . . ,Sl ,U1,U2)4.2.8
return S1, . . .Sl4.2.9end Step 14.2.10
CAPTULO 4. MTODOS DE SOLUCIN PARA EL PDPT 58
Las subrutinas InsertarD e InsertarOD se detallan a continuacin
Procedure InsertarDInput: i,R1, . . . ,Rl ,U1,U2Output: voidbegin4.3.1
Sh Rhh4.3.2v+4.3.3for k 1 to l do4.3.4
js finds(Sk)4.3.5for j js+1 to size(Sk) do4.3.6
Th Shh4.3.7InsertarNodo(Tk, j, i)4.3.8z = new triple array4.3.9if Feas(T1, . . . ,Tl ,U1,U2,z) then4.3.10
val Value(T1, . . . ,Tl ,U1,U2,z)4.3.11if val < v then4.3.12
Sh Thh4.3.13v val4.3.14
for k 1 to l do4.3.15Rk Sk4.3.16
end4.3.17
En la lnea 4.3.8 se inserta el nodo i en la posicin j de la ruta Rk. Esto se hace para todo
k y para todo j y se guarda la mejor de todas las inserciones.
CAPTULO 4. MTODOS DE SOLUCIN PARA EL PDPT 59
Procedure InsertODInput: i,R1, . . . ,Rl ,U1,U2Output: voidbegin4.4.1
S1 R1,S2 R24.4.2v+4.4.3for k 1 to l do4.4.4
for l 1 to l do4.4.5if k == l then4.4.6
for j+ 2 to size(Sk) do4.4.7for j j++1 to size(Sk)+1 do4.4.8
Th Shh4.4.9InsertarNodo(Tk, j+, i+)4.4.10InsertarNodo(Tk, j, i)4.4.11z = new triple array4.4.12if Feas(T1, . . . ,Tl ,U1,U2,z) then4.4.13
val Value(T1, . . . ,Tl ,U1,U2,z)4.4.14if val < v then4.4.15
Sh Thh4.4.16v val4.4.17
else4.4.18je finde(Sk)4.4.19js finds(Sl)4.4.20for j+ 1 to je do4.4.21
for j js+1 to size(Sl) do4.4.22Th Shh4.4.23InsertarNodo(Tk, j+, i+)4.4.24InsertarNodo(Tl , j, i)4.4.25[z, f eas]Feas(T1, . . . ,Tl ,U1,U2)4.4.26if f eas then4.4.27
val Value(T1, . . . ,Tl ,U1,U2,z)4.4.28if val < v then4.4.29
Sh Thh4.4.30v val4.4.31
for k 1 to l do4.4.32Rk Sk4.4.33
end4.4.34
En las lneas 4.4.10,4.4.11, 4.4.24 y 4.4.25 se insertan los nodos origen-destino del cliente
i en la posicin j de la ruta k. Esto se hace para todo k y para todo j. El resultado es la mejor
de todas las inserciones.
CAPTULO 4. MTODOS DE SOLUCIN PARA EL PDPT 60
Notar que la forma en que se sacan los elementos de U1 U2 en la lnea 4.2.4 no estdefinida a priori, y no se tiene un
Recommended