基于動(dòng)態(tài)規(guī)劃的多波束測(cè)線布設(shè)模型

王 楠，俞治丞，王景賢

（南京信息工程大學(xué) 大氣物理學(xué)院， 南京 210044）

聲波波束測(cè)深法是利用聲波傳播原理進(jìn)行海水測(cè)深的常用方法，其原理為測(cè)量船換能器垂直向海底發(fā)射聲波信號(hào)，并接收反射聲波信號(hào)，利用發(fā)射波與反射波時(shí)間差實(shí)現(xiàn)海水測(cè)深。為了獲得某一海域較為全面的深度數(shù)據(jù)，通常使用多波束測(cè)深法進(jìn)行測(cè)量。多波束測(cè)深法一次發(fā)射數(shù)十乃至上百個(gè)波束，能測(cè)得以測(cè)量船測(cè)線為軸線且具有一定寬度的全覆蓋水深條帶。為保證測(cè)量便利性和數(shù)據(jù)完整性，相鄰條帶間應(yīng)有10 %～20 %的重疊率。由于真實(shí)海底地形起伏變化大，若測(cè)線間隔布設(shè)不合理，易出現(xiàn)漏測(cè)，或因重疊率過高導(dǎo)致數(shù)據(jù)冗余量增大，影響測(cè)量質(zhì)量和效率。本文針對(duì)2023 年高教社杯全國大學(xué)生數(shù)學(xué)建模競(jìng)賽（CUMCM）B 題給出的四個(gè)問題[1]，基于幾何原理，建立了海底坡面多波束測(cè)深平面模型、變化測(cè)線方向的多波束三維覆蓋模型、單目標(biāo)規(guī)劃模型和微元測(cè)線規(guī)劃模型，探究不同海域情況下的多波束測(cè)線布設(shè)優(yōu)化方案。

1 問題一模型的建立與求解

問題一設(shè)定與測(cè)線方向垂直的平面（以下簡(jiǎn)稱為測(cè)線垂面）和海底坡面的交線構(gòu)成一條斜線，其與海平面的夾角為α，要求建立多波束測(cè)深的覆蓋寬度與相鄰條帶重疊率的數(shù)學(xué)模型，并求解特定位置覆蓋寬度、重疊率等指標(biāo)。

1.1 海底坡面條帶覆蓋研究

如圖1 所示，由于海底具有一定坡面，可觀察到的覆蓋條寬度應(yīng)為坡面覆蓋長(zhǎng)度在水平面上的投影。設(shè)可觀察到的覆蓋寬度為w，

其中，W 為坡面覆蓋長(zhǎng)度。若測(cè)線1 處海水深度為D1，測(cè)線2 處海水深度為D2，測(cè)線間距為d，則滿足，

若線段AC 與BD 的長(zhǎng)度分別為W11，W22，換能器夾角為θ，可通過解三角形得到測(cè)線1 覆蓋區(qū)域與測(cè)線2 覆蓋區(qū)域的重疊率為

根據(jù)三角關(guān)系，測(cè)線1 覆蓋寬度為[2]

測(cè)線2 覆蓋寬度的求解方法同測(cè)線1。

1.2 特定海底坡面條帶覆蓋求解

已知某特定海底坡面，其中心深度為D0=70 m，則根據(jù)1.1 模型，第i 條（i=-4，-3，…，4）測(cè)線的對(duì)應(yīng)海水深度Di、覆蓋寬度wi分別為

第i 條測(cè)線與第i+1 條測(cè)線（i=-4，-3，…，3）覆蓋區(qū)域重疊率為

已知測(cè)線間距Δd=200 m，且ΔD=Δdtan α，代入已知數(shù)據(jù)即可求解得到該海域多條測(cè)線處海水深度、覆蓋寬度與覆蓋區(qū)域重疊率，計(jì)算結(jié)果見表1。

由表1 可以看出：測(cè)線間距為200 m 時(shí)，僅有0 m 與200 m 海域覆蓋區(qū)域的重疊率滿足10%～20 %的測(cè)量便利性與數(shù)據(jù)完整性條件；重疊率為負(fù)值表示存在漏側(cè)。因此，在200 m 與400 m 海域間可適當(dāng)減小測(cè)線間距d，使得其覆蓋區(qū)域重疊率增大；在-800 m 與-200 m 海域間可增大測(cè)線間距d，使得其覆蓋區(qū)域重疊率減小。

2 問題二模型的建立與求解

