Osrm-backend: [Trip Plugin] Computing round trips with fixed start and end point

[chaupow]

It should be possible to set a fixed start and end point when computing roundtrip.

i.e.
A round trip that starts at location A and ends at location B and on the way other locations C, D, E, F, ... should be visited is needed. Currently the trip plugin does not support this. It should.

Implementation detail:

It should work when the distance between A and B is set to zero in the distance table.
This is not planned before osrm v4.8.0

[jcoupey]

Depending on your heuristic behaviour, setting a cost of 0 from B to A won't necessary be sufficient to ensure that B will be placed just before A in the TSP solution.
But also adding an artificially huge cost from any other point to A should do the trick, this is how I implemented it myself.

[JMGGarcia]

Hey! Is there any plan of implementing this in the future? I think it's an important feature that should exist.

[daniel-j-h]

No plans for the near future; ticket is open to track the feature.

[chaupow]

@ghoshkaj and me drafted an idea to implement this. Here's a write down of our plan as well as a failed attempt to have a formal proof but I think this could count as an unformal proof:

Given:

• _n_ points {A, B, C, D, ....}
• a distance table with distances between all of these points

Wanted:

A shortest trip that

• visits all points {A, B, C, D, ...}
• starts at A and ends at B

Claim:

• We merge the two nodes A and B to a single node BA
• We create a new distance table with
  
  
  
  • any distances from BA to another node being the distance from A to another node:
    
    dist(BA, X) = dist(A, X)
  
  
  • any distances to BA from another node being the distance from the other node to B:
    
    dist(X, BA) = dist(X, B)
  
  
• Having an algorithm _ALG_ that correctly computes the traveling salesman for the points
  {BA, C, D, ...}, we can find a solution for our problem by splitting BA in the solution
  
  
  
  • e.g. if a round trip BA → C → D → BA is a shortest roundtrip, the actual route is A → C → D → B → A
  
  

Explanation

Any solution to our problem starts at A and ends at B. As we look for a roundtrip, the trip from B to A always exist. Thus, the travel B → A is fixed.

Thus, it only has to be decided in which order all the other nodes have to be visited. And algorithm that minimizes the distance of the route visiting all nodes and also going from A to other nodes and
from other nodes going to B, also minimizes the roundtrip that we are looking for.

[tomduffey]

i have the same interest in this enhancement to trip functionality - the ability to have a fixed start and end location - i am following Trip with Fixed Start and End points(TFSE) #3408 - any news would be helpful

[huntw999]

this will help to have fixed start and fixed end point that is different - i will continue to look for an update thank you

[jcoupey]

For the record, this is how I "cheat" on the matrix to use my usual TSP solving approach in the case of an open tour:

https://github.com/VROOM-Project/vroom/blob/master/src/structures/tsp.cpp#L32-L62

Rather than creating a new BA node, I basically just set dist(B, A) to 0 and any other distance from B to a value that make it impossible to go anywhere other than A from B. Benefits of this approach is that there is no other modification on code and data. In particular this doesn't mess with cost computations as the usual evaluation during TSP solving will return consistent costs in the case of open tours.

Also the same kind of trick allows to set start only and let the optimization phase decide what should be the preferred ending point, and same way around for fixing only end point.

Hope this can help!

[ghoshkaj]

@jcoupey we ended up going with your suggestion as it was easier to manipulate the table that way! It's done and just got merged in! Closing this now.

It will be released with the next release :)

[jcoupey]

@ghoshkaj thanks for the follow-up, glad this worked for you too!