search

google / or-tools

Google's Operations Research tools:
https://developers.google.com/optimization/
Apache License 2.0
11.12k stars 2.11k forks source link

v9.1 no longer work for CVRP with number of stops visited per each vehicle route #3121

Open qiannathancao opened 2 years ago

qiannathancao commented 2 years ago

What version of OR-Tools and what language are you using? v.9.1 vs v8.0.8283

Language: C++/Java/Python/C# Python

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

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

What did you do? Steps to reproduce the behavior: In order to limit vehicle stops per each route, I added the following code before setting the first solution heuristic.

    count_stop_callback = routing.RegisterUnaryTransitCallback(lambda index: 1)
    dimension_name = 'Counter'
    routing.AddDimension(count_stop_callback, 0, 45000, True, 'Counter')
    counter_dimension = routing.GetDimensionOrDie(dimension_name)

    for vehicle_id in range(data['num_vehicles']):
        index = routing.End(vehicle_id)
        solver = routing.solver()
        solver.Add(counter_dimension.CumulVar(index) <= data['stops'])

What did you expect to see Expect to the number of stops per route does not exceed the stops being set i.e. data['stops'] for example 5 stops maximum

What did you see instead? After upgrading the version to 9.0, the routing.SolveWithParameters(search_parameters) does not exit, it runs forever. However, after re-install version 8.0.8283, it is back to normal. Question is what has been changed could cause such confliction

Make sure you include information that can help us debug (full error message, model Proto).

Anything else we should know about your project / environment

lperron commented 2 years ago

Please provide a small reproducible example.

Mizux commented 2 years ago

  1. Why not using AddConstantDimension instead ? https://github.com/google/or-tools/blob/2cb85b4eead4c38e1c54b48044f92087cf165bce/ortools/constraint_solver/routing.h#L554-L570

  2. I'm not sure the problem is related to this constraint (which seems legit BTW). Routing team did lot of change (heuristic etc) so I suspect your problem to unfortunately work better with previous implem seed/setup etc...

Could you provide your search parameter setup ?

Also, did you enable log search ? guided local search and time limit ?