Assign demands to depots in Vehicle Routing

[Frank van den Bergh]

I just found this tool and I'm getting enthusiast.

I've a logistics supplier situation, with multi depots. In general you can say these are separated operational environments. Goods are shipped from depot 1 with depot1 vehicles to their own customers and other goods are collected to return to depot 1. The same counts for depot 2, etc. I want to use this tool for simulations (e.g. what are the consequences if you don't serve this region).

I read the demand cannot be negative, so I hope the collection issue can be tackled via the pickup and delivery option. I also want to calculate the advantages of partly driving for the other organisation(s). Eg the depot1 vehicle delivers the depot1 orders and during the trip he collects goods for depot2 and drops them at depot2 on his way back and may deliver some depot2 orders as well. And this is basically really multi-depot.

I've examined the cscvrptw examples of C++ and C# but I can't see if you can set from which depot the demand should be supplied. Is this doable or has someone a nice trick in house?

[Vincent Furnon]

On Wed, Jan 22, 2014 at 10:12 PM, Frank van den Bergh <vande...@elcbenelux.nl> wrote:

I just found this tool and I'm getting enthusiast.

I've a logistics supplier situation, with multi depots. In general you can say these are separated operational environments. Goods are shipped from depot 1 with depot1 vehicles to their own customers and other goods are collected to return to depot 1. The same counts for depot 2, etc. I want to use this tool for simulations (e.g. what are the consequences if you don't serve this region).

I read the demand cannot be negative, so I hope the collection issue can be tackled via the pickup and delivery option.

Actually demand can be negative but at any point in time the quantity in a vehicle must be positive. I would model deliveries with negative demands and pickups with positive demands being careful to let the cumul variable of the vehicle start node free (not bound to zero). Then you wouldn't have to create an explicit en-route pickup and delivery model linking pickups at the depot with deliveries and deliveries at the depot with pickups. Note this will however forbid multiple visits of the depot within a given route (can be worked-around by having multiple routes for a single real vehicle).

Note that you can model each depot problem as a separate model since there's no overlap between depots.

 

I also want to calculate the advantages of partly driving for the other organisation(s). Eg the depot1 vehicle delivers the depot1 orders and during the trip he collects goods for depot2 and drops them at depot2 on his way back and may deliver some depot2 orders as well. And this is basically really multi-depot.

In this scenario you have to use an en-route pickup and delivery model (have a look at the tsptw.cc example) and consider all vehicles and deliveries in a single model.

 

I've examined the cscvrptw examples of C++ and C# but I can't see if you can set from which depot the demand should be supplied. Is this doable or has someone a nice trick in house?

You can constrain a demand to be performed by a given vehicle (therefore depot) by constraining its "vehicle variable".

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/groups/opt_out.

[Frank van den Bergh]

Hi Vincent,
Thanks for you quick answer.

Regarding the negative demand: if I follow your suggestion then a trip with only deliveries is not allowed. And if you flip the sign, a full truck load collection will only exists in a trip with also a delivery.

Multiple visits limitation is not a real problem as a truck can have multiple trips, like you wrote and is common to use so.

Regarding the pickup and delivery is not quite clear to me (and it is unfortunately not documented yet, at least I can't find it). Suppose an optimal trip is (collection = pickup at node and unload at depot): depot - delivery node 1 - collection node 2 - delivery node 3 - collection node 4 - depot. Can this be constructed by your solver if I give a demand for nodes 1 and 3, and the pickups like shown in pdptw.cc (=tsptw.cc???)? And how about when node 2 and 3 refer to the same address?

Demand-depot constraint: if I use a vehicle limitation to a demand, that node will only be serviced by a vehicle of that depot. Another vehicle (attached to another depot or a charter) will not pickup and deliver it at that depot if its on route. Maybe I can force this by creating AddPickupAndDelivery from depots to the delivery nodes. Currently this working for another depot is not taking place (so the demand-vehicle trick will do the job). Deliveries by another depot does take place a lot, but that is first transported by a night shuttle and I won't feed that into the solver.

[Frank van den Bergh]

BTW I did find the documentation. Not online, but in the documentation dir; where else :)

[Vincent Furnon]

On Thu, Jan 23, 2014 at 4:09 PM, Frank van den Bergh <vande...@elcbenelux.nl> wrote:

Hi Vincent,
Thanks for you quick answer.

Regarding the negative demand: if I follow your suggestion then a trip with only deliveries is not allowed.

If you let the load variable at the start of the route free (cumul variable for your dimension), you can have negative only demands; propagation will increase the lower bound of this variable to match what's on the route.

 

And if you flip the sign, a full truck load collection will only exists in a trip with also a delivery.

Multiple visits limitation is not a real problem as a truck can have multiple trips, like you wrote and is common to use so.

Regarding the pickup and delivery is not quite clear to me (and it is unfortunately not documented yet, at least I can't find it). Suppose an optimal trip is (collection = pickup at node and unload at depot): depot - delivery node 1 - collection node 2 - delivery node 3 - collection node 4 - depot. Can this be constructed by your solver if I give a demand for nodes 1 and 3, and the pickups like shown in pdptw.cc (=tsptw.cc???)?

The pdptw example will model this. Actually the cvrptw example with mixed > 0 and < 0 demands will work too (if you limit each route to a single trip).

 

And how about when node 2 and 3 refer to the same address?

Should work the same.

 

Demand-depot constraint: if I use a vehicle limitation to a demand, that node will only be serviced by a vehicle of that depot. Another vehicle (attached to another depot or a charter) will not pickup and deliver it at that depot if its on route. Maybe I can force this by creating AddPickupAndDelivery from depots to the delivery nodes.

Yes this will work too.

 

Currently this working for another depot is not taking place (so the demand-vehicle trick will do the job). Deliveries by another 

depot does take place a lot, but that is first transported by a night shuttle and I won't feed that into the solver.

General remarks: problems with explicit pickup and delivery pairs are harder to solve; when you can, solving several independent problems (per depot) is faster than solving a global one.

[Danendra L]

Hi Vincent,

I have a similar vehicle routing problem. For delivery, items need to be transported from the depot to the customer, while for pickups, items should be collected from the customer and return to the depot.

I attempted to differentiate between pickups and deliveries by assigning positive and negative demand values, where pickups have positive demand and deliveries have negative demand. However, I'm facing a challenge where, if the vehicle is already full at the start of its trip, it may go to pickups first.

To illustrate:

Node 1: pickup with demand 1

Node 2: pickup with demand 2

Node 3: delivery with demand -2

Node 4: delivery with demand -1

vehicle capacity: 3

I want to prevent the vehicle from visiting node 1 or 2 first, as this would exceed its capacity. Instead, it should prioritise delivering node 3 and 4, which would reduce its load from 3 and allows it to handle pickups.

Do you have any suggestions on how to approach this? 

Appreciate any tips you may have.

[Laurent Perron]

Please no necro-posting.

The initial question is ten years old.

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/ac9f1896-5af9-4462-9663-d2d6daa4dadfn%40googlegroups.com.

[Danendra L]

Sorry, I misread the year as 2024.