Uma cidade sem engarrafamentos

Capítulo 2
( o link para o capítulo 1 )

A arte de projetar redes rodoviárias

Problemas de transporte de uma cidade através dos olhos de um cientista da computação

Se me recomendassem um artigo com o título “A arte de projetar redes de estradas”, perguntaria imediatamente quantas redes de estradas foram construídas com a participação de seu autor. Devo admitir que minha atividade profissional estava longe da construção de estradas e foi recentemente associada ao projeto de microprocessadores, onde eu, entre outras responsabilidades, estava envolvida no consumo de recursos da troca de dados. Naquela época, minha mesa estava do outro lado da janela panorâmica, que dava uma bela vista da longa seção da Rodovia Volgograd e parte do Terceiro Anel de Transporte, com seus intermináveis ​​engarrafamentos de manhã à noite, de horizonte a horizonte. Um dia, tive um choque repentino de reconhecimento: “As complexidades do processo de troca de dados com as quais luto em um chip podem ser semelhantes às dificuldades que os carros enfrentam à medida que fluem pelo labirinto da rede rodoviária”.
Provavelmente, essa visão de fora e a aplicação de métodos que não eram tradicionais para a área em questão me deram a chance de entender a causa dos engarrafamentos e fazer recomendações sobre como superar o problema na prática.

Então, qual é a novidade da abordagem?

Historicamente, o principal objetivo das estradas é considerado a oportunidade que elas oferecem para viajar longas distâncias rapidamente (entre Roma e as províncias). Tal julgamento é justificado quando se trata da rede de rodovias interurbanas no nível federal: as cidades que eles conectam parecem pequenos pontos raros no atlas, e a maioria dos carros que viajam entre essas cidades passa pelo seu caminho sem virar para lugar nenhum.

No entanto, assim que virarmos várias páginas e abrirmos um mapa detalhado de uma cidade grande, a imagem mudará imediatamente: o número de endereços em que a jornada pode ser iniciada ou finalizada chega a aproximadamente dez mil, todos eles estão bastante difundidos e tamanho relativamente pequeno. Ao mesmo tempo, centenas de milhares de carros podem estar em movimento nas ruas de uma cidade ao mesmo tempo. Além disso, o objetivo de cada um deles não é apenas encher estradas já vazias, mas mover uma pessoa ou carga de um veículo. ponto com um endereço específico X para um ponto com um endereço específico Y. Juntos, isso significa que o sistema de transporte urbano deve ser adaptado para resolver efetivamente o problema de vários endereços simultâneos. Assim, as funções do sistema de transporte urbano tornam-se ainda mais semelhantes à rede telefônica ou de computadores do que à rede rodoviária interurbana.

Considerar a rede rodoviária como um circuito de comutação para um desenvolvedor ou engenheiro de hardware no campo das tecnologias de transferência de informações é uma maneira completamente natural de falar sobre um problema, mas entre as pessoas envolvidas na pesquisa de problemas de transporte, essa visão é, pelo que sei, novo.

A teoria da troca de sinal é uma ciência de engenharia estreita e, por si só, não é suficiente para planejar uma rua, entroncamento ou prever o comportamento de um fluxo de tráfego em uma seção reta e isolada de uma rodovia. Felizmente, os problemas listados acima são bem pesquisados ​​hoje e os métodos desenvolvidos para resolvê-los já foram implementados com sucesso. A teoria da troca, por sua vez, permite ao arquiteto mitigar o risco, no qual a cidade entra em colapso do transporte, apesar de todos os elementos da rede rodoviária serem executados perfeitamente. Esse risco existe porque a realização de vários endereços simultâneos é uma tarefa que consome tempo e recursos, cuja chave não é uma solução efetiva na largura das ruas e na conveniência das trocas de transporte, mas na escolha competente de qual comutação específica esquema que a rede viária proposta implementará.

A partir desta pesquisa, por exemplo, você descobrirá por que o tipo "arterial" de redes de transporte, que ainda são frequentemente usadas nas cidades modernas, é "ruim" e, junto com o crescimento da população, necessariamente levará a congestionamentos. Outro resultado interessante, que está de acordo com as observações, explica por que a expansão das estradas sozinha, se antes de todos os congestionamentos ocorrerem exclusivamente nas proximidades das trocas, dificilmente melhorará a situação, mesmo que o número de carros em circulação. a cidade continua a mesma.

Quando escrevi este artigo, era crucial para mim que fosse compreensível para o arquiteto mais comum, pudesse ser útil através de seu trabalho. Tentei introduzir o leitor na troca de questões em uma linguagem simples, para desenvolver critérios para avaliar o desempenho de uma determinada rede de estradas com a tarefa de endereçamento simultâneo e, usando exemplos de modelos, mostrei como usar esse conhecimento na prática.

O artigo é destinado a um amplo círculo de leitores que estão um pouco familiarizados com o curso universitário de matemática, a teoria dos algoritmos e estão prontos para dedicar de 1 a 5 dias a ele.

Separação e fusão de fluxos de automóveis

É uma observação óbvia para muitos motoristas que as dificuldades de trânsito surgem principalmente naquelas partes da estrada em que os carros, por algum motivo, são forçados a mudar de faixa. Exemplos incluem garfos, estreitamentos, áreas adjacentes às saídas e estradas de acesso à rodovia, trechos de rodovias onde algumas faixas são bloqueadas por um acidente ou obras na estrada.
Nesta seção, será feita uma tentativa de fornecer uma descrição quantitativa dos processos que ocorrem nesses casos, e começaremos entendendo como os carros trocam de faixa.

Duas estratégias para mudar para uma faixa de tráfego adjacente
O tráfego ao longo de uma rodovia tem uma irregularidade natural: alguém prefere dirigir um pouco mais rápido, alguém um pouco mais lento, entre alguns carros a distância diminui e fica pouco confortável para dirigir, enquanto entre outros aumenta tanto que permite que os carros se encaixem lá de faixas adjacentes. O aparecimento de tais lacunas no fluxo da faixa adjacente diretamente no lado do motorista aleatório pode ser frequente ou não muito. Se, no momento em que ele precisar fazer uma manobra, não houver espaço, o motorista poderá recorrer a pelo menos duas estratégias comportamentais:

Estratégia 1
Várias lacunas adequadas podem simplesmente ser localizadas perto da localização do motorista. Se o movimento for denso o suficiente, é improvável que o motorista seja capaz de aumentar a velocidade e captar a folga necessária, mas, diminuindo um pouco, o motorista deixaria os vizinhos transmitirem o carro para que se tornassem iguais à folga que estava originalmente para trás - não seria um grande problema. Os custos dessa estratégia são óbvios: o próprio motorista e os carros que estão atrás na pista perdem algum tempo devido à necessidade de reduzir a velocidade.

Estratégia 2
Para esperar, você precisa ter paciência e o tempo necessário para isso. Uma alternativa pode ser uma tentativa de executar a manobra necessária "aqui" e "agora". De acordo com essa idéia, o motorista dá um sinal para os carros atrás dele da faixa para a qual ele vai se mudar. Aqueles, por sua vez, em resposta ao sinal dele, deviam desacelerar um pouco e "deixar os carros que se moviam na frente deles avançarem", criando assim a lacuna do tamanho necessário em seu fluxo. Os custos de tempo, neste caso, são distribuídos entre os carros da pista, para os quais o motorista eventualmente muda.

Na vida real, ambas as estratégias estão envolvidas ao mesmo tempo: a princípio, o motorista diminui a velocidade, aguardando uma lacuna relativamente grande no fluxo da faixa adjacente e, somente depois disso, eles sinalizam os carros que se movem nela. sobre sua intenção de fazer uma manobra de mudança.

Sem dúvida, as estradas de acesso, as saídas e os estreitos das rodovias não são a única razão para a troca de faixas, o que vale lembrar ao projetar estradas. A capacidade dos carros com velocidades mais altas de ultrapassar o tráfego sem pressa é necessária para evitar a situação na rodovia quando ela se degrada para uma fila grande que se arrasta à velocidade do trator mais lento. No entanto, o problema da coexistência de veículos que circulam em velocidades diferentes tem uma natureza um pouco diferente e pode ser separado das questões em questão, uma vez que o processo de ultrapassagem e a respectiva troca entre faixas não são forçados para o motorista. Se o motorista não se apressar, de acordo com a teoria das probabilidades, uma oportunidade conveniente para realizar uma manobra será dada ao motorista naturalmente e, para isso, ele não precisa atrapalhar o movimento de outros motoristas.

O custo de uma única troca
O comportamento dos motoristas na realidade pode ser muito complicado, mas é fundamental para nós que o resultado obtido nas condições do modelo permaneça plausível: cada troca forçada entre faixas impõe uma multa de tempo aos participantes do trânsito.

Vamos agora avaliar como a quantidade de tempo perdido depende da densidade do tráfego na estrada.

Vamos considerar o movimento ao longo de cada pista como um fluxo separado. Tentando permanecer a uma distância confortável dos carros na mesma faixa, os motoristas reservam, assim, um trecho de estrada com um determinado comprimento característico d no fluxo. Deixe os carros caírem em um fluxo por unidade de comprimento. Concordamos em chamar a densidade de fluxo pequena ou dizer que ρ é pequeno se o produto ρ × d for muito menor que 1.

No momento em que o motorista percebe a necessidade de passar para a próxima linha, a probabilidade de uma estrada com o comprimento d que o motorista iria ocupar não será livre, em ρ pequeno, será aproximadamente proporcional a ρ em si. Se o evento descrito realmente ocorrer, dois carros competindo por um lugar sofrerão no total, como resultado das manobras, algum atraso no valor constante médio δ .

Supondo que ρ seja pequeno, podemos negligenciar a probabilidade de que suas ações neste momento afetem o movimento de outros carros. Assim, quando ρ é pequeno, a perda de tempo de uma comutação será α⋅ρ , onde o coeficiente α é uma quantidade empiricamente mensurável, dependendo da cultura, clima, limites de velocidade (e assim por diante), mas permanecendo aproximadamente constante nesse tempo específico e para esta cidade como um todo.

Taxa de intensidade de perda em um trecho de estrada antes da saída
Os carros que se dirigem para a saída, antes de chegarem à rampa (Gráfico 2), precisam, algumas vezes até várias vezes, mudar para a linha adjacente à direita. Cada uma dessas manobras atrapalha o fluxo e, como resultado, a velocidade média na seção antes da saída é notavelmente mais baixa do que nas seções de "trânsito" (privadas de saídas, entradas e garfos) da rodovia.


Quadro 2

Passar parte do caminho em velocidade mais baixa - representa para os motoristas (e seus passageiros) uma quantidade adicional de tempo gasto na viagem. Em outras palavras, a área da rodovia adjacente à saída é um gerador constante de perdas de tempo.

Suponhamos que a velocidade média do carro ν e a densidade do fluxo ρ no limite frontal desse trecho sejam as mesmas para todas as faixas.

Além disso, vamos supor que a densidade ρ e a vazão q em direção à saída (o número médio de carros que caem na rampa por unidade de tempo) sejam simultaneamente pequenas e s é o número de faixas na rodovia. Para chegar à saída, o motorista fará 1 a s manobras de comutação. Se a densidade do fluxo na rampa for muito menor que ρ , somente a última manobra será para o motorista praticamente "de graça", enquanto o restante causará, em qualquer caso, perdas de α⋅ρ . Em média, você terá que realizar (0 + 1 + 2 + ... + s - 1) / s = ( s - 1) / 2 manobras "caras".

Dadas as dificuldades causadas por todos os carros que se dirigem para a saída, podemos criar a fórmula para a intensidade das perdas de tempo:

I _out = q ⋅ α ρ ⋅ ( s - 1) / 2 = ( α / 2 ν ) ⋅ q ⋅ ( sρν ) ⋅ (1 - 1 / s )

O valor p = ( sρν ) nada mais é do que a vazão de todos os carros que se deslocam pela estrada na direção em questão (o número médio de carros passando por um ponto de ônibus por unidade de tempo). A última observação nos dá a oportunidade de reescrever a fórmula para uma forma mais simétrica:

I _out = ( α / 2 ν ) ⋅ pq ⋅ ( 1-1 / s )

Taxa de intensidade de perda na seção adjacente da via de acesso
A situação que surge na estrada atrás da seção onde a estrada de acesso se conecta a ela repete amplamente a situação na seção antes da saída, embora existam algumas diferenças. Deixe que um pequeno fluxo de carros de força q atravesse a rampa lateral despeje no tráfego principal da rodovia (Gráfico 3).


Quadro 3

A rampa tem apenas um comprimento finito; portanto, todos os carros recém-chegados devem ser trocados para a faixa da borda direita da rodovia. Como resultado, a densidade de tráfego na faixa da margem direita1 é localmente mais alta que a média na estrada, por isso alguns motoristas decidem mudar para uma faixa adjacente menos movimentada à esquerda, o que, por sua vez, leva a uma faixa local. aumento da densidade já na segunda faixa. Esse processo de alternância entre faixas continuará até que a densidade do fluxo seja nivelada em toda a largura da rodovia. Supondo que a velocidade média ν seja a mesma para todas as n faixas, podemos esperar que, após a conclusão dos processos de comutação, a potência de fluxo em cada uma delas aumente exatamente (1 / s ) ⋅ q .

