Hello. We set the following task: There are two dynamic lists, the first is the list of couriers, the second is the list of orders for the last 24 hours. It is necessary to effectively distribute orders among couriers. Namely: each courier has a working time (from how long - to how many), the carrying capacity of his car, and the maximum amount of cargo for one shipment. Orders have corresponding fields. So actually the question is how to effectively distribute? The problem is, if there are, for example, several small orders that are suitable in time, then distribute them accordingly to the courier with a small volume and carrying capacity of the car, and large orders to other couriers. But it may happen that the last courier to be distributed cannot take a large order, since It does not work at this time, but it works at the time when you need to deliver, for example, 2 small ones that are already distributed. Then you need to somehow redistribute small orders for the last, and large orders to the "small" courier. Actually, help with advice :)
- Still relevant ... - Eugene Shilin
- one@ Yevgeny Shilin, while the criterion of effectiveness (yes, it seems, and some other restrictions) you have defined purely intuitively . In general, the task is not easy. Something from a series of dynamic programming. - avp
- It looks like linear programming, try to dig in the direction of the simplex method . - VladD
- avp, Well, as I understand it, efficiency here is rather abstract in nature, because in practice I cannot use this distribution system in my opinion. VladD, thanks. - Eugene Shilin
- @VladD, isn’t the simplex method suitable for discrete optimization? - avp
1 answer
You can choose several approaches. The first. This is a backpack task. It will have to be slightly modified. You can read about the usual backpack problem here:
I would advise you to take a look at informats. Not only can you read a valid theory there with examples. In addition, you can try to write a task and submit it to a testing system. On the same site can be found in the examples of problems analysis of solutions published by someone. Here you can find something sensible, and not so. But here, too, is worth a look. 
. The parse opens when you click on the blue inscription "parse", located under the name of the task.
Codeforces.ru and timus.ru - here you can find tasks for various subjects of DP. Including a backpack.
As for the Gomory method. That on the Internet is full of online solvers, with which you can deal with the course of action. In more detail you can google the book Panteleev and Letova. There are two editions. In one it is written a little more, in the other - a little less. Here and here . The Gomory method allows you to solve your problem in whole numbers. This is the same simlex method that iterates over the vertices of a multidimensional polygon. After that, in the vicinity of the obtained points, it searches for the best integer solution by solving inequalities in integers. It is not difficult. Read.
The Gomory method is quite a universal thing. But it will be problematic to code. I would advise to deal with the backpack problem, since the solution will be more compact. But there will be no universal solution. We'll have to reinvent the small bike.
With regard to the criterion of efficiency, as a criterion, you can minimize the time spent on transportation, or the volume of cargo. Or both that, and another. But I would not advise taking both. At least in the beginning. In this case, you will have several objective functions. And working with it is more difficult. In addition, you can combine this into a nonlinear functional. For example, minimize the scalar product of vectors
(X, T) = x1 * t1 + x2 * t2 + ... + xn * tn, where X is the volume of the transported load, T is the time. But in this case, the problem will not have an exact solution. At least when solved by the Gomory method. In this formulation, it is nonlinear.
In any case, it all depends on your requirements. What does your task solve? Who needs it?
As soon as you deal with these methods. Choose what you want, and most importantly, why you want it, write here. Let's try to figure out if you have any questions.
