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

潘世舉

（軍事交通學(xué)院，天津　300161）

?

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

潘世舉

（軍事交通學(xué)院，天津300161）

應(yīng)急物流的特性決定了車輛調(diào)度優(yōu)化的重要性，它是保證應(yīng)急物流質(zhì)量和效益的關(guān)鍵因素。在對應(yīng)急物流車輛調(diào)度優(yōu)化進行問題描述和條件設(shè)定的基礎(chǔ)上，構(gòu)建了應(yīng)急物流車輛調(diào)度的多約束模型，同時對免疫算法及其相關(guān)問題進行了介紹，最后重點使用算例對免疫算法的應(yīng)用進行了實證研究，研究結(jié)果顯示免疫算法在應(yīng)急物流車輛調(diào)度優(yōu)化中具有一定的應(yīng)用價值。

應(yīng)急物流；車輛調(diào)度優(yōu)化；免疫算法

1　引言

應(yīng)急物流是指諸如公共衛(wèi)生、自然災(zāi)害、交通事故、社會安全等領(lǐng)域突發(fā)性事件發(fā)生后的救援物資配送和人員財產(chǎn)的轉(zhuǎn)移，應(yīng)急物流的突發(fā)性要求其必須具有快捷的響應(yīng)能力，這對于突發(fā)性事件的救援和降低生命財產(chǎn)損失具有十分重要的價值。車輛調(diào)度優(yōu)化問題是提高應(yīng)急物流敏捷性的重要手段，車輛調(diào)度優(yōu)化是指在已知貨物起始點的物流運輸網(wǎng)絡(luò)中，科學(xué)地組織和安排行車路徑，在滿足若干條件約束下實現(xiàn)既定的目標。應(yīng)急物流的車輛調(diào)度與普通物流的車輛調(diào)度之間有明顯的差異，前者對時間性和敏捷性極為重視，而對物流成本的考慮則居第二位。本文使用免疫算法研究應(yīng)急物流車輛調(diào)度優(yōu)化問題，在將時間作為第一約束要素的前提下，以最小的物流成本尋找到最優(yōu)的車輛行車路徑。

2　問題設(shè)定及模型構(gòu)建

2.1問題描述

設(shè)定本文所研究的應(yīng)急物流運輸方式為公路運輸，假設(shè)共有m受災(zāi)區(qū)域需要通過應(yīng)急物流來運輸配送救援物資，救援物資配送指揮中心的運輸車輛類型有K種，Qi為第i個受災(zāi)區(qū)域所需要的救援物資需求量，某種類型的車輛在某個受災(zāi)區(qū)域的貨物卸載時間為utik，運輸車輛最遲到達受災(zāi)區(qū)域的時間為Ktik，救援物資存儲中心與受災(zāi)區(qū)域的運輸費用為Cijk，運輸時間為tijk，其中i，j=0，1，2，3...，m，0為救援物資儲備中心編號，1，2，…，m分別為受災(zāi)區(qū)域編號。救援物資配送車輛的單車裝載容量為qk，不允許出現(xiàn)超載的情況，且必須在規(guī)定的最遲時間之前將救援物資運送到受災(zāi)區(qū)域。于是問題轉(zhuǎn)化為在上述設(shè)定的條件下，如何安排和組織救援物資運輸車輛并規(guī)定每輛運輸車輛的路線，使得總的運輸距離最短，也就是總的運輸物流成本最小。

2.2條件設(shè)定

出于構(gòu)建模型的需要，將上述復(fù)雜的問題進行簡化，做出如下的條件設(shè)定：救援物資存儲中心與各受災(zāi)區(qū)域以及各個受災(zāi)區(qū)域之間的運輸距離為已知量；救援物資可以提前送達受災(zāi)區(qū)域，但不能遲于最晚規(guī)定的時間；必須滿足所有受災(zāi)區(qū)域的救援物資數(shù)量和運輸時間，并且單個受災(zāi)區(qū)域的救援物資需求量小于運輸車輛的最大載容量；受災(zāi)區(qū)域的路況和交通條件用路況系數(shù)來表示，有正常和高峰兩種狀態(tài)。

2.3模型構(gòu)建

令g（v，e）為一個無向圖，式中v=｛vi|i=0，1，2，...，m｝為點集合，e=｛（vi，vj|vi，vj∈v，i≠j｝為邊集合，救援物資存儲中心為v0，它是運輸車輛的始點和終點，運輸車隊共有K種類型的運輸車輛，每種類型的運輸車輛其載重量為qk（k∈K），vi（i≠0）表示受災(zāi)地區(qū)，每個受災(zāi)地區(qū)對救援物資都有非負的需求量Qi，同一個運輸路線上點i與點j相鄰且位于其前面，救援物資運輸車輛到達點i的時間是Atik，卸貨時間為utik，從點i行駛到點j需要的時間為tijk，到達點j的時間為Atjk，最遲到達時間為Ktik，那么就有Atjk=Atik+utik+tijk，弧（vi，vj）表示點i與點j之間的距離dij，距離矩陣D=（dij）滿足三角不等式。根據(jù)以上設(shè)定構(gòu)建如下模型：

