SetRange() doesn't work

[TeodoraB21]

Hello!

How is it possible that even if I set a timewindow for every node, for example for node 6 I set (5,10), but in the solution it says that it arrived at time 3 in node 6, which is not correct, because it is not in the interval (5,10)? I mean how is it even a solution, when it is not correct?

*I am using C++

[Mizux]

Do you have an example code and log to reproduce it ?

[TeodoraB21]

There are 9 stops, including the depot and 2 vehicles. This are the constraints:

demands = {0,1,3,2,1,3,1,4,1};
serviceTimes = {0,2,0,0,2,0,0,2,0};

(I don't think that the distance matrix matters). This is the transit time matrix:

0 1 2 5 2 5 2 5 4
1 0 3 3 5 4 2 5 7
2 3 0 5 7 4 5 2 5
5 3 5 0 4 5 5 4 3 
2 5 7 4 0 1 5 4 1
5 4 4 5 1 0 2 1 1
2 2 5 5 5 2 0 4 2
5 5 2 4 4 1 4 0 2
4 7 5 3 1 1 2 2 0

RoutingModel routing(data.GetLocations().size(), data.GetVehicleNumber(), data.GetDepot());

Distance distance(data);
routing.SetArcCostEvaluatorOfAllVehicles(NewPermanentCallback(&distance, &Distance::Run));

Demand demand(data);
std::vector<int64> vec;
vec.push_back(10);
vec.push_back(8);
routing.AddDimensionWithVehicleCapacity(NewPermanentCallback(&demand, &Demand::Run), 0, vec, false, "Capacities");

Service service(data);
Transit transits(data);
ServiceTimePlusTransition time(NewPermanentCallback(&service, &Service::Run),NewPermanentCallback(&transits, &Transit::Run));
routing.AddDimension(NewPermanentCallback(&time, &ServiceTimePlusTransition::Compute),24, 24, false, "Time");

const operations_research::RoutingDimension& time_dimension =routing.GetDimensionOrDie("Time");

time_dimension.CumulVar(1)->SetRange(0, 24);
time_dimension.CumulVar(2)->SetRange(2, 8);
time_dimension.CumulVar(3)->SetRange(4, 7);
time_dimension.CumulVar(4)->SetRange(0, 10);
time_dimension.CumulVar(5)->SetRange(8, 10);
time_dimension.CumulVar(6)->SetRange(5, 15);
time_dimension.CumulVar(7)->SetRange(10, 24);
time_dimension.CumulVar(8)->SetRange(0, 20);

RoutingSearchParameters searchParameters = RoutingModel::DefaultSearchParameters();
searchParameters.set_first_solution_strategy(FirstSolutionStrategy::AUTOMATIC);
const Assignment* solution = routing.SolveWithParameters(searchParameters);

And this is the output:

I0227 08:02:24.974375 17456 main.cpp:294] Objective: 48
I0227 08:02:24.975374 17456 main.cpp:298] Route for Vehicle 0:
I0227 08:02:24.976372 17456 main.cpp:315] 0 Time0(0..24) -> 
stop:2 arrivalTime:2 Time2(2..8) -> 
stop:3 arrivalTime:7 Time3(4..7) -> 
stop:1 arrivalTime:10 Time1(0..24) -> 
stop:7 arrivalTime:17 Time7(10..24) -> 
stop:0 arrivalTime:24
I0227 08:02:27.103351 17456 main.cpp:316] Distance of the route: 38m
I0227 08:02:27.103351 17456 main.cpp:298] Route for Vehicle 1:
I0227 08:02:27.104339 17456 main.cpp:315] 0 Time9(0..24) -> 
stop:6 arrivalTime:2 Time6(5..15) -> 
stop:5 arrivalTime:4 Time5(8..10) -> 
stop:4 arrivalTime:5 Time4(0..10) -> 
stop:8 arrivalTime:8 Time8(0..20) -> 
stop:0 arrivalTime:12

