帶中轉(zhuǎn)點的聯(lián)盟運輸調(diào)度的遺傳算法研究

摘要：結(jié)合城市貨物運輸?shù)木唧w特點，分析了多供應(yīng)點、多中轉(zhuǎn)點的聯(lián)盟運輸調(diào)度問題的優(yōu)越性。在分析聯(lián)盟運輸調(diào)度特點的基礎(chǔ)上，建立了優(yōu)化確定聯(lián)盟運輸調(diào)度問題中轉(zhuǎn)點的數(shù)學(xué)模型，并構(gòu)造了求解該問題的有效遺傳算法。算法中針對具體問題的特點，采用較新的交叉算子。實例計算表明，提出的模型和算法能夠有效地解決AVRP中轉(zhuǎn)點的確定問題。

關(guān)鍵詞：聯(lián)盟運輸調(diào)度； 中轉(zhuǎn)點； 優(yōu)化； 遺傳算法

中圖分類號：TP301文獻標(biāo)志碼：A

文章編號：1001-3695(2007)11-0082-03

貨物運輸車流是城市交通流的重要組成部分，它在滿足社會需求的同時也給城市交通帶來了擁擠問題。為了減少部分運輸路段載荷、緩解交通擁擠和促進城市交通設(shè)施的均衡使用，在城市中心區(qū)與外部區(qū)之間優(yōu)化選擇一定數(shù)目的位置，設(shè)置具有一定作業(yè)能力的貨物中轉(zhuǎn)點，以迫使由城市外部區(qū)去往中心區(qū)的貨物運輸需求分流為兩個以上的運輸路徑進行運送，從而減輕城市內(nèi)一些路段的車流載荷。這在一定程度上緩解了城市交通擁擠現(xiàn)狀。但是，在編制運輸計劃時，不能簡單地指定某個中轉(zhuǎn)點為某些固定的需求點服務(wù)。因此如何在運輸費用最省的前提下為每一次運輸合理選擇中轉(zhuǎn)點就成為帶中轉(zhuǎn)運輸調(diào)度問題的一個關(guān)鍵。遺傳算法是模擬生物在自然環(huán)境中的遺傳和進化過程而形成的一種自適應(yīng)全局優(yōu)化概率搜索算法。與傳統(tǒng)的優(yōu)化算法相比具有搜索過程靈活、搜索效率高以及隱含并行性等特點，是一類可用于復(fù)雜系統(tǒng)優(yōu)化計算的魯棒搜索算法。

1數(shù)學(xué)模型的建立

聯(lián)盟運輸調(diào)度問題[1]（allied vehicle routing and scheduling problem，AVRP AVSP）是指在滿足運輸要求的前提下，快速組織多種交通工具，允許車輛中轉(zhuǎn)，設(shè)計物流運輸工具組合、時間組合、線路組合等最優(yōu)策略，并為每一次運輸設(shè)計最優(yōu)的行車線路和時間表，追求經(jīng)濟效益的最大化和實現(xiàn)過程的最優(yōu)化。與普通的運輸調(diào)度問題（vehicle routing problems，VRP）相比，AVRP具有三個顯著的擴展特征：允許使用不同類型交通工具、允許使用多層次交通網(wǎng)絡(luò)、允許使用貨物中轉(zhuǎn)設(shè)施。近三十年來，VRP是組合優(yōu)化的研究熱點之一，但對AVRP研究很少。

本文針對允許車輛類型不同、允許中轉(zhuǎn)、允許使用多層次交通網(wǎng)絡(luò)的AVRP，在建立選取最優(yōu)中轉(zhuǎn)點的數(shù)學(xué)模型的基礎(chǔ)上，用改進的遺傳算法進行求解，以確定最優(yōu)的中轉(zhuǎn)點。對討論的問題進行如下說明[2]。 

1)中心區(qū)即城市中集土地混合使用、行政、文化、商業(yè)、旅游以及市民居住于一體，具有人口密度高、商業(yè)發(fā)達、行政化水平高、文化活動頻繁以及路網(wǎng)密度高、車流流量大等特征的區(qū)域。

2)外部區(qū)即遠離或鄰近城市并與城市產(chǎn)生往返貨流的地點，如港口、火車站、航空站、工廠、倉庫等生產(chǎn)與保管設(shè)施。

3)中轉(zhuǎn)點位于城市中心區(qū)與外部區(qū)之間，具有一定作業(yè)能力的基礎(chǔ)設(shè)施。

對帶中轉(zhuǎn)點的聯(lián)盟運輸調(diào)度問題進行研究可以從兩個方面考慮：

a)將帶中轉(zhuǎn)點的運輸調(diào)度問題分成兩個階段。第一階段根據(jù)某市中心區(qū)各需求點的分布情況，合理選定運輸中轉(zhuǎn)點。貨物可以以適當(dāng)?shù)奶崆捌谶\達中轉(zhuǎn)點。第二階段是在優(yōu)化選定中轉(zhuǎn)點之后，綜合考慮各種配送要素，結(jié)合聯(lián)盟企業(yè)共同配送等策略進一步優(yōu)化配送方案。實現(xiàn)貨物由中轉(zhuǎn)點到最終客戶的優(yōu)化配送。

