Совместная разработка математика Рене ван Беверна, работающего в НГУ, и ученых из Берлинского технического университета (TU Berlin) получила премию за лучшую статью на конференции об алгоритмических подходах к моделированию, оптимизации и системам транспорта ATMOS, которая является частью конференции об алгоритмах ALGO. Ученые разработали алгоритм, позволяющий находить приближенные решения с гарантированной оценкой точности для задач по оптимизации маршрутов транспортных средств с ограниченной грузоподъемностью.
Международная конференция ALGO состоялась 14–18 сентября в Патрах (Греция). Постдок, ассистент кафедры теоретической кибернетики ММФ НГУ Рене ван Беверн, приглашенный в университет в рамках программы по привлечению иностранных специалистов для преподавания и обмена опытом, участвовал в конференции как победитель конкурса поддержки академической мобильности молодых преподавателей НГУ (Проект 5–100).
Ученый представил на конференции об алгоритмических подходах к моделированию, оптимизации и системам транспорта ATMOS, которая является частью конференции ALGO, разработанный совместно с учеными из TU Berlin Кристианом Комузьевичем и Мануэлем Зорге приближенный алгоритм с гарантированной оценкой точности для одной трудной задачи о маршрутизации транспортных средств с ограниченной грузоподъемностью.
Задачи маршрутизации транспорта (ЗМТ) относятся к области комбинаторной оптимизации: для парка транспортных средств, расположенных в одном или нескольких депо, должен быть определен набор маршрутов до нескольких отдаленных пунктов назначения.
Наиболее известная из ЗМТ — задача коммивояжера, для которого необходимо найти самый выгодный маршрут (по времени, расстоянию, стоимости) через n городов и вернуться в исходный пункт.
— Многие ЗМТ, в том числе задача коммивояжера, принадлежат к классу так называемых NP-трудных задач. Это значит, что с сегодняшними знаниями даже в относительно маленьких транспортных сетях невозможно вычислить оптимальные маршруты за приемлемое время. Поэтому ученые во всем мире разрабатывают приближенные алгоритмы с гарантированной оценкой точности, т. е. для наперед заданного числа α они доказывают, что их алгоритм за полиномиальное время находит маршруты не длиннее оптимальных в α раз. Такие алгоритмы называются α-приближенными, а α — оценкой их точности. Если α не зависит от размера транспортной сети, то оценка точности называется константной, — поясняет Рене ван Беверн.
Задача, рассматриваемая в представленной на конференции ATMOS статье «Approximation Algorithms for Mixed, Windy, and Capacitated Arc Routing Problems», имеет, по словам ван Беверна, следующие особенности:
— Задача коммивояжера заключается в том, чтобы найти оптимальный маршрут лишь для одного транспортного средства, обслуживающего заказчиков, находящихся в определенных точках транспортной сети. Это более простая задача, чем та, которую мы перед собой поставили: найти набор маршрутов для целого парка транспортных средств, обслуживающих определенные части самой сети, например, определенные дороги. При этом у каждой обслуживаемой дороги есть свой спрос, а транспортное средство не может удовлетворить спрос свыше своей грузоподъемности. Осложняющим фактором является так называемая асимметрическая модель транспортной сети, где стоимость проезда между пунктами в одном направлении может отличаться от стоимости проезда в обратном направлении. Вопрос о том, существует ли приближенный алгоритм с константной оценкой точности в асимметрической модели для более простой задачи коммивояжера, открыт уже более 30 лет. Для нашей задачи вообще не было приближенных алгоритмов с какой-либо гарантированной оценкой точности.
Математики не дали ответа на давно открытый вопрос, однако, им удалось разработать алгоритм с константной оценкой точности для многих практических сценариев:
— Мы разработали алгоритм с константной оценкой точности для того случая, когда дороги с позитивным спросом формируют малое количество несвязанных между собой компонентов. Например, типичный город в целях вывоза мусора схематично делится на левый берег, правый берег и несколько отдаленных районов. В нашей работе мы доказываем, что во многих практических сценариях для задачи есть приближенный алгоритм с константной оценкой точности. Будут ли наши маршруты на практике лучше тех, найденных прежними алгоритмами, покажут эксперименты.
В перспективе, подчеркивает ван Беверн, этот приближенный алгоритм может иметь широкое применение для развития городской инфраструктуры:
— Алгоритм мог бы потенциально использоваться городскими властями при уборке снега и вывозе мусора, строительными компаниями при проверке целостности структур в зданиях, службами доставки. Однако на данный момент алгоритм существует лишь в теории. Для реализации и испытания его на практике желательно иметь доступ к реальным данным, которые, к сожалению, часто являются коммерческой тайной.
Полученные результаты, по словам автора, имеют значение для теоретической стороны вопроса в целом:
— Мы доказали, что любое улучшение оценки точности для асимметрической задачи коммивояжера влечет улучшение оценки точности нашего алгоритма. Это означает, что если кто-нибудь когда-нибудь решит «давно открытый вопрос» и найдет приближенный алгоритм с константной оценкой точности для асимметрической задачи коммивояжера, то оценка точности нашего алгоритма тоже будет константной, несмотря на количество компонентов, формируемых дорогами с позитивным спросом.
Программный комитет присудил работе Рене ван Беверна, Кристиана Комузьевича и Мануэля Зорге премию за лучшую статью на конференции ATMOS-2015. Статья опубликована в материалах конференции, индексируемых базой данных Scopus.
На фото (слева направо): Христос Заролиагис (глава организационного комитета ALGO-2015, Греция), Мари Шмидт и Джузеппе Ф. Италиано (главы программного комитета ATMOS-2015, Нидерланды, Италия), Рене ван Беверн и Мануэль Зорге (два из трех соавторов работы, Россия, Германия)
Анастасия Аникина
