Demografiske endringer og befolkningsframskrivinger

Muitos critérios de parada baseados na evolução da população podem ser utilizados. Alguns são similares aos utilizados em metaheurísticas de solução única, como procedimentos estáticos (onde o fim da procura está relacionado a um número fixo de iterações ou a um tempo limite de processamento), ou procedimentos adaptativos (onde o fim da procura não é conhecido a priori, podendo ser um número fixo de iterações sem melhoria, por exemplo) (Talbi, 2009).

Outros critérios de parada são específicos para metaheurísticas baseadas em população. Eles são geralmente baseados em alguma estatística relativa à população da geração atual ou da sua evolução, sendo principalmente relacionados à diversidade da população. Quando a população estagna, continuar o algoritmo não é útil (Talbi, 2009). O conceito de população estagnada adotado no presente trabalho é quando não ocorre a entrada de novos indivíduos na população, ou seja, as soluções são idênticas por um número N de gerações. O critério de parada final será por quantidade de gerações a executar. Para simplificação, considera-se a comparação da média dos valores de aptidão de todos os indivíduos da população ao longo das gerações ao invés de se comparar os indivíduos um a um.

Neste trabalho, foi adotado um procedimento adaptativo. A repetição da busca é considerada concluída quando, mesmo depois de um número N de gerações, não é encontrada nenhuma nova solução melhor. Ou seja, quando a população está estagnada a N gerações. São feitas M reinicializações da população antes do algoritmo ser considerado concluído, de forma a se procurar em várias regiões do espaço de busca.

5.4 Alocação da Demanda

Uma vez definidas as linhas que compõem a rede, a demanda por transporte público que será atendida deve ser alocada à rede, ou seja, para cada par origem- destino, a quantidade de passageiros procura o melhor trajeto para chegar da origem ao destino considerando as linhas existentes na solução. Este melhor trajeto procura minimizar o tempo de espera, tempo de viagem dentro do veículo e transferências necessárias. O principal destaque da alocação é qual método deve ser aplicado para efetivamente escolher essa “melhor opção” para os usuários. Esse procedimento de alocação deve ser feito para cada novo indivíduo gerado e utiliza boa parte do tempo computável empregado na busca.

5.4.1 Estratégia de Alocação

A alocação da demanda é um subproblema do PRTP que por si só suscita diversos conceitos e considerações importantes. O problema tem sido estudado nos últimos anos com novas abordagens, vide referências do trabalho de Szeto et al. (2011). Os autores mencionam que o método mais comum é o baseado em frequência (frequency-based) de Chriqui e Robillard (1975), que foi generalizado nos conceitos de estratégia e hipercaminhos (hyperpath) de Spiess e Florian (1989).

Os conceitos importantes mencionados, sendo explorados em artigos recentes, são: a consideração de incertezas na demanda e na oferta, como as variabilidades dos tempos de viagem dentro do veículo, em espera e no congestionamento; a incorporação do comportamento de aversão a risco dos passageiros; e a lotação do veículo (Szeto et al., 2011). Estas considerações,

entretanto, envolvem uma maior complexidade dos modelos de alocação, e, neste momento, não serão consideradas.

Embora o método baseado em frequência ignore os horários detalhados de chegadas e partidas, estes modelos são mais eficientes computacionalmente e podem comportar redes maiores, sendo apropriadas para o planejamento estratégico e de longo prazo das redes de transporte público (Szeto et al., 2011).

A estratégia utilizada será uma adaptação dos modelos de alocação utilizados em Baaj e Mahmassani (1991), Fahn e Machemehl (2006) e Afandizadeh et al. (2013). Primeiramente, o usuário procura uma alternativa de transporte que o leve diretamente de sua origem ao seu destino, evitando-se as transferências. Caso não haja uma opção de ligação direta para a origem-destino em questão, o usuário escolherá uma dentre as opções de ligações com uma transferência para seu trajeto. Caso não exista nenhuma opção com uma transferência, então ele escolherá uma dentre as opções que envolvem duas transferências. Se novamente não existir nenhuma opção, então a viagem é considerada não atendida.

Quando ocorrer mais de uma opção dentre as ligações diretas, o usuário escolherá uma rota com uma probabilidade proporcional à sua frequência de atendimento (frequency-based). Caso não haja uma ligação direta, mas existam mais de uma opção de trajetos com uma transferência, então a proporção é calculada aplicando-se um modelo logit multinomial (McFadden, 1973), sendo a

função utilidade Ui o custo generalizado da opção de trajeto em questão.

