Construction heuristics for the airline taxi problem
Date
2014-02-12
Authors
Campbell, Ian Michael Dougal
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
A literature review of vehicle routing problems (VRPs) in general, and specifically
airline scheduling problems and the airline taxi problem, is provided. A real-world
airline taxi scheduling problem is described as experienced by a tourist airline oper-
ating in the Okavango Delta, Botswana. In this problem, a daily schedule is drawn
up manually by a team of experienced schedulers a few days before the day in ques-
tion. In this research, a slightly relaxed version of the problem is considered in order
to develop heuristics and modelling methods which will be useful for general cases.
Various methods and heuristics are proposed for the problem and tested on a small
version of the problem as well as the full-sized version. The most promising methods
are demonstrated and solutions provided. One of the methods was applied to the
actual problem to demonstrate the practical usefulness. In this case a schedule with
a cost 12% lower than the manual schedule cost was achieved. All the heuristics and
methods are applicable to certain other VRPs, particularly real-world or highly-
constrained VRPs. An example is provided of a solution method for a real-world
instance of the multi-vehicle capacitated vehicle routing problem (MVCVRP). An-
other example is provided of a standard, benchmark instance from the internet of a
capacitated vehicle routing problem with time windows (CVRPTW).