CVRPTW with Upper Bounds

[Jem Sama]

Hi folks,

I am currently working on a CVRPTW with upper bound constraints. I wanted to make sure that every vehicle should only have maximum working hours of 'vehicle_hours. 

This is the line I used in my program,

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

vehicle_hours = data['vehiclehours']

# vehicle_hours = round(vehicle_hours[vehicle_id]*60*60,3)

vehicle_hours = int(vehicle_hours[vehicle_id]*60*60)

# print(vehicle_id, vehicle_hours)

time_dimension.SetSpanUpperBoundForVehicle(vehicle_hours, vehicle_id) 

When I tried to run my program at  'vehicle_hours' 11 hours, the time covered by each vehicle doesn't exceed 8 hours. However, when I tried to run between 8-9 hours (randomly assigning per vehicle), the program doesn't work. I made sure that time windows is within 8 hrs and increased processing time. Still cant find a feasible route that follows my imposed time. 

Any idea/comments/questions are highly appreciated. 

Thanks! 

[Mizux Seiha]

Sometime first solution strategy can't find a solution with tight constraint while the GLS will later improve it, so you can try to:

* use a SetCumulVarSoftUpperBound on end node to incentive solver to only use 8h while still allowing larger working time.
* allow node to be dropped and hope GLS will bring them back to the solution but at least an initial solution can be found

[Jem Sama]

Should I use something like this?

for vehicle_id in range(data['num_vehicles']:

        vehicle_hours = data['vehiclehours']

        index_end = routing.End(vehicle_id)

        time_dimension.SetCumulVarSoftUpperBound(index_end, vehicle_hours)

Im not sure whats the parameter for SetCumulVarSoftUpperBound  if its just the same with SetSpanUpperBoundForVehicle 

[Corentin "Mizux" Le Molgat]

see: 
https://github.com/google/or-tools/blob/b37d9c786b69128f3505f15beca09e89bf078a89/ortools/constraint_solver/routing.h#L2514-L2523

[Jem Sama]

Thanks! Let me check it :) 

[Jem Sama]

I tried to implement it but the maximum work hours is still not followed. Is there a work around for this or am I doing something wrong? 

heres the code,

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

            vehicle_hours = data['vehiclehours']

            index_end = routing.End(vehicle_id)

            vehicle_hours = int(vehicle_hours[vehicle_id]*60*60)

            time_dimension.SetCumulVarSoftLowerBound(index_end, 1000, vehicle_hours)

            time_dimension.SetCumulVarSoftUpperBound(index_end, 1000, vehicle_hours)

The time I set for each vehicle to 'Work' is at 8 hours but some vehicles exceeds the 'Working Time" imposed. 

Thank you!  

On Saturday, August 7, 2021 at 3:11:09 PM UTC+8 mizu...@gmail.com wrote:

[Laurent Perron]

You set a 'soft' limit.

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/20d87685-e7f2-49ec-960c-b23384443da9n%40googlegroups.com.

[Jem Sama]

I had it that way since using SetSpanUpperBoundForVehicle doesnt work in some hours. Can you explain/expound what I should try or do if you dont mind?