What is the algorithm for the movement of couriers for delivery from restaurants?

Question

Algorithms

Good afternoon!

We are working on a food delivery system from restaurants, such as Yandex.Food or DeliveryClub.
Accordingly, an algorithm is needed that, based on order data, data on the geolocation of couriers, will give couriers optimal tasks for the next move.
I thought, maybe there are such algorithms somewhere in the public or someone can share their best practices?

Answer 1

You have an interesting problem : NP-complete , but quite solvable under the constraints of the real world.
Your salesman has a limited resource in terms of the number of delivery points. Delivery, probably, needs to be done within the specified time frame (while hot).
In total, your task is divided into two:

1. Distribute orders among couriers. And some couriers are still on the way, some are in reserve. Let's say you have 7 couriers: one is on the way far, another one is on the way and three are under loading (plus two in reserve on pickup in case of emergency). There is a flow of tasks for delivery and you need to distribute them among couriers as efficiently as possible.
   
2. Arrange the tasks of one courier in a queue so that when bypassing destinations, minimize some parameter. This is usually time, as petrol, distance, and fare are secondary and correlate with time.
   

If you are not trading in "substances", then the courier on the mission is autonomous and cannot accept additional orders. A separate story with "drop into the store and buy vodka", here the autonomy is violated, but in general it doesn't really change anything.
If the case is degenerate, that is, there are many couriers, but there are few orders, then there is no question.
Problems begin when there are a lot of couriers and a lot of orders.
To begin with, I would cluster the address space. Would construct a matrix of "price" of movement between nodes. I would move routing to a separate isolated layer so as not to be heavily dependent on a specific route builder.
You can look, for example, towards OSRM .
I did not look for ready-made services for solving the traveling salesman problem, but you should first look for a ready-made solution. It is not necessary to solve the problem itself completely and find the most efficient route. Enough that he was good enough. In any case, the errors in forecasting traffic jams and other factors will make it meaningless. Approaches to the solution are well listed on the wiki at the link above.
In general, it is technically possible to make it even cooler so that one courier can intercept the second along the way and redistribute part of the orders with him so that the total cost of moving is less.
Here, the courier, it turns out, can also deliver the goods to an arbitrary rendezvous point to another courier.
If you have a multimodal delivery system with foot and "horse" couriers, then some of the goods may be easier to release and deliver along the highway by car, and foot messengers intercept the truck along the way and carry it locally.
You can try to dig deeper into swarm algorithms.
Each act of moving a courier, receiving/transferring goods (from a restaurant to a courier, from a courier to a courier), preparing an order at a particular point of issue is a branching in the decision tree.
Such branches can be real and potential:

• The real ones are irreversible and, in fact, cut off potential branches associated with dependencies.
  
• Potential branches have a price and are dynamically characterized by a number of dependencies. Dependencies can be soft and critical: the larger the increase in the potential price of cutting off the branch, the more critical it is.
  

Where is the swarm algorithm. It is possible to spawn virtual agents that randomly (or guided by neural network signals) select certain branches from the proposed ones. The whole swarm swirls in the potential part of the decision tree. Time is on the heels and real couriers make certain decisions: the system chooses the optimal action for them, or the courier assumes that he will not be in time, or force majeure and a traffic jam. The wall of present time cuts off unreachable potential branches and kills the agents who are on them. This frees up resources and makes it possible to spawn new agents.
The neural network of agents can be mutated within the framework of genetic algorithms.
You can take the marker-pheromone concept of ant colony algorithms. This way it will be possible to mark fast routes with pheromones, and when the situation changes and they become slow, these sections will be re-marked by sorba themselves by the following agents. By the way, no one bothers to make a special type of agents in the multimodal system that will mark routes for vehicles with data from Yandex traffic jams. For walking agents, you can make separate scout ants that mark according to the Strava heat map or some local networks for collecting walking tracks.
In short, welcome to the logistic hell.

Answer 2

There are no such practices. What are you just like a little

Answer 3

Simplex method, shortest path.