Solving the Dial-a-Ride Problem using Genetic algorithms

Kristin Berg Bergvinsdottir, Jesper Larsen, Rene Munk Jørgensen

    Research output: Book/ReportReportResearch

    722 Downloads (Pure)

    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.
    Original languageEnglish
    Place of PublicationLyngby
    PublisherInformatics and Mathematical Modelling, Technical University of Denmark, DTU
    Publication statusPublished - 2004

    Cite this

    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