胡飛虎，田朝暉，李 威，韓 鑫

（西安交通大學(xué)電氣工程學(xué)院工業(yè)自動化系，西安 710049）

基于遺傳算法的應(yīng)急物資分層調(diào)度研究

胡飛虎，田朝暉，李 威，韓 鑫

（西安交通大學(xué)電氣工程學(xué)院工業(yè)自動化系，西安 710049）

針對多車型、多物資特征的應(yīng)急物資調(diào)度問題，設(shè)計分層調(diào)度方案，同時給出由兩層物資調(diào)度系統(tǒng)組成的調(diào)度算例，并將該算例轉(zhuǎn)化為2個相關(guān)的單層物資調(diào)度問題。以最小化系統(tǒng)調(diào)度任務(wù)完成時間為目標(biāo)函數(shù)，利用遺傳算法對一級和二級調(diào)度方案進(jìn)行求解，得出系統(tǒng)中每種車型依次將何種貨物從何地運往何處的具體方案。通過車輛各自運輸任務(wù)的運貨量計算和倉庫點物資的實時統(tǒng)計結(jié)果表明，該分層調(diào)度方案符合各倉庫出貨量不超過現(xiàn)存量且各災(zāi)害點物資需求得到滿足的供求條件，求解步驟簡單且運行速度快。

應(yīng)急物資調(diào)度；分層調(diào)度；車輛調(diào)度；遺傳算法；目標(biāo)函數(shù)

1 概述

啟發(fā)式優(yōu)化算法［1］被廣泛用于解決應(yīng)急物資配送的車輛調(diào)度［2-4］問題。在物資調(diào)度問題的求解方面：文獻(xiàn)［5］應(yīng)用蟻群算法對調(diào)度問題進(jìn)行優(yōu)化，將原始物資分配分為2個階段，車輛路線分配和多種物資分配，從而解決應(yīng)急物資運輸問題。文獻(xiàn)［6］在多種商品、多配送情況下，以系統(tǒng)總成本最小為目標(biāo)，建立兩階段混合整數(shù)規(guī)劃模型解決物資調(diào)度問題。文獻(xiàn)［7］提出一種混合模糊聚類算法，得出關(guān)聯(lián)兩路網(wǎng)下物資調(diào)度問題的求解方案。文獻(xiàn)［8］給出供應(yīng)與需求不平衡情況下兩階段的多種運輸方式、多物資運輸模型。文獻(xiàn)［9］提出兩階段隨機(jī)規(guī)劃方法解決調(diào)度問題。文獻(xiàn)［10］針對應(yīng)急物資調(diào)度問題，建立情景響應(yīng)式兩階段隨機(jī)規(guī)劃模型。文獻(xiàn)［11］研究了供應(yīng)鏈中傳統(tǒng)的車輛路徑問題以及多

物資網(wǎng)絡(luò)流問題，并且在交通工具、物資變化等情況下，提出解決動態(tài)調(diào)度問題的算法。分層是指路網(wǎng)調(diào)度具有層次，如省級路網(wǎng)、地方路網(wǎng)以及各種路網(wǎng)上適用的運輸工具，本文提出對此類調(diào)度問題進(jìn)行求解的思路。每層的需求點為下層的倉庫點，各層的運輸工具僅需完成各自所在層的倉庫到需求點的物資調(diào)度任務(wù)，這樣即可依次對各層調(diào)度問題進(jìn)行獨立求解，從而簡化問題，便于求解計算。物資兩層調(diào)度問題是此問題的典型特例，在實際問題中由二級調(diào)度（市縣級地方倉庫至災(zāi)害點）和一級調(diào)度（國家、省級倉庫至市縣級地方倉庫）組合成的兩層調(diào)度問題。因此，本文提出物資兩層調(diào)度問題的數(shù)學(xué)模型，以任務(wù)耗時最短為目標(biāo)，利用遺傳算法［12-14］和分層求解方法給出最優(yōu)調(diào)度方案。

