How to distribute orders among couriers?

Question

Algorithms

The task is to "intelligently" distribute orders among couriers.
There are conditionally 100 orders located throughout the city with coordinates, there is only one exit point, and each courier can take 15 orders and deliver them in a day. I've been scratching my head for two days now, how can I do this correctly? Well, at least it works. Is there any algorithm, well, or advise steps.
An idea comes to mind to divide all orders into segments and provide each segment with its own courier. But here, too, I can not understand how it is possible to divide the whole thing.

Answer 1

Almost exactly your question:
The traveling salesman problem. How to optimize the route for picking up cargo from checkpoints?
Read my comments there. :)

Answer 2

This is a task of scheduling theory, processing tasks by many mobile processors (possibly with due dates if the courier's arrival time is scheduled), and if I do not confuse anything, it is NP-complete. The exact solution is a complete enumeration of all combinations of orders and couriers, it can be optimized a little, see the topics “ Bellman function ”, “ Branch and bound method ”.
In short, we need to consider the recurrent function B_i, which is the set of Pareto optimalsolutions to the problem for i orders, and depends on the parameters of the i-th order and the solution B_(i-1). To find out the specific type of the B_i function, you need to study at the university in a mathematical specialty, and then, as already mentioned here, research the problem for a couple of years (perhaps defending a dissertation along the way). I know a person who received a doctorate for solving a similar problem .
I recommend using a live person (dispatcher), who will manually divide the set of orders into clusters, taking into account the travel time between them, and will also make operational adjustments in the process of delivering orders. According to the cluster, the courier will perfectly orient himself.
You can also use a greedy algorithm , according to the principle:
1) add one fictitious one to the end of the list of couriers (total n + 1 couriers, m tasks);
2) assign a random idle job j and (m/(n + 1) - 1) closest to it to the i-th courier;
3) if there are free couriers, increase i by 1 and go to step (2);
4) distribute the tasks assigned to the fictitious courier to those couriers, to whose starting point they are closer.
A fictitious courier is needed, because usually the latter, with such a distribution, gets fragments from different angles. But the result of the algorithm requires control by a living person.

Answer 3

There are already ready-made solutions for distributing orders among couriers and automatically building routes. Try the EdiCourier system . There, 1000 orders are distributed in 10 minutes. Everything is automated as much as possible, you can connect with your internal systems.

Answer 4

Try https://maxoptra.ru/ , it solves your problem.

Answer 5

You may like the service https://www.routistic.ru/ru