20 - Diseño de redes de transporte con congestión

8/14/2019 20 - Diseo de redes de transporte con congestin

1/20

-347-

DISEO DE REDES DE TRANSPORTE CON CONGESTIN

J. Enrique Fernndez

Departamento Ingeniera'de TransportePontificia Universidad Catlica de Chile

Resumen

El diseo de redes es un tema de fundamental importancia para la gestinde sistemas de transporte. La especificacin tradcionalmente mas trata

da consiste en escoger la mejor red de vas de infraestructura, para s_atisfacer un conjunto de demandas de transporte en el espacio, representadas por una matriz 0-D de viajes en automvil, pero tambin pueden utilizarse especificaciones que permitan determinar las caractersticas pti-mas de operacin de una red de servicios de transporte publico, que uti-lizan una red de infraestructura dada, o ambos problemas simultneamente.La formulacin matemtica de estos problemas conduce sin embargo a mode-los cuyo tratamiento y solucin acarrea importantes dificultades teri-cas y prcticas.

En este trabajo se plantean las formulaciones matemticas de los problemas de diseo de redes y se analizan sus caractersticas para el caso de

variables de decisin continuas. A continuacin se describen y analizanlos mtodos ms importantes que han sido propuestos para resolver elprcblema en casos reales.


2/20

-348-

1. Introduccin

El diseo de redes de transporte est relacionado con dos problemasde gran relevancia prctica: la determinacin de las caractersticas ope^racionales ptimas de una red de infraestructura, para satisfacer las e_mandas planteadas a travs de una matriz 0-D de viajes en automvil (PDI)y la determinacin de las caractersticas operacionales ptimas de unared de rutas de transporte publico, a fin de satisfacer las demandas portal servicio planteadas a travs de la correspondiente matriz 0-D (PDR).

En el caso del PDI las variables de decisin son las capacidades delos arcos (calles o vas) de la red de infraestructura analizada y en elcaso del PDR son las frecuencias de los servicios de transporte publico(lneas de buses, aviones, etc.) que operan en cada ruta de la red. E_s_tas variables, fundamentalmente en el caso del PDI, son de carcter dis_creto, ya que la unidad fsica relevante de definicin de capacidad esla "pista" y una va tiene siempre un numero discreto de pistas. Sin em

bargo, la utilizacin de variables discretas en la especificacin maternatica del PDI, conduce a problemas de carcter combinatorio cuya solucines prcticamente imposible para la mayora de los casos de tamao real(ver: Fernndez, 1982; Gutirrez, 1982), lo que es aun ms vlido para elcaso del PDR que posee un espacio de soluciones de mayor dimensionalidad.Por este motivo, durante el ultimo tiempo los esfuerzos de la mayora delos investigadores se han concentrado en el uso de formulaciones que utjilizan variables de decisin continuas (Steenbrink, 1974; Abdulaal y Le -blanc, 1979 y 1984; Marcotte, 1983a y 1983b; Harker y Friesz, 1984; Fernndez, 1984 y 1985) .

La utilizacin de variables de decisin continuas constituye una a_proximacin absolutamente razonable en el caso del PDR, principalmente

cuando se analizan sistemas que presentan servicios con altas frecuencias(Ej.: redes de servicios de buses urbanos en pases en desarrollo). Parael caso del PDI, Elton (1983) ha demostrado que es posible utilizar unaformulacin continua como primera etapa en la obtencin de una solucindiscreta ptima, lo que permite resolver problemas de tamao real en solouna pequea fraccin del tiempo computacional necesario para resolver drectamente una formulacin discreta.

La bondad de las soluciones a los problemas de diseo de redes se ej^tablece generalmente evaluando una funcin objetivo, que considera loscostos totales de viaje de los usuarios y los costos de construccin dela infraestructura, en el caso del PDI, y los costos totales de viaje delos usuarios y costos totales de operacin de los servicios de transporte publico ofrecidos, en el caso del PDR. En todos los casos considrados en este trabajo se supone que las vas de transporte estn sujetasal fenmeno de congestin, lo que hace que tanto el costo de viaje de losusuarios del sistema, como el costo de operacin de los oferentes de servi^cios de transporte publico, aumente al aumentar el numero de vehculosque utilizan la va. Para ambos problemas la funcin objetivo est porlo tanto constituida por dos tipos de funciones, una creciente con las va.riables de decisin (costos de construccin u operacin) y otra decrecien_te con dichas variables (costos de viaje de los usuarios del sistema).Una solucin es ptima si tiene asociado el menor costo total posible, almismo tiempo que se respetan las restricciones del problema.