2 兩層應(yīng)急物資調(diào)度問題的數(shù)學(xué)模型

已知各倉庫點的物資儲量和災(zāi)害點的物資需求量。

（1）假設(shè)條件

1）各層調(diào)度系統(tǒng)的運輸工具只負(fù)責(zé)完成各自所在層的物資調(diào)度任務(wù)。

2）一級倉庫點和二級倉庫點各物資的總存儲量一定能滿足災(zāi)害點對各物資的總需求量，且二級倉庫有一定儲量，保證不會中途空倉，導(dǎo)致二級車輛在該二級倉庫等待。

3）不考慮各運輸工具的裝卸貨時間。

4）各運輸工具的初始停放地點可為倉庫點，也可為災(zāi)害點，且在執(zhí)行完某單次任務(wù)后不必回到初始出發(fā)地點。

5）各運輸工具均滿載某單一物資正常運行，不考慮物資的混合裝載且一旦開始執(zhí)行某次運輸任務(wù)，不能中途退出。

（2）模型參數(shù)

W：應(yīng)急物資集合，即W=｛w1，w2，…，wP｝。

B：一級倉庫點集合，即B=｛b1，b2，…，bm｝。

C：二級倉庫點集合，即C=｛c1，c2，…，ca｝。

E：災(zāi)害點集合，即E=｛e1，e2，…，eq｝。

BW：一級物資儲備中心（一級倉庫）物資信息集合，即BW=｛bw1，bw2，…，bwm｝。

CW：二級物資儲備中心（二級倉庫）物資信息集合，即CW=｛cw1，cw2，…，cwn｝。

EW：災(zāi)害救援中心（災(zāi)害點）物資信息集合，即EW=｛ew1，ew2，…，ewa｝，ewk（k=1，2，…，a）表示某個災(zāi)害點的物資信息，包括需要的物資類型（wf）（f=1，2，…，P）及相應(yīng)的需求量（γkf），即 ewk=｛（w1，γk1），（w2，γk2），…，（wP，γkP）｝。

R：一級運輸工具信息集合，即 R=｛r1，r2，…，rg｝。rk（k=1，2，…，g）表示一級運輸工具信息，包含載貨量（dk）、速度（sk）、數(shù)量信息（nk），即 rk=｛dk，sk，nk｝。N=｛n1，n2，…，ng｝，nk（k=1，2，…，g）表示一級某種類型的運輸工具的數(shù)量。

V：二級運輸工具信息集合，即 V=｛ν1，ν2，…，νh｝，νk（h=1，2，…，y）表示二級運輸工具信息，包含載貨量（dk）、速度（sk）、數(shù)量信息（nk），即 νk=｛dk，sk，nk｝，N=｛n1，n2，…，nh｝，nk（k=1，2，…，h）表示二級序列某種類型的運輸工具的數(shù)量。

q為一級倉庫點和二級倉庫點間路徑距離矩陣：

l為二級倉庫點和災(zāi)害點之間的路徑距離矩陣：

μ：一級車輛的一次完整運載任務(wù)，即 μ=（bi，wf，cj）（i=1，2，…，m；f=1，2，…，P；j=1，2，…，n）。一級車輛的一次完整運載任務(wù)包括出發(fā)一級倉庫點、運載的物資種類、抵達(dá)二級倉庫點。

τ：二級車輛一次完整的運載任務(wù)，即 τ=（ci，wf，ej）（i=1，2，…，n；f=1，2，…，P；j=1，2，…，a）。二級車輛一次完整的運載任務(wù)為τ，它包括出發(fā)二級倉庫點、運載物資種類、抵達(dá)災(zāi)害點。

Φ：一級序列完整的調(diào)度方案信息，即 Φ=｛φ1，φ2，…，φP｝，其中，φg（g=1，2，…，P）表示一級序列中第g個運輸工具的調(diào)度方案信息，包括一系列運載任務(wù)序列和該運輸工具的信息，φg=｛μ1，μ2，…，μχ；rk｝，即第g個運輸工具的調(diào)度方案信息為 φg，車輛信息為rk，有χ次運載任務(wù)序列。