Para ver quanto essa troca custará aos motoristas, calculamos primeiro a potência de todos os fluxos de troca. O fluxo da rampa para a primeira faixa da rodovia já sabemos: é igual a q . Para equiparar o aumento da potência da primeira faixa a (1 / s ) ⋅ q , o fluxo da primeira faixa para a segunda deve ser (1 - 1 / s ) ⋅ q , da segunda para a terceira = ( 1 - 2 / s ) ⋅ q , de k -ésimo a ( k + 1) th = (1 - k / s ) ⋅ q . De acordo com a última fórmula, a capacidade do fluxo de comutação para a faixa da borda esquerda será (1 - ( s - 1) / s ) ⋅ q = (1 / s ) ⋅ q , conforme ordenado pelo senso comum.

Como sabemos a penalidade de tempo de uma única comutação e a potência de todos os fluxos de comutação, agora podemos calcular a intensidade total das perdas geradas por elas:

I _in = α ρ ⋅ q + α ρ ⋅ (1 - 1 / s ) ⋅ q + α ρ ⋅ (1 - 2 / s ) ⋅ q + ... + α ρ ⋅ (1 / s ) ⋅ q =

α ρ q (1 + 2 + ... + s ) / s =

α ρ q ( s + 1) / 2 =

( α / 2 ν ) ⋅ q ⋅ ( sρν ) ⋅ (1 + 1 / s ).

Lembrando novamente que sρν é a potência p do fluxo de todos os carros ao longo da rodovia, obtemos a fórmula de custo em sua forma final:

I _em = ( α / 2 ν ) ⋅ pq ⋅ (1 + 1 / s ).

Taxa de intensidade de perda no garfo simétrico
Nos parágrafos anteriores, encontramos perdas com a interação dos fluxos, um dos quais era necessariamente grande e o outro era necessariamente pequeno. Para demonstrar uma abordagem para resolver problemas quando as capacidades de ambos os fluxos são comparáveis ​​em potência, vamos considerar outro extremo: um garfo no qual ambas as direções de ramificação são igualmente populares para os motoristas (Quadro 4).


Quadro 4

Por conveniência, os carros que vão para a direita na bifurcação serão chamados de "azul" e os carros que sairão para a esquerda - "vermelho". Inicialmente, carros de ambas as "cores" se movem misturadas, dispersas entre as duas faixas da rodovia. Quando se aproximam da bifurcação, os carros vermelhos começam a vagar lentamente em direção às n faixas da esquerda e os azuis na direita: há fluxos de mudança nas duas direções entre as faixas adjacentes. Ao contrário do exemplo da via de acesso, esses fluxos não são mais "relativamente pequenos". A propósito, somente entre as duas faixas centrais há uma troca forçada de tráfego, cuja intensidade em qualquer uma das direções (da esquerda para a direita ou da direita para a esquerda) é igual a um quarto da potência de todo córrego se movendo ao longo da estrada. Felizmente, nessa situação, existe uma maneira boa o suficiente para estimar os custos gerados.
Inicialmente, podemos observar que o processo de dividir os carros em "vermelho" e "azul" provavelmente começa muito antes da bifurcação e prossegue lentamente; portanto, por um lado, deve ter pouco efeito na densidade de tráfego em uma linha separada e, por outro, faça com que os fluxos de comutação se estendam por longas distâncias, dando a oportunidade de representar cada um deles como uma combinação de um grande número de fluxos de baixa potência (Gráfico 5).



Quadro 5

Como agora estamos falando de pequenos fluxos, embora em números maiores, nada nos impede de reduzir o problema em questão aos já resolvidos. Podemos dividir mentalmente a rodovia no centro em duas partes iguais e conectá-las a um número maior de estradas de ponte de pista única, permitindo que carros vermelhos cheguem à esquerda e carros azuis à direita (Gráfico 6). Devido à simetria óbvia, ao calcular as perdas geradas, podemos nos concentrar em carros de qualquer cor, por exemplo, azul e, no final, apenas dobrar o resultado.


Quadro 6

Seja a velocidade ν e a densidade ρ iguais para todas as faixas e permaneça constante durante todo o trecho em que os carros são separados por cores. Nesse caso, a potência de fluxo de todos os carros que circulam pela estrada será:

p = 2 sρv .

Seja q ₁ , q ₂ , ... q _m denota o fluxo de carros azuis que se deslocam ao longo de estradas imaginárias para a metade direita da rodovia. Suponha que, pouco antes da seção de separação em cada faixa da rodovia, as duas cores sejam representadas com proporções iguais de 50%, o que implica que, no total
q ₁ + q ₂ + ... + q _m é igual a sρv / 2, ou seja, p / 4.

Perdas geradas pelo fluxo q _i devido à sua pequenez, podemos calcular pela fórmula:

I _i = I _out + I _in = ( α / 2 ν ) ⋅ ( p / 2) ⋅ q _i ( 1-1 / s ) + ( α / 2 ν ) ⋅ ( p / 2) ⋅ q _i (1 + 1 / s ) = ( α / 2ν ) p q _i

Resumindo a última fórmula sobre todos os i , encontramos as perdas geradas apenas pelos carros azuis:

I _azul = ( α / 2 ν ) ⋅ p ⋅ ( q ₁ + q ₂ + ... + q _m ) = ( α / 2 ν ) p 2/4.

As perdas totais, como já mencionado, serão duas vezes maiores e equivalem a:

I _div = ( a / 2 v ) p 2/2 .

Análise das fórmulas obtidas
Se dividirmos a intensidade I , que é a quantidade de tempo totalmente perdida pelos participantes por segundo, pelo fluxo lateral q , que por definição é igual ao número de carros que conectam ou saem da rodovia em um segundo, obteremos o perdas médias causadas por um desses carros:

i _in = I _in / q = ( α / 2 ν ) ⋅ p ⋅ (1 + 1 / s )

i _out = I _out / q = ( α / 2 ν ) ⋅ p ⋅ ( 1-1 / s )

Talvez o mais importante nessas fórmulas seja a proporcionalidade direta entre o fluxo de potência dos carros na rodovia pe os custos unitários i . Tudo parece como um carro tentando entrar ou vice-versa - para sair do fluxo principal, causando perturbações constantes para todos os motoristas próximos.

A segunda observação interessante e muito inesperada diz respeito ao efeito extremamente fraco sobre a intensidade das perdas geradas no número de faixas próximas à rodovia, diretamente ao lado do entroncamento. Como você pode ver, observando a fórmula de I _out , a saída geralmente é a mais eficiente em termos de tempo para uma estrada de pista única ( s = 1, i _out = 0) e as dificuldades causadas pela estrada de acesso adjacente a uma estrada. rodovia de três e seis pistas diferem apenas por

100% ⋅ [(1 + 1/3) - (1 + 1/6)] / (1 + 1/3) = 12,5%.

Se considerarmos que todo carro que já entrou no trânsito na rodovia terá que abandoná-lo, parece bastante legítimo usar um valor unificado em vez de i _in e i _out ao calcular perdas de intercâmbio

i _av = ( i _in + i _in ) / 2 = ( α / 2ν ) ⋅ p .

Apesar do fato de que a fórmula para _av não depende explicitamente do número de faixas, deve-se lembrar que sua criação (veja as suposições de entrada e _saída ) se baseia fortemente na suposição de baixa densidade de carros na estrada , portanto, é improvável que você obtenha resultados satisfatórios quando aplicado a uma rodovia muito estreita com muito tráfego.

Conclusões preliminares
Em áreas próximas a cruzamentos, inevitavelmente ocorrem obstáculos ao tráfego, afastando o tempo dos motoristas, reduzindo a velocidade média, o que leva a um aumento na densidade de carros e, consequentemente, à possível ocorrência de engarrafamentos. As perdas de tempo associadas à separação e fusão dos fluxos de automóveis serão denominadas perdas de comutação.

Perdas de um tipo semelhante estão presentes de uma maneira ou de outra em qualquer esquema de comutação: seja uma rede telefônica ou de computador, um microprocessador multinúcleo ou um serviço de entrega de correio.

Quando o motorista entra ou, inversamente, deixa o tráfego na rodovia, os custos de troca incorridos por suas ações são proporcionais à potência do fluxo de carros observado naquele momento na rodovia.

Para reduzir as perdas de comutação em toda a cidade, é necessário considerar cuidadosamente a rede de estradas implementada na fase de projeto. Um pouco mais tarde, analisaremos essa tarefa em detalhes, mas algumas recomendações óbvias podem ser listadas agora:

1. as perdas de comutação são proporcionais à potência do fluxo na rodovia - não é necessário ampliar as estradas sem a necessidade, duas pequenas rodovias são duas vezes melhores que uma grande;
2. as perdas de comutação são proporcionais à potência dos fluxos laterais - vale a pena projetar a rede para que o motorista gire o menor número de vezes possível durante sua jornada;
3. as perturbações mútuas causadas pelos motoristas dos fluxos principal e lateral devem ser menores em toda a cidade, se tentarmos impedir a fusão de rotas que se sobrepõem apenas em um pequeno trecho da estrada.

Pré-requisitos econômicos para a existência de cidades.
Um modelo de cidade com 'acesso aleatório' ²

(Nota 2: o termo é retirado do conceito de RAM e significa aleatório por probabilidade e até por consumo de tempo.)
Talvez a primeira etapa de qualquer projeto para projetar (ou redesenhar) o sistema de transporte da cidade seja tentar determinar que tipo de mudança a cidade realmente precisa agora e como suas necessidades mudarão no futuro.

Essa análise pode ser realizada se primeiro dividirmos a cidade em áreas não muito grandes, mas não muito pequenas, e depois, para cada par dessas zonas, indicar que número aproximado de viagens a um lado ou outro é necessário para seus habitantes. uma ou outra hora do dia. Ao colocar as previsões feitas em uma matriz, você receberá uma matriz de necessidades de migração dos moradores da cidade.

Exatamente para essa matriz, devemos procurar uma rede que permita que motoristas e passageiros passem o mínimo de tempo possível em uma viagem separada, exigindo das autoridades da cidade o mínimo de recursos possível para a realização da rede.

Quando se trata de cidades existentes, é importante aqui não cometer um erro e não substituir o número de viagens que as pessoas realmente precisam pelo número de viagens que historicamente foram estabelecidas sob a influência de alguns obstáculos ou dificuldades no momento da o trabalho de design. Provavelmente, a rede de transporte de Berlim "antes" e "depois" da queda do muro de separação pode servir como a ilustração mais impressionante do que foi dito.

Esta seção tratará principalmente de questões humanitárias nas quais eu não sou especialista, mas acho que discuti-las como amador é, no entanto, mais correto do que simplesmente evitar o problema.

Para melhor representar as necessidades migratórias da população, vale a pena começar com a pergunta fundamental: “Para que servem as cidades e qual é sua função útil?”

Vamos tentar responder não como moradores comuns das cidades (e vilas), mas da perspectiva da pessoa responsável pelo processo de urbanização em algum estado grande e desenvolvido. Deste ponto de vista, não é mais importante quais motivos históricos fizeram tantas pessoas amontoadas em um pequeno pedaço de terra, ou as razões pelas quais continuam a fazê-lo agora, é crucial - que efeito econômico é feito pelas cidades de um tamanho ou de outro e por quais mecanismos esse efeito é alcançado.

Na minha opinião, a principal razão para a existência de grandes cidades é, por um lado, a oportunidade para as empresas de tecnologia encontrarem funcionários de profissões raras e, por outro lado, a oportunidade para as pessoas que dominam profissões raras venderem seus produtos. serviços para empresas interessadas neles em termos competitivos. Em uma cidade pequena (não especializada), a produção de muitos bens e serviços é simplesmente impossível ou coloca as empresas de tecnologia e seus funcionários na posição de reféns mútuos, sem dar alternativas a uma ou a outra.

Por exemplo, considere a profissão não tão rara de um professor de literatura escolar. Segundo as estatísticas, a necessidade deles é de aproximadamente 1 professor por 1.000 pessoas. Em uma escola regular, 3-4 tutores ensinam literatura. A escolha de um emprego para um professor de literatura pode ser considerada competitiva se houver pelo menos 4-5 escolas secundárias na cidade, o que, em termos de população, corresponde a cerca de 15 mil pessoas.

Aparentemente, pessoas com especialização em engenharia se sentem à vontade no mercado de trabalho em cidades com uma população de pelo menos 100 mil. É claro que existem também essas profissões, cuja demanda aparece apenas em cidades com mais de um milhão de pessoas; no entanto, a existência de milhões de cidades não faz nenhum sentido econômico para mim.

Depois de tudo mencionado acima, duas hipóteses parecem bastante razoáveis ​​(cuja validade, no entanto, não afeta a verdade do conteúdo principal do artigo):

1. o adulto médio precisa viajar com mais frequência por distâncias que capturam 4-5 dos trabalhos mais promissores para eles;
2. para uma parte significativa da população que representa as profissões raras e economicamente mais valiosas, a distância das viagens mais frequentes pode ser comparável ao raio de sua cidade.

Como uma reflexão aprimorada das hipóteses 1 e 2, em meus exemplos, usarei frequentemente o modelo da cidade com 'acesso aleatório', assumindo que o poder dos fluxos de viagens necessárias seja o mesmo entre dois quartos dela, ou em outras palavras, em todas as células da matriz de necessidades de migração, há o mesmo número positivo. Se você observar aleatoriamente os registros de viagens feitas em uma cidade durante o dia, para a próxima viagem marcada, todos os trimestres terão a mesma probabilidade de ser o início ou o término dessa viagem e nenhuma relação entre a posição da os quartos 'inicial' e 'final' devem ser observados.

Redes rodoviárias com a topologia mais simples

Vamos tentar aplicar as idéias descritas nos parágrafos anteriores a alguns tipos de planos urbanos retirados da vida.

Cidade linear

