IEEE LATIN AMERICA TRANSACTIONS 1 Optimization of Public Transport Networks by Considering Alternative Positions for Network Stations Ingo P. P. Montarroyos and Danilo R. B. Araújo Abstract—Nowadays, the planning of metropolitan areas con- siders improving the quality of life of inhabitants and urban mobility is one of the main concerns. Studies point out that investments in public transportation and other modes are aimed at the overall improvement of mobility. However, there is a gap in proper tools for optimizing public transport networks. In fact, network optimization is an NP-Hard problem and there are usually many conflicting objectives that need to be optimized simultaneously. This paper proposes the use of many- objective evolutionary algorithms to address the problem of public transport networks optimization, focusing on metropolitan bus lines. The proposal consists in optimizing the position of bus stops and consequently obtaining new routes that pass through these stops in order to minimize the average travel time, the time spent between origin / destination and the variance of distance between the stops. To evaluate our proposal, a simulator was used to simulate the behavior of different passenger profiles in an urban area and the results were compared between the lines obtained by the optimization process and existing bus lines in the city of São Paulo. According to our results, optimized bus routes have mean travel time 22% less than the existing route and the time spent between origin/destination has decreased up to 18%. Index Terms—Public Transport, Public Transport Network, Bus, Optimization, Evolutionary computation. I. INTRODUÇÃO OCrescimento saudável de grandes centros metropolitanos está amplamente conectado ao fornecimento de serviços de transporte adequados. Uma crescente população urbana requer acesso a educação, comercio, emprego e lazer. A provisão de infraestruturas de transporte, como linhas de metrô e linhas de ônibus, é importante para o desenvolvimento dos centros urbanos, uma vez que permite aos cidadãos que não possuem veículos próprios a locomoção entre pontos de interesse em um menor espaço de tempo. Por outro lado, de acordo com [1], o conceito de sustentabilidade veio a ser recentemente incorporado, mesmo que em graus variantes, no que se refere a planejamento e gerenciamento urbano em difer- entes regiões do Brasil. Levando em consideração a crescente preocupação com a sustentabilidade no planejamento urbano, é preciso investir em tecnologias que auxiliem e incentivem ainda mais a utilização e implementação de meios sustentáveis. Estudos recentes mostram que a satisfação de viagem sentida Ingo P. P. Montarroyos is with Departamento de Computação, Universidade Federal Rural de Pernambuco e-mail:ingo.pastl@gmail.com Danilo R. B. Araújo is with Departamento de Computação, Universidade Federal Rural de Pernambuco e-mail:danilo.araujo@ufrpe.br por usuários de transporte público está diretamente ligara à qualidade do serviço de transporte público [2]. Portanto, o planejamento de uma infraestrutura de trans- porte público de qualidade possibilitaria que mais cidadãos se sintam motivados a escolher viagens por meios públicos, re- duzindo assim a dependência de veículos pessoais, que conse- quentemente também proporcionaria cidades mais habitáveis, saudáveis e neutras em carbono, como foi argumentado em [3]. Em adição, de acordo com [4], a qualidade de serviço pode influenciar a acessibilidade percebida em transportes públicos, uma vez que transportes públicos em sua essência proporcionam uma menor facilidade de uso que opções de transporte porta a porta, sendo assim importante enfatizar o foco nos atributos relacionados à facilidade percebida pelas pessoas de viver a vida que desejam com a ajuda do sistema de transporte público. No que se refere a qualidade de infraestrutura, o planeja- mento vai além da escolha de materiais e tecnologias para a sua construção, o projeto eficiente da topologia física de uma rede de transporte público também é essencial para o bom funcionamento e qualidade da mesma. Sob o ponto de vista do usuário de uma linha de ônibus, diversas preocupações estão presentes, como a proximidade entre as paradas e a sua localização de partida e chegada, o tempo médio de viagem, e assim por diante. Pode-se dizer que existe uma lacuna em termos de ferra- mentas adequadas para otimizar as redes de transporte público. A otimização de redes é um problema NP-Difícil e normal- mente existem muitos objetivos conflitantes que precisam ser otimizados simultaneamente. Ultimamente Algoritmos Evolucionários Multi-objetivos (AEMOs) tem sido amplamente usados para encontrar soluções quase ótimas para o projeto de topologias físicas [5] [6]. Banerjee e Kumar [5] propuseram um AEMO para lidar com o projeto da topologia física de redes ópticas, aplicando a proposta deles em três cenários de redes com 10, 21 e 36 terminais. Em [5], o desempenho do AEMO foi comparado com uma abordagens exaustivas. Essa comparação foi feita apenas com a rede de 10 terminais por causa da inviabilidade de se usar a abordagem exaustiva em redes maiores. Além disso, abordagens multi-objetivas que consideram penalidades da camadas física apresentam um grande custo computacional para avaliação de uma possível solução, visto que avaliação de desempenho geralmente é realizada por meio de simulações de Monte Carlo. Em 2023, Candeias et al. [6] propuseram INGO et al.: OPTIMIZATION OF PUBLIC TRANSPORT NETWORKS BY CONSIDERING ALTERNATIVE POSITIONS FOR NETWORK STATIONS 2 um nova metodologia de lidar com o projeto de redes ópticas considerando a posição dos nós terminais como variáveis de decisão. O método consistiu na utilização de um algoritmo de clusterização para determinar a localização inicial dos nós ter- minais e de um algoritmo evolucionário para muitos objetivos com busca local para modificar as localizações dos terminais durante o processo de otimização. Neste caso o algoritmo evolucionário escolhido foi o Non-dominated Sorting Genetic Algorithm III (NSGAIII). A proposta de Candeias et al. [6] superou abordagens tradi- cionais e inspirou este trabalho para aplicar uma metodologia de otimização de topologias semelhante no contexto de redes de transporte público, uma vez que não foram encontrados pesquisas anteriormente publicadas com uma proposta semel- hante. Por tanto, o objetivo deste trabalho é otimizar linhas de ônibus com a finalidade de melhorar a experiencia do usuário sob diversos aspectos. Nessa linha, o foco deste artigo é otimizar a posição das paradas e consequente obtenção de novas rotas que passam pelas novas paradas com o obje- tivo de minimizar o tempo médio de viagem, o tempo de deslocamento da origem/destino até as paradas e a variância entre as paradas. Para avaliação da proposta, é utilizado um simulador próprio que simula o comportamento de diferentes perfis de passageiros em uma área urbana e os resultados foram comparados entre linhas obtidas pelo processo de otimização e linhas de ônibus existentes na cidade de São Paulo. De acordo com nossos resultados, as rotas de ônibus otimizadas têm tempo médio de viagem 22% menor que a rota existente e o tempo gasto entre origem/destino diminuiu até 18%. O restante deste artigo está organizado da seguinte forma. A Seção II fornece uma revisão sobre Otimização Multi- Objetiva. A Seção III apresenta as ferramentas utilizadas na pesquisa. A Seção IV descreve o problema em detalhes. A Seção V apresenta e discute os resultados obtidos nos experimentos iniciais. A Seção VI apresenta as conclusões e sugestões para trabalhos futuros. II. OTIMIZAÇÃO MULTI-OBJETIVA AEMOs são meta-heurísticas capazes de fornecer boas soluções para problemas de otimização com vários objetivos conflitantes e apresentam baixo custo computacional em com- paração com abordagens exaustivas. Diversos AEMOs estão disponíveis na literatura [7] e neste trabalho é utilizado o algoritmo baseado em pontos de referência Non-dominated Sorting Genetic Algorithm III (NSGA-III), que é considerado por muitos como estado da arte na área, especialmente para problemas com 3 ou mais objetivos conflitantes. A. NSGA-III Em 2002, Deb et al. [8] propuseram o Non-dominated Sorting Genetic Algorithm II (NSGA-II). Desde 2002, vários estudos focados em problemas no mundo real demonstraram que o NSGA-II é uma meta heurística apropriada para a solução de problemas de otimização com muitos objetivos, especialmente se dois objetivos conflitantes são considerados [9]. Para tratar com problemas com mais de três objetivos conflitantes, Deb et al. propuseram em 2014 uma versão mel- horada do NSGA-II, denominada NSGA-III [10]. O NSGA- III funciona da seguinte maneira. Inicialmente, um conjunto de pontos de referência são gerados utilizando um método sistemático descrito em [11]. Nesse estágio, o NSGA-III inicializa a população Pt com N indivíduos. Em seguida, o NSGA-III realiza os seguintes passos a cada geração t. Primeiramente, o algoritmo cria uma população descendente Qt a partir da população Pt utilizando algumas operações como seleção aleatória, cruzamento e mutação. Em seguida, um mecanismo de seleção é utilizado na população combinada Rt = PtUQt para eliminar soluções extras. Assim, Rt é ordenada pelo método de fast-non-dominated sorting e catego- rizada em diferentes frentes de Pareto. Então, a nova população Pt + 1 é preenchida por cada nível em sequência até o nível Ft que não pode ser incluído integralmente sem que o limite de tamanho para a nova população seja ultrapassado. Essa papulação parcial é denominada St. Quando a população Pt+1 está incompleta, o algoritmo seleciona soluções da população F1 utilizando uma nova técnica que associa cada solução na população temporária St com um ponto de referência que possui a menor distância perpendicular em relação a solução. Depois disso, o NSGA-III aplica uma seleção incremental de indivíduos da população Ft. Esse procedimento é executando da seguinte maneira. Primeiramente, seja pj definido como a contagem de indivíduos em St para o j-ésimo ponto de referencia, e µj como o número de indivíduos na população Ft já associados com o ponto de referência j. Assim, o mecanismo de preservação de grupos começa procurando um conjunto de pontos de referência Jmin com o mínimo definido por pj e um desses pontos j é aleatoriamente selecionado para o conjunto. Se pj = 0, isso significa que não existe um indivíduo em St associado com o ponto de referência j. Desta forma, dois casos podem acontecer: a) se µj ̸= 0, então o indivíduo com a menor distância perpendicular em relação a linha de referência é adicionado a Pt + 1 e 1 é acrescido ao valor do termo pj ; e b) Se µj = 0, então o ponto de referência atual é eliminado. Se pj ≥ 0 então existem um ou mais indivíduos em St associados com o ponto de referência e, nesse caso, um indivíduo é aleatoriamente escolhido de Ft que esteja associado com o ponto de referência j e é adicionado a Pt + 1. Além disso, o termo pj também tem seu valor incrementado por 1. Para mais detalhes sobre o algoritmo veja o artigo original em [10]. B. Hypervolume No processo de otimização multi-objetiva existem dois objetivos distintos: descobrir soluções mais próximas possível de soluções ótimas de Pareto, e achar soluções as mais diversas possível na frente não dominada. Desta forma, para comparar e avaliar o desempenho da otimização é preciso utilizar métricas de desempenho que avaliem a convergência até a frente de Pareto ótima e a diversidade da frente de Pareto obtida. O Hypervolume [12] é uma métrica que proporciona uma medida qualitativa tanto de convergência quanto de diversidade. Se soluções são considerados pontos em um espaço objetivo, o hypervolume é o espaço n-dimensional que é contido por uma 3 IEEE LATIN AMERICA TRANSACTIONS população de soluções. Devido a propriedades do indicador [13], uma população com um maior hypervolume é mais provável de apresentar um conjunto com melhor compromisso dentre os diversos objetivos. III. FERRAMENTAS UTILIZADAS PARA A REALIZAÇÃO DA PESQUISA A. Base de dados Para validar a proposta deste trabalho foram utilizadas rotas de ônibus que estão atualmente implementadas, comparando- as com as novas soluções obtidas pelo processo de otimização. Portanto, um dos passos iniciais na execução da pesquisa consistiu em buscar dados referentes às infraestruturas de transportes públicos que estão atualmente em uso. Con- siderando a disponibilidade e corretude de dados abertos de diversas regiões metropolitanas, optou-se pela base de dados SPTrans referente à região metropolitana de São Paulo, que disponibiliza os seus dados em formato GTFS [14]. B. APIs de roteamento No processo de otimização de uma linha de transporte público é preciso avaliar a qualidade das soluções candidatas (fitness). Nesta proposta o processo de avaliação consiste em avaliar a variação da distância percorrida pelos veículos da linha entre os terminais de parada, a média de tempo de caminhada dos passageiros até as paradas (da origem até a parada de início e da parada final até o destino efetivo), e o tempo médio que estes passageiros gastaram percorrendo a linha dentro do ônibus. Para realizar os cálculos relacionados aos objetivos de otimização foi preciso a utilização de uma API que possui a funcionalidade de calculo de rotas. Uma pesquisa foi executada para tentar encontrar a API que melhor atendesse às necessidades da pesquisa, resultando na consideração de três principais APIs: Google Maps API [15], Bing Maps API [16] e OSRM API [17]. A Tabela I apresenta os principais aspectos considerados para cada API. A primeira API considerada para o aplicação foi a Google Maps API, uma vez que esta é desenvolvida pela Google, possui uma documentação de fácil leitura e é a API mais popular no mercado. A API apresentou todas as ferramentas e funcionalidades requeridas pela aplicação, sendo capaz de calcular rotas que passam por pontos específicos, chamados de waypoints, ao mesmo tempo que fornece a distância percorrida e o tempo gasto entre estes waypoints. Entretanto, a Google Maps API apresentou aspectos negativos que desencorajaram o uso nessa pesquisa. Uma chave gratuita da Google Maps API possui um limite de 1400 requisições diárias com apenas 25 waypoints cada. Um itinerário de ônibus na cidade de São Paulo possui em torno 60 terminais de parada ao longo de sua rota, resultando na necessidade de 3 requisições pra calcular totalmente uma rota. Para apresentar resultados significantes, a aplicação precisaria calcular mais de 40000 rotas. Com o limite de 1400 requisições diárias somado à necessidade de gastar 3 dessas requisições pra calcular uma única rota, não seria possível obter bons resultados em um espaço de tempo razoável. Para contornar estes limites seria preciso entrar pessoalmente em contato com a Google para elaborar um plano de contrato e obter uma chave premium, resultando em custo financeiro adicional. A segunda API considerada foi a Bing Maps API, desen- volvida pela Microsoft. Tanto a Google Maps API quanto a Bing Maps API apresentam cálculos de rotas com resultados semelhantes. Diferente da API da Google, a Bing Maps API possui o mapeamento de São Paulo desatualizado, com vias recentemente construídas ainda não mapeadas e com fluxos de direção desatualizados. Este ponto negativo, entretanto, não traria problemas para aplicação, uma vez que o processo de otimização poderia ser executado com a utilização de qualquer mapeamento. Assim como a Google Maps API, a Bing Maps API também possui limitações em sua chave gratuita, possibilitando apenas 25 waypoints por requisição e disponibilizando apenas 125000 requisições acumulativas por ano. Além da chave gratuita básica, a Bing Maps API também disponibiliza uma chave gratuita educacional para projetos não lucrativos. Esta chave mantém o limite de 25 waypoints por requisição e apresenta uma melhoria em relação ao limite de requisições, possibilitando a solicitação de 50000 requisições diárias. 50000 requisições diárias é uma melhoria significativa em relação ao limite de 14000 requisições diárias da Google Maps API, porém ainda não é um número adequado para obter-se bons resultados em um espaço de tempo razoável, levando-se em conta o limite de 25 waypoints por requisição, que resultam na necessidade de 3 requisições para calcular uma rota de 60 terminais por completo. Assim como a API da Google, os limites da Bing Maps API também podem ser contornados ao elaborar-se um contrato com a Microsoft para a aquisição de uma chave enterprise, também resultando em custo financeiro adicional. A terceira API considerada, Open Source Routing Machine - OSRM, representa uma solução open source que não ap- resenta muitas limitações ao usuário. O projeto OSRM visa implementar um motor de roteamento de alto desempenho de forma gratuita. Este motor utiliza o dados do OpenStreetMap, outro projeto que visa disponibilizar um mapeamento global gratuito. Para utilizar o sistema de roteamento é preciso antes implementá-lo em uma máquina que servirá como um servidor de API no estilo REST. Esta máquina recebe requisições no formato HTTP contendo os waypoints da rota, e retorna o resultado do roteamento no formato JSON. A OSRM API não possui limite de waypoints por rota e, já que é implementada em um servidor próprio, não possui limite de requisições diárias. Outra vantagem desta API é que o seu servidor pode ser implementado na mesma rede que a máquina executando a aplicação da pesquisa, possibilitando assim um maior desem- penho no recebimento de requisições e no envio de respostas. Entretanto, a API apresenta duas desvantagens em relação as outras APIs consideradas: a necessidade de ter uma máquina extra para implementar o servidor da API, e a menor eficiência no sistema de calculo de rotas. Considerando as vantagens e desvantagens de cada API, optou-se pela OSRM API para compor o motor de avaliação do processo de otimização desta pesquisa. INGO et al.: OPTIMIZATION OF PUBLIC TRANSPORT NETWORKS BY CONSIDERING ALTERNATIVE POSITIONS FOR NETWORK STATIONS 4 TABLE I: APIs de roteamento. Google Maps API - Chave gratuita Bing Maps API - Chave educacional OSRM API - servidor próprio Desenvolvida pela Google, uma Desenvolvida pela Microsoft, uma Projeto Open Source que utiliza das atuais gigantes da tecnologia. das atuais gigantes em tecnologia. o mapeamento OpenStreeMap 25000 requisições diárias gratuitas 125000 requisições anuais gratuitas Requisições ilimitadas Máx. 25 waypoints por requisição Máx. 25 waypoints por requisição Sem limite de waypoints por requisição Cálculo de rotas mais eficiente Cálculo de rotas mais eficiente Requer máquina extra para uso comparado com OSRM API comparado com OSRM API como servidor Recurso street view para atualização Desempenho é superior quando servidor está em mesma rede C. Ambiente No desenvolvimento da aplicação utilizou-se o JMetal [18], framework baseado em Java e que implementa vários algorit- mos de otimização, entre eles o NSGA-III, e que também pos- sui um conjunto bem conhecido de indicadores de qualidade para problemas multi-objetivos. Outras bibliotecas de progra- mação para java também foram usadas no desenvolvimento da aplicação, tais como: Apache HttpComponents para lidar com requisições HTTP; e Org.Json para manusear as respostas no formato JSON vindas da API de mapeamento. IV. DESCRIÇÃO DO PROBLEMA O problema de pesquisa tratado neste artigo pode ser formalmente formulado da seguinte forma. Considerando as geolocalizações das estações/paradas em uma linha de trans- porte público como variáveis de decisão, o objetivo é encontrar novas posições para as paradas (e novas rotas) considerando os seguintes objetivos: minimizar a média de tempo que os passageiros gastam andando de suas localizações até as paradas; minimizar a média de tempo que os passageiros permanecem no ônibus (tempo de viagem); e minimizar a variância da distância entre os terminais de parada na linha (uniformidade no atendimento à população). As geolocalizações dos terminais são definidas por T = (lati, loni), em que (i ∈ 1, 2, ..., N). lati e loni são coorde- nadas em graus da N-ésima estação/parada e N é o número total de paradas. A seguinte técnica foi utilizada para simular viagens re- alizadas por usuários que fazem uso da linha. Dadas as geolocalizações dos terminais de parada em um determinado itinerário de uma linha de transporte público, definem-se limites considerando as paradas com maior latitude, menor latitude, maior longitude e menor longitude. Os valores da maior latitude e maior longitude são incrementados por um número m de metros, e por sua vez os valores da menor latitude e menor longitude são decrementados por este mesmo valor, formando um quadrilátero que é considerado o limite das redondezas da linha de transporte sendo avaliada. No mapeamento utilizado o número de quilômetros por grau de coordenada equivale a mais ou menos 111km. Para este problema foi considerado o valor 111,32km. Um quilometro em graus de coordenada equivale a 1/111, 32 = 0, 0089. Por sua vez, um metro em graus de coordenada equivale a 0, 0089/1000 = 0, 0000089. Desta forma, para incrementar ou decrementar os valores de latitude ou longitude em metros calcula-se c = m ∗ 0, 0000089 e adiciona-se ou subtrai- se o valor de c ao valor da coordenada em questão. As coordenadas [Latmax + c; Latmin - c; Lonmax + c; Lonmin - c] formam o quadrilátero mencionado anteriormente. Dois pontos são aleatoriamente gerados dentro dos quadrilátero, um considerado a origem e o outro o destino de um passageiro no simulador. Para simular uma viagem da origem até o destino os seguintes passos são seguidos. Utiliza-se a API de roteamento para calcular o tempo to em segundos que uma pessoa leva para andar do ponto de origem até o terminal de parada mais próximo a este ponto. Em seguida a API é novamente utilizada para determinar o tempo tv em segundos gasto percorrendo a linha dentro de um veículo de transporte até o terminal mais próximo do ponto de destino. E por último A API é mais uma vez utilizada para calcular o tempo td em segundos que uma pessoa levaria para andar do terminal de descida até o ponto de destino. Seja w a soma de to e td em uma única viagem, uma quantidade x de simulações são efetuadas e a média do tempo de caminhada é obtida da seguinte forma ∑x i=1 wi x . Por sua vez os valores de tv obtidos com as x simulações são utilizadas para calcular a média de tempo de viagem dentro da linha, que pode ser definida por ∑x i=1 tvi x . Para determinar a variância da distância entre os terminais de parada, as distâncias entre os terminais da linha, medidas em metros, são obtidas através a API de roteamento e em seguida o calculo de variância é efetuado. Portanto, nesta pesquisa foi considerado um simulador de eventos discretos, no qual um evento consiste na subida/descida de um passageiro e este processo segue uma distribuição de probabilidade uniforme. Desta forma, a avaliação de aptidão de novas soluções candidatas para a linha de ônibus consiste em executar este simulador na tentativa de emular o comportamento real de uma população de passageiros que potencialmente usaram a linha considerada. Em suma, o problema pode ser resumido conforme equações abaixo. Descrição do problema: Dadas as variáveis de decisão representadas pela Eq. 1 X⃗ = [T1, T2, ..., TN ], (1) 5 IEEE LATIN AMERICA TRANSACTIONS o objetivo é minimizar  f1(X⃗) = MTC f2(X⃗) = MTV f3(X⃗) = V . (2) Na Eq. 2 MTC é a média do tempo de caminhada, em segundos, MTV é a media do tempo de viagem dentro da linha, em segundos, e V é a variância da distancia entre paradas, em metros. A. Arranjo experimental Esta subseção descreve detalhes sobre os experimentos considerados inicialmente para validar a proposta. O itin- erário escolhido para ser otimizado foi o da linha número "423032", "Sao Bernardo do Campo (Jardim Las Palmas) / São Paulo (Terminal Sacoma)", com 69 terminais de parada. Após receber o itinerário selecionado, a aplicação cria uma população inicial P1 para o algoritmo NSGA-III de tamanho 92, sendo este o tamanho definido para todas as populações geradas pelo NSGA-III. Cada indivíduo da população P1 possui um cromossomo com 69 x 2 = 138 posições (genes). O primeiro indivíduo da população, denominado de p1, tem as suas variáveis com valores equivalentes aos valores das latitudes e longitudes dos terminais do itinerário original escolhido (latitudes e longitudes da linha em operação). Todos os outros indivíduos da população P1 são criados da seguinte maneira. Considerando que p1 é o indivíduo a ser criado, 800 é o valor de m, e mg é a conversão de m para graus de coordenada, o valor de cada variável em pi será igual ao valor da variável em p1 com posição equivalente em seu vetor de características somado a um valor gerado aleatoriamente entre 0 e mg . Depois da criação da população inicial, o NSGA-III é executado da forma tradicional, mas operadores especiais foram desenvolvidos na pesquisa. O método de mutação foi um destes operadores. A mutação funciona da seguinte maneira. Considerando um determinado conjunto de duas variáveis que representa a geolocalização de um terminal de parada, é identificada a distância d entre este terminal e outro terminal mais próximo no cromossomo considerado, e em seguida um valor aleatório entre −d e d é gerado e somado a cada variável do conjunto de duas variáveis. A probabilidade de mutação é definida como 1, 0/(|X⃗|). No caso da linha 423032, a probabilidade de mutação é 1, 0/138 = 0, 007, ou 0, 7%. O método de seleção escolhido foi o Torneio Binário. O operador de cruzamento adotado seleciona dois indivíduos para gerar dois descendentes cujas variáveis receberão valores do pai 1 ou do pai 2. Cada conjunto de duas variáveis do descendente 1 tem 25% de chance para receber valor do pai 2 e 75% de chance para receber valor do pai 1. Por sua vez cada conjunto de duas variáveis do descendente 2 tem 75% de chance para receber valor do pai 2 e 25% de chance para receber valor do pai 1. Finalmente, foi determinado que 30 simulações de viagens serão executadas para avaliar cada indivíduo. Foi definido como critério de parada uma quantidade máxima de 400 gerações. V. RESULTADOS Utilizando um laptop com processador Intel i5-3337U e 6GB de memória RAM DDR3 como servidor do serviço de roteamento, um computador pessoal com processador Intel Core i5-4590 e 8GB de memória RAM DDR3 1600MHz para rodar o algoritmo de otimização, e com ambas as máquinas presentes na mesma rede local, cada execução do algoritmo com 400 gerações levou em média 9 horas para ser concluída. O gráfico da Figura 3 apresenta a média do hipervolume considerando 30 execuções independentes do algoritmo. Com base nas execuções, foi possível perceber que as primeiras iterações do algoritmo levam o hipervolume para um patamar de 0,45 e obtém-se um pico pouco acima de 0,9, que é a região com soluções de maior qualidade. A Figura 4 representa um exemplo de frente de Pareto em gráfico de coordenadas paralelas. Este gráfico foi obtido em uma das execuções do algoritmo que forneceu um hipervolume de 0,96. Na Figura 4, o objetivo 1 é referente ao tempo médio de viagem; o objetivo 2 é referente ao tempo médio que os indivíduos gastam caminhando até as paradas; o objetivo 3 é referente à variância da distância entre as paradas. A Figura 1 represente a linha de ônibus original da linha "423032" a Figura 2 representa a solução em vermelho desta- cada na Figura 4, sendo uma nova solução otimizada obtida pela proposta deste artigo. Embora as linhas sejam semelhantes quando é considerada uma inspeção visual no mapa, os valores numéricos dos objetivos considerados evidenciam a vantagem em usar o algoritmo proposto neste trabalho. A solução original da linha "423032" obteve a seguinte avaliação: 872,3 segundos como o tempo médio de viagem pela linha; 573 segundos como tempo o médio de caminhada até o destino; 140574 metros quadrados de variância na distância entre os terminais da solução. A solução destacado em vermelho no gráfico da Figura 4 obteve a seguinte avaliação: 676,5 segundos como tempo médio de viagem dentro da linha; 469 segundos como tempo médio de caminhada até o destino; e 19156,5 metros quadrados de variância na distância entre os terminais de parada na solução. Além de menor variância das distância entre paradas (melhoria de atendimento à população), obtém-se uma redução de 22,44 % no tempo médio de viagem e uma redução de 18,15% no tempo de caminhada. VI. CONCLUSÕES Este artigo propõe uma abordagem multi-objetiva para tratar o problema de otimização de linhas de transporte público considerando a otimização de diversos objetivos importantes para a população atendida, como tempo de caminhada até as paradas, tempo de viagem e variância da posição das paradas. A abordagem considera a determinação da posição das paradas e e definição das rotas, usando o algoritmo NSGA-III como linha mestra para otimização multi-objetiva. Para validação da proposta foi considerada uma importante linha de ônibus da cidade de São Paulo e uma das soluções obtidas pela proposta do artigo obteve melhoria significativa em todos os objetivos considerados, chegando a uma redução acima de 22% no tempo de viagem. INGO et al.: OPTIMIZATION OF PUBLIC TRANSPORT NETWORKS BY CONSIDERING ALTERNATIVE POSITIONS FOR NETWORK STATIONS 6 Fig. 1: Solução original Fig. 2: Solução obtida pelo algoritmo 7 IEEE LATIN AMERICA TRANSACTIONS Fig. 3: Hipervolume vs. iterações. Fig. 4: Exemplo de frente de Pareto em gráfico de coordenadas paralelas. Uma das limitações desta abordagem foi a incapacidade de considerar fatores como a qualidade do asfaltamento das ruas, a densidade demográfica de diversas regiões e a intensidade de movimentação de veículos nas vias, desta forma pode ser considerado melhorar o simulador de eventos discretos em trabalhos futuros para considerar esses fatores. Referente à outras sugestões para trabalhos futuros, devem ser consideradas diversas outras linhas de transporte público para demonstração da capacidade de generalização da pro- posta, incluindo outros modais (como metrô). Com relação aos aspectos técnicos do algoritmo proposto, poderão ser feitos estudos sobre o uso de algoritmos de clusterização para proposição de operadores meméticos para busca local da posição das paradas, e estudos com outras meta-heurísticas e ajustes paramétricos durante a execução do algoritmo. AGRADECIMENTOS Os autores agradecem o apoio financeiro fornecido pela UFRPE e CNPq. REFERENCES [1] A. N. R. da Silva, M. da Silva Costa, and M. H. Macedo, “Multiple views of sustainable urban mobility: The case of brazil,” Transport Policy, vol. 15, no. 6, pp. 350–360, 2008. [2] L. Olsson, M. Friman, K. Lättman, and S. Fujii, “Travel and life satisfaction - from gen z to the silent generation,” Journal of Transport Health, vol. 18, p. 100894, 2020. [3] M. J. Nieuwenhuijsen, “Urban and transport planning pathways to carbon neutral, liveable and healthy cities; a review of the current evidence,” Environment International, vol. 140, p. 105661, 2020. [4] M. Friman, K. Lättman, and L. E. Olsson, “Public transport quality, safety, and perceived accessibility,” Sustainability, vol. 12, no. 9, 2020. [5] N. Banerjee and R. Kumar, “Multiobjective network design for realistic traffic models,” in Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation, GECCO ’07, (New York, NY, USA), p. 1904–1911, Association for Computing Machinery, 2007. [6] J. Candeias, D. R. de Araújo, P. Miranda, and C. J. Bastos-Filho, “Memetic evolutionary algorithms to design optical networks with a local search that improves diversity,” Expert Systems with Applications, vol. 232, p. 120805, 2023. [7] B. Li, J. Li, K. Tang, and X. Yao, “Many-objective evolutionary algorithms: A survey,” ACM Comput. Surv., vol. 48, sep 2015. [8] K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, “A fast and elitist multiobjective genetic algorithm: Nsga-ii,” IEEE Transactions on Evo- lutionary Computation, vol. 6, no. 2, pp. 182–197, 2002. [9] C. A. Coello Coello, C. Dhaenens, and L. Jourdan, Multi-Objective Combinatorial Optimization: Problematic and Context, pp. 1–21. Berlin, Heidelberg: Springer Berlin Heidelberg, 2010. [10] K. Deb and H. Jain, “An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part i: Solving problems with box constraints,” IEEE Transactions on Evolutionary Computation, vol. 18, no. 4, pp. 577–601, 2014. [11] I. Das and J. E. Dennis, “Normal-boundary intersection: A new method for generating the pareto surface in nonlinear multicriteria optimization problems,” SIAM Journal on Optimization, vol. 8, no. 3, pp. 631–657, 1998. [12] L. Bradstreet, “The hypervolume indicator formulti-objective optimisa- tion: calculation and use,” The University of Western Australia, 2011. [13] E. Zitzler, L. Thiele, M. Laumanns, C. Fonseca, and V. da Fonseca, “Performance assessment of multiobjective optimizers: an analysis and review,” IEEE Transactions on Evolutionary Computation, vol. 7, no. 2, pp. 117–132, 2003. [14] SPTrans, “Gtfs - sp.” http://www.sptrans.com.br/desenvolvedores/ perfil-desenvolvedor/. Accessed: 2023-09-26. [15] G. LLC, “Google maps api.” https://mapsplatform.google.com/. Ac- cessed: 2023-09-26. [16] M. Corporation, “Bing maps api.” https://www.microsoft.com/en-us/ maps/bing-maps/choose-your-bing-maps-api. Accessed: 2023-09-26. [17] P. OSRM, “Osrm api.” https://github.com/Project-OSRM. Accessed: 2023-09-26. [18] M. V. A.J. Nebro, J.J. Durillo, “jmetal framework.” https://github.com/ jMetal/jMetal. Accessed: 2023-09-26. 1st author Ingo Porfírio Pastl Montarroyos joined the Bachelor’s degree in Computer Science at UFRPE - Universidade Federal Rural de Pernam- buco as a student in 2016. He currently holds the position of Solutions Specialist at Truewind. http://www.sptrans.com.br/desenvolvedores/perfil-desenvolvedor/ http://www.sptrans.com.br/desenvolvedores/perfil-desenvolvedor/ https://mapsplatform.google.com/ https://www.microsoft.com/en-us/maps/bing-maps/choose-your-bing-maps-api https://www.microsoft.com/en-us/maps/bing-maps/choose-your-bing-maps-api https://github.com/Project-OSRM https://github.com/jMetal/jMetal https://github.com/jMetal/jMetal INGO et al.: OPTIMIZATION OF PUBLIC TRANSPORT NETWORKS BY CONSIDERING ALTERNATIVE POSITIONS FOR NETWORK STATIONS 8 2nd author Danilo R. B. de Araújo was born in Recife, Brazil. He received the B.Sc. degree in Computer Science from the Catholic University of Pernambuco, in Recife, in 2002, and the M.Sc. degree in Computer Engineering from University of Pernambuco in 2009. He received his PhD degree in Electronics Engineering from the Federal University of Pernambuco, Recife in 2015. In 2013 he joined the Department of Computing at Federal Rural Uni- versity of Pernambuco, in Recife, where he currently is an Associate Professor. His research interests are in networking, simulation, modelling and optimization. He has coordinated several research projects financed by state and federal agencies. He also took part in research and development (R&D) projects sponsored by Itautec-Oki and Padtec-Brazil since 2003. He has authored more than 50 papers last 10 years. Prof. Danilo Araújo is Member of IEEE (Institute of Electrical and Electronics Engineers) and Member of SBC (Brazilian Society of Computing). RID: http://www.researcherid.com/rid/I-3029-2015. Citations: https://scholar. google.com.br/citations?user=o6eUGfAAAAAJ&hl=pt-BR. ACRONYMS AEMO Algoritmo Evolucionário Multi-objetivo http://www.researcherid.com/rid/I-3029-2015 https://scholar.google.com.br/citations?user=o6eUGfAAAAAJ&hl=pt-BR https://scholar.google.com.br/citations?user=o6eUGfAAAAAJ&hl=pt-BR Introdução Otimização Multi-Objetiva NSGA-III Hypervolume Ferramentas utilizadas para a realização da pesquisa Base de dados APIs de roteamento Ambiente Descrição do Problema Arranjo experimental Resultados Conclusões References Biographies 1st author 2nd author