Диссертация (1145289), страница 53
Текст из файла (страница 53)
С учетом (8.2.9),()для того чтобы точка M 3' ψ 3'' , λ''3 , t3'' попадала в ε -окрестность исходного маршрута достаточно, чтобы выполнялось условие4c12a12 + b12+≤ ε2 .4((8.2.10))(Далее, для того чтобы точка M 3' ψ 3'' , λ''3 , t3'' была достижима из точки M 2' ψ '2' , λ''2 , t 2''())за время t3' − t2' + ∆t3 − ∆t2 достаточно, чтобы выполнялось условиеa12 + b12 ≤ V2 (∆t3 − ∆t2 ) .(8.2.11)Заметим, что0 < ∆t3 − ∆t2 < 2c1 .Тогда вместо сети с параметрами a1, b1, c1 построим новую сеть с параметрамиψ 3' − ψ1'λ'3 − λ'1t3' − t1', b2 =, c2 =,a2 =N 2tN 2ψN 2λгде натуральные числа N 2ψ , N 2λ , N 2t выбираются так, чтобы для величин a2 , b2 , c2выполнялись условия (8.2.7), (8.2.8), (8.2.10) и (8.2.11).
Ясно, что новые значенияпараметров a2 , b2 , c2 будут не больше соответствующих значений предыдущихпараметров a1 , b1 , c1 .Повторим приведенную выше процедуру (i − 1) раз, в результате чего получим сеть с параметрами ai −1 , bi−1 , ci −1 . При этом все точки построенного пути()M 1 ψ1' , λ'1 , t1' ,()M 2' ψ '2' , λ''2 , t2'' ,()M 3' ψ 3'' , λ''3 , t3'' , …,окрестности исходного маршрута (r, v ) .(M i' ψ i'' , λ''i , ti'')находятся в ε -336Рассмотрим теперь общий случай для участка ломаной, соединяющего точ-()()ки M i ψ i' , λ'i , ti' и M i +1 ψ i' +1 , λ'i +1 , ti'+1 .
Найдем ближайшую к точке M i +1 точку сети спараметрами ai , bi и ci среди точек, расположенных в плоскости t = ti''+1 этой сети,где ti''+1 ≥ ti'+1 , но при этом (i − 1)ci −1 ≤ ∆ti +1 = ti''+1 − ti'+1 ≤ ici −1 . Тогда для минимальногорасстояния ρ min выполняется неравенствоρmin ≤∆ti2+1ai2−1 + bi2−1ai2−1 + bi2−12 2.+≤ i ci −1 +44()(8.2.12)()Обозначим через M i'+1 ψ i''+1 , λ''i +1 , ti''+1 ближайшую к M i +1 ψ i' +1 , λ'i +1 , ti'+1 точку, при-()надлежащую трехмерной сети. Тогда для того, чтобы точка M i'+1 ψ i''+1 , λ''i +1 , ti''+1 попадала в ε -окрестность исходного маршрута достаточно, чтобы выполнялось условиеi 2ci2−1ai2−1 + bi2−1+≤ ε2 .4(8.2.13)() была достижима из точки− ∆t ) достаточно, чтобы выполнялось условиеНаконец, для того чтобы точка M i'+1 ψ i''+1 , λ''i +1 , ti''+1()(M i' ψ i'' , λ''i , ti'' за время ti'+1 − ti' + ∆ti +1iai2−1 + bi2−1 ≤ Vi (∆ti +1 − ∆ti ) .(8.2.14)Нетрудно убедиться в том, что0 < ∆ti +1 − ∆ti < ic1 .Соответственно, вместо сети с параметрами ai −1 , bi−1 , ci −1 построим новую сеть спараметрамиti'+1 − t1'ψ i' +1 − ψ1'λ'i +1 − λ'1ai =, bi =, ci =,N itN iψN iλгде натуральные числа N iψ , N iλ , N it выбираются так, чтобы для величин ai , bi , ciвыполнялась вся совокупность условий вида (8.2.13), (8.2.14) для всех значенийj = 1, i − 1 .Повторяя данную схему p раз, получим сеть с параметрами a p , b p , c p .
При337()этом все точки построенного пути, принадлежащие данной сети, M 1 ψ1' , λ'1 , t1' ,()()()M 2' ψ '2' , λ''2 , t2'' , M 3' ψ 3'' , λ''3 , t3'' , …, M p' +1 ψ 'p' +1 , λ''p +1 , t 'p' +1 находятся в ε -окрестностиисходного маршрута (r, v ) . Это значит, что время перехода для построенногомаршрута отличается от исходного маршрута не более, чем на величину ε . ■8.3. Алгоритмы формирования маршрутовна конечном наборе допустимых траекторийПриводимые ниже алгоритмы базируются на представлении допустимыхмножеств в задачах (8.1.15), (8.1.16) конечными совокупностями допустимыхтраекторий.
Ясно, что это не гарантирует достижение экстремума, однако можнополучить определенное приближение к нему с вполне реальными вычислительными затратами на формирование маршрута.Для реализации предлагаемых алгоритмов вначале необходимо построитьнабор траекторий, допустимых по отношению к статическим ограничениям. Далее на каждой траектории из набора с помощью соответствующего алгоритмарешается задача оптимизации распределения скоростей в варианте (8.1.14) или(8.1.16).Последовательно рассмотрим алгоритмы построения наборов траекторий иоптимизации распределения скоростей.Существует большое разнообразие возможных методов для построения наборов траекторий.
Самый простой способ, рассматриваемый ниже, заключается визначально равномерном геометрическом покрытии района плавания с последующей корректировкой траекторий на допустимость с учетом статических ограничений.Другой способ может состоять, например, в построении набора траекторийв окрестности некоторой заданной судоводителем траектории. Этот вариант, вчастности, удобен для уточнения маршрута, полученного в результате поиска пути на графе, как описано в п. 8.2. Иные, более сложные варианты построения мо-338гут дополнительно учитывать известный прогноз погоды для района плавания.Рассмотрим алгоритм формирования набора траекторий, равномерно покрывающих область плавания. Исходно задаваемыми параметрами для данногоалгоритма служат: число траекторий в наборе, максимальная длина одного участка траектории и ширина набора траекторий, определяющая охватываемую данным набором область.Алгоритм № 1 построения набора траекторий.1.
Формируется траектория, соединяющая начальную и конечную точки полинии прямого курса.2. Строится набор траекторий, расположенных выше и ниже траекториипрямого курса. Построение осуществляется таким образом, чтобы заполнить всюобласть между крайними траекториями в определенном смысле равномерно.3. Проверяется допустимость каждой траектории из полученного на шаге 2набора.
При этом учитывается, что каждой из них соответствует векторri ∈ E 2 p , i ∈1, N , где N – число траекторий в наборе, p – число участков каждойтраектории. Иными словами, проверяется выполнение условий γ (ri ) ∈ Ω S , i = 1, N :если траектория γ (ri ) допустима, то вектор ri оставляется без изменений. В противном случае, строится ближайшая допустимая траектория, и вектор ri заменяется соответствующим вектором ri′ , определяющим новую траекторию γ (ri′) .В результате на выходе алгоритма получается набор допустимых по отношению к статическим ограничениям траекторий {γ (ri )}i =1 и соответствующих имNвекторов ri , i = 1, N .Аналогично данному алгоритму осуществляется построение набора траекторий в окрестности заданной судоводителем траектории.Алгоритм № 2 формирования маршрута, оптимального по времениперехода.1.
Задаются исходные данные, в качестве которых выступает набор траек-339торий{γ(ri )}iN=1 ,допустимых по отношению к статическим ограничениям, т.е.удовлетворяющих условиям γ (ri ) ∈ Ω S , i = 1, N .2. Далее на каждой траектории γ (ri ) ∈ Ω S , определяемой вектором ri , решается вспомогательная задача (9.1.14) о минимизации времени перехода на допустимом множестве V (ri ) . Это задача нелинейного программирования как по отношению к целевой функции, так и к ограничениям.
Как показывает опыт, наиболееэффективным для ее решения при достаточно близком начальном приближенииявляется стандартный метод последовательного квадратичного программирования (SQP), реализованный, например, в пакете MATLAB.Однако заметим, что решение вспомогательной задачи существует не длялюбой траектории γ (r ) , поскольку допустимое множество заданных скоростейV (r ) может быть пусто. Например, в сложных погодных условиях может оказаться, что по данной траектории нельзя пройти, не попав в опасную погодную зону.3.
Если допустимое множество V (ri ) не пустое, то в результате решенияполучается оптимальный вектор v ∗i ∈ V (ri ) и соответствующее значение времени(())перехода J T ri , v ∗i . При этом маршрут ri , v ∗i допустим.Теперь можно сформировать приближение к решению задачи (8.1.15), вы-(брав в качестве оптимального маршрута r ∗ , v ∗()меньшим временем перехода J T r ∗ , v ∗ = mini∈I ⊆{1,..., N })допустимый маршрут с наи-()J T ri , v ∗i .4.
Если допустимых маршрутов нет, то в качестве решения принимается вариант с минимальным временем нахождения в опасной зоне. Для поиска допустимых маршрутов в подобной ситуации можно либо каким-либо образом изменить исходный набор траекторий, либо ослабить ограничения, определяющиеопасные области по отношению к прогнозу погодных условий.Алгоритм № 3 построения маршрута, оптимального по расходу топлива.1. Для приближения к решению задачи (8.1.16) можно, в принципе, использовать алгоритм № 2 решения задачи (8.1.15), представленный выше, однако с340введением дополнительного ограничения на величину расхода топлива. При этомиспользуются те же исходные данные, что и для предшествующего алгоритма,т.е.
набор допустимых траекторий {γ (ri )}i =1 , и соответствующих им векторов ri ,Ni = 1, N .2. Кроме того, задается величина J Fmax , определяющая ограничение на допустимый расход топлива.3. Вводится в рассмотрение новое допустимое множество заданных скоростей на траектории γ (r ) :{}V ∗ (r ) = v | v ∈ V (r ), J F (r, v ) ≤ J Fmax ,учитывающее дополнительное ограничение. Любой вектор из этого множестваопределяет распределение скоростей на траектории γ (r ) , при котором выполняются все ограничения, определяющие множество V (r ) и, кроме того, расход топлива не превосходит заданного предела J Fmax .4. Далее для каждой траектории γ (ri ) из исходного набора решается задачао минимизации времени движения, аналогичная задаче (8.1.14), но на допустимом множестве V ∗ (ri ) .Замечание: Естественно, что множество V ∗ (r ) может оказаться пустым, например, если по траектории γ (r ) невозможно осуществить переход, потративменьшее количество топлива, чем заданное в ограничении, или если, в силусложных погодных условий, время в опасной зоне не удается сделать нулевым.5.
Если множество V ∗ (ri ) не пустое, то в результате решения задачи минимизации находится оптимальный вектор v ∗i ∗ . Соответствующий маршрут является допустимым((r , v )∈ Ωi∗∗iи для него можно вычислить время перехода)J T ri , v ∗i ∗ .6. Анализируя весь набор траекторий, можно сформировать приближение к()решению задачи (8.1.16). В качестве оптимального маршрута r ∗∗ , v ∗∗ выбирается341допустимый()маршрутJ T r ∗∗ , v ∗∗ = mini∈I ⊆{1,..., N }(снаименьшимвременемперехода)J T ri , v ∗i ∗ .Таким образом, результатом работы алгоритма является наилучший, средидопустимых маршрут, для которого время перехода наименьшее при расходе топлива, не превышающем заданного предела.7.
Если допустимых маршрутов нет, то в качестве решения принимается вариант с минимальным временем нахождения в опасной зоне или с наименьшимрасходом топлива. Для поиска допустимых маршрутов в подобной ситуацииможно либо изменить исходный набор траекторий, либо ослабить ограничения,определяющие опасные погодные области, либо увеличить значение допустимогорасхода топлива.Важно отметить, что задача оптимизации распределения скоростей в варианте (8.1.14) или (8.1.16) является существенно нелинейной.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