b)將帶中轉(zhuǎn)點的運輸調(diào)度問題本身看做是一個復(fù)雜的組合優(yōu)化問題進行研究。這種方法的研究重點集中在如何合理地縮小搜索空間和簡化求解步驟上。本文選取第一類方法對帶中轉(zhuǎn)點運輸調(diào)度問題進行研究，集中討論第一階段的調(diào)度問題。

對所討論的運輸調(diào)度問題說明如下：只考慮一個供應(yīng)點經(jīng)一定數(shù)量中轉(zhuǎn)點為需求點提供配送服務(wù)；外部區(qū)與中轉(zhuǎn)點之間的貨物運輸車輛為單一大卡車類型；中轉(zhuǎn)點的數(shù)目已知且能夠隨時提供所需的中轉(zhuǎn)服務(wù)；中轉(zhuǎn)點內(nèi)小貨車作業(yè)能力不受限制，即中轉(zhuǎn)點能夠滿足卡車貨物換裝要求；每個需求點的配送服務(wù)僅經(jīng)過一個中轉(zhuǎn)點。

AVRP的網(wǎng)絡(luò)模型描述如下[3，4]：

2問題的遺傳算法

從建立的數(shù)學(xué)模型可知，確定中轉(zhuǎn)點就是一個優(yōu)化的問題，遺傳算法在解決優(yōu)化問題方面具有一定的優(yōu)勢。特別是在求解TSP問題中取得了一定的成果。在此可以借鑒，并構(gòu)造遺傳算法。

2．1染色體的結(jié)構(gòu)

為了提高搜索效率和表達的方便，采用自然數(shù)編碼[5]。可供選擇中轉(zhuǎn)點的個數(shù)為m，從m個中轉(zhuǎn)點中可重復(fù)隨機地選取n個中轉(zhuǎn)點分配給n個需求點作為一個初始解，在求解的運輸調(diào)度問題中表示為各需求點提供中轉(zhuǎn)服務(wù)的中轉(zhuǎn)點組合，并按需求點編號順序排列。該組合是一種可能的中轉(zhuǎn)點分配方案。染色體中允許有相同的基因位，在求解的運輸調(diào)度問題中則表示多個需求點的貨物可以在一個中轉(zhuǎn)點進行中轉(zhuǎn)作業(yè)。例如，城市的外部區(qū)和中心區(qū)之間有三個中轉(zhuǎn)點可供選擇，城市中心區(qū)六個需求點并順序編號，則位串{2 3 2 3 1 2}表示第一個需求點在第二個中轉(zhuǎn)點中轉(zhuǎn)換裝，第二個需求點在第三個中轉(zhuǎn)點中轉(zhuǎn)換裝，第三個需求點在第二個中轉(zhuǎn)點中轉(zhuǎn)換裝。依此類推。 2．2產(chǎn)生初始種群

初始種群(chrom)由種群規(guī)模決定的若干染色體構(gòu)成。種群中的任一染色體必須遵循染色體的結(jié)構(gòu)要求，最終形成的染色體可由一個二維矩陣表示。

2．3適應(yīng)度函數(shù)

適應(yīng)度的計算按照個體目標(biāo)值ObjV由小到大的順序進行排列，并返回一個包含對應(yīng)個體適應(yīng)度值FitnV的列向量。2．4自然選擇

這里采用輪盤賭選擇法，并在輪盤賭選擇法的基礎(chǔ)上采用最佳個體保存選擇策略，就是用適應(yīng)度值最大的染色體代替下一代適應(yīng)度最低的染色體。這樣可以保證最優(yōu)個體可以生存到下一代，避免了最優(yōu)個體的中途丟失，并且加速算法向最優(yōu)解收斂。

2．5染色體的交叉

帶中轉(zhuǎn)點的運輸調(diào)度問題具有組間無序、組內(nèi)無序的特性，如果單純地使用一般的交叉算子往往會使一些優(yōu)秀的子串被破壞，并且在兩父個體相同時，無法再產(chǎn)生新的個體。在此采用一種有效的多點交叉算子，在多點交叉中有m個交叉位（特別當(dāng)m=1時為單點交叉），ki∈{1，2，…，n-1}。這里ki是交叉點；n是染色體的長度。這m個交叉點是通過隨機數(shù)選擇的、沒有重復(fù)、按升序排列的。父染色體中在兩個相連的交叉位間的基因進行交換，產(chǎn)生兩個新的子代；個體第一個基因位到第一個交叉點之間的位并不進行交換。 

2．6染色體的變異

