畢業(yè)論文（設計）-淺談幾種新型航線自動設計

1、淺談幾種新型航線自動設計【引言】 全世界每年都會有數十個臺風生成。臺風所帶來的大風、強降水、巨浪 和風暴潮會對船舶航行安全形成重大威脅。 全球經濟一體化進程正在加快，世界外貿海運量隨之迅速增長，而在航運 中，需要船舶安全高效營運，提高公司的經濟效益。綜上所述，需認真做好船舶營運屮的每個環(huán)節(jié)，而航線設計的好壞在這一過 程小起著十分重要的作用,因此做好航線設計工作就顯得尤為重要，本文主要介 紹幾種新型的自動航線設計方法，及與傳統的航線設計相比，其優(yōu)缺點。【現狀】航線設計(passage planning)是一項比較復雜和細致的丁作，涉及知識面 廣，選擇性和多變性強。船舶在海上航行，與陸地上汽車和火

2、車沿固定路線行駛 是大不一樣的。由于海區(qū)廣、活動余地大、氣象條件多變，各種船舶情況差異不 同，選擇航線上就各有千秋。當今時代，所謂的航線設計，一般主要依靠中、英版航海資料中給出的推薦 航線(recommended route) 0除此之外，一定要閱讀大量的相關航海圖書資料， 才能對航線的全貌有一個深入的了解和掌握。從屮選出適合本船條件和航行季節(jié) 水文氣象條件要求的安全、經濟航線。另一方面，通過人量豐富的實航經驗的積累，也可以逐步掌握某些航線的規(guī) 律。兩方面和加，才能在任何條件變化的情況下，獨立果斷地選擇航線，確定航 線。否則，畫出的航線沒把握，不安全因索多，航行起來將是盲目的，甚至是危 險的。

3、【理論框架】航線設計的原則：安全、經濟。航線設計主要途徑：堅持原則、了解氣彖、閱讀資料、研究海區(qū)、擬定航線。航線設計是一項吋間緊、任務重、繁忙而又復朵的重耍工作。傳統的航線設計步驟如下：1、備妥、改正本航線所需的航海圖書資料2、認真研究有關的航海圖書資料，充分了解航區(qū)的詳細情況3、在掌握航海資料的基礎上，根據自己的航行經驗或參考他人的航 行經驗，選定一條安全經濟的航線。4、標繪航線、填寫航線設計表而本文主要簡介幾種新型的自動航線設計法優(yōu)缺點等，如：基于數據挖掘的gis及在航海中的應用2、電了海圖平臺下的航線自動設計方法3、基于蟻群算法的航線口動牛成4、基于瞬時水深型的最短時間航線口動生成算法5

4、、應用wi7d0wsapi函數進行航線h動設計等等?！緦嵗治觯ê喗椋恳?、基于數據挖掘的gis及在航海中的應用關鍵詞：數據挖掘（dm） 聚類分析 地理信息系統（gis）簡單的說，所謂的“基于數據挖掘的gis及在航海中的應用”就是指,根據聚類分析方法屮密度凝聚的思想，提出一種新的復合聚類分析算法，進 一步將這種算法用于地理信息系統的數據挖掘，并應用于船舶航線的自動 設計。1、數據挖掘數據挖掘(data mining簡稱dm)是20世紀末 剛剛興起的數據智能分析技術， 它對以從數據庫或數據倉庫，以及其他各種大量數據類型中，口動抽取 或發(fā)現有用 的模式知識。2、地理信息系統地理信息系統(geogr

5、ap hie info r mat io n system 簡稱 gis)是一項 以計算機為基礎的新興技術，它可以對在地球上存在的東西和發(fā)生的事件進 行成圖和分析。它能把各種地理位置信息和有關的視圖結合起來，利用計算 機圖形與數據庫技術來采集存儲、編輯顯示轉換分析和輸出地理圖形及 其屬性數據。即在計算機軟硬件支持f，它可以對空間數據按地理坐標或空 間位置進行各種處理，研究各種空間實體及相互關系，通過對多因索的綜 合分析，它可以迅速地獲取滿足應用需要的信息，并能以地圖圖形或數據 的形式表示處理的結果。我們利用一種基于聚類 分析的數據挖掘方法，從 數據庫大量的數據屮，捉取冇效的數據，繪制最優(yōu)船舶航

