How to add minimum vehicle travel distance?

[Vinh Đặng]

Hello everyone,

I am working with Pickup and Delivery problem, and I want to add the minimum vehicle travel distance constraint.

Based on the tutorial:

# Define cost of each arc.
    def distance_callback(from_index, to_index):
        """Returns the manhattan distance between the two nodes."""
        # Convert from routing variable Index to distance matrix NodeIndex.
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return data['distance_matrix'][from_node][to_node]

    transit_callback_index = routing.RegisterTransitCallback(distance_callback)
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

    # Add Distance constraint.
    dimension_name = 'Distance'
    routing.AddDimension(
        transit_callback_index,
        0,  # no slack
        3000,  # vehicle maximum travel distance
        True,  # start cumul to zero
        dimension_name)
    distance_dimension = routing.GetDimensionOrDie(dimension_name)
    distance_dimension.SetGlobalSpanCostCoefficient(100)

I checked the doc (https://developers.google.com/optimization/reference/constraint_solver/routing/RoutingModel#AddDimension) and there is no lower bound parameter for the dimension, only upper bound.

So, I defined a negative distance:

def negative_distance_callback (from_index, to_index):
        """
        return the negative distance, use for minimization
        """
        return -1 * distance_callback(from_index, to_index)

    transit_neg_callback_index = routing.RegisterTransitCallback(negative_distance_callback)

dimension_name = 'Negative_Distance'
    routing.AddDimension(
        transit_neg_callback_index,
        0,  # no slack
        -1000,  # vehicle minimum travel distance
        True,  # start cumul to zero
        dimension_name)
    negative_distance_dimension = routing.GetDimensionOrDie(dimension_name)

    negative_distance_dimension.SetGlobalSpanCostCoefficient(100)

My idea is that, the cumulative negative distance should not be larger than -1000, so the true total distance should not be less than 1000.

However, the code results an error: "Check failed: min_capacity >= 0 (-1000 vs. 0)     "

So, how could I define the minimum constraint?

Thanks

----------------------------------
Best Regards
 
Vinh Dang

[Mizux Seiha]

You have soft lower lower bound: see https://github.com/google/or-tools/blob/b37d9c786b69128f3505f15beca09e89bf078a89/ortools/constraint_solver/routing.h#L2536-L2546

e.g. to have all vehicles having [10,13] visits (note since it is a soft bound solver can decide a vehicle to visit only 8 nodes but in this case it will cost 100_000 * (10-8)
```python

 routing.AddConstantDimension(

            1,

            30,

            True,  # start cumul to zero

            "Counter")

    counter_dimension = routing.GetDimensionOrDie("Counter")

    for vehicle_id in range(data["num_vehicles"]):

        index = routing.End(vehicle_id)

        counter_dimension.SetCumulVarSoftLowerBound(index, 10, 100_000)

        counter_dimension.SetCumulVarSoftUpperBound(index, 13, 100_000)

```

[Mizux Seiha]

For hard constraint distance_dimension.CumulVar(routing.End(vehicle_id)).SetRange(hard_lower_bound, hard_uppper_bound) should make it