Beta 1


Title The genetic algorithm for solving the dial-a-ride problem
Author Bergvinsdottir, Kristin Berg
Supervisor Larsen, Jesper (Department of Informatics and Mathematical Modeling, Technical University of Denmark, DTU, DK-2800 Kgs. Lyngby, Denmark)
Institution Technical University of Denmark, DTU, DK-2800 Kgs. Lyngby, Denmark
Thesis level Master's thesis
Year 2004
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øse Dial-a-Ride Problemet (DARP). I DARP skal kunder hentes og afleveres af et transportmiddel indenfor givne tidsvinduer. Formålet er at minimere transport omkosninger og maximere kundeservice samtidigt med at holde begrænsningerne. Metoden der er brugt til at løse DARP er den klassiske cluster-først, rute-næst strategi. I første omgang er den genetiske algoritme er brugt til at tildele kunder til transport midlerne og dernæst anvendes en rute algoritme lavet af Baugh et al. til at lave ruten til hvert transport middel. Løsningsmetoden er implementeret i JAVA og testet med mange tilfældigt lavet test problemer. Test problemerne er lavet af Cordeau and La- porte. Nogle forbedringsstrategier bliver præsenteret til den første løsningsmetode og resultaterne fra den bedste strategi bliver sammenlignet med resultaterne af Cordeau and Laporte.
Imprint Department of Informatics and Mathematical Modeling, Technical University of Denmark, DTU : DK-2800 Kgs. Lyngby, Denmark
Keywords Dial-a-Ride problem; meta-heuristic; combinatorial optimization; evolutionary algorithms; genetic algorithm; cluster-first; route-second; space-time nearest neighbour heuristic
Fulltext
Original Postscript imm3229.ps (2.26 MB)
Derived PDF imm3229.pdf (0.74 MB)
Admin Creation date: 2006-06-22    Update date: 2012-12-21    Source: dtu    ID: 154735    Original MXD