免疫算法在應(yīng)急物流配送車輛優(yōu)化調(diào)度中的應(yīng)用

摘要：應(yīng)急物流是處理各類突發(fā)事件對(duì)物資、人員的需求進(jìn)行緊急保障的一種特殊物流活動(dòng)。文章根據(jù)應(yīng)急物流的特點(diǎn)，將免疫算法用于應(yīng)急物流車輛調(diào)度研究中，同時(shí)通過(guò)算例，證明用免疫算法優(yōu)化車輛行駛路徑的有效性和可行性。

關(guān)鍵詞：應(yīng)急物流；免疫算法；車輛優(yōu)化調(diào)度

中圖分類號(hào)：F224文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1002-3100(2008)11-0024-04

Abstract: Emergency logistics is a kind of special logistical activity solving all kinds of unexpected events which are demanded seriously to the goods and manpower. According to the characteristics of the emergency logistics， this text applies the immune algorithm in the emergency logistics distribution VRP. At the same time， an example is given to prove the efficiency and usability in the vehicle rooting problem.

Key words: emergency logistics; immune algorithm; vehicle rooting problem

0引言

在我國(guó)，自然災(zāi)害、事故災(zāi)難、公共衛(wèi)生和社會(huì)安全等突發(fā)事件時(shí)有發(fā)生。而在各種突發(fā)事件后，救援人員的及時(shí)到達(dá)，人員財(cái)產(chǎn)的快速轉(zhuǎn)移和救援物資的運(yùn)送發(fā)放等對(duì)于提高應(yīng)急響應(yīng)能力、解決救援事件、降低生命財(cái)產(chǎn)損失具有重要的意義。其中，應(yīng)急物流的VRP（Vehicle Rooting Problem）優(yōu)化問(wèn)題是確保工作順利進(jìn)行的關(guān)鍵。

VRP是在一系列已知裝貨點(diǎn)和卸貨點(diǎn)組成的運(yùn)輸網(wǎng)絡(luò)中，組織適當(dāng)?shù)男熊嚲€路， 使車輛運(yùn)輸?shù)奈镔Y有序地通過(guò)它們，在滿足一定的約束條件（如貨物需求量、發(fā)送量、交發(fā)貨時(shí)間、車輛容量限制、行駛里程限制、時(shí)間限制等）下，達(dá)到一定的目標(biāo)（如路程最短、費(fèi)用最少、使用車輛數(shù)量盡量少等）。

應(yīng)急物流VRP與普通物流VRP決策目標(biāo)之間有明顯的差異。由于應(yīng)急物流的特殊性，人們往往更注重時(shí)間方面的及時(shí)性和最終的救災(zāi)效果，而忽視了這一物流過(guò)程中的物流經(jīng)濟(jì)性。對(duì)于應(yīng)急物流VRP優(yōu)化問(wèn)題的研究可以在滿足應(yīng)急物流時(shí)間要求（時(shí)間窗限制）的前提下，更合理的安排車輛的調(diào)度運(yùn)行，最大程度的節(jié)省物流成本。

人工免疫系統(tǒng)是從生物免疫系統(tǒng)中獲得靈感，并與計(jì)算機(jī)技術(shù)相結(jié)合以解決工程實(shí)際問(wèn)題的計(jì)算機(jī)模型。本文將免疫算法應(yīng)用于應(yīng)急物流配送的車輛優(yōu)化調(diào)度中，以便在考慮時(shí)間作為第一關(guān)鍵因素的前提下，最大程度地節(jié)省物流成本，從而找到一條最優(yōu)路徑。

1問(wèn)題描述及模型建立

為了簡(jiǎn)化問(wèn)題的復(fù)雜度并兼顧應(yīng)急物流配送的特點(diǎn)，便于模型的建立，特作以下假設(shè)：

（1）物資儲(chǔ)備中心與各受災(zāi)地點(diǎn)、各受災(zāi)地點(diǎn)之間的運(yùn)輸距離作為已知量。

（2）每個(gè)受災(zāi)地點(diǎn)對(duì)救災(zāi)物資的需求是可以提前運(yùn)達(dá)，但是不能晚于規(guī)定時(shí)間送到。即問(wèn)題為有單邊的硬時(shí)間窗的車輛調(diào)度優(yōu)化問(wèn)題。

（3）所有的受災(zāi)地點(diǎn)的需求，在物資數(shù)量方面和運(yùn)輸時(shí)間方面都能夠得到滿足；同時(shí)單個(gè)需求節(jié)點(diǎn)的需求量小于單車最大載重量。

（4）在受災(zāi)時(shí)期，路況、交通條件的變化采用路況系數(shù)，分正常和高峰兩種情況。

