Диссертация (1145289), страница 50
Текст из файла (страница 50)
Если пересечения нет и сегмент траектории, проходимый судном на данном шаге прогноза, включает конечную точку или конечная точка сегмента находится в окрестности точки B(ψ1 , λ1 ) , то вычисления заканчиваются. В противномслучае увеличивается номер шага i = i + 1 и выполняется переход к п. 2.На базе ограничений (8.1.5) – (8.1.7) и (8.1.9) можно сформировать допустимое множество Ω ∈ E 3 p в пространстве переменных (r, v ) ∈ E 3 p для конечно-мерной задачи оптимизации в виде(r, v )| ρ (t1 , r , v ) < ε , t1 ≤ T1; γ (r ) ⊂ Ω S ; vmin ≤ Vi ≤ vmax , i ∈1, p ; Ω=Tal (r, v ) = 0,где функция ρ(t1 , r, v ) определяется в соответствии с ограничением (8.1.5).Если множество Ω пусто, то не существует маршрута, обеспечивающеговыполнение всех ограничений. В противном случае на множестве допустимыхмаршрутов необходимо выбрать тот, который доставляет минимум функционалувремени J T = J T (r, v ) или расхода топлива J F = J F (r, v ) .Таким образом, задачу формирования маршрута можно представить как задачу конечномерной оптимизации видаJ T (r, v ) →min(r , v )∈Ω ⊂ E 3 p(8.1.10)в случае минимизации времени перехода илиJ F (r, v ) →min(r , v )∈Ω ⊂ E 3 p(8.1.11)в случае минимизации расхода топлива.Задачи (8.1.10), (8.1.11) являются очень сложными для непосредственногопривлечения численных методов поиска решения.
Это, в первую очередь, связано319с высокой размерностью варьируемых векторов, включающих две группы разнородных переменных. Кроме того, сложность вызвана и алгоритмическим заданием существенно нелинейных функций, определяющих критерии и допустимыемножества для оптимизации.Для упрощения решения задач формирования маршрута, разделим переменные, задающие траекторию и скорости движения по ней, и изменим постановки задач оптимизации.Пусть множество допустимых заданных скоростей зависит от выбора вектора r ∈ E 2 p , определяющего траекторию, и имеет вид{}V (r ) = v ∈ E p | ρ(t1 , r, v ) < ε, t1 ≤ T1; vmin ≤ Vi ≤ vmax , i ∈1, p ; Tal (r, v ) = 0 .
(8.1.12)Введем допустимое множество переменных r{}R S = r ∈ E 2 p | γ (r ) ⊂ Ω S , V (r ) ≠ 0/ .(8.1.13)Заметим, что множество R S состоит из векторов r , определяющих допустимыетраектории, по которым возможно движение без нарушения ограничений, формирующих множество V (r ) .На множестве векторов r ∈ R S зададим функциюT (r ) = min J T (r, v ) ,v∈V (r )(8.1.14)где J T (r, v ) вычисляется по приведенному выше алгоритму. Значением функцииT (r ) для вектора r является минимально возможное время перехода от начальной до конечной точки с учетом допустимого множества скоростей V (r ) .Следовательно, вопрос о минимизации времени перехода в рамках принятых соображений может быть поставлен в следующей форме:T (r ) → min , илиr ∈R S()J T r ∗ , v ∗ = min min J T (r, v ) ,r∈R S v∈V (r )(8.1.15)где ( r ∗ , v ∗ ) – обозначение для оптимального решения.
Очевидно, что задача(8.1.15) может быть трактована как некоторое приближение к решению задачи(8.1.10) о минимальном времени движения, но не эквивалентна ей.320Аналогично, по отношению к задаче (8.1.11) введем в рассмотрение функциюF (r ) = min J F (r, v ) .v∈V (r )Значением функции F (r ) для вектора r является минимально возможный расходтоплива за время перехода (от начальной до конечной точки) с учетом допустимого множества заданных скоростей V (r ) .
Соответственно, задачу о минимальном расходе топлива здесь можно трактовать какF (r ) → min , илиr∈R S()J F r ∗∗ , v ∗∗ = min min J F (r, v ) ,r∈R S v∈V (r )(8.1.16)где ( r ∗∗ , v ∗∗ ) – оптимальное решение.Дополнительное обоснование целесообразности перехода к задачам(8.1.15), (8.1.16) состоит в том, что целевые функции и ограничения для задач(8.1.10), (8.1.11) определены только на допустимых траекториях. Иными словами,они заданы только для тех векторов r ∈ E 2 p , для которых выполнено условиеγ (r ) ⊂ Ω S .Отсюда следует, что для указанных задач можно применять только такиечисленные методы, которые генерируют минимизирующие последовательностивекторов{rk }, k = 0,1,2...
,длякоторыхвыполняютсяусловияγ (rk ) ⊂ Ω S , k = 0,1,2... . При этом обязательным этапом является решение отдельной оптимизационной задачи о поиске начального вектора r0 ∈ E 2 p такого, чтоγ(r0 ) ⊂ Ω S .В отличие от указанной ситуации, оптимизационные задачи в вариантах(8.1.15), (8.1.16) свободны от подобных трудностей, поскольку на внутреннихшагах численного метода можно использовать и векторы r ∈ E 2 p , для которыхγ (r ) ⊄ Ω S . Это достигается разделением переменных, позволяющим для любойнедопустимой траектории γ (r ) строить ближайшую к ней траекторию γ (r ′) ⊂ Ω S ,321что существенно повышает эффективность поиска.Таким образом, задачи выбора маршрутов с уменьшением времени движения или с экономией расхода топлива далее будем рассматривать в вариантах(8.1.15) и (8.1.16) на допустимых множествах (8.1.12), (8.1.13).Для решения задач (8.1.15), (8.1.16) могут применяться комбинации различных методов конечномерной оптимизации, например, метод деформируемогомногогранника [30], [79] для оптимизации по переменным, определяющим траекторию, и метод последовательного квадратичного программирования [107] дляоптимального выбора распределения скоростей вдоль траектории.Однако вычислительные затраты, необходимые для решения задачи формирования маршрутов трансокеанских переходов при наличии сложных статических и динамических ограничений, в этом случае оказываются очень большими.Поэтому данный подход практически применим только в случае простых статических и динамических ограничений для переходов с относительно малыми длительностями.
В частности, если отбросить динамические ограничения, его можноиспользовать для построения нижних оценок функционалов времени и расходатоплива.Предлагаемый в настоящей главе подход к поиску оптимальных маршрутовсостоит из следующих этапов.1. Построение графа специального вида с учетом всех имеющихся статических и динамических ограничений и поиск кратчайшего пути на этом графе.
Результат поиска принимается в качестве начального приближения к оптимальномумаршруту.2. Уточнение решения, полученного на первом этапе. Такое уточнение может достигаться двумя путями. Первый из них состоит в оптимизации распределения скоростей v с сохранением найденной траектории r посредством решениязадачи нелинейного программирования вида (8.1.14).
Второй вариант заключается в представлении допустимого множества в задаче (8.1.15) или (8.1.16) конечным набором траекторий в окрестности начального приближения. Далее на каж-322дой траектории из указанного набора выполняется оптимизация распределенияскоростей. В качестве результата принимается тот маршрут, на котором времяперехода или расход топлива наименьшие.Описанный вариант поиска оптимального маршрута является достаточнозатратным в вычислительном плане. В связи с этим для построения грубого приближения к оптимальному маршруту может использоваться и иной подход, который состоит в изначальном представлении допустимого множества в задачах(8.1.15) или (8.1.16) конечным набором допустимых траекторий с последующимпоиском наилучшего маршрута среди этого конечного числа вариантов.
При этомна каждой из указанных допустимых траекторий решается задача оптимизациираспределения скоростей. В случае достаточно точного начального приближениядля оптимизации следует использовать методы нелинейного программирования.В противном случае, в качестве предварительного этапа для получения приближенного к оптимальному распределения скоростей может быть построен специальный граф и выполнен поиск кратчайшего пути на этом графе.В последующих параграфах приведено подробное описание разработанныхалгоритмов поиска оптимальных маршрутов. В параграфе 8.2 рассматриваютсяалгоритмы формирования маршрутов на графах, в параграфе 8.3 – алгоритмыформирования оптимальных маршрутов на конечном наборе траекторий. В параграфе 8.4 приводятся примеры работы указанных алгоритмов.8.2.
Алгоритмы формирования маршрутов на графахПредлагаемые в данном параграфе алгоритмы оптимизации основаны напредставлении маршрутов движения в трехмерном пространстве. В этом случаеисходная задача сводится к поиску траектории в трехмерном пространстве с обходом препятствий, представляющих статические и динамические ограничения.При этом для минимизации времени в пути конечная точка траектории должнаиметь наименьшее возможное значение аппликаты, где ось аппликат представляет время.323На основе трехмерного представления маршрута формируется граф и выполняется поиск кратчайшего пути на этом графе.
В зависимости от минимизируемого функционала ребрам графа присваиваются веса, характеризующие времяв пути или расход топлива. Уточнение полученного приближенного решениядостигается оптимизацией распределения скоростей на найденной траектории.С целью решения задач оптимизации (8.1.15), (8.1.16) представим процессдвижения подвижного объекта по заданному маршруту в трехмерном пространстве. В этом пространстве введем систему координат Oψλ t с началом в точке Oи с координатными осями Oψ , Oλ и Ot . При этом оси Oψ и Oλ представляютгеографические координаты, а ось Ot – текущее время.Рассмотрим статические ограничения, заданные набором замкнутых контуров, например, замкнутый контур Γkg , являющийся границей множества Ω kg иописываемый последовательностью точекΓkg = {(ψ1 , λ1 ), (ψ 2 , λ 2 ),..., (ψ n , λ n )}.(8.2.1)Тогда в трехмерном пространстве в системе координат Oψλ t запретная областьΩ kg , ограниченная контуром (8.2.1), представляет собой множество точек, ограниченное цилиндрической поверхностью с образующей, параллельной оси Ot .Перейдем к рассмотрению запретных зон, определяемых погодными условиями.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
