# Travelling Salesman problem- airport passport programs.

Discussion in 'Flight Following' started by Ozone, Jul 14, 2022.

1. ### OzonePre-takeoff checklist

Joined:
Aug 10, 2014
Messages:
174
Location:
Minnesota

Display name:
Ozone
A while back, I saw someone post maps of the traveling salesman problem as it pertains to completing various state passport programs like the MN passport program. Does anyone have those maps, or know if there's an online program or website that one could use?

2. ### donjohnstonPattern Altitude

Joined:
Aug 14, 2013
Messages:
2,018
Location:
Panama City, FL

Display name:
Don
What’s a “state passport”?

3. ### OzonePre-takeoff checklist

Joined:
Aug 10, 2014
Messages:
174
Location:
Minnesota

Display name:
Ozone
4. ### murpheyTouchdown! Greaser!PoA Supporter

Joined:
Aug 21, 2008
Messages:
11,130
Location:

Display name:
murphey
The original question was not about the state passport program, but as I understand it, a software program to help plan a trip to visit each airport. The traveling salesman problem is a classic we teach in 2nd semester CS - data structures and algorithms. This could be a fun project for my CS2 students this fall. To start, need the lat/long of each airport, then create a directed graph connecting all the airports, then let the TS program loose on it to create the most effective path.

https://www.javatpoint.com/discrete-mathematics-travelling-salesman-problem

By the way, by the time the software solves the problem, it’ll be irrelevant to you because it takes thousand of years with that many airports.

update after thinking more….no need for lat/long, just list of every airport with distance to every other airport. We got 72 in Coloraod, so that’s a HUGE list.

Last edited: Jul 15, 2022
5. ### PineconePattern Altitude

Joined:
May 24, 2022
Messages:
1,944
Location:
MD

Display name:
Pinecone
Only thing is, the traveling salesman problem assumes on long trip. I am pretty sure no one does all the airports in on single trip.

BTW MD and VA have the program also.

6. ### Rich HoltLine Up and Wait

Joined:
Jul 16, 2021
Messages:
646
Location:
SC

Display name:
holtyrd

7. ### WDDEn-Route

Joined:
Oct 16, 2019
Messages:
4,520
Location:
Atlanta / KRYY

Display name:
Vintage Snazzy (so my adult children say)
It's a simple sounding problem, but finding the solution is so complex the optimum solution can't be mathematically calculated / the true optimum solution can't be found.

8. ### OzonePre-takeoff checklist

Joined:
Aug 10, 2014
Messages:
174
Location:
Minnesota

Display name:
Ozone
Perhaps you could have your class start with ND. I have heard of several pilots who were able to to complete landing at all the airports in 1 week. Since there are fewer airports in ND, the starting point could be one airport that most people would enter the state in order to fly to all the airports.

For example, maybe most people start at Fargo (KFAR) and then exit a few days later at KBWP.

9. ### RussREn-Route

Joined:
Jan 12, 2011
Messages:
3,423
Location:
Oklahoma City, OK

Display name:
Russ
Years ago I hit all the airports in Delaware in one trip. Wasn't even a long one!

Sadly, they didn't have a passport program though.

10. ### Brad ZFinal ApproachPoA Supporter

Joined:
Dec 28, 2007
Messages:
6,705
Location:
Alexandria VA

Display name:
Actually, not distance, but time to every other airport, taking into consideration winds aloft and obstructions or airspace between the points. And adjustments for change in winds aloft over time.

Maybe a TLAR would be sufficient.

11. ### flyingronAdministratorManagement Council MemberPoA Supporter

Joined:
Jul 31, 2007
Messages:
23,047
Location:
Catawba, NC

Display name:
FlyingRon
It takes special clearance to get into three of the MD airports. There's one Virginia airport that you can't fly in yourself, but the stamp is there if you drive in (or fly in commercial).

12. ### Half FastTouchdown! Greaser!

Joined:
May 7, 2016
Messages:
11,000
Location:
Central Florida

Display name:
Half Fast

Yep, I recall that one from my Operations Research class.

There’s a different version,also, that IIRC we called a “shipping problem.” In that version, there are warehouses holding certain quantities of product and there are stores with certain demands. There are different costs for each warehouse to store route. The problem is to find a minimum cost solution that satisfies every store’s demand.

As a class assignment I had to write a program for it. It was a fun challenge.

13. ### EdFredTaxi to Parking

Joined:
Feb 25, 2005
Messages:
29,328
Location:
Michigan

Display name:
White Chocolate
If you're doing the trip a a Round Robin it actually sorts itself out rather easy if you sketch It Out by hand. You just want to make sure that no segments cross.

14. ### murpheyTouchdown! Greaser!PoA Supporter

Joined:
Aug 21, 2008
Messages:
11,130
Location:

Display name:
murphey
Avoiding crossing segments is the classic Bridges of Konigsberg problem.

Half Fast likes this.
15. ### MauleSkinnerTouchdown! Greaser!

Joined:
Oct 25, 2005
Messages:
13,824
Location:
Wichita, KS

