Solving the dial-a-ride problem with the firefly metaheuristic

Abstract

O problema Dial-a-ride (DARP) é um problema de otimização combinatória NP-difícil com aplicações práticas em transporte público orientado a usuário. O DARP é um problema de roteamento de veículos cujas instâncias consistem de um conjunto de veículos e um conjunto de solicitações para o embarque e desembarque de passageiros. Seu objetivo é atribuir as solicitações aos veículos e calcular as rotas de cada um destes, minimizando os custos operacionais e garantindo que todas as restrições, tais como capacidade dos veículos, janelas de tempo de partida e chegada, e tempo máximo de viagem do usuário, sejam obedecidas. Esse trabalho apresenta uma formulação matemática do problema e procura resolvê-lo através do Algoritmo Firefly (FA). O FA é uma nova meta-heurística baseada na natureza e inspirada no comportamento de vaga-lumes, que aplica o conceito de inteligência de enxame com o objetivo de otimizar funções matemáticas procurando por soluções quase ótimas. Com o auxílio dessa técnica nós visamos modelar e implementar um solucionador para o DARP que explore o enorme espaço de busca combinatorial, gerado pelas instâncias do problema, de uma maneira eficiente. Por fim, conduzimos uma comparação de desempenho entre o método proposto e os algoritmos encontrados na literatura científica, o que mostrou que o primeiro atinge um coeficiente de otimalidade de, em média, 90% para um conjunto de instâncias específico, e entrega, em alguns casos, resultados mais rápidos que aqueles entregues por um dos algoritmos da literatura.

The Dial-a-ride problem (DARP) is an NP-hard combinatorial optimization problem with practical applications in user-oriented public transportation. The DARP is a vehicle routing problem whose instances consist of a set of vehicles and a set of pick-up and drop-off requests from passengers. Its goal is to assign the requests to the vehicles and to calculate the routes of each one of them, minimizing the operation costs and ensuring that all the constraints, such as vehicle capacity, departure and arrival time windows, and maximal user ride time, are fulfilled. This work presents a mathematical formulation of the problem and seeks to solve it through the firefly algorithm (FA). The FA is a novel nature-based metaheuristic inspired by the behavior of fireflies, which applies the concept of swarm intelligence in order to optimize mathematical functions by looking for nearoptimal solutions. With the aid of this technique we aimed to model and implement a solver to the DARP which explores the huge combinatorial search space, generated by the problem instances, in an efficient way. Finally, we carried out a performance comparison between the proposed method and the algorithms found in the scientific literature, and found that the former achieves an average of 90% of optimality for a specific set of instances, and delivers, in some experiments, faster results than those delivered by one of the algorithms from the literature.

Das Dial-a-Ride-Problem ist ein NP-schweres kombinatorisches Optimierungsproblem, das bei benutzerorientiertem öffentlichen Personenverkehr Anwendung findet. Das DARP ist ein Tourenplanungsproblem, dessen Instanzen aus einer Menge von Fahrzeugen und einer Menge von von Fahrgästen eingetragenen Aufträgen zum Abholen und zum Absetzen bestehen. Sein Ziel ist es, den Fahrzeugen die Aufträge zuzuweisen und die Routen jedes Wagens zu berechnen, sodass die Betriebskosten minimiert werden und alle Nebenbedingungen, wie z.B. Fahrzeugnutzlast, Zeitfenster für Ein- und Ausstieg, maximale Fahrtdauer, erfüllt werden. Diese Arbeit stellt eine mathematische Formulierung des Problems vor und versucht, es durch den Einsatz des Firefly-Algorithmus (FA) zu lösen. Der FA ist eine neue naturbasierte Metaheuristik, die vom Verhalten von Glühwürmchen inspiriert ist und das Konzept von Schwarmintelligenz anwendet, um mathematische Funktionen zu optimieren, indem sie quasi-optimale Lösungen sucht. Anhand dieses Verfahrens hat diese Arbeit einen Löser des DARP modelliert und implementiert, der den riesigen kombinatorischen, von Probleminstanzen generierten Suchraum effizienterweise erforscht. Letztendlich wurde ein Leistungsvergleich zwischen der vorgeschlagenen Methode und den Algorithmen aus der wissenschaftlichen Literatur durchgeführt, der zeigte, dass die vorgeschlagene Methode einen Durchschnitt von 90% von Optimalität für eine bestimmte Menge von Instanzen erreicht und in einigen Experimenten schnellere Ergebnisse liefert, als die von einem der Algorithmen, die von der Lietratur stammen, gelieferten Ergebnisse.