3/20

-349-

Las restricciones normalmente consideradas incluyen: continuidad, yconsistencia de flujos, comportamiento espontneo de los usuarios en suutilizacin del sistema y no negatividad de las variables de decisin.

La formulacin matemtica del problema de diseo de redes cae dentrode la categora de problemas de programacin multinivel, cuyo tratamieiito ha suscitado gran inters ltimamente. Ella consiste en una rama dela programacin matemtica que puede ser vista, ya sea como una general^zacin de problemas del tipo mini-max, o como una clase particular dejuegos tipo Stakelberg (ver: Marcotte,1983b Fiek, 1984).

Lo que resta de este trabajo est estructurado como sigue: a continuacin planteamos la formulacin matemtica del problema y analizamos suscaractersticas tericas; finalmente presentamos y analizamos las caracte^rsticas de los principales mtodos de solucin propuestos.

2. Planteamiento del Problema

2.1.Problema de diseo de redes de infraestructura (PDI)

En el planteamiento del PDI usaremos la siguiente notacin:

G(N, A) Grafo dirigido que representa a la red de transporte a analzar y en la que N y A correspondan a los conjuntos da nodos yarcos respectivamente.

W = Conjunto de todos los pares origen-destino (0-D) que sirve lared.

w = ndice general correspondiente a un par 0-D (w W)

P = Conjunto de todas las rutas que existen sobre la red paraunir pares 0-D.

P = Conjunto de las rutas que unen el par w.

p = ndice general correspondiente a una ruta (p e P) .

a = ndice general correspondiente a un arco de la red (a eA).

f = Flujo sobre el arco a.

h = Flujo sobre la ruta p.

T = Demanda por viajes entre el par w.

u = Inversin o mejoramiento propuesto para el arco a. a6 = Costo constante unitario de inversin, por unidad de capaci dad, sobre el arco a.

c (f ,u ) = Costo medio de viaje sobre el arco a, que^se supone es una aaa funcin diferenciable en segundo orden con respecto a las ya

riables f y u . aJ a

C = Costo medio de viaje sobre la ruta p.P


4/20

-350-


5/20

El parmetro Xutilizado en la formulacin del PDI, corresponde al inverso del valor del tiempo de viaje, y se utiliza cuando c representa eltiempo de viaje sobre el arco a. Si c representa costos ' de operacinen unidades monetarias, A debe tomar un valor igual a la unidad.

El problema as planteado es un problema de programacin de dos nive_les. Los agentes decisores a cada nivel actan en forma jerrquica: enel nivel superior, la autoridad planificadora toma decisiones que involueran especificaciones del vector,u, de tal forma de minimizar el costosocial total asociado al sistema, pero tomando en cuenta las reaccionesde los usuarios que se encuentran en el segundo nivel jerrquico (f*(u)).A su vez, los usarios toman decisiones de uso del sistema, que determinan

el valor del vector f, de tal forma de minimizar sus costos de operacinindividuales, pero restringidos por las decisiones tomadas en el nivelsuperior respecto del vector u.

Recientemente, algunos autores han investigado problemas de este tipoen que estn involucrados varios niveles jerrquicos; en cada nivel losagentes estn restringidos por las decisiones del nivel superior y maxindzan sus beneficios tomando en consideracin las reacciones de los nivelesinferiores (ver Bard y Falk, 1982).

2.2. PDI con comportamiento ptimo de los usuarios del sistema

La funcin f*(u) representa el comportamiento espontneo de los usua

rios de una red de vas, obtenido como resultado de la superposicin dedecisiones individuales en que cada usuario trata de minimizar indepen -dientemente su costo de operacin. Dado que la operaciSn de las vas dela red estn sujetas a externalidades de congestin, tal comportamientono conduce a un ptimo social del sistema, en que el costo total socialde operacin sea mnimo, para un valor del vector u, ya que el equilibriof*(u) se obtiene como consecuencia de la consideracin de los costos me_dios individuales de operacin sobre las posibles rutas que unan pares 0-D sobre la red y no los costos marginales sociales (ver, Fernndez yFriesz, 1983).

