改進遺傳算法下的無水港集貨路徑優化研究

彭 露，陳淮莉

上海海事大學 物流科學與工程研究院，上海 201306

1 引言

隨著21世紀海上絲綢之路的逐步推進，我國沿岸的港口也變得十分繁忙，以至于經常出現擁堵情況，十分影響作業效率，在上海自由貿易區外，繁忙的外集卡也時常出現堵塞。為了解決該問題，近幾年來，無水港也在蓬勃地發展。在中國，無水港是指在內陸，依照有關國際運輸法規、條約和慣例設立的對外開放的通商口岸。具備有報關、報檢、簽發提單等港口服務功能，無水港其實就是港口功能向內陸地區的延伸。大部分的無水港都與海港有合作，為客戶辦理出口退稅和報關手續。

而隨著中國電子商務企業的蒸蒸日上，中國的很多電子商務產物要走出國門，而大批量電商貨物的運輸方式都是先通過汽車或者火車集中到較近的無水港，再通過火車運送到沿岸的海港，從而發往世界各地。因為電商產品的特性，很多時候車輛從發貨地運往無水港的時候都不能滿載，從而降低了車輛的利用率。

國外關于無水港的建設也開啟得較早，現在歐洲約有220個無水港，建于1988年，美國也約有380個主要無水港，亞洲地區也有近100個無水港，其中巴基斯坦和印度發展較早，始于1973年，印度最早始于1981年。這些無水港規模大小不一，如歐洲無水港集裝箱裝卸量從4萬噸到190萬噸不等，面積從30公頃到200公頃不等。這些國家正在利用無水港發展的機遇，促進國家經濟增長。同時，國外的學者也對這一方向進行了探索，Cullinane等[1]提出了無水港實地建設的相關策略和措施；Leachman等[2]對無水港港口集裝箱的運輸提出了一個非線性數學優化模型；Fan等[3]提出多式聯運網絡流模型用以解決無水港港口擁堵的問題；Li等[4]對沿江無水港選址建設提出相關研究；Feng等[5]從無水港與海港的相關性進行研究，提出了無水港的空間配置模型。

我國的無水港也在迅速發展，候馬陸港與青島港簽署了合作協議，北京朝陽口岸與天津港簽署合作協議，金華無水港與寧波港簽署合作協議，鷹潭也和廈門簽署了合作協議。其他相關的大型水港，如大連港、營口港等也都紛紛和內地的無水港簽署相關協議，進行合作，我國學者也在這方面進行了廣泛的探索，吳淑[6]對我國無水港投資運行模式進行了相關研究；任偉[7]以天津港為例，提出了內地無水港建設的規劃方案；邵靜靜[8]以西部內陸無水港建設為依托，提出了重慶無水港選址以及集疏運系統優化方案；賈娜娜等[9]在“一帶一路”背景下考慮無水港的跨境運輸，建立了以降低物流配送成本，最大化時間價值的非線性整數規劃模型；方琴[10]以貴州區域為例，闡明了無水港選址的相關注意事項；吉爾德[11]通過對無水港和擴展通道概念的研究，提出了區域的擴展通道模型，從而對無水港的選址作出評估；趙金樓等[12]對無水港集裝箱碼頭分階段進行路徑優化研究；胡文繽等[13]構建無水港與海港集裝箱配送路徑優化網絡，最優化集裝箱運輸成本。

以上文獻對于無水港的研究絕大部分處于理論探索和選址規劃層面，還沒有從物流運輸整體層面，考慮路徑和成本優化，構建水路和陸路聯運的出口物流配送網絡。本文的創新點在于將無水港和電商出口貨物集疏運結合起來，運用掃描法和改進遺傳算法相結合對集貨路徑進行二階段優化，以達到運輸距離及運輸成本最小化的目的。

并且考慮到電商產品數量少以及海運需拼箱的特性，本文優先對無水港輻射地的貨物進行分塊收集優化，將貨物從起始地串聯運輸直至無水港，以進一步提高無水港的集貨能力，提升作業效率。本文對包括電商貨物在內的內陸和無水港之間的貨物集疏運都有實際參考價值。

2 問題描述與模型構建

2.1 問題描述

傳統的出口電商商品從始發地到無水港采用點對點運輸，車輛數量多，但滿載率低，從而導致成本高?，F在，改進之后的策略是貨主聯合起來進行拼車，空車從無水港出發，依次經過各個載貨點，載上貨物之后，返回無水港卸下。因為每輛車都有相應的容量限制，所以需要多輛車一起配送，共同完成配送任務。電商產品的無水港的集貨問題一直以來也困擾著無水港管理人員和貨主。因為大部分貨主都是將貨物直接從起始地運送至無水港，從而導致貨物滿載率不高，對于無水港而言，大批出口貨物的不定時到達也給無水港的管理帶來了問題。

