´fico I El problema del tra

El problema de la planificaci´on de tr´afico es muy importante y puede tratarse mediante programaci´on matem´atica. El modelo cl´asico de transporte usado en las aplicaciones m´as importantes consta de cuatro etapas: 1. Fase de generaci´ on de viajes. Esta etapa comienza por considerar un sistema en red con zonas, y una base de datos de cada zona de estudio. Estos datos, que incluyen informaci´on sobre la actividad econ´omica, social, educacional, recreacional, centros comerciales, etc., se usan para estimar los viajes generados y con destino en cada zona del estudio. 2. Fase de distribuci´ on. La fase siguiente consiste en la distribuci´on de estos viajes a destinos particulares, es decir, su distribuci´on espacial, conduciendo a una matriz de viajes. 3. Divisi´ on modal. En esta fase se distribuyen los viajes entre diferentes modos de transporte. Se obtienen las matrices or´ıgenes-destinos para cada modo de tranporte. Sus elementos dan los n´umeros de viajes asociados a cada modo de transporte para cada par origen-destino ω. 4. Asignaci´ on. Finalmente, la u´ltima etapa requiere la asignaci´ on de estos viajes a la red de transporte. En este ejemplo se asignan veh´ıculos privados a la red de transporte. 88

´fico II El problema del tra

Se debe introducir un principio que gobierna el comportamiento de los usuarios en su elecci´on de la ruta de la red de transporte. Wardrop (1952) fu´e el primero en enunciar formalmente este principio, que afirma: “Bajo condiciones de equilibrio, el tr´afico se autodistribuye en redes congestionadas de tal forma que ning´ın viajante individual pueda reducir su coste mediante el cambio de rutas.” Este principio ha sido utilizado como plataforma para construir modelos de asignaci´on equilibrada. Un corolario de este principio es que si todos los viajantes perciben los costes de la misma forma, bajo condiciones de equilibrio, el tr´afico se autoajusta en redes congestionadas de forma tal que todas las rutas utilizadas entre un par O-D tienen id´enticos y m´ınimos costes, mientras que todas las rutas no usadas tienen costes mayores o iguales. Beckman et al. (1956) formularon el siguiente principio de optimizaci´on para expresar la condici´on de equilibrio derivada del primer principio de Wardrop. Este modelo predice el nivel de utilizaci´on de los diferentes arcos de la red. Por ello, puede ser utilizado para responder a preguntas como: ¿Que suceder´ıa en el nivel de servicio de la red si se construye una nueva carretera o se modifica la capacidad de una existente? 89

´fico III El problem del tra Principales elementos de este problema

1. Datos: (A, N ): un grafo dirigido (A, N ), que puede verse como un modelo de la red de carreteras. El conjunto de arcos A del grafo representa los enlaces de la red, tales como carreteras, autov´ıas, calles, etc. El conjunto de nodos N del grafo representa puntos de intersecci´on o los llamados centroides que representan zonas de estudio (or´ıgenes y destinos). W : el conjunto de pares or´ıgenes-destinos. dω : matriz dato, que representa el n´umero de viajes en coche desde i a j, para cualquier par origen-destino ω = (i, j). La matriz de or´ıgenes-destinos {dω }ω∈W se obtiene en la fase de divisi´on modal. Ca(fa): una funci´on de coste que da el retraso en el arco a ∈ A, para cada arco (i, j) ∈ A, como una funci´on del flujo total fa en ese arco a. Se supone que los veh´ıculos utilizan cualquier carretera. Por tanto, la carretera se congestiona gradualmente y el retraso en ella aumenta. Rω : el conjunto de rutas simples asociadas a ω = (i, j). 2. Variables: hr : el flujo en la ruta r. fa: el flujo en el enlace a. 90

´fico IV El problema del tra

1. Restricciones: El n´umero de usuarios de un par origen-destino ω es la suma de todos los usuarios en todas las rutas que satisfacen tal par: X

