Head of the Laboratory of Algorithmics of
Rene van Bevern, junior researcher at the Laboratory of Algorithmics
Oksana Tsidulko and a graduate student of the Technical University of Berlin
Till Flushnik proposed a new approach to solving a classic transport routing problem 鈥� a generalization of the travelling salesman problem and the problem of seven Konigsberg bridges. If the transport network is too large to find the shortest routes in a reasonable amount of time, mathematicians have shown how it can be reduced so that short routes for the reduced network are carried over to short routes for the original network. Therefore, it is sufficient to solve the problem in a reduced network. In computational experiments, transport networks are compressed to 60% of their original size while the routes are lengthened by only 1%.
Within the framework of the problem, known as the "village postman problem", it is necessary to find the shortest closed trail in a graph that includes a given subset of its edges.
Intuitively, the shortest closed trail in the transport network is required to clear snow from specified roads. The problem in this simple form also arises when monitoring readings from meters remotely, when cutting metal and when solving much more general transport routing problems: for example, back in 2015, scientists from NSU and TU Berlin proved that improving the quality of solutions for the problem of a village postman directly leads to improve the quality of solutions to problems with several vehicles with limited capacity, for which they received an award for the best result at the international conference on transport routing algorithms.
Rene van Bevern explains:
The village postman problem belongs to the so-called APX hard problems. Therefore, the complexity of the algorithms not only for the optimal solution, but even for a good approximate solution grows exponentially with the volume of input data. That is, if you suddenly have to clean one more road, the running time of the algorithm will conditionally double. And if you buy a supercomputer today that optimally solves a problem on a network of 1000 roads in a second, then it will work on 1010 roads for 17 hours already, and on 1020 roads 鈥� two years. But this also indicates a possible approach to solving the problem: after all, if it is possible to remove at least one road from the transport network, then the algorithm will work twice as fast. Of course, you can't just remove any roads from the network, because the optimal route found in such a "damaged" network may not be optimal at all for the original transport network.
Scientists figured out how to remove roads from the transport network so that the good (or optimal) routes for the reduced network are carried over to the good (or near-optimal) routes for the original network.
The Novosibirsk scientist notes:
Let's say a company offers software for transport routing, but its customers' transport networks have reached the size at which the software no longer works in an acceptable time. Then the company can easily apply our algorithm in their software. It is enough to set the algorithm "it is required to reduce this transport network so that the routes are lengthened by no more than x%", and the algorithm will compress the transport network to a size depending on these specified x%. Then the existing software can be applied to the reduced network, it will find a good route in it, and our algorithm will turn it into a route for the original network. In this case, the algorithm guarantees that the route obtained by this approach will be no more than x% longer than the route that we would have built in the original network. Here x is any positive number.
The research is carried out within the framework of under the support of the Russian Foundation for Basic Research and the German Research Society.
