Mixed pickup and delivery with variable times.

[Hugo Delsing]

We are trying to solve a vehicle routing problem where we have several people that need to be transported to their own location at a fixed time. All vehicles have a capacity (max 8people) and we need to use as little as possible vehicle to transfer all the people. Every person may only be 2 times the minimum time in the vehicle and may only be maximum of 15minutes early.

Example:

• Person A needs to be at Location Z at 10:00. The direct travel time is 30 minutes. So person A needs to be picked up between 9:00 and 9:30 to arrive in time.
• Person B needs to be at Location Y at 10:15. The direct travel time is 45 minutes. So person B needs to be picked up between 8:45 and 9:30 to arrive in time.
• The distance between Z and Y is 10minutes.
• The distance between A and B is 20 minutes.

In this case we could pickup person B at 9:10 and drive to person A.
We arrive there at 9:30 and drive to location Z where we drop of person A at 10:00.
We continue to location Y where we arrive at 10:10 to drop of person B.


Not included in example, but actually needed: At each pickup/delivery point we have a variable slack time that happens before the location time.

Example:

• We need 3minutes at person A to load.
• We need 5minutes at location Z to unload.
• We need 7minutes at person B to load
• We need 1minute at location Y to unload.

This would result in an update solution:

• We arrive at person B at 8:55 and have him loaded at 9:02.
• We drive to person A and arrive at 9:22 and have him loaded at 9:25.
• We drive to location Z and arrive at 9:55 and have person A unloaded at 10:00.
• We drive to location Y and arrive at 10:10 and have person B unloaded at 10:11.
  

Obviously there could be a lot more people/drop of locations and we need the best solution with minimum amount of vehicles.

Is this possible with the vehicle routing library and if so: How would I go about this? We solved the normal vehicle routing problem where we need to deliver people to the same location, but I have no idea about how to start with this.

[Vincent Furnon]

Hi Hugo,

On Wed, Jan 13, 2016 at 12:58 AM, Hugo Delsing <t...@checkthis2.nl> wrote:

We are trying to solve a vehicle routing problem where we have several people that need to be transported to their own location at a fixed time. All vehicles have a capacity (max 8people) and we need to use as little as possible vehicle to transfer all the people. Every person may only be 2 times the minimum time in the vehicle and may only be maximum of 15minutes early.

Not sure I understand the "2 times the minimum time in the vehicle" constraint. Is it a constraint on the maximum time between a person's pickup time and his arrival time ?

 

Example:

• Person A needs to be at Location Z at 10:00. The direct travel time is 30 minutes. So person A needs to be picked up between 9:00 and 9:30 to arrive in time.

From what you say above, a person can only be 15 minutes early which would mean pickup must happen at 9:15 at the earliest, no ? 

• Person B needs to be at Location Y at 10:15. The direct travel time is 45 minutes. So person B needs to be picked up between 8:45 and 9:30 to arrive in time.
• The distance between Z and Y is 10minutes.
• The distance between A and B is 20 minutes.

In this case we could pickup person B at 9:10 and drive to person A.
We arrive there at 9:30 and drive to location Z where we drop of person A at 10:00.
We continue to location Y where we arrive at 10:10 to drop of person B.


Not included in example, but actually needed: At each pickup/delivery point we have a variable slack time that happens before the location time.

Example:

• We need 3minutes at person A to load.
• We need 5minutes at location Z to unload.
• We need 7minutes at person B to load
• We need 1minute at location Y to unload.

This would result in an update solution:

• We arrive at person B at 8:55 and have him loaded at 9:02.
• We drive to person A and arrive at 9:22 and have him loaded at 9:25.
• We drive to location Z and arrive at 9:55 and have person A unloaded at 10:00.
• We drive to location Y and arrive at 10:10 and have person B unloaded at 10:11.
  

Obviously there could be a lot more people/drop of locations and we need the best solution with minimum amount of vehicles.

Is this possible with the vehicle routing library and if so: How would I go about this? We solved the normal vehicle routing problem where we need to deliver people to the same location, but I have no idea about how to start with this.

Sounds like this should be feasible.

First build a pickup and delivery pair for each person using RoutingModel::AddPickupAndDelivery, the pickup being the pickup location and the delivery being the arrival location. This will ensure the pickup and the delivery happen on the same route.

Then you'll need to add a time precedence constraint to ensure the pickup happens before the delivery (have a look at the pdptw example: https://github.com/google/or-tools/blob/master/examples/cpp/pdptw.cc).

Concerning the time dimension, the transit callback should return the sum of the transit times and of the loading/unloading times at each node; for instance, transit(A, x) = 3 minutes + time(A, x), transit(Z, x) = 5 minutes + time(Z, x), etc. Set time windows on each delivery node corresponding to the time constraints you have for each delivery; for instance TW(Z) should be [9:45 - 10:00].

Does this look ok to you ?

Vincent

 

--
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.
For more options, visit https://groups.google.com/d/optout.

[Hugo Delsing]

Hello Vincent,

Thank you for a nice explanation. I'm going to take a look at the AddPickupAndDelivery.

For your question:

• Not sure I understand the "2 times the minimum time in the vehicle" constraint. Is it a constraint on the maximum time between a person's pickup time and his arrival time ?
  
  

• The 2 times the minimum time, is to protect a person from extreme long combinations. If the direct travel time between A and Z is 30minutes, it wouldn't be nice to have the customer in the car for 8hours, just because it's best for the planning. So if person A is alone in the car, then the earliest pickup would be 9:15, because else he is more then 15minutes early. But perhaps we travel from A to B to C to pickup people and then drop A off at location Z. Then person A can also be picked up at 9:00 if the combined route can drop him off at location Z between 9:45 and 10:00.

Regards,
Hugo