混合遺傳算法的多式聯(lián)運運輸管理研究?

陳利民

（北京師范大學(xué)珠海分校 珠海 519087）

1 引言

多式聯(lián)運是物流系統(tǒng)中的主流方式，涉及運輸中的路線優(yōu)化選擇，以運輸費用或時間來衡量路線或者方式的優(yōu)劣［1～2］，它可以有效地提高運輸業(yè)的服務(wù)性、競爭力和綜合效益，因此它擁有很強的實際意義。運輸物流不僅要考慮交通、氣候等多個因素，而且在實際路線優(yōu)化問題中，最終確定方案的決策信息是不固定的［3］。多式聯(lián)運的出現(xiàn)很快利用在原料的采集、物品的生產(chǎn)、貨物的供應(yīng)等重要環(huán)節(jié)。同時，在經(jīng)濟一體化中，多式聯(lián)運的技術(shù)和理念也渴望由第三方物流發(fā)展到第四方物流［4］。

文獻［5］利用層次分析以及決策論的規(guī)律，對多式聯(lián)運的運輸問題問題做了研究；文獻［6］結(jié)合運輸過程的分層系統(tǒng)以及多式聯(lián)運網(wǎng)絡(luò)的建構(gòu)原理方法，提出了多式聯(lián)運決策框架；文獻［7］也提出了最優(yōu)運輸路徑的最短路法；文獻［8］將多個運輸方式的聯(lián)合解決運輸問題，將時間條件，能力限制等作為約束提出最優(yōu)路徑的啟發(fā)式算法。

本文主要利用混合遺傳算法，通過設(shè)置約束條件，建立多式聯(lián)運數(shù)學(xué)模型，對每個節(jié)點進行染色體編碼，從而求解出該算法得到的最優(yōu)解，仿真實驗得出該算法有很強的實際利用價值。

2 多式聯(lián)運的數(shù)學(xué)模型

2.1 構(gòu)建模型

我們假設(shè)有一個多式聯(lián)運運輸方式優(yōu)化問題，可以描述為，一物流公司欲將一批物資從始發(fā)地O送達目的地P，需要經(jīng)過n個城市，其中任意兩個相鄰城市間都有K種運輸方式（包括水路、公路、鐵路）可以選擇，顯然不同運輸方式的運輸時間和運輸成本是不同的，并且如果從一種運輸方式換成另外一種運輸方式，需要中轉(zhuǎn)費用和中轉(zhuǎn)時間。假設(shè)運輸方式的中轉(zhuǎn)只發(fā)生于城市內(nèi)，并且不同城市的中轉(zhuǎn)費用和中轉(zhuǎn)時間是不一樣的，那么該怎樣選擇運輸方式，才能實現(xiàn)運輸成本最少，運輸時間最短。

假設(shè)該優(yōu)化問題需滿足以下四個條件［9～10］：

條件1為物資的轉(zhuǎn)運只發(fā)生在城市節(jié)點，并且每個城市節(jié)點最多發(fā)生一次轉(zhuǎn)運；條件2為物資在城市節(jié)點間只可以整體運載，不可以分割；條件3為物資在兩個城市節(jié)點間只可以選擇一種運輸方式和一條運輸路徑；條件4為物資在每個城市節(jié)點即時中轉(zhuǎn)，沒有庫存。

在上述的多式聯(lián)運運輸方式優(yōu)化問題中，需要同時考慮最小化運輸總成本和運輸總時間，這兩個目標(biāo)的數(shù)學(xué)模型可以描述為

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

約束條件為

2.2 運輸方式與運輸路線優(yōu)化的關(guān)系

多式聯(lián)運中每兩個節(jié)點之間的運輸方式以及運輸路徑是有密切聯(lián)系的［11］。若選擇某種運輸方式如圖1（a），不同的線表示不同的運輸方式，圖1（b）表示該運輸方式所對應(yīng)的運輸路徑。在某種運輸方式下選擇的路線是判斷運輸方式好壞的依據(jù)。

3 混合遺傳算法

3.1 算法原理

