24

Given a list of cities and the cost to fly between each city, I am trying to find the cheapest itinerary that visits all of these cities. I am currently using a MATLAB solution to find the cheapest route, but I'd now like to modify the algorithm to allow the following:

  1. repeat nodes - repeat nodes should be allowed, since travelling via hub cities can often result in a cheaper route
  2. dynamic edge weights - return/round-trip flights have a different (usually lower) cost to two equivalent one-way flights

For now, I am ignoring the issue of flight dates and assuming that it is possible to travel from any city to any other city.

Does anyone have any ideas how to solve this problem? My first idea was to use an evolutionary optimisation method like GA or ACO to solve point 2, and simply adjust the edge weights when evaluating the objective function based on whether the itinerary contains return/round-trip flights, but perhaps somebody else has a better idea.

(Note: I am using MATLAB, but I am not specifically looking for coded solutions, more just high-level ideas about what algorithms can be used.)

Edit - after thinking about this some more, allowing "repeat nodes" seems to be too loose of a constraint. We could further constrain the problem so that, although nodes can be repeatedly visited, each directed edge can only be visited at most once. It seems reasonable to ignore any itineraries which include the same flight in the same direction more than once.

del
  • 6,341
  • 10
  • 42
  • 45
  • Your description of "dynamic edge weights" just sounds like directed edges with different weights in each direction. – Matt Ball Mar 12 '11 at 04:39
  • @Matt - Not sure I understand. Let's say one-way flights are $50 in each direction, or a return flight is $60. What would the weights be in each direction? – del Mar 12 '11 at 04:47
  • By "return flight," do you mean a round-trip ticket? (I think that's a British-ism). If so, you could create this by having the two vertices connected by multiple paths ($50 each way ones, and $30 each way) if you have some way to enforce that, for the second path (round-trip tickets), if the outgoing $30 path is taken then the incoming $30 one must also be taken. – Matt Ball Mar 12 '11 at 04:51
  • Yes, I meant round-trip. I didn't realise "return trip" is a British term, I have edited the question to clarify. – del Mar 12 '11 at 04:55
  • 2
    And the "separated by a common language" cliche finds another victim... :) – dappawit Mar 12 '11 at 06:39
  • To find a good fit, you can also use "modest node" and define the maximum distance, or minimum distance to travel. It can help you algorithm "breath" more and to find the best solution quicker. Another option to speed the process up is to name nodes as strings (lets say alphabetically) and run permutation algorithm, where permutation differences can be expressed as differences in lenght. – Cninroh Mar 29 '11 at 11:09
  • Repeat nodes (or missing edges) doesn't change the hardness of TSP. Just replace the cost of the edge between any two cities with the minimum cost of any path between them (adding a label so you can print the path latter) – hugomg May 03 '11 at 16:41
  • @missingno This does not work because that interferes with "dynamic edge weights" – Albert Hendriks Jul 16 '11 at 20:42
  • If you're only doing this for around 15 cities like you said in a comment to one of the answers, just use brute force. Try each possible itinerary and see which one has the smallest cost. – Gravity Jul 23 '11 at 02:18

6 Answers6

5

I haven't tested it myself; however, I have read that implementing Simulated Annealing to solve the TSP (or variants of it) can produce excellent results. The key point here is that Simulated Annealing is very easy to implement and requires minimal tweaking, while approximation algorithms can take much longer to implement and are probably more error prone. Skiena also has a page dedicated to specific TSP solvers.

ldog
  • 11,707
  • 10
  • 54
  • 70
  • 1
    I've tested it with an ACO-algorithm and is a bit like gambling. Mostly it can produce good result but it's not guaranteed while christofides is always withn the 3/2 optimum. But you are right christofides is very expensive to implement and there is no open-source solution. – Micromega Mar 14 '11 at 18:06
0

If you want the cost of the solution produced by the algorithm is within 3/2 of the optimum then you want the Christofides algorithm. ACO and GA don't have a guaranteed cost.