Display name:
MauleSkinner
Is that why you never fight a land war in Asia? Or is it because the Sta Puft Marshmallow Man is afraid of bridges?

murphey and schmookeeg like this.
16. ### Jeff OslickEn-RoutePoA Supporter

Joined:
Mar 12, 2005
Messages:
4,998
Location:
Fullerton, CA

Display name:
Jeff Oslick
Based on my experience shipping high-priority items through FedEx in the last couple years, they haven't solved the problem.

What I have learned is that there is apparently a small black hole located somewhere in Indiana.

The existence of one in Memphis is well known.

FCAJR8630, TCABM, Jim K and 1 other person like this.
17. ### Half FastTouchdown! Greaser!

Joined:
May 7, 2016
Messages:
11,000
Location:
Central Florida

Display name:
Half Fast

Yep! My alma mater, Ga Tech, has a "Seven Bridges Plaza" on campus that is a model of the problem.

G-Man and murphey like this.
18. ### Half FastTouchdown! Greaser!

Joined:
May 7, 2016
Messages:
11,000
Location:
Central Florida

Display name:
Half Fast

"FedEx - When it absolutely positively has to be lost overnight."

"UPS - Even our name spells 'oops.'"

FCAJR8630 and murphey like this.
19. ### rwellner98Cleared for Takeoff

Joined:
Jul 26, 2009
Messages:
1,037

Display name:
rw2

20. ### NoHeatEn-Route

Joined:
Jul 27, 2009
Messages:
4,857
Location:
Iowa City, IA

Display name:
17
Why would it take thousands of years to visit 72 airports?

I’m sure I could do it in 72 days of flying, without any effort to optimize anything.

Edit - maybe you were talking about years of computational time?

Last edited: Jul 15, 2022
21. ### TabukaFiling Flight Plan

Joined:
Jan 19, 2017
Messages:
7

Display name:
Tabuka
Yes, it will take a long time to determine the optimal solution, not necessarily a feasible solution.

If you are willing to accept a solution that is no more than twice the optimum, an easy and efficient approximation scheme exists in this case. Airports would form a metric graph (distance between two airports is always less or equal to any other path between the two). Original paper was by Rosenkrantz et. al. but a simplified explanation can be found in many text books or notes.

Sorry can't post links, only second post.

Last edited: Jul 15, 2022
22. ### TabukaFiling Flight Plan

Joined:
Jan 19, 2017
Messages:
7

Display name:
Tabuka
Let me see if this works; replace dot with actual dot. www(dot)cs(dot)tufts(dot)edu/~cowen/advanced/2002/adv-lect3.pdf see section 2

Joined:
Apr 18, 2013
Messages:
3,702
Location:
The city of Townsville

Display name:
Mantis Toboggan, MD
Thanks for posting this. I'm a big fan of applied trajectory optimization. There might not be a closed-form solution for the global minimum but applied/approximation methods can get you close enough.

Nauga,
and the joke about the engineer and the beautiful woman

G-Man, Tabuka and Half Fast like this.
24. ### PineconePattern Altitude

Joined:
May 24, 2022
Messages:
1,944
Location:
MD

Display name:
Pinecone
Both VA and MD programs do NOT require you to fly into any of the airports. You could drive into every one.

VA also includes 4 aviation museums you need to visit.

mcdewey likes this.
25. ### Van JohnstonPattern Altitude

Joined:
Oct 31, 2012
Messages:
1,552
Location:
South Texas

Display name:
Van Johnston
One of my bucket list problems/trips: all Major League Baseball parks in a season by GA. Complicated by fact you have to be there when home team is in town. Further complicated by fact Canada doesn’t allow basic med.

26. ### Cap'n JackFinal Approach

Joined:
Jun 25, 2006
Messages:
8,660
Location:

Display name:
Cap'n Jack
It's NP-complete, so it can be calculated. It just might take a long time to find the optimum solution for a large number of points. For a small number of points, N = a few hundred or less, an optimum solution can be calculated in a reasonable time.

I've read that people can get within a few percent of the optimum solution if N < 20 or so.

27. ### iamtheariAdministratorManagement Council MemberPoA Supporter

Joined:
Mar 15, 2016
Messages:
3,899

Display name:
Ari
Like many CS problems, traveling salesman is trivial to solve across the set of all even primes. Solving it is also a subset of the dining philosophers problem, because all people ever do is think about it but nobody actually picks up the forks.

One of the interesting parts of solving it in this context is that an optimal solution will be three-dimensional, even if you assume no wind, constant weight, and airports as points rather than their own complex set of paths with entry and exit points and a route from each to the stamp. A proper solution should consider climb, cruise, descent, and the elevation of each airport, then tell me not only the order to visit all the airports but also what altitude to fly on each leg. It's not a different problem to solve, just a fun twist on the original.

28. ### Brad WPattern AltitudePoA Supporter

Joined:
Nov 19, 2019
Messages:
1,540
Location:
NE Florida

Display name:
BLW2
related I think, something I have been curious about. My car displays a range ring on the map....much like a glide range ring on an aviation GPS
Seems to be based on the guess-o-meter range number but adjusted a bit based on potential routes. It has an artificially generated wavy line border it seems, used as a baseline depiction of the guess-o-meter number and it's truncated for gross areas it can't go...like the Atlantic Ocean for example...the ring is clipped with a wavy line just off the beach.

