Abstract
This thesis reports on research into the applicability of intelligent agents in the airline
scheduling environment. The methodology employed was to look at intelligent agent
research and then, based on this, to build models that can be used to solve some of the
airline scheduling problems.
The following was done:
· An agent-based model was developed that can assist airline schedulers in the
maintenance of a disrupted schedule. The agent model consists of a hybrid
approach combining elements of machine learning and expert systems.
· A multiagent model was developed that can generate a profitable and flyable
schedule. The multiagent model developed extends the traditional control
structures of the hierarchical agent organisation to a matrix structure. This
new model can be extended to any problem domain that deals with resource
allocation and capacity management.
To guide the thinking behind this research, a few questions were posed regarding the
problem to be solved:
Q1. Can intelligent agents play a role in the airline industry, with specific focus on
the scheduling creation and maintenance process?
Q2. What will the design of the agent models be if the scheduling needs of an
airline have to be addressed?
Q3. If the models as envisioned in question 2 can be created, what will the
practical implications be?
At a conceptual level the research produced three results:
R1. No references were found to multiagent technology in the production or
maintenance of airline schedules. This theoretical research into agent systems
shows that there is applicability in the scheduling environment, with specific
reference to schedule maintenance and generation.
R2. An agent model was created that combines declarative knowledge with
empirical learning to assist human schedulers in the day-to-day maintenanceof the schedule. Multiple solutions to a scheduling problem are generated by
the agent using embedded scheduling rules. The agent then uses the Qlearning
algorithm to learn the preferences of the human scheduler. This
approach combines the best of expert systems and machine learning.
To solve the problem of schedule generation, a multiagent system with a
matrix governance model was introduced. Aircraft and airports were
modelled as buying and selling agents. The business manager agent that
assigns individual aircrafts to specific routes was defined. This was
accomplished by matching individual aircraft capacity to origin-destination
demand. The agent model was then expanded to show how the inclusion of a
resource manager agent can handle system capacity management. This is a
matrix governance model, as an aircraft agent is managed by a business
manager agent, as well as by a resource manager agent. The initial results
from the prototype show that this model can generate profitable and flyable
schedules.
The multiagent model developed extends the traditional hierarchical agent
organisation to that of a matrix structure. The contract net protocol used for
typical multiagent coordination was adapted to work in this new control
structure. This new model can be extended to any problem domain that deals
with resource allocation and capacity management.
R3. A few airlines use expert systems to handle schedule disruptions. By
introducing machine learning, a flexibility is achieved that is currently not
available.
The approach proposed for schedule generation is not guaranteed to provide
optimal results like traditional operations research techniques, but it is useful
for high-level analysis, long-term planning, new hub or alliance planning and
research. It also has potential as a catalyst for integrated planning.
Keywords: Multiagent systems, airline scheduling
Ehlers, E.M., Prof.