The problem is at the second vehicle: from point 0 to point 6 it takes 2 time units, so it arrives at 2, but is should arrive between 5 and 15. Same problem at point 5.

What do I do wrong?

[Mizux]

how did you print this, may I have your print function ? Also you should take a look at the SlackVar and look #1051

[TeodoraB21]

I found the problem. I set a possible waiting time for the vehicles. If I put it 0 the solution will be what I need. routing.AddDimension(NewPermanentCallback(&time, &ServiceTimePlusTransition::Compute),0, 24, false, "Time");

[Mizux]

note: your 0 here is the max value allowed for the SlackVar at each nodes...

[TeodoraB21]

I understand now that that slack_max (where I put at fisrt 24 and after 0), is the maximum waiting time that a vehicle can accumulate over the route. But why, if I set the slack range time for stop 0 it applies only for the first time stop 0 is used. stop 0 is the depot, so both vehicles start from here, and I want that both of them to don't wait.

time_dimension.SlackVar(0)->SetRange(0, 0); routing.AddToAssignment(time_dimension.SlackVar(0));

Route 0: 0 Load(0) Time(0, 0) Slack(0, 0) -> 2 Load(0) Time(2, 2) -> 3 Load(3) Time(7, 7) -> 1 Load(5) Time(10, 10) -> 7 Load(6) Time(17, 17) -> 0 Load(10) Time(24, 24) Route 1: 0 Load(0) Time(0, 0) -> 6 Load(0) Time(5, 7) -> 5 Load(1) Time(8, 9) -> 4 Load(4) Time(9, 10) -> 8 Load(5) Time(12, 20) -> 0 Load(6) Time(16, 24)

[Mizux]

1) In fact internally all vehicle have a start and end index different that's why you should use routing.Start(vehicle_index) and routing.End(vehicle_index), usually you have routing.Start(0) == 0 if depot is 0 but it's just a coincidence your code is "wrong"...

2) no slack_max is the maximum "waiting time" at EACH node not over the route...

[TeodoraB21]

Ok. But I still don't understand why the slack setting was applied only for route 0, and for route 1 not?

[Mizux]

don't get it, what do you mean by was applied only for route 0 ? In your previous log you don't print slack for other nodes so.

also your "wrong" code

time_dimension.SlackVar(0)->SetRange(0, 0);
routing.AddToAssignment(time_dimension.SlackVar(0));

is equivalent to

time_dimension.SlackVar(routing.Start(0))->SetRange(0, 0);
routing.AddToAssignment(time_dimension.SlackVar(routing.Start(0)));

so you only set a range for the start node of vehicle 0 not for the "depot" node

note: small sample, supposing you have:

routing(/*num_loc=*/4, /*num_vehicles=*/2, /*depot=*/0);

Then you'll have as index: node mapping:

0: start vehicle 0,i.e. routing.Start(0)
1: node 1
2: node 2
3: node 3
4: start vehicle 1 (duplicate of depot),i.e. routing.Start(1)
5: end vehicle 0 (duplicate of depot),i.e. routing.End(0)
6: end vehicle 1 (duplicate of depot),i.e. routing.End(1)

[TeodoraB21]

ok. I thought that with this time_dimension.SlackVar(0)->SetRange(0, 0) I set the waiting time in stop 0 to be 0, even if is used multiple times.

[Mizux]

Also beware that v6.10 API half use Index or NodeIndex in its API, in v7.0 (master branch) all API unconditionally use Index so you have to use manager.IndexToNode manager.NodeToIndex to convert IN/OUT but it's at least consistent.

[TeodoraB21]

Could you tell me please how do I set the slack for every stop individually? Because like this: time_dimension.SlackVar(i)->SetRange(a, b) doesn't work if there are multiple vehicles.

[Mizux]

you need two loops, one for the locations, one for starts. Please take a look at https://github.com/google/or-tools/blob/554cbccaa95b4c11eced13f145de1bf468e1f919/examples/python/cvrptw.py#L183-L199

[TeodoraB21]

thank you very much!