基于遺傳算法的廣西集裝箱多式聯運運輸優化研究

申慧芝　經素萍　黃睿伶

【摘 要】集裝箱多式聯運作為一種新型多式聯運方式，將多式聯運和集裝箱有效地結合在一起，與傳統的運輸方式相比更安全、更靈活、更有效，正是這些特點使得近幾十年來集裝箱多式聯運快速發展，然而如何優化集裝箱多式聯運，有效地協調各種運輸方式，降低運輸成本，提高運輸效率，成為集裝箱多式聯運的有效研究課題。

【關鍵詞】遺傳算法；集裝箱；多式聯運；運輸優化

0 引言

隨著全球經濟一體化進程的加快，產業供應鏈變得越來越復雜，運輸網絡變得越來越廣泛，貨物運輸需求也發生了變化——以顧客需求為中心的方便、快捷、高效、低價的貨物運輸已成為必然趨勢，單一的集裝箱運輸模式已經不能滿足當今全球供應鏈管理的發展要求，因此，以貨物運輸為主的集裝箱多式聯運在全球范圍內得到了廣泛的認可與使用，創建高效的集裝箱多式聯運模式也已成為各國經濟可持續發展的關鍵因素之一。

集裝箱多式聯運的發展是建立在完善的綜合運輸體系之上的。然而，長期以來廣西的交通運輸已成為其經濟發展的瓶頸，由于基礎設施不完善，沒有一個統一的綜合運輸統籌部門，各種運輸方式沒有真正發揮組合優化的作用，通暢的、安全的、便捷的集裝箱多式聯運網絡尚未建立。因此，本文希望通過分析廣西集裝箱多式聯運存在的問題，以廣西集裝箱多式聯運系統內各運輸方式與運輸路徑實現最優化組合為目標，為廣西集裝箱多式聯運的發展提供參考和理論指導。

1 遺傳算法的原理及優化模型的建立和實現

1.1 遺傳算法的原理

遺傳算法簡稱GA（Genetic Algorithm），在本質上是一種不依賴具體問題的直接搜索方法。遺傳算法的基本思想是基于Darwin進化論和Mendel的遺傳學說，Darwin進化論最重要的是適者生存原理：它認為每一物種在發展中會越來越適應環境，物種每個個體的基本特征由后代所繼承，但后代又會產生一些異于父代的新變化。在環境變化時，只有那些能適應環境的個體才能保留下來。Mendel遺傳學說最重要的是基因遺傳原理。它認為遺傳以密碼方式存在于細胞中，并以基因形式包含在染色體內。每個基因有特殊的位置并控制某種特殊性質，所以，每個基因產生的個體對環境具有某種適應性。基因突變和基因雜交可產生更適應環境的后代。經過存優去劣的自然淘汰，適應性高的基因結構得以保存下來。

下圖是遺傳算法的運算過程圖：

基于上述思路，在應用上設計多式聯運最優路徑求解的步驟。將數據隨機置于起始點，對每條路線按照多個起始點計算其運輸費用。

1.2 優化模型的建立和實現

（1）根據集裝箱多式聯運運輸資源配置的分析可知，該問題屬于非線性約束組合問題，即使問題規模較小時也難以解決，隨著規模的增大，解決問題的復雜度也增大。近幾年來隨著仿真優化方法研究的逐漸完善，Tabu算法越來越多應用到仿真模型優化中，該算法具有大量隨機參數的組合優化問題等特點。

（2）運用仿真優化方法，結合仿真模型算法的特點對系統資源配置協調優化問題進行求解，通過運行仿真模型得到相應的評價指標，在滿足約束條件的基礎上，對仿真方案進行不斷的矯正，最后得出較優的運輸方案。

（3）優化模塊。主要通過遺傳算法算出問題的最優解，根據具體的目標，采用科學算法，搜索仿真模型的最優解，并對其進行優化組合。

2 基于遺傳算法的廣西集裝箱多式聯運運輸優化實例分析

2.1 問題假設

假設某多式聯運經營人準備建立和開發一條由廣西柳州（O）至廣西欽州（D）的集裝箱多式聯運路線，中途可選擇若干個（n個）城市作為中間節點，任意相鄰的兩個城市之間都有若干種（g種）運輸方式可供選擇，在相鄰的兩個城市之間各種運輸方式的運輸時間、運費、運輸能力不同，當從一種運輸方式轉換到另一種運輸方式時，需要一定的中轉時間和中轉費用，而且在整個運輸過程中的總時間不能超過運輸期限（T），在考慮上述各種因素的前提下確定最佳的運輸路線和組合方式，使得總運費和總運輸時間為最少。

為了對問題進行有效的求解，參考Spiess和Florian提出的多式聯運的優化算法，本文將每一個城市到另一個城市的每一種運輸方式都單獨作為一條運輸路線加入到運輸網絡中。即如圖2城市1到城市2是連通的，我們用一條有向箭頭表示城市1到城市2之間連通，但實際城市1到城市2共有三種運輸方式可行，所以將圖2進行改進后成為了圖3，兩種從城市1到達城市2的運輸方式成為了三條可選的運輸路線。這樣就可以將這個多式聯運運輸優化問題轉化成一個最短路問題。

2.2 優化模型的建立

針對最短路問題的特點先對模型作以下假設：

（1）運量在某兩個城市之間不能分割，即在某兩個特定的城市之間，只能選擇一種運輸方式；

（2）運輸成本與距離成線性關系。

為了建立模型用有向圖G（N，A）來代表多式聯運的運輸網絡圖，其中N表示結點集合，A表示邊集合，N表示G圖的結點總個數。C=[Cijk]表示圖G的鄰接權矩陣——即運輸費用矩陣，k={1，2，3}代表三種可行的運輸方式，其中T=[tijk]表示第二鄰接權矩陣——即運輸時間矩陣，當城市i、j沒有任何方式相鄰的時候：Cijk=tijk=N（N為一非常大的正整數）。始點與終點分別以O和D來表示。Ii表示節點i是否被選擇到運輸路線中。Ii=1代表節點被選取到運輸路線中，0代表沒有被選取。Wijk等于I（i）與I（j）相與，即I（i）與I（j）是否以第k種運輸方式被選入到運輸路線中，當I（i）&I（j）=1時，Wijk=1；當I（i）&I（i）=0時，Wijk=N，即節點i， j之間沒有被選擇作為運輸路線。

2.3 優化模型的求解算法

基于上面的問題模型可以看出這個問題是一個NP難題，很難得到全局最優解或滿意解，如用改進的遺傳算法對其進行求解，能取得較好的效果[i]。在用遺傳算法對該模型進行求解時主要要進行下面幾項工作。endprint

（1）確定個體的編碼方式：對于遺傳算法來說，它的可行解由個體來表示，主要在個體之間中進行交叉、變異的操作生成新的個體，直到得到合乎條件的個體為止。所以如何決定個體的編碼方式，對問題的求解速度、誤碼率、最優解的范圍都有很大影響。拿一個8城市3種運輸方式的運輸網絡來說，染色體長度就是8x（8+1）=72，其中城市選取用0-1來代表節點是否被選中，而運輸方式的選取用1-3的自然數編碼來表示。

（2）確定初始群體：若干個染色體或個體組成的一組向量稱為一個群體，遺傳算法計算的第一步首先要確定一個初始群體，在此基礎上才可以進行之后的遺傳進化過程。初始群體的選擇應該具有較為廣泛的代表性，并且要有足夠多的染色體（個體），否則有可能陷人局部最優解而出現早熟現象。論文的染色體生產的方式是隨機生成大部分染色體，再在群體中加入一部分可行解染色體，作為初始群體。

（3）確定適應度函數：在遺傳算法中用適應度函數來表明個體和解的優劣性，用來確定個體遺傳到下一帶的概率，適應度越高的個體遺傳到下代的概率就越高，這樣就保證了個體向最優解的方向發展。本文直接用目標函數作為適應度函數，即f（x）=z（x）。同時為了防止在計算早期出現個別特殊個體，用以下方式對適應度函數其中f是原適應度函數，f'是標定后的適應度函數，fmax、fmin分別是按照實際問題的一個估計值，δ為一個0到1之間的正實數。

（4）確定交叉和變異規則：交叉是指種群中確定的染色體做為父代，通過一定規則產生子代染色體的過程，這一過程所遵循的規則稱為交叉規則。這里我們采用兩點交叉法，在這種方法中，在親代中選擇好兩個染色體，隨機產生兩個點，作為交叉點，然后將兩個染色體中兩個交叉點之間的對應信息碼相交換得到兩個子代的染色體。然而，經過該操作后，新產生的后代不一定符合約束條件，所以還要對產生的新個體進行檢驗，如果不符合約束條件，還要重新進行交叉，直到滿足約束條件為止。

3 總結

由以上的分析可以看出，集裝箱多式聯運運輸方式組合優化模型在成本最小的前提下，通過遺傳算法和計算機編程的運用，可以較方便地求出最優解。在多式聯運運輸下，以運輸系統收益最大為目標，設計與遺傳算法相結合的組合算法對模型進行求解。在集裝箱多式聯運運輸總成本最小化的基礎上，通過對各種費用和時間的分析，為多式聯運企業選擇最優運輸路徑，也為廣西集裝箱多式聯運運輸方式合理安排提供了一定的依據。

【參考文獻】

[1]倪呈英.淺析我國集裝箱多式聯運現狀[J].物流工程與管理，2016，38（08）：88-89.

[2]潘常虹，范厚明.集裝箱多式聯運系統的Petri網建模及其性能分析[J].鐵道運輸與經濟，2015，37（03）：59-63.

[3]周躍.集裝箱多式聯運運輸決策與協調問題的研究[D].南京：河海大學，2006.

[4]張得志，凌春雨.多種運輸方式的組合優化模型及求解算法[J].長沙鐵道學院學報，2002.

[5]井祥鶴，魏冬峰，周獻忠.運輸方式選擇多目標優化問題混合遺傳算法[J].計算機工程與應用，2008（6）：210-214.

[6]康凱，牛海嬌，朱越杰，張維存.多式聯運中運輸方式與運輸路徑集成優化模型研究[J].計算機應用研究，2010.endprint