Computational Complexity of Air Travel Planning [pdf] (2003)

The PDF was produced by ITA, which famously used Common Lisp:<p>* <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;ITA_Software" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;ITA_Software</a><p>From 2001, a message from the same author as the linked paper:<p>&gt; (Here&#x27;s an email Carl de Marcken of ITA Software sent to a friend, describing their experiences using Lisp in one of the software industry&#x27;s most demanding applications.)<p>* <a href="https:&#x2F;&#x2F;www.paulgraham.com&#x2F;carl.html" rel="nofollow">https:&#x2F;&#x2F;www.paulgraham.com&#x2F;carl.html</a>

This is well over 20 years old and is based on pre 9&#x2F;11 flight data. I would suspect that a lot has changed since then. So proceed with no caution at all.

This is a very popular article that get submitted every now and then (nearly every year) [1].<p>I think this kind of problem would be a very nice for logic, optimization and constraint programming that probably can be solved with modern tools like Google OR-Tool or Monash University MiniZinc [1],[2],[3].<p>[1] Past:<p><a href="https:&#x2F;&#x2F;hn.algolia.com&#x2F;?query=Computational%20Complexity%20of%20Air%20Travel%20Planning&amp;type=story&amp;dateRange=all&amp;sort=byDate&amp;storyText=false&amp;prefix&amp;page=0" rel="nofollow">https:&#x2F;&#x2F;hn.algolia.com&#x2F;?query=Computational%20Complexity%20o...</a><p>[2] Logic, Optimization, and Constraint Programming: A Fruitful Collaboration - John Hooker - CMU (2023) [video]:<p><a href="https:&#x2F;&#x2F;www.youtube.com&#x2F;live&#x2F;TknN8fCQvRk" rel="nofollow">https:&#x2F;&#x2F;www.youtube.com&#x2F;live&#x2F;TknN8fCQvRk</a><p>[3] Google OR-Tools:<p><a href="https:&#x2F;&#x2F;developers.google.com&#x2F;optimization" rel="nofollow">https:&#x2F;&#x2F;developers.google.com&#x2F;optimization</a><p>[4] MiniZinc:<p><a href="https:&#x2F;&#x2F;www.minizinc.org&#x2F;" rel="nofollow">https:&#x2F;&#x2F;www.minizinc.org&#x2F;</a>

A very interesting dive into, as the title says, the computational complexity of air travel planning. Graph algorithms with lots of complexity added due to the wide variety of fare conditions that airlines have dreamt up over the years.<p>The article may be from 2003 but I would call it an evergreen. While I imagine some of the details have changed since then, I suspect that the complexity has only grown since then.

Are there any public, open, comprehensive datasets on flights?

(2003)