Ω：二級調(diào)度方案，即 Ω=｛ω1，ω2，…，ωq｝，其中，ωg（h=1，2，…，q）表示二級序列中第 h個運輸工具的調(diào)度方案信息，包括一系列運載任務(wù)序列和該運輸工具的信息；ωh=｛τ1，τ2，…，τy；νf｝，即第 h個運輸工具的調(diào)度方案信息為 ωh，車輛信息為 νf，有y次運載任務(wù)序列。

T1：一級車輛調(diào)度時間集合，即 T1=｛t1φ1，

t1φ2，…，tφP｝。其中，t1φg（g=1，2…，P）表示第 g個運輸工具的調(diào)度完成時間。整個調(diào)度任務(wù)完成時間T1s=max（t1φg）。

T2：二級車輛調(diào)度時間集合，即 T2=｛t2ω1，t2ω2，…，t2ωq｝。其中，t2ωh（h=1，2，…，q）表示第 h個運輸工具的調(diào)度完成時間。整個調(diào)度任務(wù)完成時間T2s=max（t2ωh）。

目標(biāo)函數(shù)：m in（max｛T1s，T2s｝）。

3 兩層調(diào)度算例

一級倉庫點分別為 b1，二級倉庫點分別為 c1，c2，c3，災(zāi)害點分別為e1，e2，e3，e4，e5，3種應(yīng)急物資w1，w2，w3，即分別對應(yīng)為藥品、食品、生活用品。一級序列有2種車型，分別為大、小貨車，車輛編號分別為1～6，7～8，運載量分別為10 t和5 t，滿載速度分別為80 km/h和85 km/h。二級系統(tǒng)有2種車型，分別為大、小貨車，車輛編號分別為1～4，5～14，運載量分別為10 t和5 t，滿載速度分別為60 km/h和65 km/h。公路運輸路徑關(guān)系如圖1所示，一級高速公路運輸路徑距離（高速公路）如表1所示，二級高速公路運輸路徑距離（普通公路）如表2所示。3種應(yīng)急物資在各倉庫點中的庫存量和在各災(zāi)害點中的需求量如表3所示，其中，“∞”表示兩點間的道路不通。求解目標(biāo)：以調(diào)度完成時間最短為目標(biāo)，求解調(diào)度方案。

圖1 各倉庫、災(zāi)害點的運輸路徑關(guān)系

表1 一級各倉庫、二級各倉庫的運輸路徑距離 km

表2 二級各倉庫、災(zāi)害點的運輸路徑距離 km

表3 各倉庫、災(zāi)害點的存儲量與需求量

4 應(yīng)用遺傳算法的算例求解過程

4.1 參數(shù)編碼

在一次應(yīng)急物資調(diào)度中，參加調(diào)度任務(wù)的所有車輛的調(diào)度任務(wù)序列為一條染色體，其中任一輛車的全部調(diào)度任務(wù)為一個基因，任一輛車的部分調(diào)度任務(wù)定義為基因序列，任一輛車的單次完整調(diào)度任務(wù)為一個基因單元。

本文研究模型采用符號編碼方式，具體編碼符號定義如下：

b1代表一級倉庫點。

c1，c2，c3分別代表3個二級倉庫點。

e1，e2，e3，e4，e5分別表示5個災(zāi)害點。

w1，w2，w3分別代表藥品、食品和生活用品。

r1，r2分別代表一級2種運輸工具：大貨車和小貨車，且r1=｛10，80，6｝，r2=｛5，85，2｝，即大貨車和小貨車的載重量分別為10 t和5 t，滿載速度分別為80 km/h和85 km/h。大小貨車按先大車后小車依次編號。

ν1，ν2分別代表二級2種運輸工具：大貨車和小貨車，且 ν1=｛10，60，4｝，ν2=｛5，65，10｝，即大貨車和小貨車的載重量分別為10 t和5 t，滿載速度分別為60 km/h和65 km/h。編號同一級。

