應急物流配送車輛調度的遺傳算法求解

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

關鍵詞：應急物流；車輛配送；遺傳算法

1 引言

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

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

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

2 模型描述

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

把物資儲備中心和受災節(jié)點統一看作是運輸網絡中的節(jié)點。設在同一線路上點h是點i前面的相鄰點，車輛到達點h的時間為RTh，到達點i的時間為RTi，則有：

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

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

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

3 應用遺傳算法對問題求解

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

3.1 解的編碼和初始解構造

3.1.1 編碼原則

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

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

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

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

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

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

3.1.2 初始解構造算法

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

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

步驟2：隨機選擇一個受災節(jié)點添加到染色體中，轉步驟1；

步驟3：判斷可用車輛數m的值是否大于0，如果是，則轉步驟4；否則轉步驟5；

步驟4：隨機選擇染色體中的一個位置插入0，m--，轉步驟3；

步驟5：則染色體構造完畢。

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

3.2 初始種群的構造

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

3.3 適應度函數

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

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

3.4遺傳算子

3.4.1 交叉算子

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

3.4.2 變異算子

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

3.4.3 選擇算子

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

3.5 算法停止條件

設置最大不進化代數 ，如果每代染色體的最小適應度經過 代仍沒有進化，則算法停止。

3.6 對算法的改進

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

4 仿真研究與討論

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

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

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

5 結論

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

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

6 下一步研究方向

本文的應急物流車輛調配算法是基于一個物資中心的情況進行的，并且物資運輸的方式也是單一的。在較大的災害中，對于多個物資中心、運用多種運輸方式進行全局的統籌管理，將會更加有助于物資的即時送達和總體成本的控制。

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