r∈Rω

hr = dω , ∀ω ∈ W.

(95)

Los flujos deben ser no-negativos: hr ≥ 0, ∀r ∈ Rω , ∀ω ∈ W.

(96)

El flujo de cada enlace a es la suma de todas las rutas que lo usan: X

X

w∈W r∈Rω

δa,r hr = fa ∀a ∈ A,

donde δa,r = 1 si r ∈ Rω contiene el arco a. 2. Funci´ on a minimizar: Se minimiza la funci´on: Z =

X

a∈A

Z

fa 0

Ca(x)dx.

(97)

donde Ca, es una funci´on que da el tiempo de viaje asociado al enlace a. Un funci´on usual es: Ca(fa) = c0a + ba(fa/ka)na .

(98)

donde Ca(fa) es el tiempo de viaje en el enlace a para un flujo fa, c0a es el tiempo asociado a enlace libre, ka es la capacidad pr´actica del enlace, y na es una constante. 91

´fico V El problem del tra

Consid´erese el ejemplo de la figura adjunta y sup´ongase que hay 4000 viajes de A a B, y 2500 viajes de A a C. Las rutas disponibles para satisfacer el par de demanda ω1 = (A, B) son r1 = a1, r2 = a2 − a4, y r3 = a3 − a4, y las rutas para el par ω2 = (A, C) son r4 = a2 and r5 = a3. En este ejemplo W = {w1, w2}, y Rω1 = {r1, r2, r3} y Rω2 = {r4, r5}. Las variables de flujo en las rutas son h1, . . . , h5, y las de flujo en l´ınea f1, . . . , f4.

Bypass a1 a4 a2

C

A a3

B

Town-Centre La formulaci´on del problema para este caso es: Minimizar Z = sometido a h1 + h2 + h3 h1 h3 + h5 h1, . . . , h5

= = = ≥

4 Z X i=1

fai 0

Cai (x)dx

4000, h4 + h5 = 2500, f1, h2 + h4 = f2, f3, h2 + h3 = f4, 0.

92

(99)

´fico VI El problem del tra

En este ejemplo se ha utilizado la funci´on (98). N´otese que   na Z Z x fa fa 0     dx 0 Ca (x)dx = 0 ca + ba ka  n +1 a f b a 0  a   = cafa + n a + 1 ka Los par´ametros utilizados son los de la Tabla siguiente: Par´ ametros para las funciones BPR Enlace ka c0a ba na 1 500 5 1 4 2 400 7 1 4 3 400 10 1 4 4 500 2 1 4 La soluci´on se da en la Tabla: Flujos en enlaces a1 3845.913 a2 2354.419 a3 299.667 a4 154.087

93

Flujos en rutas r1 3845.913 r2 154.087 r3 0.000 r4 2200.333 r5 299.667

66

Cap´ıtulo 3. Programaci´ on no lineal

3.6

El problema de la asignaci´ on de tr´ afico

