1
$\begingroup$

I am solving a CVRPTWPD using Google ORTools. Here, objective is to minimize the travelled distance and not time.

I have start locations for each vehicle but arbitrary end locations are possible. I have added dummy node for arbitrary end locations.

Also, there are more than one type of vehicle and time matrix depends on the speed of type of vehicle. I need to implement soft time window constraints for all orders. Based on various sources on internet and my understanding of ortools, I'm implementing it as follows:

travel_time_callback_indices = []

for _, row in driver_df.iterrows():
    speed = row["speed_meter_per_sec"]
    vehicle_travel_time_callback = partial(travel_time_callback, speed_in_mps=speed)
    travel_time_callback_index = routing.RegisterTransitCallback(vehicle_travel_time_callback)
    travel_time_callback_indices.append(travel_time_callback_index)


dimension_name = 'Time'
routing.AddDimensionWithVehicleTransitAndCapacity(
    travel_time_callback_indices,
    7200,  # Max Slack
    [7200]*driver_df.shape[0],  # vehicle maximum travel time
    False,  # don't start cumul to zero
    dimension_name)

time_dimension = routing.GetDimensionOrDie(dimension_name)

Till here, it works fine. As soon as I add TW constraints as follows, kernel dies.

penalty = 1 # $1/second
# Add time window constraints for each location except depot.
for location_idx, time_window in enumerate(data['time_windows']):
    index = manager.NodeToIndex(location_idx)
    time_dimension.CumulVar(index).SetMin(time_window[0])
    time_dimension.SetCumulVarSoftUpperBound(index, time_window[1], penalty)

Please note that all the vehicle start locations and dummy node have been given the max possible time window.

I need to understand why is kernel dying? Is there any better way to implement soft time window constraints?

$\endgroup$

1 Answer 1

1
$\begingroup$

I was able to fix this. I checked on following points:

  1. time callback function must return an integer and not float.
  2. You can not add time window constraints on depots.
penalty = 1 # $1/second
# Add time window constraints for each location except depot.
for location_idx, time_window in enumerate(data['time_windows']):

    if location_idx in data["depots"] + dummy_depot:
        continue    

    index = manager.NodeToIndex(location_idx)
    time_dimension.CumulVar(index).SetMin(time_window[0])
    time_dimension.SetCumulVarSoftUpperBound(index, time_window[1], penalty)
```
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.