傳統作業方式如圖1所示，車輛直接從發貨點出發，采用點對點運輸。改進后的作業方式如圖2，車輛從無水港出發，依次經過沿線的發貨點，裝貨完成之后，返回無水港卸貨。

圖2 改進后運輸示意圖

2.2 模型建立

2.2.1 符號說明

參數：

P表示無水港；

i表示發貨點；

N表示所有發貨點的集合，N=(1,2,…,n)；

t表示工作時段，t∈T；

dij表示任意兩發貨點形成的路徑，i,j∈N；

Q表示每輛貨車的最大承載量；

qn表示每個發貨點擁有的貨物質量，n∈N；

Vk表示第k輛車服務的發貨點集合；

K表示所有集貨運輸車輛的集合。

決策變量：

xijk：0-1，若集貨運輸車輛k經過發貨點(i,j)，并且順序從i→j，則為1，否則為0；

yik：0-1，若集貨運輸車輛k經過發貨點i，則為1，否則為0；

zitk：0-1，若在計劃時間t集貨運輸車輛k經過發貨點 i，則為1，否則為0。

2.2.2 運輸模型

假設max(qi)

（1）每輛車都以無水港作為起點和終點；（2）每一個配送點只用一輛車進行服務；（3）每輛車都不允許超過最大載重量。建立運輸模型如式（1）至式（7）所示。式（1）為目標函數，表示所有運輸車輛的總路程最小化：

式（2）為每輛貨車的最大載重約束：

式（3）表示在每一個發貨地同一時間恰好由一輛貨車提供服務：

式（4）表示在同一時間一輛貨車只在一個發貨點進行集貨運輸：

式（5）表示任何一輛集貨運輸車最多進行一個緊前作業：

式（6）表示任何一輛集貨運輸車最多進行一個緊后作業：

式（7）表示任一集貨運輸車通過發貨點i,j的先后順序：

式（8）定義了相關變量之間的關系：

式（9）表示所有車輛起點和終點都在無水港：

式（10）表示每輛車的路徑的軌跡都恰好為一個Hamilton簡單圈：

3 改進遺傳算法

CVRP問題是一個NP-Hard問題，在經過第一步掃描法分組之后，就將該問題轉化為了VRP問題。在這個問題中，伴隨著發貨點的增加，研究問題的復雜程度將呈指數增長?？紤]到傳統遺傳算法在解決這類問題時運算效率較低、響應慢等問題。在此提出了一種基于最近鄰、禁忌搜索和遺傳算法的改進遺傳算法（IGA），在對初始種群創建方式優化后來加快算法的速度；并且通過改變交叉、變異策略等來改善算法的早熟收斂以及局部搜索較差等問題。

3.1 染色體編碼

對于每個配送路徑中的n個目標，以及無水港，將染色體分為n+1段，其中每一段對應一個發貨點的編號。如圖3所示，采用整數排列編碼，分別表示各輛集貨車通過發貨點的先后順序，時段順序值越小表示越先通過。其中0表示無水港，1,2,…,n表示n個發貨點。圖3中染色體表示各集貨車從無水港出發，第1輛集貨車先通過第1個發貨點，然后依次經過第7個發貨點以及第6個發貨點，第2輛車依次經過第3、第2個發貨點，以此類推，最終均返回無水港。

圖3 染色體編碼

3.2 種群初始化

隨機選取一個發貨點作為初始點，通過使用最近鄰算法創建初始種群，找到距離它最近的發貨點作為次結點，并以此次結點作為初始結點，循環往復找到最后一個發貨點，由此創建初始種群。但這樣產生的解可能會違反同一時刻同一集貨車通過發貨點的先后順序等約束。在此對初始解進行修復。

假設集貨車通過發貨點2和3，但2先于3，發貨點5和7的貨物由同一集貨車運輸。如圖4所示，對違反約束的染色體進行修復。

圖4 染色體修復

3.3 適應度函數

在適應度函數中考慮不可行解的懲罰策略。以所有發貨點的貨物質量總和不超過車輛的承受范圍，以及每條路線的長度不超過車輛的最大行駛距離為雙重約束。如果所有發貨點均在路線中，則說明該解決方案可行，不可行路線a=0，否則a=1。以Z為目標函數，不可行路徑的懲罰權重為M（無限大的正數），解決方案E可以用式（11）表示：

式（12）表示適應度函數。在對染色體個體解碼后得到不可行路線的數量a和目標函數值Z。將二者代入方程可得染色體個體的適應度 f。

3.4 種群選擇策略

3.4.1 選擇

