Equilíbrio Dinâmico do Usuário (DUE)¶

Para que uma Dynamic Traffic Assignment se torne um DUE, as hipóteses comportamentais sobre como os viajantes escolhem as rotas precisam ser consistentes com o princípio de equilíbrio dinâmico do usuário. Ran e Boyce 1996, formulam a versão dinâmica do equilíbrio do usuário de Wardrop nos seguintes termos: Se, para cada par OD em cada instante de tempo, os tempos reais de viagem experimentados pelos viajantes que partem no mesmo horário forem iguais e mínimos, o fluxo dinâmico de tráfego na rede estará em um estado de equilíbrio dinâmico do usuário (DUE) baseado em tempo de viagem.

Abordagem heurística no Aimsun Next ¶

Essa formulação poderia corresponder aos cenários hipotéticos nos quais aplicações ATMS e ATIS funcionarão e sistemas confiáveis de informação de tráfego/previsão de tráfego se tornarão disponíveis aos viajantes, permitindo que eles ajustem seus comportamentos de acordo. Alternativamente, ela pode ser considerada a realização de um processo no qual os viajantes ajustam suas informações atuais com conjecturas sobre as condições de tráfego esperadas à frente; isso poderia corresponder ao processo seguido por passageiros pendulares que adaptam seu comportamento de acordo com um processo de aprendizado dia a dia, dependendo das flutuações dos padrões de tráfego, até considerarem que nenhuma melhoria adicional é possível. Essa interpretação é implementada em uma abordagem de microssimulação por meio de um procedimento heurístico iterativo que mimetiza o processo de aprendizado dia a dia, levando a uma solução que pode ser interpretada como um DUE, Barcelo e Casas 2002, Liu et al. 2005.

A implementação no Aimsun Next replica a simulação $N$ tempos e custos dos links para cada link $j$, para cada intervalo de tempo $t, t+1, ..., L$ (onde $L = T/t$, $T$ sendo o horizonte de simulação e $t$ o intervalo de tempo definido pelo usuário no qual atualizar caminhos e fluxos de caminho) a cada iteração $n$ são armazenados. Assim, na iteração $n$ os custos dos links da iteração anterior $n-1$ pode ser usado para estimar o custo esperado do link na iteração atual. Seja $S_a^{jl}(v)$ seja o custo atual do link a com fluxo $v$, na iteração $l$ da replicação $j$, então os custos médios dos links para o futuro $L-l$ intervalos de tempo, com base nos custos de link experimentados para o anterior $j-1$ replicações é dado por

O custo de link "previsto" pode então ser calculado como:

O custo resultante do caminho k para o i-ésimo par OD é dado por:

onde, como de costume, a matriz de incidência arco-caminho δ$_{ak}$ é:1 se o link $a$ pertence ao caminho $k$ e 0 caso contrário.

Os custos dos caminhos são os argumentos da função de escolha de rota (logit, C-logit, proporcional, definida pelo usuário, etc.) usada na iteração $l+1$ para dividir a demanda $g_i^{l+1}$ entre os caminhos disponíveis para o par OD $i$.

A implementação padrão na versão atual do Aimsun Next usa uma versão simplificada que consiste em uma função de custo de link definida como:

Onde $c_{it}^{k+1}$ é o custo usando o link i no tempo $t$ na iteração $k+1$, e $c_{it}^k$ e $c_{it}^k$ correspondem, respectivamente, aos custos esperados e experimentados dos links neste intervalo de tempo a partir de iterações anteriores.

Abordagens algorítmicas para DUE ¶

Pode-se demonstrar que a abordagem DUE pode ser implementada em termos da resolução do seguinte modelo matemático:

E as equações de balanceamento de fluxo

Onde, como antes, $f_{rsp}(t)$ é o fluxo no caminho $p$ de $r$ para $s$ origem de partida $r$ no intervalo de tempo $t$, τ$_{rsp}(t)$ é o custo real do caminho a partir de $r$ para $s$ na rota $p$ no intervalo de tempo $t$, θ$_{rs}(t)$ é o custo do caminho mais curto de $r$ para $s$ partindo da origem $r$ no intervalo de tempo $t$, $P_{rs}(t)$ é o conjunto de todos os caminhos disponíveis a partir de $r$ para $s$ no intervalo de tempo $t$, é o conjunto de todos os pares origem-destino $(r,s)$ na rede e $d_{rs}(t)$ é a demanda (número de viagens) de $r$ para $s$ no intervalo de tempo $t$. Pode-se demonstrar que isso é equivalente a resolver um problema de desigualdade variacional de dimensão finita que consiste em encontrar um vetor de fluxos de caminho f* tal que:

Wu et al. 1991, Wu et al. 1998a and 1998b, prove que isso é equivalente a resolver a inequação variacional discretizada:

Onde é o conjunto de todos os caminhos disponíveis. Diversos algoritmos foram propostos para resolver essa desigualdade variacional a partir de algoritmos de projeção: (Wu et al 1991, Wu et al. 1998a, Wu et al. 1998b, Florian et al. 2001) ou métodos de direções alternadas, Lo e Szeto 2002, a várias versões do Method of Successive Averages (MSA), Tong and Wong 2000, Varia e Dhingra 2004, Florian et al 2002, Mahut et al. 2003a, Mahut et al. 2003b, e Mahut et al. 2004. O procedimento MSA redistribui os fluxos entre os caminhos disponíveis em um procedimento iterativo que, na iteração n, calcula um novo caminho mínimo a partir da origem $r$ ao destino $s$ no intervalo de tempo $t$, $c_{rs}(t)$, então o processo de atualização dos fluxos dos caminhos é:

Dependendo dos valores dos coeficientes de ponderação αn, diferentes esquemas MSA podem ser implementados Carey and Ge 2007. Talvez o valor mais típico seja:

Um algoritmo MSA modificado interessante é descrito em Varia e Dhingra 2004, em que o coeficiente de ponderação leva em conta um comprimento de passo variável que depende dos tempos de viagem atuais dos caminhos:

Uma das possíveis desvantagens computacionais dessas implementações de MSA é o número crescente de caminhos no caso de redes grandes; para evitar isso no caso das atribuições DTA no Aimsun Next, o usuário tem a opção de especificar o número máximo K de caminhos a manter para cada par origem-destino; portanto, ao implementar o MSA no Aimsun Next, considerou-se que seria desejável manter esse recurso.

Várias implementações MSA modificadas foram propostas para manter o controle sobre o número de caminhos em algoritmos MSA, Peeta e Mahmassani 1995, Sbayti et al. 2007, porém, possivelmente uma das mais eficientes computacionalmente é a proposta por Florian et al. 2002 (veja também Mahut et al. 2003b e 2004) modificando o algoritmo MSA para manter limitado o número de caminhos alternativos a considerar para cada par origem-destino. Esta variante do algoritmo inicializa o processo com base em um esquema de carregamento incremental que distribui a demanda entre os caminhos mais curtos disponíveis; o processo é repetido por um número predeterminado de iterações, após o qual nenhum novo caminho é adicionado e a fração correspondente da demanda é redistribuída de acordo com o esquema MSA. O MSA modificado funciona da seguinte forma:

Seja K o número máximo de iterações para calcular novos caminhos:

Esta é a versão do algoritmo MSA implementada no Aimsun Next. No entanto, considerando a possibilidade de repetir caminhos mais curtos de uma iteração para a próxima para manter um máximo de K diferentes caminhos mais curtos, uma implementação adequada do algoritmo requer que o número de iterações n é definido por par OD e intervalo de tempo.

No Aimsun Next, está disponível uma modificação do algoritmo MSA chamada WMSA, proposta por Liu et all 2007. O algoritmo MSA na iteração n, 1/n da demanda é deslocada e, em WMSA 2/(n+1) da demanda é deslocada. A próxima figura mostra a quantidade de demanda deslocada em função do número da iteração.

Demanda movida em função do número da iteração usando MSA e WMSA

O critério de convergência ¶

Todas as abordagens propostas para DUE são baseadas em procedimentos de simulação para o processo de carregamento da rede e, portanto, são de natureza heurística, de modo que nenhuma prova formal de convergência pode ser fornecida. Consequentemente, uma forma de determinar empiricamente se a solução alcançada pode ser interpretada em termos de um DUE, no sentido de que "os tempos reais de viagem experimentados pelos viajantes que partem no mesmo horário são iguais e mínimos", pode ser baseada em uma versão ad hoc da função Relative Gap proposta por Janson 1991:

Onde