6、線。如圖1, gis ± 5個主要的元素構成：硬件、軟件、數據、人員和 模型。3、復合聚類分析算法z = < z. z2,z c r為一有限數據集合，77是數據集小元素的個數,將該數據集小的數據 分為&類(1 < k < n) f則z將被劃分為&個門xk 的分類區(qū)域u = g 疋： &的確定是根據不同 對象的需要。對于每一個小區(qū)域p按照密度算法選取凝聚點；vc1, c2 ( c < 6)為球半徑，通常(=2 c),s( i f j) =/ z( i) - z( j) /a)式中. s ( i , j)為兩樣本點z ( i) , z (

7、j)之間的距離,i丿if s r 7, j) wg孵木點落入。球域丿，then計算落入g球域的樣木點，and then選擇密度最大的樣木點作為第一凝聚點戸;2)對于密度次大的樣本點if s (a，j)丸傳羊木點落入g球域丿，then忽略此樣木點，if 5 ( p, j) 2g傳羊本點不落入g球威丿，then選擇此樣本點作為第二凝聚點化;這樣，按照樣品密度由大到小一直選下去，每次c 開始 j(從數擔庫“i 讀取藪據 i丿測試數據量 樣本排序 按照實際要求i計算凝聚點求平均密度 中心.和已選的任一凝聚點的距離不小于c2的樣品作為新 的凝聚點 o對于以上所求得的凝聚點再求平均密度中心，利用重心連接算

8、法公式：其中x i , y是樣本點乙的橫坐標和縱坐標。如右圖為復合聚類分析算法的計算機流程。c 結束 2)以下給出了兩維平面上gis中船舶航線設計 的結果，與傳統的基于密度的方法相比較。圖3為 采用聚類分析方法在matlab上的聚類結果；圖4 為采用傳統的基于密度的方法在matlab上的聚 類結果。由圖3圖4的比較可以看出，采用聚類分 析方法的聚類效果要比傳統的基于密度的方法的優(yōu) 越,航線設計明顯。圖3采用聚類分析方法的聚類結果-22-50-40-30-20-100經度（°）10 20246282-30233463-38圖4基于密度方法的聚類結果4、dm在gis中的應用示例數據來口于

9、gps,通過access建立專門的數據庫（如圖5所示），對數據 進行存儲,組織和管理。利用access建立數據庫時，設定相應的規(guī)則，保證數據的有效性。aft*“ 加to. 40r r . liua q九fbfe疋右to，戈忖厘*的位置，描到電了海圖的和應地點。由于數據量龐大，故需要采用dm方法從數據庫屮提取圖5 access建立專門的數拯庫該數據庫僅包含1張表，表中的每條記錄，包括5個字段，分別為number（序號）,td （船名）,lat （緯度）,long （經度）,date （日期）,time （時間），這樣一條記錄就完整地記錄了某條船在某一時刻的確切位置。所用地理信息系統軟件為esr1

10、 的arcview3o 2，在arcview 3。2中調用access中的數據,并利用arcview 3o2提供的工具去除不必要的數據，對空間數據 進行處理后，可以將數據庫中包含的所有的船有價值的信息。以船舶航線設計為例說明dm用8布宜話斯艾利斯與好望角之間的航賤設計在gis小的應用，圖6為采用dm進行船舶航線設計的過程。如圖6所示，先從衛(wèi)星上得到全球船舶分布數據，然后選取樣本數據，例如:選擇從布宜諾斯艾利斯和好望角之間的海域（如圖7所示），并導岀該區(qū)域所 包含的數據，再用我們所介紹的方法進行聚類一種基于數據挖掘的gis及在航海 屮的應用3分析,提取能確定最優(yōu)航線的數據，最終將所得數據所確定的