在自然變化中，變異是一隨機過程，是基因上的一個等位基因被另一個替代而產(chǎn)生的新的遺傳結(jié)構(gòu)。在遺傳算法中，變異采用任意小概率，典型值在0.001～0.1。在本問題求解過程中采用2交換作為變異算子，即在每代群體中隨機選取染色體上的兩點，然后將選定的兩點基因碼進行交換，從而完成變異。采用變異率為0.01。

本文所構(gòu)造的遺傳算法是在基本遺傳算法的基礎(chǔ)上改進的。在隨機產(chǎn)生的種群中進行世代的進化，按照適應(yīng)度的高低選擇雙親；經(jīng)過一系列算子的操作產(chǎn)生優(yōu)于父代的子代，用子代以0.9的代溝代替父代，執(zhí)行新一輪的進化，直到滿足停止條件，產(chǎn)生最優(yōu)個體，獲得最優(yōu)解。該算法的程序流程如圖1所示。具體的操作步驟如下：

begin

設(shè)置算法參數(shù)

隨機產(chǎn)生初始種群；

for(gen=0；gen

{

for(i=0；i

{

計算種群中第i 個染色體的適應(yīng)度；

計算種群中第i 個染色體的目標(biāo)值； 

}

根據(jù)適應(yīng)度選擇父代；

根據(jù)交叉概率進行交叉操作； 

根據(jù)變異概率進行變異操作；

用新生的子代以0.9的代溝代替父代；

}

End

3實驗計算與結(jié)果分析

為驗證本文針對帶中轉(zhuǎn)點的聯(lián)盟運輸調(diào)度所設(shè)計的遺傳算法的實際運行效果，以2個供應(yīng)點、15個需求點、8個中轉(zhuǎn)點為例進行了計算機求解。問題的具體描述如下：某城市中心區(qū)內(nèi)有15個需求點需要配送服務(wù)，在該城市中心區(qū)和外部區(qū)之間共有8個中轉(zhuǎn)點可以提供足夠的中轉(zhuǎn)服務(wù)，應(yīng)用本文遺傳算法為本次配送服務(wù)選取最優(yōu)的中轉(zhuǎn)服務(wù)。實驗計算所需要的基本數(shù)據(jù)，即需求點的易達程度系數(shù)W={0.47 0.97 0．76 0．84 0．95 0.87 0.96 0.87 0.95 0.97 0.98 0.95 0.82 0.95 0.92}。實驗結(jié)果如表1~3所示。

4結(jié)束語

中轉(zhuǎn)點的優(yōu)化確定是帶中轉(zhuǎn)的聯(lián)盟運輸調(diào)度問題的一個核心問題。本文在建立中轉(zhuǎn)點優(yōu)化確定數(shù)學(xué)模型的基礎(chǔ)上，構(gòu)造了求解該問題的遺傳算法。實驗結(jié)果表明該算法簡單有效，但由于運輸調(diào)度問題還可以衍生出很多更為復(fù)雜也更貼近實際應(yīng)用的問題[7，8]，如多個供應(yīng)點、多車隊、時間窗、多重運輸需求、多種運輸環(huán)節(jié)、多重交通網(wǎng)絡(luò)、多重約束條件、客戶需求多樣性等，這些都是帶中轉(zhuǎn)點聯(lián)盟運輸調(diào)度問題必須綜合考慮的問題，也是今后進一步研究的方向。

參考文獻：

[1]師凱，蔡延光， 鄒谷山， 等. 分段蟻群算法在運輸調(diào)度問題中的應(yīng)用[J]. 廣東工業(yè)大學(xué)學(xué)報， 2006，23(1):72-76.

[2]朱強，卜雷，徐建閩. 城市貨物換裝站非約束選址模型及其遺傳算法[J].華南理工大學(xué)學(xué)報：自然科學(xué)版， 2005，33(7):92-95.

[3]吳堅，史忠科. 基于遺傳算法的配送中心選址問題[J].華南理工大學(xué)學(xué)報：自然科學(xué)版，2004，36(15):71-74.

[4]蔣忠中，汪定偉. B2C電子商務(wù)中配送中心選址優(yōu)化的模型與算法[J].控制與決策， 2005，20(10):1125-1128.

[5]王小平，曹立明.遺傳算法——理論、應(yīng)用與軟件實現(xiàn)[M].西安：西安交通大學(xué)出版社，2005.

[6]雷英杰，張善文，李續(xù)武，等.MATLAB遺傳算法工具箱及應(yīng)用[M]. 西安：西安電子科技大學(xué)出版社，2005.

[7]蔡延光，錢積新，孫優(yōu)賢. 多重運輸調(diào)度問題的模擬退火算法[J]. 系統(tǒng)工程理論與實踐，1998 （10）：11-15.

[8]蔡延光，錢積新，孫優(yōu)賢. 多重運輸調(diào)度問題基于雙表的并行表搜索算法[J]. 系統(tǒng)工程理論與實踐，1998 （11）：20-26.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文”