摘要：在應(yīng)急物流中，合理的車輛調(diào)度優(yōu)化可以極大地節(jié)約物流成本。本文結(jié)合實(shí)際情況，對應(yīng)急物流車輛調(diào)度問題的特點(diǎn)進(jìn)行了分析，構(gòu)建了一般性非滿載應(yīng)急物流車輛調(diào)度優(yōu)化的數(shù)學(xué)模型，并采用智能優(yōu)化算法中的遺傳算法該問題進(jìn)行求解。仿真結(jié)果表明，該算法是可行和有效的。

關(guān)鍵詞：應(yīng)急物流；車輛配送；遺傳算法

1 引言

近年來，自然災(zāi)害和人為災(zāi)害頻發(fā)，造成了巨大的人員傷亡和財產(chǎn)損失。如2003年的SARS造成經(jīng)濟(jì)損失176億美元，2008年的汶川大地震8451億人民幣，2011年的日本海嘯和核污染事件的經(jīng)濟(jì)損失更達(dá)到了1000億美元以上。在這些損失中，由于應(yīng)急物流造成的損失約占總損失的15%至20%。[1]

應(yīng)急物流是以提供應(yīng)急物資為目的，以追求時間效益最大化和災(zāi)害損失最小化為目標(biāo)的特殊物流活動，具有突發(fā)性、非常規(guī)性和不確定性、時間約束緊迫性等特點(diǎn)。[2]目前國內(nèi)外對應(yīng)急物流系統(tǒng)的研究主要有應(yīng)急車輛書的配置[3]、應(yīng)急資源調(diào)配[4]和應(yīng)急配送車輛調(diào)度 [5]。

針對應(yīng)急物流車輛調(diào)配問題的研究，國外起步于上世紀(jì)90年代。而在我國從2006年底，經(jīng)國資委、民政部批準(zhǔn)全國第一個從事應(yīng)急物流的專業(yè)組織——中國物流與采購聯(lián)合會應(yīng)急物流專業(yè)委員會成立之后，關(guān)于應(yīng)急物流中的車輛調(diào)配問題的研究逐步展開。我國幅員遼闊，每年突發(fā)災(zāi)害都較多，目前系統(tǒng)地、定量地對我國災(zāi)害救助應(yīng)急物流配送車輛調(diào)度優(yōu)化模型基本沒有進(jìn)行研究，對突 發(fā)性事件的決策還存在著應(yīng)對遲緩、缺少科學(xué)依據(jù)等問題。因此，本文所研究的問題具有重要的現(xiàn)實(shí)意義。

2 模型描述

使用圖G(V，E)描述物資儲備中心和受災(zāi)點(diǎn)的交通情況，其中V為所有的節(jié)點(diǎn)的集合（包括物資儲備中心節(jié)點(diǎn)、受災(zāi)點(diǎn)和其他相關(guān)節(jié)點(diǎn)），V0∈V為物資儲備中心；E為圖所有邊的集合，eij∈E表示節(jié)點(diǎn)Vi，Vj之間的邊。G為無向圖，即邊eij是無方向的。有n個受災(zāi)地區(qū)向救災(zāi)指揮中心請求救災(zāi)物資的配送，第i個受災(zāi)節(jié)點(diǎn)對于救災(zāi)物資的需求量為gi，卸貨時間為UTi，最遲允許車輛到達(dá)時間為LTi，物資儲備中心與受災(zāi)節(jié)點(diǎn)、受災(zāi)節(jié)點(diǎn)之間的廣義運(yùn)輸（距離）費(fèi)用為cij，運(yùn)輸時間為tij（i，j=0，1，2，…，n，物資儲備中心編號為0，受災(zāi)節(jié)點(diǎn)編號為1，2，…，n），配送卡車單車裝載容量為q（q>gi，i=1，2，…，n）。

把物資儲備中心和受災(zāi)節(jié)點(diǎn)統(tǒng)一看作是運(yùn)輸網(wǎng)絡(luò)中的節(jié)點(diǎn)。設(shè)在同一線路上點(diǎn)h是點(diǎn)i前面的相鄰點(diǎn)，車輛到達(dá)點(diǎn)h的時間為RTh，到達(dá)點(diǎn)i的時間為RTi，則有：

模型中，ctj表示為從點(diǎn)i到點(diǎn)j的運(yùn)輸成本，它的定義可以是距離、費(fèi)用、時間等，一般根據(jù)實(shí)際情況確定，可同時考慮車輛數(shù)和運(yùn)行費(fèi)用，如下確定：