-351-


6/20

-352-

Sin embargo, si suponemos que los usuarios se comportan en forma sc>cialmente ptima, en su eleccin de rutas de viaje sobre la red, podemosconsiderar el vector f, adems del vector u, como variables de decisin

del PDI. En tal caso desaparece la restriccin f*(u), representada porel problema PEU, y obtenemos la la siguiente formulacin notablemente massencilla:


7/20

-353-

(8)

Por lo tanto, en este caso, el PDI se transforma en un problema desolucin prcticamente trivial. El problema (8) es aun ms fcil de re_solver que un problema estandard de asignacin de flujos sobre la redoriginal. Es necesario aclarar que esta notable caracterstica es unaconsecuencia de haber supuesto que las funciones de costo de capacidad sonlineales. Si en vez de ello suponemos que estas funciones son de la forma:

(9)

la expresin de u (f ) resultante de resolver el problema (5) resulta ser ennuestro caso:

(10)

e introduciendo (10) en (7) obtenemos

(11)


8/20

-354-

Esta ultima formulacin es equivalente a un problema estandard deasignacin de flujos sobre la red original, con funciones de costo mo_dificadas, el que puede ser resuelto eficientemente utilizando algorit^ mos

del tipo Frank-Wolfe (Leblanc et al, 1975) o Partan (Florian et al, 1985).Es fcil ver que (11) se transforma en (8) para m = 1.

Por lo tanto, podemos conlcuir que si suponemos que los usuariosutilizan la red de transporte en forma socialmente ptima, el PDI setransforma en un problema que puede ser resuelto en forma eficiente utilizando algoritmos ampliamente conocidos.

2.3.Problema de diseo de rutas de transporte publico (PDR)

En el caso del PDR consideraremos una red G(N, A) que sirve como in_fraestructura comn para la operacin de transporte privado y transportepblico. Si tomamos como ejemplo el sistema de rutas de transporte publjLco de una ciudad, tendremos que la mayora de los arcos de la red sernsimultneamente utilizados por buses y automviles y por lo tanto los eostos de operacin de ambos medios estarn interrelacionados: un aumento delflujo de automviles afectar al costo de operacin de los buses yviceversa. Por lo tanto, tendremos dos funciones de costo de operacinpara cada arco, cada una de ellas dependiente del flujo total:

(12)

(13)

en que cr es la funcin de tiempo de viaje de los vehculos de transpojr tepblico sobre el arco a y c la funcin de costos de operacin detransporte privado, adems: a


9/20

-355-

:: Tendremos tambin que .-'los cors tos totales de operacin sobre un arco,

para cada medio sern:;' " > ;. . ,;'; -.: r. .'.


10/20

Por ltimo, un fenmeno importante a considerar en la operacin detransporte publico( Ej .: servicios de buses en ciudades de pases en djesarrollo) es el de las lneas comunes (De Cea, 1984). Es as como dis -

tintas lneas utilizan un mismo conjunto de arcos o segmento comn de ruta, haciendo que un usuario cuyos nodos de acceso y egreso a la red eten sobre dicho segmento, tenga varias lneas o servicios alternativosque puede utilizar. Por lo tanto, incluiremos la siguiente notacin adcional:

-356-


11/20

La funcin objetivo consta de varios trminos distintos: los dos

primeros representan el costo de viaje de los usuarios de transporte prjivado, el tercero los tiempos totales de viaje sobre el vehculo para losusuarios de transporte pblico, el cuarto el tiempo total de acceso y elquinto el tiempo total de espera, incurridos por los usuarios de trans -porte pblico y el termino final (sexto) representa el costo total de ope_racin de todas las lneas o servicios de transporte publico.

Al igual que en el caso del PDI, el PDR as planteado es tambin unproblema de programacin en dos niveles. En el nivel superior, una autorjLdad central toma decisiones acerca de la especificacin del vector d, detal forma de minimizar el costo social total asociado con el sistema, perotomando en cuenta las reacciones de los usuarios de transporte privado ytransporte pblico que se encuentran en el nivel jerrquico inferior, Asu vez, los usuarios toman decisiones de uso del sistema que determinan elvalor del vector F, de tal forma de minimizar sus costos de .operacin individuales, pero restringidos por las especificaciones del vector d decidjidas en el nivel superior.