Os primeiros grandes assentamentos foram originados predominantemente ao longo da costa, em áreas de uma fina faixa de terra entre o mar e as falésias, ou ao longo dos caminhos de estradas movimentadas; assim, no processo de crescimento, eles adquiriram estreitas fronteiras alongadas. Muitos desses assentamentos sobreviveram até os dias atuais, mantendo sua forma alongada e se transformando em cidades modernas (veja a ilustração abaixo).


(uma área excluída do Rio de Janeiro, o autor é desconhecido)

Muitas vezes, em uma cidade assim, existe apenas uma estrada larga em torno da qual ela é construída. Suponha que cada quarto (zona de divisão territorial) gere um fluxo de viagens com potência 1, o número de todos esses quartos seja igual a n , e a própria cidade siga o modelo de migração de 'acesso aleatório'.


Quadro 7

Vamos tentar encontrar para os parâmetros listados acima como o tempo médio de viagem e a área necessária da estrada mudam com o aumento de n .

Portanto, permita que todos os quartos tenham a mesma forma e tamanho, e seu número se multiplique por λ (lambda) vezes. É óbvio que

• o comprimento da estrada principal aumenta em um fator de λ .

Devido ao modelo aceito de 'acesso aleatório', 50% das viagens iniciadas na metade direita da cidade terminam na metade esquerda (o oposto também estará correto), portanto, com um aumento no número de trimestres por um fator de λ , a potência do fluxo que passa pelo meio da cidade também se multiplicará por λ vezes. Discussões semelhantes com a mesma inferência serão verdadeiras se, em vez do meio, considerarmos qualquer ponto da cidade em uma determinada proporção (1: 3, 2: 5), o que implica que

• a potência do fluxo ao longo da estrada principal aumenta em um fator de λ ;
• o número de faixas da estrada principal requeridas em cada seção multiplica por λ vezes.

Mais ou menos óbvio que a duração média da viagem e com ela

• o tempo líquido de viagem gasto para cobrir a distância aumenta por um fator de λ .

Tudo o que resta para calcular é o número de vezes que o tempo perdido devido aos custos de troca em uma viagem aumentará. Um fluxo lateral com potência 1 entra e sai de cada trimestre, que juntos geram perdas de tempo com intensidade:

I = I _in + I _out = ( α / 2 ν ) p ⋅ 2,

onde p é a potência do fluxo na estrada principal. Já sabemos que o número de quartos e a potência do fluxo na estrada principal aumentam em um fator de λ ; portanto, as perdas de tempo totais geradas pela rede multiplicam-se por λ ² vezes. Por outro lado, o número de viagens geradas pela rede, entre as quais, como resultado, todas essas perdas são alocadas, aumenta em um fator de λ , por isso

• o tempo líquido de viagem perdido devido aos custos de troca aumenta em um fator de λ .

Vamos exibir todos os resultados em uma tabela:

Topologia linear
O número de pontos de endereço (quartos) com energia 1 ........................ n
Área total da estrada ............................................... ....................................... O ( n ² )
Tempo líquido de viagem,
gasto para cobrir a distância ............................................. ...................... O ( n )
Tempo líquido de viagem,
perdido devido a custos de troca ............................................. ........................ O ( n )
Número de nós de comutação .............................................. ..................... O ( n )
Número de nós de comutação, dada a potência dos fluxos laterais ............. O ( n )

A notação usada ' y = O ( x )' significa que os parâmetros x e y são funcionalmente dependentes e, quando x cresce sem limite, a razão x / y tende a um número finito, diferente de zero.

Cidade celular

O segundo método de planejamento bastante comum é organizar os quartos na forma de uma matriz retangular, semelhante à maneira como as porções são colocadas em uma barra de chocolate.

Concordamos em chamar essas cidades de 'celulares'. ".


(Los Angeles, foto: Slava Stepanov)

O gráfico 8 mostra um padrão de cidade celular que consiste em n (considerando as 'metades') quartos, formando um quadrado regular. Os quartos são separados um do outro por um total de √ n estradas, estendendo-se condicionalmente de oeste a leste, e √ n estradas que se estendem de sul a norte. No total, essas estradas formam cruzamentos √ n × √ n , cada um dos quais pode ser implementado como um cruzamento de semáforos ou através de pontes / viadutos.


Quadro 8

Independentemente de haver tráfego de mão única ou de mão dupla, qualquer viagem do ponto A ao ponto B em uma cidade celular pode ser realizada ao longo de uma rota que envolve não mais que duas ruas e não mais que uma curva em um cruzamento.

Supondo que, como no exemplo anterior, cada trimestre gere um fluxo de viagens com energia 1, e as necessidades de migração da população sigam o modelo de 'acesso aleatório', podemos calcular, agora para uma cidade celular, as leis pelas quais os average travel time and the resource intensity of road network construction will change with increasing quantity of quarters.

Se o número de quartos aumentar por um fator de λ , então:

• a área da cidade se multiplica por λ vezes e suas dimensões lineares, mantendo as proporções - por √ λ ,
• a distância média de viagem e o tempo líquido para cobri-la, sendo proporcional às dimensões lineares, multiplique por √ λ vezes,
• o número de ruas e o número de quartos adjacentes a uma determinada rua multiplicam-se por √ λ vezes,
• a potência do fluxo de tráfego, sendo proporcional ao número de trimestres com os quais o fluxo está 'em contato' (uma explicação desse termo será dada posteriormente), multiplica por √ λ vezes,
• the required area of ​​all roads grows as (number of streets) × (length of one street) × (power of street flow) = √ λ ⋅ √ λ ⋅ √ λ = λ √ λ

Os fluxos laterais são divididos entre os que vão de ou para os bairros e os que passam de uma rua para outra nos cruzamentos. O poder dos primeiros fluxos, de acordo com as condições, sempre permanece igual à unidade. Através dos segundos, quase todo o tráfego está se movendo, chegando ou saindo da rodovia, se levarmos em conta que há muito mais bairros na cidade do que bairros em uma determinada rua. Como resultado, a mudança na potência dos segundos fluxos pode ser estimada pela fórmula (mudança na potência do fluxo) / (aumento no número de cruzamentos em uma rua específica) = √ λ / √ λ= 1. A igualdade da última razão com a constante sugere que esses fluxos não mudam significativamente com um aumento no número de trimestres; portanto, o aumento nos custos de comutação gerados pela rede como um todo será: (aumento no total número de quartos + cruzamentos) × (mudança no valor do fluxo em uma única rua) = λ √ λ . Como a potência do fluxo de migração gerado por todos os trimestres aumentou por um fator de λ , então

• o tempo líquido de viagem perdido devido aos custos de troca aumenta por um fator de √ λ

Vamos exibir todos os resultados em uma tabela:

Topologia celular

O número de pontos de endereço (quartos) com energia 1 ..................... n
Área total da estrada ............................................... .................................... O ( n √ n )
Tempo líquido de viagem,
gasto para cobrir a distância ............................................. ................... O (√ n )
Tempo líquido de viagem,
perdido devido a custos de troca ............................................. .................... O (√ n )
Número de nós de comutação .............................................. .................. O ( n )
Número de nós de comutação, dada a potência dos fluxos laterais .......... O ( n )

Comparando as redes linear e celular, é difícil não notar que o aumento na intensidade de recursos necessários para a construção e o tempo gasto em uma viagem, com o crescimento da cidade, é muito mais rápido para a primeira rede do que para a primeira rede. o segundo. Por exemplo, uma cidade celular composta por 100 quartos requer 10 vezes menos asfalto, e viajar em média requer 10 vezes menos tempo em comparação com uma cidade linear do mesmo tamanho. Portanto, faz sentido usar redes de estradas com topologia linear apenas em cidades muito pequenas.

Se, durante algum tempo, esquecermos a existência de custos de comutação, a topologia celular pode ser considerada uma maneira ideal de projetar redes de estradas, pois fornece uma estimativa O assintoticamente ideal para a duração média da viagem e a área de estrada necessária. De fato, para qualquer localização mais ou menos 'compacta' da cidade (com acesso aleatório), a duração da viagem não será mais lenta do que a raiz quadrada da área da cidade, que por sua vez geralmente é diretamente proporcional à população . Como resultado, obtemos o mesmo O (√ n ).

O fato de uma rota típica em uma cidade celular percorrer uma “esquina” em vez de uma linha reta implica, em princípio, a oportunidade de procurar as melhores maneiras de planejar cidades, mas a economia de 20% (esse é o o máximo que podemos ganhar se os carros aprenderem a atravessar paredes) é improvável que algum dia forçará os arquitetos a abandonar o arranjo retangular de ruas e estradas.

O limite mais baixo possível dos custos de construção (e manutenção) da rede pode ser obtido lembrando-se que cada carro reserva uma parte da faixa para seu movimento. Como resultado, a área total de estradas é proporcional ao produto do tempo médio de viagem (duração média da viagem) e ao número de carros na cidade: O (√ n ) × O ( n ) = O ( n √ n ) (compare com a tabela de uma cidade celular).

Se falamos sobre a quantidade de tempo perdido nas viagens devido aos custos de mudança, surpreendentemente, sua relação com a quantidade de tempo para percorrer a distância não depende assintoticamente do número de quartos na cidade celular ou linear (O (√ n ) / O (√ n ) = O (1), O ( n ) / O ( n ) = O (1)). Em outras palavras, a porcentagem de tempo perdido em viagens devido à mudança, tanto nas grandes como nas pequenas cidades, será a mesma. A partir disso, podemos concluir que, se não houve problemas sérios com os custos de troca em uma cidade pequena (podemos sugerir que eles venceram de 10 a 20%), então em uma cidade grande eles ainda não devem ser observados e, se foram, então eles permaneceriam para existir, não importa como a cidade crescesse e aumentasse.

Como não sabemos qual das alternativas é verdadeira (ou melhor, sabemos que existem problemas com o tráfego nas grandes cidades), vale a pena tentar melhorar a topologia de uma cidade celular para que os custos de troca diminuam pelo menos por um fator de alguns tempos constantes.

Exemplos úteis de redes irrealistas

Vamos testar se a topologia celular segue as recomendações que desenvolvemos analisando a alternância de fluxos na estrada.

1) Não amplie estradas sem a necessidade.
Sim. O tráfego é distribuído por muitas estradas (compare com uma cidade linear).

2) Evite projetar a rede em que o motorista precise girar um grande número de vezes em uma viagem.
Sim. Provavelmente, qualquer viagem será realizada ao longo de uma rota que exige apenas uma curva nas ruas.

3) Tente impedir a fusão de rotas que se sobrepõem apenas em uma seção curta da estrada.
- Aqui, talvez, haja algo para trabalhar. Apesar do número mínimo de voltas por viagem, a rota como parte do fluxo da rodovia principal passa por um grande número de nós de comutação (O ( n )), em cada um dos quais é desperdiçado um tempo valioso.

A última observação motiva a investigar a seguinte pergunta: “Qual é o mínimo do número médio de nós de comutação pelos quais uma jornada deve passar por uma rede de estradas que conecta n trimestres?”

A tarefa de procurar por uma rede desse tipo faz sentido, é claro, apenas com a condição de que o número de fluxos combinados ou divididos por qualquer nó de comutação seja preliminarmente limitado de cima por um determinado valor fixo. Caso contrário, você sempre poderá apresentar uma rede viária com n pontos de endereço e um único mega-entroncamento.


(o autor é desconhecido)

É muito mais fácil investigar o problema real se anteriormente era possível revelar pelo menos parte dos padrões usando alguns exemplos simples, mesmo que nem todos realistas. Seguindo essa lógica, esqueceremos temporariamente as limitações geométricas da construção de estradas e a necessidade dos viajantes de percorrer distâncias, concentrando toda a nossa atenção em como as redes abstratas resolvem o problema do endereçamento paralelo. Em relação aos nós de comutação, assumiremos por enquanto que cada um deles divide o fluxo em duas partes (o nó de divisão) ou combina dois fluxos em um.


Quadro 9

Árvore de endereços
Que exista um ponto de endereço inicial , em que todas as viagens, sem exceção, comecem, e outro n ponto final nos quais eles terminam com igual probabilidade (Quadro 9).

É necessário criar uma rede de transporte que permita ao motorista passar o menor número possível de nós de comutação.

A solução óbvia (para programadores), que se sugere aqui, é usar uma árvore binária balanceada, ao mesmo tempo precisamos colocar um único ponto de início no topo da árvore e colocar os n pontos de acabamento restantes um em cada de suas folhas (Quadro 10). A rede construída da maneira descrita será chamada como a árvore de endereços direta.


Quadro 10

Mudando as direções de todos os fluxos na árvore de endereços direta para o oposto, obtemos assim a árvore de endereços reversa , cujo objetivo é conectar n pontos de partida com um único ponto de chegada.

Nos casos em que n é uma potência de dois, qualquer rota dentro da árvore de Endereços passa exatamente pelo log ₂ n nós de comutação, que é indubitavelmente (assintoticamente) menor que o mesmo indicador para uma rede com celular (O (√ n )), ou topologia linear (O ( n )).

Dois tipos mais simples de redes logarítmicas

Usando redes 'em forma de árvore' como blocos de construção, não é difícil generalizar a solução anterior para o caso quando existem k pontos de partida. Existem duas maneiras fáceis de fazer isso.

A primeira maneira é usar a árvore de endereços reversa para coletar primeiro as rotas de todas as viagens em um fluxo comum e, em seguida, usando a árvore de endereços direta, divida esse fluxo em subfluxos endereçados ao seu destino (Gráfico 11, esquema superior )


Quadro 11

