Modelos e Algoritmos de Planejamento de Transportes e Análise de Demanda no Aimsun Next¶

O Modelo de Quatro Etapas no Planejamento de Transportes ¶

A demanda de viagens urbanas e a análise de mobilidade evoluíram para uma metodologia bem estabelecida, comumente chamada de modelo de quatro etapas.

Esta seção descreve os Modelos de Planejamento de Transportes e Análise de Demanda implementados no Aimsun Next e os algoritmos que eles usam. Ela é composta pelas seguintes seções:

• Arquitetura do Sistema
• Zonas
• Rede
• Geração de Viagens
• Distribuição de Viagens
• Atribuição Estática
• Ajuste estático

O fatiamento da demanda estática para prepará-la para simulações dinâmicas começa com: - Ajuste Estático de Partida

Arquitetura do Sistema ¶

Ortúzar e Willumsen (2001), propõem uma metodologia geral representada conceitualmente no diagrama abaixo, que incorpora o modelo clássico de quatro etapas. Sua abordagem metodológica consiste nas seguintes etapas:

• Etapa I:

  Os objetivos do estudo são definidos, as estratégias para alcançar esses objetivos são selecionadas e os dados necessários para conduzir o estudo são coletados. Isso geralmente implica:

  • A coleta dos dados socioeconômicos e de uso do solo, geralmente estruturados de acordo com um esquema de zoneamento que particiona a área objeto do estudo.
  • A coleção de todas as informações referentes à infraestrutura de transporte: autoestradas, rodovias, vias, ruas e ruas urbanas, linhas de transporte coletivo, ferrovias, etc.

• Estágio II:

  Esta é a etapa de modelagem e contém três das quatro etapas do modelo de quatro etapas: - A construção dos modelos de Geração e Atração de Viagens (Etapa I) - A construção dos modelos de Distribuição de Viagens (Etapa II) - A construção dos modelos de Divisão Modal (Etapa III)

• Estágio III:

  A etapa de previsão, também conhecida como Modelos de Alocação de Viagens. Esta é a Etapa IV do modelo de transporte de quatro etapas.

• Estágio IV:

  A etapa de avaliação; os resultados da previsão são analisados e avaliados usando os critérios identificados na etapa I. Os resultados são reportados e entregues aos tomadores de decisão.

Processo¶

A metodologia, conforme representada no diagrama, com o Modelo de Quatro Etapas destacado na caixa azul, deve ser entendida como um processo iterativo no qual os resultados de qualquer etapa podem levar à reavaliação das anteriores, ou à necessidade de novos dados ou evidências para refinar as etapas anteriores.

As ferramentas e algoritmos de modelagem nos componentes de planejamento de transportes e análise de demanda do Aimsun Next foram projetados para apoiar o analista de transportes na aplicação das funções mais relevantes do modelo de quatro etapas.

Zonas¶

A análise de transportes é conduzida com modelos cujos componentes são:

• A infraestrutura e os serviços de transporte: isto é, a rede viária, o transporte coletivo etc.
• As políticas de operação e controle do sistema de transporte.
• A demanda por viagens, incluindo padrões de atividade e uso do solo, isto é, o esquema de zonas.

Viajar é uma atividade que ocorre ao se deslocar de um local para outro por uma rede de transporte (Oppenheim, 1995). Assim, a maioria dos conceitos usados na modelagem de sistemas de transporte tem uma dimensão espacial, e a primeira questão a ser tratada é como representar a estrutura espacial.

A abordagem tradicional é usar um conjunto de zonas agregadas, nas quais as localizações dos viajantes são agrupadas em "zonas de tráfego" definidas pelo analista. O tamanho de cada zona de tráfego pode variar de um quarteirão urbano a um bairro inteiro ou uma cidade, dependendo dos requisitos do modelo. Cada zona de tráfego é representada por um nó "centroide" (geralmente localizado no centro geométrico ou de gravidade da zona). A estrutura espacial abstraída correspondente a uma determinada estrutura geográfica pode ser visualizada em uma área hipotética como na figura abaixo, na qual cada ponto branco representa a localização de um viajante individual e os pontos pretos, os centroides das zonas. No processo de planejamento de transportes, a representação típica da demanda consiste em uma partição da área em estudo em zonas de tráfego. A chave para uma modelagem bem-sucedida é determinar o número e o tamanho apropriados dessas zonas.

Rede¶

A infraestrutura de transporte é modelada em termos de um grafo \(G=(N,A)\), cujos nós \(i_N\) representam "centroides", isto é, as fontes ou origens das viagens e os sumidouros ou destinos dessas viagens, ou representam interseções. Os links a∈A representam a infraestrutura física, isto é, as seções de via ou de rua urbana entre interseções, e há "dummy links", também chamados de "conexões", cuja função é conectar fisicamente os nós de origem e destino ao grafo que modela a rede viária. O grafo pode ser interpretado como uma abstração da rede viária física.

Quando uma rede viária é representada como um grafo abstrato, como na modelagem de alocação estática, há um conjunto de regras que deve ser seguido para fornecer uma representação realista. Isto é, as interseções devem ser representadas em termos de subgrafos que modelam os movimentos permitidos, e as penalidades de conversão são associadas a esses movimentos para representar os atrasos na rede viária. A figura abaixo mostra um exemplo de junção representada como um layout físico e como uma rede abstraída.

O Aimsun Next fornece três classes principais de objetos para dar suporte ao processo de modelagem em quatro etapas:

• Seções viárias e nós são usados para descrever a rede.
• Centroides e conexões descrevem as zonas e as vinculam à rede viária.
• Uma Matriz de Viagens T descreve a demanda de tráfego em que as entradas \(t_{ij}\) representam o número de viagens com origem na zona i e destino na zona j.

O Aimsun Next fornece ferramentas para criar, editar e vincular esses objetos para formar um modelo de transportes.

A figura abaixo mostra um exemplo de matriz OD para a rede do exemplo, na qual os nomes de linhas e colunas identificam as zonas (centroides).

Modelos de Geração / Atração de Viagens¶

A primeira fase no modelo de quatro etapas é um processo de geração e atração de viagens para estimar o número de viagens que se originam e/ou terminam em cada zona. Esta fase do processo de estimativa da demanda de viagens pode ser realizada tanto no nível desagregado do domicílio quanto no nível agregado das zonas, quando se assume que o número de viagens é uma função das características zonais. No que segue, restringiremos nossa descrição aos modelos agregados.

Cada zona de origem terá uma capacidade para geração de viagens que pode ser modelada em termos de suas características socioeconômicas (uso do solo, nível de renda, domicílios, posse de automóvel, emprego, etc.) como uma função:

(1.1)

em que \(O_{i}\) é o número de viagens geradas pela i-ésima zona e \(V_{ik}\) é a k-ésima variável socioeconômica da zona.

Da mesma forma, como destino, cada zona, no nível agregado, terá uma capacidade de atração de viagens que também pode ser modelada como função de suas características socioeconômicas:

