A tricky and lucrative problem has existed for decades in the airline industry that was ripe for a mathematician to solve. Given a set of criteria, what is the most efficient order in which to land airplanes during inclement weather?
Many obstacles arise when inclement weather strikes an airport. One of the biggest issues is the reshuffling of airplanes that need to be landed. When this inclement weather strikes, a Ground Delay Program is run which delays some flights from landing during the inclement weather, while others may even be canceled. This effort is called a Ground Delay Program. Once a Ground Delay Program has been run, there must be a new schedule in which the flights are landed, as some can no longer make the time slot for which they were originally assigned, while others could arrive much earlier. There are, however, legal issues; you cannot just take away an airline’s landing slot at an airport without a justified trade. The issues of efficiency and legal issues complicate this algorithm, and also make it a lucrative problem to be solved.
At this point you may be familiar with matching problems, but usually these matching problems, such as the stable marriage problem, deal only with two different groups with preferences. What if, as is the case here, there is a set of criteria that needs to be satisfied on top of the preferences? How do we consider factors such as the estimated time of arrival and the property rights of the airlines when coming up with an algorithm? James Schummer and Rakesh Vohra developed an algorithm that attempts to do just that. In this presentation, we’ll see the development of the model and how graph theory was creatively used to solve this problem.
Great presentation Nick. I like how you taught us about the compression algorithm and explained what was wrong with it, telling us the need for the TradeCycle Algorithm. The examples helped in understanding how the algorithms work with the airplane industry. I also like that you added the issue with the TradeCycle algorithm even though it did not involve mathematics. It is interesting that airlines purposefully do not tell of every cancelled flight so they can have higher priority when landing in inclement weather. It is all about the money and safety of their clients. Algorithms are not perfect and including the issues with each helped show this without going too much into detail. Your presentation was organized and easy to follow. Great job!
Hi Nick, great presentation! I thought it was really cool how you added in constraints and real-world “red tape” problems to make the example more realistic. Also, your introduction of both algorithms was easy to follow, and I appreciated the in depth conversation about the strengths and weaknesses of both. Nice Job!
I thought the presentation was really well formatted, organized and thought out. Last semester we got a killer presentation about airplane overbooking by Corey and you followed it up with another dynamite presentation about landing times. Really came full circle there, I only wish someone would now do a presentation about the aerodynamics of a plane. All around really well done, I may have got lost in the sauce a tad but this is something that is better when presented in person so I don’t hold that against you at all. Good luck in law school buddy!
Well done, this was a very technical and informational presentation! I found it interesting that airlines who understand the algorithm know that they cannot report flights in order to improve their position for a better slot. I wonder if in the future if the algorithm will be able to include a penalizing factor? That way, if an airline were to frequently not report canceled flights, it would affect their positioning to a worse slot in an effort to limit “slot destruction”. There seems to be a love of aviation topics in seminar as Jake pointed out, so maybe in the next seminar class, we should reach out to the creators of this algorithm, or an air traffic controller who has seen TradeCycle in action to see if they would be willing to chat with us?
Hello! I really enjoyed your presentation! Your topic was incredibly interesting, and I love how necessary and important solving this problem is, considering the business and legal implications. I think that it was really great that you went through the Compression Algorithm, pointed out some of its flaws, and then showed the advantages of the TradeCycle Algorithm. I’m so glad you included the video to explain the TradeCycle Algorithm. Your video was excellent and really helped explain how the algorithm works. Thank for the quick note about what a directed cycle is for those of us who didn’t take Graph Theory yet! Great job!
Hello. I like your topic and also like your presentation along with the real problem. Also, graph theory is used as a solution. It is interesting and made me motivated to study graph theory.
This really is one of the best seminar presentations I’ve seen. The topic is super cool and you put a ton of time into this. I’m glad you brought up potential problems with the algorithm. I like seeing when things can break down in math, especially with examples. This was really interesting to learn about. Really good job!
I love when algorithms get involved! Very neat topic (particularly since I covered an airplane-related topic last semester and find them interesting!). I appreciate the way you looked at this problem on a smaller scale than most airports function to show the gist of the algorithm. Obviously there are a lot of considerations to be made about flight cancelation and this seems very closely tied with one of the great unsolvable issues of computer science: the bin packing problem. We want to shove as much into a fixed size bin (schedule) with the greatest value within the bin. Right now this is an NP problem (cannot be solved with any determinate algorithm) but it can be estimated (with algorithms like you mentioned).
Good work!