問題二中，測(cè)線方向與海底坡面法向在水平面上投影的夾角為β，要求給出特定β 取值下多波束測(cè)深的覆蓋寬度。為便于研究，需要將問題一的平面模型擴(kuò)展為三維立體模型。建立海底坡面的三維坐標(biāo)系，如圖2 所示。

圖2 海底坡面三維坐標(biāo)系示意

2.1 沿測(cè)線海水深度變化研究

當(dāng)測(cè)量船沿測(cè)線方向前進(jìn)l 時(shí)，該路程中海水深度的變化量為

式中，γ1為測(cè)線垂面與坡面交線（圖2 中線段AB）與海平面的夾角，可以通過解析測(cè)線垂面與海底坡面的法向量求得。若測(cè)線垂面法向量為海底坡面法向量為，那么γ1滿足

2.2 測(cè)線覆蓋區(qū)域分析

在三維坐標(biāo)系下研究測(cè)線的覆蓋區(qū)域時(shí)，需要作垂直于測(cè)線方向的平面，該平面即為發(fā)射波所在的平面，其與海底坡面的交線即為測(cè)線覆蓋區(qū)域。若該平面在海底坡面三維坐標(biāo)系下的法向量為則其與海底坡面的交線與海平面的夾角γ2可以表示為

γ2的意義與問題一中角α 的意義相似，則可將問題二的三維問題轉(zhuǎn)變?yōu)楹Ｋ疃妊販y(cè)線變化的二維平面問題。通過對(duì)三維平面的解析，得到變化測(cè)線方向的多波束測(cè)深情況下覆蓋寬度wm的表達(dá)式，

其中，D（β，l）為夾角為β 的測(cè)線行進(jìn)路程l 時(shí)的海水深度，其變化量由公式（8）確定。

2.3 特定位置覆蓋寬度求解

問題二需要求解β 的8 個(gè)取值，測(cè)量船沿測(cè)線方向運(yùn)動(dòng)2.1 海里，每間隔0.3 海里測(cè)量一次海底情況。當(dāng)β∈（π/2，3π/2）時(shí)，在測(cè)線方向上海水深度逐漸減小；當(dāng)β∈（0，π/2）∪（3π/2，2π）時(shí)，在測(cè)線方向上海水深度逐漸增大。已知l=0時(shí)的海水深度，可以對(duì)海水深度進(jìn)行離散化分段求解，表達(dá)式為

進(jìn)而得到在（iπ/4，iΔl）情況下的覆蓋寬度的表達(dá)式為

將賽題給定的換能器夾角等已知條件代入上述公式，即可求解得到不同測(cè)線方向、不同船體位置情況下的覆蓋寬度。由于海底為固定坡面，在各個(gè)測(cè)量方向上，覆蓋寬度呈線性變化，并具有對(duì)稱性特征，如圖3 所示。

圖3 覆蓋寬度與測(cè)線方向、船體位置關(guān)系

3 問題三模型的建立與求解

問題三限定了一片南北長(zhǎng)2 海里、東西長(zhǎng)4海里的矩形海域，海底依然具有一定坡度，且西深東淺，要求設(shè)計(jì)滿足重疊率條件、可以完全覆蓋該海域的多條測(cè)線，并盡可能使測(cè)線長(zhǎng)度最短。為便于測(cè)量海底情況和計(jì)算重疊率，盡可能確保不漏測(cè)，測(cè)線應(yīng)均為直線[3]，且測(cè)區(qū)內(nèi)的各主測(cè)線應(yīng)為平行關(guān)系。

3.1 南北方向平行測(cè)線設(shè)計(jì)

為使得測(cè)線盡可能分布稀疏，直接考慮相鄰兩側(cè)線之間重疊10 %的情況。先確定第一條南北向測(cè)線，使得測(cè)線條帶覆蓋區(qū)域左邊界與矩形海域西邊界完全重合。再以重疊率為10 %確定下一條測(cè)線。以此類推，從西到東設(shè)計(jì)出可以覆蓋矩形海域、重疊率固定為10 %的多條測(cè)線（如圖4 所示）。最后計(jì)算測(cè)線總長(zhǎng)度。

圖4 測(cè)線條帶覆蓋示意

第一條測(cè)線對(duì)應(yīng)坐標(biāo)x0應(yīng)與測(cè)線左覆蓋區(qū)域長(zhǎng)度一致，x0的表達(dá)式為

由于設(shè)定兩條測(cè)線的覆蓋區(qū)域重疊率為10%，根據(jù)重疊關(guān)系求解得到第一條測(cè)線的右側(cè)坡面覆蓋長(zhǎng)度為

第二條測(cè)線的位置坐標(biāo)為