(1.2)

onde, como antes, \(D_{j}\) é o número total de viagens atraídas pela zona \(j\), e \(v_{jk}\) é a k-ésima variável socioeconômica da zona \(j\).

No nível zonal agregado, as técnicas mais frequentemente usadas para geração e atração de viagens são baseadas em análise de regressão múltipla e, então, uma forma comum para funções \(O_i\) e \(D_{j}\) poderia ser:

(1.3)

em que o \(v_{ik}\) os valores são os fatores de "produção" ou "atração" de viagens fornecidos, dependendo do tipo de modelo, e \(a_{ik}\) values são os parâmetros cujos valores numéricos serão estimados por regressão múltipla a partir dos dados disponíveis de pesquisas, bases de dados censitárias e outras fontes. Os fatores de geração / atração de viagens nesta abordagem podem ser zonas e atributos dos viajantes, bem como outros atributos, como os dos modos de viagem, rotas de viagem, número de paradas de ônibus, ou tempos e custos de viagem.

Modelos e Algoritmos de Distribuição de Viagens¶

A distribuição de viagens é a próxima etapa na Metodologia de Quatro Etapas e é realizada depois que a geração/atração de viagens é concluída. Ela consiste em distribuir entre vários destinos cada uma das origens de viagem Oi. Uma vez definido o conjunto de centroides, os movimentos desejados sobre a rede viária podem ser expressos em termos de uma matriz "origem-destino", cujas entradas especificam o fluxo (número de viagens ao longo do período de tempo do estudo) entre cada centroide de origem e cada centroide de destino na rede:

Matriz OD: T=\([t_{ij}]t_{ij}\) = número de viagens entre a origem \(i\) e destino \(j\)

Levando em conta a geração/atração de viagens de cada zona, a matriz de mobilidade, também chamada de matriz de viagens e matriz Origem-Destino, OD, que modela a demanda de transporte na área objeto de estudo, o problema de distribuição (Erlander and Stewart, 1990) trata da determinação de uma matriz não negativa {\(t_{ij}\):} satisfazendo as restrições marginais:

(EQN TD1)

e outras condições, como a soma das viagens de partida ser igual à soma das chegadas:

(2.2)

A Equação (2.1) significa que a soma das viagens geradas em cada origem para todos os destinos deve ser igual à capacidade de geração de viagens de cada origem, e a soma de todas as viagens que chegam a cada destino a partir de todas as origens deve ser igual à capacidade de atração de viagens de cada destino.

Estão disponíveis três métodos para realizar os cálculos de distribuição de viagens, um por considerando o crescimento nas matrizes de origem e destino usando Mobiliário técnicas, e duas em Modelagem da demanda usando um Modelo gravitacional ou um Modelo de Escolha de Destino.

Métodos de Fator de Crescimento (Furnessing)¶

Assumindo que uma matriz de viagens básica ou de referência {\(t_{ij}\)} de um estudo anterior ou de uma pesquisa recente está disponível. O objetivo é estimar uma matriz de viagens {\(T_{ij}\)} para um ano de projeto usando informações disponíveis sobre a taxa de crescimento da área de estudo entre o ano da matriz de referência e o ano de projeto.

Neste caso, há informações disponíveis sobre o número futuro de viagens com origem e término em cada zona. Portanto, há dois conjuntos de fatores de crescimento disponíveis para viagens que entram e saem de cada zona: \(a_{i}\) e \(b_{j}\) respectivamente, de modo que:

(2.3)

Um modelo conhecido como fator de crescimento duplamente restrito; o cálculo de {\(T_{ij}\)}, conforme definido por (2.3), satisfazendo as condições:

(2.4)

Isso requer o cálculo dos coeficientes de crescimento \(a_{i}\) e \(b_{j}\) o que é feito com o procedimento de balanceamento Furness (Furness, 1965; ver também Fratar 1954, Bregman, 1967).

O procedimento de balanceamento Furness é formulado da seguinte forma:

• Etapa 0. Inicialização Definir l=0 (contador de iterações), e (2.5)

• Etapa 1. Balanceamento de linhas

• Etapa 2. Balanceamento de colunas

• Etapa 3. Teste de parada

O teste de convergência para o processo é

Se o erro aceitável ε for satisfeito ou l+1= lmax, (o número máximo de iterações foi atingido), então STOP.

Caso contrário, defina l:=l+1 e retorne à Etapa 1.

Ortúzar e Willumsen destacam (Ortúzar e Willumsen, 1990), que os métodos de fator de crescimento são simples de entender e fazem uso direto de matrizes de viagens observadas e de previsões de crescimento das extremidades das viagens. Isso também os limita a previsões de curto prazo, pois os métodos não levam em conta mudanças nos custos de transporte decorrentes de alterações na rede. Também é importante observar que eles preservam os "zeros estruturais"; qualquer célula \(t_{ij}\) que é igual a zero na matriz OD do ano-base, será igual a zero na prevista \(T_{ij}\) matriz OD.

Métodos do Modelo de Demanda ¶

Os Modelos Gravitacionais pertencem à família de modelos projetados para prever padrões futuros de viagens quando ocorrem mudanças significativas na rede. Seu nome deriva da observação de que o volume de viagens tem alguma semelhança com a força da gravidade, com uma razão direta em relação à massa (ou população) de uma zona e uma razão inversa em relação à distância entre zonas.

Os modelos de escolha de destino são um tipo de modelo de distribuição de viagens ou de interação espacial formulado como modelos de escolha discreta, tipicamente modelos logit, que atribuem viagens por meio de probabilidades, maximizando a utilidade de cada viajante ao ir de cada origem para cada destino. A chave desse modelo é a premissa de que os viajantes selecionam seu destino com base na utilidade que ele tem para eles, tentando maximizá-la. Esse modelo é reversível: com as mesmas utilidades, pode-se usar as viagens geradas (lado de partida) ou as viagens atraídas (lado de chegada) para fazer a atribuição de viagens.

Ao contrário do Gravity Model, o modelo Destination Choice não ajusta automaticamente as viagens atribuídas aos vetores Generation/Attraction. No Aimsun Next, para resolver esse problema, shadow prices são adicionados às utilidades e calculados recursivamente. No entanto, essa é uma parte opcional que pode não ser necessária e, em alguns casos, até indesejável, porque distorce as utilidades modeladas pelo usuário.

Comparação entre o modelo gravitacional e o modelo de escolha de destino¶

Uma comparação entre os dois modelos de demanda é mostrada nas tabelas abaixo. Observe que, embora o Destination Choice Model ofereça mais capacidade do que o Gravity Model, ele também exige maior conhecimento dos fatores que controlam a demanda para ser usado de forma eficaz. No entanto, observe que ambos os modelos ainda omitem muitos atributos não observados ou não quantificados, como o preço e a qualidade dos bens e serviços oferecidos nos destinos, relações sociais, hábitos dos viajantes e a estética de uma área.

