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: https://riders.deliveroo.com.sg/en/tech-round-up-stacking-orders)

The scale is about 200k orders hourly and 5000 riders. Run time is important here. (on demand service)

What I have in mind is this:

(1) Collect orders per few minutes interval and sort all orders by their prep time O(nlogn)

(2) group orders by restaurant O(n)

(3) Starting from the order that has the smallest remaining prep time, look for any orders in the same restaurant within the time window (let's say 3-5 mins), if exists group them as a stack. O(1).

  • locations of delivery points are not considered here to reduce computations - most delivery points are within 3km in a given zone.
  • not so interested in global optima for computational time. Picking the order that has the smallest remaining prep time is to avoid considering all combinations for rider - orders permutation matching.

(4) Run simulated annealing for semi-optimal TSP for vehicle routing. (ex. Pickup order A, B, C from the same restaurants -> deliver C to A to B)

I understand for multiple PICKUP and Dropoff the problem would translate into VRPTW - a hard problem to solve in real-time.

A somewhat easier problem - single Pickup and multiple Drop off would there be any better way than what I have in mind right now?

Many thanks in advance.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.