Best or-tools TSP settings to achieve same result as OptaPlanner

[Nick Talbot]

Hi all,

I am investigating migrating a TSP solver from OptaPlanner to or-tools, and have been experimenting with a small graph of a depot at 21 locations, connected by symmetric links of 84 edges, i.e. not all nodes are connected to all other nodes (some links are forbidden/do't exist).

Our OptaPlanner implementation can get down to a 'cost' of 465 in a few seconds using Local Search / First Fit / Tabu type configuration.

I have tried several configurations for the or-tools version, such as different combinations as ROUTING_GUIDED_LOCAL_SEARCH / ROUTING_PATH_CHEAPEST_ARC or ROUTING_TABU_SEARCH / ROUTING_GLOBAL_CHEAPEST_ARC etc.

However, the best solution that the or-tools implementation has come up with is a higher cost of 571, and when the solution is visualised, it is clearly not as optimal as the OptaPlanner solution.

What are the 'best' set of or-tools Heuristic / First Solution Strategy configurations to get a good solution within e.g. 30 or 60 seconds? From what I've seen so far, I can't get or-tools to produce as good a result as from OptaPlanner.

Any tips?

Many thanks

Nick Talbot

[Vincent Furnon]

Hi Nick,

Did you try ROUTING_LOCAL_CHEAPEST_INSERTION, ROUTING_GLOBAL_CHEAPEST_INSERTION and ROUTING_SAVINGS as first solution heuristics ? Using guided local search with a time limit is a good idea.

How did you model forbidden links ?

Can you share your model ?

Vincent

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Nick Talbot]

Hi Vincent, thanks for the reply!

I took another look at my solution and it turned out I wasn't comparing apples with apples, in that I hadn't yet appreciated how to compute a TSP solution that had an undetermined finish point (as opposed to finishing at a specified end point).

Thankfully another forum post https://groups.google.com/forum/#!topic/or-tools-discuss/dpBlBDwQG4w gave me an inkling of how to code that (an extra dummy end depot with zero cost to get to it from all other nodes).

I've now moved onto trying to get Time WIndows to work correctly. I've defined a cumulative Dimension, but the solution doesn't seem to be working yet ...

I also found this detailed write up of the or-tools http://www.lia.disi.unibo.it/Staff/MicheleLombardi/or-tools-doc/user_manual/manual/TSP.html which is extremely helpful.

Thanks

Nick