選擇操作也就是從舊的群體中以一定的概率選擇個體到新的個體中去，在本文中使用Select函數完成，個體被選中的概率和適應度的值有關，個體適應度越大，被選中的概率越大[14]。

3.4.2 交叉

改進遺傳算法采取雙切點交叉法。在父代染色體中隨機選擇兩個切點，對其中的片段進行交換，對未交換的染色體片段以部分映射的方式消除沖突，以發貨點染色體為例，交叉示范如圖5。

圖5 染色體交叉

3.4.3 變異

圖6 染色體變異

染色體變異能夠輔助產生新個體，有助于提高局部搜素能力，同時保持種群的多樣性。改進遺傳算法采用逆轉變異法[15]，在染色體集貨車部分隨機選取2個變異點，將父代染色體中的基因互換，生成下一代染色體。如圖6所示。需要進行基因修復。首先，在交叉時，若交換的染色體片段是“0”基因位，則需要重新生成切點，在變異時，如出現交換兩基因位相同，重新生成交換位置。其次，需要判段染色體片段是否滿足假設條件（3），若不滿足，將集貨車承載范圍外的發貨點擁有的貨物分配給其他集貨車輛。

3.6 改進遺傳算法流程

考慮最近鄰算法生成的路徑的基因總體表現較為優良，可遺傳算法則是具有較高的并行性。由此，本文通過結合最近鄰和禁忌搜索思想的遺傳算法來解決無水港運輸路徑優化問題。改進遺傳算法的流程如下顯示，算法流程如圖7所示。

圖7 改進遺傳算法流程圖

步驟1將種群規模設定為N，交叉概率為c，變異概率為v，選擇概率是s，和隨機概率r，并設定算法終止條件r=Iteration，置進化代數r=0，禁忌表t。

步驟2隨機選擇一個發貨點，由最近鄰算法所生成路徑的集合設為P，與此同時計算個體的適應度值，并從集合P中隨機選擇N個初始化第一代種群S(r)。

步驟3及時更新禁忌表t，并將已經搜索過的路徑儲存在其中。

步驟4在種群S(r)中比較適應度函數，從中尋優選擇部分個體作為父代F。

步驟5交叉操作后產生新的路徑S1，此路徑不與禁忌表中的以往路徑重復。

步驟6變異操作后產生新的路徑S2，且不與禁忌表中的歷史路徑重合。

步驟7更新父代和子代的并集Srecent(r)。

步驟8引入新的個體，然后隨機生成新的路徑S*(r)，與禁忌表中的以往路徑不相重復。

步驟9 r←r+1，在Srecent(r)?S*(r)中尋優選擇N個個體作為新的種群S(r)。

步驟10如果滿足所有條件，則停止運行并且輸出最優值 f，否則返回步驟3。

3.5 基因修復

4 案例研究

4.1 實驗設置

經過交叉、變異操作后，對于不滿足約束的染色體，

與上海港合作的昆山無水港要進行貨物收集，昆山港附近有20個發貨點，發貨點的坐標儲存于一個元胞矩陣XY中，每個發貨點的發貨量儲存于元胞矩陣A中，將每輛車的最大載重設定為1 400 kg。

相應的發貨點位置，發貨量如表1所示。

表1 發貨點坐標及發貨量

4.2 掃描法分組

如圖8所示，首先構造極坐標系，逆時針旋轉極軸，以車輛承載量1 400 kg為約束條件，進行分組處理。如圖9所示，通過掃描法，將20個發出點分成了三個區域，每個區域內的發出總量不超過1 400 kg，需要使用3輛貨車進行裝載。

圖8 建立極坐標系

4.3 算法參數及實驗結果

4.3.1 小規模實驗

在此案例分析中，使用MATLAB對該路徑優化進行模擬仿真。進行實驗的計算機配置為Win10 64位操作系統，安裝內存（4.00 GB），CPU頻率1.80 GHz，所得出的有關運行時間等的數據，都與該機器有關。

圖9 貨物分區示意圖

實驗具體參數設置如下，種群規模數量為120，算法終止條件Iteration=400，交叉概率為0.9，變異概率為0.02，同時車輛超載的懲罰權重為300。

對發貨點優先級以及車輛運輸約束如表2所示。

表2 優先級與運輸約束

在滿足各種約束的情況下得到無水港集貨運輸路徑優化過程中距離的大小與迭代次數變化的仿真數據如表3。路徑優化收斂圖如圖10，當迭代次數在149次之后，路徑優化值沒有發生改變，在迭代次數達到400時，算法終止。

表3 模擬仿真數據

圖10 運輸路徑優化收斂圖

從表3中可以看出，當迭代次數為149時，最短路徑顯示為552.37 km，并且，隨著迭代次數的延伸，最短路徑并未發生改變。最優路徑如圖11所示。

