Route atribuição - Route assignment

Atribuição da rota , escolha de rota , ou alocação de tráfego diz respeito à selecção de rotas (alternativas chamado caminhos) entre origens e destinos em redes de transporte . É a quarta etapa no convencional transporte previsão de modelo, após geração de viagem , distribuição viagem , e escolha modo . A análise intercâmbio zonal de distribuição de viagens fornece tabelas viagem origem-destino. Análise de escolha do modo diz que os viajantes vão usar que modo . Para determinar as necessidades de instalação e os custos e benefícios, precisamos saber o número de viajantes em cada rota e ligação da rede (a rota é simplesmente uma cadeia de ligações entre uma origem e destino). Precisamos realizar o tráfego (ou viagem) atribuição. Suponha que exista uma rede de auto-estradas e sistemas de trânsito e uma proposta disso. Em primeiro lugar, quero saber o padrão atual de atraso de tráfego e, em seguida, o que aconteceria se a adição foram feitas.

atribuição automática

técnicas de longa data

O problema de estimar quantos usuários estão em cada rota é de longa data. Planejadores começaram a olhar duro para ele como auto-estradas e vias expressas começou a ser desenvolvido. A rodovia ofereceu um nível superior de serviço sobre o sistema viário local, e desviou o tráfego a partir do sistema local. Em primeiro lugar, foi o desvio da técnica. Foram utilizadas razões de tempo de viagem, temperado por considerações de custos, conforto e nível de serviço .

Os Chicago Área de Estudo Transporte pesquisadores (CATS) desenvolveram curvas de desvio para freeways contra ruas locais. Havia muito trabalho na Califórnia, também, para a Califórnia teve as primeiras experiências com o planejamento freeway. Além do trabalho de um tipo de desvio, os CATS atacou alguns problemas técnicos que surgem quando se trabalha com redes complexas. Um dos resultados foi o algoritmo de Bellman-Ford-Moore para encontrar caminhos mais curtos em redes.

A questão da abordagem desvio não lidar com foi o feedback da quantidade de tráfego em links e rotas. Se uma grande quantidade de veículos tentar usar uma instalação, a instalação torna-se congestionadas e viagens aumenta o tempo. Na ausência de alguma forma a considerar feedback, estudos iniciais de planejamento (na verdade, a maioria no período 1960-1975) ignorou feedback. Eles usaram o algoritmo de Moore para determinar caminhos mais curtos e atribuiu todo o tráfego para caminhos mais curtos. Isso é chamado de tudo ou cessão nada porque quer todo o tráfego de i para j se move ao longo de uma rota ou não.

O tudo-ou-nada ou menor atribuição caminho não é trivial de uma visão técnico-computacional. Cada zona de trânsito está ligada a n - 1 zonas, de forma que há numerosos caminhos a serem considerados. Além disso, estamos em última análise, interessados no tráfego em links. A ligação pode ser uma parte de vários caminhos, e ao longo de percursos de tráfego tem que ser somadas ligação por ligação.

Um argumento pode ser feito favorecendo a abordagem de tudo ou nada. Ele vai desta forma: O estudo de planejamento é apoiar investimentos de modo que um bom nível de serviço está disponível em todos os links. Usando os tempos de viagem associados com o nível planejado de serviço, os cálculos indicam como o tráfego fluirá uma vez melhorias estão no lugar. Sabendo as quantidades de tráfego em links, a capacidade de ser utilizados para atender o nível de serviço desejado pode ser calculado.

procedimentos heurísticos

Para ter em conta o efeito da carga de tráfego em tempos de viagem e equilíbrios de trânsito, várias heurísticas foram desenvolvidos procedimentos de cálculo. Uma heurística procede de forma incremental. O tráfego a ser atribuído é dividido em partes (geralmente 4). Atribuir a primeira parte do tráfego. Calcule novos tempos de viagem e atribuir a próxima parte do tráfego. O último passo é repetido até que todo o tráfego é atribuído. Os GATOS utilizada uma variação sobre este; atribuiu linha por linha na tabela de OD.

A heurística incluído na coleção FHWA de programas de computador procede de outra maneira.

