Construction heuristics for the airline taxi problem

Campbell, Ian Michael Dougal
Journal Title
Journal ISSN
Volume Title
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).