同時，為了驗證改進遺傳算法（IGA）的有效性和優越性，將其與傳統遺傳算法（GA）以及粒子群算法（PSO）進行比較，采用相同的實驗數據，并將三種算法參數設置基本一致，對比結果如表4所示。

表4 路徑優化結果對比

圖11 配送路徑示意圖

從表4可以看出，在同等條件下，本文所采用的改進遺傳算法在較少的迭代次數下迅速得到比遺傳算法以及粒子群算法明顯更優的解，充分說明本文算法的有效性。

對一區而言，使用改進遺傳算法進行路徑優化得到的最優路徑全長為199.61 km；二區的最優路徑全長為168.79 km；三區的最優路徑全長為183.97 km。三輛汽車總的行駛距離為552.37 km。

由圖11可看出：

第一輛貨車：

昆山無水港→發貨點14→發貨點13→發貨點17→發貨點15→發貨點3→發貨點2→發貨點18→昆山無水港

第二輛貨車：

昆山無水港→發貨點5→發貨點19→發貨點10→發貨點4→發貨點1→發貨點9→昆山無水港

第三輛貨車：

昆山無水港→發貨點20→發貨點7→發貨點8→發貨點11→發貨點12→發貨點16→發貨點6→昆山無水港

4.3.2 大規模實驗

圍繞1個無水港進行貨物收集，本次實驗設置發貨點數量為50個，各點貨物總質量為9 650 kg，采取小規模實驗中相同的集貨方式，可以得到在發貨點增多時車輛配送軌跡，如表5所示。

表5 大規模實驗車輛配送表

4.3.3 多規模實驗下的算法對比

在集貨運輸發貨點數量N以及運輸車輛數m規模不同時，比較改進遺傳算法（IGA）、傳統遺傳算法（GA）以及粒子群算法（PSO）在運行結果以及運行時間上的優劣性，如表6所示。

對比表6結果可知，在小規模情景中，改進遺傳算法下的最優解略好于遺傳算法以及粒子群算法，但得到解的速率遠大于二者。在實驗規模的不斷擴大下，從運行時間以及計算結果雙重對比下，改進遺傳算法的優越性都得到充分體現。綜上所述，改進遺傳算法能更好地解決本文所提出的問題模型。

5 結果對比

以文中使用的小規模實驗數據作為依據，用兩種傳統運輸方式與本文改進集貨方式運輸之后的結果進行對比分析，比較三種方式在運送成本方面的優劣性。

5.1 貨主自有卡車運輸

假定每輛車固定成本為1 000元/天，每輛車的變動成本為1.5元/（天·km）。傳統無水港集貨方式采取點到點集貨，就本文而言，集貨方式如圖12所示。使用MATLAB編程可以求得所有貨車行駛的總路程為1 659.74 km，需要使用20輛貨車。

表6 多規模實驗結果算法對比

圖12 傳統集貨方式

成本計算方法為式（13）：

使用傳統方式集貨的貨車數量m=20，總行駛距離L=1 659.74 km，所得總成本C總=69 792.2元 。

5.2 托運方式運輸

因為發貨點都會就近選擇無水港，所以距無水港的距離都不會太遠，所以托運單價穩定。根據市場調研發現托運單價均價為3元/kg。托運總價格計算方法由式（14）給出：

由各發貨點貨物總質量以及上式可得托運總成本為12 120元。

5.3 改進后運輸方式

針對本文所提出的問題，經過研究后得出需要三輛貨車即可滿足20個發貨點所有貨物的運輸，并且通過改進的遺傳算法得出最優行駛路徑為552.37 km，根據式（13），可以得出C總=5 485.67元 。將三種運輸方式進行對比，如表7。

表7 三種運輸結果對比

6 結語

針對無水港的集貨效率低、成本高等問題，提出了一種切實可行的解決辦法，即通過共享車輛的形式，既降低了發貨商的成本，也使得無水港的管理更加便捷。

通過使用掃描法，在不超過車輛最大載重限額的約束下，將發貨點進行分組安排。其次使用改進的遺傳算法進行組內路徑優化，并用遺傳算法以及粒子群算法對不同規模的集貨運輸進行分析與之對比，得到最優的調度策略，突出改進遺傳算法的有效性和優越性。通過Matlab進行數學模擬實驗，最終得到改進后車輛需求總數為3輛，配送總成本為5 485.67元，將結果與兩種傳統方式比較，得出了比自有車輛運輸節省92.14%成本，比辦理托運節省了54.74%成本的結論，從而證明了本文中所述的方法是更優的。

同時，在本文的研究中未考慮客戶對貨物配送時間以及滿意度的限制，在之后的研究中可以增加約束。另外，針對近幾年興起的城際拼車運輸模式，對其最優路徑的研究也不失為一條好的思路。