基于多周期目標的海上救助船配置優(yōu)化

陳曉旭 鐘銘

【關(guān)鍵詞】 救助船;救助站點;配置;多周期;多目標蟻群算法

0 引 言

在海上交通流量不斷增加的同時海上事故數(shù)量也在增加。交通運輸部海上搜救中心的統(tǒng)計數(shù)據(jù)顯示，每個月都有近百起各種類型各種等級的海上事故。據(jù)統(tǒng)計，2017―2020年，我國海域共計發(fā)生事故起，平均每年發(fā)生約起。這些事故不僅造成了巨大的人員傷亡和財產(chǎn)損失，而且對社會和海洋環(huán)境也造成了極大的破壞。事故發(fā)生的數(shù)量與位置是隨著時間的變化而變化的，以不變的救助船配置計劃應(yīng)對時刻變化的事故是不科學(xué)的，在一定程度上會影響救助效果，造成資源的閑置與浪費。因此，本文研究多周期目標救助船動態(tài)配置方案，以保證救助船配置在每一時期都能達到最優(yōu)，提高救助效率。

近年來，國內(nèi)外專家和學(xué)者在海上救助船配置方面作了許多深入研究。但這些研究的主要不足之處是：（1）多著重于考慮船舶類型、響應(yīng)時間以及救援成本等對救助船進行靜態(tài)配置，未充分研究如何對救助船進行動態(tài)配置;（2）多周期目標配置模型會產(chǎn)生調(diào)度成本，有的學(xué)者在研究中會設(shè)定一個固定值，而現(xiàn)實中調(diào)度救助船要考慮很多因素的影響，比如距離、救助船的類型等;（3）忽視了救助船的可用性及救助能力對救助船配置的影響。針對這些不足，筆者根據(jù)海上事故發(fā)生規(guī)律，擬定幾個周期，對每個周期的每個站點的救助船進行配置，使得每個周期的救助船配置達到最優(yōu)，并在周期間調(diào)度船舶，確保事故需求區(qū)域在任何時候都能得到良好的覆蓋。本文構(gòu)建多周期的救助船配置模型，目標是最大化救助站點覆蓋的事故數(shù)量以及最小化救助船調(diào)度的成本，并使用多目標蟻群算法求解模型，以渤海海域為例驗證模型與算法的有效性。

1 問題描述與建模

本文所要研究的問題是考慮到事故發(fā)生的時變性（即事故發(fā)生的數(shù)量和位置隨時間不斷變化的特性）與救助船的不可獲得性，如何對海上救助船進行多周期配置?？紤]在不同周期的每個時期內(nèi)，從候選救助站點中選擇合適的救助站點，并配置不同類型的救助船數(shù)量，以使得目標函數(shù)達到最優(yōu)解。

為方便對海上應(yīng)急救助船進行多周期配置優(yōu)化，筆者作出如下假設(shè)：

（1）每次發(fā)生事故造成的人員傷亡數(shù)量不同，產(chǎn)生的救助需求也不同，根據(jù)事故等級標準規(guī)定，隨機產(chǎn)生每起事故的遇險人數(shù)表示每起事故的需求。

（2）綜合考慮海上事故發(fā)生規(guī)律，以一年為一個規(guī)劃期對救助船進行規(guī)劃。

（3）按救助船就近調(diào)度原則，避免在各地點之間對同一救助船重復(fù)往返調(diào)度。由于海上事故與陸上事故不同，為方便計算，不考慮正在執(zhí)行救助任務(wù)的救助船，調(diào)度成本只考慮距離因素。

多周期的救助船配置模型的目的是在所有的周期t∈T（T={1，2，…，n}）內(nèi)從候選的救助站點中決定救助站點配置的救助船數(shù)量，從而使救助船能夠在標準救助時間內(nèi)到達所有的事故需求區(qū)域，即最大化救助站點覆蓋事故數(shù)量和最小化調(diào)度救助船的成本。

相關(guān)參數(shù)說明如下的數(shù)學(xué)符號表示：

（1）集合。K為救助船類型集合，k∈K; T為所有周期的集合，t∈T; I為救助站點集合，i∈I; J為事故區(qū)域點集合，j∈J;Ka為能夠響應(yīng)a等級事故的船舶類型集合，k∈Ka; ?K 為t時期能在r時間內(nèi)從救助站點j到達事故區(qū)域點i的救助船類型集合，k∈K ; K 為t時期不能在r時間內(nèi)從救助站點j到達事故區(qū)域點i的救助船類型集合，k∈K ; J 為t時期能在r時間內(nèi)從到達事故區(qū)域點i的救助站點集合， j∈J ; ?Iw為高風(fēng)險事故區(qū)域點集合，i∈I ; A為事故風(fēng)險等級集合，a∈A。

（2）參數(shù)。 為事故區(qū)域點i在t時期發(fā)生的a等級事故的次數(shù);vk為k型救助船的速度;為在t時期k型救助船從救助站點j到救助站點j'的距離;nK為救援系統(tǒng)中最大救助船數(shù)量;njK為救助站點j允許?？康淖畲缶戎瑪?shù)量;nk為k型救助船的最大數(shù)量;nt為t時期可用的救助船數(shù)量;s為k型救助船在t時期的供給能力; 為在t時期事故區(qū)域點i發(fā)生的a等級事故的救助船需求量;bk為k型救助船單位距離產(chǎn)生的燃油成本。

（3）決策變量。 為在t時期在救助站點j布置k型救助船時， =1，否則 =0; 為在t時期救助站點j的k型救助船能夠覆蓋事故區(qū)域點i時， =1，否則 =0; 為在t時期在救助站點j配置的k型救助船數(shù)量; 為從t時期至t+1時期內(nèi)，從救助站點j' 調(diào)度到備選救助站點j的k型救助船數(shù)量。

式（1）、式（2）表示模型的目標函數(shù)，式（1）要求在不同周期間調(diào)度救助船的成本最小，式（2）表示最大化所有站點能夠覆蓋的事故數(shù)量。式（3）表示t時期在救助站點j的k型救助船到達事故區(qū)域點i的距離要小于在規(guī)定時間內(nèi)在救助站點j的k型救助船能夠到達的最遠距離。式（4）表示在t時期內(nèi)救助站點j部署的k型救助船是否能夠覆蓋事故區(qū)域點i，到事故區(qū)域點i的最大時間要小于規(guī)定的響應(yīng)時間。式（5）表示t時期在r時間內(nèi)能夠到達事故區(qū)域點i的救助站點合集。式（6）全覆蓋約束：保證每一時期所有事故區(qū)域點i能在規(guī)定的響應(yīng)時間內(nèi)被覆蓋。式（7）多重覆蓋約束：在每一時期內(nèi)，高風(fēng)險事故區(qū)域點i能在規(guī)定的響應(yīng)時間內(nèi)被覆蓋兩次以上，保證了高風(fēng)險事故區(qū)域點能夠有2艘以上的救助船響應(yīng)。式（8）表示所有站點分配的救助船數(shù)量不能超過該類型救助船的總可使用數(shù)量。式（9）表示每個時期分配給各個救助站點的救助船數(shù)量應(yīng)當(dāng)小于該時期可用的救助船數(shù)量。式（10）表示當(dāng)救助站點j的k型救助船不能覆蓋事故區(qū)域點i時，在救助站點j的k型救助船數(shù)量為0。式（11）表示在每個救助站點放置的救助船數(shù)量不能超過該救助站點可放置的最大救助船數(shù)量。式（12）多周期配置數(shù)量約束：表示經(jīng)歷救助船的調(diào)度后救助站點j的救助船數(shù)量變化，t+1期的救助船數(shù)量等于t時期的救助船數(shù)量加上從別的救助站點到救助站點j的救助船數(shù)量再減去從救助站點j到別的救助站點的救助船數(shù)量。式（13）供求約束：表示在每個時期內(nèi)配置的救助船所提供的供給能力要大于該時段各個需求區(qū)域產(chǎn)生的不同等級的需求。式（14）、式（15）變量約束：x 、x 為0-1變量。

2 算法設(shè)計

由于蟻群算法中蟻群的正反饋機制能夠在較快的時間內(nèi)獲得最優(yōu)解，且多周期救助船配置模型是一個非確定性難題（NP-Hard），難以在有限的時間和資源下得出精確解;因此，本文在經(jīng)典的蟻群算法的基礎(chǔ)上，根據(jù)多周期多目標救助船配置模型的特點設(shè)計多目標蟻群算法求解。此外，多周期模型的求解規(guī)模遠遠大于單一時段的求解規(guī)模，直接利用蟻群算法編碼多周期的解會使計算規(guī)模呈指數(shù)增長，降低解的精確性。結(jié)合貪婪算法的思想，利用蟻群算法尋求每一時段的最優(yōu)解，再通過對時段循環(huán)迭代得到最優(yōu)解。

（6）進入下一個周期p=p 1，在每個周期都重新初始化該周期對應(yīng)的事故需求數(shù)量和空間分布以及救助船不可獲得率。

（7）得到所有周期的優(yōu)化結(jié)果，計算救助船調(diào)度的成本與救助站點覆蓋的事故數(shù)量。

3 實例驗證及結(jié)果分析

3.1 數(shù)據(jù)收集

本文以渤海海域的數(shù)據(jù)為例，首先對渤海海域2017―2020年的數(shù)據(jù)進行統(tǒng)計分析，獲得渤海海域事故發(fā)生規(guī)律，并以此為依據(jù)選擇劃分的周期。對收集的數(shù)據(jù)使用k-means算法獲得事故區(qū)域中心坐標（見表1）。結(jié)合渤海海域船舶部署現(xiàn)狀與事故分布現(xiàn)狀，選擇的候選救助站點坐標（見表2）。渤海海域現(xiàn)有專業(yè)救助船信息見表3。

3.2.1 不同周期下的站點選擇結(jié)果分析

以2017―2020年的數(shù)據(jù)為參考依據(jù)，對一整年的專業(yè)救助船進行多周期配置。多周期配置中不同的周期劃分得到的優(yōu)化結(jié)果不同。周期的劃分必須符合事故發(fā)生的周期性規(guī)律。雖然海上事故在每周、每天甚至每小時發(fā)生的數(shù)量與位置都存在一定的周期性，但數(shù)量較少，以較短的時間作為一整個周期會產(chǎn)生較大的成本，不符合經(jīng)濟性原則。因此，以渤海海域事故發(fā)生規(guī)律為依據(jù)，劃分以半年（T=2）、季度（T=4）、月度（T=12）為間隔的3種不同的周期對救助船進行動態(tài)配置與調(diào)度，分析不同周期下的配置結(jié)果與一整年的配置結(jié)果的差異。

分析算法運行得到的配置結(jié)果，可獲得在不同周期下每個救助站點被選中的概率，得到在多周期優(yōu)化配置中每個救助站點的重要程度，從而為決策者是新建應(yīng)急救助基地還是配置更多救助船提供參考依據(jù)。由不同的周期中救助站點被選中的概率（見圖1）可以看出，0、1、3、4、6、11、13這7個救助站點在不同周期中被選中的概率較高，在劃分的每個周期內(nèi)被選中的概率都在90%以上。這是由于在這些救助站點附近海域發(fā)生的事故數(shù)較多，需要較多的救助船類型和數(shù)量，同時在這些救助站點部署救助船，能夠在較短的時間內(nèi)啟動事故響應(yīng)機制，達到更好的救助效果。選中概率較低的救助站點，說明在該站點附近海域發(fā)生的事故數(shù)量較少，在該救助站點配置救助船能夠覆蓋的事故數(shù)較少以及該救助站點距離其他事故區(qū)域較遠，不能實現(xiàn)多重覆蓋。從另一方面來看，被選中概率較低的救助站點也是不可或缺的：只要救助站點被選中的概率大于0，就說明在某個時期該救助站點附近海域發(fā)生了事故，產(chǎn)生了需求;如果忽略這些需求可能會造成人員的生命財產(chǎn)損失。因此，可以考慮在某些選中概率較低的救助站點周期性地配置救助船，實行24 h值班，預(yù)防事故的發(fā)生，保障在事故發(fā)生時及時響應(yīng)。

從不同周期下的配置結(jié)果（見表4）可以發(fā)現(xiàn)，如果對救助船進行多周期的配置，每個時期所得到的最優(yōu)的救助船配置數(shù)量不同，符合由于不同時期事故的波動性造成的需求不同而導(dǎo)致的配置結(jié)果不同這一規(guī)律。

3.2.3 不同周期下的救助效果分析

從不同周期下的救助效果對比（見表5）可以看出，隨著周期的增加，救助船調(diào)度的次數(shù)及數(shù)量隨著周期內(nèi)的需求變動也在增加，調(diào)度的成本也會增加。雖然調(diào)度產(chǎn)生了成本，但多周期的配置所能達到的救助效果也會提升，各個救助站點對事故區(qū)域點的覆蓋次數(shù)和覆蓋率也有所提升。在對事故的響應(yīng)時間方面：T=0時，對事故的平均響應(yīng)時間為1.25 h;T=2時，平均響應(yīng)時間縮短到了0.83 h，提升33.6%;T=4時，平均響應(yīng)時間為0.71 h，提升43.2%。說明多周期的對救助船配置確實提升了救助船的應(yīng)急救助響應(yīng)時間。從覆蓋次數(shù)及多重覆蓋率來看，T=2比T=0多覆蓋了124起事故，在救助覆蓋率上也增加了8%。在救助船的調(diào)度方面，隨著周期的增加，救助船調(diào)度的次數(shù)必然會增加，同時由于快艇與小船的數(shù)量較少，對事故應(yīng)急響應(yīng)時間較短，被選中的概率就高，小船與快艇的調(diào)度次數(shù)要比大船的調(diào)度次數(shù)多。不同周期劃分情況下T=12的救助效果最好，但產(chǎn)生的調(diào)度成本最高，調(diào)度次數(shù)最多。

4 結(jié) 語

本文針對海上救助船配置問題，建立了考慮事故時變性與救助船可用性的多周期多重覆蓋模型，并運用多目標蟻群算法進行求解。以渤海海域為例進行實例驗證，證實了模型及算法的有效性，得出以下3點結(jié)論：

（1）多周期多重覆蓋模型考慮了救助船的船型、速度、救助能力、可獲得性及事故的時變性等因素，雖然增加了問題的復(fù)雜性以及求解的難度，但更加貼近實際;

（2）多周期配置模型，能夠改善平均應(yīng)急響應(yīng)時間、救助站點覆蓋的事故數(shù)量以及多重覆蓋率;

（3）隨著周期的增加，對救助船的調(diào)度次數(shù)就一定會增加，相應(yīng)的調(diào)度成本也會增加。

此外，由于海上救助情況較為復(fù)雜，本研究尚有不足之處：為了便于計算救助船的移動成本，只考慮了由于距離產(chǎn)生的成本，對救助資源的多周期移動和配置可以同時考慮救助飛行隊。之后的研究也可以考慮多周期對救助船移動產(chǎn)生的成本和多周期配置能夠提升的救助水平的權(quán)衡。