Solving the Dial-a-Ride Problem using Genetic algorithms

AbstractIn 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.
TypeTechnical report
PublisherInformatics and Mathematical Modelling, Technical University of Denmark, DTU
AddressRichard Petersens Plads, Building 321, DK-2800 Kgs. Lyngby
SeriesIMM-Technical report-2004-20
Electronic version(s)[pdf] [ps]
BibTeX data [bibtex]
IMM Group(s)Operations Research