Nem todos os fatores que afetam a escolha podem ser medidos diretamente. Eles são inferidos pelos modelos.

Tabela derivada de Recurso de Previsão de Viagens.

Modelo gravitacional¶

A forma geral do modelo gravitacional é capturada na seguinte equação:

(2.6)

em que \(O_i\), o número de viagens geradas pela origem \(i\) é a "massa" da origem \(i\), \(D_j\), a capacidade de atração de viagens do destino \(j\) é a "massa" do destino \(j\), α é uma constante e f(\(c_{ij}\)) é uma função de impedância em termos do custo \(c_{ij}\) de viajar da origem \(i\) ao destino \(j\). A aplicação da fórmula (2.5) não pode ser feita imediatamente, pois a constante não pode ser determinada de tal forma que as restrições marginais (2.1) e (2.2) sejam satisfeitas. Isso requer a introdução de fatores de normalização adicionais \(A_i\) e \(B_j\), e o modelo é reformulado da seguinte forma:

(2.7)

Os vários tipos de modelos gravitacionais são classificados pela forma da função de impedância; os mais comuns são:

• Modelos gravitacionais com função de impedância exponencial
• Modelos gravitacionais com função de impedância de potência
• Modelos gravitacionais com função de impedância combinada

Modelos gravitacionais com uma função de impedância exponencial¶

Dada a natureza indeterminada do modelo, geralmente haverá um grande número de matrizes viáveis para um determinado conjunto de \(O_i\) e \(D_j\), porque há \(i*j\) elementos e apenas restrições i+j nas equações (2.1). Isto implica que uma escolha entre as matrizes viáveis {\(T_{ij}\)} deve ser feita de acordo com algum critério adicional. Para levar explicitamente em consideração os custos de viagem entre zonas ao \(c_{ij}\) do custo de deslocamento da zona i para a zona j para todas as zonas estiver disponível, o custo poderá ser incluído explicitamente no modelo de entropia, adicionando-o como uma restrição ao gasto total no sistema, quando custos generalizados forem usados, ou ao tempo total de viagem no sistema quando os custos forem medidos em termos de tempos de viagem.

O modelo modificado agora é:

(2.8)

que é novamente um modelo de otimização convexa cuja função Lagrangeana é:

(2.9)

onde, como antes, α\(_i\) e β\(_j\) são, respectivamente, os multiplicadores Lagrangeanos i-ésimo e j-ésimo da restrição em (2.8), γ é o multiplicador Lagrangeano da restrição de tempo, e as condições de otimalidade são válidas para:

(2.10)

Então, fazendo as alterações,\(A_i\) \(O_i\)=exp{-α\(_i\)}, ∀ i ∈ I e \(B_j\) \(D_j\) = exp{-β\(_j\)}, ∀ j ∈ J a solução pode ser reescrita como:

(2.11)

E os coeficientes de balanceamento \(A_{i}\) e \(B_{j}\) pode ser calculado pelo seguinte algoritmo de Furness modificado:

Etapa 0. Inicialização Definir l=0 (contador de iterações), e \(A_i^0= B_j^0 =1\) , ∀ \(i\) , ∀ \(j\)

Etapa 1. Balanceamento de linhas

Etapa 2. Balanceamento de colunas

Etapa 3. Teste de parada

Se os critérios de convergência forem menores que ε ou l+1= lmax, (o número máximo de iterações ) então STOP. Caso contrário, defina l:=l+1 e retorne à Etapa 1.

Um valor estimado recomendado para o multiplicador Lagrangeano γ é o inverso do custo médio de viagem entre zonas; isto é, γ= (custo médio de viagem)^-1^.

Modelo de Escolha de Destino¶

O Modelo de Escolha de Destino calcula probabilidades \(p_{ij}\) de atribuir viagens geradas na origem \(i\) (\(O_i\)) para destinos \(j\):

(3.1)

Onde \(i,j\) são as zonas de origem e destino e \(O_i\) são as viagens geradas por origem \(i\).

Para alcançar isso, é usado um método de alocação por maximização de utilidade baseado em um Multinomial Logit Model, com funcionalidade adicional (opcional) para corresponder aos valores totais de atração por destino (\(A_j\)) calculado pela etapa de Geração/Atração ao atribuído pelo cálculo de Escolha de Destino da Distribuição de Viagens. Observe que este modelo também pode ser aplicado no sentido oposto; usando valores de atração em vez de valores de geração:

(3.2)

Onde \(A_j\) são os valores atraídos e \(\tilde{p}_{ij}\) é a probabilidade de um viajante com destino \(j\) para partir da origem \(i\). Como a descrição deste problema simplesmente troca origens e destinos, sua descrição é omitida aqui.

Maximização da utilidade e modelo de escolha logit multinomial¶

O modelo de escolha de destino implementado no Aimsun Next usa um modelo de escolha Logit Multinomial, um modelo de maximização de utilidade para reproduzir escolhas dos tomadores de decisão. Para mais detalhes sobre o modelo, consulte https://data.princeton.edu/wws509/notes/c6s3.

Primeiro, uma utilidade U é uma quantidade que mede "quão útil é uma escolha para o tomador de decisão em relação a outra ou outras" - portanto, a escolha a é preferido à escolha b if:

(3.3)

Neste caso, a e b são os pares origem-destino ij.

A partir da Eq.(3.3), fica claro que os valores relativos da utilidade são fundamentais; assume-se que o viajante escolherá a opção que maximiza sua utilidade. A partir dessa definição, a probabilidade de escolher a opção a ∈ A é:

(3.4)

No entanto, as utilidades estão sempre vinculadas a erros estatísticos nos atributos das escolhas, que então se tornam:

(3.5)

Onde \(U^{(0)}_a\) é o valor exato da utilidade e (ε\(_a)\) é um termo de erro.

O Modelo Logit Multinomial assume que todos os erros são iguais e têm a seguinte distribuição:

(3.6)

Isso leva a:

(3.7)

Observe que aqui as decisões são baseadas apenas na utilidade de cada viajante individual, que é independente das utilidades de outros viajantes. No entanto, como os viajantes interagem na rede de transporte, suas escolhas são afetadas pelas ações dos outros. Por exemplo, se um viajante for dissuadido pela lotação ou por atrasos na opção a, sua decisão será afetada pelo número de outros viajantes que escolheram esta opção.

Opções com probabilidade zero¶

Em um Modelo de Escolha de Destino, é possível programar a modificação das utilidades para excluir uma ou mais opções, preservando as probabilidades das opções restantes. O processo consiste em transformar as utilidades de modo que as seguintes afirmações sejam satisfeitas:

• As probabilidades das escolhas excluídas são zero: \(p_a = 0\) em que \(a\) é uma escolha excluída (par OD).
• As probabilidades entre as escolhas não excluídas devem ser invariantes para manter a ordem de preferências independentemente de outras opções.

(3.8)