Como a frequência de operação depende da demanda, este processo será calculado através de iterações no processo de alocação, até que haja um equilíbrio na rede.

O modelo aplicado neste trabalho difere do aplicado em Afandizadeh et al. (2013), pois, no referido, os autores utilizam o tempo de viagem total. Em outros trabalhos são considerados apenas o tempo de viagem dentro do veículo, sem aplicar o modelo logit, como em Baaj e Mahmassani (1991) e Fan e Machemehl (2006).

Já neste trabalho, para cada opção concorrente de transporte entre dois pares de nós que exigem uma ou duas transferências, será calculado o custo

generalizado para cada opção (5.2), e a probabilidade de escolha da opção será resultado do modelo logit aplicado (5.1).

_∑

O custo generalizado de cada opção é calculado somando-se os custos relativos a uma opção de transporte, ou seja, o tempo total equivalente de viagem multiplicado pelo valor da hora do passageiro. Não se soma a tarifa do sistema pois não acarreta mudança na escolha de rotas, já que é a mesma para todas. É considerado um fator multiplicador do tempo de espera, pois este custa 1,7 vezes mais, em média, que o tempo de viagem dentro do veículo (Abrantes e Wardman, 2011). Para as transferências foi considerada uma penalidade fixa (valores na aplicação da Seção 6.1) além dos tempos de espera, como nos trabalhos revisados.

O pseudocódigo do algoritmo de alocação está resumido na Figura 5.9. Embora não conste no pseudocódigo por motivos de concisão, quando uma demanda é alocada, todos os parâmetros de tempo de espera total da rede, tempos de transferências, tempos dentro dos veículos e demandas totais de zero, uma e duas transferências são atualizadas.

O algoritmo de alocação exige iterações (passo 4), pois as frequências são atualizadas para atender as demandas das linhas, através da fórmula (5.3), afetando os tempos de espera dos trajetos. Essa mudança pode alterar a atratividade de cada opção, já que o custo generalizado reflete um alto tempo de espera acumulado. Foram consideradas duas iterações, já que a terceira não compensa o custo computacional, pois não ocorrem mudanças consideráveis nos valores das frequências.

Onde:

⁄

No pseudocódigo da Figura 5.9 são mencionados três métodos, a saber:

criaLigacoesDiretas (passo 3), criaLigacoes1Transfer (passo 16) e criaLigacoes2Transfer (passo 24). Esses métodos são chamados durante a

execução do algoritmo de alocação para preencher as estruturas de dados que contém todas as opções de trajetos entre cada par origem-destino.

Inicialmente, são calculadas todas as opções de trajetos diretos (passo 3 da Figura 5.9). Em seguida, Para cada par OD não nulo (passos 5 a 7) é procurada a disponibilidade de trajetos diretos para que seja alocada a demanda (passo 8). Caso exista mais de uma opção de trajeto direto, é aplicada a regra de frequência compartilhada entre os ônibus, gerando uma frequência equivalente (frequency-

based, passo 12).

Quando não existir trajetos diretos, o algoritmo chama o método que calcula as opções que exigem uma transferência do usuário (passo 16). Quando existirem mais de uma opção de transporte utilizando uma transferência, então é feito o cálculo da probabilidade de cada opção considerando o modelo logit e a utilidade de custo generalizado (passo 21).

Se nesse par OD não existir uma opção que exija uma transferência (passo 23), então é chamada a busca por opções que exigem duas transferências (passo 24). Caso não haja ligações com duas transferências para aquela demanda de par OD então é considerada uma demanda como não atendida.

Os métodos são chamados a cada par OD que necessita da informação, evitando-se um gasto computacional intenso para calcular todas as opções. Devido a sua importância dentro do modelo de alocação, os algoritmos de busca por opções de trajeto serão detalhados nas seções a seguir.

Quanto ao cálculo do tempo de espera, ele é calculado após cada atualização de carregamento e é feito da seguinte forma, conforme o tipo de trajeto do usuário:

 1 opção com 1 rota direta: metade do intervalo;

 2 ou mais opções com rotas diretas: metade do intervalo equivalente (soma das frequências de todas as linhas diretas);

 1 opção com 1 ou 2 transferências necessária: soma da metade dos intervalos de passagem das linhas na origem, no 1º e no 2º ponto de transferência;

 2 ou mais opções com 1 ou 2 transferências necessária: soma da metade dos intervalos equivalentes do conjunto de linhas da origem, das que servem o usuário no 1º ponto de transferência e das que servem o usuário no 2º ponto de transferência.