algorithmtraveling-salesmanhamiltonian-cycle

TSP for a flights fares

I am trying to solve a Traveling-salesman problem with a flight fares, so main idea is to start from one Airport and visit all Airports only once and return to origin.

So for example: Starting from LAX Visit LV, CA, NY End LAX.

This is a classic graph problem where we can represent an Airport as Node and Route as Edge with a price as edge weights. enter image description here

So this is the easiest part, what is really confusing me is the dates that user wish to travel. For example I want to give user option to chose a dates that he/she wish to travel, say starting at 01 and finish 15. So I want to find a cheapest way how to do that. For example Output will be something like that:

01 - LAX - LV; 04 - LV - CA; 08 - CA - NY; 15 - NY - LAX

So I understand that I can put extra attributes on edges, but the question is how the algorithm will distinguish how to travers a graph, for example not choosing a edge with a least weight that is already in past. enter image description here

So you can see that I have a two edges coming out from CA (Note edges format is DD - price, 01 - 20 means 1st of the date and cost 20), and how to deal with this type of situation when multiple edges to same node present.

It also can be viewed as three dimension graph where third dimension is the date that user travels. So the main question is how to deal with those dates?

Hope I got to the point, any suggestions appreciated

Thanks with advance.

Solution

  • The way I understood your problem, you need the cheapest path which arrives before an specific time. If that's the case, one possible answer can be that you still solve it only based on the prices of the flights, and at the same time for each possible answer in the queue (I am assuming a method like Dijkstra) you keep that how much time has passed (for comparing with deadline).

    Whenever you want to add the neighbors of a possible answer you can check that if it is before the deadline and if it is not you ignore that instance.

    In summery you are still finding all possible paths from cheapest to the most expensive in order and you choose the first one which does not contradicts with your deadline.