What algorithm to use for the task?

Question

Programming

The question arose of finding an algorithm for the following task (the condition was compiled by myself by analogy, initially a completely different industry, numbers, properties):
There are 1000 units of goods in the warehouse that need to be delivered in 3 hours.
There is a transport company with 1000 vehicles for delivery.
The delivery time of the goods and the return of the car back to the warehouse can take from 5 to 30 minutes, the car can take only one unit of goods.
Preparing the car (starting) for the first delivery takes 2 minutes.
The time of the car for delivery is paid hourly, for example, one hour costs 100 rubles.
That is, if we send all 1,000 cars for delivery, we will have time to deliver everything in a maximum of 35 minutes, that is, we will meet exactly 3 hours, but the costs will be huge - 1,000 cars * 100 rubles = 100,000 rubles.
It is necessary to create an algorithm that optimizes the schedule so that it can meet 3 hours, but at the same time spend as little money as possible.
The task seems to be similar to the transport task, but with some restrictions (the first start of the car takes 2 minutes, you need to meet 3 hours). Has anyone encountered a similar problem, or can tell me which way to dig?

Answer 1

The problem is reduced to dividing the initial set of goods into groups, the total delivery time of which does not exceed 2:58, but is as close as possible to this value.
The exact solution - enumeration of all options - is not applicable to such a number of loads.
One of the approximate solution methods is the greedy algorithm . Sort the goods in descending order of delivery time. Let's get (1000/(178/30)) = 169 cells and for each cargo from the sorted list we will look through the cells starting from the first one for the possibility of adding cargo to it, taking into account the restrictions.

Answer 2

books.google.ru/books?id=HIaf7DSPtl0C&printsec=fro...
The Assignment Problem, page 163 and so on through the footnotes.
An excellent book to say the least.
PS because your situation is much simpler and the cost of delivery does not depend on the contractor - I would try the following algorithm for a change: sort orders in descending order of delivery time, and loop through them, trying to find the maximum number of order sets with a total delivery time of 1 -2-3 hours.
However, I'm not sure that a hard milimeter has a practical meaning, because in real logistics + -20% for the delivery time is normal.