目標函數(shù)（1）表示總的救援物資配送費用最小；約束（2）表示k類型輛車h服務(wù)受災(zāi)區(qū)域點i時的援助物資需求量不能超過其最大載重量；約束（3）表示每個受災(zāi)區(qū)域點只配送1次物資；約束（4）、（5）表示任何一個受災(zāi)區(qū)域點只接受1輛運輸配送車的服務(wù)；約束（6）表示點i、點j為k類型的運輸車輛所服務(wù)，并且點i優(yōu)于點j優(yōu)先得到服務(wù)；約束（7）表示派出的救援物資配送車輛數(shù)量等于返回的車輛數(shù)量；約束（8）表示救援物資運送到需求點的時間必須滿足最遲規(guī)定的時間；約束（9）表示k類型的車經(jīng)過點i、點j的時間；約束（10）表示k類型的車從點i行駛到點j的費用。

3　免疫算法

免疫算法作為一種優(yōu)化組合算法，借鑒和繼承了免疫系統(tǒng)的記憶機制、學(xué)習(xí)性和適應(yīng)性，在應(yīng)用免疫算法解決優(yōu)化組合問題時，其步驟與免疫系統(tǒng)都有著對應(yīng)的關(guān)系，諸如抗原對應(yīng)需要求解的問題，抗體對應(yīng)候選解，抗體和抗原之間的匹配度使用親和力來描述，兩個抗體之間的相似度用排斥力來描述。

3.1抗體

使用自然數(shù)對抗體進行編碼。救援物資存儲中心用0表示，各個受災(zāi)區(qū)域節(jié)點用1，2，3，…，8表示。當(dāng)m= 8時，抗體為012345678，其可以理解為：救援物資運輸車輛從存儲中心0出發(fā)，經(jīng)過下面的子線路再返回到救援物資儲備中心：

（1）救援物資儲備中心0—受災(zāi)區(qū)域節(jié)點1—受災(zāi)區(qū)域節(jié)點2—受災(zāi)區(qū)域節(jié)點3—救援物資儲備中心0；

（2）救援物資儲備中心0—受災(zāi)區(qū)域節(jié)點4—受災(zāi)區(qū)域節(jié)點5—受災(zāi)區(qū)域節(jié)點6—救援物資儲備中心0；

（3）救援物資儲備中心0—受災(zāi)區(qū)域節(jié)點7—受災(zāi)區(qū)域節(jié)點8—救援物資儲備中心0。

通常情況下在解空間集合中用隨機的方法生成抗體，抗體群中抗體的個數(shù)一般為網(wǎng)絡(luò)節(jié)點個數(shù)的2倍。

3.2親和力

免疫算法的抗原使用目標函數(shù)值，其與抗體之間的匹配度即為抗體抗原之間的親和力，也就是說抗體的優(yōu)化程度使用親和力來進行描述，取目標函數(shù)的倒數(shù)，即：

式中 f（v）為目標函數(shù)，抗體的優(yōu)化程度與對應(yīng)解的目標函數(shù)值大小成反比例關(guān)系，優(yōu)化程度越高說明其親和力越大，親和力最大的抗體為最優(yōu)抗體。

3.3排斥力

兩個抗體之間的排斥力與不相同基因的數(shù)量成正比。

3.4免疫算子

對于車輛調(diào)度優(yōu)化問題來說，父代個體使用浮點數(shù)編碼方案，即：

使用順序交叉方法生成子代個體如下：

3.5優(yōu)質(zhì)串保留

如果存在多個抗體、抗原之間較大的親和力且抗體中包含的基因串相同，那么這個基因串就為優(yōu)質(zhì)串。優(yōu)質(zhì)串保留是指在優(yōu)質(zhì)串檢測中對下一代的抗體群中的新抗體以一定的概率p0（0＜p0＜1）使用優(yōu)質(zhì)串代替原來的基因串。

3.6免疫算法的應(yīng)用步驟

（1）將目標函數(shù)（1）作為抗原，令抗體群規(guī)模為N，抗體群規(guī)模大小一般為網(wǎng)絡(luò)節(jié)點數(shù)量的2倍，并設(shè)定最大的進化代數(shù)為MaxGEN。

（2）在解空間中利用隨機的方法生成P個候選解作為初始抗體群，未進化時的代數(shù)為NGEN=0，在抗體群中隨機選擇一個抗體作為最優(yōu)抗體，并記為A，其親和力為MaxAPP。

（3）計算抗體群中每個抗體的親和力。

（4）對本代抗體進行基因交叉操作和基因變異操作，然后計算獲得新抗體的親和力。

