What commercial flight route needs the most (min poss.) stops from A to B? | Hacker News Reader

What commercial flight route needs the most (min poss.) stops from A to B?

travel.stackexchange.com

It depends on when you do the query. Years ago (mid 2000s) at ITA, Carl wrote code to find the longest possible shortest route between any two airports with scheduled flights. At the time the winner was Wasu, New Guinea to Peawanuck, Ontario, which took a minimum of 90 hours and many flights. There are airports you can only get to at the end of a long line of stops; this drives the number of stops way up.

Slightly unrelated, but you can book flights between Seattle (SEA) and Everett (PAE), and there's a PAE-LAS-SFO-SEA route that takes 20 hours.

These two Airports are only 37 miles away from each other. There's a shuttle between them that takes 75 minutes.

It looks like Alaska will sell you tickets for PAE to SEA via any one of SFO, LAS, LAX, PHX...

Yes, it's a popular 'mileage-run' route. Aka a flight routing that frequent flyers take solely for the purposes of gaining more miles/status

In a decade there will be a light rail that is even faster than the shuttle! (Between Everett and SeaTac or the city)

Back about 1980, I took a flight from the Washington, DC, Metro area to Denver. My recollection is that we took off from BWI, stopped at Dulles, and continued on via Des Moines. But BWI to Dulles is nearer 60 miles, I think.

In that era, many airlines were still operating much as they had in the regulated era - without a fully developed hub-and-spoke system. So service to a lot of smaller airports wasn't directly back to a hub; you got on at some point in a series of stops and they did very brief layovers to take on or debark passengers.

ICAO four-letter airport codes are hierarchical. The first one or two letters indicate the country, e.g.:

EDDF - Frankfurt (E: Northern Europe, D: Germany)

EKCH - Copenhagen (E: Northern Europe, K: Denmark)

VTBS - Bangkok (V: South/Southeast Asia, T: Thailand)

KJFK - New York JFK (K: USA)

Using ICAO codes, you can make sense of a written out route at a glance. Taking one of the examples from the link:

AUY TAH VLI BNE BKK CPH SFJ JAV JUV NAQ

becomes

NVVA NVVW NVVV YBBN VTBS EKCH BGSF BGJN BGUK BGQQ

I.e.: Vanuatu (a few jumps) -> Australia -> Thailand -> Denmark -> Greenland (a few jumps).

Make a connectedness matrix of airports x airports with 1 marking a connection and 0 marking no connection. You can now iterate over legs by multiplying the matrix with itself. Do this until all values in the matrix are zero. The previous iteration shows a 1 where the longest routes are.

What is this part of graph theory called, and are there similar insights from doing elementary operations on adjacency matrices?

I don't know what this part of graph theory is called but I noticed in college that this is taught in the graph theory class from the mathematics department but not in the graph theory class from the computer science department.

If the graph is an undirected graph the adjacency matrix is symmetric. People study the eigenvalue spectrum; the largest eigenvalue is bounded by the highest degree of a vertex in the graph.

Algebraic graph theory

Subfield: Spectral graph theory

https://en.m.wikipedia.org/wiki/Algebraic_graph_theory

As for adjacency matrices -- consider the (oriented) vertex-edge incidence matrix D (vertices x edges, each edge is a column, head is +1 and tail is -1, other entries are zero). Then D and D' (transpose) both have interpretations (stop and think about them; they're like gradient and divergence), as does L = D D' (graph Laplacian).

This also generalizes from graphs to simplicial complexes (triangles, tetrahedra). And "connected components" of graphs generalize to higher homology groups (loops, voids):

https://pi.math.cornell.edu/~hatcher/AT/AT.pdf

Great idea but two typos.

Multiplying the adjacency matrix by itself gives the number of walks of a specified length. Therefore you would keep multiplying the matrix by itself until all values are nonzero. Then the previous iteration shows a zero where the longest routes are.

Shows it’s been a while… :)

This is now obsolete question, because of technical progress. Just now all change.

Economically, most cost effective route one hop, without additional landings. And also, it is very big hassle, to manage all passengers and their luggage in hub, and all these transfers are time consuming and tiresome.

~15 years ago, unfortunately, only largest planes (747/380) could fly any route in one hop, but smaller (ie 737) could not. And all air transport economy built with concept of "hub world" - existed several big hubs, like Frankfurt, between them flight big planes, and to reach smaller airports, used small planes or some other transport.

Also important thing, air companies in past have to maintain good relations with hubs, so this was also question of politics and big pain for business.

But then appeared new small planes with much better fuel efficiency (787 and new modification of A-3xx, sorry forgot exact number), plus changed regulations accepted two-engined planes fly farther from reserve airport, so now any airport reachable with small plane and hubs concept slow dissolve.

Sure, still exist number of rare visited places, where just very few tourists appear, but for now their place in "post-hub world" is "under construction", nobody could predict how things will change in nearest months.

Back when airline status was based on number of segments this would have been a useful tool if you could find the lowest cost route on a single airline group. For example "find the most number of segments at the lowest cost per segment using only One World flights"

My first thought was the Guam Island Hoper between Guam and Honolulu at 7 airports.

[added] 8 if you add MNL (Manila) on arrival to Guam

https://en.wikipedia.org/wiki/Island_Hopper

You are looking for the airport pair with the highest number of minimum hops required to get between them.

Guam and Honolulu both have direct flights to Seoul so it’s not a great example.

Is there a flight db preferably with price info?

Reply on news.ycombinator.com