其中，c1為相對于運(yùn)行時間的費(fèi)用系數(shù)；c0為車輛的固定費(fèi)用，即增加一輛車的邊際費(fèi)用。一般認(rèn)為，派出一輛車的固定費(fèi)用遠(yuǎn)遠(yuǎn)高于車輛行駛費(fèi)用，因此該模型是在極小化車輛數(shù)的前提下，在極小化運(yùn)行費(fèi)用。減小c0的值將會使使用的車輛數(shù)增多，而線路長度縮短。若令C1=0，C0>0，則模型目標(biāo)是使用的車輛數(shù)最少。

在數(shù)學(xué)模型中，目標(biāo)函數(shù)(2)表示總運(yùn)輸里程（費(fèi)用）最低，約束條件(3)表示任一臺單車裝載量不允許超過車輛容量約束，約束條件(4)救災(zāi)物資送到各個需求節(jié)點(diǎn)的時間必須在時間窗范圍內(nèi)，約束條件(5)表示任何一個受災(zāi)地區(qū)需求節(jié)點(diǎn)只有1臺車?？啃敦?，約束條件(6)表示車輛k只駛?cè)敕峙浣o其運(yùn)輸任務(wù)的客戶，約束條件(7)表示車輛k只駛出分配給其運(yùn)輸任務(wù)的需求節(jié)點(diǎn)，約束條件(8)表示車輛k的線路必須是連通的。

3 應(yīng)用遺傳算法對問題求解

由于車輛調(diào)配問題已經(jīng)被證明為NP-H問題[6]，本文將采用智能優(yōu)化算法中的遺傳算法，對問題進(jìn)行求解。對于遺傳算法的描述如下。

3.1 解的編碼和初始解構(gòu)造

3.1.1 編碼原則

本文中染色體采用簡單直觀的自然數(shù)編碼（序數(shù)編碼），用0表示物資儲備中心，用1，2，…，n表示各節(jié)點(diǎn)。例如：染色體021035406780表示行駛線路：

子線路1：物資儲備中心0→節(jié)點(diǎn)2→節(jié)點(diǎn)1→物資儲備中心0

子線路2：物資儲備中心0→節(jié)點(diǎn)3→節(jié)點(diǎn)5→節(jié)點(diǎn)4→物資儲備中心0

子線路3：物資儲備中心0→節(jié)點(diǎn)6→節(jié)點(diǎn)7→節(jié)點(diǎn)8→物資儲備中心0

染色體中的每個子路線稱為一個基因，則示例染色體中包含了3個基因，分別是，0210，03540和06780；每個基因以0開始，以0結(jié)束，表示子路線從物資中心出發(fā)，回到物資中心。

在本文的編碼方式中，基因中的每個子基因位是有序的，即若表示子線路的基因中相鄰兩位互換位置，會使目標(biāo)函數(shù)值改變；而子線路之間是無序的，若表示子線路的基因互換位置不會改變目標(biāo)函數(shù)值。

3.1.2 初始解構(gòu)造算法

基于3.1.1節(jié)中解的編碼方式，采用如下算法構(gòu)造遺傳算法的初始解。

步驟1：判斷是否所有受災(zāi)節(jié)點(diǎn)都訪問到，是則轉(zhuǎn)步驟:3；

步驟2：隨機(jī)選擇一個受災(zāi)節(jié)點(diǎn)添加到染色體中，轉(zhuǎn)步驟1；

步驟3：判斷可用車輛數(shù)m的值是否大于0，如果是，則轉(zhuǎn)步驟4；否則轉(zhuǎn)步驟5；

步驟4：隨機(jī)選擇染色體中的一個位置插入0，m--，轉(zhuǎn)步驟3；

步驟5：則染色體構(gòu)造完畢。

采用上述的構(gòu)造方法，可能得到連續(xù)的0，則表明該方案中有空閑的車輛。

3.2 初始種群的構(gòu)造

初始抗體群是按照上面3.1節(jié)中編碼原則隨機(jī)生成的?？贵w群的規(guī)模 定義為抗體群中抗體的個數(shù)，它是影響算法性能的一個重要的因素。按經(jīng)驗(yàn)N一般定義在20-100之間，同時取網(wǎng)絡(luò)中節(jié)點(diǎn)個數(shù)的2倍左右作為抗體群規(guī)模，如網(wǎng)絡(luò)中節(jié)點(diǎn)個數(shù)為V時，抗體群的規(guī)模為Vx 2。按照上述的編碼方式，隨機(jī)產(chǎn)生N個編碼長度為l的抗體，l=任務(wù)節(jié)點(diǎn)數(shù)+車輛數(shù)+1。

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

