Optimization-based heuristics for vehicle routing and scheduling

Kilby, Philip John (1991). Optimization-based heuristics for vehicle routing and scheduling PhD Thesis, School of Physical Sciences, The University of Queensland. doi:10.14264/uql.2015.637

Attached Files (Some files may be inaccessible until you login with your UQ eSpace credentials)
Name Description MIMEType Size Downloads
THE7724.pdf Thesis (fulltext) application/pdf 2.87MB 1

Author Kilby, Philip John
Thesis Title Optimization-based heuristics for vehicle routing and scheduling
School, Centre or Institute School of Physical Sciences
Institution The University of Queensland
DOI 10.14264/uql.2015.637
Publication date 1991
Thesis type PhD Thesis
Supervisor John Holt
Total pages 157
Language eng
Subjects 01 Mathematical Sciences
Formatted abstract
This thesis is concerned with the problem of finding routes for a fleet of vehicles which must make deliveries to a number of customers at various locations. If temporal aspects are also involved, such as customers specifying the range of times when they will accept delivery, or the goods being produced before delivery can begin, there is also a scheduling component to the problem.

At present, exact algorithms cannot be used on a day-to-day basis for large problems of this type, as they require too much processing time. In this thesis we investigate methods which, although heuristic, are based on exact methods. Such methods offer hope of finding good, quick solutions to these problems. 

Research is centred on two types of problem. The first area of study concerns problems where the vehicles are only subject to capacity constraints. A new algorithm called PETAL, based on exactly solving a modified Assignment Problem, is suggested for this problem. This algorithm is described and compared with other algorithms from the literature. The PETAL algorithm performs well when compared with these algorithms.

The second area of study is in the situation where customers specify acceptable times for delivery, and where the product is being produced immediately before delivery. Such problems arise, for example in the delivery of newspapers. This is a relatively new area of research, and a full introduction is given. The only existing algorithm for this problem, developed by a number of researchers including the author, is described. A new algorithm based on Set Partitioning is introduced, and extended to incorporate column generation. The two algorithms are compared, with results that encourage further work on the Set Partitioning algorithm.
Keyword Transportation -- Mathematical models

Document type: Thesis
Collection: UQ Theses (RHD) - UQ staff and students only
Citation counts: Google Scholar Search Google Scholar
Created: Fri, 30 Jan 2015, 14:52:35 EST by Mary-Anne Marrington on behalf of Scholarly Communication and Digitisation Service