μ=（bi，wf，cj）代表一級的基因序列單元，其中，bi代表一級倉庫點；wf代表運輸物資種類；cj代表目的二級倉庫點。

Φ=｛φ1，φ2，…，φP｝表示某個運輸工具在某次調(diào)度任務(wù)中的全部調(diào)度任務(wù)。

τ=（ci，wf，ej）表示二級的基因序列單元，其中，ci代表出發(fā)二級倉庫點；wf代表運輸物資種類；ej代表目的災(zāi)害點。

Ω=｛ω1，ω2，…，ωq｝表示某個運輸工具在某次調(diào)度任務(wù)中的全部調(diào)度任務(wù)。

種群初始化即為按照設(shè)定的種群規(guī)模，生成相應(yīng)數(shù)目的染色體。本文遺傳算法中種群規(guī)模為50。

本文將調(diào)度任務(wù)完成時間定為目標(biāo)函數(shù)值。

4.2 遺傳算子

遺傳算子具體如下：

（1）基本遺傳算子

染色體間交叉操作和基因的變異操作實現(xiàn)遺傳算法的基礎(chǔ)功能。在獨立處理各級調(diào)度任務(wù)的遺傳算法中，染色體的雜交過程中采用多點一致雜交。多點一致雜交的具體雜交操作為：對2條父代染色體的每個相同基因位置上的基因序列依次進(jìn)行雜交操作，即選取兩相同基因位置的基因序列的一共有的雜交點，互換雜交點后續(xù)的該基因位置的基因序列。

（2）輔助遺傳操作算子

根據(jù)供求關(guān)系約束條件，對遺傳變異產(chǎn)生的染色體進(jìn)行處理，使各需求點的需求均滿足，使得一級倉庫點的各型物資出貨量不超過對應(yīng)物資儲量。修復(fù)操可以分為：補給量大于需求量，補給量小于需求量，供給量大于存儲量。分別按照相應(yīng)的處理方法進(jìn)行修復(fù)。

計算遺傳算法生成的染色體所對應(yīng)的調(diào)度方案中的每個物資需求點的對應(yīng)補給量。逐個將各需求點的各型物資需求量與其補給量進(jìn)行比較，若對某點某型物資補給量小于需求量，則在最先完成任務(wù)鏈的車增加一次運輸這種物資到該點的任務(wù)，重復(fù)此步驟至所有需求點對各類型物資需求均得到滿足。

若某點某型物資補給量過多，則在染色體中將含有到該點該型物資運輸任務(wù)的車中找到完成任務(wù)鏈耗時最長的那輛車，并刪除一次過量補給的任務(wù)，重復(fù)此步驟至各需求點對各型物資至補給均不過剩。

對于倉庫點修復(fù)處理則在染色體中搜索某物資出貨量大于實際儲量的倉庫，隨機(jī)將含有這些不合理的任務(wù)的車輛的轉(zhuǎn)貨點轉(zhuǎn)移到儲量富余的倉庫，重復(fù)此步驟至一級倉庫點對各型物資出貨量不超過其儲量。二級倉庫的物資出貨大于其儲量產(chǎn)生的缺口由一級調(diào)度系統(tǒng)來補充完成，因此計算二級調(diào)度的遺傳算法中無此修復(fù)操作。

本文將目標(biāo)函數(shù)值的倒數(shù)定義為適應(yīng)度值。若調(diào)度方案任務(wù)完成時間越短，則目標(biāo)函數(shù)值越小，其適應(yīng)度值越高。

4.3 分層獨立求解

本文算例二級倉庫有一定儲備保證二級車輛在二級倉庫不會有等待現(xiàn)象、一級調(diào)度任務(wù)時間相對二級調(diào)度任務(wù)時間較短?；诖?，采用分層獨立求解方法。

