Airplanes and Gates
In class we have been studying bipartite graphs and perfect matchings. A perfect matching occurs when there are an equal number of nodes on each side of a bipartite graph and each node is connected by an edge to the node it is assigned, and no two nodes on the left are assigned to the same node on the right. One example of a real-life situation that should have perfect matchings is plane-gate matches. When a plane lands at an airport, it should have a gate to pull up to right after it touches down. However, as most of us have experienced, this is not always the case. In this article in USA Today, (http://travel.usatoday.com/experts/cox/story/2012-09-10/Ask-the-Captain-No-open-gate-after-landing-Why/57722552/1, pilot John Cox answers questions about why there are not always open gates after landing. He says that if a flight is late, the opening at a gate intended for that flight soon expires, because other flights need to take the gate next. As a result of flights getting late and not having gates to go to, a domino effect is created, which makes more flights have to wait for gate openings.
Perhaps, at a certain time, say 10 am, the plane-gate graph should look something like this:
It is not necessarily this simple, but in the graph above, each plane landing at that particular time has a gate to pull into. It is a perfect matching; this is how it is supposed to be. Each plane is supposed to have an open gate. However, when planes start to get late, like if A and B were to be late, at 10:30 am, the graph might look something like this:
Planes E and F were supposed to pull into gates 1 and 2 respectively, but because Planes A and B were late, they do not have anywhere to pull into. Now perhaps if gates 3 and 4 are open (which is unlikely), E and F can pull up to one of them. However, as the pilot explains in the article, changing the gate also alters the path of the luggage, the departure of outbound passengers, etc. This could cause more delays for other flights, and would cause at least some delay for the passengers on planes E and F. There is obviously no longer a perfect matching in the graph above because two of the planes do not have any place to go no matter what.
If planes A and B land after E and F, that will also be a big problem. A and B were supposed to have gates 1 and 2 at an earlier time, but their opening has expired. Again, two planes will have to wait or change gates and they don’t have anywhere to go.
We as passengers obviously get very frustrated when our plane does not pull up to a gate right away. However, after looking at these graphs, one can see that it is certainly not an easy task to schedule and plan these matches between planes and gates. When planes start to get late, ground control personnel have to measure the effects of changing gates.
Rmg232