同理，對(duì)于第i 條測(cè)線的坐標(biāo)，可以得到迭代公式。再根據(jù)初值條件Dleft=110+2×1 852tanα，通過迭代可以得到第1 條到第n 條測(cè)線的坐標(biāo)。

綜上，動(dòng)態(tài)規(guī)劃求解模型為

根據(jù)上述計(jì)算，當(dāng)兩兩測(cè)線的重疊率固定為10 %時(shí)，求解得到在南北方向上共需要設(shè)計(jì)34條測(cè)線，測(cè)線總長(zhǎng)度為125 936 m。南北向平行設(shè)計(jì)測(cè)線時(shí)，覆蓋率與測(cè)線條數(shù)呈線性關(guān)系，覆蓋率越大，測(cè)線條數(shù)越多。因此，10 %重疊率情況下測(cè)線總長(zhǎng)度最小。

3.2 東西方向平行測(cè)線設(shè)計(jì)

當(dāng)船自西向東移動(dòng)時(shí)，船體所在海域的深度越來越淺，覆蓋寬度也越來越小，沿測(cè)線方向覆蓋區(qū)域形狀為梯形。在較深處，可能會(huì)重疊率過大，而在較淺處，則可能會(huì)漏測(cè)。當(dāng)深度變化不大時(shí)，梯形趨近于一個(gè)矩形，深處與淺處的重疊率相近，在合理設(shè)計(jì)下可完全覆蓋海域，且重疊率為10 %～20 %。

經(jīng)計(jì)算，矩形海域西邊界最深處海水的深度為Dleft=206.94 m，東邊界最淺處海水深度為Dleft=13.06 m。借助問題二模型進(jìn)行簡(jiǎn)單計(jì)算，可以發(fā)現(xiàn)在最深處只需設(shè)計(jì)6 條測(cè)線，而在最淺處則需設(shè)計(jì)高達(dá)上百條測(cè)線。測(cè)線數(shù)差別過大，必定會(huì)產(chǎn)生漏測(cè)與重疊率過高的情況。因此，所有測(cè)線呈東西走向是不合理的。與此類似，所有斜向平行測(cè)線設(shè)計(jì)也無法解決類似問題。

綜上，該矩形海域最優(yōu)布設(shè)策略為：南北向平行設(shè)計(jì)34 條測(cè)線，測(cè)線總長(zhǎng)為125 936 m，測(cè)線具體布設(shè)如圖5 所示。

圖5 南北方向測(cè)線布設(shè)設(shè)計(jì)

4 問題四模型的建立與求解

問題四要求針對(duì)一個(gè)海底凹凸不平的實(shí)際海域進(jìn)行測(cè)線布設(shè)設(shè)計(jì)。現(xiàn)已給出該海域（南北長(zhǎng)5 海里、東西寬5 海里）的歷史單波束測(cè)深情況。以此數(shù)據(jù)為基礎(chǔ)，對(duì)該海域重新進(jìn)行更為精確的多波束測(cè)深設(shè)計(jì)，并嘗試求解測(cè)線布設(shè)的最優(yōu)方案。

4.1 海域信息分析

若多條等深線近似平行，且相鄰兩條等深線的距離近似相等，則可認(rèn)為這些等深線代表一個(gè)固定坡度的坡面。為簡(jiǎn)化問題，將近似相互平行且距離相近的多條相鄰等深線歸為一組，其對(duì)應(yīng)的海域可近似為具有固定坡度的坡面。

依據(jù)所給單波束測(cè)深數(shù)據(jù)，繪制等深線圖，并將該海域分成三個(gè)區(qū)域進(jìn)行分析，如圖6 所示。

圖6 按等深線分區(qū)示意

4.2 固定坡面區(qū)域①、②測(cè)線設(shè)計(jì)

區(qū)域①與區(qū)域②的等深線基本相互平行且兩兩相距較近，故可將這兩個(gè)分區(qū)擬合成一個(gè)固定坡面。如圖6，區(qū)域①可近似為一個(gè)直角三角形，即擬合出了一個(gè)上界為-80 m，下界為-197.20 m的坡面。根據(jù)問題三設(shè)計(jì)方案，沿等深線布設(shè)測(cè)線是最優(yōu)方案。選取合適坐標(biāo)點(diǎn)求解得到該擬合坡面坡度α1=0.046 2 rad。利用動(dòng)態(tài)規(guī)劃的求解思想，結(jié)合問題三模型與區(qū)域邊界條件，可求解得到三角區(qū)域覆蓋寬度的表達(dá)式。