$f_{rsp}^n(t)$ é o fluxo no caminho p partindo da origem $r$ no instante $t$ na iteração $n$ com destino s.
τ$_{rsp}^n(t)$ é o custo experimentado ou instantâneo do caminho p.
θ$_{rs}^n(t)$ é o custo do caminho mais curto para caminhos que partem da origem r no instante t na iteração n com destino s.

A diferença τ$_{rsp}^n(t)$ - θ$_{rs}^n(t)$ mede o custo excedente experimentado pelo fato de usar um caminho p em vez disso, o caminho mais curto.

Em versões anteriores, o custo do caminho mais curto na fórmula RGap para caminhos que partem da origem θ$_{rs}^n(t)$ era o do caminho com o custo mínimo entre o conjunto de caminhos usados. A partir do Aimsun Next 22, este é o custo do caminho mais curto recém-calculado com os custos atualizados ao final da iteração.

Isso é mais preciso e permite uma melhor avaliação do RGap para pares OD nos quais todos os veículos usam o mesmo caminho. No entanto, você pode observar que o RGap no Aimsun Next 22 é maior e que o DUE realiza mais iterações para convergir. Se isso for uma preocupação, você ainda poderá usar o cálculo anterior adicionando uma nova variável de experimento com o nome $DTARGAPEVALUATION e um valor de RGAP20.

A razão mede o custo excedente total em relação ao custo mínimo total se todos os viajantes tivessem usado os caminhos mais curtos.

O Aimsun Next contém vários critérios de parada como parte do processo DUE. São eles:

Número máximo de iterações - O processo DUE será interrompido após o número máximo de iterações, mesmo que as outras condições de parada não sejam atendidas.
Um Relative Gap global - Este é o principal critério de parada. Ele pode ser definido no aba Dynamic Traffic Assignment do editor de experimento para um número específico n de iterações consecutivas.
Um critério opcional de fluxo (a caixa de seleção correspondente deve ser ativada primeiro) - Uma porcentagem x% de links com uma variação de fluxo abaixo de y% por pelo menos n iterações consecutivas.
Um critério opcional de custo (a caixa de seleção correspondente deve ser ativada primeiro) - Uma porcentagem x% de links com uma variação de custo abaixo de y% por pelo menos n iterações consecutivas.

Se os critérios de fluxo/custo forem usados, a convergência é atingida quando tanto o critério de gap quanto os critérios de fluxo/custo são cumpridos, ou quando o número máximo de iterações é calculado.

Além disso, é possível definir uma matriz de gap relativo alvo. Isso define um RGap alvo para cada par OD. Se o RGap de um determinado par OD for menor que o alvo, nenhum novo caminho será calculado para esse par OD na próxima iteração, e os caminhos atuais e os percentuais atuais de uso desses caminhos serão usados. Se o RGap de um determinado par OD for maior que o alvo, novos caminhos serão calculados para esse par OD na próxima iteração e o uso dos caminhos será atualizado. Este não é um critério de parada e não substitui o valor global de RGap.

Para usar uma matriz de gap relativo, o usuário deve criar um objeto de matriz e definir o conteúdo para Relative Gap. Isso deve então ser selecionado na aba de atribuição dinâmica de tráfego do experimento.

O framework computacional no Aimsun Next ¶

O arcabouço computacional para DTA proposto por Florian 2001 e Florian 2002 consiste em dois componentes:

Um método para determinar as taxas de fluxo dependentes do caminho nos caminhos da rede
Um método de Dynamic Network Loading, que determina como esses fluxos de caminho dão origem a volumes de arcos dependentes do tempo, tempos de viagem em arcos e tempos de viagem em caminhos.

Isso foi implementado no Aimsun Next conforme mostrado no diagrama conceitual abaixo. Quando a caixa de diálogo Dynamic Scenario é selecionada, o sistema oferece três opções: microscópica, mesoscópica e híbrida, que determinam a abordagem de simulação na qual o carregamento da rede se baseia; e, para cada carregamento de rede, são oferecidas duas alternativas: DTA ou DUE.

DTA baseia-se na abordagem heurística descrita usando modelos estocásticos de escolha de rota.
DUE baseia-se na heurística iterativa descrita acima e nos algoritmos MSA ou baseados em gradiente.

