The traveling salesman problem

Question

Algorithms

Suppose there is an agency of courier services in the city. Let there be 5 couriers. Metros, buses and couriers can also walk. Each courier has to go to several places.

Question - HOW to lay the optimal (in terms of time (primarily) and money) route? (algorithm). Yes, this is the traveling salesman problem, but slightly modified.

I would like the program to send a courier from metro line to metro line by bus in 10 minutes and 20 rubles, and not by metro through the center in 40 minutes and 19 rubles.

those. there is a list of the metro and the address where to take it (the metro is tied to the address). There are 5 couriers and 25 transfers to be made (5 for each). It is necessary for each courier to transfer 5 transmissions so that the time and cost are optimal. Well, the weight is there, too.

As I imagine what it is ... it becomes uncomfortable. Already mentally prepared for a complete enumeration, but I can’t come up with an algorithm yet

Answer 1

Figured it out. In general, you need to get lists of routes somewhere and pull out a metro map from somewhere. After that, you will need to build a complete graph of the costs of moving from each stop to each. This is done once. Then, when distributing parcels, you will again need to find the shortest routes between travel points, using a previously prepared graph of travel prices. And already on this point-to-point graph, do a complete enumeration. There shouldn't be a lot of resources to gobble up, and we don't have an Olympiad when we need to meet in a second. Something like that.

Answer 2

You have some 25 transfers and 5 couriers. On such volumes, you can safely use full enumeration and not bother. The only thing is to build a complete graph of moving prices from each point to each.

Answer 3

After that, for each destination, we bind to the 3 nearest stations. And we are looking for the shortest paths from each point to each + to the point of departure. And already on the basis of these data, you can draw a complete enumeration of possibilities. Something like that.

Answer 4

You also need to decide on the time-money weighting function - in any case, optimization is not done according to two criteria, and there are two ways:
1) set one of the criteria as a restriction, for example, all parcels are delivered no longer than a day
2) introduce a weight function, but here it is necessary to normalize time and money, for example, time to the number of hours in a working day, and cost to the maximum budget of the courier.

Answer 5

Overkill, of course. And as written above, using "dynamic programming", i.e. memorize and use already calculated options and sub-options.
In real life, they try to solve such problems in a zonal way. And for Moscow and, probably, St. Petersburg in the form of sectors around the metro lines. To make it convenient to move around in the sector. Sectors may overlap slightly. Then, for lemmings, you select a route based on the preference to be in one sector or at most adjacent ones. Well, take into account the number of points. You can further take into account their remoteness and set the sequence of bypass.
It’s easy to solve by brute force on a full map - it’s building subway lines, ground transport, taking into account water barriers, fucking railway tracks, traffic jams, the fare is more difficult to calculate. As a result, you will use one courier for 50%, and the other for 150%.