Two hub location problems for transportation systems

Abstract

Redes do tipo eixo-raio são normalmente utilizadas em sistemas de transporte com o intuito de rotear eficientemente commodities e passageiros entre vários pares de origem e destino. Duas variações do problema de localização de concentradores são propostas. Programas inteiros mistos são apresentados e resolvidos através de métodos exatos e heurísticos. O primeiro problema estudado propoem o desenho da malha aérea global, com base na localização de gateways em redes do tipo eixo-raio, diferenciando passageiros domésticos e internacionais. Uma formulação de programação inteira mista é desenvolvida e dois algoritmos baseados no métodos de decomposição de Benders são implementados para resolver o problema. Enquanto a versão monolítica não consegue resolver instâncias médias dentro de um tempo máximo, os algoritmos propostos são capazes de resolver instâncias maiores em um tempo razoável. A segunda variação do problema de localização de concentradores estudado otimiza o desenho de uma rede de transporte genérica considerando rotas flexíveis. Nessa versão, além de localizar nós concentradores e alocar nós não-concentradores a nós concentradores, as rotas dos veículos são definidas. Enquanto a maioria dos estudos até então presentes na literatura consideram um fator de desconto fixo para representar economias de escala em links entre hubs e uma topologia específica para as redes, esse trabalho introduz uma formulação inteira mista, em que economias de escalas dependem da tecnologia de transporte escolhida para operar as rotas e a topologia da rede é determinada endogenamente. Duas metaheurísticas são implementadas para achar boas soluções para o problema em tempos computacionais razoáveis.