Programación dijkstra

ufeffI. Introducción:

En transporte es de especial interés para muchos profesionales saber como se comportan los equilibrios espontáneos que generan las decisiones individuales de los usuarios. Para calcular estos equilibrios existen distintas maneras para abordar el problema de calculo dependiendo de la estructura de costos de la red. En particular, par alas redes de transporte público, lasinteracciones de los flujos de las distintas secciones de línea no son simétricas entre distintos pares de arcos, de forma que se genera un problema particular para resolver. En estos casos se utiliza el algoritmo de Diagonalización. El objetivo de este informe es explicar como funciona este algoritmo, sus particularidades y resultados, además de una comparación con su extensión streamlined. Paraello, el trabajo comprende además una versión programada del algoritmo de diagonalización, el cual genera a partir de una red de nodos y arcos la red equivalente de secciones de línea de TP y a partir de ella utilice la matriz de demanda para establecer el equilibrio espontaneo de los usuarios.





II. Marco Teórico:

Las redes de transporte público presentan se trabajan de formadistinta a las redes comunes y corrientes. Esto se debe a las decisiones que pueden tomar los usuarios frente a distintas situaciones, por ejemplo cuando un usuario viaje de un nodo (por ejemplo 1) a otro nodo no consecutivo (por ejemplo 3) este tiene la opción de hacerlo en una misma línea sin realizar trasbordo en algún nodo de la ruta (por ejemplo 2) o cambiarse de línea según estime conveniente. Parael caso en que no se cambia se agrega un arco a la red que va desde el nodo de origen hasta el destino, siempre y cuando lo haga en la misma línea sin hacer trasbordos. Esto corresponde a la primera parte del problema cuando se aborda una red de transporte público, donde se toma la red G(N, A) y se transforma a G(N, L) con las secciones de cada línea que correspondan. En la figura se muestra unared G(N, A) con una sola línea y como queda la red G(N, L) correspondiente, que considera las posibles decisiones que pueden tomar los usuarios.




Luego de generar la red considerando las distintas secciones para cada línea, viene el paso donde se calculan los costos para cada sección de arco, los que tienen una estructura bastante distinta a los costos para redes de transporte privado. Enprimer lugar considera un costo fijo correspondiente a la tarifa, y de un costo asociado al tiempo de viaje (este se calcula a través de la relación entre el tiempo de viaje y el valor subjetivo del tiempo para los individuos). Luego tiene un costo por el tiempo de espera que es calculado a partir de la razón entre un parámetro representado por alpha y la frecuencia, donde alpha depende de laregularidad de las llegadas de los buses. La ultima parte de la estructura de los costos en la red de TP es una expresión as compleja que considera la congestión en los arcos de la red. Esta corresponde a la multiplicación del parámetro beta por la razón entre la suma de los flujos de las secciones de línea compitentes y de la misma y la capacidad elevada a un parámetro n. de forma mas general, sepresenta la estructura de costos de la siguiente manera:










Una vez generada la red G(N, L) y asociado el costo a cada una de las secciones de línea, esta armada la red de TP, de ese punto en adelante lo que se necesita es asociar los flujos en un estado de equilibrio (en esta instancia se calculan solo los flujos en equilibrio de usuarios según el primer principio de Wardrop), locual se realiza utilizando el algoritmo programado de Diagonalización.

Antes de estudiar este ultimo algoritmo, es importante tener en cuenta como funciona el algoritmo de Frank-Wolfe. FW funciona de forma similar al método del gradiente. En primera instancia recibe un conjunto de flujos factibles para el problema. Luego entra en la etapa de aproximación lineal en la cual busca la ruta...