Es importante notar que el PDR no es un problema convexo, dado que lafuncin F*(d) no es convexa. Sin embargo, si suponemos F dado y constante,podemos definir tantos problemas unidimensionales en funcin de d como 1neas de transporte pblico existan. Para cada uno de estos proble_mas se supone que todas las frecuencias son fijas a excepcin de una deellas.

Los problemas unidimensionales as definidos son convexos ya que tan_to las funciones C como C son convexas en d para F dado y 1-as funcionesde tiempo de espera y costos de operacin Gr son tambin convexas

en d para F dado. Por ltimo, la funcin de tiempo de acceso escons_tante para F dado, ya que los flujos VY. son dados y el tiempo de

acceso tV. es independiente de las frecuencias? d ; por lo tanto, el ternno co- J rrespondiente de la funcin objetivo r puede ser eliminado deconsideracin en el problema unidimensional en funcin de d .

Esta convexidad de la funcin objetivo en trminos de cada uno de los dres una propiedad importante para la solucin del PDR, dado que comnmente los algoritmos de solucin incluyen dentro de su operacin busque dasunidimensionales, que tendrn solucin nica si es que la funcin uni~~dimensional involucrada es convexa.

357-


12/20

-358=-"'**

3. Principales Mtodos de Solucin

Los mtodos o enfoques de solucin ms importantes que han sido pro -puestos para resolver los problemas de diseo de redes son los siguientes:

3.1. Algoritmo de Hooke and Jeeves (H-J)' ' ' Este mtodo consiste en la utilizacin del algoritmo de

Hooke andJeeves (1961). Dicho algoritmo es suficientemente robusto como para norequerir convexidad, ni una expresin explcita de las derivadas de lafuncin objetivo con respecto a las variables de decisin. Su aplicacinsolo requiere que la funcin analizada sea continua y evaluable para cual_quier valor factible de las variables y fue originalmente propuesta porAbdulaal- y Leblanc (1979) para la solucin del PDI. *

El algoritmo de H-J trabaja sobre la base de la repeticiqn de un pro_cedira-iento de do fases: En la primera, partiendo de una solucin facti -ble x cualquiera que sirve como punto base, se,realiza un proceso de busqueda exploratoria a travs de cada una de las coordenadas del espacio desoluciones, que permita definir una "buena" direccin local de descenso,(reduccin del valor, de la funcin obejtivo). .Para ello, se toma una delas variables x:.. l_l se aumenta su valor en una cantida pre-establecida yse evala la " funcin objetivo en el nuevo punto x as definido. Siel valo obtenido resulta menor que el correspondiente al punto base, seacepta x y se: pasa a examinar la siguiente .variable x. . Sji. por-el contra_rio, la funcin.objetivo resulta tener un mayor valor en x, se disminuyeel valor original de x.- en 6 y, se vuelve a evaluar la funcin objetivo.Si resulta menor que en el punto de partida, se acepta el nuevo puntoy se continua con la siguiente coordenada. En caso de que el valor de lafuncin objetivo resulte mayor, se vuelve al punto base y se pasa a exa_

minar la siguiente coordenada. Este proceso se repite hasta completar elnumero total de las variables involucradas en el vector . Si ninguna delas bsquedas exploratorias, con respecto a todas las variables contenidasen el vector x, logra encontrar un nuevo punto que disminuya el valor dela funcin objetivo, se reduce el valor de en una cantidad pre-estable-cida y se repite todo el proceso de nuevo. El algoritmo se detiene cuandoel valor de 6 decrece mas all de un valor de "tolerancia" predefinido.

Cuando la primera fase ha dado como resultado un nuevo punto o solu -cionfactible, en el cual la funcin obj'etiv tiene un valor menor que en elpunto-base anterior, stos dos puntos definen Una direccin de avance enel espacio X. La longitud de avance se determina por la distancia entrelos dos puntos, multiplicada por un parmetro a . . ...