11、航線，在 地圖小以描點的方式顯示出來（如圖8所示）因為從gps得來的全球船舶分布數據是朵亂無章的、隨機的，所以通過測 試數據量、樣木排序將數據進行預處理, 再進行區(qū)域分割，經多次試驗證明k的選取與77有關，至少保證每個 i丿內樣本點數大于10 , i大i為樣本點太 少，聚類效果不明顯；當然太多的話，設 計的航線就會失真。從布宜諾斯艾利斯 和好槊角之間的海域取的樣本點有1844個，取k =100，試驗證明，此時的 聚類效果最好。二、電子海圖平臺下的航線自動設計方法關鍵詞：電子海圖系統；船舶航線；自動設計；障礙區(qū)；可航渡區(qū)域與傳統的手工作業(yè)方法相比，為優(yōu)化艦船計劃航線設計，提出了一種基于 電子海圖

12、的自動設計方法。通過追蹤安全等深線和處理障礙區(qū)，得到可航渡區(qū) 域。在可航渡區(qū)域內，進行路徑的可航渡性測試，自動搜索一條安全的最短計 劃航線，并根據障礙區(qū)的動態(tài)變化，實時調整和優(yōu)化航線。實驗結果表明，該方 法在效率、經濟性、可靠性等方面都具有明顯的優(yōu)勢。傳統的航線設計方法已難以適應現代特種航海行動的需求。因此，研究電 了海圖平臺下的計算機口動設計航線方法，在海圖上任意兩點z間口動地找出 一條最短的可行性航線，具有理論和現實意義。該段將通過追蹤安全等深線，處 理障礙區(qū)，得到可航渡區(qū)域。在可航渡區(qū)域內，進行航路的可航渡性測試，自 動地生成最短計劃航線。1、安全等深線的追蹤口動化航線設計，首先應求出可

13、以安全航行的水域。在矢量電了海圖平臺 下，根據數字水深模型，由計算機自動追蹤岀安全等深線。同時考慮航行障礙 物的影響，確定障礙區(qū)的范圍。當前用于艦船導航的海圖水深為不規(guī)則的離散 點數據，本文采用三角網法追蹤等深線。圖1是利用某海區(qū)的水深數據構建的 三角網和繪制10 m安全等深線后，從原圖中截取的一部分。在圖1中，左側為淺水區(qū)，右側為深水區(qū)。箭頭方向為等深線的止向；反 之，淺水區(qū)在右、深水區(qū)在左的方向為等深線的負向。內部為淺水區(qū)的閉合等 深線（圖1小的cl ）為第i類等深線；內部為深水區(qū)的閉合等深線（圖1小的 c2 ）為第ii等深線；非閉合等深線（圖1中的c3 ）為第iii類等深線。圖1三角網及

14、等深線2、安全水域的提取安全等深線是艦船航行的安全區(qū)域與危險區(qū)域的分界線。第i類安全等深 線的內部區(qū)域，通常是島礁、淺地等地理要素（稱為自然障礙區(qū)）。第iii類不 封閉安全等深線，為安全水深區(qū)與危險水深區(qū)的邊界線。沿這類等深線的正向， 將其與研究區(qū)域外邊界形成一封閉區(qū)域，其內部為淺水區(qū)域，也是自然障礙區(qū)。 第ii類等深線，盡管內域深于安全水深，但其位于更大障礙區(qū)的內部，航線分 析時只需考慮外圍障礙區(qū)。考慮這些障礙物影響域，即為點、線、而h標的緩沖區(qū)域，是一種人工障礙區(qū), 如圖2中的方框內區(qū)域a 1 o所有這些不可航渡的區(qū)域統稱為障礙區(qū)。圖2障礙區(qū)3、障礙區(qū)的擴充障礙物位置的不確定性、風（流、浪

15、）對安全性的影響、艦船的回旋半徑、圖3可航渡區(qū)域 導航定位系統精度等因素，都會對可行性航線設計存在一定的影響?？紤]這些 不確定性因素的影響，岀于對安全可靠性的考慮，將原有障礙區(qū)的范圍進行一 定的擴充，以便留有余地。此過程類同目標的緩沖區(qū)求取，該段中采用角平分 線的方法求擴充影響區(qū)，被擴充的不確定性區(qū)域如圖3所示。4、障礙區(qū)的處理某些障礙物進行擴充后，兩個障礙物之間可能相互相交，如圖2中的障礙 區(qū)a 2. a 3 o對丁相交的障礙物多邊形，應進一步進行多邊形求并的操作。經 過合并處理后，形成如圖3所示的障礙區(qū)a 4。某些障礙區(qū)進行擴充，多邊形 的邊述可能自相交，都需要進行相應的處理。經過一系列相

