Solving the dial-a-ride problem using iterated local serach

Abstract

The Dial-a-Ride Problem (DARP) is an NP-hard combinatorial problem. The DARP is a variant of the Vehicle Routing Problem (VRP), focusing in the transportation of passengers. It consists in, given a set of requests for pick-up and delivery requested by users and a set of homogeneous vehicle, optimize the assignment of requests to vehicles in order to serve all requests, providing optimal routes and respecting problem constraints such as route duration, vehicle capacity, passenger ride time, departure and arrival time windows. This work presents an approach to DARP using the Iterated Local Search (ILS) metaheuristic, which has been successfully applied in solving other variants of the VRP. The goal of this work was to evaluate the suitability of ILS in the context of DARP. For that, a comparison between obtained results and the ones found in the literature was presented and indicated promising results.

O Dial-a-Ride Problem (DARP) é um problema combinacional NP-difícil. O DARP é uma variante do Vehicle Routing Problem (VRP), focando no transporte de passageiros. O problema consiste em, dado um conjunto de requisições de coleta e entrega feitas por usuários e um conjunto de veículos idênticos, otimizar a atribuição de requisições a veículos com objetivo de atender todas as requisições, produzindo rotas ótimas e respeitando limitações impostas pelo problema, como capacidade máxima dos veículos, tempo máximo de rota de um passageiro e janelas de tempo no embarque e desembarque. Este trabalho apresenta uma abordagem para o DARP utilizando a metaheurística Iterated Local Search (ILS), que tem sido aplicada com sucesso na resolução de outras variantes do VRP. O objetivo desse trabalho foi avaliar a adequação do ILS ao contexto do DARP. Para isso, comparações entre resultados obtidos e resultados disponíveis na literatura foram realizadas e indicaram resultados promissores.