Las caractersticas de convergencia del mtodo estn gobernadas fundamentalmente por los valores de los dos parmetros ayo los que debendeterminarse en forma numrica para cada tipo de problema a tratar. En elcaso del PDI, se ha encontrado que una buena combinacin de valores es:

, -----------__

1/ Supongamos que x representa el vector d las variables de deci^sion. En el caso del PDI tendremos x E u y en el caso del PDR x5 d


13/20

-359-

a=ly 6= O,5 (ver Elton, 1983) cuando g es del tipo g = 3 |u , enque el exponente n determina las caractersticas de rendiemientos aescala en la cosntruccin de infraestructura (en el pre_ sent trabajoestamos suponiendo n = 1).

Est claro que na puede asegurarse que el mtodo obtenga un ptimoglobal a menos que el problema a resolver fuera convexo, lo que no ocu.rre en el caso del PDI ni del PDR. Sin embargo, dada la forma en quefunciona, el mtodo permite explorar cualquier funcin continua no conve_xa por extraa que sea su forma. A fin de mejorar las posibilidades deobtener un ptimo, la aplicacin del mtodo puede repetirse usando dis -tintos puntos de partida escogidos aleatoriamente.

Como acabamos de ver, cada iteracin del mtodo de H-J requiere deuna bsqueda exploratoria y un avance en la direccin escogida. Sisuponemos que en la primera fase, para la mitad de las variables x. bas_ta explorar en un solo sentido del eje correspondiente y para la otra

