Vehicle routing with minimum locations per route.

[keerthys]

Hi,
I have been trying to use the or-tools routing model for generating routes with the following constraints,

1. Time window constraint for customer to visit.
2. Maximum capacity for a vehicle.
3. Penalty for critical customer to be included in the route.
4. Minimum capacity for a vehicle to ensure that we don't operate vehicles which are under capacity.

I am able to implement (1), (2) and (3) following the wiki docs and code samples. But not sure how to achieve (4). I tried to use SetEndCumulVarSoftLowerBound on capacity dimension but results to be not optimal. As I change the value of the cumulVar parameter in the method, results varies a lot and skips entries for certain cumulVar.

Any pointers and help on implementing (4) along with 1..3 would be really helpful.

I am pasting the code I use for creating model below for reference.

num_vehicles = 3
routing = pywrapcp.RoutingModel(num_locations, num_vehicles)
...
        parameters = routing.DefaultSearchParameters()
        parameters.first_solution_strategy = (routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
        parameters.time_limit_ms = 5 * 1000  # 5 seconds search time limit
        parameters.use_light_propagation = False
        parameters.log_search = True

        # Set the depot.
        routing.SetDepot(depot)

        # Put callbacks to the distance function and travel time functions here.
        dist_between_locations = CreateDistanceCallback(locations)
        dist_callback = dist_between_locations.Distance
        routing.SetArcCostEvaluatorOfAllVehicles(dist_callback)

        # Adding capacity dimension constraints.
        demands_at_locations = CreateDemandCallback(demands)
        demands_callback = demands_at_locations.Demand
        vehicle_capacity = vehicle_capacity  # Maximum number of demands vehicle can carry
        null_capacity_slack = 0
        fix_start_cumul_to_zero = True
        capacity = "Capacity"
        routing.AddDimension(demands_callback, null_capacity_slack, vehicle_capacity, fix_start_cumul_to_zero,
                             capacity)

        capacity_dimension = routing.GetDimensionOrDie(capacity)
        for vehicle in range(0, num_vehicles):
            capacity_dimension.SetEndCumulVarSoftLowerBound(vehicle, 2, 1000)

        # Adding time dimension constraints.
        time_per_demand_unit = serviceable_duration_seconds  # seconds to service a customer
        horizon = self.__get_offset_from_start_of_day(vehicle_report_back_time)
        time = "Time"
        speed_kmph = vehicle_speed_kmph  # speed of vehicle in mk per hour assumed to be constant

        service_times = CreateServiceTimeCallback(demands, time_per_demand_unit)
        service_time_callback = service_times.ServiceTime

        total_times = CreateTotalTimeCallback(service_time_callback, dist_callback, speed_kmph)
        total_time_callback = total_times.TotalTime

        # Add a dimension for time-window constraints and limits on the start times and end times.
        routing.AddDimension(total_time_callback,  # total time function callback
                             horizon,
                             horizon,
                             fix_start_cumul_to_zero,
                             time)

        # Add limit on size of the time windows.
        time_dimension = routing.GetDimensionOrDie(time)
        for order in range(1, num_locations):
            start = start_times[order]
            end = end_times[order]
            time_dimension.CumulVar(order).SetRange(start, end)

        #Adding penalty for dropping order. Only first three locations are made critical here
        non_depot = set(range(1,3))
        penalty = 10  # The cost for dropping a node from the plan.
        nodes = [routing.AddDisjunction([int(c)], penalty) for c in non_depot]

        # Solve displays a solution if any.
        assignment = routing.SolveWithParameters(parameters)

[mjfwest]

I'm not quite sure what you want by point 4. Setting a cost of a vehicle maybe the way to do it?
You can do that with

"""
 # Create a set of vehicles, the number set by the length of capacity.
    vehicles = Vehicles(capacity=capacity, cost=cost)
""" 

See cvrptw_plot.py for an example. If I understand things correctly, doing it this way, a vehicle cost will be added if the vehicle is used. Setting this cost high will prevent vehicle 'under use'

[keerthys]

Thanks for the quick reply Martin.

Basically we have a requirement like vehicle should be operated only if the
route had more than X orders and also want to make sure that heavy weight
orders gets first picked up in the routes.

By setting up penalty as weight of order, we are able to make sure heavy
weight are included in the routes. But those heavy weight order may end up
falling in a route which has less than X orders(minimum criteria for van).
In order to avoid this case we need a hook to specify the minimum capacity
for a vehicle as well so that both our above requirement will be met.

Hope this clarifies.

On 19 Oct 2016 11:12 pm, "Martin West" notifications@github.com wrote:

I'm not quite sure what you want by point 4. Setting a cost of a vehicle
maybe the way to do it?
You can do that with
"""

Create a set of vehicles, the number set by the length of capacity.

vehicles = Vehicles(capacity=capacity, cost=cost)
"""
See cvrptw_plot.py for an example. If I understand things correctly, doing
it this way, a vehicle cost will be added if the vehicle is used. Setting
this cost high will prevent vehicle 'under use'

—
You are receiving this because you authored the thread.
Reply to this email directly, view it on GitHub
#261 (comment),
or mute the thread
https://github.com/notifications/unsubscribe-auth/AAyhCTzk-_LyrBkrKZNM_8mHGU48ugCEks5q1lZxgaJpZM4KbPvR
.

[keerthys]

Today after some testing, I ran into yet another issue with penalty where it is not working as expected. For instance, for the the following configuration,

1. Vehicle Capacity - 3
2. Number of vehicle - 1
3. C1, C2, C3 - 28.418896,77.092099000000005 (same location)
4. C4 - 28.494976, 77.089542
5. All customers with same delivery slot.

When I add the following disjunction it gives me C1, C2, C3 in route
[routing.AddDisjunction([int(c)], 1100) for c in set(range(1,4))]
routing.AddDisjunction([4], 1000)

Where as when I add the following disjunction it gives me C4 in route
[routing.AddDisjunction([int(c)], 1005) for c in set(range(1,4))]
routing.AddDisjunction([4], 1000)

I expected it should have given C1,C2 & C3 for both the cases as their penalty is higher than the penalty of C4.

Can you check and let me know what might be going wrong?

[asif03051993]

Hi,
We would also like to know how is the cost of route gets calculated when there is different penalty for orders and with time windows, serviceability time, distance etc.

[pocman]

If you want a hard constraint, you can simply add a constant dimension of value 1 and add a constraint on the cumulative var of this dimension at the end of each vehicle end.

[pocman]

For the critical customer, you should add a disjonction around each not critical node and the solver will be able to skip them (at some high cost).
Looking at your 4 requirements, I don't see any need for any kind of custom penalty.

[Mizux]

like proposed in #515 you can use:

minimum_allowed_capacity = 42 # put your 4. requirement value here
capacity = "Capacity"
routing.AddDimension(
    demand_evaluator, # function which return the load at each location (cf. cvrp.py example)
    0, # null capacity slack
    data.vehicle.capacity, # vehicle maximum capacity
    True, # start cumul to zero
    capacity)
capacity_dimension = routing.GetDimensionOrDie(capacity)
for vehicle in xrange(vehicle_number): 
    capacity_dimension.CumulVar(routing.End(vehicle)).RemoveInterval(0, minimum_allowed_capacity)

[PritambhatYoryo]

I am trying to solve very similar problem mentioned in #4 above.
In my cases we need to make sure vehicles are used to certain min % of their weight capacity say 80%.
Is it possible using below ?

minimum_allowed_capacity = 42 # put your 4. requirement value here
capacity = "Capacity"
routing.AddDimension(
demand_evaluator, # function which return the load at each location (cf. cvrp.py example)
0, # null capacity slack
data.vehicle.capacity, # vehicle maximum capacity
True, # start cumul to zero
capacity)
capacity_dimension = routing.GetDimensionOrDie(capacity)
for vehicle in xrange(vehicle_number):
capacity_dimension.CumulVar(routing.End(vehicle)).RemoveInterval(0, minimum_allowed_capacity)

[PranoyKumar3]

like proposed in #515 you can use:

minimum_allowed_capacity = 42 # put your 4. requirement value here
capacity = "Capacity"
routing.AddDimension(
    demand_evaluator, # function which return the load at each location (cf. cvrp.py example)
    0, # null capacity slack
    data.vehicle.capacity, # vehicle maximum capacity
    True, # start cumul to zero
    capacity)
capacity_dimension = routing.GetDimensionOrDie(capacity)
for vehicle in xrange(vehicle_number): 
    capacity_dimension.CumulVar(routing.End(vehicle)).RemoveInterval(0, minimum_allowed_capacity)

Hi Mizux,
I am using RemoveInterval as shown above to give minimum capacity to my vehicles, but the routing library is unable to find a solution,
Model data:
The total number of orders - 568
Total number of vehicles - 16
Max capacity of vehicles - 80
Minimum capacity of vehicles - 30
I used the above data, I even tried reducing the minimum capacity of vehicles to 1 to check if it works but i still didn't find any solution, let me know how to resolve this problem.

Thanks in advance.

[Mizux]

try to use this instead:

or-tools/ortools/constraint_solver/routing.h

Lines 2516 to 2526 in b77bd3a

	/// Sets a soft lower bound to the cumul variable of a given variable index.
	/// If the value of the cumul variable is less than the bound, a cost
	/// proportional to the difference between this value and the bound is added
	/// to the cost function of the model:
	/// cumulVar > lower_bound -> cost = 0
	/// cumulVar <= lower_bound -> cost = coefficient * (lower_bound -
	/// cumulVar).
	/// This is also handy to model earliness costs when the dimension represents
	/// time.
	void SetCumulVarSoftLowerBound(int64 index, int64 lower_bound,
	int64 coefficient);

[PranoyKumar3]

try to use this instead:

or-tools/ortools/constraint_solver/routing.h

Lines 2516 to 2526 in b77bd3a

	/// Sets a soft lower bound to the cumul variable of a given variable index.
	/// If the value of the cumul variable is less than the bound, a cost
	/// proportional to the difference between this value and the bound is added
	/// to the cost function of the model:
	/// cumulVar > lower_bound -> cost = 0
	/// cumulVar <= lower_bound -> cost = coefficient * (lower_bound -
	/// cumulVar).
	/// This is also handy to model earliness costs when the dimension represents
	/// time.
	void SetCumulVarSoftLowerBound(int64 index, int64 lower_bound,
	int64 coefficient);

Thank you Mizux for responding,
I understand that the function you mentioned makes the constraint soft, but I am facing a problem in the following scenario:
when I am using guided local search strategy at 10s (lower search time limit) the total distance traveled by my vehicles is 1,32,256 m and the objective value is 1,41,32,256 which means that the vehicles which could not satisfy the lower bound were met with a penalty, but when I increase the search time limit to 100s, the total distance traveled by all my vehicles is 65445m and the objective value is also 65445 which means that the minimum capacity constraint of all my vehicles should be satisfied, but in reality 8 out of 16 vehicles haven't satisfied the constraint but still the penalty wasn't added to the objective value. I would like to know what the reason for this is.
NOTE: There are no assigned orders in either of the scenarios and no other constraint other than min max capacity were added to them.

Thank you in advance

[Mizux]

strange, seems a bug.

• does vehicle who doesn't respect the constraint visit some nodes or go directly to end node ?
• Are you sure to set this LowerBound 16 times i.e. for each vehicle end ?

[PranoyKumar3]

strange, seems a bug.

* does vehicle who doesn't respect the constraint visit some nodes or go directly to end node ?
They visit a few nodes around 1 or 2
* Are you sure to set this LowerBound 16 times i.e. for each vehicle end ?

Hi,
This is how i defined the constraint for each vehicle:

counter_dimension = routing.GetDimensionOrDie('Capacity')
for vehicle_id in range(data['num_vehicles']):
    counter_dimension.SetCumulVarSoftLowerBound(vehicle_id,30,100000)

data['num_vehicles'] = 16

[Mizux]

you must use routing.End():

counter_dimension = routing.GetDimensionOrDie('Capacity')
for vehicle_id in range(data['num_vehicles']):
    counter_dimension.SetCumulVarSoftLowerBound(routing.End(vehicle_id), 30, 100000)

[PranoyKumar3]

you must use routing.End():

counter_dimension = routing.GetDimensionOrDie('Capacity')
for vehicle_id in range(data['num_vehicles']):
    counter_dimension.SetCumulVarSoftLowerBound(routing.End(vehicle_id), 30, 100000)

Hi Mizux,
I tried making changes that you asked for but the minimum capacity constraint still doesn't seem to be implemented the solver, I have attached a google colab link to a mini problem i created, kindly go through it.
Kindly let me know if this is a bug and if there is any alternative to achieve this functionality.

Google Colab Link: https://colab.research.google.com/drive/1zrBibaeAZErSuihjwSvlXeDNSHOZ1PwT?usp=sharing

Result :
The vehicle 4 seems to be delivering no shipment in spite of minimum capacity constraint.
And the cost for violating the constraint has also not been added to the objective cost.

Thank you in Advance