目標(biāo)函數(shù)（1）表示產(chǎn)生的費(fèi)用最小，約束式（2）表示l型車k服務(wù)需求點(diǎn)i時(shí)的需求量不允許超過(guò)其車輛的載重量；式（3）表示每個(gè)需求點(diǎn)只允許訪問(wèn)一次；式（4）、（5）表示任何一個(gè)受災(zāi)地區(qū)需求節(jié)點(diǎn)只有1臺(tái)車?？啃敦?；式（6）表示i，j為k所服務(wù)客戶，且i為j前趨；式（7）表示排除的車輛數(shù)等于返回的車輛數(shù)；式（8）表示救災(zāi)物資送到各個(gè)需求節(jié)點(diǎn)的時(shí)間必須在時(shí)間窗范圍內(nèi)；式（9）表示l型車行駛經(jīng)過(guò)i，j的時(shí)間，并考慮路況；式（10）表示l型車從i行駛至j時(shí)的費(fèi)用。

2免疫算法

免疫算法是借鑒了免疫系統(tǒng)學(xué)習(xí)性、適應(yīng)性以及記憶機(jī)制等特點(diǎn)而發(fā)展起來(lái)的一種優(yōu)化組合方法，在使用免疫算法解決優(yōu)化問(wèn)題時(shí)，各個(gè)步驟都與免疫系統(tǒng)有對(duì)應(yīng)關(guān)系。如抗原對(duì)應(yīng)要解決問(wèn)題數(shù)據(jù)輸入（如目標(biāo)、約束）；抗體對(duì)應(yīng)問(wèn)題的解；親和力對(duì)應(yīng)解的評(píng)估等。具體對(duì)應(yīng)關(guān)系如表1所示。在用免疫算法求解優(yōu)化問(wèn)題時(shí)，待求的問(wèn)題對(duì)應(yīng)為抗原，候選解即是抗體，抗體中的每一位稱為一個(gè)基因，應(yīng)用親和力來(lái)描述抗體和抗原之間的匹配程度，用排斥力來(lái)描述兩個(gè)抗體之間的相似程度。

2.1抗體表示

抗體采用自然數(shù)編碼。用0表示物資儲(chǔ)備中心，用1，2，…，8表示各節(jié)點(diǎn)。例如n=8時(shí)，抗體為01230456078，抗體編碼的表示可理解為：車輛從車場(chǎng)0出發(fā)，經(jīng)過(guò)：

子線路1：物資儲(chǔ)備中心0?邛節(jié)點(diǎn)1?邛節(jié)點(diǎn)2?邛節(jié)點(diǎn)3?邛物資儲(chǔ)備中心0；

子線路2：物資儲(chǔ)備中心0?邛節(jié)點(diǎn)4?邛節(jié)點(diǎn)5?邛節(jié)點(diǎn)6?邛物資儲(chǔ)備中心0；

子線路3：物資儲(chǔ)備中心0?邛節(jié)點(diǎn)7?邛節(jié)點(diǎn)8?邛物資儲(chǔ)備中心；

抗體通常是在解空間中用隨機(jī)的方法產(chǎn)生的，初始化抗體群規(guī)模即抗體群中抗體的個(gè)數(shù)，根據(jù)經(jīng)驗(yàn)，一般取網(wǎng)絡(luò)節(jié)點(diǎn)個(gè)數(shù)的2倍作為抗體群規(guī)模。

2.2親和力函數(shù)

本文采用目標(biāo)函數(shù)值作為免疫算法的抗原?？贵w與抗原之間的親和力反應(yīng)了抗體與抗原之間的匹配程度，也可以說(shuō)是通過(guò)親和力來(lái)描述抗體的優(yōu)化程度。本文取目標(biāo)函數(shù)的倒數(shù)，即：

式中，fv為目標(biāo)函數(shù)?？贵w越優(yōu)化，抗體v對(duì)應(yīng)解的目標(biāo)函數(shù)值就越小，它的親和力就越大；稱抗體群中親和最大的抗體為本帶抗體群的最優(yōu)抗體。

2.3排斥力函數(shù)

抗體A與B之間排斥力的計(jì)算函數(shù)定義為：

抗體A和B之間不相同的基因數(shù)量越大，它們的排斥力就越大。

2.4免疫算子

（1）對(duì)換算子

對(duì)于VRP問(wèn)題來(lái)說(shuō)，父代個(gè)體P1和P2分別采用浮點(diǎn)數(shù)編碼方案：

P1：012304560780 P2: 025604780130

采用基于路徑表示的順序交叉OX操作，兩代父代個(gè)體交叉時(shí)，通過(guò)選擇父代個(gè)體1的一部分，保存父代個(gè)體2中城市編碼的相對(duì)順序生成子個(gè)體。通過(guò)該方法生成子代個(gè)體：

O1：027804560130 O2：035604780120

（2）重組算子

對(duì)交叉后的群體，以某一概率改變某一個(gè)或者一些基因位上的基因值為其他的等位基因，變異本身是一種局部隨機(jī)搜索，與選擇算子結(jié)合在一起，保證了免疫算法的有效性，使免疫算法具有局部的隨機(jī)搜索能力，同時(shí)使得免疫算法保持種群的多樣性，以防止出現(xiàn)未成熟收斂。本文采用單點(diǎn)基因位換位算子和多對(duì)基因位換位算子的操作。

