I know the TSP (traveling sales person) in osm2po is beta but it works quite well.

Is there a way to designate a final target location that is different from the initial source location. In other words, I would like to designate:

  1. Start location
  2. Several intermediate locations
  3. End location (different from start location)
  4. Determine the best way to begin at the Start location, travel to all the intermediate locations while hitting the End location last.

Currently, I see the TSP only does a round trip from an initial start location.

  • 2
    Doesn't that conflict with the definition of a TSP? Jul 13, 2012 at 22:16
  • Since osm2po isn't open source, the only one who can definitely answer your question is the author himself.
    – underdark
    Jul 13, 2012 at 22:18
  • Indeed. This is no TSP problem. But you are right in that the algo is pretty similar.
    – Carsten
    Jul 14, 2012 at 12:55

3 Answers 3


I've just modified osm2po-tsp. Now it should handle different sources and targets and intermediate vertices.

  • Thanks Carsten. Is the modified osm2po-tsp a new build or did you just overwrite some classes? How would I go about implementing this?
    – maw269
    Jul 16, 2012 at 17:56
  • Don't know why, but whuber deleted the answer to your question above. I can send you an in-between-version, which is close to final 4.5.0. Contact me via mail.
    – Carsten
    Jul 17, 2012 at 4:45
  • 1
    Received and working brilliantly! Just what I wanted. I think this will be a great addition to your next version.
    – maw269
    Jul 17, 2012 at 20:01

It can be done fairly easily be adding an artificial and additional node to the cost-matrix used by the TSP-optimization. The new elements in the matrix should have a "relevant" mix of values 0 and infinite to give the desired solution.

  • I don't know what osm2po uses, but if it solves the symetrical TSP, there is no guarantee the optimal path it finds will no start with the edge that he wants to be the last — after all, it will have a comparatively minimal cost assigned. Jul 14, 2012 at 19:36
  • If it is symmetrical, the whole sequence can just be swapped if wrong. We (www.routeware.dk) have had the above system working for a long time with several combinations of round-trip, open-ended and start-end optimizations for a long time with asymmetrical optimization. Jul 15, 2012 at 22:10

I think it is not necessary to add a ghost node to the matrix. All I have to do is to leave the last line (target / last node) with Max-Cost so it cannot act as source. The intrinsic TSP step which usually considers nodes [0, 1, 2, 3, 0 ] e.g. and permuts over [1, 2, 3] to avoid cycles just needs a small modification to [0, 1, 2, 3] and a permutation over [1, 2].

By the way: osm2po-tsp is indeed beta but works quite nice. Neither it uses nearest-neighbour heuristic nor uses lin2/3Opt or sth. like this. It is programmed straight forward and returns results close to optimum. It is useful for a small number of nodes (up to 12) but not more. To avoid buckling at more than 12 nodes It is necessare to use heuristics. One for populating the matrix (nearest neighbour) and another for the TSP itself (lin2/3Opt e.g.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.