通過對上述問題以及模擬運輸網(wǎng)絡(luò)圖的分析能夠發(fā)現(xiàn)，該運輸方式優(yōu)化問題實質(zhì)是約束條件下的最短路問題［12～13］。即在給定的約束條件下，實現(xiàn)目標(biāo)城市對間路線的最優(yōu)組合問題。因此，本文試圖采用隨機化搜索，即遺傳算法來實現(xiàn)各城市對間路線的最優(yōu)組合。第一步先進行編碼和群體初始化（群體數(shù)量為K）生成一組方案集，分別算出各個方案的運輸總成本 Fˉ(k)????(k=1，2，…，K)；第二步對Fˉ(k)進行排序，可以采用區(qū)間數(shù)排序來辨別個體的優(yōu)劣，以此為依據(jù)構(gòu)造混合遺傳算法尋求最優(yōu)路線組合方案。隨機化搜索路徑如圖2所示。

圖2 隨機化搜索路徑圖

3.2 染色體編碼技術(shù)

模型中我們采用字符代碼對其進行編碼，其中城市對間的運輸路線編號代表該問題的染色體編碼［14］。如果從運輸始發(fā)地O到目的地P之間需要經(jīng)過n個城市，從始發(fā)地O到目的地P之間要經(jīng)過2n+1個虛擬城市。我們用一組2n+1個數(shù)字來代表一個運輸路線組合的染色體編碼。

例如：

即在始發(fā)地和城市1組成的城市對間我們選取第3條路線，在城市1和城市2組成的城市對間我們選取第1條路線……在城市n與目的地組成的城市對間我們選取第2條路線。最初群體初始化時，每個染色體的第 1，3，5，7，…，2n-1，2n+1個基因是從城市對間的路線編號中隨機生成排列得來，第 2，4，6，…，2n 個基因分別與第 3，5，7，…，2n+1個基因相同，故可以直接復(fù)制。根據(jù)某個染色體的編碼串，可以記錄下對應(yīng)運輸任務(wù)在城市對間所選取的路線。

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

假 設(shè) 存 在 某 一 染 色 體 為 ch(k)=(y1，y2，…，y2j-1，y2j，y2j+1，…，y2n，y2n+1) ，它 的 意 思 是 在 城 市j-1與城市 j組成的城市對間選取第 y2j-1條路線，在城市 j與城市 j+1組成的城市對間選取第y2j條路線。到達城市 j時，需要從第 y2j-1條路線轉(zhuǎn)換成第 y2j條路線。我們將運輸總成本Fˉ(k)視作染色體ch(k)所表示的路線組合方案的目標(biāo)函數(shù)［15］：

運輸總時間方程：

構(gòu)造的適應(yīng)度函數(shù)Eˉ(k)如下：

其中Cmax是一個恰當(dāng)?shù)妮斎胫?。個體的適應(yīng)度與其適應(yīng)度函數(shù)值成正相關(guān)，并且個體遺傳到下一代的概率與適應(yīng)度也成正相關(guān)。

3.4 構(gòu)造遺傳算子

首先：選擇算子，第一步對群體中的所有個體進行排列，依據(jù)適應(yīng)度值從大到小的次序進行，之后將其均分為10組；第二步依次將第l組中所有個體復(fù)制兩份，將第2～9組中所有個體復(fù)制一份，第10組不復(fù)制。這樣選擇算子可以保證每次進化都可以使適應(yīng)度高的個體被復(fù)制到新的種群中，同時群體規(guī)模不變。

其次：交叉算子，即群體間隨機配對，從而將隨機生成交叉點位置，再單獨用交叉概率交換交叉點后的基因，生成新的個體。為確保新個體為有效染色體，我們對交叉點位置做如下設(shè)計：設(shè)ch(x)、ch(y)為一對交叉染色體，交叉點是第k個基因座之后，那么k取值為

其中 rα為[0 ， 1]內(nèi)一個服從均勻分布的隨機數(shù)；n表示經(jīng)過的城市數(shù)量；round()表示四舍五入到最接近的整數(shù)。

最后：變異算子，ch(x)=(c1，c2，…，ck，…，c2n+1)向 ch*(x)=(c1，c2，…，，…，c2n+1)。

