Routing: Dimension with slack and evaluator = 0 vs evaluator != 0 #4531
Description
What version of OR-Tools and what language are you using?
Version: main (9.11.4210)
Language: Python
Which solver are you using
Routing Solver
What operating system?
Ubuntu 22.04.4 LTS
Definition of the problem
The problem consists of stops with deliveries and depots for pick-ups, each vehicle has a different capacity, and they can refill the depot when necessary to continue.
To avoid the problem of returning to the depot, X copies of the depot are created so that they can return.
Initial implementation
A dimension has been created to simulate the loading of one/several vehicles in a route optimisation. As defined, the optimiser should load the vehicle when it visits the depot:
final_capacity = starting_capacity + 0 +slack
where:
max1 => max capacity of the vehicle
max2 => biggest capacity of all vehicles
starting_capacity = [0, max1]
final_capacity = [0,max1]
slack = range (0,max2)
Subsequently, the vehicle should be able to unload X amount of weight when making deliveries and be able to return to the depot to reload as mentioned above.
Here is the depot/capacity code
def create_cargo_evaluator(self, cargo_index):
# Define the cargo counters
cargo = Counter()
for visit in self.visits:
cargo[visit["destination"]] -= visit["cargos"][cargo_index]
for depot in self.depots:
cargo[depot["destination"]] += 0
def capacity_evaluator(from_index):
"""Returns the demand of the node."""
# Convert from routing variable Index to demands NodeIndex.
from_node = self.manager.IndexToNode(from_index)
return cargo.get(from_node, 0)
return capacity_evaluator
def add_cargo_evaluator(self):
if "cargos" in self.vehicles[0]:
capacity_cargos = []
for i in range(len(self.vehicles[0]["cargos"])):
max_capacities = [vehicle["cargos"][i] for vehicle in self.vehicles]
capacity_evaluator_index = self.routing.RegisterUnaryTransitCallback(
self.create_cargo_evaluator(i),
)
self.routing.AddDimensionWithVehicleCapacity(
capacity_evaluator_index,
max(max_capacities),
max_capacities,
True, # start cumul to zero
f"Capacity-{i}",
)
capacity_cargo = self.routing.GetDimensionOrDie(f"Capacity-{i}")
capacity_cargos.append(capacity_cargo)
for x in self.starts:
index = self.manager.NodeToIndex(x["destination"])
capacity_cargo.SlackVar(index).SetValue(0)
for x in self.visits:
index = self.manager.NodeToIndex(x["destination"])
capacity_cargo.SlackVar(index).SetValue(0)
return capacity_cargos
Initial test
Here is a small test to verify the integrity of the code.
We also have a simple dimension that limits the number of deliveries a vehicle can make (only deliveries, not depot visits). This is called "max_services".
The test is about two vehicles limited to one delivery with a common depot. The 'reload' property of the depot is the number of copies of the depot that are made so that more than one vehicle can visit the depot and reload. Max Services limits the number of deliveries each vehicle can make to 1, so we ensure that each vehicle is assigned a depot.
_vehicles = [
{
"id": "vehicle1",
"dimensions": [2],
"origin": [0, 0],
"final": [0, 0],
"max_services": 1,
},
{
"id": "vehicle2",
"dimensions": [2],
"origin": [0, 0],
"final": [0, 0],
"max_services": 1,
},
]
_visits = [
{
"id": "delivery1",
"kind": "delivery",
"destination": [1, 1],
"dimensions": [1],
},
{
"id": "delivery2",
"kind": "delivery",
"destination": [1, 1],
"dimensions": [1],
},
]
_depots = [
{"id": "depot1", "destination": [1, 1], "reloads": 10},
]
def test_DepotsWithMaxServices(self):
time_matrix, distance_matrix, vehicles, visits, depots = build_distance_matrix(
{
"vehicles": _vehicles,
"visits": _visits,
"depots": _depots,
},
city_block_distance,
)
routes = Optimizer(
vehicles, visits, time_matrix, distance_matrix, depots=depots
).optimize()
Expected result:
vehicle1: origin -> depot1 -> delivery1 -> final
vehicle2: origin -> depot1 -> delivery2 -> final
Obtained result:
vehicle1: origin -> final
vehicle2: origin -> depot1 -> delivery2 -> final
The problem where the stops are being assigned to only one vehicle, happens with any amount of vehicles and stops.
Changing evaluator value
However, we have tried to change the value of the deposit in the evaluator from 0 to 1 after reading some discussions and forums about it so that the function looks like :
def create_cargo_evaluator(self, cargo_index):
# Define the cargo counters
cargo = Counter()
for visit in self.visits:
cargo[visit["destination"]] -= visit["cargos"][cargo_index]
for depot in self.depots:
cargo[depot["destination"]] += 1 # THIS IS THE ONLY CHANGE
def capacity_evaluator(from_index):
...
return capacity_evaluator
This makes that for the previous test, it gives the expected result:
vehicle1: origin -> depot1 -> delivery1 -> final
vehicle2: origin -> depot1 -> delivery2 -> final
Problem with new evaluator value
On the other hand, using 1 as a value creates problems when vehicles have more than one dimension of capacity and have to recharge for only one of the dimensions, for example:
_vehicles = [
{
"id": "vehicle1",
"dimensions": [3,3],
"origin": [0, 0],
"final": [0, 0],
},
]
_visits = [
{
"id": "delivery1",
"kind": "delivery",
"destination": [1, 1],
"dimensions": [3,0],
},
{
"id": "delivery2",
"kind": "delivery",
"destination": [1, 1],
"dimensions": [3,0],
},
]
_depots = [
{"id": "depot1", "destination": [1, 1], "reloads": 10},
]
def test_DepotsWithMaxServices(self):
time_matrix, distance_matrix, vehicles, visits, depots = build_distance_matrix(
{
"vehicles": _vehicles,
"visits": _visits,
"depots": _depots,
},
city_block_distance,
)
routes = Optimizer(
vehicles, visits, time_matrix, distance_matrix, depots=depots
).optimize()
Expected result:
vehicle1: origin -> depot1 -> delivery1 -> delivery2 -> final
Obtained result:
vehicle1: origin -> depot1 -> delivery1 ->final
What I understand that happens is that once the vehicle has made the first stop and arrives at the second delivery, the formula is as follows:
final_capacity = starting_capacity + 1 + slack
For the first dimension, where a delivery has been made, it will be:
3 = 0 + 1 + slack(2)
However, for the second dimension it will be:
4 = 3 + 1 + slack(0)
Where 4 > max_capacity, therefore, it won't be able to revisit the depot.
If the behavior when we set 0 in the evaluator for the depot load was the same as the behavior when we set 1; we could get a result as follows:
Dimension 1:
3 = 0 + 0 + slack(3)
Dimension 2:
3 = 3 + 0 + 0 + slack(0)
Allowing a valid result.
Conclusions
My main concern is that, on a theoretical level, the behavior of the optimizer should be the same having the evaluator value as 0 or as a different number than 0.
But as we can see the behavior is not the same.
What can be the causes of this mismatch? Is that we're not fully understanding the behavior, or that there's something wrong in the optimizer when using this kind of evaluators?
I would appreciate any kind of suggestion/insights on what could be the causing of this.