• 0. Comece por carregar todo o tráfego usando um procedimento de tudo ou nada.
• 1. Calcule os tempos de viagem resultantes e transferir tráfego.
• 2. Agora, começar a transferir o uso de pesos. Calcule os ponderados tempos de viagem nos dois carregamentos anteriores e usá-las para a próxima missão. A última iteração recebe um peso de 0,25 e o anterior obtém um peso de 0,75.
• 3. Continuar.

Esses procedimentos parecem funcionar “muito bem”, mas eles não são exatas.

algoritmo de Frank-Wolfe

Dafermos (1968) aplicou o algoritmo de Frank-Wolfe (1956, Florian 1976), que pode ser usado para lidar com o problema de equilíbrio de tráfego. Suponha que estamos considerando uma rede de auto-estrada. Para cada link existe uma função afirmando a relação entre resistência e volume de tráfego. O Bureau de Estradas Públicas (BPR) desenvolveu um link (arco) de congestionamento (ou volume-delay, ou link performance) função, que vamos chamar de S _um (v _um )

${\ S_ displaystyle {a} \ esquerda ({v_ {a}} \ direita) = t_ {a} \ esquerda ({1 + 0,15 \ esquerda ({\ frac {v_ {a}} {C_ {a}}} \ right) ^ {4}} \ right)}$

• t _um = tempo de viagem livre fluxo no link de um por unidade de tempo
• v _um = volume de tráfego na ligação um por unidade de tempo (um tanto mais exacta: Fluxo de tentar usar ligação um ).
• c _um = capacidade de ligação a , por unidade de tempo
• S _um (v _um ) é o tempo médio de viagem de um veículo por ligação a

Existem outras funções de congestionamento. Os gatos tem sido usado por muito tempo uma função diferente da que utilizada pela BPR, mas parece haver pequena diferença entre os resultados obtidos quando os GATOS e funções BPR são comparados.

atribuição de equilíbrio

Para atribuir o tráfego para os caminhos e as ligações que temos de ter regras, e há o conhecido equilíbrio Wardrop (1952) condições. A essência delas é que os viajantes vão se esforçar para encontrar o caminho mais curto (menor resistência) da origem ao destino, eo equilíbrio da rede ocorre quando nenhum viajante pode diminuir o esforço de viagem, mudando para um novo caminho. Estes são denominados condições óptimas de utilizador, para nenhum utilizador vai ganhar alterem caminhos de viagem para uma vez que o sistema está em equilíbrio.

O usuário equilíbrio ideal pode ser encontrado resolvendo o seguinte problema de programação não-linear

${\ Displaystyle \ min \ soma _ {{a} \ int _ {0} ^ v_ {{a}} {S_ {a} \ esquerda (x \ direita)}} dx}$

sujeito a:

${\ Displaystyle v_ {a} = \ soma _ {i} {\ soma _ {J} {\ soma _ {r} {\ alfa _ {ij} ^ {AR} x_ {ij} ^ {r}}}} }$

${\ Displaystyle \ sum _ {r} {x_ {ij} ^ {r} = T_ {ij}}}$

${\ Displaystyle v_ {a} \ GEQ 0, \; x_ {ij} ^ {r} \ 0} GEQ$

onde é o número de veículos no caminho r de origem i para o destino j . Assim, a restrição (2) diz que todas as viagens devem ocorrer - i = 1 ... n; j = 1 ... n${\ Displaystyle x_ {ij} ^ {r}}$

${\ Displaystyle \ alpha _ {ij} ^ {ar}}$= 1 se uma ligação está no caminho r de i para j; zero nos outros casos. Então restrição (1) resume o tráfego em cada link. Há uma restrição para cada ligação na rede. A restrição (3) assegura nenhum tráfego negativo.

Exemplo

Um exemplo de Eash, Janson, e Boyce (1979) vai ilustrar a solução para o problema programa não linear. Existem duas ligações de nó de um nó a 2, e não é uma função da resistência para cada ligação (ver Figura 1). As áreas sob as curvas da Figura 2 corresponde à integração de 0 a um de uma equação, que soma a 220.674. Note que a função de ligação b é traçado no sentido inverso.

${\ S_ displaystyle {a} = 15 \ esquerda ({1 + 0,15 \ esquerda ({\ frac {v_ {a}} {1000}} \ direita) ^ {4}} \ direita)}$