Se k e n são potências de dois, no final, qualquer rota passa exatamente pelos nós de comutação log ₂ k + log ₂ n . Concordamos em nos referir às redes projetadas de acordo com o algoritmo descrito como redes logarítmicas (unidirecionais) com mesclagem preliminar .

A segunda maneira de resolver o mesmo problema pode ser realizada revertendo na primeira solução a ordem das operações de fusão e divisão. Sua implementação pode ser descrita da seguinte maneira: para cada ponto de partida, criamos um conjunto exclusivo de duplicatas imaginárias de todos os pontos de chegada e, em seguida, conectamos a essas duplicatas (não mais imaginárias) com uma árvore de endereços direta.

Para concluir o design da rede, resta apenas conectar agora cada ponto de chegada com suas k duplicatas imaginárias aplicando a árvore de endereços reversa (Gráfico 11, esquema inferior).

Sempre que n e k são potências de dois, o número de nós de comutação ao longo de qualquer rota na rede recém-construída será novamente igual ao log ₂ k + log ₂ n . Concordamos em nos referir a redes como redes logarítmicas (unidirecionais) com divisão preliminar .

Conversão de redes unidirecionais em redes simétricas
Geralmente, nos referimos a qualquer rede como unidirecional se os pontos de endereço conectados por ela forem estritamente divididos em pontos de início e fim. Por padrão, para redes unidirecionais, será assumido que ele fornece pelo menos uma rota de viagem possível de qualquer ponto de início a qualquer ponto de chegada.

Além de uma jornada ao longo da vida, é difícil encontrar exemplos em que alguns pontos de endereço sirvam apenas como o início de uma rota e outros apenas o fim. Aproximaremos nosso raciocínio da realidade se incluirmos redes nas quais dois pontos de endereço estão conectados por rotas em ambas as direções. Concordamos em nos referir a essas redes como simétricas.

De fato, não existe uma lacuna ideológica entre redes unidirecionais e simétricas: cada rede simétrica também pode ser usada como uma rede unidirecional e cada rede unidirecional, conectando inicialmente um número igual de pontos de início e de término, pode ser transformado em simétrico (Quadro 12).


Quadro 12

Os gráficos 13a e 13b mostram as formas 'simétricas' da rede logarítmica com mesclagem preliminar e da rede logarítmica com divisão preliminar. Seus exemplos provam a possibilidade fundamental de conectar n quartos por esse tipo de rede, dentro do qual o número de nós de comutação durante qualquer viagem será proporcional ao logaritmo do número de quartos na cidade.


Quadro 13 a


Quadro 13 b

Estimativa precisa do limite inferior

Uma grande variedade de redes já foi acumulada até agora, cada uma das quais com função própria que descreve a dependência do número médio de nós de comutação ao longo da jornada no número de pontos de endereço na cidade. No entanto, ainda não sabemos quão pequeno esse número pode ser, em princípio, para um determinado número de quartos. A estimativa do limite inferior pode ser obtida usando a abordagem da informação.

Na verdade, permita que uma rede viária conecte n pontos de endereço entre si e as necessidades de migração da população sejam tais que qualquer viagem, não importa onde tenha começado, tenha a mesma chance de terminar em qualquer lugar da cidade.

Para resolver o problema em questão, geraremos uma mensagem informativa auxiliar, seguindo esta receita: por um longo período, coletamos registros de todas as viagens que possuem um ponto de partida fixo e anotamos aleatoriamente os endereços onde essas viagens terminou. A mensagem resultante será uma sequência aleatória que consiste nos nomes de n pontos de endereço da cidade.

Uma maneira de transmitir esta mensagem a Marte é primeiramente codificar todos os nomes em palavras binárias do mesmo tamanho, transformando a mensagem original em uma sequência de 0s e 1s e, em segundo lugar, enviar a sequência resultante através de um canal de comunicação digital. Como para a codificação distinguível do conjunto de n nomes são necessárias palavras binárias de log ₂ n de comprimento, o comprimento da mensagem digital será:

(número de registros) × log ₂ n caracteres.

O mais interessante é que, de acordo com a teoria da informação, independentemente do algoritmo de codificação usado, é simplesmente impossível transmitir a mesma mensagem com um número menor de caracteres binários.

Uma alternativa para transmitir diretamente os nomes codificados dos pontos de chegada pode ser um método no qual é indicado para cada viagem, em que direção possível a rota virou na próxima bifurcação. De acordo com nossas suposições, todos os garfos da rede podem ter apenas duas ramificações; portanto, para indicar a direção em cada caso, é necessário exatamente 1 bit. Para quem tem um mapa da cidade e conhece o ponto de partida, a cadeia de bits será suficiente para rastrear cada rota e restaurar a sequência original de seus destinos. Se o número médio de garfos (nós de divisão) visitados durante uma viagem for x , o comprimento da mensagem binária com o novo método de codificação será: (número de registros) × x .

Como foi dito anteriormente, o novo método de codificação não pode ser mais eficiente que o método de transferência direta de endereço binário, portanto: (número de registros) × x ≥ (número de registros) × log ₂ n , é por isso:

x ≥ log ₂ n .

Embora a última desigualdade tenha sido deduzida inicialmente para um grupo de viagens que possuía um ponto de partida fixo comum, ela acabou sendo independente da escolha específica desse ponto. É por isso que podemos estender o resultado a todas as viagens na cidade de uma só vez, obtendo assim a primeira parte da estimativa em questão:

P1 ) Desde que cada nova viagem tenha igual probabilidade de terminar em qualquer um dos n pontos de endereço da cidade, o número médio de nós de divisão por rota não pode ser menor que log ₂ n .

Voltando mentalmente o relógio, podemos converter cada ponto final da viagem no ponto inicial e cada nó binário da divisão da rede - o nó binário da fusão. Este pequeno truque nos permite obter automaticamente de P1 a segunda parte ausente da estimativa:

P2 ) Desde que cada viagem concluída tenha chances iguais de começar em qualquer um dos n pontos de endereço da cidade, o número médio de nós mesclados por rota não pode ser menor que o log ₂ n .

Se recordarmos a existência de uma rede logarítmica com mesclagem preliminar e de uma rede logarítmica com divisão preliminar, obteremos imediatamente dois exemplos de redes que são ótimas em termos do número de nós de comutação, que, em média, é visitado dentro delas durante uma viagem Vamos ver se essa qualidade ajuda a reduzir a intensidade das perdas de comutação geradas.

Custos de comutação em redes logarítmicas

Se compararmos as redes com a fusão preliminar e a divisão preliminar, a primeira parecerá muito mais atraente devido à sua simplicidade. Infelizmente, essa simplicidade também tem um lado oposto da moeda: combinar todas as rotas em um fluxo contradiz a recomendação i1 , causando potencialmente grandes perdas de tempo. A rede com divisão preliminar parece atender aos requisitos i1 - i3 , no entanto, a julgar pelo Gráfico 13b, tende a aumentar rapidamente o número de membros de estradas e nós de comutação usados. A última qualidade pode tornar as redes desse tipo muito caras para uso prático.

Analisaremos essas perguntas com mais detalhes. Para começar, concordamos que a cidade segue o modelo de migração com 'acesso aleatório' e que o fluxo gerado por qualquer um de seus pontos de endereço tem uma potência 1.

Perdas nas redes com fusão preliminar

No gráfico 14, você pode ver um diagrama de fluxos decorrentes das condições acima mencionadas na rede com uma fusão preliminar.


Quadro 14

Pareceu-me conveniente descrever a própria rede em sua forma unidirecional, implicando que cada ponto de partida e de chegada, assinado com os mesmos números no gráfico, na verdade significa o mesmo ponto de endereço na cidade.

Com base no diagrama, podemos calcular a intensidade dos custos de comutação gerados na rede. Vamos começar pela metade esquerda, onde, através da árvore de endereços reversa, todas as rotas são reunidas em um fluxo. Cada nó de comutação nesta parte da rede representa o local em que duas rodovias unidirecionais se fundem em uma (Gráfico 15).


Quadro 15

Se, inicialmente, cada uma das estradas for carregada com eficiência, depois da fusão, não haverá necessidade de reduzir o número de faixas, como resultado, não haverá custos de troca respectivos.

Vamos supor que um fluxo com a potência 1 já seja suficiente para carregar efetivamente a estrada ao longo de pelo menos duas faixas. Nesse caso, chegaremos a uma conclusão inesperada: a fusão dos fluxos de carros na rede logarítmica com a fusão preliminar ocorre absolutamente 'de graça', sem causar perdas de tempo.

O cálculo dos custos que surgem na metade direita não é muito mais difícil. Essa parte da rede é uma árvore de endereços direta, cada nó do qual é uma bifurcação simétrica que já estudamos. Quando o fluxo de entrada com potência p , a intensidade das perdas resultantes no garfo é ( α / 2 ν ) ⋅ p 2/2 . A potência do fluxo que entra no garfo raiz é: n , portanto, a intensidade das perdas no nó raiz é: ( α / 2 ν ) ⋅ n 2/2 . Em cada próxima geração da árvore de endereços, o número de garfos dobra e a potência do fluxo de entrada é reduzida pela metade. Como resultado, a fórmula das perdas dentro da árvore inteira assumirá a forma:

I _{t_div1} = ( α / 2 ν ) ⋅ (1/2) ⋅ [ n ² + 2 ( n / 2) ² + 4 ( n / 4) ² + ... + ( n / 2) ⋅ 2 ² ] =

( α / 2 ν ) ⋅ ( n / 2) ² [1 + 1/2 + 1/4 + ... + 2 / n ] ≈ ( α / 2 ν ) ⋅ n ²

Como o poder do fluxo de viagens gerado em conjunto por todos os pontos de endereço é n , os custos de tempo por viagem são em média ( α / 2 ν ) ⋅ n , mostrando assim uma dependência linear do tamanho da cidade.

Quando se trata de redes abstratas, é difícil fazer uma estimativa significativa da área das estradas que elas usam. Como uma medida alternativa da complexidade estrutural, a potência total de todos os fluxos laterais pode ser calculada. Conforme planejado, o valor resultante deve refletir a intensidade de recursos da construção de todas as trocas exigidas pela rede. Não posso dizer que, na prática, esse método sempre tenha uma boa interpretação, mas provavelmente será obtida uma idéia aproximada da quantidade de trabalho que temos pela frente.

Dentro da rede logarítmica com mesclagem preliminar, os fluxos laterais existem apenas na árvore de endereços direta, e sua potência total para cada geração de nós é a mesma: n / 2. No total, há log ₂ n de gerações de nós na árvore, portanto, um novo método para avaliar a complexidade fornece uma estimativa da complexidade: O ( n log ₂ n ).

Redes logarítmicas com fusão preliminar

O número de pontos de endereço com energia 1 .......................................... .......... n
Tempo médio de viagem
perdido devido aos custos de mudança:
assintóticos ................................................. .................................................. ... O ( n )
valor exato ................................................ .................................................. ..... ( α / 2 ν ) ⋅ n
Número de nós de comutação .............................................. ................................ O ( n )
Número de nós de comutação, dada a potência dos fluxos laterais ........................ O ( n log ₂ n )

Perdas nas redes com divisão preliminar

Passamos agora à análise da rede logarítmica com divisão preliminar, assumindo novamente que a rede é usada para conectar os pontos de endereço com a energia 1 na cidade com 'acesso aleatório'.
O Gráfico 16 mostra um fragmento dele consistindo em um ponto de endereço junto com as árvores de Endereço direta e reversa adjacentes a este ponto.


Quadro 16

Primeiro de tudo, podemos estimar a intensidade das perdas de comutação geradas pelo fragmento.
Os custos incorridos durante a divisão dos fluxos podem ser encontrados pela seguinte equação I _{t_div1} = ( α / _2ν ) ⋅ n ² , que foi deduzida para a árvore de endereços direta no exemplo anterior, 1 em vez de n . De fato, as árvores de endereços diretas nos Gráficos 16 e 14 têm a mesma profundidade e envolvem os fluxos similares em poder (nota: similaridade significa a capacidade de obter um conjunto de valores multiplicando os valores de outro conjunto por um número fixo , para ilustrar, a semelhança entre triângulos pelos lados). Devido à relação quadrática entre o valor dos custos de comutação que ocorrem em uma única bifurcação e a potência de seu fluxo de entrada, uma diminuição simultânea de todos os fluxos em n vezes reduzirá as perdas na árvore inteira em n ² vezes, portanto, em vez disso dos antigos ( α / 2 ν ) ⋅ n ² , obtemos um valor igual a:

I _{t_div2} = ( α / 2 ν ).

Agora podemos calcular o valor dos custos na metade esquerda do fragmento.
Devido ao pouco valor dos fluxos combinados da estrada dentro da árvore de endereços reversa, desta vez não seria razoável construir uma estrada com mais de duas faixas. A fusão nessas condições não é mais gratuita: em contraste com o exemplo anterior, há áreas estreitando-se na rodovia (Gráfico 17), onde necessariamente haverá custos de troca.


fig. 17

Supondo que o motorista conheça antecipadamente o estreitamento, podemos assumir que o processo de mudança da pista sem saída é lento, sendo esticado centenas de metros ao longo da rodovia. Nesse caso, temos o direito de recorrer ao truque que usamos anteriormente para calcular as perdas na bifurcação simétrica - para dividir o fluxo total de migração q em muitas pequenas partes q _ie interpretar cada uma delas como um fluxo lateral de a rampa. As perdas geradas por cada sub-fluxo são calculadas pela fórmula:

Se _i = ( α / 2 ν ) ⋅ p q _i ⋅ (1 + 1 / s ), no entanto, existem duas sutilezas aqui.