Anyway, the thing I'd live to know more about is how it's calculating all the potential routes and points. Supposedly taking into account things like elevation but I'm convinced that it's not continually calculating every point and every possible route because when you zoom in there are some areas and roads that just don't make sense.....

29. ### Cap'n JackFinal Approach

Joined:
Jun 25, 2006
Messages:
8,660
Location:

Display name:
Cap'n Jack
What do you mean by "not difficult"?
• Just a slight addition of parameters to the original problem? It might be. The original problem could be "minimize the energy needed to complete a stop at every site", where energy expended per unit time was constant. This adds a difference in potential energy to each site.
• The problem as a whole isn't difficult to solve? No, but it takes more time as more points are added
• Mathematically not difficult? It's classified as "NP-hard" so depending an the number of points, it can take a long time to solve, as suggested by the point above this one.

nauga likes this.
30. ### Initial FixLine Up and Wait

Joined:
Jul 10, 2019
Messages:
621

Display name:
Initial Fix
I did this using excel for Missouri. It was fun learning some features I hadn’t used before. One of the harder parts was just finding a reliable source of public airport data. The sheet was one off and would take tinkering to work for other states.

#### Attached Files:

File size:
128 KB
Views:
20
NoHeat likes this.
31. ### iamtheariAdministratorManagement Council MemberPoA Supporter

Joined:
Mar 15, 2016
Messages:
3,899

Display name:
Ari
I said “not different, not “not difficult.” Meaning that the third dimension of doing it with airplanes is the same fundamental problem as the original from what I think was called CS240 when I took it. It’s just a matter of calculating optimum altitude between airport pairs (optimize for time, fuel consumption, or any other variable of your choosing) and then using the optimized variable instead of distance when you run your traveling salesman algorithm. Adding an O(n^2) step to an O(n!) algorithm isn’t that big of a deal. (Actually I think traveling salesman can be written faster than O(n!) but that doesn’t change my point. It’s just been a long time so I’m thinking in O(n!) terms for the sake of discussion.)

And, as I said, it’s trivial for the set of even primes, with a well-known algorithm that runs in O(1).

32. ### Cap'n JackFinal Approach

Joined:
Jun 25, 2006
Messages:
8,660
Location:

Display name:
Cap'n Jack
Yes, I misread it! My apologies!

33. ### iamtheariAdministratorManagement Council MemberPoA Supporter

Joined:
Mar 15, 2016
Messages:
3,899

Display name:
Ari
None needed. You gave me a chance to write a sentence consisting mostly of nots.

34. ### SaltyTouchdown! Greaser!

Joined:
Dec 21, 2016
Messages:
12,098
Location:
FL

Display name:
Salty
Lol

I ran a computation in a fairly fast computer for a couple of weeks and didn’t even hit a fraction of the combinations for the optimum state capitals flight plan and that’s only 50 points. I believe that’s ~3e64 combinations.

35. ### SaltyTouchdown! Greaser!

Joined:
Dec 21, 2016
Messages:
12,098
Location:
FL

Display name:
Salty
36. ### Cap'n JackFinal Approach

Joined:
Jun 25, 2006
Messages:
8,660
Location:

Display name:
Cap'n Jack
37. ### SinistarEn-Route

Joined:
Sep 9, 2016
Messages:
3,656

Display name:
An aside from the math:

Just found out during our EAA chapter meeting today that the MN DOT will no longer provide the Passport Booklets to airports where they can be left out or handed out Now they will need to be requested from the state. I can see why, but I have seen plenty of kids hop out of plane, walk into our outdated FBO, see that booklet and the stamper and think its pretty cool. Of course, every stamper we've had has been stolen LOL.

I did manage to get the KMSP stamp by actually flying in.

What makes the passport program more drawn out is actually having to full stop, shutdown, go into the building, find the stamp (if it hasn't been taken) and then start up again. Had touch and go counted, you could easily knock out 3-6 on any day except way north. Today, we also learned that a pilot's log entry with that airport also counts which helps with the stolen stamp and no booklets issue. A guy at our airport did a ton of flying over the past two years and I think he has them all except KMSP. Maybe he will get that last one on his IOE trip, that would be cool. I guess you get a nice jacket.

38. ### NoHeatEn-Route

Joined:
Jul 27, 2009
Messages:
4,857
Location:
Iowa City, IA

Display name:
17
Iowa has a program, too, run by a private organization, Fly Iowa, not the state government.

https://flyiowa.org/fly-iowa-challenge/

Over 100 airports, so it’s a big project to undertake, visiting all of them. No stamp, touch-and-goes allowed.

39. ### PineconePattern Altitude

Joined:
May 24, 2022
Messages:
1,944
Location:
MD

Display name:
Pinecone
And because of this, you aren't doing it in one day, unless it is Rhode Island or Delaware.

So you have the added issue of returning home after every few.

Joined:
Aug 21, 2008
Messages:
11,130
Location: