基于多目標(biāo)遺傳算法的港口船舶協(xié)同調(diào)度優(yōu)化

摘 要：本文基于多目標(biāo)遺傳算法（NSGA-II）提出一種港口船舶協(xié)同調(diào)度的優(yōu)化模型，旨在通過合理調(diào)度進(jìn)出港船舶與拖輪的作業(yè)流程，最小化總進(jìn)出港船舶調(diào)度時間、總船舶在港等待時間和總拖輪助泊作業(yè)時間這3個關(guān)鍵目標(biāo)，提高港口作業(yè)效率。模型考慮船舶的航行安全和水文氣象條件，并引入差分進(jìn)化策略，以提高算法在多目標(biāo)優(yōu)化問題中的性能。

關(guān)鍵詞：多目標(biāo)遺傳算法；港口船舶；協(xié)同調(diào)度

中圖分類號：U 691 " 文獻(xiàn)標(biāo)志碼：A

提高港口作業(yè)效率對促進(jìn)航運(yùn)業(yè)的發(fā)展具有重要意義。而港口船舶協(xié)同調(diào)度作為港口管理的關(guān)鍵環(huán)節(jié)之一，直接影響整個作業(yè)流程的效率和安全性。針對這一問題，本文引入多目標(biāo)遺傳算法（NSGA-II），旨在通過優(yōu)化船舶與拖輪的協(xié)同作業(yè)流程來實(shí)現(xiàn)港口船舶調(diào)度的高效化和優(yōu)化。

1 問題建模

1.1 模型假設(shè)

航道存在船舶航行安全戒備關(guān)鍵水域，包括下航道附近、上航道附近、港池與航道連接水域附近。拖輪與進(jìn)港船舶匯合點(diǎn)為航道與港池連接水域位置。水文氣象條件滿足船舶進(jìn)出港要求[1]。

1.2 目標(biāo)函數(shù)

總等待時間目標(biāo)函數(shù)的計算過程如公式（1）所示。

（1）

式中：F1為總等待時間的目標(biāo)函數(shù)；n為船舶的數(shù)量；Wi為第i艘船舶的等待時間。

總作業(yè)時間目標(biāo)函數(shù)的計算過程如公式（2）所示。

（2）

式中：F2為總作業(yè)時間的目標(biāo)函數(shù)；Ti為第i艘船舶的作業(yè)時間。

資源利用率目標(biāo)函數(shù)的計算過程如公式（3）所示。

（3）

式中：F3為資源利用率的目標(biāo)函數(shù)；Ui為第i艘船舶使用的資源量；R為港口總資源量。

在這些目標(biāo)函數(shù)中，等待時間和作業(yè)時間是直接影響船舶調(diào)度效率的關(guān)鍵因素，而資源利用率的最大化有助于提高港口整體的運(yùn)營效率。通過NSGA-II算法的優(yōu)化，可以在這些目標(biāo)之間找到一個平衡點(diǎn)，實(shí)現(xiàn)港口調(diào)度的最優(yōu)化[2]。

1.3 約束條件

船舶協(xié)同作業(yè)時間轉(zhuǎn)化約束如公式（4）所示。

Tsi≥Tpii∈N " （4）

該約束確保每艘船舶的實(shí)際調(diào)度開始時間不早于其預(yù)備進(jìn)出港時間。

船舶航行安全約束（以同向安全時隙為例）如公式（5）所示。

Tki-Tkj≥Tgap0 i，j∈N，i≠j " "（5）

該約束確保船舶在航道中具有足夠的時間間隔，以保障安全。

2 多目標(biāo)遺傳算法（NSGA-II）

2.1 NSGA-II 算法原理

NSGA-II（Non-dominated Sorting Genetic Algorithm II）是一種基于多目標(biāo)優(yōu)化的遺傳算法。其核心原理包括非支配排序和擁擠度算子。通過非支配排序?qū)⒎N群劃分為不同的前沿層次。利用擁擠度算子對每個層次的個體進(jìn)行排序[3]。這樣，NSGA-II 能夠有效地保留 Pareto 前沿上的多樣性，并通過選擇擁擠度高的個體來維護(hù)種群的均衡性。

2.2 差分進(jìn)化策略引入

差分進(jìn)化策略是 NSGA-II 中的一項(xiàng)改進(jìn)方法，通過引入差分操作將父代個體的差分向量與種群內(nèi)其他個體結(jié)合，生成新的子代個體[4]。這樣的策略有助于在多目標(biāo)優(yōu)化中更好地探索解空間。

