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.