本文應(yīng)用遺傳算法先對二級調(diào)度系統(tǒng)進(jìn)行求解得出在滿足二級災(zāi)害點時的二級優(yōu)秀調(diào)度方案，根據(jù)此方案得出二級倉庫的理論出貨量，進(jìn)而判斷各二級倉庫的物資是否不足，根據(jù)二級倉庫的理論不足量再對一級調(diào)度系統(tǒng)進(jìn)行遺傳算法求解得出補足二級倉庫的理論物資缺口的一級優(yōu)秀調(diào)度方案。

詳細(xì)流程如下：首先初始化二級種群（50條染色體），對二級種群進(jìn)行雜交、變異、修復(fù)操作生成新的50條二級染色體，經(jīng)過自適應(yīng)度評價的篩選得到較優(yōu)的新的二級種群，再對新的一級種群進(jìn)行雜交、變異、修復(fù)操作生成最新的50條一級染色體，如此重復(fù)上述過程，直到滿足終止條件，得到滿足各個二級倉庫點的需求二級染色體序列。通過分析滿足要求的二級染色體序列可以計算出各二級倉庫需要從一級倉庫需求的物資種類和數(shù)量，需要從一級倉庫補貨的二級倉庫即為一級調(diào)度系統(tǒng)的需求點，再用遺傳算法對一級調(diào)度系統(tǒng)進(jìn)行同樣的操作即可得出一級調(diào)度方案。

5 算例求解分析

5.1 求解過程

本文將遺傳算法迭代過程中染色體的目標(biāo)函數(shù)值即任務(wù)完成時間與迭代次數(shù)的關(guān)系數(shù)據(jù)進(jìn)行保存并繪圖分析。當(dāng)?shù)聊臣壵{(diào)度的任務(wù)完成時間穩(wěn)定時，此時種群中的最優(yōu)染色體所對應(yīng)的調(diào)度方案即可對應(yīng)得到該級的一個優(yōu)秀調(diào)度方案。

（1）二級任務(wù)完成時間的收斂情況

基于遺傳算法求解一級序列并且在迭代50 000次基礎(chǔ)上，得到最優(yōu)一級序列和二級倉庫獲得量，將二級倉庫獲得量與二級倉庫的原有存儲量作為二級序列現(xiàn)有存儲量，基于遺傳算法求解滿足要求的二級序列。

分析前50 000次迭代任務(wù)時間和迭代次數(shù)的關(guān)系數(shù)據(jù)簡單算出任務(wù)時間下降梯度，在完成50 000次迭代后得到最優(yōu)二級序列的任務(wù)完成時間的收斂情況下，二級序列的調(diào)度任務(wù)完成時間（T2s）與迭代次數(shù)的關(guān)系分別如圖2和表4所示。

圖2 迭代50 000次后二級任務(wù)完成時間的收斂情況

表4 二級任務(wù)完成時間與迭代次數(shù)的關(guān)系1

由圖2可知，在50 000次迭代后，二級序列任務(wù)完成時間的收斂圖中能看到收斂比較明顯，但是數(shù)值沒有穩(wěn)定。根據(jù)之前的數(shù)據(jù)預(yù)測任務(wù)時間穩(wěn)定發(fā)生在200 000次以內(nèi)，因此本文分析迭代200 000次的調(diào)度任務(wù)時間與迭代次數(shù)的關(guān)系，其二級序列調(diào)度任務(wù)完成時間與迭代次數(shù)的關(guān)系分別如圖3和表5所示。

圖3 迭代200 000次后二級任務(wù)完成時間的收斂情況

表5 二級任務(wù)完成時間與迭代次數(shù)的關(guān)系2

由圖3可知，當(dāng)將二級迭代200 000次時，可以看到數(shù)據(jù)有明顯收斂趨勢，迭代次數(shù)為90 000時任務(wù)完成時間已經(jīng)穩(wěn)定。由表5可知，當(dāng)二級序列迭代次數(shù)達(dá)到50 000次以上，任務(wù)完成時間下降速度緩慢，當(dāng)?shù)螖?shù)到達(dá) 90 000次時，收斂值達(dá)到70.04 h。

