Ortools RoutingModel not finding best solution to a VRP in a 14-node example

[Geoff Leyland]

Hi,

We're using or-tools to solve a multi-depot Vehicle Routing Problem. Occasionally we notice that it gives us a solution that looks a little suboptimal, but the problems we're solving are large enough that it's hard to tell by eye.

After some time, we've managed to find a 4-depot, 14-node (that is, ten nodes to visit) problem that displays this behaviour. We've also managed to distill the code required to show the problem down to about 100loc.

The code is at available at: https://gist.github.com/geoffleyland/a2e721091207aa98f9a6aa5920c8e194

I'm using a freshly-compiled version of or-tools from git HEAD:

$ git log
commit 9a299d7fae511a8d906b8c5535e2a5761182c694
Author: Laurent Perron <lpe...@google.com>
Date: Fri Sep 8 13:58:10 2017 +0200

minor improvement to internal comments

which was compiled on OS X (10.12.6) with clang (Apple LLVM version 8.1.0 (clang-802.0.42)). The test code was compiled with the following command-line:

c++ -std=c++11 -o ortools_vrp_4_depots_14_stops ortools_vrp_4_depots_14_stops.cpp -I/usr/local/include/or-tools -lortools


The code solves the problem three times:
- the first time, using the distance matrix as shown in the code. It obtains an optimal distance of 12409m, in which vehicles 0, 2 and 3 are used.

- we then swap the first two rows and columns of the distance matrix (essentially changing the ordering of the depots) and re-solve, obtaining a better distance of 11567m (842m less), and using all of the vehicles

- finally we swap back and run again, as a safety check, obtaining the same solution as the first run (as expected)


In the second solution the vehicle in row 0 gets the most work, but since we swapped, this is vehicle 1 from the previous solution. That is, the vehicle that gets most of the work in the better of the two solutions gets no work in the worse of the two.


We think that we should obtain the same solution regardless of the ordering of the depots in the distance matrix, and would appreciate any help spotting any deficiencies in our code, as we feel like we're running short of options we haven't explored.


If it's helpful, we have:
- tried a number of RoutingSearchParameters, but we haven't managed to make a difference, hence they are not shown in the code.
- made the distance matrix symmetric (as shown it is not) by coping the upper triangle. This didn't make a difference either.
- changed the order in which we specified the depots in the depots vector passed to the RoutingModel constructor. Nor did this make a difference.


As I said, we'd appreciate any help working out what's up.

Warm Regards,
Geoff

[Vincent Furnon]

Have you tried Parallel Cheapest Insertion as first solution heuristic. I get a cost of 11567 in all cases with it. Note that we are going to release a version of the Savings algorithm which is multi-depot aware and will behave well too (and might be faster).

--
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-discuss+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Geoff Leyland]

Bonjour Vincent!

On Tuesday, 12 September 2017 11:54:35 UTC+12, Vincent Furnon wrote:

Have you tried Parallel Cheapest Insertion as first solution heuristic. I get a cost of 11567 in all cases with it. Note that we are going to release a version of the Savings algorithm which is multi-depot aware and will behave well too (and might be faster).

Thanks!  That works in my test code, but it took a while to get it working in our "actual" code.  The problem turned out to be that we call R.CloseModel() before the solve, and when you do this in the example, it doesn't work either.  I've updated the gist at https://gist.github.com/geoffleyland/a2e721091207aa98f9a6aa5920c8e194 to reflect the new code (Calling set_first_solution_strategy and CloseModel).

Am I using CloseModel wrong?  We pass an initial solution to the VRP, and as I understood it, I need to call CloseModel before I build the initial assignment from my representation of the initial solution, and in order to pass an initial solution to SolveFromAssignmentWithParameters.

