Modeling Airline Scheduling (Modeling Module)

The context for this Modeling Module is airline scheduling. It begins with a preliminary reading, Networks, which provides a brief introduction to graph theory and its application to a variety of networks. This is followed by a preliminary activity, Networks as Models, which revisits two of the networks discussed in the reading. The activity concludes with a modeling question: How can we model transportation with a network? Students analyze four transportation scenarios.

In Activity 1, Starting From Scratch – Setting Up Airline Routes, the situation is simplified by including only six airports. To further simplify the situation, the number of routes, m, is used as a measure proportional to airline costs, while the average number of legs for all possible journeys between airports, l, measures customer satisfaction. Students model airline routes with two networks: one that minimizes l, and the other that minimizes m. Toward the end of the activity, students begin working with weighted networks, where weights are related to travel time.

In Activity 2, the airport system is expanded from six to twelve airports. As a project, students create a network that is a compromise between a point‑to‑point model and a huband‑spoke model. Then they evaluate their model compared to a point‑to‑point model and a hub‑and‑spoke model.

The focus of Activity 3 is to find the shortest path between two nodes in a network. After finding the shortest path between two nodes in a small network, students are introduced to Dijkstra’s algorithm. They apply the algorithm to an airline network finding the path with the shortest travel time connecting two airports.

In Activity 4, given a schedule of flights, students determine the fewest number of planes needed to run this schedule. They model the schedule of flights using flights as nodes and links between flights that cannot use the same plane. Network coloring is applied, and a greedy coloring algorithm is introduced.