A transformação considera o limite das probabilidades quando as utilidades das escolhas excluídas tendem a ∞. Esse limite significa que as escolhas excluídas nunca são preferidas em relação a qualquer uma das escolhas não excluídas.

(3.9)

(3.10)

Onde \(a\) é uma escolha não excluída do conjunto não excluído (A-Ω) e Ω é o conjunto de opções excluídas.

Numericamente, isso é equivalente a reescalonar o denominador e definir as probabilidades excluídas como zero, o que preserva a Eq.(3.8).

Modelo de escolha de destino com restrições de geração/atração¶

O objetivo deste método é impor as restrições de atração no Modelo de Escolha de Destino. Em geral, as viagens alocadas a cada destino devem corresponder aos valores atraídos calculados (observe que, porque \(p_{ij}\) são normalizadas, as gerações correspondem às viagens atribuídas por construção). Assim, nesta seção descrevemos o método para impor as seguintes restrições:

(3.11)

Onde \(A_j\) é a atração do destino \(j\), \(O_i\) a geração por origem \(i\) e \(p_{ij}\) é a probabilidade de um viajante ir de \(i\) para \(j\) que é dado por:

(3.12)

Para impor todos os \(A_j\) restrições de atração, minimizamos uma métrica que considera o erro com o método de descida do gradiente modificando as utilidades:

em que \(s_j\) é a precificação sombra deles.

A métrica é expressa como:

(3.13)

Onde τ\(_j\) são os pesos (opcionais) de destino \(j\). Observe que a função \(F\) é convexo em termos de \(V_r\), mas não necessariamente em termos de \(s_j\).

Ao minimizar esta métrica, impomos que a atração seja igual ao número total de viagens atribuídas a cada destino, como na equação (3.11).

Usando as fórmulas do método de descida do gradiente:

(3.14)

(3.15)

3.(16)

(3.17)

(3.18)

Portanto:

(3.19)

Também pode ser reescrito como:

(3.20)

E, finalmente, o algoritmo é, a partir da etapa \(k\) para \(k+1\):

(3.21)

Onde μ é o tamanho (pequeno) do passo. μ também pode mudar entre passos e será selecionado para minimizar F.

(3.22)

Para encontrar o mínimo:

(3.23)

Porque \(s_j\) - μ\(g_j\) é convexa em μ, então, a função resultante também é convexa e os pontos estacionários também são mínimos e, portanto, mínimos globais. Para simplificar a notação \(V_r(0) = V_r\) e o ponto estacionário é um mínimo.

Portanto:

(3.24)

Mínimos Locais¶

Existe a possibilidade de uma multiplicidade de pontos estacionários, que podem ser mínimos, máximos ou um ponto de sela. A função a ser minimizada pode ser escrita como:

(3.25)

É evidente que ele possui apenas um ponto estacionário δF/δ\(V_j=0\) , um mínimo global quando \(\hat{V}_j = V_j\) para todos \(j\). No entanto, em termos dos preços-sombra \(V = V(s_q)\) não é necessariamente o único mínimo. Portanto, para determinar os pontos estacionários (máx., mín. ou sela):

(3.26)

O método de descida do gradiente encontra um mínimo local por definição; no entanto, não há como garantir, isto é, com diferentes valores de \(A_j\) , \(O_i\) e \(p_{ij}(s_q = 0)\) que o mínimo encontrado é global. Neste caso, \(dV_k/ds_q\) nunca se reduz a zero e, na prática:

(3.27)

Portanto, usando a Eq.(3.9), podemos encontrar para \(j = q\):

(3.28)

e para \(j\) ≠ \(q\)

(3.29)

Os únicos casos em que \(dV_k/ds_q\) desaparecem primeiro, quando todas as probabilidades de ir para o destino \(j\) \(p_{ij}\) são zero exceto por um valor e o segundo caso quando \(p_{iq} = 0\). Nenhum desses é alcançado numericamente, pois correspondem a &\(s_q\) ± ∞.

Alocação Estática de Tráfego: Modelos de Equilíbrio do Usuário¶

Os padrões de fluxo por uma rede viária podem ser considerados como o resultado de dois mecanismos concorrentes:

• Os usuários do sistema tentam viajar de uma forma que minimize a desutilidade associada ao transporte.

  • Motoristas viajando entre uma determinada origem e um determinado destino tendem a escolher a rota com o menor tempo de viagem.

• A desutilidade associada à viagem não é fixa, mas depende em parte do uso do sistema de transporte.

  • O tempo de viagem em cada um dos caminhos que conectam a origem e o destino é uma função do fluxo total de tráfego devido ao congestionamento.

Consequentemente, pode não ser óbvio qual dos padrões de fluxo pela rede apresenta o menor tempo. A análise de transportes considera o nível de serviço de transporte (ou seu inverso, a desutilidade de viagem) e os fluxos. Os resultados da análise levam a um conjunto de fluxos e a um conjunto de medidas de nível de serviço que estão em equilíbrio entre si.

O objetivo do modelo é descrever a interação entre o congestionamento e as decisões de viagem que resultam nesse fluxo. Como o congestionamento aumenta com o fluxo e as viagens são desestimuladas pelo congestionamento, essa interseção pode ser modelada como um processo que atinge equilíbrio entre congestionamento e decisões de viagem.

A impedância de viagem, ou nível de serviço, associada aos links que representam uma rede viária, pode incluir muitos componentes, refletindo tempo de viagem, segurança, custo de viagem, estabilidade do fluxo e outros. A representação mais comum dessa impedância é em termos de tempo de viagem, na medida em que estudos empíricos parecem indicar que ele é um fator primário de dissuasão do fluxo e, por outro lado, é mais fácil de medir do que muitos outros componentes possíveis de impedância. Como mencionado, o nível de serviço em serviços de transporte é geralmente uma função de seu uso. Devido ao congestionamento, o tempo de viagem em redes viárias é uma função crescente do fluxo. A representação típica da impedância de link é em termos das chamadas funções "volume-delay", que expressam o tempo de viagem \(s_a(v_a)\) no link a∈A em função do volume \(v_a\) nesse link. Estas são funções não lineares cuja aparência teórica é semelhante à representada na figura abaixo, sempre abaixo da capacidade do link.

O conceito de equilíbrio na análise de transportes¶

É um conceito emprestado da teoria dos mercados perfeitamente competitivos, modelado em termos de dois grupos interativos: os produtores e os consumidores. O comportamento dos produtores é caracterizado por uma função de oferta e o comportamento dos consumidores é caracterizado por uma função de demanda. A função de oferta expressa a quantidade de bens que o fornecedor produz em função do preço do produto. À medida que o preço aumenta, torna-se lucrativo produzir mais e a quantidade ofertada aumenta.

A função de demanda descreve o comportamento agregado dos consumidores ao relacionar a quantidade do produto consumida ao seu preço. À medida que o preço aumenta, a quantidade consumida diminui. A figura acima ilustra funções simples de demanda e oferta para um determinado produto. O ponto em que as duas curvas se interceptam é caracterizado pelo preço de "equilíbrio de mercado", P^∗^, e quantidade produzida Q^∗^. O ponto (P^∗^,Q^∗^) é o ponto em que o preço permanece estável; isto é conhecido como o ponto de "equilíbrio".

