In the Dial-a-Ride problem (DARP) customers send transportation requests to an operator. A request consists of a specified pickup location and destination location along with a desired departure or arrival time and demand. The aim of DARP is to minimize transportation cost while satisfying customer service level constraints (Quality of Service). In this paper we present a genetic algorithm for solving the DARP. The algorithm is based on the classical cluster-first route-second approach, where it alternates between assigning customers to vehicles using a genetic algorithm and solving independent routing problems for the vehicles using a routing heuristic. The algorithm is implemented in Java and tested on publicly available data sets.
|Place of Publication||Lyngby|
|Publisher||Informatics and Mathematical Modelling, Technical University of Denmark, DTU|
|Publication status||Published - 2004|
Bergvinsdottir, K. B., Larsen, J., & Jørgensen, R. M. (2004). Solving the Dial-a-Ride Problem using Genetic algorithms. Informatics and Mathematical Modelling, Technical University of Denmark, DTU. http://www.imm.dtu.dk/pubdb/p.php?3395