Need algorithm suggestions for flight routings

Question

I'm in the early stages of thinking through a wild trip that involves visiting every commercial airport in India. A little research shows that the national carrier - Air India, has a special ticket called the Silver Pass that allows unlimited travel on their domestic network for 15 days. I would like to use this as my weapon of choice!

See this for a map of all the airports served by Air India

I have the following information available with me in Excel:

• All of the domestic flight routes (departure airports and arrival airports in IATA codes)
• Duration for every flight route
• Weekly frequency for every flight (not all flights run on all days of the week, for example)

Given this information, how do I figure out what is the maximum number of airports that I can hit in 15 days using the Silver Pass ticket? Looking online shows that this is either a traveling salesman problem or a graph traversal problem. What would you guys recommend that I look at to solve this.

Some background on myself - I'm just beginning to learn Python and would like to figure out a way to solve this problem using that. Given that, what are the python-based algorithms/libraries that I should be looking at that will help me structure an approach to solving this?

Answer 1

Your problem is closely related to the Hamiltonian Path problem and Traveling Salesman Problem, which are NP-Hard.

Given an instance of Hamiltonian Path Problem - build a flight data:

1. Each vertex is an airport
2. Each edge is a flight
3. All flights leave at the same time and takes the same time.(*)

(*)The flight duration and departure time [which are common for all] should be calculated so you will be able to visit all terminals only if you visit each terminal only once. It can be easily done in polynomial time. Assume we have a fixed time of k hours for the ticket, we construct the flight table such that each flight takes exactly k/(n-1) hours, and there is a flight every k/(n-1) hours as well¹ [remember all flights are at the same time].

It is easy to see that if and only if the graph has a hamiltonian path, you can use the ticket to visit al airports, since if we visit a certain airport twice in the path, we need at least n flights and the total time will be at least (k/(n-1)) * n > k, and we failed the time limit. [other way around is similar].

Thus your problem [for general case] is NP-Hard, and there is no known polynomial solution for it.

---

1: We assume it takes no time to pass between flights, this can be easily fixed by simply decreasing flight length by the time it takes to "jump" between two flights.