Para sistemas de transporte, a demanda é representada em termos de uma função de demanda que relaciona o número de viagens ao seu custo (isto é, tempo de viagem), e a oferta é representada em termos de uma função de desempenho (isto é, tempo de viagem entre pares OD), como na figura abaixo.

O equilíbrio do usuário é alcançado quando "nenhum viajante pode melhorar seu tempo de viagem alterando unilateralmente as rotas" ou, conforme originalmente formulado por Wardrop (1952), "Os tempos de viagem em todas as rotas efetivamente usadas são iguais ou inferiores àqueles que seriam experimentados por um veículo em qualquer rota não utilizada", formulação conhecida como o primeiro princípio de Wardrop ou princípio do Equilíbrio do Usuário de Wardrop.

Um exemplo simples extraído de Sheffi (1985) ajudará a ilustrar e compreender o Princípio de Wardrop. Considere uma rede simples como a da figura abaixo, com apenas uma origem e um destino conectados por duas rotas alternativas, com uma demanda total de \(q\) viagens, gerando os fluxos de tráfego \(x_1\) e \(x_2\), nas rotas um e dois, respectivamente, atendendo \(q = x_1+x_2\).

Vamos também assumir que os tempos de viagem \(s_1\) e \(s_2\) nas rotas 1 e 2, respectivamente, são determinados pelas funções de desempenho \(s_1(x_1)\) e \(s_2(x_2)\) da figura abaixo, que estimam o tempo de viagem em função do fluxo de tráfego em cada rota.

Se o fluxo total for q < q’ , então tudo é atribuído à rota 2, cujo tempo de viagem é menor, como mostra a parte (a) da figura abaixo, mas para um fluxo maior \(q = x_1+x_2\) a distribuição de fluxo em equilíbrio, \(x_1\) e \(x_2\), entre as rotas 1 e 2 deve ser feita de tal forma que os tempos de viagem em ambas as rotas sejam os mesmos, conforme mostrado na parte (b) da figura abaixo.