O primeiro é que os carros não migrarão além da próxima linha.
De fato: os fluxos nas duas faixas centrais, devido à simetria óbvia, devem sempre ter aproximadamente a mesma densidade, para que os motoristas não tenham muitos motivos para cruzar a linha do meio. A partir da observação realizada, pode-se inferir que na fórmula para perdas causadas por fluxo lateral parcial, s é igual a 1.

À medida que os carros saem das faixas laterais, alternando para duas faixas centrais, a potência de fluxo dentro das faixas centrais aumenta gradualmente, mudando em cada caso de P / 2 para P. Assim, a segunda sutileza é a dependência significativa de p do número de substream i , o que nos faz escrever:

não
I _i = ( α / 2 ν ) ⋅ p q _i ⋅ (1 + 1 / s ),
mas:
I _i = ( α / 2 ν ) p ( i ) ⋅ q _i ⋅ (1 + 1 / s ).

No caso em que muitas partes pequenas, nas quais o fluxo de migração foi dividido, tinham tamanho igual, a dependência p ( i ) é expressa por um gráfico linear (Gráfico 18)


Quadro 18

Para calcular a taxa de intensidade de perda, precisamos recorrer à integração ou (isso torna possível uma forma particularmente simples de uma função integrável) assumir como p ( i ) o valor médio no gráfico igual a 3 P / 4. Como o fluxo total de migração do lado de cada pista de borda é P / 2, a intensidade das perdas em um nó de fusão separado será:

Eu _mesclar = 2 ⋅ ( α / 2 ν ) ⋅ (3 P / 4) ⋅ ( P / 2) =

= ( a / 2 v ) 3 P 2/4.

Para encontrar as perdas de tempo geradas dentro de um fragmento na árvore de endereços reversa, podemos aplicar a fórmula para _mesclar em cada um de seus nós:

I _{t_merge} = (3/4) ⋅ ( α / 2 ν ) [1 ⋅ (1/2) ² + 2 ⋅ (1/4) ² + 4 ⋅ (1/8) ² + ... + ( n / 2) 1 (1 / n ) ² ] ≈

≈ (3/4) ⋅ ( α / 2 ν ) [1/4 + 1/8 + 1/16 + ...] =

= (3/8) ⋅ ( α / 2 ν ) [1/2 + 1/4 + 1/8 + ...] =

= (3/8) ⋅ ( α / 2 ν ).

Os custos totais que surgem no fragmento devido à fusão e divisão de fluxos serão:

I _{t_merge} + I _{t_div2} = ( α / _2ν ) [1 + 3/8] = 11/8 ( α / 2ν ).

Uma rede logarítmica com divisão preliminar contém apenas n tais fragmentos, e exatamente n fluxos com potência 1 são gerados por seus pontos de endereço; portanto, o valor que acabamos de encontrar é exatamente igual às perdas de comutação por viagem média.

De fato, é mais importante para nós nem mesmo um número específico, que é igual aos custos específicos de troca, mas o fato de que esses custos permanecem constantes com o aumento de n . Este último torna a rede logarítmica com divisão preliminar assintoticamente a mais econômica em relação à perda de comutação entre todos os tipos de redes que estudamos anteriormente.

Infelizmente, a liderança não é livre. Apesar do valor extremamente pequeno do grande número de fluxos, cada árvore de endereços incluída na rede contém cerca de 2 n trechos de estrada de duas faixas e aproximadamente n nós de comutação em tamanho real. Existem 2 n árvores na rede, o que significaO ( n ² ) membros e nós, o que o torna não apenas o mais econômico em termos de eficiência de tempo, mas também a rede mais cara para construir, entre todos os exemplos considerados.

Quanto à soma dos fluxos laterais, seu valor, como pode ser facilmente calculado, cresce com a velocidade O ( n log2 n ) e, neste caso, não tem muito significado.

Redes logarítmicas com divisão preliminar

O número de pontos de endereço com energia 1 .......................................... ............ n
Tempo médio de viagem
perdido devido aos custos de mudança:
assintóticos ................................................. .................................................. ...... O (1)
valor exato ................................................ .................................................. ........ 11/8 ( α / 2 ν ).
Número de nós de comutação .............................................. ................................... O ( n ² )
Número de nós de comutação, dada a potência dos fluxos laterais ........................... O ( n log ₂ n )

Rede logarítmica equilibrada

Perdas de comutação excepcionalmente pequenas e, ao mesmo tempo, considerável consumo de recursos da construção da rede, decorrentes da aplicação de uma rede logarítmica com divisão preliminar, nos fazem querer encontrar uma maneira de mudar seu design para que o consumo de recursos seja significativamente reduzido, enquanto o os custos de troca não aumentariam substancialmente.

Obviamente, o principal culpado por um número excessivamente grande de estradas na rede é a eficiência extremamente baixa de seu uso. O último é claramente visto no Gráfico 19, que mostra um diagrama detalhado dos fluxos dentro de uma árvore de endereços direta adjacente ao i-ésimo ponto de endereço.


Quadro 19

No gráfico, o número acima do ramo da árvore denota a potência do fluxo que passa ao longo do ramo, e o intervalo abaixo é o conjunto de pontos de endereço entre os quais esse fluxo será eventualmente distribuído. Assumimos que todos os membros apresentados no gráfico são rodovias de duas pistas; o número de membros em cada geração da árvore é indicado na parte inferior da figura.

Após uma análise cuidadosa, você pode observar que a regra pela qual o fluxo é dividido em um nó específico é determinada exclusivamente pela posição desse nó na Árvore de Endereços e não depende do número do ponto de endereço que deu início a essas viagens. .

Se houver vários fluxos endereçados ao mesmo conjunto de pontos, e cada um deles não for poderoso o suficiente para preencher o caminho designado a ele, por que não combiná-los em uma única estrada? De fato, essa idéia essencialmente simples torna possível construir uma boa rede abstrata que gera perdas de comutação relativamente pequenas e é econômica em termos do número de estradas utilizadas.

Voltando à árvore Endereço do i-ésimo ponto, vemos que o fluxo que entra no nó raiz é dividido em dois fluxos filho com capacidade de 1/2 cada. O primeiro fluxo filho consiste em viagens endereçadas a pontos do intervalo [1; n / 2], o segundo consiste em viagens endereçadas a pontos do intervalo [( n / 2) + 1; n ]

Seguindo a idéia descrita acima, combinamos os fluxos filho do mesmo tipo em cada ponto ímpar e o ponto de endereço que o segue em ordem com um número par. Essa técnica permite que cada par de pontos selecionado tenha, em vez de quatro fluxos com uma potência de 1/2, apenas dois fluxos com a potência 1 (Gráfico 20). Nomearemos o fragmento obtido da futura rede como BN ₂ [i; eu +1].


Quadro 20

Se os fluxos filho não foram combinados, mas ainda estavam dentro da árvore de Endereços, na próxima geração de nós, cada um deles seria novamente dividido em duas partes, iguais à potência e ao tamanho dos conjuntos dos pontos de endereço para quais as viagens estão indo.

Por que quebrar a tradição estabelecida, porque após o processo de combinação ainda temos o mesmo conjunto de tipos de fluxo de antes, mas com apenas menos representantes de cada tipo. Para cada um dos fluxos de saída de BN ₂ [i; i +1], podemos aplicar exatamente a mesma regra de divisão que se aplicaria a um fluxo de seu tipo dentro da árvore de endereços.

Não há razão para não repetir indutivamente a construção lógica descrita acima para combinar-dividir os mesmos fluxos. O gráfico 21 mostra um esquema para combinar dois fragmentos
BN ₂ em um fragmento de BN ₄ , por outro lado, o Gráfico 22 mostra o mesmo algoritmo no caso geral.


Gráfico 21


Gráfico 22

No final, o processo de ampliação dos fragmentos será concluído e nos levará ao único elemento BN _n [1; n ] Vamos chamá-lo de rede logarítmica balanceada (Quadro 23).


Quadro 23

Vamos examinar esta rede quanto à complexidade e ao valor das perdas de comutação geradas.
Com base na natureza indutiva do projeto da rede Balanced, o número de nós de comutação incluídos em sua estrutura pode ser descrito pela equação recorrente:

nós (BN _k ) = 2 nós (BN _{k / 2} ) + 2 k ,

com a seguinte limitação:

nós (BN ₁ ) = 0.

A solução para este sistema de equações é a função:

nós (BN _n ) = 2 n log ₂ n .

Como o projeto de BN _n requer etapas de indução de log ₂ n , cada jornada passa por nós de divisão de log ₂ n e o mesmo número de nós de mesclagem, alternando entre eles no seu caminho (Gráfico 24).


Gráfico 24

Perdas geradas dentro de cada nó de divisão:
( α / 2 ν ) ⋅ (1) 2/2 .

Perdas geradas em cada nó de mesclagem:
( a / 2 ν ) ⋅ 3 ⋅ (1/2) 2/4 = 3/16 ( a / 2 ν ).

Considerando que o número de ambos na Rede Balanceada é n log ₂ n , podemos obter o valor exato das perdas totais de comutação:
11/16 ( α / 2ν ) n log ₂ n ,

qual por uma viagem é:
11/16 ( α / 2 ν ) log ₂ n

Rede logarítmica equilibrada

O número de pontos de endereço com energia 1 .......................................... .......... n
Tempo médio de viagem
perdido devido aos custos de mudança:
assintóticos ................................................. .................................................. ... O (log ₂ n )
valor exato ................................................ .................................................. .... 11/16 ( α / 2ν ) log ₂ n
Número de nós de comutação .............................................. ............................... O ( n log ₂ n )
Número de nós de comutação, dada a potência dos fluxos laterais ....................... O ( n log ₂ n )

Os números obtidos acima permitem considerar a Rede Balanceada como um bom compromisso entre a quantidade de perdas de tempo introduzidas e a complexidade estrutural geral. Seu uso como rede viária de uma cidade real é, em princípio, possível, mas dificilmente economicamente viável. Parece-me que a área em que o uso da Rede Balanceada pode realmente ser de grande benefício são os sistemas de informação em larga escala com requisitos estritos para a quantidade de atraso do sinal, como comunicações celulares, Internet, computação distribuída e computadores com multiprocessadores . Para nós, o maior valor da Rede Balanceada é o método pelo qual ela foi projetada. Um pouco mais tarde, usando uma modificação desse método, poderemos melhorar as redes de cidades lineares e celulares que são realmente cruciais em termos práticos.

Por que cidades históricas estão condenadas a engarrafamentos

Minha declaração pode parecer inesperada, mas a resposta à pergunta por que cidades em desenvolvimento natural, geralmente sofrem congestionamentos, já foi encontrada por nós nos parágrafos anteriores. Então, qual é a essência disso?

O fato é que muitas cidades históricas que sobreviveram após a era das fortalezas medievais (por exemplo, quase todas as capitais do “Velho Mundo”) herdaram dessa época a estrutura radial das ruas. Infelizmente (para os residentes modernos), uma rede de estradas com uma topologia semelhante não escala bem: o denso arranjo de estradas radiais perto do centro está se tornando muito raro na periferia. Como resultado, no processo de crescimento populacional, as ruas inicialmente localizadas à margem das poucas estradas que levavam à fortaleza se tornaram maiores e as ruas que apareceram na periferia eram curtas e não adquiriram significado de trânsito suficiente para crescer. largura. Como resultado, a rede de estradas que vemos agora nas grandes cidades históricas geralmente se refere a sistemas de transporte do tipo arterial e, em nossa terminologia,às redes logarítmicas com fusão preliminar (incompleta).


(Estradas de Moscou, foto: Slava Stepanov)

Se falarmos sobre o comprimento das estradas que um motorista deve percorrer, a implementação desse tipo de rede não é ruim: a distância percorrida geralmente difere pouco da distância da linha reta e sua O valor médio na cidade, como deveria ser para os sistemas de transporte “decentes”, cresce a uma taxa de O (√ n ). O problema é que, com a ampliação da cidade na rede logarítmica com uma fusão preliminar, os custos de troca gerados por ela aumentam muito rapidamente: o tempo durante o qual, em média, a viagem é prolongada por causa deles depende do número de pessoas que vivem na cidade como O ( n ). É claro que a partir de alguns n, esse tempo prevalecerá sobre o tempo líquido para superar a distância; em outras palavras, os engarrafamentos aparecerão na cidade.

Sem dúvida, a reorganização do sistema de transporte nas grandes cidades históricas é uma tarefa que pode ser resolvida. No entanto, é importante entender que a construção de outra, duas ou cinco grandes artérias de transporte, embora melhore ligeiramente a situação na cidade, mas não elimina a causa raiz dos engarrafamentos. Aparentemente, a única maneira de superar as desvantagens da rede logarítmica com a fusão preliminar é usar outra rede. Um bom candidato aqui pode ser uma rede com topologia celular, dentro da qual o tempo para cobrir a distância está crescendo, pelo menos na mesma proporção em que as perdas de comutação estão aumentando.


(noite Berlim, foto: Vincent Laforet)

Talvez seja por isso que Berlim moderna, embora com grandes rodovias arteriais, já se destaque por uma estrutura celular claramente visível.

Existem muitas soluções interessantes no mundo sobre como tornar os moradores das cidades históricas mais móveis, mas o principal prêmio na luta pela acessibilidade do transporte provavelmente deve ser dado aos engenheiros de Barcelona.


(Rede rodoviária atualizada de Barcelona, ​​foto: Vincent Laforet)

Um olhar mais atento às redes de cidades lineares e celulares

