Bicycle messenger / TSPPD with OptaPlanner

Question

Dear OptaPlanner experts!

I would like to use OptaPlanner (or a similar Open Source Java Framework) to optimize routes for a bicycle messenger service. Let's assume 5 messengers have to pick up 30 envelopes FROM a certain origin and deliver them TO a certain destination:

            X(FROM) Y(FROM) X(TO)   Y(TO)
envelope 1  13745   55419   13883   55756
envelope 2  8406    53246   13937   55854
envelope 3  15738   57396   35996   79499
envelope 4  12045   60418   19349   57118
envelope 5  13750   56416   35733   78403
envelope 6  13190   57068   11860   59749
envelope 7  15021   55768   14098   57379
envelope 8  11513   58543   11501   59683
envelope 9  12013   64155   14120   59301
envelope 10 15006   57578   35511   78426
envelope 11 11450   58819   11916   58338
envelope 12 13728   56304   35524   79013
envelope 13 15104   60923   17937   57066
envelope 14 11373   58388   13983   53804
envelope 15 18575   55186   18718   54381
envelope 16 11639   50071   17363   58375
envelope 17 11273   53410   10860   60441
envelope 18 13766   59041   13963   57769
envelope 19 16138   55801   16183   56024
envelope 20 13728   56146   14301   61694
envelope 21 12848   57059   13586   59734
envelope 22 13645   56488   13955   55859
envelope 23 12896   56838   13937   55908
envelope 24 13341   58150   35709   78924
envelope 25 13483   57303   13614   57820
envelope 26 12741   63478   15230   59838
envelope 27 14676   51691   16501   48361
envelope 28 13748   54933   14120   56110
envelope 29 17875   59565   20453   61903
envelope 30 9772    56424   6404    55601

My five messengers are distributed through the city (so I don't have a single depot) and they don't have to go back to where they started:

            X       Y
messenger A 13750   57578
messenger B 15104   53410
messenger C 13728   55801
messenger D 12741   63478
messenger E 14676   18575

I would use the following hard constraints:

• Every messenger can carry up to fifteen envelopes
• The way an envelope travels should be less than three times the direct route (so the delivery doesn't take too long)

And these soft constraints:

• Optimize the way the messenger has to cycle

I guess I have to adjust the vehicle routing example, but since I am a newbie I don't know where to start. How can I make sure that an envelope is picked up before the messenger tries to deliver it? It would be great if you could help me out here...

Thank you!

Astrogeology

Answer 1

I am no OptaPlanner expert. But I'd like to pickup what you mentioned in your brackets (or similar Open Source Framework). However, if OptaPlanner already provided you with a reasonable solution, you can probably ignore this. If not or you just want to compare the results, this might be interesting for you.

First, the problem you describe sounds simple but is one of the more challenging. It is basically a Capacitated VRP with Pickup and Deliveries, Multiple Depots, Open Routes and Time Windows/Restrictions. You probably cannot find many Open Source solutions for this kind of problem.

I created a project called jsprit. jsprit can solve your problem. It is neither similar to OptaPlanner nor it is framework. It has a strong focus on vehicle routing problems and is a Java toolkit (i.e. a set of libraries). I implemented your problem. Here you can find the commented code.

I slightly changed one of your constraints ("The way an envelope travels should be less than three times the direct route so the delivery doesn't take too long"). If you want to ensure that deliveries are comparably fast, I believe you are better off making this constraint relative to the "best" messenger. Thus, I replaced it with ("The way an envelope travels should be less than three times the direct route with the best messenger, i.e. the messenger that is the fastest on the direct route").

Look at the result (you can plot it and get a brief report) and play with other constraints or the algorithm configuration to adapt it to your requirements. If you have questions, do not hesitate to contact me.

jsprit is in absolute terms and in comparison to OptaPlanner a very young project, eventually you find bugs or constraint definition is not that comfortable as it should be. But the good thing is, you can help to improve it ... by reporting bugs, criticising and suggesting alternative solutions etc. :).

Fibrinolysis

Answer 2

Take the VRP (vehicle routing) example and adjust it like this:

• Rename the class Vehicle to Messenger
• Change the class Messenger's depot property to startingLocation
• Remove the "vehicle go back to depot" constraint (except if the messengers need to go back to their starting location).
• Rename the class Customer to EnveloppeExchange with type PICKUP or DELIVERY
• Note: if a pickup and delivery EnveloppeExchange has the same location, use 2 separate EnveloppeExchange instances.
• Add a shadow variable in EnveloppeExchange called messengerContents which enumerates the set of envelops the messenger that arrives at that EnveloppeExchange has. Write a VariableListener (see docs) that keeps that shadow variable up to date.
• Add a constraint that the messengerContents at a delivery EnveloppeExchange must contain the required enveloppe
• Add a constraint that the messengerContents at any EnveloppeExchange must not be larger then 15
• Add a constraint that any envelope X, the sum of the EnveloppeExchange distances, for which the EnveloppeExchange's messengerContents contains that envelope X, must not exceed 3 times the direct route.

And it's best to use 6.0.0.CR4 (released today).

Sharolynsharon

Hey Geoffrey, thank you for your quick answer. I succeeded to rename to Messenger and startingLocation, then removed the "vehicle go back to depot" constraint. I would now add PICKUP and DELIVERY types. How would you import these types? Your first importing a list of IDs and locations, then IDs and demand, then whether the ID is a startingLocation or depot. Would you add another list specifying whether it is PICKUP or DELIVERY? If so, how would you know what envelope belongs to what PICKUP and what DELIVERY location? – Astrogeology