${\ Displaystyle S_ {b} = 20 \ esquerda ({1 + 0,15 \ esquerda ({\ frac {v_ {b}} {3000}} \ direita) ^ {4}} \ direita)}$

${\ Displaystyle v_ {a} + v_ {b} = 8000}$

Figura 1: Two rede de rotas

Figura 2: Solução gráfica para o equilíbrio Atribuição Problema

Figura 3: Atribuição de veículos que não satisfaçam a condição de equilíbrio

No equilíbrio existem 2.152 veículos na ligação a e 5847 em ligação b . O tempo de viagem é o mesmo em cada rota: cerca de 63.

A Figura 3 ilustra uma atribuição de veículos que não é consistente com a solução de equilíbrio. As curvas são inalteradas. Mas com a nova alocação de veículos às rotas a área sombreada tem de ser incluído na solução, então a solução Figura 3 é maior do que a solução na Figura 2 pela área da área sombreada.

atribuição de trânsito

Existem também métodos que foram desenvolvidos para atribuir os passageiros a veículos de trânsito.

Integrar opções de viagem

O modelo de planejamento de transportes urbanos evoluiu como um conjunto de passos a serem seguidos, e os modelos evoluiu para o uso em cada etapa. Às vezes havia passos dentro passos, como foi o caso para a primeira declaração do modelo de Lowry . Em alguns casos, constatou-se que passos podem ser integrados. De modo mais geral, os passos resumo das decisões que podem ser feitas ao mesmo tempo, e seria desejável para melhor replicar que na análise.

modelos de demanda desagregados foram inicialmente desenvolvidos para tratar o problema modo de escolha. Esse problema assume que um decidiu fazer uma viagem, onde essa viagem vai, e em que momento a viagem será feita. Eles têm sido usados ​​para tratar o contexto mais amplo implícita. Tipicamente, um modelo aninhado será desenvolvido, por exemplo, começando com a probabilidade de uma viagem a ser feita, em seguida, examinar a escolha entre os lugares, e, em seguida, o modo de escolha. O tempo da viagem é um pouco mais difícil de tratar.

modelo de entropia duplamente constrangida de Wilson tem sido o ponto de partida para esforços a nível agregado. Esse modelo contém a restrição

${\ Displaystyle T_ {ij} C_ {ij} = C}$

onde o são os custos de deslocação da ligação, refere-se ao tráfego em um link, e C é uma restrição de recursos para ser dimensionada quando ajuste do modelo com os dados. Em vez de usar essa forma da restrição, a função de resistência monótona crescente utilizado em alocação de tráfego pode ser usado. O resultado determina movimentos zona para zona e atribui o tráfego para redes, e isso faz muito sentido da maneira como se poderia imaginar que o sistema funciona - o tráfego zona para zona depende da resistência ocasionada pelo congestionamento. ${\ Displaystyle c_ {ij}}$${\ Displaystyle t_ {ij}}$

Em alternativa, a função de resistência de ligação poderá ser incluída na função de objectivo (e a função de custo total eliminada das restrições).

A abordagem da escolha desagregada generalizada evoluiu como tem uma abordagem agregada generalizada. A grande questão é sobre as relações entre eles. Quando usamos um modelo macro, gostaríamos de conhecer o comportamento desagregada ele representa. Se estamos fazendo uma análise micro, gostaríamos de saber as implicações totais da análise.

Wilson deriva um modelo de gravidade semelhante com os parâmetros ponderados que dizem algo sobre a atratividade de origens e destinos. Sem muita matemática podemos escrever probabilidade de declarações escolha com base na atratividade, e estes tomam uma forma semelhante a algumas variedades de modelos de demanda desagregar.

demanda de viagens integrando com atribuição de rota

Há muito que se reconheceu que a demanda de viagens é influenciado pela oferta de rede. O exemplo de uma nova abertura da ponte onde ninguém foi antes de induzir o tráfego adicional foi observado durante séculos. Muita investigação tem ido para desenvolver métodos para permitir que o sistema de previsão para explicar diretamente para esse fenômeno. Evans (1974) publicada uma dissertação de doutoramento em uma combinação matematicamente rigorosa do modelo de distribuição de gravidade com o modelo de atribuição de equilíbrio. A mais antiga citação dessa integração é o trabalho de Irwin e Von Cube, como relatado por Florian et al. (1975), que comentar o trabalho de Evans:

