Take the 2-minute tour ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.

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.

share|improve this question
2  
Doesn't that conflict with the definition of a TSP? –  lynxlynxlynx Jul 13 '12 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 '12 at 22:18
    
Indeed. This is no TSP problem. But you are right in that the algo is pretty similar. –  Carsten Jul 14 '12 at 12:55

3 Answers 3

up vote 3 down vote accepted

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

share|improve this answer
    
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 '12 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 '12 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 '12 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.

share|improve this answer
    
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. –  lynxlynxlynx Jul 14 '12 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. –  Uffe Kousgaard Jul 15 '12 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.)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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