La planificaci´ on del tr´ afico ha motivado un buen n´ umero de modelos matem´aticos. El an´ alisis de estos modelos ayuda a planificar y predecir los efectos que determinados cambios en la red de tr´ afico tendr´ an en la buena marcha de la red. El esquema t´ıpico de planificaci´ on del transporte usado en las aplicaciones consta de cuatro etapas: 1. Fase de generaci´ on de viajes. Esta etapa comienza considerando un sistema de zonificaci´on y una serie de datos relativos a cada zona del estudio. Estos datos, que incluyen informaci´ on sobre la actividad econ´ omica, la distribuci´ on social, los recursos educacionales y l´ udicos, los espacios para compras, se usan para estimar el n´ umero total de viajes generados y atra´ıdos a cada zona bajo estudio. 2. Fase de distribuci´ on. La siguiente etapa consiste en la adjudicaci´ on de estos viajes entre or´ıgenes y destinos, determinando la llamada matriz de viajes origen-destino. 3. Descomposici´ on modal. A continuaci´ on, la descomposici´on modal produce la adjudicaci´ on de viajes a modos diversos. En esta fase las matrices origen–destino se obtienen para cada modo de transporte. Sus elementos son el n´ umero total de viajes por modo de transporte para cada par origen–destino O–D ω. 4. Asignaci´ on. Finalmente, la u ´ltima etapa requiere la asignaci´ on de estos viajes a la red de transporte. Este ejemplo trata sobre la asignaci´ on de autom´ oviles privados a la red de tr´ afico. Debe introducirse un principio que gobierne el comportamiento de los usuarios al elegir la ruta en la red. Wardrop [102]) fu´e el primero en enunciar formalmente este principio: “Bajo condiciones de equilibrio, el tr´ afico se organiza en redes congestionadas de tal modo que ning´ un veh´ıculo puede reducir el tiempo de viaje mediante un cambio de ruta.” Este principio se ha usado como punto de partida para confeccionar modelos de asignaci´on en equilibrio. Un corolario de este principio es que si todos los viajeros perciben el tiempo de los viajes del mismo modo, bajo condiciones de equilibrio, todas las rutas utilizadas entre un par O-D tienen el mismo tiempo m´ınimo mientras las no usadas requieren un tiempo igual o mayor. Beckman et al. [10] formularon el siguiente problema de optimizaci´ on para expresar las condiciones de equilibrio que se derivan del primer principio de Wardrop. Este modelo predice el nivel de uso de los diferentes arcos de la red. As´ı, puede usarse para responder cuestiones como qu´e ocurrir´ıa en el nivel de uso de la red si se construyera una nueva carretera o si la capacidad de una determinada ruta se modificara. Los elementos principales de este problema son: 1. Datos

3.6. El problema de la asignaci´ on de tr´ afico

67

(N , A): una grafo dirigido (N , A), que se entiende como un modelo de la red de tr´ afico con un conjunto de nodos N , y un conjunto de arcos A que representan las calles. El conjunto de nodos N del grafo representan intersecciones o tambi´en los llamados centroides, que indican las zonas del estudio (or´ıgenes y destinos). W : el conjunto de pares or´ıgenes–destinos. dω : datos de entrada que representan el n´ umero de viajes en coche desde el origen i al destino j, para cada par origen–destino ω = (i, j). La matriz de pares origen–destino {dω }ω∈W se obtiene en la fase de distribuci´ on modal. Ca (fa ): una funci´ on de coste que indica el retraso en el arco a ∈ A, para cada arco (i, j) ∈ A, como funci´ on del flujo total fa que lleva el mismo arco a. Rω : el conjunto de rutas para el par ω = (i, j). 2. Variables hr : el flujo en la ruta r fa : el flujo en el arco a 3. Restricciones. El n´ umero de usuarios de un par origen–destino ω es la suma del n´ umero total de usuarios en caminos distintos que satisfacen tal par: hr = dω , ∀ω ∈ W (3.15) r∈Rω

Adem´as, el flujo de cada camino debe ser no negativo: hr ≥ 0, ∀r ∈ Rω , ∀ω ∈ W

(3.16)

El flujo de cada arco a es la suma del flujo en todos los caminos que lo usan: - δa,r hr = fa ∀a ∈ A w∈W r∈Rω

donde δa,r = 1 si r ∈ Rω contiene el arco a, y 0 en otro caso. 4. Funci´ on a optimizar. El problema de asignaci´ on de tr´ afico minimiza la siguiente funci´ on: - . fa Z = Ca (x)dx (3.17) a∈A

0

Como resultado del volumen creciente de tr´afico, la velocidad en los arcos tiende a disminuir. La funci´ on Ca , es decir el tiempo necesario para atravesar el arco a, tiene en cuenta este hecho. Estas funciones en el an´alisis de sistemas

68

Cap´ıtulo 3. Programaci´ on no lineal

