f y s de vrp con demanda variable, transbordos y ventanas de tiempo

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


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

)


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.


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


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


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-


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


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-


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


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


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


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


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


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


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


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


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


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.


{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.


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.


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 .


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


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.


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


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.


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


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)


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].


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.


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


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


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)


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+ .


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


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


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.


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


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).


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).


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).


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


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.


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.


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.


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


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


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.


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


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


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.


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

f y s de vrp con demanda variable, transbordos y ventanas de tiempo

Documents