The University of Edinburgh -
Division of Informatics
Forrest Hill & 80 South Bridge

MSc Thesis #9907

Title:Vehicle Routing Problems with Time Windows
Date: 1999
Abstract:In vehicle routing problems with time windows there is typically a central depot with unlimited supplies, and a set of customer sites each of whom is expecting a delivery of some specified quantity of materials. There is a fleet of vehicles, each vehicle has a known capacity. The travelling distance between every pair of locations is known. In benchmark problems Euclidean distance is used and vehicles travel at constant speed. Each customer wants their own delivery to happen with a pre-specified time window. For example, supermarkets often hire casual labour for just two hours to help unload a large delivery and do not wish to pay overtime. The aim of this project is to study whether evolutionary methods can be usefully employed to solve such problems, for example to decide which heuristics to employ under which circumstances. A variety of more direct GA methods have already been investigated by Thangiah et al at Slippery Rock University. It will be important to compare the results of new approaches to existing ones. A collection of 56 non-trivial benchmark problems can be found at http://www.zpr.Uni-Koeln.DE/ABS/Projects/Optimization\\VehicleRouting/Links/dataset-links.html The site also has a useful bibliography and details of best known results for each problem. Although such benchmark problems are phrased in terms of vehicle routing, there are obvious analogues of such problems in a wide variety of commercial and military logistical tasks and so it will be useful to try to develop new methods of handling them effectively.

[Search These Pages] [DAI Home Page] [Comment]