Математики НГУ показали эффективную редукцию данных для классической задачи маршрутизации транспорта

Press/Media: Press / Media

Description

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

Subject

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

Period15 Oct 2020

Media contributions

2

Media contributions

  • TitleМатематики НГУ показали эффективную редукцию данных для классической задачи маршрутизации транспорта
    Degree of recognitionRegional
    Media name/outletсайт НГУ
    Media typeWeb
    CountryRussian Federation
    Date15.10.2020
    PersonsРене Андреасович ван Беверн, Оксана Юрьевна Цидулко
  • TitleМатематики НГУ показали эффективную редукцию данных для классической задачи маршрутизации транспорта
    Degree of recognitionRegional
    Media name/outletНовости сибирской науки
    Media typeWeb
    CountryRussian Federation
    Date15.10.2020
    PersonsРене Андреасович ван Беверн