Balancing VRPTW (Pickup and Delivery), with 2 bulks of Tasks

[Hai Dang Tu]

Hi, 

Here is some context for the problem:

I am using VRPTW with pickup and deliveries. I have multiple windows (for pickup, for deliveries and for driver shifts)

for each delivery node (soft): 

distance_dimension.SetCumulVarSoftLowerBound(node, when_can_i_start, early_task_penalty) 

distance_dimension.SetCumulVarSoftUpperBound(node, when_can_i_end, late_task_penalty) 

for each pickup node (hard): distance_dimension.CumulVar(node).SetMin(when_can_i_start_pickup) distance_dimension.CumulVar(node).SetMax(when_can_i_end_pickup) 

for each driver: 

//Here I set the hard constraint on the start (depot), so it must start exactly "when_can_this_driver_start".

 index_start = routing.Start(vehicle_id) distance_dimension.CumulVar(index_start).SetRange(when_can_this_driver_start, when_can_this_driver_start) 

 //end index 

index_end = routing.End(vehicle_id) distance_dimension.CumulVar(index_end).SetRange(0,when_can_this_driver_end_hard)

Everything works correctly in most cases, except when the shift is long (9 AM to 18 PM), and I have 2 "bulks" of tasks, i.e. 

*20 tasks(40 pairs) which can be picked up from 9AM to 19PM (and delivered by 22 PM, but that's not the problem). Let's call these "morning" tasks 

*50 tasks (100 pairs) which can be picked up from 16:30PM to 22PM. Let's call these "afternoon" tasks.

The Time Dimension has 24h slack, because the pickups have hard constraints.

Using 2 drivers (vehicles), with exact same shift (9AM to 18PM), the solution it gives me is to assign all the "morning" tasks to one driver (the other driver slacks until 16:30), while the "afternoon" tasks are balanced correctly between the 2 of them. I am using SetGlobalSpanCostCoefficient to balance globally (it works, since both routes end almost at the same time), but if I understand correctly, it also "balances" considering the slack time, so it doesn't fix my issue. Any ideas ?  Maybe a way to add a penalty when the slack times are imbalanced ?

Thank you in advance.

[blind.line]

I’m confused by your variable names. 

You seem to refer to “distance_dimension” as if it is time. 

My recommendation would be to fix that first (call it time everywhere), then create an actual “distance” dimension that is not time, and has no slack, and use that to balance the vehicles. 

Equivalently, create another time-related dimension that has no slack that only accumulates the travel times for each vehicle. 

I hope that helps, but perhaps not because as I said your code and terminology confuses me. 

James

On Jul 1, 2024, at 08:00, Hai Dang Tu <haidan...@gmail.com> wrote:

Hi, 

--
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/d4add4ce-fa6b-4ebe-b099-115efb9d00efn%40googlegroups.com.