0 like 0 dislike
9 views
For example, there is an Agency for courier services in the city. Let's say you have 5 couriers. Metro, buses and couriers to walk also know how Every courier needs to go to a few places.

The question is — HOW to find a better (time (primarily) and money) route? (algorithm). Yes, it is the task of kommivoyazhera, but little changed.

I would like to have the program sent a courier from branch to branch station by bus in 10 minutes and 20 rubles instead of the subway through the center in 40 minutes and 19 rubles.

ie there is a list of metro and the address where to take (the subway is bound to the address). There are 5 couriers and 25 assists which need to conduct (5 each). Everyone needs the courier to convey the 5-speed to the time and cost was optimal. Well, the weight there.

How to imagine what it is... is not alone. Already mentally prepared for the full bust, but can't come up with an algorithm
| 9 views

0 like 0 dislike
Figured. In General, you need somewhere to get a list of routes and pull from somewhere the subway map. Then you will need to build a complete graph of the values of travel from each stop for each. This is done once. Then, when you distribute a package, it will be necessary to find again the shortest routes between waypoints using a prior prepared a graph of price movements. And on this count point to point to do an exhaustive search. Resources to eat a lot must not, and we have not the Olympics, when you have a second to meet. Something like this.
by
0 like 0 dislike
You have some 25 assists, and 5 couriers. For such volumes, we can safely use the full search and not to bother. The only construct complete graph travel costs from each point to each.
by
0 like 0 dislike
Then for every destination tied to the 3 closest stations. And looking for shortest paths from each point to kajou + to the point of sending. And on the basis of these data it is possible to draw an exhaustive search of the possibilities. Something like this.
by
0 like 0 dislike
Still need to decide on a weight integration and time is money, and in any case according to two criteria optimization is not done and there are two ways:
1) put one of the criteria in the restriction, for example no longer than a day to be delivered all parcels
2) enter the weighting function, but here it is necessary to oterminal time and money, such as time to the number of hours in the working day, and the cost to the maximum budget of the courier.
by
0 like 0 dislike
Robin, of course. And as written above, using "dynamic programming," i.e., to remember and to use already calculated the options and sub-options.
\r
In real life, these tasks we try to solve the zonal method. And for Moscow and probably St. Petersburg in the form of sectors around the metro. To the sector for movement. Sectors can slightly overlap each other. Then the lemmings to select a route based on the preference to be in the same sector or max related. Well, the number of points taken into account. You can continue to take into account their remoteness and the sequence of bypass ask.
\r
Just solve by brute force on the full map is to build a metro line, ground transport, consider the water hazard, the fucking railroad tracks, tube, and costs harder to calculate. You end up with one carrier, 50% will use, and the other at 150%.
by

0 like 0 dislike