（5）本代抗體群中最優(yōu)抗體的親和力記為CAPP，如果其大于MaxAPP，那么NGEN=0，這時MaxAPP的值為CAPP，并將其視為當(dāng)前最優(yōu)抗體，否則對NGEN進行遞增操作。

（6）如果NGEN大于MaxGEN，就轉(zhuǎn)到步驟（9）。

（7）計算本代抗體群中各個抗體之間的排斥力大小，并根據(jù)相關(guān)公式計算抗體群中各抗體之間的濃度調(diào)節(jié)適應(yīng)度。

（8）下一代抗體群為濃度調(diào)節(jié)適應(yīng)度最高的P個抗體，然后再對這P個抗體以一定的概率進行保留操作，回到步驟（4）。

（9）回到當(dāng)前最優(yōu)抗體并將其對應(yīng)的應(yīng)急物流車輛調(diào)度優(yōu)化方案作為為題的解，算法結(jié)束。

4　算例實證

某地區(qū)發(fā)生了突發(fā)性自然災(zāi)害，并向救援物資儲備中心發(fā)出了救援請求。救災(zāi)指揮中心需要向該地區(qū)8個受災(zāi)節(jié)點進行救援物資配送。經(jīng)過分析決定使用一種類型的車輛進行物資運載，最大載重量為8t，每小時行車速度為60km，物資運載車輛必須保證在不超載的前提下將救援物資在規(guī)定的時間內(nèi)送達受災(zāi)節(jié)點。表1、表2給出了各受災(zāi)節(jié)點的救援物資需求數(shù)量、救援物資儲備中心與各受災(zāi)節(jié)點以及各受災(zāi)節(jié)點之間的距離，其中救援物資儲備中心用數(shù)字0表示。

表1　各受災(zāi)節(jié)點數(shù)據(jù)

表2　救援物資儲備中心與各受災(zāi)節(jié)點及各受災(zāi)節(jié)點之間的距離

根據(jù)免疫算法的相關(guān)求解公式，本實例中免疫算法個體種群規(guī)模為20，編碼長度為12，交叉概率為0.6，變異概率為0.3，濃度閾值為0.25，提取概率為0.3，排斥力為0.01，注射概率為0.4，不進化代數(shù)的最大值為20，對免疫算法進行50次循環(huán)計算，得到的計算結(jié)果見表3。

表3　算例的免疫算法計算結(jié)果

因此該算例的救援物資最佳配送距離為600，與之對應(yīng)的車輛調(diào)度路徑為065408207310。

5　總結(jié)

本文使用免疫算法研究了應(yīng)急物流車輛調(diào)度優(yōu)化問題，經(jīng)過實例分析證明，該算法具有可行性，并且提高了優(yōu)化質(zhì)量和效率，因此在應(yīng)急物流車輛調(diào)度中具有一定的應(yīng)用價值。

［1］高本河，伍慧飛.多資源調(diào)度中應(yīng)急物流出救點最少問題的優(yōu)化［J］.物流技術(shù)，2009，（1）.

［2］張裕華，潘郁.基于蟻群算法的應(yīng)急物流配送車輛調(diào)度研究［J］.物流科技，2009，（5）.

［3］王海軍，楊麗娟，萬鈺然.模擬退火算法在應(yīng)急物流車輛調(diào)度中的應(yīng)用［J］.物流工程與管理，2009，（6）.

［4］陳明華，李迎秋，羅耀琪.應(yīng)急物流車輛調(diào)配問題的研究［J］.計算機工程與應(yīng)用，2009，（24）.

［5］韓景倜，池為疊，韓小妹.基于應(yīng)急物流體的應(yīng)急救援物資調(diào)度模型［J］.系統(tǒng)仿真學(xué)報，2009，（18）.

［6］英升賀，李毅鑫.動態(tài)規(guī)劃和整數(shù)規(guī)劃在應(yīng)急物流物資配送優(yōu)化中的應(yīng)用研究［J］.物流技術(shù)，2009，（8）.

Application of Immunity Algorithm in Optimizing Emergency Logistics Vehicle Dispatching

Pan Shiju
（Military Transportation Academy， Tianjin 300161， China）

The property of emergency logistics predestines the significance of vehicle dispatching optimization which plays a key role inensuring the quality and benefit of the emergency logistics process. In this paper， after describing the dispatching optimization problem of theemergency logistics vehicles and setting its premises， we built the corresponding multi- constraint model， at the meantime， introduced theimmunity algorithm and the related issues， and at the end， in a numerical example， studied empirically the application of the immunityalgorithm， showing that it was of certain application value in optimizing the dispatching of the emergency logistics vehicles.

emergency logistics； vehicle dispatching optimization； immunity algorithm

F224；F252.14

A

1005-152X（2016）07-0080-03

10.3969/j.issn.1005-152X.2016.07.018

2016-06-17

潘世舉，男，河南平頂山人，軍事交通學(xué)院學(xué)生，研究方向：軍用車輛。