Answer the question
In order to leave comments, you need to log in
Algorithm for the transport problem?
Tell me how / what algorithm to solve the following problem:
1) There is a city
2) There are "Used goods buyers"
in the city 3) There are "Used goods sellers" in the city
4) There is a fleet of cars that can deliver goods from "sellers " -> "buyers"
There are a number of restrictions:
1) Different volume of cars
2) Different carrying capacity of cars
3) Working hours of the car (driver and loaders) - (for example, from 9 to 16)
4) Time at which the "Seller" can give the goods "Car" (for example: from 7 to 12)
5) The time at which the goods can be delivered to the "Buyer" (for example, from 14 to 19)
Sample task:
Seller Vasya sells an Old TV (61x100x40 20 kg),can give the goods from 7 to 13
Seller Petya sells Refrigerator (56, 185, 43 30 kg), can deliver goods from 8 to 12
Buyer Misha buys "Old TV", delivery time from 12 to 15
Buyer Dima buys "Refrigerator", delivery time from 13 to
18
Machine 1 - Load capacity 2000 kg, dimensions 200x190x150
Machine 2 - Load capacity 2000 kg, dimensions 200x190x150 Time
must be taken into account for:
1) Moving between points (places of loading and unloading goods)
2) for loading and unloading goods
Example of a manual solution:
10.00 - "Machine 1" at Petya's, loading the refrigerator
11.00 - "Machine 1" at Vasya's, loading the TV
12.00 - "Machine 1" at Misha's, unloading the TV
13.00 - "Machine 1" at Dima's, the Refrigerator is unloaded
There is no single "warehouse" in the task .
It is necessary to draw up a schedule for drivers - what goods and from whom they pick up and to whom they deliver, while minimizing the number of cars used.
At this stage, the exact result is more important than the speed of counting .
Answer the question
In order to leave comments, you need to log in
For a small number of machines and events, it is solved by dynamic programming on the event graph.
For a large number - there is no exact solution, but genetic algorithms have proven very well (the result is suboptimal with an error of no more than 3% of the optimal).
Didn't find what you were looking for?
Ask your questionAsk a Question
731 491 924 answers to any question