Avaliação da abordagem de leilões no roteamento dinâmico para operação de transporte responsivo à demanda

Abstract

A atratividade do transporte público é drasticamente reduzida para usuários distantes dos centros de distribuição. Esse problema, conhecido como Last Mile Problem, pode ter seu efeito reduzido através de sistemas de transporte veicular sob demanda. Contudo, métodos exatos para cálculo das rotas de tais veículos são geralmente ineficientes perante cenários de alta escala e dinâmicos, onde os pedidos de transporte ocorrem durante a operação. Esse trabalho investiga o problema de roteamento dinâmico de veículos usando coordenação descentralizada baseada em leilões. O objetivo é reduzir a insatisfação dos clientes, quantizada a partir da espera média por atendimento e tempo médio de viagem, enquanto também reduz-se o custo de operação da frota, avaliada como proporcional ao tempo de uso dos veículos. As rotas criadas através da abordagem de leilões são comparadas com o ótimo em cenários diversos. Os resultados indicam que a abordagem desenvolvida é capaz de gerar bons resultados em tempo de processamento reduzido, principalmente quando há uma frota veicular sobre-ajustada. Estudos com cenários maiores e comparações com outros métodos de roteamento são indicados para melhor avaliação.

Abstract: The attractiveness of public transport is dramatically reduced for users far from distribution centers. This problem, known as Last Mile Problem, can have its effect reduced through on-demand vehicular transport systems. However, exact methods for calculating the routes of such vehicles are generally inefficient in the face of large scale and dynamic scenarios where transport requests occur during operation. This paper investigates the problem of dynamic vehicle routing using decentralized auction-based coordination. The goal is to reduce customer dissatisfaction, quantified from the average waiting for service and average travel time, while also reducing the cost of operating the fleet, assessed as proportional to the time of use of vehicles. Routes created through the auction approach are compared to optimal in various scenarios. The results indicate that the developed approach is able to generate good results in reduced processing time, especially when there is an over-adjusted vehicle fleet. Studies with larger scenarios and comparisons with other routing methods are indicated for further evaluation.