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:
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?
A: The airline's flight dispatch office will look at the most-efficient route. The selection of the route can include the mileage, wind and cost of over-flight permits. Based on these criteria the answer to your question would be because it is the most cost-efficient.
They display airways that connect any two places you need to go. Airways are designed to keep air traffic organized and separated. An airline dispatcher uses a computer to help analyze the weather and winds between the origin and destination. He or she then determines the most economic route using the airway system.
Route planning is dictated by a range of factors including weather, geopolitics, how much a country charges for aircraft to fly over its territory, and even runway length.
A routing is a sequence of flight covered by a single airplane. A rotation is a routing that starts and ends at the same location. Each airplane has to visit a maintenance station at regular intervals. Maintenance are performed in several airports called base at night.
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:
(*)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 well1 [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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With