16、應的處理后，障礙 區(qū)、航行安全性不確定區(qū)域和可航渡區(qū)域如圖3所示。5、可航渡路線的測試求得安全的可航渡區(qū)域后，就耍建立一條最短的安全航線。如圖4所示，當 艦船需要從出發(fā)點s航行到目的點d ,其可行性航線建立步驟如下：（1）先建 立一條從s至ud的可航渡性測試線圖4（a） o如果測試線不經過障礙區(qū)，則 兩點z間可以直線航行。如果僅從航海要求考慮，則從s至ijd的直線段就為海 圖上的最短設計航線。（2）如果經過障礙區(qū)，則求出測試線穿越且離s最近的 障礙區(qū)01 , 01的頂點必定分布于測試線的左右兩側。（3）計算s到01各個頂 點的方位，然后在測試線兩側，分別求出與測試線sd方位z差的最大值amax

17、l. amax2。對應的兩個頂點分別是兩側能繞過障礙區(qū)的兩個航路點。比較的大 小，取其中較小的一個夾角相對應的頂點為航線的下一個航路點如圖4（ a 中，a maxi < a max2 ,相對應的頂點pi為下一個航路點。當每次遇到新障礙 物時，需同時記錄左右兩條路徑，其相應處理見后面部分的詳細介紹。（4） 繼續(xù)測試pi與d是否可直線航渡，如果可直線航渡，建立r至ijd的航段，航線 設計完成。如果不可直線航渡，則重新計算到障礙區(qū)a各頂點的兩側極值方位 差amaxl. a max2 （計算時，應排除pi到r的方位計算），取夾角較小者所對應頂點p2為下一個航路點。不斷進行可航渡性測試，直到航路點

18、與終點可直線航行，則此條可航性航線建立完成。在建立航路點到極值方位差所對頂點的航 段中，中間叮能碰到障礙物，所以應對建立的每一航段都進行叮航渡性測試。如圖4( b)所示,建立測試線sd,求出測試線穿越月.離s最近的障礙區(qū)01 ,根據可航渡路線屮方位相差最小原則，下一個航路點應為卩2。在建立s到匕的航段中，發(fā)現sp2經過障礙區(qū)。所以要對建立的航段sp2同樣進行可航渡性測試,最后形成的結果應先增加航路點p 1 ,形成sp1、p 1 p2兩個航段。圖4 可航渡性測試6、可航渡路線的優(yōu)化如圖5( a)所示，建立測試線sd ,由于sd經過最近的障礙物01 ,根據方位相差最小原則，建立下一個航路點p 1

