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

Good day!

Sawing system of delivery of food from restaurants, like Yandex.Food or Deliveries.
Accordingly, the desired algorithm, which is based on the data about orders and data on the location of couriers to give the couriers the optimal objectives for the next move.
Thought maybe such algorithms is somewhere in public or someone might share their experience?
April 19th 20 at 12:27
4 answers
April 19th 20 at 12:29
Interesting problem you have: NP-complete, but under the constraints of the real world manageable.
Your salesman is a limited resource in the number of delivery points. Delivery, probably need to do it within that time frame (while hot).
Total your task is split into two:
  1. To distribute the orders among couriers. Moreover, some carriers are still in transit, some in reserve. For example, couriers you 7: one for the road far away, another on the way and three are under load (plus two in reserve waiting in the wings in case of contingencies). There are a number of objectives for delivery and should be distributed among the couriers as efficiently as possible.
  2. To put the task to one of the courier to the queue so that when the bypass destination points to minimize a parameter. Usually this time, as gasoline, distance and travel cost secondary and correlated with time.

If you are not "substances" haggling, the courier on a mission offline and cannot accept additional orders. A different story with "the call to the boutiques and buy vodka", then autonomy is violated, but overall nothing really changes.

If this is a degenerate case, that is a lot of couriers and orders a little, then there is no question.
The problem starts when a lot of couriers and a lot of orders.

For a start I'd spent the clustering of the address space. Would build a matrix of "price" of travel between nodes. They took to the routing on a separate isolated layer, so as not to be strongly dependent on the specific Builder routes.
You can look, for example, in the OSRM.

I was not looking for ready-made services for solving the travelling salesman problem, and you ought to first look for a ready solution. The task itself do not have to solve completely and find the most efficient route. Enough that he was good enough. In any case, the error of predicting traffic jams and other factors will make it meaningless. Approaches to well listed on the wiki at the link above.

It is technically possible to do even cooler to one of the second courier can intercept and redistribute with him of the orders so that the total cost of movement was less.
Here the courier, it turns out, can deliver the goods even in a random rendezvous point to another courier.
If you have a multi-modal delivery system with Hiking and "horse" couriers, the merchandise may possibly be easier to release and deliver the trunk of the car, and foot messengers intercepted the truck along the way and spread locally.
You can try the deeper you dig swarm algorithms.
Every act of the courier's movements, acceptance/transfer of the goods (from the restaurant to the courier from the courier to the courier), preparation of the order in a particular issuing point is betweenie in the decision tree.
Such branching can be real and potential:
  • Real and irreversible in its fact cut off a potential branch associated dependencies.
  • Potential branches have their price and dynamically characterized by the number of dependencies. Dependencies are soft and critical: the more potentially increase prices will result in clipping the branches, the more it is critical.

Where is the swarm algorithm. You can spawn virtual agents that randomly (or guided by signals of the neural network) choose one or the other branch of the proposed. The entire swarm swirling in the potential of the decision tree. Time is running along and the real couriers take certain decisions: the system them selects the optimal action, or courier assumes no time or force majeure and tube. Wall present unattainable potential cuts off the branches and kills the agents that they were. This frees up resources and enables spaunit ' new agents.
Neural network agents can mutate in the framework of genetic algorithms.
You can take a marker pheromone concept of ant algorithms. So will the pheromones be marked the fastest routes, and when the situation will change and they will become slow, these areas will be relabeled themselves serboi the following agents. Incidentally, nobody prevents a multimodal system to do a special kind of agents that would mark routes for vehicles data from Yandex traffic jams. For Hiking agents, you can make otdelnyj ants scouts who mark according heat map of Strava or some local networks of Hiking tracks.

In short, welcome to pojalovat logistics adok.
Wow! Thanks for the super valuable comment!) We can think about! - ole24 commented on April 19th 20 at 12:32
@ole24, Yes there was... nothing. Tryndet - no bags to roll. The hardest part is then debugging, analysis and justification of this Sodom and Gomorrah to do=). - Arely.Macejkovic34 commented on April 19th 20 at 12:35
April 19th 20 at 12:31
There are no such developments. You just like a little
Not the fact what not)
These services are sawed for hundreds of companies over the last 10 years. It is a chance that someone can to share them. - ole24 commented on April 19th 20 at 12:34
@ole24, Yes, they sawed hundreds of companies. They pay their developers for millions of dollars. And so no one with you for free will not share.
You just like a little - bennie.Goldner commented on April 19th 20 at 12:37
@bennie.Goldner, but in fact it is now in Russia for example are only Yandex and Delivery. And the other hundreds of developers who have participated in such projects, there is a chance that you can share your knowledge.
At least in the format: "the Basic algorithm such that, pay attention to that fact, we had such a problem, so decided that." - ole24 commented on April 19th 20 at 12:40
@bennie.Goldner, otherwise it turns out that nobody needs to share the experience gained on the job?) However, experience of similar sites suggests otherwise) - ole24 commented on April 19th 20 at 12:43
@ole24, you are naive Chukchi boy. Himself a contradiction.
>"otherwise it turns out that nobody needs to share the experience gained on the job?) However, experience of similar sites suggests otherwise)"

So, where is this experience?

This is what I'm telling you, Padawan - bennie.Goldner commented on April 19th 20 at 12:46
So, where is this experience?

There is but so so. Out OSM, OSRM is the same. Of course, the more specific the task, the less solutions are available, however they come across Kustanai and harder in implementation. And so no one bothers to stir up the open-source project with this theme. Open source is good if resources are not many, the task popular, but by itself money does not bring, since it relies on malomobiljnykh business.
At the same time there's the same OSRM in a cool usable product grew. Take it and enjoy it in commercial projects.
And there are many such. - Arely.Macejkovic34 commented on April 19th 20 at 12:49
April 19th 20 at 12:33
the facility location problem (facility location problem)

solved any classical heuristics, for example. genetic algorithm
Thank you! We will see this algorithm. - ole24 commented on April 19th 20 at 12:36
April 19th 20 at 12:35
The simplex method, shortest path.

Find more questions by tags Algorithms