MWC 2018
2018
Computex
IFA 2018
Классическая задача коммивояжёра связана с выбором оптимального маршрута ко всем пунктам назначения и последующему возвращению домой. Похожая задача решается в процессе экспедиции к нескольким астероидам, ведь на кону стоит экономия ограниченных запасов топлива. Но только с большой оговоркой — астероиды не стоят на месте, они движутся по своим сложным орбитам, что усложняет «космическую» логистику на порядки. И теперь этой задаче нашли решение.
Источник изображения: ИИ-генерация ChatGPT/3DNews
Ведущими авторами исследования были Исаак Рудич (Isaac Rudich) с кафедры математической и промышленной инженерии Политехнического института Монреаля (Polytechnique Montréal) в Канаде и Михаэль Рёмер (Michael Römer), аналитик с факультета делового администрирования и экономики Билефельдского университета (Universität Bielefeld) в Германии.
Технически задача имеет двухуровневую структуру. Внешний уровень — комбинаторный: в каком порядке посещать астероиды. Внутренний уровень — это небесная механика: для каждой пары целевых астероидов нужно найти оптимальное окно вылета и траекторию перелёта. Этот внутренний уровень сводится к вариантам решения задачи Ламберта — определению орбитальной дуги между двумя движущимися телами за заданное время.
Поскольку такой расчёт приходится повторять для множества возможных последовательностей, прямой перебор быстро становится невозможен за разумное время. Поэтому авторы предложили составлять диаграммы решений, которые наглядно представляют значительное множество маршрутов, а также специализированный подход на основе графов, позволяющий отсекать заведомо бесперспективные ветви и уменьшать число вычислений отдельных траекторий.
Для ряда тестовых задач исследователи получили не просто хорошие маршруты, а решения с доказуемой оптимальностью. По их словам, это первое точное решение подобной задачи для космической логистики в условиях, близких к реальным. Это важно не только для гонки за астероидами, но и для других сценариев: многократных сближений с малыми телами, обслуживания спутников, удаления мусора, космической разведки, добычи ресурсов и межпланетной логистики.
Учёные считают, что даже если бы удалось добиться улучшения логистики всего на 1 %, это всё равно означало бы существенную экономию времени, денег и топлива. Их исследование также можно применить для решения проблем на Земле, таких как планирование автобусных маршрутов, цепочек поставок и судоходных маршрутов, где динамику задают погода и пробки на дорогах, пусть даже пункты назначения никуда не перемещаются, как это происходит в космосе.
Источник:
