Abstract
M.Sc.
This thesis investigates how intelligent agents can be used to solve airline scheduling
problems. It is divided into three parts. The first states what airline scheduling consists
of; the second discusses the results of a literature study; and the third consists of solutions
to the problem.
Airline scheduling consists of three major activities viz. market-driven flight generation,
crew assignment and operational problem management. The market schedulers first
create a flight set based on a forecast of passenger numbers and passenger preferences.
The crew schedulers attempt to crew the flights generated by the market schedulers
(subject to safety and rest regulations). The operational schedulers maintain the flights
from seven days prior to the day of operation to one day after the end of the flight.
Finding a global solution to this three-phase operation is the airline scheduling problem.
An agent-based solution to the airline scheduling problem was the focus of this thesis.
Agents encapsulate many useful artificial intelligence solution strategies. For the
proposed solution to the market driven scheduling problem a distributed negotiation
scheme using agents was used. A routing and an assignment agent were defined to assist
the crew scheduler. Finally an operational scheduling agent was defined to solve the
operational scheduling problem. The routing and assignment agents make use of FIFOqueues
and genetic algorithms. The operational scheduling agent makes use of a
traditional expert system combined with a learning algorithm to give it more flexibility.
A prototype, developed in Java, was used to demonstrate how agents could solve the
market driven scheduling problem. This distributed negotiation scheme was
implemented on Sun SPARC workstations running the Solaris operating system. A
prototype developed in Delphi was also developed to show how learning algorithms
could be applied to the scheduling environment.