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

demarcken.org

72 points·chollida1··9 comments

I found that last page with the BOS-HNL-LAX-PWM-BOS circle query really fascinating for a couple of different reasons: 1) the fact that ITA could already do this in 2003, and 12 years later, most flight search engines still can't handle that kind of query, and 2) that a very similar itinerary today is less than half the price[1].

(As a side note, how awesome is it that you can deep-link to a specific fare on Google Flights?)

[1] https://www.google.de/flights/?gl=US#search;iti=BOS_HNL_2015...

You mean like this?

https://www.hipmunk.com/flights#f0=BOS;t0=HNL;d0=2015-02-11;...

Doesn't hipmunk use ITA's routing engine?

Yes, they do.

Neat to see the graphical presentation of flight options (page 38) that would presumably evolve into Hipmunk seven years later.

That sort of graphing of time intervals goes back at least to the Gantt chart:

http://en.wikipedia.org/wiki/Gantt_chart

Maybe Hipmunk saw the one in the presentation, but it wouldn't be surprising if they had not.

The website they built is called ITA Matrix (http://matrix.itasoftware.com) and it's still available today even after Google acquired them. It's the most powerful flight search engine out there.

And it's written in Lisp!

Please fix typo in title to 'design'

Reply on news.ycombinator.com