Solving the Dial-a-Ride Problem using Genetic algorithms |
|
| Abstract | 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. |
| Type | Technical report |
| Year | 2004 |
| Publisher | Informatics and Mathematical Modelling, Technical University of Denmark, DTU |
| Address | Richard Petersens Plads, Building 321, DK-2800 Kgs. Lyngby |
| Series | IMM-Technical report-2004-20 |
| Electronic version(s) | [pdf] [ps] |
| BibTeX data | [bibtex] |
| IMM Group(s) | Operations Research |