基于最短路徑快速算法的船舶管路自動(dòng)創(chuàng)設(shè)方法

基于最短路徑快速算法的船舶管路自動(dòng)創(chuàng)設(shè)方法

0船舶管路敷設(shè)管道配置在許多行業(yè)都很常見(jiàn)。例如，工廠管道配置和船舶管道配置[2、三、四、五、六、七、八、九、十、十一月、十二]，飛機(jī)管道配置和機(jī)電產(chǎn)品管道布局等。船舶管路布置是大型船舶設(shè)計(jì)中的重要步驟之一,管路設(shè)計(jì)的效率和質(zhì)量直接影響船舶的研發(fā)成本和經(jīng)濟(jì)價(jià)值。管路設(shè)計(jì)在船舶設(shè)計(jì)中占有較大比重,即便最簡(jiǎn)單的商船也需要15~20種管路系統(tǒng),同時(shí)管路布置要考慮各種約束條件,因此復(fù)雜度極高。當(dāng)前主流的船舶計(jì)算機(jī)輔助義。船舶管路布置要求在特定三維空間區(qū)域?qū)ふ乙粭l或多條滿足約束條件并連接各給定接口的管路路徑。船舶管路敷設(shè)設(shè)計(jì)(ComputerAidedDesign,CAD)系統(tǒng)尚沒(méi)有管路自動(dòng)布置模塊支持,主要依靠工程人員憑經(jīng)驗(yàn)交互設(shè)計(jì),設(shè)計(jì)過(guò)程具有隨意性、周期長(zhǎng)等問(wèn)題。因此船舶管路布置已經(jīng)成為船舶生產(chǎn)設(shè)計(jì)的瓶頸之一,提高管路布置的自動(dòng)化和優(yōu)化水平,對(duì)船廠和船東具有重要的經(jīng)濟(jì)意中的約束種類繁多,其中易于被自動(dòng)化算法處理的約束包括:(1)物理約束管路需連接指定連接點(diǎn),且管路之間、管路與設(shè)備之間無(wú)干涉。(2)經(jīng)濟(jì)約束管路長(zhǎng)度盡量短,彎頭盡量少,管路布置后應(yīng)有最優(yōu)空間;經(jīng)濟(jì)性約束往往作為優(yōu)化目標(biāo)看待,不是必須滿足的剛性約束。(3)生產(chǎn)或安裝約束管路盡可能沿艙壁、可依附設(shè)備布置,與鋼結(jié)構(gòu)件平行或垂直;首先安裝主管道,然后按管徑大小依次安裝。(4)安全約束保證管路與管路、管路與設(shè)備之間的最小距離;油管避免在鍋爐上方通過(guò);蒸汽管、油管、水管、柴油機(jī)排氣管避免在配電板及其他電器上方通過(guò);管路不能阻礙通道。(5)操作及維護(hù)性約束管路布置必須為設(shè)備維修和更換等行為留出足夠的空間。國(guó)內(nèi)外很多學(xué)者對(duì)管路布置問(wèn)題進(jìn)行了研究,并取得了一定成果。采用的方法包括人機(jī)交互法、專家系統(tǒng)法、優(yōu)化或啟發(fā)式算法。其中采用各類算法求解管路布置的研究相對(duì)較多,包括遺傳算法、蟻群算法、單元格生成法、迷宮法、粒子群算法和混合算法等。近年來(lái)船舶管路敷設(shè)問(wèn)題日益受到關(guān)注,代表性的研究包括:KANGS和MYUNGS采用專家系統(tǒng)解決船舶管路敷設(shè)問(wèn)題,描述了專家系統(tǒng)的求解目標(biāo),基于面向?qū)ο蠹夹g(shù)對(duì)知識(shí)、規(guī)則、經(jīng)驗(yàn)等進(jìn)行形式化處理,并給出一個(gè)以管線長(zhǎng)度和彎頭為優(yōu)化目標(biāo)的原型系統(tǒng);范小寧首次提出使用蟻群算法求解船舶管路敷設(shè)問(wèn)題,該方法基于網(wǎng)格分解模型,可以充分利用敷設(shè)區(qū)域的特點(diǎn)和約束來(lái)評(píng)價(jià)路徑的優(yōu)劣,缺點(diǎn)是隨著敷設(shè)規(guī)模的增大導(dǎo)致效率降低;PARK和STORCH提出單元生成算法,路慧彪對(duì)該方法進(jìn)行了更深入、具體的論述,單元生成法從起始點(diǎn)開(kāi)始按照固定樣式或擴(kuò)展樣式模板生成管路路徑段,直至終點(diǎn),主要問(wèn)題是敷設(shè)過(guò)程中可選擇的路徑段生成方式有限,考慮約束較少,甚至在布置空間復(fù)雜的情況下無(wú)法按固定樣式生成路徑;ASMARA和NIENHUIS提出一種將確定性算法和非確定性算法相結(jié)合的管路敷設(shè)方法,確定性算法選擇Dijkstra算法進(jìn)行最短路徑搜索,非確定性算法選擇粒子群算法進(jìn)行決策優(yōu)化,該方法結(jié)合了確定性算法的高效率和非確定性算法的尋優(yōu)能力,但算法會(huì)在一定的敷設(shè)順序下無(wú)法找到可行解,且對(duì)敷設(shè)中管路盡量沿艙壁或艙底敷設(shè)等約束條件考慮較少;MARTINS采用與ASMARA類似的方法開(kāi)發(fā)了一個(gè)用于船舶管路敷設(shè)的軟件工具;KIMURA將T型管路分支看作特殊設(shè)備,簡(jiǎn)化帶分支管路的布置問(wèn)題模型,利用多目標(biāo)優(yōu)化遺傳算法進(jìn)行求解;ANDO和KIMURA將布置空間網(wǎng)格化,映射成有向加權(quán)圖,然后應(yīng)用Dijkstra算法對(duì)船舶管路敷設(shè)中的彎管和彎頭約束進(jìn)行重點(diǎn)分析。管路布置問(wèn)題類似于復(fù)雜布置空間中的路徑尋優(yōu),理論上屬于NP難問(wèn)題,至今仍未形成成熟的理論方法,還有很多問(wèn)題亟待解決。1基于網(wǎng)格化方法生成路網(wǎng)的路徑管路自動(dòng)布置首先要將布置空間映射到抽象模型空間,主要映射方法包括可視圖法、自由空間法和網(wǎng)格化法等。網(wǎng)格化法將待布置空間分解成小尺寸網(wǎng)格。布置空間內(nèi)的設(shè)備、維修空間、過(guò)道、管路等均可由其覆蓋的網(wǎng)格來(lái)描述。管路在敷設(shè)時(shí),根據(jù)其約束條件為網(wǎng)格賦予能量值或狀態(tài)值,敷設(shè)算法計(jì)算敷設(shè)路徑。網(wǎng)格法便于空間信息的提取、描述和處理,因此大量研究方法均基于網(wǎng)格法求解。本文也基于網(wǎng)格化方法處理布置空間。每個(gè)網(wǎng)格節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)包括:網(wǎng)格編號(hào)(id),網(wǎng)格中心坐標(biāo)(centerPt),網(wǎng)格長(zhǎng)(length)、寬(width)、高(height),網(wǎng)格所在的行(rowID)、列(columnID)、層(layerID)位置,網(wǎng)格所屬的管路(pipeID),網(wǎng)格所屬的障礙物(ObstacleID),網(wǎng)格能量值(power)。網(wǎng)格化方法的主要問(wèn)題是隨著問(wèn)題空間的增大或網(wǎng)格化精度的提高,網(wǎng)格數(shù)目激增,從而導(dǎo)致以此為基礎(chǔ)的路徑生成算法的效率降低。隨著計(jì)算機(jī)軟硬件技術(shù)的發(fā)展,網(wǎng)格化方法受限于內(nèi)存空間的情況得到緩解,對(duì)于超大規(guī)模的布置問(wèn)題可以對(duì)空間進(jìn)行拆分后分塊求解。已有的基于網(wǎng)格化方法生成管路路徑的方法包括以下幾種:(1)基于啟發(fā)信息的隨機(jī)方法,該方法得到的路徑優(yōu)化程度較低,往往只作為遺傳算法、粒子群等算法的初始解構(gòu)造。(2)利用蟻群算法模擬大量螞蟻覓食過(guò)程中的路徑尋優(yōu),基于信息素的遺留與揮發(fā),最終收斂到最短路徑。該算法適合單獨(dú)使用,但其搜索過(guò)程需要較多的迭代過(guò)程,因此效率較低。(3)利用Lee算法或其改進(jìn)算法,模擬波的擴(kuò)散原理,具有很強(qiáng)的繞障能力,在網(wǎng)格空間求解最短路徑時(shí)是一種很有效的方法。但其主要缺點(diǎn)是空間復(fù)雜度較大,并且在路徑探索時(shí)難以考慮復(fù)雜約束。(4)利用Dijkstra算法,先將網(wǎng)格空間映射成有向圖或加權(quán)有向圖,然后應(yīng)用Dijkstra算法求解最短或最優(yōu)路徑。2基于最短路徑快速算法的船舶管道生成方法2.1改進(jìn)策略在分次器至分類最短路徑快速算法(ShortestPathFasterAlgorithm,SPFA)是一種對(duì)Bellman-Ford算法的改進(jìn)算法,最早由段凡丁于1994年提出,用于求解加權(quán)有向圖中的單源點(diǎn)最短路徑問(wèn)題。無(wú)向圖可以用兩條方向相反的有向邊取代每條無(wú)向邊,將無(wú)向圖轉(zhuǎn)換成有向圖求解。SPFA在求解稀疏圖(邊數(shù)遠(yuǎn)小于頂點(diǎn)數(shù))時(shí)有良好的表現(xiàn),且SPFA對(duì)邊的權(quán)值沒(méi)有特殊限制,可以處理負(fù)邊。SPFA的基本思想與Bellman-ford算法相同,也是利用每個(gè)頂點(diǎn)來(lái)松弛其相鄰頂點(diǎn)到源點(diǎn)s的最短距離,但不再對(duì)所有頂點(diǎn)進(jìn)行盲目嘗試,而是僅維持一個(gè)待松弛的候選頂點(diǎn)隊(duì)列Q,只有被松弛操作過(guò)的頂點(diǎn)才被加入隊(duì)列中,從而減少了冗余計(jì)算。當(dāng)隊(duì)列中已無(wú)可松弛的頂點(diǎn)時(shí)算法結(jié)束。算法一定可以在結(jié)束時(shí)求得s到各頂點(diǎn)的最短距離,其正確性證明和效率分析見(jiàn)文獻(xiàn)。對(duì)于任意隨機(jī)生成圖,其收斂速度隨圖及邊的權(quán)值分布而略有不同,算法的平均時(shí)間復(fù)雜性為O(k|E|),k為所有頂點(diǎn)進(jìn)隊(duì)的平均次數(shù),|E|為圖中邊數(shù)。Dijkstra算法時(shí)間復(fù)雜度為O(|V|2),|V|為圖中頂點(diǎn)數(shù),對(duì)于使用Fibonacci堆優(yōu)化的Dijkstra算法時(shí)間復(fù)雜度為O(|E|+|V|log|V|),但其實(shí)現(xiàn)過(guò)程較復(fù)雜。SPFA的性能在很大程度上取決于被松弛頂點(diǎn)的順序,越靠近源點(diǎn)s的頂點(diǎn)越先被松弛,從而可以降低各頂點(diǎn)再次被松弛的幾率,進(jìn)而加速算法的結(jié)束過(guò)程。標(biāo)準(zhǔn)算法基于先進(jìn)先出(FirstinFirstout,FIFO)原則更新距離,沒(méi)有考慮距離標(biāo)號(hào)的作用,實(shí)現(xiàn)中使用雙向隊(duì)列DQ替換Q,并結(jié)合以下兩種策略可以較大程度地改善標(biāo)準(zhǔn)SPFA的性能,令d(v)表示v到s的最短路徑。(1)小標(biāo)號(hào)優(yōu)先(SmallLabelFirst,SLF)改進(jìn)策略當(dāng)頂點(diǎn)j要進(jìn)入隊(duì)列DQ時(shí),比較d(j)和d(i),其中i為DQ的隊(duì)首元素。如果d(j)≤d(i),則將j放置到DQ隊(duì)首,否則將j放置到DQ隊(duì)尾。(2)大標(biāo)號(hào)延后(LargeLabelLast,LLL)改進(jìn)策略設(shè)i為隊(duì)列DQ的隊(duì)首元素,,如果d(i)>a,則將i放置到DQ隊(duì)尾。重復(fù)該過(guò)程,直到頂點(diǎn)i滿足d(i)≤a,對(duì)i做出隊(duì)操作。2.2相鄰網(wǎng)格間的距離統(tǒng)計(jì)及優(yōu)化標(biāo)準(zhǔn)SPFA描述了在二維圖中求解最短路徑的方法,但船舶管路布置問(wèn)題顯然是在三維空間中尋找最短路徑,通常先將三維網(wǎng)格空間轉(zhuǎn)換成二維圖,即每個(gè)網(wǎng)格作為圖中的一個(gè)頂點(diǎn)(障礙物或是已敷設(shè)管路上的網(wǎng)格除外),再根據(jù)網(wǎng)格間的鄰接關(guān)系確定圖中的邊,例如網(wǎng)格A和網(wǎng)格B相鄰,則在圖中存在一條連接頂點(diǎn)A和頂點(diǎn)B的邊。在二維圖上可以方便地應(yīng)用最短路徑算法。但這種方法存在以下不足:(1)需要為存儲(chǔ)二維圖額外分配空間,且轉(zhuǎn)換操作需要運(yùn)算時(shí)間;(2)轉(zhuǎn)換后的二維圖失去了頂點(diǎn)間直觀的鄰接關(guān)系;(3)在多管路敷設(shè)問(wèn)題中,先敷設(shè)管路被視為障礙物,需要在二維圖中刪除其對(duì)應(yīng)的頂點(diǎn)和邊,操作繁瑣。本文提出一種直接在三維網(wǎng)格空間應(yīng)用SPFA的改進(jìn)算法,用三維數(shù)組pCell[M][N][L]表示網(wǎng)格空間,pCell[i][j][k](0≤i<M,0≤j<N,0≤k<L)表示空間中的網(wǎng)格點(diǎn),則相鄰網(wǎng)格三個(gè)下標(biāo)中有兩個(gè)相同,另一個(gè)相差1。一般情況下,每個(gè)網(wǎng)格至多在上、下、左、右、前、后方向上有6個(gè)相鄰網(wǎng)格,但對(duì)于處在布置空間邊界或鄰接障礙物的網(wǎng)格(在某個(gè)方向上它的鄰接網(wǎng)格不存在),則與其相鄰的網(wǎng)格少于6個(gè)。因此,如果將空間內(nèi)網(wǎng)格看作頂點(diǎn)、兩網(wǎng)格間相鄰看作兩頂點(diǎn)間有一條邊,則總邊數(shù)|E|至多為6|V|,符合稀疏圖|E|=O(|V|)的判斷標(biāo)準(zhǔn),適于SPFA求解。算法中用dist[id]記錄編號(hào)為id的網(wǎng)格到起點(diǎn)網(wǎng)格的距離,prev[id]用于記錄編號(hào)為id的網(wǎng)格在回溯路徑時(shí)指向的父網(wǎng)格編號(hào),s[id]用于記錄編號(hào)為id的網(wǎng)格是否在隊(duì)列Q中,其中0≤id<M×N×L。網(wǎng)格編號(hào)與其所在行列層編號(hào)可以換算。根據(jù)行列層編號(hào),計(jì)算網(wǎng)格編號(hào)如下:根據(jù)網(wǎng)格編號(hào),計(jì)算行列層編號(hào)如式(2)~式(4)所示:式中:id為網(wǎng)格編號(hào),rowID為行編號(hào),columnID為列編號(hào),layerID為層編號(hào),TL為一層中含有網(wǎng)格數(shù)目,TC為一列中含有網(wǎng)格數(shù)目,/為整除運(yùn)算符,%為取余運(yùn)算符?；谝陨蠑?shù)據(jù)結(jié)構(gòu),改進(jìn)SPFA描述如下。步驟1問(wèn)題初始化。分割布置空間為M×N×L個(gè)網(wǎng)格點(diǎn),記為pCell[M][N][L];根據(jù)布置空間內(nèi)設(shè)備和約束信息設(shè)置網(wǎng)格狀態(tài)和能量;指定管路起始點(diǎn)s的位置sPt,并根據(jù)式(1)由sPt計(jì)算起點(diǎn)對(duì)應(yīng)id,記為sID;size←網(wǎng)格邊長(zhǎng)(根據(jù)管徑和安全距離確定)。設(shè)定網(wǎng)格能量權(quán)重初值power_wgt;dist[cell.id]←INFINITE;prev[cell.id]←-1;s[cell.id]←0;(cell∈pCell)。步驟3dist[sID]←0;s[sID]←1;sID入隊(duì)列Q。步驟4隊(duì)列Q不為空時(shí),執(zhí)行步驟5~步驟14。步驟5k←Q隊(duì)首元素;Q隊(duì)首元素出隊(duì)列;s[k]←0。步驟6tPos←依據(jù)式(2)~式(4)計(jì)算id號(hào)為k的網(wǎng)格的行、列、層位置;取tPos處網(wǎng)格c,c←pCell[tPos.layerID][tPos.columnID][tPos.rowID]。步驟7對(duì)網(wǎng)格c的每個(gè)相鄰網(wǎng)格nc執(zhí)行步驟步驟8~步驟14(nc為與c上下左右前后相鄰且在布置空間內(nèi)的網(wǎng)格)。步驟8index←nc.id。步驟9如果nc不是障礙物網(wǎng)格,則執(zhí)行步驟10~步驟14。步驟10t←dist[k]+size+power_wgt×nc.power。步驟11如果t<dist[index],則執(zhí)行步驟12~步驟14。步驟12dist[index]←t;prev[index]←k。步驟13如果s[index]為0,即nc網(wǎng)格標(biāo)號(hào)不在Q中,則執(zhí)行步驟14。步驟14index入隊(duì)列Q;s[index]←1。算法中的步驟9在擴(kuò)展搜索時(shí)會(huì)避開(kāi)障礙物占據(jù)網(wǎng)格,保證了避障能力。算法在步驟10中對(duì)標(biāo)準(zhǔn)SPFA的距離松弛函數(shù)進(jìn)行改進(jìn),除了考慮路徑長(zhǎng)度外,還將路徑所在網(wǎng)格的能量值也加入其中,并為網(wǎng)格能量值進(jìn)行加權(quán)處理。因?yàn)榫W(wǎng)格能量值根據(jù)約束條件設(shè)置,所以修改后的松弛函數(shù)可以處理諸如貼壁敷設(shè)、沿能量帶分布敷設(shè)、成束敷設(shè)等約束。power_wgt≠0,即考慮網(wǎng)格能量對(duì)管路敷設(shè)的影響,可使管路沿艙底、艙壁、可依附設(shè)備表面等低能量空間敷設(shè),同時(shí)又可使某些管路避開(kāi)諸如高溫、電器等特殊設(shè)備周圍的高能空間敷設(shè);如果power_wgt=0,則忽略能量所代表的約束,此時(shí)管路布置的物理長(zhǎng)度最短。多管路敷設(shè)時(shí),可將已敷設(shè)管路周圍網(wǎng)格能量設(shè)為負(fù)值,則應(yīng)用SPFA布置后續(xù)管路時(shí),已敷設(shè)管路周邊網(wǎng)格將獲得較小的評(píng)價(jià)值,進(jìn)而引導(dǎo)新管路沿此類網(wǎng)格敷設(shè)以實(shí)現(xiàn)成束敷設(shè)的效果?；赟LF策略對(duì)Improved_SPFA算法進(jìn)行優(yōu)化,首先將隊(duì)列結(jié)構(gòu)改為雙向隊(duì)列,然后在步驟14入隊(duì)操作時(shí)按SLF策略入隊(duì)列?；贚LL策略對(duì)Improved_SPFA算法優(yōu)化也需使用雙向隊(duì)列,然后將步驟5隊(duì)首元素出隊(duì)列改為按LLL策略選擇元素出隊(duì)列。SLF與LLL策略可以組合在一起使用。三種改進(jìn)算法的實(shí)際效果將在后文實(shí)驗(yàn)中給出。2.3基于距離獲取仿真SPFA結(jié)束后,起點(diǎn)網(wǎng)格s到任意網(wǎng)格的最短距離都已求出,船舶管路布置需要給出每條管路的敷設(shè)路徑,可以借助prev數(shù)組(記錄當(dāng)前網(wǎng)格到其父網(wǎng)格的線索)回溯求解,但僅能在利用SLF或LLL優(yōu)化前使用,否則得到的路徑會(huì)產(chǎn)生大量彎頭,如圖1a所示。這是因?yàn)閮?yōu)化算法改變了網(wǎng)格點(diǎn)特定的松弛順序,所以雖然路徑長(zhǎng)度仍最短,但需要大量彎頭,不滿足船舶管路敷設(shè)的要求。為此,提出一種基于距離回溯的去彎頭方法,效果如圖1b所示。以圖2為例描述基于距離的路徑回溯算法,找出一條從S到T的路徑,在保證長(zhǎng)度最短的同時(shí)彎頭最少,網(wǎng)格中的數(shù)值代表算法計(jì)算后網(wǎng)格到S的距離。從T開(kāi)始,在其正交鄰居網(wǎng)格中找出數(shù)值最小的網(wǎng)格,如果存在可選網(wǎng)格不唯一,則按自定義的優(yōu)先規(guī)則選擇,例如優(yōu)先級(jí)排序?yàn)?下>左>上>右),則選擇下方網(wǎng)格;然后從選中網(wǎng)格開(kāi)始重復(fù)該過(guò)程,直到S結(jié)束。將該方法擴(kuò)展到三維空間時(shí)需注意:(1)每個(gè)網(wǎng)格的鄰居網(wǎng)格最多有6個(gè),回溯時(shí)要判斷相應(yīng)網(wǎng)格是否存在;(2)網(wǎng)格的“距離值”包含網(wǎng)格能量,不是最短距離;(3)只有起始網(wǎng)格的“距離值”為0,將其作為回溯終止條件;(4)使用基于距離的路徑生成算法,則算法2不再需要prev數(shù)據(jù)結(jié)構(gòu);(5)不同的優(yōu)先級(jí)規(guī)則會(huì)產(chǎn)生不同的解,管路設(shè)計(jì)系統(tǒng)需支持自定義優(yōu)先級(jí)規(guī)則。2.4連接多分支機(jī)構(gòu)管路的設(shè)置算法描述當(dāng)布置的管路有多條時(shí),不同的管路敷設(shè)順序會(huì)產(chǎn)生不同的布置方案,工程經(jīng)驗(yàn)為按管徑的大小安排敷設(shè)順序,管徑越大,要求管路以更短、更少?gòu)澱鄣姆绞讲贾?從而降低管路布置的成本。對(duì)于管徑相近的管路,可由設(shè)計(jì)者安排或由優(yōu)化算法評(píng)估敷設(shè)順序。對(duì)先敷設(shè)管路占據(jù)網(wǎng)格標(biāo)記為障礙物,避免后敷設(shè)管路與其發(fā)生干涉;對(duì)于帶分支管路,如果有主管路則優(yōu)先布置主管路,管路分支點(diǎn)常在主管路上開(kāi)設(shè),如果各分支管路不分主次,則由設(shè)計(jì)者或優(yōu)化方法指定敷設(shè)順序。優(yōu)化算法將管路(或管路接口)敷設(shè)順序編碼成算法的解,然后將解所代表的敷設(shè)序列按確定性算法進(jìn)行布置和評(píng)價(jià),迭代優(yōu)化后給出合理敷設(shè)順序。本文布置算法在管路敷設(shè)順序確定之后進(jìn)行,利用優(yōu)化算法確定敷設(shè)順序?qū)⑦M(jìn)一步研究。在網(wǎng)格空間中找出連接多分支管路各接口的最短路徑是圖論中的斯坦納樹(shù)問(wèn)題,屬于NP難問(wèn)題,不能在多項(xiàng)式時(shí)間內(nèi)求得最優(yōu)解,本文使用如下近似算法。算法2Branch_Pipe。定義序列S,并將管路待連接的分支接口按指定順序放入(例如S←ABCD);定義集合M,將S隊(duì)首元素放入(例如M←{A});定義一個(gè)有序集合N,將S剩余元素依次放入(例如N←{B,C,D});定義集合BP,用于存放管路包含的網(wǎng)格,將起點(diǎn)網(wǎng)格放入(例如BP←{A})。步驟2當(dāng)N≠?時(shí),循環(huán)執(zhí)行步驟3~步驟7。步驟3X←取出N首元素。步驟4Improved_SPFA(X),以X為起點(diǎn)計(jì)算其到空間中各可達(dá)網(wǎng)格的最短距離。步驟5T←BP中到X“距離”值最小的網(wǎng)格。步驟8依據(jù)BP所包含的網(wǎng)格生成各分支管路路徑。如果分支管路中有主管路,則Branch_Pipe算法需作以下修改:(1)敷設(shè)序列中優(yōu)先排列主管路連接點(diǎn),即優(yōu)先敷設(shè)主管路;(2)主管路布置完成后,按分支管的管徑尺寸重新網(wǎng)格化空間,并標(biāo)記已敷設(shè)的主管路所覆蓋網(wǎng)格;(3)對(duì)序列中的剩余連接點(diǎn)應(yīng)用Improved_SPFA算法后,僅從主管路所覆蓋網(wǎng)格中找出到分支連接點(diǎn)“距離”最小的網(wǎng)格,據(jù)此形成一條分支管路,以保證分支點(diǎn)在主管路上;(4)將新形成分支管路所覆蓋的網(wǎng)格標(biāo)記成障礙,以避免后續(xù)分支管路與其發(fā)生干涉。2.5最佳優(yōu)化條件的確定在標(biāo)準(zhǔn)Dijkstra算法中,如果只關(guān)注從起點(diǎn)到目標(biāo)點(diǎn)的最短路徑,可以在迭代過(guò)程中加入判斷條件,即如果要松弛的頂點(diǎn)就是目標(biāo)頂點(diǎn),則終止迭代過(guò)程。仿照該方法可以在Improved_SPFA方法中步驟12之后加上相同條件來(lái)加速算法的結(jié)束過(guò)程。但是該方法不再保證得到的路徑是最短路徑,因?yàn)榻Y(jié)束時(shí)的目標(biāo)頂點(diǎn)可能還會(huì)被后續(xù)未處理的頂點(diǎn)繼續(xù)松弛改進(jìn)。但這種改進(jìn)對(duì)實(shí)際工程計(jì)算有很大的意義,例如當(dāng)優(yōu)化空間很大、待敷設(shè)管路接口間距離又很接近時(shí),利用該條件可以避免探索大量無(wú)用頂點(diǎn)從而加快搜索速度,并且實(shí)驗(yàn)發(fā)現(xiàn)大多數(shù)情況下,對(duì)于單管敷設(shè)得到的次優(yōu)解與最優(yōu)解是一致的。在敷設(shè)多分支管路時(shí),從某接口網(wǎng)格開(kāi)始擴(kuò)展搜索,當(dāng)擴(kuò)展到已構(gòu)建好的分支管路占據(jù)的網(wǎng)格時(shí)停止,將相遇網(wǎng)格作為該分支的目的連接點(diǎn),避免了搜索全部可用網(wǎng)格空間和在已敷設(shè)分支網(wǎng)格中尋找最近網(wǎng)格的計(jì)算代價(jià),極大地提升了算法效率。2.6網(wǎng)格擴(kuò)展算法管路在沿網(wǎng)格敷設(shè)的過(guò)程中最小的折彎長(zhǎng)度可能只有一個(gè)網(wǎng)格的距離,而網(wǎng)格的尺寸是根據(jù)管徑和管路間的最小距離約束設(shè)置的,可能不滿足特定管路加工時(shí)對(duì)管路材料折彎的剛性要求,或是特定管路內(nèi)輸送介質(zhì)流阻對(duì)管路最小直線距離的要求。為滿足特定管路敷設(shè)過(guò)程中對(duì)最小折彎長(zhǎng)度的要求,在Improved_SPFA中從當(dāng)前網(wǎng)格向相鄰網(wǎng)格擴(kuò)展時(shí)就不能逐點(diǎn)擴(kuò)展,而要在擴(kuò)展方向上按最小折彎長(zhǎng)度向外擴(kuò)展。在采用基于距離的路徑回溯算法時(shí)也要求每次回溯的距離滿足最小折彎長(zhǎng)度約束。修改后的算法敷設(shè)的管路不是距離最短的,但卻是在滿足最小折彎長(zhǎng)度約束管路中距離最短的。但網(wǎng)格擴(kuò)展時(shí)引入最小折彎長(zhǎng)度,每次按固定最小長(zhǎng)度向外擴(kuò)展,將減小搜索空間,在某些情況下無(wú)法生成滿足條件的路徑。如圖3中的算法每次以2個(gè)網(wǎng)格的長(zhǎng)度向外擴(kuò)展,圖3a和圖3c無(wú)法在終點(diǎn)網(wǎng)格要求的管路方向上形成路徑。為此提出以下改進(jìn)策略。設(shè)起點(diǎn)網(wǎng)格為S,方向矢量為α,終點(diǎn)網(wǎng)格為E,方向矢量為β,最小擴(kuò)展長(zhǎng)度為n個(gè)網(wǎng)格。在路徑生成失敗時(shí),每次嘗試在起點(diǎn)S規(guī)定的敷設(shè)方向選擇一個(gè)修正連接點(diǎn)S′,S與S′的距離小于n;在終點(diǎn)E規(guī)定的敷設(shè)方向擴(kuò)展出n-1個(gè)修正連接點(diǎn)E′,運(yùn)行算法,S′到E(或E′)可形成路徑并滿足管路接口對(duì)初始方向的要求,則路徑生成成功。最終路徑由SS′,S′E′,E′E構(gòu)成。圖3b和圖3d為應(yīng)用改進(jìn)策略得到路徑的過(guò)程。2.7按兩種約束方式得到的管路成束布置管路支架可以提高管路承重、減少管路振動(dòng)和變形、限制管路走向,是管路敷設(shè)的重要約束。本文將支架視為管路附件進(jìn)行布置,在通過(guò)算法得到管路的可行路徑之后添加支架等附件,例如每隔一個(gè)固定的距離設(shè)置一個(gè)支架。在管路布置時(shí)考慮管路的貼壁約束,以方便支架的安裝和節(jié)省空間。對(duì)于走向和性質(zhì)相近的管路,為了共用支架以方便安裝和節(jié)省成本,可以在已敷設(shè)管路的適當(dāng)位置安裝支架,然后將支架位置指定為后敷設(shè)管路的中間連接點(diǎn),利用本文算法敷設(shè)各連接點(diǎn)之間的管路,最后連接各管路段以形成共享支架、成束敷設(shè)的管路。前文提出的通過(guò)設(shè)置管路周圍網(wǎng)格能量值來(lái)引導(dǎo)管路成束敷設(shè)的約束較弱,例如在不同管路原始連接點(diǎn)相距較遠(yuǎn)時(shí),就可能起不到引導(dǎo)作用,而通過(guò)支架限制的方式,可以保證管路的成束敷設(shè),是強(qiáng)約束,但同時(shí)也降低了求解的靈活性,圖4為按兩種不同約束方式得到的管路成束布置效果。此外,本文方法未考慮支架占用空間,實(shí)際應(yīng)用中需對(duì)管路位置做適當(dāng)修正以滿足支架安裝需求。3實(shí)驗(yàn)與結(jié)果分析3.1模擬示例3.1.1設(shè)置希望偏離的設(shè)置設(shè)計(jì)模型如圖5所示。敷設(shè)空間定義為30m×6m×12m的立方體,中心點(diǎn)定義為坐標(biāo)原點(diǎn)(0,0,0);布置空間內(nèi)有設(shè)備M1~M10,虛擬障礙物R1~R5。敷設(shè)空間內(nèi)設(shè)備及障礙物的位置用對(duì)角坐標(biāo)點(diǎn)表示如下:式中:R1用來(lái)控制管路避開(kāi)中心部位,為在建造和維修階段所用的吊車、絞車和移動(dòng)設(shè)備提供操作空間,在其周圍設(shè)有希望遠(yuǎn)離的能量分布帶;R2用來(lái)為設(shè)備M2提供維修空間;R3為限制管路通過(guò)的過(guò)道空間;M9為一燃油箱,因此在其上部設(shè)置虛擬障礙R4,以防止高溫管路通過(guò)上方,并且為保證安全在M9周圍設(shè)有希望遠(yuǎn)離的能量分布帶;M10為配電板,其上部設(shè)置虛擬障礙物R5,以限制水管、油管、蒸汽管等通過(guò)。待敷設(shè)的管路有8條,直徑為0.2m~0.3m的管路為P1和P2,敷設(shè)時(shí)將空間按100×20×40網(wǎng)格化;直徑為0.1m~0.2m的管路為一條多分支管路P3,不設(shè)主次分支,敷設(shè)時(shí)將空間按150×30×60網(wǎng)格化;直徑為0.1m以下的管路為P4~P8,敷設(shè)時(shí)將空間按300×60×120網(wǎng)格化。網(wǎng)格化時(shí)若障礙物邊界位于某些網(wǎng)格內(nèi),則將這些網(wǎng)格擴(kuò)展為障礙物。網(wǎng)格用行、列、層編號(hào)(從0開(kāi)始)來(lái)描述位置。各管路接口的網(wǎng)格坐標(biāo)如下:式中:SpLength,SpWidth,SpHeight為敷設(shè)空間尺寸;cellLength,cellWidth,cellHeight為網(wǎng)格化時(shí)網(wǎng)格尺寸;FLOOR為向下取整函數(shù)。3.1.2自動(dòng)敷設(shè)結(jié)果算法設(shè)置如下:管路敷設(shè)順序從P1~P8,分支管路P3的接口按前文數(shù)據(jù)依次選擇;距離松弛函數(shù)的網(wǎng)格能量權(quán)重值為1;管路最小折彎長(zhǎng)度不小于2個(gè)網(wǎng)格邊長(zhǎng);優(yōu)化方法選擇SLF;管路敷設(shè)結(jié)束按最優(yōu)管路生成條件;成束敷設(shè)策略選擇按網(wǎng)格能量引導(dǎo);路徑生成按基于距離的回溯方法。本文自動(dòng)敷設(shè)方法的布置結(jié)果如圖6所示,能夠滿足的約束包括:(1)物理約束管路能夠連接指定接口,且各管路之間、管路與設(shè)備之間無(wú)干涉。(2)生產(chǎn)或安裝約束管路沿艙壁或鋼結(jié)構(gòu)件平行或垂直敷設(shè);走向相近的管路盡可能成束敷設(shè),參見(jiàn)管路P1和P2的布置;管路滿足對(duì)最小折彎長(zhǎng)度的要求。(3)安全性和維護(hù)性約束管路避開(kāi)操作空間、通道空間、設(shè)備維修空間、鍋爐和配電板等設(shè)備上方敷設(shè);管路適當(dāng)遠(yuǎn)離中心操作空間和高溫鍋爐進(jìn)行敷設(shè),參見(jiàn)管路P1,P2和P5在R1和M9周圍的布置。(4)經(jīng)濟(jì)性約束管路在滿足以上約束的同時(shí),長(zhǎng)度盡可能短且彎頭數(shù)目盡可能少。3.1.3實(shí)驗(yàn)結(jié)果分析實(shí)驗(yàn)機(jī)器配置:Intel(R)Core(TM)i3CPU@2.67GHz;RAM2G;Windows7。表1為不同優(yōu)化后算法與基本SPFA效率的對(duì)比(算法均采用最優(yōu)終止條件)。分析實(shí)驗(yàn)數(shù)據(jù)可以得出以下結(jié)論:(1)本文方法求解管路布置效率很高,敷設(shè)空間按300×60×120網(wǎng)格化時(shí),SLF_LLL優(yōu)化算法耗時(shí)最多的一條管路約為1.2s;文獻(xiàn)在20×20×20網(wǎng)格空間對(duì)一條單管路采用遺傳算法進(jìn)行布置,收斂至最優(yōu)解耗時(shí)30s。(2)基于敷設(shè)8條管路的總時(shí)間對(duì)SPFA各優(yōu)化方法在時(shí)間效率方面進(jìn)行比較,SLF提升58%,LLL提升20%,SLF聯(lián)合LLL提升66%;SLF對(duì)算法的改進(jìn)效果顯著,LLL算法改進(jìn)效果相對(duì)較小且不穩(wěn)定,甚至在個(gè)別情況出現(xiàn)退化,SLF結(jié)合LLL算法改進(jìn)效果最佳,但改進(jìn)效果并非兩種改進(jìn)策略的累加效果。3.2實(shí)際船海水熱水系統(tǒng)的管道配置3.2.1海水冷卻系統(tǒng)的布置以一艘船舶為實(shí)例,總長(zhǎng)116m,型寬18m,型深8.35m,設(shè)計(jì)吃水5.4m,主機(jī)型號(hào)6S35MC,航速16.7節(jié)。以其機(jī)艙中海水冷卻系統(tǒng)管路設(shè)計(jì)為例驗(yàn)證本文算法的有效性。實(shí)例數(shù)據(jù)取自文獻(xiàn),其建模方法與本文相同,但使用基于模板的路徑生成法進(jìn)行管路布置,后文將對(duì)比兩者的布置結(jié)果。圖7中陰影部分為海水冷卻系統(tǒng)的布置范圍。在布置海水冷卻系統(tǒng)管路時(shí),只需對(duì)一定范圍內(nèi)的船艙空間及內(nèi)部設(shè)備建模即可,文獻(xiàn)模型如圖8a所示,其中給出了雙層底和花鋼板的位置。本文方法建模時(shí)艙內(nèi)物體與原模型相同,雙層底及花鋼板將作為影響管路敷設(shè)的約束條件,布置空間規(guī)范成能容納相關(guān)設(shè)備的外包絡(luò)矩形空間,模型如圖8b所示。待連接的管系設(shè)備包括:低位海水箱(A),高位海水箱(B),停泊冷卻海水泵(C),主海水泵1(D),主海水泵2(E)。影響管系布置的周邊設(shè)備包括:輔空氣瓶(F),主空氣瓶1(G),主空氣瓶2(H),控制空氣瓶(I),汽笛空氣瓶(J),霧笛空氣瓶(K),雜用空氣瓶(L),海水淡化裝置海水泵(M),制淡裝置海水泵(N),消防泵(O),蒸餾水艙(P),總用泵(Q),艙底泵(R)。關(guān)于詳細(xì)的布置需求,請(qǐng)參考文獻(xiàn)。此處僅列出管路接口的部分信息,如表2所示。3.2.2利益調(diào)節(jié)及其他布置利用本文方法布置此實(shí)例管系需要處理以下約束條件:(1)為保證管路布置對(duì)接口方向的要求,從起點(diǎn)位置按規(guī)定接口方向向外延展適當(dāng)距離,得到的新位置作為算法處理的管路