O critério de convergência depende da alternativa selecionada: a conclusão do carregamento da demanda no DTA e a conclusão do número de iterações definido ou quando o Rgap a função atinge a precisão desejada.

Uma implementação computacional eficiente dessa abordagem conceitual exige que a parte analítica do processo, isto é, o cálculo e a seleção de caminhos, seja implementada independentemente do processo de carregamento dinâmico da rede selecionado para implementar a parte heurística da Alocação Dinâmica de Tráfego. Em outras palavras, quando a consistência da rede se mantém para a representação meso e micro, o cálculo de caminhos baseado em custos de links dependentes do tempo deve ser o mesmo, e a única diferença dependerá dos valores dos argumentos das funções de custo dos links, que serão fornecidos, respectivamente, pela simulação mesoscópica de tráfego ou pela simulação microscópica de tráfego usada para o Carregamento Dinâmico da Rede.

Diagrama conceitual da atribuição dinâmica heurística

A arquitetura de software integrada do Aimsun Next permite esse cálculo comum de caminhos mínimos, dado que as representações da rede compartilham o mesmo modelo de objetos e o mesmo banco de dados do modelo, e os veículos podem ser únicos e os mesmos para meso e micro se o modelo meso for baseado em uma abordagem que individualiza os veículos; então, o cálculo de caminhos pode ser realizado por um "servidor de caminho mínimo" comum e os caminhos são os mesmos em ambos os níveis. A abordagem conceitual para atribuição dinâmica de tráfego proposta na figura anterior foi implementada em termos de um "Servidor de Atribuição Dinâmica de Tráfego". A estrutura desse servidor é mostrada abaixo.

Estrutura do Servidor de Alocação Dinâmica de Tráfego

Parâmetros DUE ¶

Antes de executar o modelo, os parâmetros do Dynamic User Equilibrium são definidos nas propriedades do Experimento em aba Dynamic Traffic Assignment.

Estimativa das taxas de fluxo de caminhos ¶

A nova abordagem implementa a estimação das taxas de fluxo nos caminhos com base em um Dynamic User Equilibrium (DUE). Este processo implementa um processo iterativo para minimizar o Gap Relativo aplicando o método da médias sucessivas (MSA),

Iniciar e Continuar um Equilíbrio Dinâmico do Usuário ¶

Continuar ou iniciar uma DUE a partir de uma DUE anterior ou de uma Macro Assignment usando um arquivo APA é possível independentemente de a rede ter sido alterada ou não. A primeira iteração ao iniciar ou continuar uma DUE usando uma alocação anterior é usada para calcular os custos dos links. Se a rede tiver sido alterada, o Corretor de APA pode ser usado para garantir que a rede e o arquivo APA sejam consistentes. O APA fixer verifica um arquivo APA e o "corrige" com base na configuração atual da rede, para que ele possa ser usado em uma versão modificada da rede. Isso contorna a restrição de que os caminhos só podem ser específicos de uma versão da topologia da rede. O APA fixer implementa as seguintes alterações:

Adição e remoção de centroides e/ou conexões
Adição, remoção ou modificação de movimentos de conversão e/ou definições de entidades de conexão de movimentos de conversão
Adição, remoção ou modificação de seções

O corretor APA é uma ferramenta de linha de comando que recebe como entrada:

O arquivo APA original
A rede revisada
O identificador do experimento na rede revisada.

O novo arquivo APA é gerado em um novo diretório "correctedapa" localizado no mesmo diretório do APA original.

Nos três casos, o corretor de APA assegura que o arquivo APA resultante será compatível com a nova rede e assegurará que a atribuição anterior seja consistente. Assim, para cada origem e destino, a atribuição soma 100%.

Resultado Incremental ¶

Para melhorar o processo geral de convergência e obter rotas melhores, um resultado incremental pode ser usado. A diferença entre um resultado normal e um resultado incremental é o número de iterações externas. Em um resultado normal há apenas uma iteração externa usando a demanda definida no cenário. Em um resultado incremental, o usuário pode especificar um número de iterações externas com diferentes percentuais crescentes. O percentual de cada iteração externa define a proporção da demanda que será usada. As primeiras iterações têm demanda menor e essa demanda é aumentada a cada iteração externa, com 100% da demanda na última iteração.

O objetivo é desenvolver o roteamento em uma rede não congestionada para evitar a distorção no roteamento provocada pelo excesso de congestionamento na simulação.