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

Пресса/СМИ: Новостная публикация

Описание

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

Предмет

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

Период15 окт 2020

Материалы СМИ

2

Материалы СМИ

  • ЗаголовокМатематики НГУ показали эффективную редукцию данных для классической задачи маршрутизации транспорта
    Степень признанияРегиональная
    Название СМИсайт НГУ
    Тип подачи информацииВеб
    СтранаРоссийская Федерация
    Дата публикации15.10.2020
    ПерсоныРене Андреасович ван Беверн, Оксана Юрьевна Цидулко
  • ЗаголовокМатематики НГУ показали эффективную редукцию данных для классической задачи маршрутизации транспорта
    Степень признанияРегиональная
    Название СМИНовости сибирской науки
    Тип подачи информацииВеб
    СтранаРоссийская Федерация
    Дата публикации15.10.2020
    ПерсоныРене Андреасович ван Беверн