適應(yīng)度函數(shù)用來描述解的優(yōu)化程度，適應(yīng)度函數(shù)的值越小，解就越優(yōu)化。本文的適應(yīng)度函數(shù)公式如下：

上式的第二項(xiàng)和第三項(xiàng)表示對違反車輛載重約束和時間約束的解給予懲罰，M取比較大的正數(shù)（如果允許晚到即軟時間窗，可以把M定義為一個合適的值）。

3.4遺傳算子

3.4.1 交叉算子

對換算子采用單點(diǎn)交叉，交叉后可能出現(xiàn)某一個或者幾個城市重復(fù)通過，而某些城市卻沒有走到的情況，即交叉后的染色體不合法。對于不合法的新染色體，采用3.1.2節(jié)中的算法重新生成新的染色體替換。

3.4.2 變異算子

本文采用單點(diǎn)基因變異的變異算子，即隨機(jī)選取染色體中的一個基因（對應(yīng)一條子路線），將子路線中的節(jié)點(diǎn)重新排序得到新的染色體。則對于染色體021035406780，選取第2個基因位進(jìn)行變異后得到的一個可能的結(jié)果是021054306780。

3.4.3 選擇算子

本文中將染色體的適應(yīng)度值取倒數(shù)后，采用輪盤賭法對種群中的染色體執(zhí)行選擇操作，以使得適應(yīng)度小的染色體對應(yīng)較小的選擇概率。

3.5 算法停止條件

設(shè)置最大不進(jìn)化代數(shù) ，如果每代染色體的最小適應(yīng)度經(jīng)過 代仍沒有進(jìn)化，則算法停止。

3.6 對算法的改進(jìn)

算法中使用了精英保留策略，設(shè)置安全閥，保存每代的最優(yōu)染色體，使其不經(jīng)過交叉和變異直接進(jìn)入下一代。

4 仿真研究與討論

作者編寫了遺傳算法的程序，按照上述步驟對算例進(jìn)行了求解，編程環(huán)境： Windows XP + Visual Studio；計算機(jī)硬件：CPU主頻2.4G，內(nèi)存2G。

遺傳算法的參數(shù)為：染色體數(shù)量N=20；編碼長度l=12；交叉概率pc=0.6；變異概率pm=0.15。程序執(zhí)行結(jié)果隨最大不進(jìn)化代數(shù) 變化情況如表1所示（表1中結(jié)果為程序執(zhí)行50次的平均值）。

從以上結(jié)果可以看出，①遺傳算法可以從大量的不可行解中有效地找到可行解；②遺傳算法搜索到最優(yōu)解的概率較大，最大不進(jìn)化代數(shù)設(shè)置越大，算法的解與最優(yōu)解越接近；③遺傳算法的平均運(yùn)算結(jié)果較優(yōu)，平均結(jié)果比最優(yōu)解大5.3%，并且當(dāng)最大不進(jìn)化代數(shù)達(dá)到100時，算法的平均結(jié)果僅比最優(yōu)解大0.3%。

5 結(jié)論

我國屬于自然災(zāi)害頻發(fā)的國家，每年為救災(zāi)所進(jìn)行的物流活動花費(fèi)了大量的社會財富，使用合理的配送算法可用有效地節(jié)約物流成本，并且能夠保障物資的即時送達(dá)。

本文主要所研究的是應(yīng)急物流過程的最后一個階段——應(yīng)急物資配送的車輛調(diào)度優(yōu)化問題。本文以應(yīng)急物流配送環(huán)境下的應(yīng)急物資配送為運(yùn)用背景，在對車輛調(diào)度算法進(jìn)行研究的基礎(chǔ)上，結(jié)合應(yīng)急物資配送的實(shí)際特點(diǎn)，建立了數(shù)學(xué)模型，并在此基礎(chǔ)上運(yùn)用遺傳算法進(jìn)行求解，結(jié)果證明遺傳算法應(yīng)用于該問題有較好的收斂性和全局搜索性。

6 下一步研究方向

本文的應(yīng)急物流車輛調(diào)配算法是基于一個物資中心的情況進(jìn)行的，并且物資運(yùn)輸?shù)姆绞揭彩菃我坏?。在較大的災(zāi)害中，對于多個物資中心、運(yùn)用多種運(yùn)輸方式進(jìn)行全局的統(tǒng)籌管理，將會更加有助于物資的即時送達(dá)和總體成本的控制。

因此，在后續(xù)的工作中，將把研究重點(diǎn)放在對多中心點(diǎn)的物資調(diào)配問題，以及多交通工具的統(tǒng)籌調(diào)配問題的研究上。