Algorithm for stacked orders in food delivery (Pick up and deliveries)-CodePudding

I am trying to implement stacking orders

While the most optimal solution would be to consider picking up orders from nearby restaurants that have similar food prep time AND nearby delivery locations.

I'd like to start off with something slightly easier - that is stacking orders only from the SAME restaurants that have similar food prep time to multiple deliver points. (Deliveroo example:

This takes 0.4 milliseconds.

pickup timer test
manhatten 0 0 0
c 0.0 0.0 rest
c 2.5 2.5 topright
c -2.5 2.5 topleft
c 2.5 -2.5 bottomright
c 2 2 neartopright

route rest -> topright -> neartopright -> topleft -> bottomright -> rest ->
raven::set::cRunWatch code timing profile
Calls           Mean (secs)     Total           Scope
       1        0.0003218       0.0003218       TravellingSalesManCalculation
       1        2.23e-05        2.23e-05        CalculateManhattenDistances

For 800 order stacks that is 1/3 second when processed in series. Adding the order stacking time shown above, gives total calculation time of less than a second. You will have to add the time taken to receive the order data from your server and then send the routes to the drivers which will depend on your server and network, but I would guess you will need just a few more seconds. ( You still haven't posted your runtime requirement!!! )

Note: I am assuming that all that the drivers need is a list of delivery locations in optimal order, when they can use their own GPS device to find the detailed route to the next delivery. If this is not the case, and the drivers need detailed routing ( left right, second left ... ) then this will take longer. Please let me know how you want this to work.

I have increased the number of restaurants to 5000

C:\Users\James\code\pickup\bin>pickup.exe
Pickup
Orders per hour                20000
Order collection time mins     5
Restaurants                    5000
Pickup window mins             5
Maximum order preparation mins 15
1416 order stacks created
raven::set::cRunWatch code timing profile
Calls           Mean (secs)     Total           Scope
       1        2.80843         2.80843         stack

Since the order rate has not increased, the number of order per restaurant is reduced and so is the opportuniy to stack orders - result is an significant increase in calculation time.