mitad es necesario moverse en ambos sentidos (x. + y x. - ), lo quepodra considerarse un caso promedio, sern necesa-rias l,5n evaluaciones de la funcin objetivo en esta fase, en que n esel numero de variables del problema. Por lo tanto, si se realizan N ite_raciones del mtodo, se requerirn en promedio N(l,5n + 1) evaluaciones,dado que una evaluacin adicional es necesaria en la segunda fase deavance (en el peor de los casos seran N(2n + 1). Para evaluar la fun -cin objetivo del PDI es necesario realizar una asignacin de equilibrioa la red, proceso que es computacionalmente caro, por lo que no resultamuy atractivo que el nmero de evaluaciones dependa de n. Sin embargo,Abdulaal y Leblanc (1979) propusieron una modificacin del algoritmo queha dado muy buena resultados prcticos. Ella est basada en la observa^cin de que los flujos de equilibriof*(u) F*(d) no cambian significati^

vamente cuando slo una de las componentes de u d es levemente modifjLcada. Por lo tanto, no es necesario calcular nuevos flujos de equili -brio, para cada modificacin de las componentes de x durante la fase ex^ploratoria, sino que basta con utilizar, para las evaluaciones de la fuiicin obj etivo, los mismos flujos obtenidos para el punto base de la bs_queda. As, cada iteracin del mtodo requiere slo una asignacin deflujos de equilibrio, necesitndose en total slo N asignaciones, inde -pendientemente del numero de variables.

Es importante recalcar que la gran ventaja del mtodo de H-J es queno exige ningn atributo especial a la funcin objetivo del problema a resolver, salvo continuidad. Adems este algoritmo pertenece a la familiade mtodos de coordenadas que son muy sencillos de implementar ya que norequieren el clculo de derivadas o Hessianas de la funcin objetivo (loque en nuestro caso adems no es posible dado que no conocemos la expresin de las funciones f*(u) o F*(d)).

Sin embargo, estas mismas caractersticas pueden constituirse en unproblema que afecte a la eficiencia computacional del algoritmo, ya queeste no hace uso de niguna caracterstica de regularidad que la funcinobjetivo pueda presentar. En especial hemos visto que la funcin objet^vo del PDR es convexa en cada una de las variables d para F dado y algosimilar ocurre en el caso del PDI, cuya funcin objetivo es convexa encada uno de los u para f dado.


14/20

-360-

Esta propiedad es utilizada por el mtodo de optimizacion- equilibrioque describimos a continuacin.

-3.2. Mtodo de descomposicin: optimizacion-equilibrio

Este algoritmo fue originalmente propuesto por Steenbrink, (1974) pa_ra la solucin del PDI y consiste en un procedimiento heurstico de dosfases: En la primera, se supone que el vector u es fijo y se resuelve el'KU para encontrar f*(u). La aagumla faae aupona a au vat qua al vectorf es fijo, e igual al conjunto de flujos de equilibrio determinados en lafase anterior, y procede a calcular los correspondientes valores ptimosde las componentes del vector u. Dado que f es fijo, esto ultimo puederealizarse independientemente para cada arco de la red. Por lo tanto, elalgoritmo consiste en una secuencia de asignaciones de equilibrio a la redseguidas por minimizaciones unidimensionales, para todos los arcosconsiderados en el vector u. Las dos fases del proceso se repiten hastaque se satisfaga algn criterio de convergencia pre-definido.

Dado un valor fijo del vector u, la primera fase, que calcula losflujos de equilibrio f*(u), consiste en resolver el PEU. Esto puede rejlizarse mediante la aplicacin del algoritmo de Frank-Wolfe, tcnica quees hoy da estandard para la solucin de este problema (ver, Fernndez yFriesz, 1983).

Por otra parte, la segunda fase, que supone que el vector f es cons_tante, consiste en la solucin de una serie de problemas de minimizacinunidimensionales e independientes entre s.

Cada uno de estos problemas tiene la forma especificada en (5) cuyasolucin, como vimos en la seccin 2.2. conduce a la expresin analticaexplcita de u (f ) presentada en (6). a

aEsto permite que la segunda fase sea computacionalmente muy eficien.

te ya que se reduce a evaluar una serie de expresiones del tipo (6), enlas que todos los trminos son constantes y f corresponde al valor ob_tenido como resultado de la primera fase.

Si la funcin g (u ) es no lineal, como en (9), u (f ) tiene una eicpresin como la dada en (10).

Harker y Friesz (1984) caracterizan este algoritmo como un juego nocooperativo del tipo Cournot-Nash, entre los usuarios y los planificad^res del sistema de transporte. En dicho juego, cada jugador acta con unavisin miope del comportamiento de s oponente, tratando de maximizar suutilidad individual bajo el supuesto de que sus acciones no producirnninguna reaccin en su contricante. Este juego alcanza una solucin deequilibrio cuando ninguno de los participantes puede aumentar su utilidadmediante un cambio unilateral de estrategia. En nuestro caso, en cadaiteracin del algoritmo, los planificadores no estn tomando en cuenta quelos usuarios reaccionarn con nuevos flujos de equilibrio ante las modificaciones introducidas en el vector u. Harker y Friesz, tambin plaritean que la solucin exacta al PDI corresponder ms bien a la de un


15/20

-361-

juego del tipo Stackelberg y en consecuencia argumentan que el mtodo dedescomposicin, optimizacin-equilibrio, no conducir a la solucin deseida del PDI.

Por su parte Fisk (1984) caracteriza el mtodo de descomposicin cmo una solucin iterativa al problema del "lider y el seguidor". En nues_tro caso, los planificadores representaran al "lider", que optimiza losvalores de u dados ciertos valores de f y los usuarios seran los "segu^Ldores", que reacomodan sus flujos como consecuencia de las decisiones tmadas por los planificadores. Fisk hace notar tambin que el mtodo dedescomposicin tiene la forma del algoritmo de aproximaciones sucesivasusado para resolver el problema de punto fijo y = G(y) (ver Ortega yRheinboldt, 1970), pero que la solucin ptima al PDI, u*, no correspondeal punto fijo de G. Indica tambin que, (de acuerdo a Marcotte) el meto_do de descomposicin corresponde a resolver el problema de Cournot-Nash

usando el enfoque de Gauss-Seidel. Sin embargo, Fisk muestra que este me_todo puede producir resultados intermedios que poseen un valor de la fun-cin objetivo menor que el correspondiente a la solucin de equilibriodel problema Cournot-Nash.

El mtodo puede tambin ser aplicado a la solucin del PDR. En djicho caso, la primera etapa consiste en una asignacin de flujos de equjLlibrio multimodal y la segunda en una minimizacin unidimensional en lasvariables d .

r

La asignacin multimodal se realiza utilizando el mtodo de relaja,cin o diagonalizacin. En nuestro caso y dado que en la primera etapadel mtodo de descomposicin las frecuencias son fijas, el mtodo de dia_

gonalizacin converge en una sola iteracin del siguiente tipo (ver,Florian y Spiess, 1983):


16/20

-362-

Note que dado que en esta etapa las frecuencias d son constantes, elsegundo trmino de la funcin Z es constante y por lo tanto puede eliminar_se de consideracin en el correspondiente problema de minimizacin. Por lotanto, el problema a resolver en el Paso 2 se reduce a:

A continuacin y para completar la primera etapa del mtodo de descomposicin, se procede a asignar la matriz 0-D de viajes en transportepublieo a la red R de rutas de dicho nodo, utilizando los tiempos de viaje cobtenidos arriba. Por lo tanto, como resultado de la primera etapa obtendremos una especificacin del vector de flujos multimodal F.

En la especificacin del PDR hemos supuesto que la particin modal esfija entre transporte privado y transporte pblico y por lo tanto existe una

matriz 0-D fija para cada modo. Es importante anotar que la especiacacin puede ser extendida para incluir particin modal variable. En talcaso, es posible tambin resolver el problema de asignacin multimodal condemanda variable utilizando una variacin del mtodo de diagonalizacinpresentado arriba, que bsicamente consiste en una modificacin del Paso 2,que, implica uncluir en la funcin Z un trmino que considere las demandasvariables por transporte privado.

La segunda etapa del mtodo de descomposicin consiste en resolver unproblema unidimensional en d para cada ruta de transporte publico. Losproblemas a resolver son de la forma:

(17)


17/20

Es interesante hacer notar que en este caso los problemas de mininazacin unidimensional planteado en (17) no son completamente separables enlas variables d , para F dado, ya que al existir lneas comunes, lavariacin de la frecuencia de una lnea especfica afecta a loscostos de operacin, y tiempos de viaje y espera de todos los usuarios, delas lneas que poseen algn segmento comn con ella.

3.3. Aproximacin a una solucin ptima del sistema

Como vimos en la seccin 2.2 una forma de simplificar el PDI es su_poner que la distribucin de flujos sobre la red f*(u) ser de acuerdo aun ptimo de operacin del sistema y no a un equilibrio de usuarios. Conello la formulacin del PDI se simplifica notablemente y su solucin sepuede obtener en forma muy eficiente mediante la utilizacin de algo_ritmos conocidos y probadamente convergentes.

Varios autores (Los, 1979, Marcotte, 1983b Abdulaal y Leblanc, 1984)han propuesto utilizar el resultado obtenido del PDI1 como una aproximacin razonable al resultado del PDI.

3.4. Acotamiento del PDI

Harker y Friesz (1984) proponen utilizar los mtodos descritos en lospuntos 3.2 y 3.3 para acotar la solucin exacta al PDI.

Los citados autores justifican este enfoque basados en los siguien-tes argumentos:

i ) El mtodo de H-J es un procedimiento heurstico que no asegura laobtencin de la solucin exacta al PDI y adems es demasiado caroen trminos computacionales como para ser aplicado en el caso deredes de tamao real.

