Nose

ASIGNACION DE VIAJES A REDES DE TRANSPORTE PRIVADO CONGESTIONADAS: ALGORITMOS

1

Métodos de Solución del Problema de Equilibrio de Usuarios en una Red de Transporte 1) Métodos heurísticos (Capítulo 5.1 de Sheffi. )

Iteraciones Todo o Nada Promedio“Todo o Nada” últimas iteraciones Asignación Incremental por par O-D

2

2) Métodos que usan el Enfoque de la Programación Matemática. a)Algoritmo de Frank-Wolfe: Adaptación del Método del Gradiente Método iterativo de dos fases para encontrar una solución al Problema de Optimización Equivalente (P.O.E.):
FASE I : Determinación de una dirección de descenso de

la F.O.
FASE II: Cálculo del avance en la dirección determinada

en la fase 1 para minimizar el valor de la F. O.
3

Algoritmo de Frank-Wolfe (Continuación):
FASEI: Se resuelve una aproximación lineal del problema

original (P.O.E.), en un punto inicial dado, (sujeto a las mismas restricciones: solución factible). La solución a esta aproximación, combinada con la solución anterior define la dirección de búsqueda.
FASE II: Se minimiza el valor de la F. O. dentro del tramo

unidimensional factible definido por la dirección de búsqueda. Determina cuántomoverse en la dirección de búsqueda de modo de minimizar la función objetivo original. 4

Algoritmo de F-W (Representación Gráfica): Z(x) F.O. Z(x) convexa
Ω definido por restricciones lineales; Ω convexo

Z(Xk) Solución inicial Factible Xk

Ω
5

Algoritmo de F-W (Aproximación Lineal):

z(x)
Z(Xk) Solución inicial Factible Xk

Plano tangente (ZL(x)) a la F.O. en Xk ; ZL(x) ≤ Z(x)∀ x∈ Ω

Ω

6

Algoritmo de F-W. FASE I : Dirección de Descenso
Aprox. Lineal a la F.O.: zL(x-xK) PROBLEMA LINEAL

zL(xk)

Ω

zL(yk)

xk

(yk - xk) Dirección

yk Sol. Auxiliar
7

Algoritmo de F-W. FASE II : Min. Unidimensional
Nueva Solución: X(K+1) = xk+λ(yk - xk)

z (yk - xk) z(yk)

zL(xk) = Z(xk)

z(xk +λ(yk - xk))
Ω

xk+λ(yk - xk)
Solución inicial Factible Xkyk Sol. Auxiliar
8

Algoritmo de F-W. FASE II : Min. Unidimensional

z(x)
z(xk) z(xk +λ(yk - xk))

Solución inicial Factible Xk

Ω

xk+λ(yk - xk)

yk Sol. Auxiliar
9

Algoritmo de F-W.: Final Iteración k
z(x)

Z(Xk+1) Nueva Solución Factible Xk+1 Ω

10

Descripción Analítica del Algoritmo de Frank-Wolfe
Problema de Optimización Equivalente Transformada de Beckmann Z(X)Min :

fa ⎧ ⎫ ⎪ ⎪ ⎨ Z = ∑ ∫ ca ( x)dx ⎬ a 0 ⎪ ⎪ ⎩ ⎭

s.a :

p∈Pw

∑h

p

⎫ ⎪ ⎪ fa = ∑δap ⋅ hp , ∀a ∈ A⎬ p∈P ⎪ ⎪ hp ≥ 0, ∀p ∈ P ⎭ = Tw , ∀w ∈W

Conjunto de restricciones lineales AX = b

11

Descripción Analítica del Algoritmo de Frank-Wolfe
Formulación compacta del P.O.E.:

Min : Z ( x ) s.a. : A x = b;

x≥0

Z(X): Transformada de Bechmann Función no lineal en x,continua, diferenciable y convexa

A: matriz de (m n) parámetros (δap) x: vector de (n 1) variables (flujos en arcos, a ∈ A) b: vector de (m 1) elementos (datos de viajes O-D)
x x x

12

Fase 1: Fase de aproximación lineal (búsqueda de dirección)
Dada una solución factible xk, sea yk la solución al siguiente problema de programación lineal:

Min : s.a. :

ZL ( yk ) A y k = b;
k

ZL(y)corresponde a una aproximación lineal de Z en xk (Plano yk ≥ 0 tangente a Z(x) en xk).
k k T

ZL ( y ) = Z ( x ) +∇Z ( x

) (y

k

−x

k

)

La nueva solución yk será factible para el problema original (P.O.E.) y recibe el nombre de Solución Auxiliar . ZL(y) es una función lineal en la variable (yk). Notar que: xk, Z(xk) y ∇Z(xk) son constantes.

13

Fase 1: Fase deaproximación lineal (continuación)
Por lo tanto: Minimizar ZL(y) es equivalente a minimizar:

∇Z ( x

k T

)

⋅y

k

Así, la solución auxiliar se puede obtener resolviendo:

Min : ∇ Z ( x ) ⋅ y
k T

k

s.a . :
Pero recordemos que:

A y = b;
k

y ≥0
k

∂ Z ({ f a } ) ∂ fa

= ca ( f a ) , ∀a ∈ A
14

Fase 1: Fase de aproximación lineal (continuación)
Por lo tanto:

∇ Z...