Get best of the week

Como criar um modelo de transporte multi-agente

Olá Habr!

Imagine que temos a tarefa de construir uma nova estrada. Você pode construir uma estrada com duas faixas em cada direção, mas e se isso não for suficiente? Ou, pelo contrário, acontece que uma faixa seria suficiente, mas para a implementação do projeto era necessário comprar muitos terrenos? Nos dois casos, a decisão será ineficaz. Para minimizar esses riscos, os planejadores de transporte recorrem à modelagem computacional para obter ajuda. Este artigo é uma breve digressão para o mundo da modelagem multiagente.



Usando o modelo, que é uma cópia do sistema de transporte real, é possível estimar a taxa de transferência necessária em cada trecho da estrada projetada, experimentar diferentes opções de rastreamento ou, por exemplo, estimar o período de retorno de um projeto, se for uma estrada com pedágio na estrutura de uma parceria público-privada. Mas outras tarefas importantes podem ser resolvidas: como organizar as melhores rotas de transporte público e calcular a receita potencial dos operadores, como avaliar a presença de uma escassez de vagas em uma área específica e muitas outras.

O mais interessante é que qualquer pessoa pode construir um modelo semelhante na era do software livre!

Uma das ferramentas de modelagem multiagente mais comuns é o código aberto.MATSim (Simulação de Transporte Multi-Agente) .

O MATSim simula o comportamento de agentes individuais. Um agente é uma representação por computador de um indivíduo no mundo real. Cada um desses agentes possui um plano diário, com base no qual ele se move de uma atividade para outra (por exemplo, casa-trabalho-casa, casa-instituto-trabalho-casa, casa-loja-trabalho-trabalho-casa-2 etc.), criando portanto, a demanda por infraestrutura rodoviária. Uma representação esquemática do plano diário é mais ou menos assim:

imagem

Para criar planos realistas de agentes que refletirão o comportamento real das pessoas durante o dia, são levados em consideração o número total de residentes de agentes, seus reassentamentos, locais de trabalho, estudo, localização de lojas, shopping centers, estações de trem e outros locais de atividade. Para validar a demanda, o modelo também é calibrado com base em pesquisas de campo: reconhecimento e cálculo dos fluxos de câmeras de vigilância e drones usando uma rede neural ou, por exemplo, medições manuais de intensidade nas estradas.

imagem

Durante a simulação, os agentes são distribuídos pela rede, imitando o comportamento realista das pessoas: implementando seu plano, os carros ocupam um lugar na estrada e nos estacionamentos, os usuários de transportes públicos tomam lugares no ônibus e também interagem entre si e, se muitos agentes selecionam uma estrada por vez, engarrafamentos e congestionamentos são criados. Tudo é como no mundo real!

Após a conclusão da simulação, é feita uma avaliação do cumprimento dos planos diários dos agentes, chamados de pontuação. O agente adquire unidades de serviço público no processo de atividade e as perde durante o movimento. Consequentemente, os agentes presos em um engarrafamento perdem mais unidades de serviços públicos do que os agentes que se deslocam pelas estradas livres.

Após cada iteração, alguns agentes reconstroem seu plano com base em informações sobre a carga da rede rodoviária de maneira a melhorar seu desempenho: os agentes podem alterar a hora de partida, o modo de transporte ou a rota. Os demais agentes seguem seus planos anteriores, que são armazenados na memória do programa.

Idealmente, após a simulação, um equilíbrio de Nash deve ser alcançado - isto é, uma situação em que nenhum agente pode melhorar sua posição sem piorar a posição de outros agentes. Geralmente, essa é a situação que se desenvolve ao longo do tempo nas estradas da cidade, dada a repensação diária da experiência do dia anterior por seus moradores. Para isso, são realizadas pelo menos 200 iterações no quadro de um cenário. Todo o ciclo de trabalho do MATSim é mais ou menos assim:

imagem

Da teoria à prática!