其中 rα為[0 ， 1]內(nèi)一個服從均勻分布的隨機數(shù)；n表示經(jīng)過的城市數(shù)量；round()表示四舍五入到最接近的整數(shù)。K是城市對間路線數(shù)量。對個體ch(x)=(c1，c2，…，ck，…，c2n+1)進行變異的具體操作設(shè)計如下：

2）若 k=1，則令 ck=；若 k≠1，則令 ck=且ck-1=，隨即產(chǎn)生新的個體。

3.5 算法流程

結(jié)合上述分析，混合遺傳算法的多式聯(lián)運運輸路線優(yōu)化問題的步驟如下：

Step 1：群體初始化 G(s)，s=0（s是進化的代數(shù)，G(s)是第s代群體），設(shè)群體數(shù)量為M，對初始化群體進行編碼。

Step 2：計算個體的適應(yīng)度Eˉ(k)及其對應(yīng)方案的運輸總時間 Tˉ(k)。

Step 3：若 Tˉ(k)＞ Tˉ0，則刪除該個體。

Step 4：若在步驟3中刪除了q個個體，為保證群體內(nèi)個體數(shù)量不變，則從剩余群體中復(fù)制q個個體。

Step 5：對群體中的所有個體按照適應(yīng)度從大到小的順序進行排列。

Step 6：若 s≤S（S是遺傳運算停止條件），那么轉(zhuǎn)到步驟7，反之轉(zhuǎn)到步驟1。

Step 7：對群體G(s)進行選擇操作。

Step 8：用交叉算子對群體G(s)實行交叉操作。

Step 9：用變異算子對群體G(s)實行變異操作。

Step 10：對群體的多樣性進行判斷和調(diào)整。

Step 11：得 到 新 一 代 群 體 G(s+1)，G(s)←G(s+1)，s← s+1，轉(zhuǎn)步驟2。

Step 12：對適應(yīng)度最大的染色體解碼，從而結(jié)束遺傳迭代。

4 仿真實驗

仿真中假設(shè)一批貨物，重量是4000t，時間要求在［40h～50h］從O地運送到Q地。O、Q兩處之間的運輸網(wǎng)絡(luò)信息（表1）以及換裝信息（表2），另外貨物的特殊性，使得增加了其他約束條件中途換裝次數(shù)不能多于兩次，通過混合遺傳算法求解最佳運輸路徑，最佳運輸方式求解最佳的運輸方式，使得組合使總費用最省，并且時間期限也到達到客戶標(biāo)準。

表1中給出了每條線路中每個節(jié)點的運輸費用范圍以及運輸時間范圍，表2給出每個節(jié)點的換裝時間與費用，這都是算法中的約束條件，用來求解最優(yōu)解。

表1 運輸網(wǎng)絡(luò)信息

表2 換裝信息

取群體規(guī)模M=50，交叉概率是0.7，變異概率為0.01，迭代次數(shù)為50，用本文的混合遺傳算法程序?qū)υ搯栴}進行最優(yōu)化求解。如圖3可知，當(dāng)?shù)降?次時，優(yōu)化結(jié)果不變，此時運輸總費用是［350，370］范圍，而運輸?shù)目倳r間范圍是［35，42］，運輸總費用和運輸總時間隨進化代數(shù)的變化曲線如圖3所示。算法求解的最優(yōu)結(jié)果為運輸路線方式是5即②→②→②→③，運輸?shù)奶摂M運輸網(wǎng)絡(luò)如圖4。

圖3 運輸總費用與運輸總時間變化圖

圖4 求解結(jié)果虛擬運輸網(wǎng)絡(luò)圖

5 結(jié)語

本文對于多式聯(lián)運問題中運輸路徑以及運輸方式的多樣性的客觀需求和目標(biāo)客戶對貨物運輸時的經(jīng)費、時間等實際的要求作為約束條件，基于以上問題本文提出了運輸方式和運輸路徑構(gòu)成優(yōu)化模型，設(shè)計混合遺傳算法對優(yōu)化模型進行求解，通過實際的運輸路徑、運輸費用、運輸時間以及換裝次數(shù)等多個要求進行算法迭代，獲得優(yōu)化的運輸方案，通過實例對模型及算法進行檢驗，可以很好地供應(yīng)商提供更好的選擇方案。