Travelling Salesman problem- airport passport programs.

Ozone

Ozone

Pre-takeoff checklist
Joined
Aug 10, 2014
Messages
194
Location
Minnesota
Display Name
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?
 
Ozone said:
These are examples of the passport programs:

https://www.dot.state.mn.us/aero/aviationeducation/aviationpassport/passport.html

https://sdpilots.com/fly_sd.php

https://wisconsindot.gov/Pages/travel/air/pilot-info/flywi.aspx

https://www.flywashington.org/

Older article about many passport programs: https://www.aopa.org/news-and-media/all-news/2016/september/pilot/news-fly-your-state
Click to expand...
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:
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.
 
Rich Holt said:
I thought FedEx already had this problem solved.
Click to expand...
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.
 
murphey said:
...This could be a fun project for my CS2 students this fall...
Click to expand...

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.
 
Pinecone said:
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.
Click to expand...

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

Sadly, they didn't have a passport program though.
 
murphey said:
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.
Click to expand...

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.
 
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).
 
murphey said:
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.
Click to expand...



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.
 
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.
 
EdFred said:
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.
Click to expand...
Avoiding crossing segments is the classic Bridges of Konigsberg problem.
 
Rich Holt said:
I thought FedEx already had this problem solved.
Click to expand...

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.
 
Jeff Oslick said:
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.
Click to expand...


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

"UPS - Even our name spells 'oops.'"
 
murphey said:
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
Click to expand...

Here's the database you want: https://adip.faa.gov/agis/public/#/airportSearch/advanced
 
murphey said:
it takes thousand of years with that many airports … 72 in Coloraod, so that’s a HUGE list.
Click to expand...

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:
NoHeat said:
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?
Click to expand...

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:
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
 
@Tabuka: www.cs.tufts.edu/~cowen/advanced/2002/adv-lect3.pdf
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
 
flyingron said:
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).
Click to expand...

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.
 
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.
 
WDD said:
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.
Click to expand...
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.

EdFred said:
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.
Click to expand...
I've read that people can get within a few percent of the optimum solution if N < 20 or so.
 
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.
 
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.....
 
iamtheari said:
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.
Click to expand...
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.
 
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.
 

Attachments

  • 9959DE8A-3A0B-4DD0-ADF3-7C8CE04F9173.jpeg
    9959DE8A-3A0B-4DD0-ADF3-7C8CE04F9173.jpeg
    128 KB · Views: 20
Cap'n Jack said:
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.
Click to expand...
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). :)
 
iamtheari said:
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). :)
Click to expand...
Yes, I misread it! My apologies!
 
Cap'n Jack said:
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.
Click to expand...
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.
 
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.
 
Sinistar said:
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.
Click to expand...

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.
 
iamtheari said:
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.)
https://people.eecs.berkeley.edu/~vazirani/algorithms/chap6.pdf
And, as I said, it’s trivial for the set of even primes, with a well-known algorithm that runs in O(1). :)
Click to expand...
 
You must log in or register to reply here.
Back
Top