改進(jìn)遺傳算法下的無(wú)水港集貨路徑優(yōu)化研究

彭 露，陳淮莉

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

1 引言

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

而隨著中國(guó)電子商務(wù)企業(yè)的蒸蒸日上，中國(guó)的很多電子商務(wù)產(chǎn)物要走出國(guó)門，而大批量電商貨物的運(yùn)輸方式都是先通過(guò)汽車或者火車集中到較近的無(wú)水港，再通過(guò)火車運(yùn)送到沿岸的海港，從而發(fā)往世界各地。因?yàn)殡娚坍a(chǎn)品的特性，很多時(shí)候車輛從發(fā)貨地運(yùn)往無(wú)水港的時(shí)候都不能滿載，從而降低了車輛的利用率。

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

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

以上文獻(xiàn)對(duì)于無(wú)水港的研究絕大部分處于理論探索和選址規(guī)劃層面，還沒(méi)有從物流運(yùn)輸整體層面，考慮路徑和成本優(yōu)化，構(gòu)建水路和陸路聯(lián)運(yùn)的出口物流配送網(wǎng)絡(luò)。本文的創(chuàng)新點(diǎn)在于將無(wú)水港和電商出口貨物集疏運(yùn)結(jié)合起來(lái)，運(yùn)用掃描法和改進(jìn)遺傳算法相結(jié)合對(duì)集貨路徑進(jìn)行二階段優(yōu)化，以達(dá)到運(yùn)輸距離及運(yùn)輸成本最小化的目的。

并且考慮到電商產(chǎn)品數(shù)量少以及海運(yùn)需拼箱的特性，本文優(yōu)先對(duì)無(wú)水港輻射地的貨物進(jìn)行分塊收集優(yōu)化，將貨物從起始地串聯(lián)運(yùn)輸直至無(wú)水港，以進(jìn)一步提高無(wú)水港的集貨能力，提升作業(yè)效率。本文對(duì)包括電商貨物在內(nèi)的內(nèi)陸和無(wú)水港之間的貨物集疏運(yùn)都有實(shí)際參考價(jià)值。

2 問(wèn)題描述與模型構(gòu)建

2.1 問(wèn)題描述

傳統(tǒng)的出口電商商品從始發(fā)地到無(wú)水港采用點(diǎn)對(duì)點(diǎn)運(yùn)輸，車輛數(shù)量多，但滿載率低，從而導(dǎo)致成本高?，F(xiàn)在，改進(jìn)之后的策略是貨主聯(lián)合起來(lái)進(jìn)行拼車，空車從無(wú)水港出發(fā)，依次經(jīng)過(guò)各個(gè)載貨點(diǎn)，載上貨物之后，返回?zé)o水港卸下。因?yàn)槊枯v車都有相應(yīng)的容量限制，所以需要多輛車一起配送，共同完成配送任務(wù)。電商產(chǎn)品的無(wú)水港的集貨問(wèn)題一直以來(lái)也困擾著無(wú)水港管理人員和貨主。因?yàn)榇蟛糠重浿鞫际菍⒇浳镏苯訌钠鹗嫉剡\(yùn)送至無(wú)水港，從而導(dǎo)致貨物滿載率不高，對(duì)于無(wú)水港而言，大批出口貨物的不定時(shí)到達(dá)也給無(wú)水港的管理帶來(lái)了問(wèn)題。

傳統(tǒng)作業(yè)方式如圖1所示，車輛直接從發(fā)貨點(diǎn)出發(fā)，采用點(diǎn)對(duì)點(diǎn)運(yùn)輸。改進(jìn)后的作業(yè)方式如圖2，車輛從無(wú)水港出發(fā)，依次經(jīng)過(guò)沿線的發(fā)貨點(diǎn)，裝貨完成之后，返回?zé)o水港卸貨。

圖2 改進(jìn)后運(yùn)輸示意圖

2.2 模型建立

2.2.1 符號(hào)說(shuō)明

參數(shù)：

P表示無(wú)水港；

i表示發(fā)貨點(diǎn)；

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

t表示工作時(shí)段，t∈T；

dij表示任意兩發(fā)貨點(diǎn)形成的路徑，i,j∈N；

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

qn表示每個(gè)發(fā)貨點(diǎn)擁有的貨物質(zhì)量，n∈N；

Vk表示第k輛車服務(wù)的發(fā)貨點(diǎn)集合；

K表示所有集貨運(yùn)輸車輛的集合。

決策變量：

xijk：0-1，若集貨運(yùn)輸車輛k經(jīng)過(guò)發(fā)貨點(diǎn)(i,j)，并且順序從i→j，則為1，否則為0；

yik：0-1，若集貨運(yùn)輸車輛k經(jīng)過(guò)發(fā)貨點(diǎn)i，則為1，否則為0；

zitk：0-1，若在計(jì)劃時(shí)間t集貨運(yùn)輸車輛k經(jīng)過(guò)發(fā)貨點(diǎn) i，則為1，否則為0。

2.2.2 運(yùn)輸模型

假設(shè)max(qi)

（1）每輛車都以無(wú)水港作為起點(diǎn)和終點(diǎn)；（2）每一個(gè)配送點(diǎn)只用一輛車進(jìn)行服務(wù)；（3）每輛車都不允許超過(guò)最大載重量。建立運(yùn)輸模型如式（1）至式（7）所示。式（1）為目標(biāo)函數(shù)，表示所有運(yùn)輸車輛的總路程最小化：

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

式（3）表示在每一個(gè)發(fā)貨地同一時(shí)間恰好由一輛貨車提供服務(wù)：

式（4）表示在同一時(shí)間一輛貨車只在一個(gè)發(fā)貨點(diǎn)進(jìn)行集貨運(yùn)輸：

式（5）表示任何一輛集貨運(yùn)輸車最多進(jìn)行一個(gè)緊前作業(yè)：

式（6）表示任何一輛集貨運(yùn)輸車最多進(jìn)行一個(gè)緊后作業(yè)：

式（7）表示任一集貨運(yùn)輸車通過(guò)發(fā)貨點(diǎn)i,j的先后順序：

式（8）定義了相關(guān)變量之間的關(guān)系：

式（9）表示所有車輛起點(diǎn)和終點(diǎn)都在無(wú)水港：

式（10）表示每輛車的路徑的軌跡都恰好為一個(gè)Hamilton簡(jiǎn)單圈：

3 改進(jìn)遺傳算法

CVRP問(wèn)題是一個(gè)NP-Hard問(wèn)題，在經(jīng)過(guò)第一步掃描法分組之后，就將該問(wèn)題轉(zhuǎn)化為了VRP問(wèn)題。在這個(gè)問(wèn)題中，伴隨著發(fā)貨點(diǎn)的增加，研究問(wèn)題的復(fù)雜程度將呈指數(shù)增長(zhǎng)?？紤]到傳統(tǒng)遺傳算法在解決這類問(wèn)題時(shí)運(yùn)算效率較低、響應(yīng)慢等問(wèn)題。在此提出了一種基于最近鄰、禁忌搜索和遺傳算法的改進(jìn)遺傳算法（IGA），在對(duì)初始種群創(chuàng)建方式優(yōu)化后來(lái)加快算法的速度；并且通過(guò)改變交叉、變異策略等來(lái)改善算法的早熟收斂以及局部搜索較差等問(wèn)題。

3.1 染色體編碼

對(duì)于每個(gè)配送路徑中的n個(gè)目標(biāo)，以及無(wú)水港，將染色體分為n+1段，其中每一段對(duì)應(yīng)一個(gè)發(fā)貨點(diǎn)的編號(hào)。如圖3所示，采用整數(shù)排列編碼，分別表示各輛集貨車通過(guò)發(fā)貨點(diǎn)的先后順序，時(shí)段順序值越小表示越先通過(guò)。其中0表示無(wú)水港，1,2,…,n表示n個(gè)發(fā)貨點(diǎn)。圖3中染色體表示各集貨車從無(wú)水港出發(fā)，第1輛集貨車先通過(guò)第1個(gè)發(fā)貨點(diǎn)，然后依次經(jīng)過(guò)第7個(gè)發(fā)貨點(diǎn)以及第6個(gè)發(fā)貨點(diǎn)，第2輛車依次經(jīng)過(guò)第3、第2個(gè)發(fā)貨點(diǎn)，以此類推，最終均返回?zé)o水港。

圖3 染色體編碼

3.2 種群初始化

隨機(jī)選取一個(gè)發(fā)貨點(diǎn)作為初始點(diǎn)，通過(guò)使用最近鄰算法創(chuàng)建初始種群，找到距離它最近的發(fā)貨點(diǎn)作為次結(jié)點(diǎn)，并以此次結(jié)點(diǎn)作為初始結(jié)點(diǎn)，循環(huán)往復(fù)找到最后一個(gè)發(fā)貨點(diǎn)，由此創(chuàng)建初始種群。但這樣產(chǎn)生的解可能會(huì)違反同一時(shí)刻同一集貨車通過(guò)發(fā)貨點(diǎn)的先后順序等約束。在此對(duì)初始解進(jìn)行修復(fù)。

假設(shè)集貨車通過(guò)發(fā)貨點(diǎn)2和3，但2先于3，發(fā)貨點(diǎn)5和7的貨物由同一集貨車運(yùn)輸。如圖4所示，對(duì)違反約束的染色體進(jìn)行修復(fù)。

圖4 染色體修復(fù)

3.3 適應(yīng)度函數(shù)

在適應(yīng)度函數(shù)中考慮不可行解的懲罰策略。以所有發(fā)貨點(diǎn)的貨物質(zhì)量總和不超過(guò)車輛的承受范圍，以及每條路線的長(zhǎng)度不超過(guò)車輛的最大行駛距離為雙重約束。如果所有發(fā)貨點(diǎn)均在路線中，則說(shuō)明該解決方案可行，不可行路線a=0，否則a=1。以Z為目標(biāo)函數(shù)，不可行路徑的懲罰權(quán)重為M（無(wú)限大的正數(shù)），解決方案E可以用式（11）表示：

式（12）表示適應(yīng)度函數(shù)。在對(duì)染色體個(gè)體解碼后得到不可行路線的數(shù)量a和目標(biāo)函數(shù)值Z。將二者代入方程可得染色體個(gè)體的適應(yīng)度 f。

3.4 種群選擇策略

3.4.1 選擇

選擇操作也就是從舊的群體中以一定的概率選擇個(gè)體到新的個(gè)體中去，在本文中使用Select函數(shù)完成，個(gè)體被選中的概率和適應(yīng)度的值有關(guān)，個(gè)體適應(yīng)度越大，被選中的概率越大[14]。

3.4.2 交叉

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

圖5 染色體交叉

3.4.3 變異

圖6 染色體變異

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

3.6 改進(jìn)遺傳算法流程

考慮最近鄰算法生成的路徑的基因總體表現(xiàn)較為優(yōu)良，可遺傳算法則是具有較高的并行性。由此，本文通過(guò)結(jié)合最近鄰和禁忌搜索思想的遺傳算法來(lái)解決無(wú)水港運(yùn)輸路徑優(yōu)化問(wèn)題。改進(jìn)遺傳算法的流程如下顯示，算法流程如圖7所示。

圖7 改進(jìn)遺傳算法流程圖

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

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

步驟3及時(shí)更新禁忌表t，并將已經(jīng)搜索過(guò)的路徑儲(chǔ)存在其中。

步驟4在種群S(r)中比較適應(yīng)度函數(shù)，從中尋優(yōu)選擇部分個(gè)體作為父代F。

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

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

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

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

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

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

3.5 基因修復(fù)

4 案例研究

4.1 實(shí)驗(yàn)設(shè)置

經(jīng)過(guò)交叉、變異操作后，對(duì)于不滿足約束的染色體，

與上海港合作的昆山無(wú)水港要進(jìn)行貨物收集，昆山港附近有20個(gè)發(fā)貨點(diǎn)，發(fā)貨點(diǎn)的坐標(biāo)儲(chǔ)存于一個(gè)元胞矩陣XY中，每個(gè)發(fā)貨點(diǎn)的發(fā)貨量?jī)?chǔ)存于元胞矩陣A中，將每輛車的最大載重設(shè)定為1 400 kg。

相應(yīng)的發(fā)貨點(diǎn)位置，發(fā)貨量如表1所示。

表1 發(fā)貨點(diǎn)坐標(biāo)及發(fā)貨量

4.2 掃描法分組

如圖8所示，首先構(gòu)造極坐標(biāo)系，逆時(shí)針旋轉(zhuǎn)極軸，以車輛承載量1 400 kg為約束條件，進(jìn)行分組處理。如圖9所示，通過(guò)掃描法，將20個(gè)發(fā)出點(diǎn)分成了三個(gè)區(qū)域，每個(gè)區(qū)域內(nèi)的發(fā)出總量不超過(guò)1 400 kg，需要使用3輛貨車進(jìn)行裝載。

圖8 建立極坐標(biāo)系

4.3 算法參數(shù)及實(shí)驗(yàn)結(jié)果

4.3.1 小規(guī)模實(shí)驗(yàn)

在此案例分析中，使用MATLAB對(duì)該路徑優(yōu)化進(jìn)行模擬仿真。進(jìn)行實(shí)驗(yàn)的計(jì)算機(jī)配置為Win10 64位操作系統(tǒng)，安裝內(nèi)存（4.00 GB），CPU頻率1.80 GHz，所得出的有關(guān)運(yùn)行時(shí)間等的數(shù)據(jù)，都與該機(jī)器有關(guān)。

圖9 貨物分區(qū)示意圖

實(shí)驗(yàn)具體參數(shù)設(shè)置如下，種群規(guī)模數(shù)量為120，算法終止條件Iteration=400，交叉概率為0.9，變異概率為0.02，同時(shí)車輛超載的懲罰權(quán)重為300。

對(duì)發(fā)貨點(diǎn)優(yōu)先級(jí)以及車輛運(yùn)輸約束如表2所示。

表2 優(yōu)先級(jí)與運(yùn)輸約束

在滿足各種約束的情況下得到無(wú)水港集貨運(yùn)輸路徑優(yōu)化過(guò)程中距離的大小與迭代次數(shù)變化的仿真數(shù)據(jù)如表3。路徑優(yōu)化收斂圖如圖10，當(dāng)?shù)螖?shù)在149次之后，路徑優(yōu)化值沒(méi)有發(fā)生改變，在迭代次數(shù)達(dá)到400時(shí)，算法終止。

表3 模擬仿真數(shù)據(jù)

圖10 運(yùn)輸路徑優(yōu)化收斂圖

從表3中可以看出，當(dāng)?shù)螖?shù)為149時(shí)，最短路徑顯示為552.37 km，并且，隨著迭代次數(shù)的延伸，最短路徑并未發(fā)生改變。最優(yōu)路徑如圖11所示。

同時(shí)，為了驗(yàn)證改進(jìn)遺傳算法（IGA）的有效性和優(yōu)越性，將其與傳統(tǒng)遺傳算法（GA）以及粒子群算法（PSO）進(jìn)行比較，采用相同的實(shí)驗(yàn)數(shù)據(jù)，并將三種算法參數(shù)設(shè)置基本一致，對(duì)比結(jié)果如表4所示。

表4 路徑優(yōu)化結(jié)果對(duì)比

圖11 配送路徑示意圖

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

對(duì)一區(qū)而言，使用改進(jìn)遺傳算法進(jìn)行路徑優(yōu)化得到的最優(yōu)路徑全長(zhǎng)為199.61 km；二區(qū)的最優(yōu)路徑全長(zhǎng)為168.79 km；三區(qū)的最優(yōu)路徑全長(zhǎng)為183.97 km。三輛汽車總的行駛距離為552.37 km。

由圖11可看出：

第一輛貨車：

昆山無(wú)水港→發(fā)貨點(diǎn)14→發(fā)貨點(diǎn)13→發(fā)貨點(diǎn)17→發(fā)貨點(diǎn)15→發(fā)貨點(diǎn)3→發(fā)貨點(diǎn)2→發(fā)貨點(diǎn)18→昆山無(wú)水港

第二輛貨車：

昆山無(wú)水港→發(fā)貨點(diǎn)5→發(fā)貨點(diǎn)19→發(fā)貨點(diǎn)10→發(fā)貨點(diǎn)4→發(fā)貨點(diǎn)1→發(fā)貨點(diǎn)9→昆山無(wú)水港

第三輛貨車：

昆山無(wú)水港→發(fā)貨點(diǎn)20→發(fā)貨點(diǎn)7→發(fā)貨點(diǎn)8→發(fā)貨點(diǎn)11→發(fā)貨點(diǎn)12→發(fā)貨點(diǎn)16→發(fā)貨點(diǎn)6→昆山無(wú)水港

4.3.2 大規(guī)模實(shí)驗(yàn)

圍繞1個(gè)無(wú)水港進(jìn)行貨物收集，本次實(shí)驗(yàn)設(shè)置發(fā)貨點(diǎn)數(shù)量為50個(gè)，各點(diǎn)貨物總質(zhì)量為9 650 kg，采取小規(guī)模實(shí)驗(yàn)中相同的集貨方式，可以得到在發(fā)貨點(diǎn)增多時(shí)車輛配送軌跡，如表5所示。

表5 大規(guī)模實(shí)驗(yàn)車輛配送表

4.3.3 多規(guī)模實(shí)驗(yàn)下的算法對(duì)比

在集貨運(yùn)輸發(fā)貨點(diǎn)數(shù)量N以及運(yùn)輸車輛數(shù)m規(guī)模不同時(shí)，比較改進(jìn)遺傳算法（IGA）、傳統(tǒng)遺傳算法（GA）以及粒子群算法（PSO）在運(yùn)行結(jié)果以及運(yùn)行時(shí)間上的優(yōu)劣性，如表6所示。

對(duì)比表6結(jié)果可知，在小規(guī)模情景中，改進(jìn)遺傳算法下的最優(yōu)解略好于遺傳算法以及粒子群算法，但得到解的速率遠(yuǎn)大于二者。在實(shí)驗(yàn)規(guī)模的不斷擴(kuò)大下，從運(yùn)行時(shí)間以及計(jì)算結(jié)果雙重對(duì)比下，改進(jìn)遺傳算法的優(yōu)越性都得到充分體現(xiàn)。綜上所述，改進(jìn)遺傳算法能更好地解決本文所提出的問(wèn)題模型。

5 結(jié)果對(duì)比

以文中使用的小規(guī)模實(shí)驗(yàn)數(shù)據(jù)作為依據(jù)，用兩種傳統(tǒng)運(yùn)輸方式與本文改進(jìn)集貨方式運(yùn)輸之后的結(jié)果進(jìn)行對(duì)比分析，比較三種方式在運(yùn)送成本方面的優(yōu)劣性。

5.1 貨主自有卡車運(yùn)輸

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

表6 多規(guī)模實(shí)驗(yàn)結(jié)果算法對(duì)比

圖12 傳統(tǒng)集貨方式

成本計(jì)算方法為式（13）：

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

5.2 托運(yùn)方式運(yùn)輸

因?yàn)榘l(fā)貨點(diǎn)都會(huì)就近選擇無(wú)水港，所以距無(wú)水港的距離都不會(huì)太遠(yuǎn)，所以托運(yùn)單價(jià)穩(wěn)定。根據(jù)市場(chǎng)調(diào)研發(fā)現(xiàn)托運(yùn)單價(jià)均價(jià)為3元/kg。托運(yùn)總價(jià)格計(jì)算方法由式（14）給出：

由各發(fā)貨點(diǎn)貨物總質(zhì)量以及上式可得托運(yùn)總成本為12 120元。

5.3 改進(jìn)后運(yùn)輸方式

針對(duì)本文所提出的問(wèn)題，經(jīng)過(guò)研究后得出需要三輛貨車即可滿足20個(gè)發(fā)貨點(diǎn)所有貨物的運(yùn)輸，并且通過(guò)改進(jìn)的遺傳算法得出最優(yōu)行駛路徑為552.37 km，根據(jù)式（13），可以得出C總=5 485.67元 。將三種運(yùn)輸方式進(jìn)行對(duì)比，如表7。

表7 三種運(yùn)輸結(jié)果對(duì)比

6 結(jié)語(yǔ)

針對(duì)無(wú)水港的集貨效率低、成本高等問(wèn)題，提出了一種切實(shí)可行的解決辦法，即通過(guò)共享車輛的形式，既降低了發(fā)貨商的成本，也使得無(wú)水港的管理更加便捷。

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

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