（2）一級任務(wù)完成時間的收斂情況

本文將一級序列的迭代過程的循環(huán)終止條件設(shè)定為最大迭代次數(shù)50 000次，在完成50 000次迭代后得到一級序列任務(wù)完成時間的收斂情況下，一級序列的調(diào)度任務(wù)完成時間（T1s）與迭代次數(shù)的關(guān)系分別如圖4和表6所示。由圖4可知，當(dāng)將一級序列終止條件定為迭代50 000次時，任務(wù)時間有明顯的收斂趨勢，因此將非聯(lián)動調(diào)度中的一級序列的循環(huán)終止條件設(shè)定為50 000次。由表6可知，當(dāng)?shù)?0 000次時，收斂值達(dá)到45.25 h。

圖4 迭代50 000次后一級任務(wù)完成時間的收斂情況

表6 一級任務(wù)完成時間與迭代次數(shù)的關(guān)系

5.2 調(diào)度方案

由兩層調(diào)度任務(wù)完成時間穩(wěn)定時對應(yīng)的最優(yōu)染色體可得最終調(diào)度方案，如表7和表8所示。其中，一級大貨車編號為1～6，小貨車編號為7～8；二級大貨車編號為1～4，小貨車編號為5～14。

表7 一級調(diào)度方案

表8 二級調(diào)度方案

5.3 結(jié)果分析

通過表7和表8可以看出，一級調(diào)度方案任務(wù)完成時間問 45.25 h，二級調(diào)度方案任務(wù)時間是70.04 h，通過對車輛各自運輸任務(wù)的運貨量計算和倉庫點物資的實時統(tǒng)計可得調(diào)度方案嚴(yán)格地符合供求條件，即一級倉庫各種物資的出貨量均不大于其實際存儲量，二級各倉庫的補給量與原有存儲量之和均不小于出貨量，各災(zāi)害點的各種物資的補給量均嚴(yán)格滿足其實際需求量。同時每級調(diào)度方案中車輛各自任務(wù)時間相互偏差較小，調(diào)度合理。

6 結(jié)束語

本文以調(diào)度任務(wù)完成時間最短為目標(biāo)，提出求解多種物資、多種車型的應(yīng)急物資分層調(diào)度問題，并對此問題建立數(shù)學(xué)模型。從簡化問題的角度設(shè)計求解方法，通過設(shè)定符合實際情況的條件，使得串聯(lián)的調(diào)度系統(tǒng)間耦合程度降低，采用遺傳算法對各調(diào)度層進(jìn)行依次獨立求解。設(shè)計一個典型算例進(jìn)行程序設(shè)計并得出結(jié)果，通過結(jié)果分析可知約束條件均嚴(yán)格滿足且系統(tǒng)調(diào)度資源得到充分利用，分層獨立求解方法在滿足二級倉庫有一定儲備的情況下，求解步驟較簡潔，并可明顯提高求解速度。因此，本文求解方法對求解分層調(diào)度問題具備可行性。然而，本文求解方法無法從全局最優(yōu)的角度求得不同條件下的調(diào)度結(jié)果，因此，如何應(yīng)用整體聯(lián)動的求解方法對物資分層調(diào)度進(jìn)行求解將是今后研究的方向。并且對本文求解方法進(jìn)行擴(kuò)充，將調(diào)度問題擴(kuò)展至多階段調(diào)度，也是有待研究的內(nèi)容。

［1］ Mladenovic N.基于單點搜索的元啟發(fā)式算法［M］.趙秋紅，肖依永，譯.北京：科學(xué)出版社，2013.

［2］ 張俊偉，王 勃，馬范援.多倉庫多配送點的物流配送算法［J］.計算機(jī)工程，2005，31（21）：192-194.

［3］ 廖良才，王 棟，周 峰.基于混合遺傳算法的物流配送車輛調(diào)度優(yōu)化問題求解方法［J］.系統(tǒng)工程，2008，26（8）：27-32.