Micromega
  • 12,486
  • 7
  • 35
  • 72
  • 2
    @epitaph- Can you apply Christofides here? We're not guaranteed that the triangle inequality holds. – templatetypedef Mar 13 '11 at 05:31
  • @templatetypedef: I don't have any formal cs or math degree so I'm just guessing: OP is not looking for code and why is http://en.wikipedia.org/wiki/Triangle_inequality not working with return flights? I can construct a MST with a round-trip and still looking for triangle inequality? The other problem is to find a triangle inequality because this is very expensive! – Micromega Mar 14 '11 at 17:58
  • The triangle equality must hold to use Christofides because TSP without the triangle inequality is NP-hard to approximate within any constant factor. Without that guarantee, Christofides is not guaranteed to give a good result. – templatetypedef Mar 14 '11 at 18:22
  • @templatetypedef: Do you repeat Christofides or Wikipedia here? I did christofides? – Micromega Mar 14 '11 at 18:26
  • I'm not sure I understand what you're saying. My argument is that because we don't know that the triangle inequality holds in the original setup, even ignoring the round-trip costs, Christofides cannot be applied here because it makes strong assumptions about the edge costs. – templatetypedef Mar 14 '11 at 18:33
  • @templatetyped: In mathematics, the triangle inequality states that for any triangle, the sum of the lengths of any two sides must be greater than the length of the remaining side. That is exploited by Prof. Christofides to find a perfect matching in a non-bipartite graph. And also a double-MST is already the double of the tsp optimum. – Micromega Mar 14 '11 at 19:34
  • I understand this and how the Christofides algorithm works, that's not the concern here. My concern is that in this particular problem description, we don't know that the distances in the input graph satisfy the triangle inequality. This means that while the Christofides algorithm itself is perfectly fine (it's actually one of my favorite algorithms!), it won't work in this case because it assumes that the triangle inequality holds in the input graph, though in this problem the input graph doesn't necessarily obey the triangle inequality. – templatetypedef Mar 14 '11 at 19:36
  • I'm a bit lost here. I already wrote that I can construct a MST with round trips and still searching for a triangle inequality to further improve the solution? Do you want me to withdraw my answer? After all OP it doesn't look for code and mabye he should ask this question to cstheory.stackoverflow? – Micromega Mar 14 '11 at 20:10
  • AH... I completely misinterpreted what you said. Sorry about that - we were arguing completely different questions! Don't take down this answer! However, can you elaborate a bit on how you construct the MST with round-trips and how you'd use that to find a solution? This is an interesting idea, but right now it's buried in these comments. :-) – templatetypedef Mar 14 '11 at 20:13
  • I use Prim's algorithm and also pushing different weights into a map for a roundtrip shouldn't be that though. Then I double the MST and I use the Fleury algorithm to find a Euler-Path. That's for the double-MST. – Micromega Mar 14 '11 at 20:33
  • Correct me if I'm wrong, but if you don't have that the triangle inequality holds in the initial graph, doesn't this approach not give you any bounds on how good of an approximation this is? – templatetypedef Mar 14 '11 at 20:35
  • Actually I'm not talking about finding a bound with the triangle ineqeuality. And also I can't see how you can construct a relationship between the "initial graph" and the triangle inequality. – Micromega Mar 14 '11 at 20:47
  • The triangle equality as applied to graphs means that if you have edges uv, vw, and uw, then l(uv) + l(vw) <= l(uw). If the weights in the initial graph satisfy this relation, then the input graph satisfies the triangle inequality. But independently of this, is there any guarantee that the MST-based solution will have any bearing on the optimum solution? – templatetypedef Mar 14 '11 at 20:48
  • LOL! I know that the double-MST is double the optimal solution because I brute-force the solution. But in wikipedia there is another equation from Pythagoras... It seems to me you know this already before. – Micromega Mar 14 '11 at 21:00
0

Firstly, what is approximate number of cities in your problem set? (Up to 100? More than 100?) I have a fair bit of experience with GA (not ACO), and like epitaph says, it has a bit of gambling aspect. For some input, it might stop at a brutally inefficient solution. So, what I have done in the past is to use GA as the first option, compare the answer to some lower bound, and if that seems to be "way off", then run a second (usually a less efficient) algorithm.

Of course, I used plenty of terms that were not standard, so let us make sure that we agree what they would be in this context:

  1. lower bound - of course, in this case, MST would be a lower bound.
  2. "Way Off" - If triangle inequality holds, then an upper bound is UB = 2 * MST. A good "way off" in this context would be 2 * UB.
  3. Second algorithm - In this case, both a linear programming based approach and Christofides would be good choices.
Josh
  • 189
  • 12
  • 1
    It would be less than 100 cities. Currently I'm experimenting with around 15. Could you give any further clarification as to why linear programming or Christofides are good choices for this problem? Do they allow repeat nodes and dynamic weights? – del Mar 27 '11 at 14:31
  • I'm not others, my name is epitaph. Thank you for answer! – Micromega Mar 29 '11 at 13:21
  • @epitaph: Fixed that! (Obviously, I should read the names better) – Josh Mar 30 '11 at 22:40
  • Thanks, mate. Sorry for the downvote. Too bad OP isn't give the bounty! What do you think of user templatetypedef? Isn't it a bizarr discussion? – Micromega Mar 31 '11 at 10:01
0

Solving the TSP is a NP-hard problem for its subcycles elimination constraints, if you remove any of them (for your hub cities) you just make the problem easier.

But watch out: TSP has similarities with association problem in the meaning that you could obtain non-valid itineraries like:

Cities: New York, Boston, Dallas, Toronto

Path:

Boston - New York New York - Boston

Dallas - Toronto Toronto - Dallas

which is clearly wrong since we don't go across all cities.

The subcycle elimination constraints serve just to this purpose. Including a 'hub city' sounds like you need to add weights to the point and make an hybrid between flux problems and tsp problems. Sounds pretty hard but the first try may be: eliminate the subcycles constraints relative to your hub cities (and leave all the others). You can then link the subcycles obtained for the hub cities together.

Good luck

Marco A.
  • 43,032
  • 26
  • 132
  • 246
0

If you limit the problem to round-trips (i.e. the salesman can only buy round-trip tickets), then it can be represented by an undirected graph, and the problem boils down to finding the minimum spanning tree, which can be done efficiently.

In the general case I don't know of a clever way to use efficient algorithms; GA or similar might be a good way to go.

mitchus
  • 4,677
  • 3
  • 35
  • 70
  • Good idea, but I am looking for a more general solution that doesn't constrain the itinerary to round-trips. – del May 05 '11 at 09:42
  • Ok. In any case I advise you not to think of your problem as a TSP, because it is so far removed from the original TSP that I really doubt you can carry any useful techniques over. – mitchus May 05 '11 at 13:23
0

Do you want a near-optimal solution, or do you want the optimal solution?

For the optimal solution, there's still good ol' brute force. Due to requirement 1 involving repeat nodes, you'll have to make sure you search breadth-first, not dept-first. Otherwise you can end up in an infinite loop. You can slowly drop all routes that exceed your current minimum until all routes are exhausted and the minimal route is discovered.

Amish Programmer
  • 2,051
  • 3
  • 19
  • 22
  • I'm looking for a near-optimal solution. Take a look at the extra constraint I added to the end of my question - each flight can only be taken once (i.e. each directed edge of the graph can only be traversed once), so neither BFS nor DFS will result in an infinite loop. – del Jul 21 '11 at 04:26