CODEWITHSUNDEEP
c#or-tools
Hunzla Ali
Hunzla Ali

Reputation: 61

How to limit number of locations for each vehicle in Google OR-Tools Route Optimization

I have implemented Or-Tools for route optimization. Its working fine. Only one thing which i want to achieve that limit number of locations for each vehicle. For example, maximum two(2) locations defined for each vehicle.

I have tried to implement Capacity Constraint but it does not work. Also i tried to implement SetSpanUpperBoundForVehicle function, in this case solution object is null.

Here is my code

RoutingDimension timeDimension = routing.GetMutableDimension("Time");
            timeDimension.SetSpanUpperBoundForVehicle(2, 0);
            timeDimension.SetSpanUpperBoundForVehicle(2, 1);
            timeDimension.SetSpanUpperBoundForVehicle(2, 2);

How can i limit this number of routes? Please help.

Upvotes: 2

Views: 1684

Answers (1)

Mizux
Mizux

Reputation: 9291

Simply create a counter dimension, at each location add 1, then for each vehicle limit the capacity to the number of maximum locations allowed.

e.g. reusing vrp.py sample and adding:

   # Create counter
    def counter_callback(from_index):
        """Returns 1 for any locations except depot."""
        # Convert from routing variable Index to user NodeIndex.
        from_node = manager.IndexToNode(from_index)
        return 1 if (from_node != 0) else 0;

    counter_callback_index = routing.RegisterUnaryTransitCallback(counter_callback)

    routing.AddDimensionWithVehicleCapacity(
        counter_callback_index,
        0,  # null slack
        [4,5,4,6],  # maximum locations per vehicle
        True,  # start cumul to zero
        'Counter')

possible output:

%python vrp.py
Objective: 6780
Route for vehicle 0:
 0 -> 7 -> 0
Distance of the route: 388m

Route for vehicle 1:
 0 -> 14 -> 16 -> 15 -> 3 -> 4 -> 0
Distance of the route: 2716m

Route for vehicle 2:
 0 -> 13 -> 12 -> 11 -> 1 -> 0
Distance of the route: 1804m

Route for vehicle 3:
 0 -> 5 -> 8 -> 6 -> 2 -> 10 -> 9 -> 0
Distance of the route: 1872m

Total Distance of all routes: 6780m

As you can see, routes respect the 4, 5, 4, 6 locations limit.

Note: For C# syntax, it is barely the same see https://github.com/google/or-tools/blob/stable/ortools/constraint_solver/samples/VrpCapacity.cs and https://github.com/google/or-tools/blob/stable/ortools/constraint_solver/samples/VrpCapacity.csproj

Upvotes: 7

Related Questions