Depois que os métodos de análise foram encontrados e aperfeiçoados em redes abstratas, agora é hora de aplicá-los a casos mais realistas de cidades com topologia Linear e Celular. Nesta seção, tentaremos analisar com detalhes os recursos de suas redes de transporte, estabelecer o valor numérico da taxa de intensidade das perdas de chaveamento, descobrir como seu valor depende do tamanho dos trimestres e discutir possíveis variações e melhorias.

Cidade linear
Desta vez, consideraremos um exemplo de cidade em que existem duas rodovias de mão única: rodovia ocidental com tráfego na direção norte e leste com tráfego na direção sul (Gráfico 25).


Gráfico 25

Deixe que cada trimestre gere um fluxo com energia 1. Nesse caso, a potência de uma rota indo de um quarto para outro é de 1 / n .

Para começar, definiremos o poder dos fluxos laterais nas rodovias. A rodovia é única maneira ocidental ao chegar às quartas do i do trimestre ( n - i ) o sul localizado, e a única maneira do conseguir trimestre do i é o trimestre para os ( i - 1) para o norte localizados. Isso significa que o poder da troca de tráfego flui entre a rodovia ocidental e o trimestre i:

q _{W_out} = ( n - i ) / n- a potência do fluxo lateral que sai da estrada ocidental,
q _{W_in} = ( i - 1) / n - a potência do fluxo lateral de entrada.

É claro que o poder dos fluxos laterais na estrada oriental depende de i de maneira simétrica:
q _{E_out} = ( i - 1) / n - a potência do fluxo lateral que sai da estrada oriental,
q _{E_in} = ( n - i ) / n - a potência do fluxo lateral de entrada.

Obviamente, a soma dos fluxos que saem do i - _ésimo trimestre:
q _{E_in} + q _{W_in}= ( n - 1) / n ,

coincide com a soma dos fluxos que entram:
q _{E_out} + q _{E_out} = ( n - 1) / n ,

e esses dois valores não dependem de i (cada trimestre tem um fluxo com potência 1 / n , esse fluxo consiste em viagens que começam e terminam dentro do trimestre especificado).

Para calcular a potência dos fluxos principais, traçaremos uma linha imaginária através da estrada ocidental no mesmo nível do i- ésimo trimestre. No total, esta linha cruzará:
(o número de quartos para o sul) × (o número de quartos para o norte) = (n - i ) ( i - 1) de rotas que juntas criam um fluxo com a potência:

P _W ( i ) = ( n - i ) ( i - 1) / n .

A mesma fórmula:
(número de quartos para o sul) × (número de quartos para o norte) / n ,
deve expressar a potência do fluxo de tráfego na estrada leste P _E , ou seja,

P _E ( i ) = P _W ( i ) = P ( i ).

Conhecendo a potência de todos os fluxos principal e lateral, podemos calcular a taxa de intensidade de perdas que ocorre na rede na área próxima ao i- ésimo trimestre:

I ( i ) = ( α / 2 ν ) ⋅ P ( i ) ⋅ [( q _{E_in} + q _{W_in} ) ⋅ (1 + 1 / s ) + ( q _{E_out} + q _{E_out} ) ⋅ ( _1-1 / s )] =
= ( α / 2 ν ) ⋅ P ( i ) ⋅ [(1 - 1 / n ) ⋅ (1 + 1 / s ) + ( 1-1 / n ) ⋅ ( 1-1 / s )] =
= ( α / 2 ν ) ⋅ 2 P ( i ) ⋅ (1 - 1 / n ) =
= 2 ( α / 2 ν ) ⋅ ( 1-1 / n ) ⋅ ( n - i ) ( i - 1) / n =
= 2 ( α / 2 ν ) ⋅ (1 - 1 / n ) ⋅ ( n - i ) ⋅ ( i - 1) ⋅ (1 / n ).

Se resumirmos a última expressão em i , obteremos a taxa de intensidade de perdas gerada por toda a rede como um todo.

I = I _i I ( i )
= 2 _i 2 ( α / 2 ν ) ⋅ ( 1-1 / n ) ⋅ ( n- i ) ⋅ ( i - 1) ⋅ (1 / n ) =
= 2 ( α / 2 ν ) ⋅ (1-1 / n ) ⋅ n ² ⋅ Σ _i (1 - i / n ) ⋅ ( i / n - 1 / n ) ⋅ (1 / n ) ≈
≈ 2 ( α / 2 ν ) ⋅ n ² ⋅ Σ _i (i / n ) ⋅ (1 - i / n ) ⋅ (1 / n ).

O Σ soma _i ( i / n ) ⋅ (1 - i / n ) ⋅ (1 / n ) para qualquer grande n pode ser substituído com boa precisão pela integral:

∫ t (1 - t ) d t ( t ∈ [ 0; 1]) = 1/2 - 1/3 = 1/6.

Com base nisso, podemos obter que a intensidade das perdas de comutação em uma cidade Linear comn trimestres com potência 1 para quantidades:

I = ( α / 2 ν ) n ² /3.

Até o momento, consideramos apenas exemplos nos quais trimestres sempre geravam fluxos com energia 1. Vamos considerar se a fórmula para perdas de comutação de uma cidade linear mudará se, a cada trimestre, não houver uma fonte de fluxo com energia 1, mas - λ (os quartos se tornarão λ vezes maiores).

Vamos tomar uma cidade com m trimestres. Se trimestres fluxos gerados com um poder, em seguida, as perdas de comutação seria ( α / 2 ν ) m ² /3.

Um aumento na potência de produção de viagem a cada trimestre por um fator de λ leva a um aumento nos fluxos principal e lateral por um fator de λ . Como resultado, os custos em cada junção, e, portanto, dentro da rede como um todo, aumento por um factor de X ² vezes, e as transformações perdas fórmula em:

I = ( α / 2 ν ) m ² ⋅ X ² /3 .

Em grande parte, não importa como as perdas de comutação dependem do número de quartos na cidade, o principal para nós é como elas dependem do poder de fluxo de todas as viagens geradas dentro dela, ou seja, no número nfontes com energia de 1. Neste caso, n é igual a m ⋅ X , por conseguinte,:

I = ( α / 2 ν ) m ² ⋅ X ² /3 =
= ( α / 2 ν ) ( m ⋅ X ) ² / 3 =
= ( α / 2 ν ) n ² /3.

Em outras palavras, mudar perdas em uma cidade linear não depende de quão pequena é a fragmentação de seu território em quadrantes.

Cidade celular

Imagine uma cidade celular na qual as rodovias de ruas perpendiculares sejam alocadas em diferentes alturas / níveis. Isso seria possível, por exemplo, se todas as rodovias que seguissem de norte a sul fossem erguidas em pontes e as rodovias que se estendessem de oeste a leste fossem construídas na superfície da Terra. Se, além disso, todas as rodovias tiverem tráfego de mão dupla, a rede de estradas dessa cidade será referenciada à topologia celular padrão (Gráfico 26).

O ponto aqui, é claro, não é colocar em prática a rede descrita acima: ela não pareceria muito esteticamente agradável no contexto da paisagem da cidade e, além disso, devido à necessidade de intercâmbios em vários níveis, ela comeria a melhor metade do espaço da rua. No entanto, essa rede puramente hipotética é uma boa maneira de obter as estimativas necessárias, que mais tarde podem ser facilmente estendidas a redes de estradas realmente interessantes do ponto de vista de sua aplicabilidade em cidades reais.

Como sempre, presumiremos que as necessidades de migração dos residentes sejam descritas pelo modelo de 'acesso aleatório' e iniciaremos nossa consideração com o caso em que a potência de todos os fluxos gerados por um determinado trimestre seja 1.

No exemplo da cidade celular padrão, é conveniente se afastar da tradição estabelecida e considerar como o ponto de endereço não um bairro separado, mas uma zona territorial de forma quadrada na interseção de rodovias e 1/4 dos quartos. adjacente a ele. O gráfico 27 ​​mostra o posicionamento relativo de várias dessas zonas e mostra um padrão de tráfego dentro de uma delas. Este gráfico demonstra claramente que qualquer motorista, saindo do trimestre, tem a oportunidade de entrar na estrada, seguindo na direção de qualquer um dos quatro lados do mundo.


Gráfico 26

Para calcular o valor dos custos de troca gerados pela cidade, calcularemos a potência de todos os fluxos principais e laterais dentro de cada uma de suas zonas territoriais. A forma e o posicionamento mútuo das zonas nos permitem recorrer a uma analogia do xadrez para resolver o problema em questão, considerando as zonas como células de campo e o movimento de carros entre elas - como movimentos da torre (Quadro 27). Em um caso geral, a torre pode ser movida de uma célula para outra em dois movimentos; se ambas as células estiverem na mesma linha horizontal ou vertical, então - de uma só vez.


Gráfico 27

Para evitar muitas reservas inconvenientes, assumimos que o movimento em que a torre não se move para lugar algum também é permitido de acordo com nossas regras. A rota de movimento da torre, composta por dois movimentos, um dos quais é necessariamente realizado verticalmente e o outro - horizontalmente, será chamado de mais simples. É razoável considerar o movimento 'parado' como vertical e horizontal ao mesmo tempo. Nesse caso, é verdade que quaisquer duas células no painel são conectadas umas às outras por exatamente duas rotas mais simples.

Para os motoristas, a rota mais simples é a maneira mais fácil de obter, com o mínimo de interferência, de uma zona territorial para outra; portanto, é razoável supor que viagens reais ocorrerão ao longo de linhas de rota elementares. De acordo com o modelo de 'acesso aleatório', o fluxo com a potência 1 gerada pelo ponto de endereço (zona territorial) deve ser igualmente distribuído entre todos os n = d ² pontos de endereço da cidade. Portanto, a potência do fluxo que passa ao longo de uma linha de rota é 1 / (2 n ).

Podemos calcular o fluxo com o que a energia passa através da célula ( i , j ) na direção do sul para o norte. A rota mais simples cruza a célula ( i , j) do sul para o norte em apenas duas situações. O primeiro deles (Gráfico 28 à esquerda):

1a) a célula inicial da rota está localizada em uma das últimas ( d - i ) linhas horizontais (linhas);
2a) o ponto final da rota é uma das primeiras ( i - 1) células da j- ésima linha vertical (coluna);
3a) a rota começa com uma seção horizontal ou fica inteiramente dentro da j- ésima coluna.


Gráfico 28

As condições que descrevem a segunda situação parecem simétricas (Gráfico 28 à direita):

1a) o ponto inicial da rota é uma das últimas ( d - i ) células da j- ésima linha vertical;
2a) a célula de chegada da rota está localizada em uma das primeiras ( i - 1) linhas horizontais;
3a) a rota começa com uma seção vertical ou fica inteiramente dentro da j- ésima coluna.

No tabuleiro de xadrez existem apenas 2 × [ d ⋅ ( i - 1) + 1⋅ ( i - 1)] × ( d - i) rotas mais simples adequadas para os requisitos, que juntos criam um fluxo com a potência:

P _SN ( i , j ) = ( d + 1) ⋅ ( i - 1) ⋅ ( d - i ) / n (= P _SN ( i )).

Fixando j , obteremos a função

( P _SN ) _j ( i ) = P _SN ( i , j = Const),

descrevendo a dependência da potência do fluxo que se move para o norte ao longo da j- ésima rodovia vertical na distância até o limite superior da cidade, medido em células.
Existem várias observações mais ou menos óbvias sobre as funções ( P _SN ) _j ( i ), vamos discuti-las.

Vamos começar com uma circunstância que seria difícil ignorar: P _SN ( i , j ) praticamente independente do segundo argumento. Como resultado, as funções ( P _SN ) _j ( i ) = P _SN (i ) possuam a mesma forma para todos os valores de j , ou seja, a posição específica da rodovia dentro da cidade Celular não afeta sua carga. Formalmente, a última afirmação é comprovada apenas para a rodovia em direção ao norte, mas devido às simetrias da cidade, ela se aplica automaticamente à rodovia de outras direções também.

Agora, vejamos a fórmula para o próprio P _SN ( i ):

( d + 1) ⋅ ( i - 1) ⋅ ( d - i ) / (2 n ).

Como vemos, toda a dependência de P _SN dei on i está na expressão ( i - 1) ⋅ ( d - i ). Essa expressão pode ser interpretada como o produto dos comprimentos dos trechos direito e esquerdo nos quais a seção inteira de comprimento d se divide depois que o i-ésimo elemento é excluído (Gráfico 29a).


Gráfico 29a


Gráfico 29b

É claro que, se você alterar “direita” para “esquerda” e “esquerda” para “direita” (Gráfico 29b), o resultado do produto permanecerá o mesmo. Com base em uma observação tão simples, podemos extrair duas inferências que são, em essência, muito úteis para nós:

1. the function P _SN ( i ) is symmetric with respect to the midpoint of the street i = (d + 1)/2, in order words, the flow power at a distance Δ from the lower boundary of the city is exactly the same as at a distance from the lower boundary of the city is exactly the same as at a distance Δ from the upper boundary.
2. On the whole, the city itself is symmetrical up and down, therefore, to get the function ( P _NS ) _j ( i ), which describes the power flow on the j -th highway, but in a southward direction, it's enough to simply mirror the function graph ( P _SN ) _j ( i ) in the line i = ( d + 1)/2. Since ( P _SN ) _j ( i ) = P _SN ( i ), and the graph P _SN ( i ) with respect to the line i = ( d + 1)/2 is symmetric, then ( P _NS ) _j ( i ) = P _SN ( i ) = P _vert ( i ),, in other words,
3. direct and oncoming traffic flows have equal power at any point of the city. A closer graph of P _SN ( i )is shown in Chart 30 (it is believed that d >> 1, i >> 1, d − i >> 1).

Gráfico 30

