Description

Заведующий лабораторией алгоритмики Механико-математического факультета Рене ван Беверн, младший научный сотрудник лаборатории алгоритмики ММФ Оксана Цидулко и аспирант Берлинского технического университета Тиль Флюшник предложили новый подход к решению одной классической труднорешаемой задачи маршрутизации транспорта — обобщения задачи коммивояжера и задачи о семи кенигсбергских мостах. Если транспортная сеть слишком большая для нахождения коротких маршрутов за приемлемое время, математики показали, как ее можно уменьшить, чтобы короткие маршруты для уменьшенной сети переносились на короткие маршруты для исходной сети. Поэтому достаточно решать задачу в уменьшенной сети. В вычислительных экспериментах транспортные сети сжимаются до 60% исходного размера при удлинении маршрутов всего на 1%. Результат опубликован в специальном выпуске по маршрутизации транспорта международного журнала Networks.

Subject

Заведующий лабораторией алгоритмики Механико-математического факультета Рене ван Беверн, младший научный сотрудник лаборатории алгоритмики ММФ Оксана Цидулко и аспирант Берлинского технического университета Тиль Флюшник предложили новый подход к решению одной классической труднорешаемой задачи маршрутизации транспорта — обобщения задачи коммивояжера и задачи о семи кенигсбергских мостах. Результат опубликован в специальном выпуске по маршрутизации транспорта международного журнала Networks.