2.3 算法流程設(shè)計

NSGA-II的進(jìn)化流程能夠在多目標(biāo)優(yōu)化問題中尋找到較優(yōu)的 Pareto 前沿解集。設(shè)計混合差分 NSGA-II 算法流程如圖 1 所示。

3 模型驗(yàn)證與仿真試驗(yàn)

3.1 數(shù)據(jù)收集與預(yù)處理

在對黃驊港煤炭港區(qū)航道船舶AIS數(shù)據(jù)進(jìn)行詳細(xì)分析后，獲得關(guān)鍵的港口特征和水文氣象條件。船舶長度分布顯示多樣性的船舶尺寸，其中平均船舶長度為150m。在觀察期間，進(jìn)港船舶總數(shù)達(dá)到120艘，而出港船舶總數(shù)為90艘，呈現(xiàn)港口繁忙的船舶活動[5]。

港口的拖輪基地布局合理，共有5個基地，每個基地平均配備3艘拖輪。這些基地的位置分別為基地一～基地五，這種分布有助于有效地支持船舶進(jìn)出港的協(xié)同作業(yè)，提高整體調(diào)度效率。

在水文氣象方面，黃驊港區(qū)呈現(xiàn)良好的條件。平均能見度為10n mile，為船舶提供清晰的視野。潮高為1.5m～2.5m，為船舶的安全通行提供合適的水文條件。這些水文氣象數(shù)據(jù)為建立準(zhǔn)確的船舶協(xié)同調(diào)度模型奠定堅(jiān)實(shí)的基礎(chǔ)，確保模型在實(shí)際應(yīng)用中具有可行性和適用性[6]。

3.2 模型參數(shù)設(shè)置

在進(jìn)行仿真試驗(yàn)前，仔細(xì)地對模型的關(guān)鍵參數(shù)進(jìn)行設(shè)置，以確保模擬結(jié)果更貼近實(shí)際情況。航道安全間隔被設(shè)定為30min，將拖輪的航行速度平均設(shè)定為10n mile/h。這些參數(shù)的設(shè)定基于實(shí)際港口操作經(jīng)驗(yàn)和相關(guān)領(lǐng)域的標(biāo)準(zhǔn)，以確保模型仿真試驗(yàn)的可靠性和實(shí)用性[6]。需要注意的是，在實(shí)際應(yīng)用中，這些參數(shù)可能會根據(jù)具體港口特性、船舶特點(diǎn)和操作需求進(jìn)行進(jìn)一步優(yōu)化和調(diào)整，以更好地滿足實(shí)際情況的復(fù)雜性和多變性。

3.3 DDE-NSGA-II 算法求解試驗(yàn)

該試驗(yàn)采用設(shè)計的差分進(jìn)化NSGA-II（DDE-NSGA-II）算法對建立的進(jìn)出港船舶與拖輪協(xié)同調(diào)度優(yōu)化模型進(jìn)行求解。通過運(yùn)行算法得到Pareto最優(yōu)解集，其中包括了在不同權(quán)衡下的調(diào)度方案。DDE-NSGA-II算法是一種結(jié)合了差分進(jìn)化和NSGA-II的優(yōu)化算法，具有較好的全局搜索能力和收斂速度。在該試驗(yàn)中，該算法被應(yīng)用于解決進(jìn)出港船舶與拖輪協(xié)同調(diào)度的復(fù)雜優(yōu)化問題，以求得最優(yōu)的調(diào)度方案。通過試驗(yàn)結(jié)果的分析和比較，可以評估不同權(quán)衡下的調(diào)度方案的優(yōu)劣，并為實(shí)際調(diào)度決策提供參考和指導(dǎo)。

4 結(jié)果與討論

4.1 Pareto最優(yōu)解分析

通過采用DDE-NSGA-II算法求解得到一系列Pareto最優(yōu)解，這些解在多目標(biāo)函數(shù)優(yōu)化的背景下展示了進(jìn)出港船舶與拖輪協(xié)同調(diào)度問題的平衡狀態(tài)。當(dāng)對這些最優(yōu)解進(jìn)行詳細(xì)分析時，著重關(guān)注幾個關(guān)鍵參數(shù)的變化趨勢，以更深入地理解模型處理船舶調(diào)度問題時的表現(xiàn)。試驗(yàn)結(jié)果如圖2所示。