ii ) El enfoque simplificado, que considera una distribucin de flujos deacuerdo a un ptimo del sistema, entrega una solucin con un va_ lorque constituye una cota inferior para la solucin exacta al PDI. Estoes obvio si se considera que ningn otro principio de distribu_ cinde flujos puede presentar un costo total de operacin menor. As,para cualquier valor dado del vector u, el costo total de ope racines mnimo cuando los flujos se distribuyen de acuerdo a un ptimodel sistema.

iii) El mtodo de descomposicin optimizacin-equilibrio no es capaz deentregar el valor de la solucin exacta al PDI, pero sin embargo,provee una cota superior para esta.

-363-


18/20

-364-

Este enfoque presenta la dificultad de que el rango definido por lasdos cotas puede ser demasiado amplio en casos con elevada congestin y laeleccin del vector u dentro de dicho rango plantea graves problemas de de_finicion.

4. Agradecimientos

El presente trabajo fue realizado como parte de una investigacin quecuenta con el financiamiento del Departamento de Investigaciones de la Universidad Catlica de Chile (DIUC), el Fondo Nacional de Desarrollo Tecnol_gico y el International Development Research Center del Gobierno Canadierise.

Referencias

ABDULAAL, M.S. y LEBLANC, L.J. (1979) Continuous equilibrium networkdesign models. Transportation Research, Vol 13B, 19-32.

