Possible regression with routing solver with v9.5

[ankane]

Hi, congrats on the 9.5 release! Think I may have found a regression with the routing solver.

What version of OR-Tools and what language are you using? Version: v9.5 Language: Python

Which solver are you using (e.g. CP-SAT, Routing Solver, GLOP, BOP, Gurobi) Routing Solver

What operating system (Linux, Windows, ...) and version? macOS 13

What did you do?

Ran the VRP example: https://developers.google.com/optimization/routing/vrp#entire_program1

What did you expect to see Maximum of the route distances: 1552m (like previous versions)

What did you see instead? Maximum of the route distances: 1712m

[ankane]

I'm seeing errors with that example for v9.4 and v9.3, but with v9.2, the output is:

Objective: 161408
Route for vehicle 0:
 0 ->  8 ->  6 ->  2 ->  5 -> 0
Distance of the route: 1552m

Route for vehicle 1:
 0 ->  7 ->  1 ->  4 ->  3 -> 0
Distance of the route: 1552m

Route for vehicle 2:
 0 ->  9 ->  10 ->  16 ->  14 -> 0
Distance of the route: 1552m

Route for vehicle 3:
 0 ->  12 ->  11 ->  15 ->  13 -> 0
Distance of the route: 1552m

Maximum of the route distances: 1552m

For v9.5, the output is:

Objective: 177500
Route for vehicle 0:
 0 ->  9 ->  10 ->  2 ->  6 ->  5 -> 0
Distance of the route: 1712m

Route for vehicle 1:
 0 ->  16 ->  14 ->  8 -> 0
Distance of the route: 1484m

Route for vehicle 2:
 0 ->  7 ->  1 ->  4 ->  3 -> 0
Distance of the route: 1552m

Route for vehicle 3:
 0 ->  13 ->  15 ->  11 ->  12 -> 0
Distance of the route: 1552m

Maximum of the route distances: 1712m

[Regista6]

Just wanted to leave this here. With v9.4 I'm getting the correct output (1552m) but 1712m with v9.5 on Windows (C++)!.

[Mizux]

confirmed, the initial solution found by the first solution strategy PATH_CHEAPEST_ARC is a little bit odd.

just add in python:

    search_parameters.local_search_metaheuristic = (
        routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)
    search_parameters.time_limit.FromSeconds(1)

output:

 Objective: 161408
Route for vehicle 0:
 0 ->  8 ->  2 ->  6 ->  5 -> 0
Distance of the route: 1552m

Route for vehicle 1:
 0 ->  9 ->  10 ->  16 ->  14 -> 0
Distance of the route: 1552m

Route for vehicle 2:
 0 ->  1 ->  4 ->  3 ->  7 -> 0
Distance of the route: 1552m

Route for vehicle 3:
 0 ->  13 ->  15 ->  11 ->  12 -> 0
Distance of the route: 1552m

Maximum of the route distances: 1552m

Note: in this example we didn't want to introduce the GLS yet, so maybe will update the doc accordingly. Also now we can see the improvement of the GLS over the first solution strategy's initial solution ;0

[Regista6]

Enabling the solver log (only Path_Cheap_Arc), it seems both v9.4 and v9.5 start with Relocate and Cross operators. However, v9.4 ends with TwoOpt, and v9.5 ends with RelocateExpensiveChain.

Edit: Not entirely related to v9.5, but it seems versions >v9.1 produce output 98 min on vrp_resource whereas v9.1 produces the displayed output of 90 min.

[Mizux]

note: AFAIK team worked on a dynamic sorting of operator/validator per complexity (ed 3 bins of set of operators) aka less complex validator are checked first (with the last failed first kind of LRU stuff) in order to improve the validation speed thus the search speed thus the solver should be able to explore more research space... note2: IIRC the default operator list has been tweaked also (need to add a note to the release note -_-)

[ankane]

Thanks @Mizux, can confirm that fixes it.