［4］ 陳子俠，葉慶泰.基于城市配送的單車線路算法研究［J］.計算機(jī)工程，2005，31（11）：32-34.

［5］ Wei Yi，Kumar A.Ant Colony Optimization for Disaster Relief Operations［J］.Transportation Research Part E，2007，43（6）：660-672.

［6］ Hindi K S，BastaT.Effieient Solution of a Multicommodity，Multi-modal Network Flow Model for Disaster Relief Operations［J］.Transportation Researchpart A，1996，30（3）：231-235.

［7］ Sheu Jiuh-Biing.Special Issue on Emergency Logistics Management Transportation Research Part E：Logistics and Transportation Review［J］.Transportation Research Part E，2005，41（5）：459-460.

［8］ Barbarosoglu G，Arda Y.A Two-stage Stochastic Programming Framework for Transportation Planning in Disaster Response［J］.Journal of the Operational Research Society，2004，55（1）：43-53.

［9］ Beradi P，Bruni M E.A Probabilistic Model Applied to Emergency Service Vehicles Location［J］.European Journal of Operational Research，2009，196（1）：323-331.

［10］ Barbarosoglu G，Arda Y.A Two-stage Stochastic Programming Framework for Transportation Planning in Distaster Response［J］.Journal of the Operational Research Society，2004，55（1）：43-53.

［11］ Ozdamar L，Ekinci E.Emergency Logistic Planning in Natural Disasters［J］.Annals of Operations Research，2004，129（1-4）：217-245.

［12］ 張 軍.計算智能［M］.北京：清華大學(xué)出版社，2009.

［13］ 徐 磊.基于遺傳算法的多目標(biāo)優(yōu)化問題的研究與應(yīng)用［D］.長沙：中南大學(xué)，2007.

［14］ 徐宗本，張講社，鄭亞林.計算智能中的仿生學(xué)理論與算法［M］.北京：科學(xué)出版社，2003.

編輯 陸燕菲

Research on Hierarchical Scheduling of Emergency Supp lies Based on Genetic Algorithm

HU Feihu，TIAN Chaohui，LI Wei，HAN Xin

（Department of Industrial Automation，School of Electrical Engineering，Xi’an Jiaotong University，Xi’an 710049，China）

Aiming at the hierarchical scheduling problem of multi-vehicle and multi-supply，this paper proposes a hierarchical scheduling scheme.A two-layer scheduling example is demonstrated for the problem，and it decouples the tow-layer example into two single-layer problem s.Taking minimize system scheduling task completion time as the objective function，it uses the genetic algorithm to get the scheduling scheme which describes the specific type of carried cargo，the source and the destination for each type of vehicle in sequence.In this hierarchical scheduling scheme，the output in each warehouse is below its storage，the requirement quantity of supplies in each emergency point meets requirement by the real-time statistics in each warehouse and the calculation of carried cargo in each task.The solving process of this scheme is simple and fast.

emergency supplies scheduling；hierarchical scheduling；vehicle scheduling；genetic algorithm；objective function

胡飛虎，田朝暉，李 威，等.基于遺傳算法的應(yīng)急物資分層調(diào)度研究［J］.計算機(jī)工程，2015，41（10）：53-58.

英文引用格式：Hu Feihu，Tian Chaohui，Li Wei，et al.Research on Hierarchical Scheduling of Emergency Supp lies Based on Genetic Algorithm［J］.Computer Engineering，2015，41（10）：53-58.

1000-3428（2015）10-0053-06

A

TP311.1

10.3969/j.issn.1000-3428.2015.10.011

國家自然科學(xué)基金資助項目（61174154）；中央高校基本科研業(yè)務(wù)費專項基金資助項目。

胡飛虎（1973-），男，副教授、博士生導(dǎo)師，主研方向：復(fù)雜網(wǎng)絡(luò)建模及優(yōu)化調(diào)度，嵌入式智能控制系統(tǒng)；田朝暉、李 威、韓 鑫，碩士研究生。

2014-09-22

2014-11-15E-mail：2476008926@qq.com