區(qū)域①為三角形海域，按照上述算法會(huì)出現(xiàn)漏測(cè)區(qū)域。根據(jù)三角關(guān)系，求得漏測(cè)區(qū)域面積的表達(dá)式為

其中，? 為測(cè)線與海平面的夾角。在區(qū)域①中，重疊率固定為10 %，存在一定的漏測(cè)率。通過上述分析，使用動(dòng)態(tài)規(guī)劃求解得到區(qū)域①測(cè)線總長(zhǎng)度為32 098 m。

同理，將區(qū)域②擬合為北深南淺的固定坡面。區(qū)域②最優(yōu)解為測(cè)線方向?yàn)檎龞|正西、覆蓋率恒定為10 %。由于區(qū)域②為矩形海域，則可直接利用問題三的模型進(jìn)行求解，得到區(qū)域②測(cè)線總長(zhǎng)度為66 672 m，且不會(huì)出現(xiàn)漏測(cè)區(qū)域。

4.3 基于微元法的區(qū)域③測(cè)線設(shè)計(jì)

由圖6 可知，區(qū)域③的等深線具有一定折角，因此，不可使用固定坡度擬合方法簡(jiǎn)化處理。若要使得區(qū)域③測(cè)線設(shè)計(jì)盡可能優(yōu)化，仍需使測(cè)線盡可能沿等深線分布。

區(qū)域③的右邊界處等深線近似平行且間距較近，在該范圍內(nèi)進(jìn)行固定坡面擬合，從所給數(shù)據(jù)中取點(diǎn)計(jì)算，可估算其大致坡度為0.054 rad。以-80 m與-60 m 之間的某等深線D0為起始位置，固定覆蓋率為10 %，自東向西設(shè)計(jì)測(cè)線。

以等深線-D0在所給數(shù)據(jù)中篩選對(duì)應(yīng)深度，得到等深線附近散點(diǎn)的集合，其中散點(diǎn)Pi的坐標(biāo)為（xi，yi，zi）。由于散點(diǎn)間距極小，為方便后續(xù)計(jì)算，令各散點(diǎn)上測(cè)線方向均為正南正北向。在坡面固定為=0.054 rad 時(shí)，可求得Pi處覆蓋寬度為

結(jié)合公式（19）、（20），可根據(jù)前一測(cè)線的估計(jì)坡度與大量散點(diǎn)坐標(biāo)，確定下一測(cè)線的估計(jì)坡度與散點(diǎn)坐標(biāo)，據(jù)此迭代直至結(jié)束。

初始位置的選擇在該迭代過程中至關(guān)重要，使用遺傳算法求解以下規(guī)劃模型：

其中，j=0，1，…，n-1。

采用遺傳算法[4]求解得最小測(cè)線下的最優(yōu)D0為-75 m，該初始測(cè)線矩形覆蓋區(qū)域的右邊界恰好與-80 m 深度線重合，且未浪費(fèi)覆蓋空間。

圖7 為區(qū)域③具體測(cè)線的走向。由圖7 可看出，海水深度在東南方向較深，在西南方向較淺，符合等深線的走向。

圖7 區(qū)域③測(cè)線設(shè)計(jì)示意

在所得測(cè)線布設(shè)下，利用動(dòng)態(tài)規(guī)劃和基于遺傳算法的微元法即可得最短測(cè)線總長(zhǎng)為308 800 m。因?yàn)閰^(qū)域②為矩形且深度分布較為均勻，所以區(qū)域②為滿覆蓋情況，而區(qū)域③是微元法求解，誤差很小，因此只需要計(jì)算區(qū)域①的漏測(cè)面積，即可得到漏測(cè)百分比，為0.211 9 %。由于區(qū)域②在區(qū)域下邊緣處布設(shè)的測(cè)線覆蓋寬度超出原有區(qū)域，與區(qū)域③重疊較多，而區(qū)域②測(cè)線為正東西走向，長(zhǎng)度為4 海里。此外，區(qū)域①和③臨界處覆蓋率小于20 %，因此重疊率超過20 %部分的總長(zhǎng)度即為區(qū)域②測(cè)線長(zhǎng)度，為7 408 m。

綜上，經(jīng)計(jì)算得到測(cè)線總長(zhǎng)度為308 800 m，漏測(cè)區(qū)域占總待測(cè)海域面積的0.219 9 %。表明在上述測(cè)線布設(shè)下近似滿足全覆蓋要求，重疊率超過20 %部分的總長(zhǎng)度為7 408 m，仍有部分區(qū)域數(shù)據(jù)冗余，模型存在改進(jìn)空間。