Para executar o primeiro cenário, precisamos do Intellij IDEA (ou Eclipse) com Java 1.8 integrado.
Abrimos o IDE, clonamos o repositório MATSim no github e nosso primeiro cenário está pronto para ser executado! Tão simples. Mas vamos primeiro ver quais arquivos de entrada usamos. Para a simulação mais simples, existem três deles: rede, planos, configuração.

Rede


O arquivo de rede é a rede na qual os agentes se movem. Consiste em nós e nós / links. Cada link possui atributos diferentes: tipo, comprimento do segmento, taxa de transferência, velocidade máxima, número de faixas, tráfego unidirecional, modos de transporte permitidos, etc.

imagem

Criar uma grade da cidade manualmente é difícil, impraticável e ineficiente. Por exemplo, nossa grade de São Petersburgo consiste em 26 mil nós e 46 mil links. Mas há boas notícias. A grade pode ser convertida do OpenStreetMap e editada usando o JOSM, que também é de código aberto.

Planos


O arquivo de planos é uma representação estruturada dos planos diários dos agentes. No cenário inicial, temos 100 agentes que saem de carro (mode = ”car”) pela manhã (end_time = ”05:59”) de casa (tipo = ”h”, link = ”1”) para trabalhar (tipo = "W", link = "20"), após o qual, após algum tempo (dur = "02:30"), eles retornam para casa.



Config


Finalmente, no arquivo de configuração, todas as configurações necessárias são definidas para executar o script. O MATSim consiste em módulos que você pode personalizar, adicionar ou remover conforme necessário.
Muitas das configurações no arquivo de configuração são intuitivas, mas você também pode sempre pesquisar as chamadas. Livro MATSim . Agora vamos considerar apenas dois módulos.
No módulo planCalcScore, os parâmetros de pontuação são definidos: por exemplo, para chegadas tardias, o agente recebe uma multa de 18 unidades. utilidade por hora (respectivamente, atrasar-se por 10 minutos equivale a perder 3 unidades de utilidade); o desempenho de alguma atividade (por exemplo, desempenho) traz 6 unidades utilitárias por hora e dirigir um carro custa as mesmas 6 unidades utilitárias por hora.Para encontrar parâmetros de pontuação realistas, as pesquisas de opinião costumam ser usadas para analisar o "custo" tempo.”

no módulo de estratégia, os parâmetros de re-planejamento são configurados, por exemplo, qual a percentagem de agentes (ModuleProbability) vai tentar a nova rota (redirecionar) durante a próxima iteração.



Assim, o objetivo da simulação é ajudar o get agente do ponto a ao ponto B com o menor custo.

Execução de script


Hora de abrir o RunMatsim runner e executar nosso primeiro script!

Os resultados da simulação estarão na pasta de saída na raiz do projeto. Os principais arquivos de visualização são rede e eventos. O arquivo de eventos contém informações por segundo sobre todas as ações de cada agente; portanto, com base nesse arquivo, você pode restaurar a imagem completa do movimento de todos os agentes. Você pode visualizar os resultados usando a Via .
Para resultados mais representativos, aumentarei o número de agentes para 500. É assim que a distribuição de 500 agentes se parece após a primeira iteração ...



No início da iteração, os agentes calcularam o caminho mais curto usando DijkstraComo resultado, a intensidade do tráfego em uma seção da rede excedeu sua taxa de transferência, um congestionamento se formou. Mas e se você lhes der a oportunidade de tentar rotas diferentes?



Após 200 iterações (~ 5 minutos), os agentes foram redistribuídos pela rede, o nível de carga do link agora não excede 0,5 e o tempo médio de viagem para todos os agentes diminuiu 14% (5 minutos). Viva, superamos a cortiça!

Ah, se fosse assim tão simples! Na realidade, os sistemas de transporte são muito mais complicados. Nos artigos a seguir, vou contar como participei do desenvolvimento de modelos de São Petersburgo e outras cidades e como resolvemos problemas práticos em casos reais. Scientia potentia est!



Postado por Andrey Kolomatsky, analista de transporte da OTSLab.

More articles:


All Articles