19、,依次得到下一個航路點p 2。可是在圖5( a)屮發(fā)現，從s可直航到p 2 , pi成為了一個兀余的航路點。所以需要對建立的可航渡段進行優(yōu)化，刪除冗余的航路點，保證最大的直線航段。在航 線生成過程中，當遇到新障礙物時，不進行方位差比較，分別記錄兩側的兩條 可能性路圖5多條路徑的優(yōu)化0),需要同吋建立條路徑sp i和sp3 ,沿障礙物0繞行時，從p】或p3分 別測試路徑時，可采用方位和并最小原則使接下來的各口測試路徑plii-o但遇 到新障礙物0 ,又需重新從測試點再次建立兩條路徑，從p 2分別到p 5和p 7(在p 2s'jp 5的可航渡性測試屮，用前而方法自動增加必要的航路點)，從p

20、4分別到p 6和p7 ,形成4條路徑。不斷循環(huán),直到測試點與d可視，當有n個航行障礙物時，需要建立2n條路徑，最后從中選取最短者為最后結果。失事平臺 的殘骸、不斷人為設置的航行障礙等，都可能對可航渡的區(qū)域和最優(yōu)航線構成一 種動態(tài)的影響。因此，在航線自動設計方法小，述應考慮這種障礙區(qū)的動態(tài)檢 測及實時更新，當障礙區(qū)發(fā)生變化后，采用前面所述的方法，重新自動搜索最 短航線。7、實驗與分析圖6安全水深1() m的最短航線為了驗證算法的有效性，本文進行了相關實驗。圖6中的折線是為安全水 深10 m的艦船所設計的航線，是在可航渡區(qū)域提取的基礎上，自動生成的一條 最短計劃航線。 圖7是艦船從起 點航行到點p

21、后, 人工障礙區(qū)發(fā)生 變化，自動地進 行最短航線調 整。圖8是為安 全水深12 m的 艦船口動生成的 最短航線，圖9 是為安全水深要 求7 m的艦船所 牛成的最短航 線。圖7障礙物變化后的最短航線圖8安全水深12 m的最短航線圖9安全水深7 m的最短航線8、比較（缺點：可靠率低）采用該航線口動設計方法，可以方便地根據不同艦船的吃水要求，隨意地 選定安全水深。只要輸入起點和終點的位置，即能顯示最短計劃航線。表1是 在某航線的設計屮，計算機自動設計與使用手工作業(yè)方法在設計耗時、航線距離 及可靠率（不穿越擴充后障礙區(qū)的設計航線占所有設計航線的比率）方面的比 較。表1兩種方法在設計耗時、距離航線及可靠

22、率方面的比較采用方法設計耗in/s航線距岡m可靠率倫傳統于工方法自動設計方法1320.618621.815327.4三、基于蟻群算法的航線自動生成關鍵詞：蟻群算法 航線口動生成 航行帶搜索策略航線平滑為了減輕航海人員制定航線的繁復勞動，減少航線制定時的個人主觀性， 基于蟻群算法進行航線自動生成研究。以電子海圖為基礎，通過示例證明了蟻群 算法用于航線自動生成的可行性。該法不僅實現了航線制定的自動化，而且可以 在相關搜索策略中運用專家的思想，增加航線制定的科學性，提高航行的安全 性。1、蟻群算法螞蟻覓食時，對于從蟻窩到食物源的諸多途徑,開始時不同的螞蟻會選擇不 同的路徑，但最后，幾乎所有的螞蟻都會

23、找到同一條最短的路徑。這是i大i為螞蟻 尋找最短路徑的過程是一個交互式的過程，它們會在經過的路上留下一定量的 外激素，而且能感知這種激素的存在及強度并朝該物質強度高的方向運動。這些 激索既會隨通過的螞蟻數量增加而增加，也會隨時間的流逝而按一定的函數關 系消逝。因為最短路徑通過的螞蟻數量較多，所以其上激素的積累速度將比其他 路徑快。蟻群通過外激素這種物質來不斷地交流反饋信息，最終找到一條從蟻窩 到食物源的最佳路徑。蟻群算法就是基于自然界螞蟻的這種功能設計出的一 種尋 優(yōu)決策方法，設定一定數量的人工螞蟻，按照一定的搜索規(guī)則，獲取綜合性能最 佳的路經。2、海區(qū)的柵格劃分海區(qū)的柵格劃分，涉及到航線生成

24、的精度和速度。柵格劃分的顆粒越細，航 線設計的精度越高，但計算量增大。船舶在航行中，有一定的航行帶寬區(qū)域，即 航行帶，通常取3倍均方并作為航行帶寬比較可靠。將航行帶寬度作為海圖網格 劃分的單位，可以保證生成航線的安全性，避免進入危險區(qū)域。網格點的信息素是蟻群算法的基礎，它是人工螞蟻搜索尋優(yōu)的依據。網格點的信息素町 山下列因素組成：坐標、可航行、信息濃度、啟發(fā)系數。網格點的信息素可用如 下結構表示：struct xinxisu double jd, wd;boll state;double t , n ; 1）坐標jd、wd是網格點的經緯度值，一旦海區(qū)的柵格劃分完畢，其值也就確定。2）可航性st

25、ate,可航為true,否則為false。有些網格點初始吋為true, 但隨著搜索進程，該點的前行路線被完全封堵，其state則可能cbtrue變?yōu)?falseo3）信息濃度t表示該點人工螞蟻通過的頻率指標，是人工螞蟻搜索決策的 重要依據，各點初始值為同一值，隨著螞蟻搜索過程中揮發(fā)和獎懲作用，螞蟻 走得多的點增大，相反則降低。4）啟發(fā)信息a為螞蟻決策提供信息，可表示為到目的點的距離。3、搜索策略搜索是蟻群算法的核心，優(yōu)秀的搜索算法，可以使搜索過程快捷準確，相 反則會使搜索進程緩慢，有時甚至無法獲得尋優(yōu)結果。制定合理的搜索策略,可 參照有關專家的思想，提高航線設計的科學性。采用下列搜索策略。前行