2.5濃度調(diào)節(jié)適應(yīng)度

濃度調(diào)節(jié)適應(yīng)度是在親和力的基礎(chǔ)上引入濃度調(diào)節(jié)機(jī)制，抗體B的濃度調(diào)節(jié)適應(yīng)度函數(shù)gB定義如下：gB

2.6優(yōu)質(zhì)串保留策略

2.7免疫算法的步驟

Step1：將式（1）中的目標(biāo)函數(shù)作為免疫算法的抗原；設(shè)置抗體群規(guī)模為N，一般取網(wǎng)絡(luò)節(jié)點(diǎn)個(gè)數(shù)的2倍作為抗體群規(guī)模；設(shè)置最大的進(jìn)化代數(shù)MAXGEN；

Step2：根據(jù)自然數(shù)編碼規(guī)則2.1所述在解空間隨機(jī)產(chǎn)生P個(gè)候選解作為初始抗體群，設(shè)置未進(jìn)化代數(shù)NGEN值為0，隨機(jī)選擇抗體群中一個(gè)抗體A作為當(dāng)前最優(yōu)抗體。并根據(jù)親和力函數(shù)（11）計(jì)算抗體A的親和力作為MAXAPP；

Step3：根據(jù)親和力函數(shù)計(jì)算過(guò)程計(jì)算抗體群中各抗體的親和力；

Step4：采用對(duì)換算子對(duì)本代抗體進(jìn)行基因交叉操作，采用重組算子對(duì)本代抗體進(jìn)行基因變異操作，經(jīng)過(guò)計(jì)算生成新抗體的親和力；

Step5：如果本代抗體群中最優(yōu)抗體的親和力CAPP>MAXPP，則將NGEN的值為0；MAXPP賦值為CAPP。保留本代抗體群的最優(yōu)抗體為當(dāng)前最優(yōu)抗體；否則NGEN遞增；

Step6：如果NGEN>MAXGEN，則轉(zhuǎn)步驟9；

Step7：根據(jù)排斥力函數(shù)計(jì)算本代抗體群中各抗體間的排斥力，根據(jù)公式計(jì)算本代抗體群中各抗體的濃度調(diào)節(jié)適應(yīng)度；

3算例分析

某地區(qū)發(fā)生自然災(zāi)害，所在地區(qū)的救災(zāi)物資儲(chǔ)備中心需要向8個(gè)受災(zāi)節(jié)點(diǎn)進(jìn)行救災(zāi)物資配送。該物資儲(chǔ)備中心只采用一種車型，其載重量為8噸，車速60公里/小時(shí)。車輛不能超載且必須在規(guī)定時(shí)間之前把物資送到受災(zāi)節(jié)點(diǎn)。各節(jié)點(diǎn)的物資需求量及物資儲(chǔ)備中心與各需求點(diǎn)之間、各需求點(diǎn)相互之間的距離表2、3所示（其中節(jié)點(diǎn)0表示物資儲(chǔ)備中心）。

得到最佳配送總距離為605km。對(duì)應(yīng)的最優(yōu)配送路徑為065408270310。

4結(jié)束語(yǔ)

文章采用了免疫算法，將其用于單邊時(shí)間窗的應(yīng)急物流配送的車輛調(diào)度中。該算法簡(jiǎn)單可行，提高了優(yōu)化算法的質(zhì)量和搜索效率。通過(guò)算例可以看到該算法的方便快捷，但是其全局收斂性和速度還需進(jìn)一步的理論證明和檢驗(yàn)，以保證此類算法的通用有效性。

參考文獻(xiàn)：

[1] 武亞麗，段富. 免疫算法在物流車輛優(yōu)化調(diào)度中的應(yīng)用[J]. 微計(jì)算機(jī)信息，2007(27):44-47.

[2] 陳杰. 基于遺傳算法的應(yīng)急物資運(yùn)輸調(diào)度[D]. 哈爾濱：哈爾濱工業(yè)大學(xué)，2006.

[3] 袁慶達(dá)，杜文，周再玲. 帶軟時(shí)間窗的混合車隊(duì)車輛路線問(wèn)題的模型和算法研究[J]. 西南交通大學(xué)學(xué)報(bào)，2001(4):26-29.

[4] 謝秉磊，毛科俊，安實(shí). 應(yīng)急物流運(yùn)輸中的車輛調(diào)度策略分析[J]. 西南大學(xué)學(xué)報(bào)，2007(3):42-46.

[5] 張斌. 物流配送車輛調(diào)度優(yōu)化研究[D]. 大連：大連海事大學(xué)，2007.

[6]Chun J S， Kim M K， Jung H K， etal. Shape opimitization of electho magnetic devices using immune algorithm[J]. IEEE Trans on Magnetics，1997(31):94-99.

[7]Jean-Yves Potvin， Tanguy Kervahut， Bruno-Laurent Garcia， Jean-Marc Rousseau. The Vehicle Rooting Problem with Time Windows[J]. Part I：Tabu Search， INFORMS Journal on Computing， 1996(20):56-61.