"O trabalho de Evans lembra um pouco os algoritmos desenvolvidos por Irwin e Von Cube [‘Restraint Capacidade em programas de atribuição de modo multi-viagem’HRB Bulletin 347 (1962)] para um estudo de transporte de Toronto, Canadá. O seu trabalho permite feedback entre congestionada distribuição de cessão e viagem, embora eles se aplicam procedimentos seqüenciais. Partindo de uma solução inicial do problema de distribuição, as viagens Interzonais são atribuídos às rotas mais curtas iniciais. para sucessivas iterações, novos caminhos mais curtos são computados, e os seus comprimentos são usados ​​como tempos de acesso para a entrada do modelo de distribuição. os novos fluxos Interzonais são então atribuídos em alguma proporção das rotas já foram encontrados. o procedimento é interrompido quando os tempos Interzonais para iteração sucessiva são quase iguais ".

Florian et al. proposto um modo um tanto diferente para resolver a tarefa de distribuição combinado, aplicando directamente o algoritmo de Frank-Wolfe. Boyce et al. (1988) resumem a pesquisa sobre problemas de equilíbrio da rede, incluindo a atribuição com a demanda elástica.

Discussão

Um problema de três ligação não pode ser resolvido graficamente, ea maioria dos problemas de rede de transporte envolvem um grande número de nós e links. Eash et al., Por exemplo, estudou a rede viária em DuPage County, onde havia cerca de 30.000 ligações de sentido único e 9.500 nós. Como os problemas são grandes, é necessário um algoritmo para resolver o problema de atribuição, eo algoritmo de Frank-Wolfe (com várias modificações modernas desde o primeiro publicado) é usado. Comece com uma atribuição tudo ou nada, e depois seguir a regra desenvolvido por Frank-Wolfe para iterar em direção ao valor mínimo da função objetivo. (O algoritmo aplica soluções viáveis ​​sucessivas para alcançar convergência para a solução óptima. Ele usa um procedimento de busca eficiente para mover o cálculo rapidamente para a solução óptima.) Os tempos de viagem correspondem às duas variáveis ​​deste problema de programação.

É interessante que o algoritmo de Frank-Wolfe estava disponível em 1956. A sua aplicação foi desenvolvida em 1968, e levou quase mais duas décadas antes do primeiro algoritmo de atribuição de equilíbrio foi incorporado em software de planejamento de transporte comumente usado ( Emme e Emme / 2 , desenvolvidos Florian e outros em Montreal). Nós não gostaria de tirar qualquer conclusão geral a partir da observação aplicação lenta, principalmente porque podemos encontrar exemplos contrários sobre o ritmo eo padrão de desenvolvimento técnica. Por exemplo, o método simplex para a solução de problemas de programação linear foi elaborado e amplamente aplicado antes do desenvolvimento de grande parte da teoria de programação.

A declaração do problema e algoritmo tem aplicações gerais em todo engenharia civil - hidráulica, estruturas e construção. (Ver Hendrickson e Janson 1984).

Veja também

• Routing (redes de computadores)

Referências

• Dafermos, Stella. C. e FT Sparrow O tráfego Assignment Problem para uma rede geral.”J. da Res. do National Bureau of Standards, 73B, pp. 91-118. 1969.
• Florian, Michael ed., O tráfego de equilíbrio Métodos, Springer-Verlag, 1976.
• Wardrop, JC Alguns aspectos teóricos da Estrada Research Traffic “, Proceedings, Institution of Civil Engineers Parte 2, 9, pp. 325-378. 1952
• Eash, Ronald, Bruce N. Janson, e David Boyce equilíbrio Trip Atribuição: Vantagens e implicações para a prática, Transportation Research Registro 728, pp 1-8 de 1979..
• Evans, Suzanne P.. "Derivação e Análise de alguns modelos para combinar Distribuição de viagem e Assignment". Transportation Research, Vol 10, pp 37-57 1976
• Hendrickson, CT e BN Janson, “uma rede comum de fluxo Formulação de problemas de engenharia Vários civis” Sistemas de Engenharia Civil 1 (4), pp. 195-203, 1984