1 Operations Research, Department of Informatics and Mathematical Modeling, Technical University of Denmark2 Department of Informatics and Mathematical Modeling, Technical University of Denmark3 Department of Transport, Technical University of Denmark4 unknown5 Department of Management Engineering, Technical University of Denmark
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.
Main Research Area:
Informatics and Mathematical Modelling, Technical University of Denmark, DTU, 2004