Оптимизация съемки распределенных участков земной поверхности с использованием методов комбинаторики

В силу разнообразия задач по изучению земной поверхности с использованием космических и авиационных съемочных систем возможны различные условия их применения, один из вариантов которых состоит в получении изображений нескольких участков земной поверхности, компактно распределенных в локальном районе. Подобная ситуация имеет место при мониторинге распределенных природно-техногенных комплексов, оценивании последствий стихийных бедствий на территориях населенных пунктов. В таком случае критическое значение имеет своевременность получения объективной информации при ограниченном съемочном ресурсе.
Подходы к планированию съемки на основе точных и эвристических методов комбинаторики приобретают особую актуальность в условиях, когда район съемки является крупномасштабным с множеством распределенных по его площади малоразмерных съемочных участков, покрытие которых затруднено из-за недостатка временного технического ресурса или его ограниченности. При этом формирование программы полета для воздушного судна или программы перенацеливания космического аппарата для последовательной съемки нескольких участков на местности сопровождается решением задачи по построению маршрута, обеспечивающего рациональность применения используемой техники. Таким возможным путем для формирования съемочного маршрута является решение «задачи коммивояжера» (ЗК), широко применяемой в сферах логистики, маршрутизации транспорта, планирования производств, анализа данных и др.
Построенный указанным образом съемочный маршрут принимается за оптимальный. В настоящее время практикуются разные по точности эвристические методы (алгоритмические стратегии) решения ЗК, например: «грубой силы», «ветвей и границ», «ближайшего соседа», «муравьиный алгоритм» и др. Указанные методы подразумевают вычисления различной сложности и характеризуются различной ресурсоемкостью, что также сказывается на времени решения задачи. Таким образом, для обоснованного выбора метода решения ЗК для формирования съемочного маршрута, необходимо учитывать количество участков в пределах района и ограничения, накладываемые на время вычислений.
Цель исследования состоит в сравнении результатов построения съемочных маршрутов на основе точного и эвристических методов комбинаторики, базирующихся на различных подходах к решению ЗК. Полученные результаты могут быть использованы при составлении программы съемки множества участков, расположенных в пределах одного района, в ходе мероприятий планирования.
Для выбора средства оптимального решения ЗК с целью составления съемочного маршрута в условиях временных и ресурсных ограничений проведено исследование, в рамках которого тестировались и сравнивались между собой различные методы комбинаторики. В качестве точного (эталонного) метода принят метод «грубой силы», подразумевающий поиск кратчайшего пути путем полного перебора всех возможных вариантов съемочного маршрута. При этом метод «грубой силы», обеспечивающий самый простой и точный подход к решению ЗК, в условиях большого количества участков съемки не применим на практике в силу значительных требований к вычислительным ресурсам. Снизить вычислительную сложность процедуры поиска оптимального съемочного маршрута предлагается путем использования альтернативного подхода к решению ЗК.
С этой целью проведены исследования, в рамках которых с эталонным методом «грубой силы» по показателям времени и точности вычислений сравнивались другие, в том числе эвристические, методы комбинаторики: «ветвей и границ», «ближайшего соседа» и «муравьиный алгоритм». Анализ результатов исследований выбранных методов показал, что наиболее точным и быстрым из исследуемых решений ЗК стало использование «муравьиного алгоритма». В условиях эволюции района съемки, роста количества участков съемки и ужесточения временных ограничении к планированию применения ВС указанный метод комбинаторики обладает явными преимуществами для вычисления оптимальных съемочных маршрутов.
Таким образом, полученные результаты могут использоваться для обоснованного выбора метода комбинаторики, наилучшим образом подходящего для оптимизации съемочного маршрута. Результаты исследования целесообразно использовать в интересах разработки средств планирования съемки земной поверхности в условиях роста количества малоразмерных участков в пределах съемочного района и при наличии временных ограничений.