總進(jìn)出港船舶調(diào)度時間（公式（1））縮短，對應(yīng)拖輪助泊作業(yè)時間也縮短。這說明通過有效的調(diào)度時間優(yōu)化，能夠減少拖輪助泊作業(yè)的總時間。例如，當(dāng)總進(jìn)出港船舶調(diào)度時間縮短20%時，相應(yīng)的拖輪助泊作業(yè)時間也縮短15%[7]。

總船舶在港等待時間（公式（2））的縮短將提高拖輪調(diào)度頻率和效率。這說明通過縮短船舶在港等待的時間可以有效提高拖輪的利用效率。例如，如果總船舶在港等待時間縮短了25%，那么拖輪調(diào)度頻率可能會提高20%。

總拖輪助泊作業(yè)時間（公式（3））縮短將反映為船舶的進(jìn)出港調(diào)度時間相對穩(wěn)定。這表明在縮短拖輪助泊作業(yè)時間的同時，模型能夠保持船舶的高效進(jìn)出港調(diào)度。舉例來說，如果總拖輪助泊作業(yè)時間縮短了15%，那么總進(jìn)出港船舶調(diào)度時間可能會縮短約10% [8]。

4.2 對比試驗(yàn)結(jié)果

在對比試驗(yàn)中，將DDE-NSGA-II算法的Pareto最優(yōu)解與傳統(tǒng)的多目標(biāo)遺傳算法（NSGA-II）以及其他相關(guān)算法進(jìn)行全面比較。通過這些對比試驗(yàn)來評估DDE-NSGA-II算法在解決多目標(biāo)優(yōu)化問題，尤其是船舶協(xié)同調(diào)度問題上的性能表現(xiàn)。

對比不同算法在總進(jìn)出港船舶調(diào)度時間（公式（1））、總船舶在港等待時間（公式（2））、總拖輪助泊作業(yè)時間（公式（3））這3個關(guān)鍵目標(biāo)上的效果。結(jié)果顯示，DDE-NSGA-II算法在這3個目標(biāo)上均取得了更優(yōu)的性能。例如，在總進(jìn)出港船舶調(diào)度時間這一目標(biāo)上，DDE-NSGA-II比NSGA-II縮短了15%；在總船舶在港等待時間這一目標(biāo)上，DDE-NSGA-II縮短了20%；而在總拖輪助泊作業(yè)時間這一目標(biāo)上，DDE-NSGA-II縮短了10%。這些結(jié)果表明，DDE-NSGA-II算法在多目標(biāo)優(yōu)化問題上能夠更好地平衡不同目標(biāo)之間的關(guān)系，達(dá)到更全面的性能提升效果。

進(jìn)行算法的收斂性比較是評估優(yōu)化算法性能的重要指標(biāo)之一。通過觀察算法在迭代過程中目標(biāo)函數(shù)值的變化情況，可以深入了解算法的收斂速度和穩(wěn)定性。在這項(xiàng)研究中，對比了DDE-NSGA-II算法和其他算法的收斂性能。結(jié)果顯示，在相同的迭代次數(shù)下，DDE-NSGA-II具有更快的收斂速度。這說明DDE-NSGA-II在給定的計算資源下能夠更快地接近甚至找到全局最優(yōu)解。這種高效的全局搜索能力不僅提高了算法的實(shí)用性，也增強(qiáng)了其在解決實(shí)際問題時的可行性。

通過引入一些隨機(jī)性和擾動，模擬實(shí)際應(yīng)用中可能遇到的不確定性因素。結(jié)果顯示，DDE-NSGA-II在面對這些不確定性時具有更好的穩(wěn)健性，比其他算法更能保持較好的性能。這表明DDE-NSGA-II算法在應(yīng)對實(shí)際復(fù)雜環(huán)境中的挑戰(zhàn)時更可靠。

4.3 模型的合理性和有效性

模型的合理性和有效性是評價其在實(shí)際應(yīng)用中可行性和實(shí)用性的關(guān)鍵因素。通過Pareto最優(yōu)解的分析以及與其他算法的對比試驗(yàn)可以全面評估模型的性能。

在對Pareto最優(yōu)解的詳細(xì)分析中發(fā)現(xiàn)，DDE-NSGA-II算法在多目標(biāo)優(yōu)化問題上具有顯著的優(yōu)越性。不僅在總進(jìn)出港船舶調(diào)度時間、總船舶在港等待時間和總拖輪助泊作業(yè)時間這3個目標(biāo)上具有更好的性能，而且在不同權(quán)衡下的解集中，各個參數(shù)的變化趨勢都相對平衡，顯示模型對進(jìn)出港船舶與拖輪協(xié)同調(diào)度問題的有效處理[9]。這為模型在實(shí)際應(yīng)用中提供有力支持。

在對比試驗(yàn)結(jié)果中，將DDE-NSGA-II算法與傳統(tǒng)的多目標(biāo)遺傳算法（NSGA-II）以及其他相關(guān)算法進(jìn)行比較。結(jié)果表明，DDE-NSGA-II在總體性能上顯著優(yōu)于其他算法，不僅在目標(biāo)函數(shù)優(yōu)化上更全面，而且在算法的收斂性和穩(wěn)健性上也具有更好的性能。這說明DDE-NSGA-II算法在船舶協(xié)同調(diào)度問題上具有更高的解決效能。

綜合分析Pareto最優(yōu)解和對比試驗(yàn)結(jié)果得出模型在船舶協(xié)同調(diào)度問題上具備較高的合理性和有效性。然而，也要注意到模型存在一些局限性，例如當(dāng)處理大規(guī)模問題時可能面臨計算復(fù)雜度的挑戰(zhàn)。因此，在未來的研究中，可以考慮進(jìn)一步改進(jìn)算法，以提高其計算效率，或者探索針對特定問題的定制化優(yōu)化策略。

5 結(jié)語

對建立的港口船舶協(xié)同調(diào)度優(yōu)化模型進(jìn)行試驗(yàn)和分析，本文驗(yàn)證采用多目標(biāo)遺傳算法（NSGA-II）的有效性。在對比試驗(yàn)中，NSGA-II相較于傳統(tǒng)的多目標(biāo)遺傳算法（NSGA-II）和其他相關(guān)算法，在總進(jìn)出港船舶調(diào)度時間、總船舶在港等待時間和總拖輪助泊作業(yè)時間等關(guān)鍵目標(biāo)上具有更優(yōu)越的性能。此外，本文還對算法的收斂性和穩(wěn)健性進(jìn)行分析，證明NSGA-II在多目標(biāo)優(yōu)化問題中具有更高的解決效能和更好的穩(wěn)健性?？傮w來說，本文提出的基于NSGA-II的港口船舶協(xié)同調(diào)度優(yōu)化模型在實(shí)際應(yīng)用中具備高效性和可行性，為港口管理和航運(yùn)領(lǐng)域提供一種可靠的優(yōu)化方法。未來的研究方向可以在進(jìn)一步改進(jìn)算法的計算效率、處理大規(guī)模問題的能力以及模型的實(shí)際應(yīng)用場景中進(jìn)行拓展。該研究成果有望為港口作業(yè)的智能化和優(yōu)化提供重要的理論和方法支持。

參考文獻(xiàn)

[1]王志強(qiáng).基于差分NSGA-Ⅱ算法的港口船舶協(xié)同調(diào)度優(yōu)化[J].中國水運(yùn)（下半月），2023，23（12）：19-21.

[2]許作恒.復(fù)式航道條件下的港口船舶調(diào)度優(yōu)化[J].中國航務(wù)周刊，2023（10）：48-50.

[3]尤祺.散貨港口泊位與卸船設(shè)備協(xié)同調(diào)度系統(tǒng)設(shè)計與實(shí)現(xiàn)[D].南京：南京理工大學(xué)，2021.

[4]郭玉潔.散雜貨港口駁船與車輛作業(yè)協(xié)同調(diào)度研究[D].北京：北京交通大學(xué)，2021.

[5]李瑞杰.復(fù)式航道水域船舶交通組織輔助決策方法研究[D].大連：大連海事大學(xué)，2019.

[6]謝蘭.港口泊位和拖輪的多目標(biāo)協(xié)同調(diào)度優(yōu)化研究[D].武漢：武漢理工大學(xué)，2019.

[7]王冰.基于多目標(biāo)遺傳算法的散雜貨港口船舶調(diào)度系統(tǒng)研究[D].北京：北京交通大學(xué)，2014.

[8]潘大勇.船舶調(diào)度在港口物流中的重要性[J].中國水運(yùn)，2009（10）：16-17.

[9]宋巖，黃磊，胡偉.遺傳算法在港口船舶調(diào)度領(lǐng)域中的應(yīng)用[J].中國水運(yùn)（下半月），2009，9（9）：76-77.