Outra forma de visualizar o equilíbrio do usuário (UE) entre as duas rotas é sobrepor as duas curvas de custo (tempo de viagem ou atraso por volume) (Bell and Iida,(1997) conforme mostrado na figura abaixo. À esquerda da interseção das duas curvas, a rota 1 custa menos que a rota 2, e há um incentivo para trocar para a rota 1. À direita da interseção, a rota 2 custa menos que a rota 1 e há um incentivo para trocar para a rota 2. A interseção das duas curvas representa o ponto de equilíbrio no qual os custos das rotas 1 e 2 são iguais e não há incentivo para trocar de rota. Geometricamente, a interseção também corresponde ao ponto que minimiza a área total sob as funções de custo; em qualquer outro ponto, a área será maior.

Os principais modelos de tráfego para a estimativa da distribuição dos fluxos de tráfego em uma rede viária são baseados em modelos matemáticos de escolha de rota, isto é, na modelagem de como os usuários selecionam suas rotas sob as condições de tráfego vigentes.

O conceito de equilíbrio desempenha um papel central neste processo de construção do modelo. Wardrop enunciou os dois princípios que formalizaram esse conceito de equilíbrio e introduziu o postulado comportamental da minimização dos custos totais, que, juntamente com os princípios, constitui a hipótese fundamental de modelagem. Modelos de equilíbrio de tráfego são modelos descritivos destinados a prever fluxos em links e tempos de viagem que resultam da forma como os usuários escolhem rotas de suas origens até seus destinos em uma rede de transporte (Florian, 1986, e Florian e Hearn, 1995) (Sheffi, 1985).

O primeiro princípio afirma que "Os tempos de viagem em todas as rotas efetivamente usadas são iguais ou inferiores àqueles que seriam experimentados por um único veículo em qualquer rota não usada".

Os fluxos de tráfego que satisfazem esse princípio geralmente são denominados "fluxos otimizados pelo usuário", porque cada usuário escolhe a rota que percebe como a melhor. Os "fluxos otimizados pelo sistema" são caracterizados pelo segundo princípio de Wardrop, que afirma que "o tempo total de viagem é mínimo".

Os Modelos de Atribuição Estática de Tráfego construídos de acordo com esses princípios e com o postulado de minimização do custo total consideram um determinado período de tempo para o qual as características da demanda foram determinadas e estimam os padrões de fluxo que resultam da interação entre a demanda e as características de congestionamento da infraestrutura de transporte disponível.

A rede viária é modelada em termos de um grafo, cujos nós n ∈N representam origens, destinos e interseções de links, e links, a∈A representam a infraestrutura de transporte, conforme discutido acima. O fluxo de viagens em um link a é dado por \(v_a\), e o custo de viajar em um link é dado por uma função de custo do usuário \(s_a(v)\) em que \(v\) é o vetor de fluxos dos links em toda a rede. Como essas funções modelam o atraso de tempo para uma viagem no arco \(a\), elas são chamadas de funções volume/atraso. Uma hipótese-chave de modelagem referente ao comportamento dessas funções é que se presume que sejam monotônicas, isto é, tais que:

(4.1)

e também se assume que sejam contínuas e diferenciáveis.

As demandas de origem a destino, \(g_i\), i ∈* , onde é o conjunto de pares origem/destino, OD, pode usar caminhos direcionados \(k\), \(k\)∈\(K_i\), onde \(K_i\) é o conjunto de caminhos para o par OD \(i\). Os fluxos nos caminhos \(k\), \(h_k\), satisfazem as condições de conservação de fluxo e não negatividade:

(4.2)

Os fluxos dos links correspondentes \(v_a\) são dados por:

(4.3)

Onde:

O custo de cada caminho \(s_k\) é a soma dos custos de usuário dos links no caminho \(k\):

(4.4)

Let \(u_i\) seja o custo do caminho de menor custo para quaisquer pares OD \(i\):

(4.5)

O modelo de equilíbrio do usuário na rede, baseado no primeiro princípio de Wardrop, é formulado supondo que, para cada par OD, o princípio ótimo do usuário de Wardrop é satisfeito, ou, em outras palavras, que todos os caminhos direcionados utilizados têm custo igual, isto é:

(4.6)

sobre o conjunto viável (4.2)-(4.3). Este modelo de equilíbrio de rede pode ser reescrito na forma de uma desigualdade variacional:

(4.7)

em que \(h_k\) é qualquer fluxo de caminho viável. Se h^∗^~k~>0 , então s^∗^~k~=u^∗^~k~ porque \(h_k\) pode ser menor que h^∗^~k~, se h^∗^~k~=0 então a desigualdade é satisfeita quando s^∗^~k~-=u^∗^~k~≥0.

Somando sobre k∈K~i~, e i∈, e levando em conta as restrições (4.2) e (4.3) quando a demanda \(g_i\) é constante, o modelo (4.7) pode ser reformulado da seguinte forma (Fisk and Boyce, 1983) (Magnanti, 1984) (Dafermos, 1980):

(4.8)

que é a formulação de desigualdade variacional derivada por (Smith, 1979).

Modelos de Demanda Fixa de Equilíbrio do Usuário¶

Quando as funções de custo do usuário são separáveis, isto é, dependem apenas do fluxo no link s~a~(v)= s~a~(v~a~)a∈A, e demandas \(g_i\) são considerados constantes, independentes dos custos de viagem; a formulação de desigualdade variacional tem o seguinte problema equivalente de otimização convexa (Patriksson, 1994; Florian and Hearn, 1995):

(4.9)

e a restrição definicional de \(v_a\) (4.3).

Embora o problema de alocação de tráfego seja um caso especial de fluxos de rede multi-commodity não lineares, e possa ser resolvido por qualquer um dos métodos usados para a solução desse problema, algoritmos mais eficientes para resolver esse problema, baseados em uma adaptação do método de aproximação linear de Frank e Wolfe (Frank e Wolfe, 1956) foram desenvolvidos nos últimos anos (Leblanc at al., 1975) (Nguyen, 1976) (Florian, 1976). Outros algoritmos eficientes baseados na abordagem simplicial restrita foram desenvolvidos por Hearn et al. (Lawphongpanich e Hearn, 1982) (Guélat, 1982) ou em uma adaptação do método das tangentes paralelas (PARTAN) (Florian et al., 1987).

A adaptação do método de aproximação linear para resolver o problema de alocação de equilíbrio do usuário requer apenas o cálculo dos caminhos mais curtos e uma minimização unidimensional de uma função convexa. Partindo de uma solução viável, o método de aproximação linear gera uma direção de descida viável (Bazaraa et al, 1993; Sheffi, 1985) resolvendo um subproblema obtido pela linearização da função objetivo. Em seguida, uma solução aprimorada é encontrada no segmento de reta entre a solução atual e a solução do subproblema. Para o UE com demandas fixas formulado em (4.9), onde as funções de custo são separáveis, a aproximação linearizada da função objetivo em uma iteração intermediária l quando a solução atual \(v^{(l)}\) é:

(4.10)

Porque \(S(v^{(l)})\) e ∇S(v^(l)^)(v^(l)^) são constantes, o subproblema linearizado a ser resolvido se reduz a:

(4.11)

alterando a ordem de somatório na função objetivo de (4.11) e usando (4.4), o objetivo torna-se:

(4.12)

Como os termos da função objetivo (4.12) agora podem ser separados por par OD \(i\), a solução do subproblema linearizado pode ser obtida calculando o caminho mais curto para cada par OD i e alocando a demanda \(g_i\) aos links desses caminhos. Essa alocação ou atribuição de demanda é chamada de atribuição "tudo-ou-nada". Isso produz o vetor de fluxo de arco:

(4.13)

e a direção de descida é:

(4.14)

Uma iteração do algoritmo de aproximação linear é concluída encontrando a solução de

(4.15)

ou, de forma equivalente, anulando sua derivada, isto é, encontrando &lambda; onde 0≥λ≥1, para o qual

(4.16)

a menos que o mínimo de (4.14) seja atingido para λ=0 ou λ=1.

A principal vantagem computacional do método de aproximação linear é que os caminhos usados em cada iteração para calcular a direção de descida são gerados conforme necessário e não precisam ser mantidos em iterações sucessivas. Assim, os requisitos de armazenamento não aumentam com o número de iterações. Em cada iteração, apenas os fluxos \(v^{(l)}\) e os custos dos links \(s^{(l)}\) precisam ser mantidos, além dos dados de links da rede.

Porque \(S(v)\) é uma função convexa e ∇S(v)=s(v),

(4.17)

O lado direito de (4.17) fornece um limite inferior para os valores ótimos S(v^∗^) em cada iteração. O melhor limite inferior obtido até uma iteração atual \(l\) é:

(4.18)

Assim, um critério natural de parada, normalmente denominado gap relativo (RGAP), é

(4.19)

De modo geral, todas estas adaptações do método de aproximação linear (LAM) se enquadram no seguinte arcabouço algorítmico (Florian, 1986; Florian e Hearn, 1995), que é a utilizada para a função Traffic Assignment no Aimsun Next:

ETAPA 1: Inicialização: Encontrar uma solução viável inicial \(v^{(1)};s^{(1)}=s(v^{(1)});l=1\)

ETAPA 2: Solução do subproblema linearizado na iteração l

em que \(s^{(l)}_k\) é o custo no caminho k na iteração l. Para cada par OD \(i\) o algoritmo encontra o caminho mais curto \(k\)^∗*\(_i\) e executa uma alocação tudo-ou-nada, encontra os fluxos \(h^{(l)}_k\), calcula o vetor de fluxo do arco \(y^{(l)}\) de acordo com (4.12), e a direção de descida \(d^{(l)}=y^{(l)}-v^{(l)}\) de acordo com (4.13)

ETAPA 3: Verificar se um critério de parada predeterminado é satisfeito (i.e. RGAP≤ε). Se for satisfeito, então PARE; caso contrário, continue para a Etapa 4.

ETAPA 4: Encontrar o tamanho de passo ideal λ^(l)^ by solving (4.15)

ETAPA 5: Atualizar fluxos e custos dos links

Conjunto \(l=l+1\) e retorne à Etapa 2.

A lenta convergência do método de aproximação linear na vizinhança da solução ótima levou à investigação de variantes do método, que poderiam melhorar a taxa de convergência mantendo a simplicidade e as vantagens computacionais das aproximações lineares.

Um método para acelerar a convergência próxima da solução ótima é alterar a direção de descida conforme explicado em (Daneva 2002). Em vez da direção de descida explicada na equação 4.14, é usada a direção de descida FW conjugada. A direção de descida FW conjugada é encontrada como:

(4.20)

Tal que:

(4.21)

Com H^l^ a Hessiana da função objetivo UE na l-ésima iteração.

Estimação de Fluxos de Demanda OD usando Contagens de Tráfego: Ajuste de Matriz¶

Se houver informações disponíveis sobre os fluxos de tráfego atuais em um subconjunto de links da rede, com pelo menos um número significativo de links, tanto em quantidade quanto em disposição, essas informações podem ser usadas para ajustar a matriz OD local e obter uma melhor representação dos padrões de viagem. Em outras palavras, estamos buscando métodos destinados a melhorar as estimativas dos fluxos atuais de demanda origem-destino, combinando estimadores diretos e/ou indiretos (modelo) com outras informações agregadas relacionadas aos fluxos de demanda OD (Cascetta, 2001). A seguir, as informações agregadas serão identificadas com contagens de tráfego em alguns links da rede de transporte.

De um certo ponto de vista, o problema de estimar fluxos OD usando contagens de tráfego pode ser considerado o inverso do problema de alocação de tráfego. O problema de alocação de tráfego pode ser definido como o de calcular fluxos nos links a partir de fluxos OD, da rede e do modelo de escolha de caminhos. Inversamente, o problema em estudo é o de calcular os fluxos OD a partir dos fluxos medidos nos links, usando a rede e o modelo de escolha de caminhos (veja a Figura abaixo).

A estimação de matrizes OD usando contagens de tráfego tem recebido atenção considerável nos últimos anos, tanto do ponto de vista teórico quanto empírico. Isso pode ser facilmente explicado pelo custo e pela complexidade das pesquisas amostrais, bem como pela falta de precisão relacionada tanto aos estimadores diretos quanto aos estimadores por modelo dos fluxos OD. Por outro lado, não é incomum encontrar uma infraestrutura de detectores já existente em uma rede, tornando os fluxos em links (contagens de tráfego) em algum subconjunto dos links da rede baratos e facilmente obtidos, muitas vezes automaticamente. Além disso, em muitas aplicações de engenharia de transportes, as estimativas de fluxos OD têm essencialmente o objetivo de prever fluxos de tráfego derivados de mudanças na rede, e espera-se que uma matriz capaz de reproduzir com precisão suficiente tais agregados forneça melhores previsões dos impactos esperados das mudanças na rede.

No problema de estimação da matriz OD, estamos interessados em encontrar um vetor viável (matriz OD) g∈Ω, onde \(g={g_i}\),i∀ I, consiste na demanda para todos os pares OD. Pode-se assumir que a atribuição da matriz OD aos links da rede é feita de acordo com a matriz de proporções de atribuição \(P={p_{ia}}\),i∀I,a∀A em que cada elemento na matriz é definido como a proporção da demanda OD \(g_i\) que usa link \(a\). A notação \(P=P(g)\) é usado para destacar que, em geral, essas proporções dependem da demanda.

Quando atribuída à rede, a matriz OD induz um fluxo \(v={v_a}\),a∀A, nos links da rede. Assumimos que os fluxos observados, \(\hat{v}\)-{\(\hat{g}_a\)}, estão disponíveis para um subconjunto dos links, a ∈\(\hat{A}\)⊆A, e que uma matriz de referência \(\hat{g}\)∈Ω também está disponível. O problema genérico de estimação de matriz OD agora pode ser formulado (Petersson, 2003) as:

(5.1)

As funções \(F_1(g,\hat{g})\) e \(F_2(v,\hat{v})\) representam medidas de distância generalizada entre a matriz OD estimada \(g\) e a matriz de referência fornecida \(\hat{g}\), e entre os fluxos de links estimados \(v\) e os fluxos observados nos links \(\hat{v}\), respectivamente.

Os parâmetros γ1 e γ2 refletem a crença relativa (ou incerteza) nas informações contidas em \(\hat{g}\) e \(\hat{v}\); e o problema pode ser interpretado como um problema de dois objetivos. Os dois objetivos são expressos em \(F_1\) e \(F_2\), e γ1 e γ2 são os fatores de ponderação correspondentes.

O conjunto de matrizes OD viáveis, Ω, normalmente consiste nas matrizes OD não negativas, mas também pode ser restrito àquelas matrizes dentro de um certo desvio em relação aos valores de referência, isto é:

para algum parâmetro adequado α que indique o nível de tolerância. Uma formulação análoga pode ser usada para indicar um desvio máximo em relação à observação de fluxo do link com um parâmetro de tolerância β>0:

Outra possibilidade é restringir a demanda total de viagens em todos os pares OD que se originam ou terminam em um determinado nó, o que, no modelo de quatro etapas, representaria um ajuste da distribuição de viagens em relação à geração de viagens.

Obviamente, a matriz OD resultante depende da função objetivo minimizada em (5.1), isto é, da escolha da medida de distância. Uma das distâncias inicialmente propostas, provavelmente por analogia com o problema de distribuição de viagens, foi a função de entropia máxima, que em sua forma original pode ser formulada como:

(5.2)

Nesta formulação extrema, a matriz de referência não tem influência alguma, e a estimação da matriz OD é mais um procedimento de distribuição de viagens. Em uma função de entropia mais avançada, pesos individuais são atribuídos a cada elemento i∈I, um caso de interesse especial é aquele baseado no princípio da informação mínima (van Zuylen e Willumsen, 1980):

(5.3)

Outro tipo de medidas baseia-se na máxima verossimilhança, que maximiza a verossimilhança de observar a matriz OD de referência e as contagens de tráfego observadas condicionadas à matriz OD estimada. Assume-se que os elementos da matriz OD de referência são obtidos como observações de um conjunto de variáveis aleatórias. Para um sistema distribuído segundo Poisson com um fator de amostragem ρ, a medida objetivo pode ser formulada como:

(5.4)

\(F_2\) pode ser formulado de maneira semelhante à de (5.2) ou (5.4).

Um tipo de função objetivo que está se tornando mais usado nesses modelos é aquele baseado na formulação de mínimos quadrados, como por exemplo:

(5.5)

que podem ser ponderadas usando as informações sobre a significância de cada observação, como, por exemplo, quando as medições contidas em \(\hat{v}\) são calculadas como médias a partir de um conjunto de observações para cada link; então, neste caso, podemos usar a variância σ^2^~a~ como uma medida de quão importante é cada observação de ligação e, portanto, reformular (5.5) como:

(5.6)

Uma desvantagem das abordagens de maximização de entropia, conforme formuladas em (5.1), está no tratamento da observação de fluxo em links como restrições e, portanto, como livres de erro (Bell e Iida, 1997). Uma forma de tentar superar essa desvantagem é usar uma abordagem de mínimos quadrados generalizados para fornecer uma estrutura que permita erros provenientes de várias fontes; o método também produz erros padrão para a tabela de viagens, indicando assim a robustez relativa dos valores ajustados. O método foi proposto pela primeira vez por Cascetta (Cascetta, 1984).

O problema de otimização equivalente tem a forma:

(5.7)

As entradas são estimativas prévias dos fluxos OD, \(\hat{g}\), medições de fluxo do link \(\hat{v}\), matrizes de variância-covariância das estimativas prévias e das medições de fluxo nos links (X e Y respectivamente), e a matriz de proporções de escolha de links P(g). Como as matrizes de variância-covariância são definidas positivas e a função objetivo é convexa, o mínimo é dado de forma única por:

(5.8)

Isso resulta no seguinte estimador linear:

(5.9)

Ao contrário do modelo de entropia máxima, não há nada que impeça que valores ajustados negativos para os fluxos OD sejam produzidos pelo estimador de mínimos quadrados generalizados. Embora valores negativos refletissem valores reais pequenos, ainda assim são contraintuitivos. Bell (Bell, 1991) considerou a introdução de restrições de não negatividade para a matriz OD ajustada.

É bem conhecido que, em geral, existem muitas matrizes OD que, quando atribuídas à rede, podem induzir fluxos equivalentes nos links observados. O conjunto de restrições na formulação genérica do problema (5.1) para determinar g:

(5.10)

consiste em uma equação para cada observação de fluxo de link e, portanto, é um sistema de equações indeterminado enquanto o número de pares OD |I|, é maior que o número de observações de fluxo dos links |\(\hat{A}\)|, e isso é especialmente verdadeiro para grandes redes reais. Além disso, as informações transferidas pelo sistema de equações são delimitadas por dependências topológicas. Um princípio básico em fluxos típicos de rede é que, para fluxos consistentes, as equações de balanço devem ser satisfeitas ou, em outras palavras, a soma dos fluxos de entrada e de saída em qualquer nó intermediário deve ser zero; um princípio que também pode ser interpretado em termos físicos pela lei de Kirchoff. Isso significa que, para cada interseção, pelo menos um fluxo de ligação é linearmente dependente dos demais, o que resulta em uma dependência por linha para o sistema de equações.

Por outro lado, os elementos não nulos \(p_{ia}(g)\) são diferentes de zero porque o link a faz parte de um ou mais caminhos mais curtos para o par OD i∈I. No entanto, como todo subcaminho de um caminho mais curto é um caminho mais curto, todo par de nós ao longo de um determinado caminho mais curto também está conectado por partes desse caminho mais curto, e isso resulta em uma dependência por coluna para o sistema de equações.

Assim, podemos concluir que o sistema de equações (5.10) muito provavelmente não tem posto completo, o que aumenta ainda mais a liberdade de escolha para o problema de estimação OD e, portanto, a forma de determinar o \(p_{ia}(g)\) torna-se crucial para a qualidade do modelo de estimação da matriz OD, e isso geralmente é feito em termos de como a matriz de alocação P(g) é calculado, e se é dependente de g ou não ou, em outras palavras, se as escolhas de rota são feitas em relação ao congestionamento ou não.

Se a alocação da matriz OD na rede for independente dos fluxos dos links, isto é, se tivermos uma rede não congestionada, P(g)=P é uma matriz constante. Nesse caso, o primeiro conjunto de restrições em (5.10) pode então ser formulado como:

(5.11)

Além disso, esta substituição pode ser realizada diretamente no objetivo, ou seja, na função \(F_2(v,\hat{v})\), o que reduz a estimação da matriz OD a um problema na variável g apenas. Assumindo que as medidas de desvio \(F_1\) e \(F_2\) são convexas, e o conjunto de matrizes OD viáveis &Omega; é linear, ou pelo menos convexa, o problema de estimação OD pode ser resolvido facilmente com algum algoritmo padrão adequado de programação não linear; esta é a abordagem usual adotada na maioria dos casos (van Zuylen e Willumsen, 1980).

A hipótese de que a alocação, isto é, a escolha de rota, é independente da carga nos links pode ser considerada realista apenas em uma rede com uma taxa de congestionamento muito baixa, ou em redes nas quais, na prática, apenas uma rota pode ser usada.

Se assumirmos que a rede está congestionada e que as rotas são escolhidas em relação aos tempos de viagem atuais, as proporções de rota dependem da situação atual do tráfego, que por sua vez depende da matriz OD. Assim, a relação entre as proporções de rota P e a matriz OD g só pode ser definida implicitamente. O conjunto de soluções viáveis para o problema de estimação (5.1) é definido como todos os pontos (g,v) em que v é a solução de fluxo do link que satisfaz uma atribuição da demanda correspondente g, então o problema genérico de estimação de matriz OD (5.1) pode ser reformulado como um programa de otimização bilevel da seguinte forma:

(5.12)

na qual queremos encontrar o \(g\) que minimiza \(F(g,v)\) sujeito a ∈Ω, sob a hipótese de que o fluxo do link induzido \(v\) satisfaz as condições de atribuição em equilíbrio obtidas resolvendo o problema de nível inferior:

(5.13)

O núcleo da heurística implementada no Aimsun Next é um método de ajuste baseado em um método de otimização em dois níveis (Florian e Chen, 1995; Codina e Barceló, 2004). O algoritmo pode ser entendido como o cálculo de uma sequência de matrizes OD que reduzem consecutivamente o erro de mínimos quadrados entre contagens de tráfego provenientes de detectores e fluxos de tráfego obtidos por uma alocação de tráfego. A estimação da matriz OD requer informações sobre as rotas usadas pelas viagens contidas na matriz OD \((d_{ij})\). Isso requer a definição da rota e das proporções de viagens em relação ao total de viagens \(d_{ij}\) usado em cada rota originada na zona \(i\) e terminando na zona \(j\). Essa informação é difícil de manipular e armazenar em bancos de dados de tráfego, levando em conta que o número de rotas conectando todos os pares Origem-Destino em uma rede conectada pode crescer exponencialmente com o tamanho da rede. Essa é a razão pela qual é usada uma abordagem de programação matemática baseada em um algoritmo de alocação de tráfego, que é resolvida a cada iteração sem exigir a definição explícita das rotas.

O procedimento de ajuste por otimização bilevel de Spiess (Spiess, 1990) resolve o seguinte problema de otimização não linear bilevel:

(5.14)

em que \(v_a(g)\) é o fluxo no link \(a\) estimado pelo problema de atribuição de tráfego de nível inferior com a matriz de viagens ajustada \(g\), \(h_k\) é o fluxo no \(k-th\) caminho para o i-ésimo par O-D, e \(\hat{v}_a\) é o fluxo medido no link \(a\). \(I\) é o conjunto de todos os pares Origem-Destino na rede, e \(K_i\) é o conjunto de caminhos que conectam o \(i-th\) par OD. \(s_a(v_a)\) é a função volume-atraso para o link a∈A. O algoritmo usado para resolver o problema é de natureza heurística, do tipo descida mais íngreme, e não garante que um ótimo global para o problema formulado será encontrado. O processo iterativo é o seguinte:

Na iteração \(k\):

• Dado um \(s_o\) solução \(g^k_i\), uma atribuição de equilíbrio é resolvida, fornecendo fluxos nos links \(v^k_a\), e proporções {\(p^k_{ia}\)} satisfazendo a relação

  

• A matriz de referência é usada na primeira iteração (i.e.)

  

• O gradiente da função objetivo \(F(v(g))\) é calculado com base na alteração relativa na demanda, de modo que uma alteração na demanda seja proporcional à demanda na matriz inicial e os zeros sejam preservados no processo. Isto é escrito como:

  

• O gradiente é aproximado por:

  

em que \(\hat{A}\)⊂A é o subconjunto de links com contagens de fluxo e \(p_k=h_k/g_i\).

O comprimento do passo é aproximado como:

em que

Para garantir a convergência, o comprimento do passo deve satisfazer a condição:

Se a condição for violada por algum \(i\) então o comprimento do passo deve ser limitado de acordo: