Options for Trip plugin brute force search

[danpat]

Currently, the trip plugin performs a brute force search for up to 10 coordinates, then switches to a farthest insertion heuristic.

There are some exact solutions to the TSP (e.g. https://en.wikipedia.org/wiki/Held%E2%80%93Karp_algorithm) that could offer exact solutions for more coordinates with the same time bounds.

We should do some investigation to see if there are some easy wins here, including:

• implementing other algorithms
• pulling in third-party solver libraries

10 coordinates is useful, but small. If we could double, or triple that, 30 coordinates has a bunch of real-world use cases and it'd be nice to offer exact solutions.

/cc @oxidase @chaupow

[oxidase]

Some improvement can be achieved by using an upper bound for the initial weight and lower bound in branching. An exampleTsp.txt with 1-tree bound for data from http://www.math.uwaterloo.ca/tsp/world/countries.html#WI wsahara.txt djibuty.txt

It is usable for up to 30~40 nodes for symmetric graphs. For asymmetric graphs some heuristic can be applied to make graph symmetric (it will not work for one-directional edges) or the graph can be converted to symmetric one by duplicating nodes, but it will reduce usability to ~15-20 nodes.

[HGuillemet]

Explicit choice of the algorithm used via parameters would be nice, instead of the arbitrary threshold of 10. I understand that this can lead to easy DoS, but there are situations (private routing server) where you won't mind spending a couple of seconds finding the exact solution.

Maybe a compilation option allowing to change the threshold would be better.

[daniel-j-h]

What you could do is make the brute-force threshold a engine-wide limit. Follow the max_locations_trip limit and add the threshold:

• https://github.com/Project-OSRM/osrm-backend/blob/59b70c4d1113956f9351c344ad616cd71be9c930/include/engine/engine_config.hpp#L85
• https://github.com/Project-OSRM/osrm-backend/blob/59b70c4d1113956f9351c344ad616cd71be9c930/include/engine/plugins/trip.hpp#L31
• https://github.com/Project-OSRM/osrm-backend/blob/master/src/engine/plugins/trip.cpp#L241
• https://github.com/Project-OSRM/osrm-backend/blob/59b70c4d1113956f9351c344ad616cd71be9c930/src/tools/routed.cpp#L110

then you can check it in the trip plugin.

By the way @HGuillemet just leaving this here - https://github.com/mapbox/node-or-tools

[danpat]

Given that the brute-force search is O(N!), I don't expect you'll be able to change the limit very much - we picked 10 because it's still "fast" (<1 second), but I'm pretty sure it's in the minutes range by 13, and the hours by 15 or 16.