As potências dos principais fluxos ao longo das rodovias horizontais são facilmente encontradas usando simetrias rotacionais; formalmente, esse processo pode ser implementado através de uma simples substituição de i por j em P _SN ( i ) e uma pequena correção do índice mais baixo.

O próximo passo a tomar é encontrar a potência dos fluxos laterais. As viagens que entram ou deixam o tráfego em uma estrada vertical dentro da célula ( i , j ) podem ser convenientemente divididas em quatro categorias:

1. the flow q _{in_transit} : start point is in any cell of the i -th horizontal, finish point is in any cell of the j -th vertical, except for the ( i , j ) itself (Chart 31a);
2. the flow q _{out_transit} : start point is in any cell of the the j -th vertical, except for the ( i , j ) itself, finish point is in any cell of the i -th horizontal (Chart 31b);
3. the flow q _in : start point is the ( i , j ) itself, finish one is any cell outside the i -th horizontal (Chart 31c);
4. the flow q _out : start point is in any cell outside the i -th horizontal, finish point is the ( i , j ) itself (Chart 31d);

Quadro 32: abcd

Tendo contou o número de linhas de rota que pertencem a cada categoria separada, pode-se concluir que as potências de todas as quatro fluxos são os mesmos e iguais:

q ₀ = d ⋅ ( d - 1) / (2 N )

Tendo o valores das potências dos fluxos principal e lateral em uma rodovia vertical, não é difícil calcular o valor dos respectivos custos de troca. Dentro de uma única célula ( i , j ), os custos de comutação serão iguais a:

I _vert ( i , j ) = ( α / 2 ν ) ⋅ P_vert ( i ) ⋅ [( q _in + q _{in_transit} ) ⋅ (1 + 1 / s ) + ( q _out + q _{out_transit} ) ⋅ ( _1-1 / s )]
= 4 ( α / 2 ν ) ⋅ ( d + 1) ( i - 1) ( d - i ) ⋅ d ( d - 1) / 2 n ² ≈
≈ 2 ( α / 2ν ) ⋅ d ⁵ ⋅ ( i / d ) (1 - i / d ) ⋅ (1 / d ) ⁴ =
= 2 ( α / 2 ν ) ⋅ d ² ⋅ ( i / d ) (1 - i / d ) ⋅ (1 / d ).

Para encontrar os custos incorridos em todas as ruas verticais de toda a cidade, precisamos somar I _vert ( i , j) Para ambos os índices:

Eu _vert = Σ _ij I _vert ( i , j ) =
= 2 ( α / 2 ν ) ⋅ d ² ⋅ Σ _ij ( i / d ) (1 - i / d ) ⋅ (1 / d ) .

Como o valor dos summands não depende de j de maneira alguma, a soma do segundo índice é equivalente à multiplicação por d :

∑ _ij ( i /d ) (1 - i / d ) ⋅ (1 / d ) = d ⋅ Σ _i ( i / d ) (1 - i / d ) ⋅ (1 / d ).

Última montante pode o ser aproximada pela integral já sabemos que:

Σ _i ( i / d ) (1 - i / d ) ⋅ (1 / d ) ≈ ∫ t (1 - t ) d t (t [0; 1]) = 1/2 - 1/3 = 1/6.

Nesta baseada, pode-se obter:

I _vert = ( α / 2 v ) ⋅ d ³ /3 = ( α / 2 v ) ⋅ n √ n / 3.

A resposta é que podemos questionar o que é o valor dos custos de I _Horiz , que surgem nas rodovias horizontais, usando a simetria da cidade:

I _horiz = I _vert = ( α 2 / ν ) ⋅ n √ n / 3.

Portanto, a taxa de perdas de comutação de intensidade dentro de toda a rede de cidade celular padrão é igual a:

I = I _vert + Eu _horiz = 2/3 ⋅ ( α / 2 ν ) ⋅ n √ n ,

e por viagem, em média, os custos de troca serão

2/3 ⋅ ( α / 2 ν ) ⋅ √ n

O efeito do tamanho da célula no valor das perdas de troca

Quartos que geram fluxos com energia 1 são uma limitação bastante artificial das condições do problema. Podemos estender os resultados obtidos acima aos casos em que a potência do fluxo gerado por uma célula é igual a λ .
Deixe a cidade consistir em m tais células. Se todas as células tivessem potência 1, a intensidade das perdas totais de comutação seria I ₁ = 2/3 ⋅ ( α / 2 ν ) ⋅ m √ m . Um aumento no número de viagens por um fator de λ multiplicará por λvezes a potência de todos os fluxos principal e lateral nas rodovias, o que, por sua vez, causará um aumento de λ ² em todos os custos de troca gerados na cidade. A nova fórmula para a taxa de intensidade de perdas assumirá a seguinte forma:

I = 2/3 ⋅ ( α / 2 ν ) λ ² ⋅ m √ m

Se assumirmos que a célula consiste em λ pontos de endereço com potência 1, então o total o número de tais pontos será: n = λm . Vamos expressar I em função de n e λ :

I = 2/3⋅ ( α / 2 ν ) λ ² ⋅ m √ m =
2/3 ⋅ ( α / 2 ν ) ⋅ √ λ ⋅ ( λ √ λ ) ⋅ ( m √ m )
= 2/3 ⋅ √ λ ( α / 2 ν ) ⋅ ( λ m ) √ ( λ m ) =
= 2/3 ⋅ √ λ( α / 2 ν ) ⋅ n √ n .

O custo médio por viagem sob as novas condições será 2/3 ⋅ √ X ( α / 2 ν ) ⋅ √ n , sendo √ X maior do que o seu valor numa cidade feita de trimestres 1 com energia.

A última fórmula nos diz que, para a mesma população, densidade populacional e área total de todas as estradas, quanto maior o tamanho dos quartos escolhidos por seu arquiteto, maiores os custos de troca. No caso em que a população da cidade está desigualmente distribuída em seu território, é claro que precisamos prestar atenção não às dimensões geométricas, mas antes de tudo ao número médio de pessoas no trimestre e à sua atividade migratória.


(Foto do centro de Nova York: Vincent Laforet)

A observação feita acima é especialmente importante ao projetar áreas com edifícios arranha-céus. Devido à combinação de alta densidade populacional e sua alta mobilidade, é crucial projetar quartos em áreas de arranha-céus várias vezes menores em tamanho do que o habitual para edifícios comuns. Nas civilizações, onde a construção de arranha-céus tem uma longa história, a prática de isolar até grandes edifícios separados em um quarto é generalizada.

Uma cidade celular com regulamentos de semáforo
Em cada caso, quando as linhas de duas rodovias movimentadas se cruzam no mapa, o arquiteto deve fazer uma escolha: levante uma dessas estradas até a ponte, permitindo que o fluxo da outra passe livremente abaixo ou realize a interseção na forma de interseção e resolva o conflito de fluxo pela regulamentação dos semáforos. A segunda opção é frequentemente escolhida nas cidades, pois é atraente de maneira simples, não implica a necessidade de construir estruturas de engenharia em larga escala e, além disso, fornece aos pedestres uma maneira fácil de atravessar a rua.


(bairros comerciais de Los Angeles à tarde, foto: Boris Shein)

O uso de semáforos em redes com topologia celular possui características próprias. No capítulo 1, foi mostrado que, com a sincronização adequada dos semáforos, os carros, enquanto se deslocam pela mesma rua, nem precisam parar nos cruzamentos: um sinal verde sempre acenderá em sua direção. Esse tipo de fenômeno é geralmente chamado de gerenciamento de tráfego de ondas verdes. Para criá-lo, os fluxos de tráfego precisam ser divididos em dois alternados: cheios de carros e livres deles. A seguir, é selecionado um modo de operação dos semáforos que, no período em que a próxima “parte” passa pelo cruzamento por uma das ruas, a parte anterior dos carros que se deslocam pela rua perpendicular já passou por ela e a próxima um ainda não chegou (Quadro 33).


Gráfico 33

A gestão do tráfego de ondas verdes carrega seus próprios custos e impõe certas restrições ao layout das ruas da cidade.

Olhando novamente para o Gráfico 33, é fácil ver que, a qualquer momento, exatamente metade da área de todas as estradas não é realmente usada. Para compensar esse tempo de inatividade, na metade usada ativamente, a energia local dos carros circula e o número de faixas necessárias para eles deve ser duas vezes maior do que em uma cidade com viadutos.

A segunda circunstância mais importante associada ao uso de ondas verdes é a regulamentação estrita do tamanho permitido dos quartos: seu comprimento (para ruas de mão dupla) deve ser múltiplo do comprimento da onda verde cheia (uma seção do fluxo dentro do qual é possível um movimento sem obstáculos), totalizando cerca de 500 metros. Conforme observado no parágrafo anterior, as áreas com alta densidade populacional exigem um aumento da frequência da localização das estradas, de modo que a restrição na distância entre as rodovias (o tamanho permitido dos quartos) pode potencialmente causar dificuldades no trânsito.

É interessante notar que, no gerenciamento de tráfego de ondas verdes, as regras de comutação dentro da rede mudam ligeiramente. Por exemplo, a adição de mais um carro ao fluxo de tráfego principal pode ser realizada nos intervalos entre as zonas preenchidas, sem causar assim sérios custos de comutação (ponto 1 no Gráfico 34a).


Gráfico 34

É claro que este carro em si terá que perder algum tempo aguardando a zona vazia mais próxima antes de entrar na estrada e, depois disso, permanecer no semáforo até que a próxima zona cheia atinja (ponto 2, Gráfico 34a). o valor dessas perdas não depende do tamanho da cidade ou da ocupação do tráfego na rua; portanto, elas podem ser negligenciadas em larga escala.

A situação é completamente diferente se um carro tenta sair do tráfego da rodovia (Gráfico 34b). Aqui, aparentemente, não há mais maneiras complicadas de reduzir as perdas de comutação criadas pelo motorista. Além disso, devido à duplicação da potência local do fluxo dentro das zonas cheias, a saída de um carro selecionado aleatoriamente causa custos de tempo duas vezes mais do que em uma cidade com viadutos. No total, a “entrada” mais barata e a “saída” mais cara compensam uma à outra, fazendo com que a cidade de semáforos a esse respeito quase não seja melhor, mas pior que a padrão.

Viaduto Cidade celular com tráfego só de ida

Além do uso de semáforos, há pelo menos mais uma oportunidade para evitar os monstruosos intercâmbios da cidade Standard. Implica dividir espacialmente as vias de mão dupla (Gráfico 35).


Gráfico 35

Como resultado dessas mudanças, o número de ruas dobrará, todas se tornarão ruas de mão única, mas o mais importante é que as trocas serão bastante simplificadas (Gráfico 36).


Gráfico 36

Como o número de rodovias em direção a cada um dos lados do mundo e o número de viagens ao longo delas permanecem os mesmos, todos os poderes fluem juntamente com os custos de mudança na cidade de celular unidirecional e na cidade padrão com 2 vezes maiores (linearmente) trimestres, devem coincidir. Se compararmos as cidades Standard e One-way com os mesmos tamanhos de trimestre, as perdas de troca no segundo serão duas vezes maiores.

Redes rodoviárias avançadas

Rua “linear”

Como reduzir as perdas de comutação em uma rede celular? A resposta para essa pergunta pode ser encontrada selecionando uma analogia correta, com a ajuda de um pouco de conhecimento.

Vamos considerar uma modificação um tanto incomum da rede celular, o que implica que todas as estradas que se estendem de oeste a leste são de mão dupla, enquanto as perpendiculares a elas são apenas de mão única: norte ou sul, e essas direções se alternam da rua para a rua.

Como sempre, assumiremos que a cidade segue o modelo de acesso aleatório, e cada quarto gera um fluxo com energia 1.

Nesse caso, parece bastante plausível que o fluxo tenha se originado dentro do trimestre ( i , j) é distribuído entre as ruas mais próximas da seguinte maneira: 1/4 dela vai para a estrada horizontal para o norte, 1/4 - para a estrada horizontal para o sul, 1 / 4⋅ i / d - para a estrada vertical para o norte e 1 / 4 ⋅ (1 - i / d ) - para a segunda estrada vertical para o sul (Gráfico 37).

Gráfico 37

De fato, de acordo com os algoritmos de rota discutidos anteriormente, de acordo com as estatísticas, metade das viagens começa em uma seção horizontal e, para os motoristas que preferem essa metade, deve, em grande parte, não importar se o caminho está no norte ou no norte. para o sul do trimestre ( i , j ). A metade restante das viagens começará a partir de uma seção vertical de tráfego e será dividida entre as rodovias em direção ao sul e norte como uma proporção do número de quartos situados ao sul do trimestre ( i , j ) e o número de quartos situados para o norte a partir dele.

Quanto ao fluxo de viagens em direção ao trimestre ( i , j), a regra de sua divisão em relação às rodovias que circundam o bairro será simétrica (gráfico 38).


Gráfico 38

Entre os quatro cruzamentos adjacentes ao trimestre ( i , j ), podemos considerar separadamente os fluxos laterais no cruzamento da rodovia horizontal mais baixa e da rua vertical com tráfego para o norte (Gráfico 38). O fluxo de carros entrando no cruzamento e indo da rua horizontal para a vertical é:
1 / 2⋅ (número de quartos na horizontal) × (número de quartos na vertical não inferior a ( i , j )) ⋅ 1 / d ² =
= 1/2 ⋅ d ⋅ i / d ² =
= 1/2 ⋅ i/ d .

