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 the bike sharing service. Suppose 5 envoys have to pick up 30 envelopes from a specific source and deliver them to a specific 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 around the city (therefore, I do not have one warehouse), and they do not need to return to where they started:

  XY 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 restrictions:

• Each messenger can carry up to fifteen envelopes
• The way to move the envelope should be less than three times on the direct route (therefore, delivery does not take too much time).

And these soft restrictions:

• Optimize the way the messenger should cycle

I think I need to set up an example of vehicle routing, but since I'm a beginner, I don't know where to start. How can I make sure the envelope is picked up before the messenger tries to deliver it? It would be great if you could help me here ...

Thanks!

Answer 1

Take the VRP (Vehicle Routing) example and configure it as follows:

• Rename the Vehicle class to Messenger
• Change class Messenger depot property to startingLocation
• Remove the limitation of "returning the vehicle back to the depot" (unless the messengers must return to their original location).
• Rename the Customer class to EnveloppeExchange with type PICKUP or DELIVERY
• Note: if pickup and EnveloppeExchange delivery have the same location, use 2 separate instances of EnveloppeExchange .
• Add a shadow variable to EnveloppeExchange called messengerContents , which lists the set of octets sent to this EnveloppeExchange . Write a VariableListener (see Docs) that updates this shadow variable.
• Add the restriction that messengerContents on EnveloppeExchange delivery must contain the required envelope
• Add the restriction that messengerContents in any EnveloppeExchange should not be more than 15
• Add the restriction that any envelope X, the sum of the EnveloppeExchange distances for which EnveloppeExchange messengerContents contains this X wrapper, must not exceed 3 times the direct route.

And best of all, use 6.0.0.CR4 (released today).

Answer 2

I am not an expert at OptaPlanner. But I would like to choose what you mentioned in your brackets (or a similar Open Source Framework). However, if OptaPlanner has already provided you with a reasonable solution, you can probably ignore it. If not, or you just want to compare the results, this may be of interest to you.

Firstly, the problem you are describing sounds simple, but is one of the most difficult tasks. This is basically Capacitated VRP with pickup and delivery, several depots, open routes and Windows time / restrictions. You probably can't find many open source solutions for this kind of problem.

I created a project called jsprit . jsprit can solve your problem. It is not like OptaPlanner and is not the basis. He pays great attention to the problems of vehicle routing and is a set of Java tools (i.e. a set of libraries). I implemented your problem. Here you can find the commented code.

I slightly changed one of your restrictions ("The way to move envelopes should be less than three times on the direct route, so delivery does not take too much time"). If you want the deliveries to be relatively fast, I think that you are better off making this restriction regarding the “best” messenger. Thus, I replaced it ("The method of moving envelopes should be three times smaller than the direct route with the best messenger, that is, the fastest messenger on the direct route").

Look at the result (you can build it and get a short report) and play with other restrictions or algorithm configurations to adapt it to your requirements. If you have any questions, feel free to contact me.

jsprit is in absolute terms and, compared to OptaPlanner, is a very young project, you will eventually find that errors or limiting restrictions are not as convenient as they should be. But it's good that you can help improve it ... reporting bugs, criticizing and suggesting alternative solutions, etc. :).