26、策略根據螞蟻尋優(yōu)的思想和計劃航線制定的特點，人工螞蟻從一個網格點向下一 個網格點前行時，遵循下列原則：a、下一網格點應是可航行點；b、下一網格點到航線終點的距離應比現在的距離近；c、當滿足上面兩條原則的下一網格點有多個可選時，采用加權隨機的方法 選取。加權隨機的做法是：根據搜索的進程，確定采用輪盤賭和最優(yōu)兩種方法的權重，即隨機采用兩 種方法的隨機數范圍，根據產生的隨機數值，確定哪種方法。這樣既保證各可航 點均有被選的可能，增強搜索的多樣性，避免過早出現搜索停滯，同時乂保證 經濟路徑被選的可能性大，最優(yōu)路徑通過的概率高。在確定兩種方法權值時，搜 索開始輪盤賭方法的權值取0. 9,最優(yōu)法取0. 1

27、,以保證搜索的多樣性；搜索結 束時兩者的權值互換，以保證快速收斂；搜索過程中，輪盤賭方法的權值為：0. 9- 0. 8 x i/ n, i為迭代次數，n為總迭代數。兩種方法都需要計算各下一可選點的代價p (s):(1丿式（1）中，a、b為常數，用來調節(jié)信息濃度t和啟發(fā)信息i）的影響強度, n為可選的下一網格點數。最優(yōu)方法是選取代價最小的網格點為前行的下一網格點；輪盤賭法則需根 據各點的代價值，及產生隨機數落入各點對應區(qū)間情況，確定前行的下一網格 點。前行的網格點選定后，將當前點加入航路點鏈表，前行的網格點設為當前 位置，再重復上述搜索過程，如此循環(huán)，直至螞蟻達到目標點（見圖1）。圖1螞蟻搜索流

28、程退后方法如果某點的前行網格點均為不可行點，則螞蟻必須作后退處理。后退的方法 是：將當前點設為不可行點，并在航路點鏈表小刪除，將航路點鏈表小的前一 個點作為當前點繼續(xù)前行搜索。5、信息素的更新信息素更新時機是：在每只人工螞蟻完成搜索過程，到達終點后；一代蟻 群形成最優(yōu)可行航線后。信息索更新的內容包括“揮發(fā)”和“獎勵”處理。信息素更新的計算公式：t(3)( 1-p ) t (s) +p a t (s)"；(2) t (s)二 q/ p( s)j式(2)中，p ( 0< p < 1)為信息索增量控制參數，(1-p ) t (s)使網格點s的信息素被“揮發(fā)”，這是對所冇網格點的

29、 操作；(l-p) t (s)為對被通過點的“獎勵”，只對航路點鏈表屮的點操 作。q為常數，大小決定每次獎勵的程度，p ( s)為通過s點的代價。經過信息素的更新，未被螞蟻“訪問”的節(jié)點，由于“揮發(fā)”作用，信息素 強度將越來越小，未來對人工螞蟻的吸引力也就越小；經常被螞蟻“訪問”的點, 由于“獎勵”作用，信息索強度將越來越大，未來對人工螞蟻的吸引力也就越 大。6、航線優(yōu)先航線選優(yōu)在一代螞蟻群搜索結束和所有螞蟻群搜索結束后進行，分別選岀 蟻群最優(yōu)和最后最優(yōu)航線。航線選優(yōu)的準則：航線代價最小。航線代價包括經濟代價ve和安全代價vs。經濟代價ve由航行吋間和油耗決定。為簡化求解，經濟代價化為航程的函 數：ve二ce / dis。dis為航線的總航程，ce為系數。安全代價vs包描航行安全(礙航物、水深影響)和軍事安全(遭敵打擊的 可能性)，這里只考慮航行安全。水深代價的計算:id 二(：d刀皿i = 1(1人/ ( dep th -1)draft )depth < ladep th > i )&