A potência do fluxo lateral na direção oposta é:
1 / 2⋅ (o número de quartos na vertical é estritamente menor que ( i , j )) × (o número de quartos na vertical) ⋅ 1 / d ² =
= 1/2 ⋅ ( d - i ) ⋅ d / d ² =
= 1/2 ⋅ (1 - i / d ).

Vamos agora voltar a atenção da cidade celular como um todo para qualquer uma de suas ruas verticais, vamos chamar de My_street. Em virtude das simetrias, não limitaremos nosso raciocínio de nenhuma maneira, se assumirmos que o movimento ao longo de My_street é direcionado de sul para norte (Gráfico 39).


Gráfico 39 O

Gráfico 40 mostra a potência dos fluxos principal e lateral na rodovia ao longo de My_street, que, como o leitor pode perceber, são incrivelmente semelhantes a gráficos semelhantes para a rodovia de mão única de uma cidade linear (Gráfico 26).



Gráfico 40

Nestes exemplos, os diagramas de fluxo coincidem completamente se dentro de My_street os fluxos laterais relativos a cada par de quartos opostos e a estrada horizontal abaixo deles são formalmente designados a uma célula territorial imaginária. Como pode ser visto nas tabelas anteriores, a rede rodoviária de uma cidade linear gera algumas das maiores perdas de comutação entre as redes que já estudamos. Desse ponto de vista, o padrão de tráfego dentro dos limites de uma única rua de uma cidade celular parece extremamente ineficiente e é um elemento que deve ser aprimorado em primeiro lugar.

Rede avançada de cidades lineares

Portanto, estamos enfrentando a tarefa de melhorar uma rede Linear para que ela não se torne uma "quadrada". A circunstância que representa a maior ineficiência na operação da Rede Linear é a fusão de todas as rotas em apenas dois fluxos de tráfego muito grandes. Nesta situação, um passo razoável seria dividir os fluxos ao longo de suas duas rodovias em Q partes iguais. Como os custos de tempo causados ​​por cada carro entrando ou saindo do tráfego são proporcionais à intensidade do tráfego, como resultado da divisão das linhas da rua em Q partes isoladas (Gráfico 41a), as perdas de comutação dentro de uma cidade linear deveriam ter diminuído o tempo Q .


Gráfico 41

Mesmo após a construção de dez estradas próximas, não podemos esperar que os próprios motoristas sejam igualmente distribuídos entre eles - infelizmente, não parece haver chance de sucesso. Uma decisão muito mais ponderada seria projetar a rede para que cada estrada não conduza a todos os quadrantes, mas apenas a um pequeno “segmento” da cidade, onde seria difícil chegar sem usar a estrada especificada (Gráfico 41b )

Você pode ver uma idéia semelhante no esquema de movimentação de elevadores dentro de edifícios de vários andares, onde cada elevador permite entrar e sair não em todos os andares, mas apenas dentro de uma certa faixa de altura. Aceitando esse conceito, vamos dar uma olhada na estrada r _k , que dá acesso ao segmento Δ_k = ( x _k , x _{k +1} ] para viagens que começaram (não estritamente) ao sul a partir de xk (acredita-se que a numeração dos quartos seja realizada de baixo para cima)

.De cada trimestre, esse número é menor (não estritamente ) do que x _k , um q _em , riacho com uma potência de delta _{do k} | / n (1 / n a cada trimestre dentro delta _{do k} ) Entra na estrada r _{o k} , ao mesmo | tempo, é um assumido que existe a nenhuma possibilidade de virada de r _kpara qualquer um dos trimestres mencionados, seja devido a regras de tráfego estabelecidas ou devido a um projeto especial da rede rodoviária.

Os carros acumulados sobre o segmento [1, x _k ] acabará por ser distribuído igualmente entre os quartos dentro Δ _k , por conseguinte, se não houvesse viagens cujos pontos de início e de acabamento estão dentro Δ _k , em seguida, o lado flui q _{para fora} na direcção de cada quarto desta seção teria a potência x _k / n (Gráfico 42).


Gráfico 42

De fato, a contribuição de viagens “internas” para a potência dos fluxos laterais existe, no entanto, o valor dessa contribuição nunca excede | Δ _k | / n , portanto, no caso em que x _k >> | Δ _k |, pode ser simplesmente negligenciado. A potência p _k da corrente principal ao longo de r _k com as simplificações feitas será representada por um gráfico de duas seções retas com um P _k máximo igual a x _k ⋅ | Δ _k | / n. O valor aproximado de perdas de comutação na estrada r _k pode ser encontrada pela fórmula:

I _k = ( α / 2 ν ) ⋅ Σ _x [ q _em ( x ) ⋅ P _k ( x ) ⋅ (1 + 1 / s ) ] + ( α / 2 ν ) ⋅ Σ _x [ q _fora ( x ) ⋅ P _k ( x ) ⋅(1 - 1 / s )] =

= ( α / 2 ν ) ⋅ (1 + 1 / s ) ∑ _x [| Δ _k | / n ⋅ p _k ( x )] + ( α / 2 ν ) ⋅ ( 1-1 / s ) ∑ _x [ x _k / n ⋅ p _k ( x )]

= ( α / 2 ν ) ⋅ (1 + 1 / s) ⋅ ( x _k ⋅ | Δ _k | / n ) ⋅ ( ∑ _x p _k ( x )) / x _k + ( α / 2 ν ) ⋅ (1 - 1 / s ) ⋅ ( x _k ⋅ | Δ _k | / n ) ⋅ ( Σ _x p _{a k} ( x )) / | Δ _k |,

onde a primeira soma é tomada sobre um segmento x ∈ [1, x _k ] e a segunda sobre x ∈ Δ _k . As manifestações de A:

( Σ _x p _{a k} ( x )) / x _k , x ∈ [1, x _k ] e

( Σ _x p _{a k} ( x )) / | Δ _k |, x ∈ Δ _k

não são outra coisa senão a potência média do fluxo ao longo de r _kdentro dos intervalos indicados. Como o gráfico de potência dentro desses intervalos tem a forma de uma linha reta, a potência média em ambos os casos é P _k / 2. Substituindo

x _k ⋅ | Δ _k | / n por
P _k ,

finalmente apresentamos a fórmula para a taxa de intensidade de perdas em sua forma mais simples:

I _k = 2 ( α / 2 ν ) ⋅ P _k ⋅ P _k / 2 = ( α / 2 ν ) ⋅ P _k ²

Vamos agora tentar calcular a sequência x _k dos números daqueles trimestres pelos quais uma cidade linear deve ser dividida em segmentos. Como critério para a seleção de segmentos, podemos assumir o requisito de que a potência máxima do fluxo de tráfego P _k nas estradas que os aproximam tenha o mesmo valor, independente de k , ou seja:

x _k ⋅ | Delta _{do k} | = Const.

Lembrando que | Delta _{do k} | = x _{k + 1} - x _k , podemos inferir a equação da diferença:

x _{k + 1} - x_k = Const / x _k .

Supondo que x e k são variáveis ​​contínuas, e substituindo

x _{k + 1} - x _k = x ( k + 1) - x ( k )

por d x / d k ⋅ 1,

podemos aproximar a equação da diferença pelo diferencial:

d x / d k = Const / x <=> x d x = Const ⋅ d k .

a partir da qual podemos inferir uma solução para x _k na forma geral:

x _k = C ₁ √ ( k + C ₂ ).

Resta-nos para determinar o valor das constantes C ₁ e C ₂ com base em suas condições de contorno, no entanto, há uma sutileza importante nesta matéria. Diferentemente da situação em outros segmentos, todos os carros que chegavam da rodovia oeste aos bairros do segmento com o número 1 iniciavam suas viagens dentro do mesmo segmento. Como resultado, o gráfico da potência de fluxo na primeira rodovia ao norte terá a forma de uma parábola invertida regular.

Ao mesmo tempo, as condições a priori das quais a fórmula para x _k foi obtida assumiram essencialmente que os gráficos de potência de fluxo em todas as rodovias deveriam estar próximos de uma vista triangular, e as próprias viagens deveriam começar principalmente fora do segmento para onde são direcionadas. para. Esses requisitos podem ser cumpridos com razoável precisão se dividirmos formalmente o primeiro segmento em duas partes iguais, sem aumentar o número de estradas. A maioria das viagens que ocorrem ao longo da primeira rodovia começa na metade sul e termina na metade norte. Considerando apenas eles, não cometemos um grande erro no cálculo das perdas de chaveamento, mas agora o diagrama de potência do fluxo principal terá apenas uma forma triangular (Gráfico 43).


Gráfico 43

É o meio do primeiro segmento que deve ser considerado o ponto x ₁ na fórmula para x _k . Isso nos permite obter a primeira condição de contorno:

x ₂ = 2 x ₁ ou

√ (2 + C ₂ ) = 2 ⋅ √ (1 + C ₂ ) =>

C ₂ = - 2/3.

A segunda condição de contorno pode ser obtida com a exigência de que as estradas e os segmentos de tudo sejam exatamente Q , o que significa que x _{Q + 1} deve ser posterior ao trimestre com o maior número na cidade:

C₁ √ ( Q + 1 - 2/3) = n + 1, onde

C ₁ ≈ ( n + 1) / √ Q .

Portanto,

x _k ≈ ( n + 1) ⋅ √ ( k - 2/3) / √ Q ,

| Delta _{do k} | ≈ d x / d k = ( n + 1) / 2√ ( k - 2/3) ⋅ √ Q

P _k = x _k ⋅ | Δ _k | / n =

= ( n + 1) ² /2 n ⋅ Q ≈ n / 2 Q

I _k = ( α / 2 ν ) ⋅ P _k ² =

= ( α / 2 ν )⋅ ( n / 2 Q ) ² .

Como todas as rodovias 2 Q geram perdas da mesma intensidade, o valor dos custos de comutação em toda a rede será:

I = 2 Q ⋅ ( α / 2 ν ) ⋅ ( n / 2 Q ) ² = ( α / 2 ν ) ⋅ n ² /2 Q .

Como você pode ver, o resultado desejado foi alcançado: depois de dividir as principais rodovias em Qpartes, as perdas diminuíram de fato por um fator de Q (exceto pelo aumento de 1/3 para 1/2 do coeficiente constante, em comparação com a fórmula da cidade linear usual). Bem, estamos no meio do caminho, resta apenas aplicar esse resultado para melhorar a cidade com a arquitetura Celular.

'Elevador de arranha-céu' em uma cidade celular

Por uma questão de simplicidade, consideraremos um exemplo de cidade em que todas as ruas são de mão única. Usando a analogia entre uma cidade linear e as ruas individuais de uma cidade celular, podemos dividir a estrada ao longo da última em Qpeças. Por padrão, acredita-se que, saindo do trimestre, o motorista possa escolher qualquer estrada que passe perto dele. Ao mesmo tempo, entre todas as rodovias ao longo de uma rua, há uma curva em direção a um bairro específico de exatamente uma delas. No processo de estabelecimento de regras, sua uniformidade e simplicidade são extremamente importantes. Vamos dar uma olhada no gráfico 44:


No gráfico 44,

todas as ruas têm a mesma visão e as mesmas regras de qual das estradas abre acesso a qual bairro. O gráfico 45 mostra um diagrama de curvas permitidas entre rodovias. Olhando para esta foto, é difícil não ficar confuso. O mesmo é dito frequentemente sobre o esquema subterrâneo em alguma cidade grande. No entanto, em ambos os casos, tudo se torna claro e simples se você souber a lógica da ideia. A regra lógica das curvas permitidas parece bastante simples: se você estiver dirigindo ao longo de uma estrada, você cruza estradas perpendiculares ao seu movimento e pode se transformar em um quarto localizado diretamente atrás delas, pode se transformar em qualquer uma dessas estradas.


Gráfico 45

A topologia 'Elevador de arranha-céu' é compatível com cruzamentos e passagens superiores de semáforos. É difícil, mas possível generalizá-lo em redes não necessariamente de estrutura celular ou linear. Este último é realmente importante para cidades históricas, onde é improvável que seja uma decisão correta demolir metade dos monumentos históricos para projetar muitas pequenas ruas retas, mas nas quais já existem ruas bastante grandes que podem acomodar vários dois - ou rodovias com três faixas.

Sobre os problemas de transporte e o trabalho de um matemático

É agradável concluir o trabalho laborioso de 6 meses. Obviamente, o trabalho que escrevi não resolve todos os problemas e dificuldades do projeto de estradas - esse problema requer um grande número de pessoas muito versáteis e com várias habilidades. No entanto, seus resultados oferecem uma oportunidade de ver erros importantes em cidades já construídas e fornecem métodos para evitar esses erros no futuro. Este artigo não foi concebido como um livro de referência, cobrindo todos os casos possíveis que um engenheiro pode enfrentar na prática - considerei que meu principal objetivo é fornecer um novo ponto de vista, desenvolver uma nova maneira de raciocinar e falar sobre o problema, fornecer o leitor com o mínimo necessário de exemplos de modelos simples que podem ser expandidos ainda mais pelo leitor.

Fica triste quando você percebe quanto tempo foi perdido pelos moradores da cidade em engarrafamentos, apenas porque na hora certa não havia matemático que pudesse passar a noite em um problema completamente solucionável. Quantos desses problemas ainda cercam nossa vida ou ocultam sua profissão? Existe uma pessoa sentada perto de você no trabalho cujas ferramentas são um lápis e uma folha de papel?

Espero que tudo mude para melhor.

Gostaria de expressar minha sincera gratidão a Janine Lacroix (pseudônimo) por seu trabalho na tradução deste texto do russo original para o inglês.
Obrigado pela atenção e boa sorte!
Sergei Kovalenko

2019
magnolia@bk.ru


(Foto: Vincent Laforet)