Заведующий лабораторией алгоритмики Механико-математического факультета Рене ван Беверн, младший научный сотрудник лаборатории алгоритмики ММФ Оксана Цидулко и аспирант Берлинского технического университета Тиль Флюшник предложили новый подход к решению одной классической труднорешаемой задачи маршрутизации транспорта — обобщения задачи коммивояжера и задачи о семи кенигсбергских мостах. Если транспортная сеть слишком большая для нахождения коротких маршрутов за приемлемое время, математики показали, как ее можно уменьшить, чтобы короткие маршруты для уменьшенной сети переносились на короткие маршруты для исходной сети. Поэтому достаточно решать задачу в уменьшенной сети. В вычислительных экспериментах транспортные сети сжимаются до 60% исходного размера при удлинении маршрутов всего на 1%. Результат опубликован в специальном выпуске по маршрутизации транспорта международного журнала Networks.
В рамках задачи, известной как «задача деревенского почтальона», необходимо найти кратчайший замкнутый обход в графе, включающий заданное подмножество его ребер.
Интуитивно требуется кратчайший замкнутый маршрут в транспортной сети для уборки снега с заданных дорог. Задача в этом простом виде также возникает при дистанционном снятии показаний со счётчиков, при резке металла и при решении куда более общих задач маршрутизации транспорта: например, ещё в 2015 году ученые НГУ и TU Berlin доказали, что улучшение качества решений для задачи деревенского почтальона непосредственно приводит к улучшению качества решений задач с несколькими транспортными средствами с ограниченной вместимости, за что они получили премию за лучший результат на международной конференции по алгоритмам маршрутизации транспорта.
— Задача о деревенском почтальоне относится к так называемым APX-трудным задачам. Поэтому трудоёмкость алгоритмов не только для оптимального решения, но даже для хорошего приближённого решения растёт экспоненциально с объемом входных данных. То есть если вдруг придётся почистить на одну дорогу больше, время работы алгоритма условно удвоится. И если вы сегодня купите суперкомпьютер, который оптимально решает задачу на сети из 1000 дорог за секунду, то над 1010 дорогами он будет работать уже 17 часов, а над 1020 дорогами — два года. Но это также указывает на возможный подход к решению задачи: ведь если удастся из транспортной сети удалить хотя бы одну дорогу, то алгоритм будет работать в два раза быстрее. Разумеется, нельзя просто так удалять какие угодно дороги из сети, ведь найденный в такой «испорченной» сети оптимальный маршрут может вовсе не оказаться оптимальным для исходной транспортной сети, — объяснил Рене ван Беверн.
Ученые выяснили, как нужно удалять дороги из транспортной сети, чтобы хорошие (или оптимальные) маршруты для уменьшенной сети переносились на хорошие (или почти оптимальные) маршруты для исходной сети.
— Допустим, компания предлагает ПО для маршрутизации транспорта, но у ее заказчиков транспортные сети достигли размеров, при которых ПО уже не работает за приемлемое время. Тогда компания может легко применить наш алгоритм в своем ПО. Достаточно задать алгоритму «требуется уменьшить эту транспортную сеть так, чтобы маршруты удлинились не более, чем на х%», и алгоритм сожмет транспортную сеть до размера, зависящего от этих заданных х%. Потом существующее ПО может быть применено к уменьшенной сети, оно в ней найдёт хороший маршрут, и наш алгоритм превратит его в маршрут для исходной сети. При этом алгоритм гарантирует, что полученный таким подходом маршрут будет не более чем на x% длиннее, чем маршрут, который мы бы построили в исходной сети. Тут x — любое число больше нуля, — отметил новосибирский ученый.
Исследования проводятся в рамках совместного проекта НГУ и TU Berlin под совместной поддержкой Российского фонда фундаментальных исследований и Немецкого научно-исследовательского общества.