Circunvalación a1 a4 a2

Aa

B

C

3

Centro de la ciudad Figura 3.8: Diagrama para la red de carreteras. de tr´ afico son positivas, no lineales y estrictamente crecientes. Los par´ametros que relacionan el tiempo de viaje, Ca , en el arco en funci´ on del flujo fa , en ´el, es el tiempo de viaje libre de flujo, c0a , y la capacidad pr´ actica del arco, ka , que es una medida del flujo a partir del cual, el tiempo de viaje se incrementar´ a muy r´ apidamente si el flujo aumenta. La expresi´ on m´ as com´ un para Ca (fa ), llamada la funci´ on BPR, es $ % na fa Ca (fa ) = c0a + ba (3.18) ka Ejemplo 3.4 (problema de asignaci´ on de tr´ afico). Consid´erese el problema de una ciudad con una v´ıa de circunvalaci´ on y varias rutas centrales seg´ un se ilustra en la Figura 3.8. Imag´ınese que se realizan 4000 viajes desde A hasta B, y 2500 desde A hasta C. Las rutas disponibles para satisfacer la demanda del par ω1 = (A, B) son r1 = a1 , r2 = a2 − a4 , y r3 = a3 − a4 , y las rutas para el par ω2 = (A, C) son r4 = a2 y r5 = a3 . En este ejemplo W = {w1 , w2 }, y Rω1 = {r1 , r2 , r3 } y Rω2 = {r4 , r5 }. Las variables de flujo en los caminos son h1 , . . . , h5 , y las variables de flujo en los arcos son f1 , . . . , f4 . Como $ %n a . fa . fa x Ca (x)dx = c0a + ba dx ka 0 0 $ %na +1 ba fa = c0a fa + na + 1 ka la formulaci´ on completa es como sigue. Minimizar Z=

4 . i=1

sujeto a

0

fai

Cai (x)dx =

-

c0ai fai

a∈A

bai + nai + 1

$

fai kai

%nai +1

(3.19)

h1 + h 2 + h 3

= 4000

h4 + h 5

= 2500

(3.21)

= f1

(3.22)

h1

(3.20)

69

Ejercicios Tabla 3.6: .Par´ ametros para las funciones BPR Enlace a 1 2 3 4

ka 500 400 400 500

c0a 5 7 10 2

ba 1 1 1 1

na 4 4 4 4

Tabla 3.7: Estimaci´ on de los viajes Flujo en los arcos a1 3845.913 a2 2354.419 299.667 a3 a4 154.087

Flujo en las rutas r1 3845.913 r2 154.087 r3 0.000 r4 2200.333 r5 299.667

h2 + h4 h3 + h 5

= f2

(3.23)

= f3

(3.24)

h2 + h 3

= f4

(3.25)

≥ 0

(3.26)

h1 , . . . , h5

En este ejemplo se han usado las funciones en (3.18), y la tabla 3.6 muestra los par´ ametros. La soluci´on correspondiente se encuentra en la tabla 3.7.

Ejercicios 3.1 Una mesa debe pasar a trav´es de un ´angulo recto en un pasillo de A unidades de anchura hacia otro de B unidades de ancho. ¿Cu´ ales son los tama˜ nos de la mesa (a unidades de ancho y b unidades de largo) que permite tal movimiento? 3.2 Se desea construir un hospital entre dos ciudades que distan D entre s´ı. El lugar elegido corresponde al menos contaminado en la l´ınea que une las dos ciudades. Sabiendo que la contaminaci´ on es proporcional a los residuos de las industrias presentes y al inverso de la distancia m´ as 1, y que la segunda ciudad genera 3 veces m´ as actividad industrial que la primera, determinar el lugar o´ptimo para el hospital. 3.3 Encontrar la m´ınima longitud de una escalera que debe apoyarse sobre la pared si una caja de dimensiones a y b est´a colocada justo en el rinc´ on de