@MASTERSTHESIS\{IMM2004-03229,
    author       = "K. B. Bergvinsdottir",
    title        = "The genetic algorithm for solving the dial-a-ride problem",
    year         = "2004",
    keywords     = "Dial-a-Ride problem, meta-heuristic, combinatorial optimization, evolutionary algorithms, genetic algorithm, cluster-first, route-second, space-time nearest neighbour heuristic",
    school       = "Informatics and Mathematical Modelling, Technical University of Denmark, {DTU}",
    address      = "Richard Petersens Plads, Building 321, {DK-}2800 Kgs. Lyngby",
    type         = "",
    note         = "Supervised by Assoc. Prof. Jesper Larsen",
    url          = "http://www2.compute.dtu.dk/pubdb/pubs/3229-full.html",
    abstract     = "In this project the genetic algorithm (GA) is used to solve the dial-a-ride problem (DARP). In a dial-a-ride system customers are to be picked up and delivered within given time windows by a transportation vehicle. The aim is to minimize transportation cost and maximize the customer service level while satisfying the constraints.

The approach used to solve the {DARP} is the classical cluster-first, route-second strategy. That is, the customers are assigned to vehicles using a genetic algorithm and then a routing heuristic algorithm developed by Baugh et al. is used to make a route for each vehicle. The solution method is implemented in {JAVA} and tested on several randomly generated test problems. The test problems are taken from Cordeau and Laporte. Several improvement strategies to the initial solution method are proposed and the results from the best strategy are compared to the results obtained by Cordeau and Laporte.

In Danish:

I dette projekt er den genetiske algoritme (GA) brugt for at l{\o}se Dial-a-Ride Problemet (DARP). I {DARP} skal kunder hentes og afleveres af et transportmiddel indenfor givne tidsvinduer. Form{\aa}let er at minimere transport omkosninger og maximere kundeservice samtidigt med at holde begr{\ae}nsningerne.

Metoden der er brugt til at l{\o}se {DARP} er den klassiske cluster-f{\o}rst, rute-n{\ae}st strategi. I f{\o}rste omgang er den genetiske algoritme er brugt til at tildele kunder til transport midlerne og dern{\ae}st anvendes en rute algoritme lavet af Baugh et al. til at lave ruten til hvert transport middel. L{\o}sningsmetoden er implementeret i {JAVA} og testet med mange tilf{\ae}ldigt lavet test problemer. Test problemerne er lavet af Cordeau and La- porte. Nogle forbedringsstrategier bliver pr{\ae}senteret til den f{\o}rste l{\o}sningsmetode og resultaterne fra den bedste strategi bliver sammenlignet med resultaterne af Cordeau and Laporte."
}