Существует множество подходов к решению данной задачи, среди которых есть только два универсальных – это генетические алгоритмы и метод полного перебора, которые будут описаны в пункте 1.1.2. Остальные же методы решения данной задачи решают его лишь приближенно в общем случае. Рассмотрим один из таких методов – метод кластеризации.
Данный метод описан в работе [4]. В данной работе предлагается сначала провести кластеризацию всех объектов по методу k-средних. Этот метод заключается в том, что все объекты разбиваются на количество кластеров k, равное количеству БЛА следующим образом:
случайным образом на поле решения задачи выбрасывается k точек, которые являются центрами кластеров (центроидами);
каждый объект заносится в кластер того центроида, к которому он находится ближе всего;
после того, как все объекты занесены в кластеры, позиции центроидов пересчитываются таким образом, чтобы суммарное расстояние до всех объектов оказалось минимальным;
шаги 2 и 3 повторяются до тех пор, пока центроиды не перестанут передвигаться.
Таким образом, алгоритм выделяет группы объектов, которые максимально схожи внутри себя, но при этом максимально различны между собой.
После проведения кластеризации к объектам внутри каждого кластера применятся алгоритм «упаковки», суть которого заключается в том, чтобы перевести координаты каждого из объектов в полярные, а замет отсортировать их по углу поворота, а затем по радиусу в порядке возрастания. Таким образом, получается некоторая последовательность облета объектов, которая будет оптимизироваться на следующих шагах.
К полученной последовательности применяется алгоритм имитации отжига (алгоритм поиска минимума некоторой функции), целевой функцией которого является время облета объектов в заданной последовательности.
Последним шагом данного метода является применение алгоритма поиска «Tabu search», суть которого сводится к тому, что в случае, если алгоритм находит решение, которое потенциально является оптимальным, он «запрещает» его, и «разрешает» движение в сторону максимизации времени полета БЛА. Таким образом, алгоритм препятствует «застреванию» поиска в локальных минимумах.
Сильные стороны:
применение множества способов препятствования попаданию в локальные минимумы.
Слабые стороны:
исключение взаимодействия между БЛА;
применяется сразу несколько методов поиска и оптимизации, что существенно увеличивает время расчета;
метод применим только для неподвижных объектов.
Похожие статьи:
Классификация видов услуг
На борту воздушных судов для пассажиров предоставляется огромное множество услуг. Услуги на борту можно поделить на: номинальные, включенные в стоимость авиабилета дополнительные. От классности обслуживания будет зависеть какие услуги будут являться номинальными, а какие дополнительными. Международ ...
Анализ себестоимости
Себестоимость продукции – это денежное выражение затрат предприятия на производство продукции и ее реализацию. Себестоимость рассчитывается делением расходов, относящихся к определенному виду продукции, на количество единиц этого вида продукции. Себестоимость перевозок на железнодорожном транспорте ...
Оценка качества работы маршрутных такси
В практической деятельности автотранспортных предприятий и управлений очень часто встречается необходимость в оценке качества работы, выполняемой отдельными исполнителями, подразделениями и службами. Это делают при подведении итогов работы, а также при оценке качества обслуживания пассажиров в горо ...