Food delivery: order/rider assignment optimization algorithms?

Alright so admittedly this is something I’ve been thinking about for a while, although I have relatively little idea of how I want to practically implement within my apps. This is MUCH further down the line for me- once I’ve completed my little “super app ecosystem”.

BTW I am talking about automated dispatching here, I’m assuming this is cloud functions type of thing. As computers can make a highly complex mathematical decision within seconds and literally data centers are ubiquitous and run 24/7 worldwide. Dynamic services for dynamic people! :smile:

I did take a Probability with Stochastic Processes class in school, so I am vaguely aware of things like VRP (vehicle routing problem). A very well known example of VRP is the Travelling Salesman Problem. A salesman wants to visit a set of cities one time each and wants to follow the path with the minimum distance. The salesman starts from a city and goes back to the same one at the end. This problem is similar yet very different to the one at hand lol…I also know a bit about Markovian mathematics too

These companies desire to make partnerships with restaurants that don’t have their own delivery service. They want to offer the restaurants to have the ability to reach customers on their mobile phones…customers to order meals via the company and hand off occurs at their home. The objective will thus be to minimize the time a
customer will have to wait to get their meal and preventing the lateness of such a delivery service.

Immediate dispatching deals with this order process in a straightforward way, however IMO its not appropriate. A new order is sent to the rider as soon as it’s booked, even if the rider won’t head to the pickup restaurant for another half an hour and is on another delivery! Remember these systems must be dynamic! I would think some sort of deferred dispatching would be appropriate. With deferred dispatching, the algorithm (typically cloud functions I would think?) will hold back a buffer of undispatched orders.
With deferred dispatching, undispatched orders are frequently reassigned to different riders as conditions change - for example when new orders are created or unexpected delays occur. This makes the delivery network more robust, as a late-running rider can have their undispatched orders reassigned to a different rider. The riders themselves only see dispatched orders, so they are unaware of this ongoing reassignment -typically. On the other hand, with immediate dispatching, orders are never reassigned to a different rider after order creation. Conversely, there is no buffer of undispatched orders held back. At least that’s how I imagine this to work … LOL!

However there is a lot more to this! I came across this from the Doordash Engineering blog : “… Upon arriving in the optimization layer, our new order’s potential offers are scored and ranked to allow the mixed-integer program (MIP) to make its decisions, a process that we describe in a previous article, titled Next-Generation Optimization for Dasher Dispatch at DoorDash. Our scoring function is designed to recognize tradeoffs between efficiency (using Dasher time as efficiently as possible) and quality (getting deliveries to consumers as quickly as possible), while trying to account for explained and unexplained variance in our ML estimates of order ready times, travel times, and Dasher acceptance rate. Once every offer is scored, we solve the MIP using Gurobi, a software-based commercial MIP solver that is able to solve this type of problem at scale very efficiently.” Link here Oh and here is a link to the Optimizer they use, Gurobi

The companies wish to pay the delivery man by commission, as this reduces the lemons law within regards to workers. Also because the amount of orders/demand is relatively dynamic, the companies would like to pay riders for actual deliveries and not doing nothing. Again the overall goal is to minimize cost per delivery, in order for what looks to be very narrow profit margins. A lot of these companies are still in the red… and we are 10 years into this!

This interview speaks volumes although IMO Delivery hero is on its way to being in better financial shape then Uber and many others Man this interviewer does not his punches back! “How much money have you lost?!” and “I don’t believe in your business model!” … great stuff! Hard questions lol

#superapp, #gigeconomy #delivery #uber

Here are some more interesting links:
Academic paper - The Meal Delivery Routing Problem

Delivery Routing Problem Test Instances (bit old but somewhat insightful code)

Evolution of delivery dispatch

The log-com bubble is about to burst on “on demand deliveery”