Meaning of Pickup and Delivery services

[yowl yowlxx]

Hi,

Just getting started with jsprit, but I've read around for an similar question and not found an answer.  Say I have 2 pickup locations, A and B, each deliverying quantity 1 of a cargo.  There are 2 delivery locations, C and D, each requiring quantity 1.  There are no depots as such, just the pick up locations.  There is one vehicle and so there are 4 possible solutions:

A->C, followed by B ->D
A->D, followed by B->C
B->C, followed by A ->D
B->D, followed by A->C

The vehicle has to pick up before it can deliver, but there are no fixed shipments, i.e. the cargo at A can go to C or D.

I thought I could model this with Pickups and Deliveries but it seems to make the delivery before the pickup which I don't want as I am modelling ships going from load ports to discharge ports.  Is there a way to model this?

Thanks,

Scott

[Stefan Schroeder]

Hi Scott,

when modelling pickups and deliveries (the ones that extend Service), it is assumed that pickups (once picked up) stay in the vehicle until it arrives at its end location, and it is assumed that deliveries are (implicitly) picked up at the start location of the vehicle and unloaded at delivery location.
What I can suggest you is to model it as open multiple depot problem with services (for example deliveries that extend Service). This assumes that you also have several vehicles, at least one vehicle at A and B. Optimize it which results for example in two open routes, tour1 = A -> C and tour2 = B -> D, and pull together the resulting routes into a single route for your one vehicle, i.e. vehicle_start_location - tour1 - tour2 - vehicle_end_location. If your case becomes more complex than the example you sent (which I assume it is) than this probably yields sub-optimal results.
The other way might be to fork jsprit and extends it such that it can deal with shipments having multiple pickup and delivery locations. I assume it is not the most difficult extension since instead of having one pickup loop you have several (but it is probably little more difficult than just adding another loop).
Another way is what was once suggested from Phil that you can define four shipments A->C, A->D,B->C,B->D and define A->C and A->D as related, i.e. that you need to make sure (by defining an appropriate constraint) that only one shipment, either A->C or A->D, can be in the solution. The other will end up in the unassigned job list. But as Phil also wrote, it is more a random walk rather than a guided search. But still, you might get reasonable solutions, especially if you use the regret insertion (since regret insertion scores the jobs first according to opportunity costs, second_best - best).

Best
Stefan
 

Am 02/03/15 um 21:17 schrieb yowl yowlxx:

--
You received this message because you are subscribed to the Google Groups "jsprit-mailing-list" group.
To unsubscribe from this group and stop receiving emails from it, send an email to jsprit-mailing-...@googlegroups.com.
To post to this group, send email to jsprit-ma...@googlegroups.com.
Visit this group at http://groups.google.com/group/jsprit-mailing-list.
For more options, visit https://groups.google.com/d/optout.

[yowl yowlxx]

HI Stefan,

Thanks for explaining pickup and delivery, I now understand why they work as they do.  You are right in that this is an example, a more realistic example would have 10 ships(vehicles) with 20 load ports and 20 discharge ports with the vehicles starting either at some port, not necessarily a load port or at sea (i.e. not at any port).  So with the second option I guess that would be 20 X 20 = 400 shipments although I could probably cut that down by looking at other factors.  I will try that approach to see how it goes. 

On a different approach, I don't know the authors, but what is the possibility of getting some paid development done to get a better fit for this scenario?

Thanks,

Scott

To unsubscribe from this group and stop receiving emails from it, send an email to jsprit-mailing-list+unsub...@googlegroups.com.