I'm a little uncomfortable that the quality of the solutions we obtain in small problems is dependent on the initial solution heuristic.  I'd feel better if there was a solution involving search parameters.  In the actual code I had GLOBAL_CHEAPEST_ARC as the first solution heuristic (now changed, thanks!), and use full_path_lns, relocate_neighbours, path_lns, tsp_opt, tsp_lns, extended_swap_active, make_active, and GUIDED_LOCAL_SEARCH - basically everything we could find, because things are solving fast enough.  But I wonder if, if I'm using CloseModel incorrectly, whether any of this has an effect?

While you're there, if I may, is there a good way of estimating the number of vehicles needed to perform all the work in a VRP?  We have "depots" in several locations, but can operate over several days.  We first solve a simplified version of the problem (homogeneous vehicle costs) with far too many days to see how many days we need, and then solve the "full" problem with only the days we need.  Solving the two problems is quicker than solving the full problem with too many days, but I suspect there's something smarter to do.

Merci beaucoup de ton aide!

Geoff

[Geoff Leyland]

Sorry to reply to myself, but...

On Tuesday, 12 September 2017 12:23:00 UTC+12, Geoff Leyland wrote:

Bonjour Vincent!

Am I using CloseModel wrong?  We pass an initial solution to the VRP, and as I understood it, I need to call CloseModel before I build the initial assignment from my representation of the initial solution, and in order to pass an initial solution to SolveFromAssignmentWithParameters.

I just read the docs, and for the first time saw CloseModelWithParameters.  Sorry for the noise, and I apologise for not reading them as I wrote!

 

[Vincent Furnon]

I agree with you that it'd be better if local search found the proper solution whatever the first solution strategy was. We'll investigate, In any case I wouldn't recommend GLOBAL_CHEAPEST_ARC as it's in general slower and less effective than PathCheapestAddition, Savings or the Insertion heuristics.

As for estimating the number of vehicles, what type of constraints do you have (I didn't see any in the code you shared)? In any case your approach is interesting. If you have capacity constraints you might want to size the fleet based on demands vs capacity + some slack.

--

[Vincent Furnon]

BTW activating guided local search also leads to the optimal solution - you might want to try that out too (with a time limit). 

[Geoff Leyland]

> On 12/09/2017, at 12:45 PM, 'Vincent Furnon' via or-tools-discuss <or-tools...@googlegroups.com> wrote:
>
> BTW activating guided local search also leads to the optimal solution - you might want to try that out too (with a time limit).

Yes, it does! Thanks. Now that I've worked out how to use CloseModelWithParameters, suddenly all of those parameters are making a real difference (and, as you say, some are a bit slow).

> I agree with you that it'd be better if local search found the proper solution whatever the first solution strategy was. We'll investigate, In any case I wouldn't recommend GLOBAL_CHEAPEST_ARC as it's in general slower and less effective than PathCheapestAddition, Savings or the Insertion heuristics.

As above, and as you know, they do work, when you turn them on properly.

> As for estimating the number of vehicles, what type of constraints do you have (I didn't see any in the code you shared)? In any case your approach is interesting. If you have capacity constraints you might want to size the fleet based on demands vs capacity + some slack.

We're writing tools to plan field operations for the coming 2018 Census of New Zealand. One of the operations happens a couple of weeks after the census and involves field officers visiting every dwelling in the country that hasn't yet responded.

In this operation, field officers start and end at their homes each day, and work four hours a day, work is counted from arriving at the first dwelling they visit to leaving the last they visit. The operation has a fixed number of field officers, but runs until Statistics NZ are satisfied with the response. For modelling purposes, this means until we've visited all of the dwellings. So, we know the number of vehicles, we know the hours per day, but we don't know how many days.

We minimise travel distance + distortions. The distortions are things we've added to the objective to try to get the routes "nice for field officers". Some of these distortions lead to heterogenous arc costs for the field officers.

Solving with a large number of days with heterogeneous arc costs proved a bit slow, hence the current approach: solve the problem with no cost to and from work, heterogeneous arc costs and the correct time constraint (so all the officers look exactly the same) with too many days to estimate days required, and then solve the full problem with a tight constraint on days.