BARD, J.F. y FALK, J.E. (1982) An explicit solution to the multilevelprogramming problem. Computers and Operations Research, Vol 9t 771C

DE CEA, J. y BUNSTER, J.P. (1985) Asignacin todo o nada a redes detransporte publico: tratamiento de lneas comunes y transbordos.Primer Congreso Iberoamericano de Mtodos Computacionales en Inge-niera, Madrid, 1 - 5 de Julio 1985, Espaa.

ELTON, P. (1983) Anlisis de Mtodos Continuos de Solucin al Problemade Diseo de Redes. Tesis de Ingeniero Civil, Departamento de Inge_niera de Transporte, Pontificia Universidad Catlica de Chile, Saritiago.

FERNANDEZ, J.E. (1982) Peculiaridades de la aplicacin del mtodo deBranch and Bound al diseo ptimo de redes de transporte. Apuntesde Ingeniera 7, 107-147.

FERNANDEZ, J.E. y FRIESZ, T.L. (1983) Equilibrium predictions intransportation markets: the state of the art. TransportationResearch, Vol. 17B.N2, 155-172.

FERNANDEZ, J.E. (1984) Mtodos de diseo de redes: aplicaciones alcaso de transporte. Segundo Congreso Latinoamericano de Investiga-cin Operativa e Ingeniera de Sistemas, Buenos Aires, 20-24 Agosto1984, Argentina.

FERNANDEZ. J.E. (1985) Caractersticas computacionales de heursticascontinuas para el diseo de redes de transporte. Primer CongresoIberoamericano de Mtodos Computacionales en Ingeniera, Madrid, 1 -5 Julio 1985, Espaa.


19/20

-355-

FISK, C.S. (1984) Game theory and transportation systems modelling.Transportation Research, Vol, 18B, N4/5, 301-313.

FL0R1AN, M. y SPIESS, H. (1983) On binary mode choice/assignmentmodels. Transportation Science, Vol. 17, Nl, 32-46.

FLORIAN, M., GUELAT, J. y SPIESS, H. (1985) An efficiente implemen-tation of the "Partan" variant of the linear approximation raethodfor the network equilibrium problem. Publication N 395, Centre deRecherche sur les Transports, Universit de Montreal, Canad.

GUTIRREZ, F.R. (1982) Anlisis de Mtodos de Solucin al Problemade Diseo de Redes. Tesis de Ingeniero Civil, Departamento de Iiigeniera de Transporte, Pontificia Universidad Catlica de Chile,Santiago.

HARKER, P.T. y FRIESZ, T.L. (1984) Bounding the soluton ofthe continuous network design problem. En J. Volmuller y R.Hamerslag (eds.), Proceedings of the Ninth International Symposiumon Transportation and Traffic Theory. VNU Science Press, Uthrech.

H00KE, R. y JEEVES, T. (1961) Direct search solution of numericalstatistical problems. Journal of the Association of ComputerMachinery, Vol 8, 219-229.

LEBLANC, L.J., MORLOK, E. y PIERSKALLA, W. (1975) An efficientapproach to solving the road network equilibrium traffic assignmentproblem. Transportation Science, Vol 9, 309-318.

LEBLANC, L.J. y ABDULAAL, M. (1984) A comparison of user-optimumversus system-optimum traffic assignment in transportation networkdesign. Transportation Research, Vol. 18B, N 2, 115-121.

LOS, M. (1979) A discrete convex programming approach to the simul-taneous optimization of land-use and transportation. TransportationResearch, Vol. 13B , 33-48.

MARCOTTE, P.(1983a) An analysis of heuristics for the network designproblem. En V.F. Hurdle, E. Hauer y G. N. Steuart (eds.), Proceedings ofEight International Symposium on Transportation and Traffic Theory.University of Toronto Press, Canad.

MARCOTTE, P. (1983b) Network optimization with continuous controlparameters. Transportation Science, Vol. 17, 181-197.

ORTEGA, J. y RHETNBOLDT, W. (1970) Iterativa Solution of NonlinearEquations in Several Variables. Academic Press, Nueva York.

STEENBRINK, P.A. (1974) Optimization of Transport Networks, Wiley,Nueva York,


20/20

Documents

20 - Diseño de redes de transporte con congestión