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

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

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

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

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

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

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

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

1 概述

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

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

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

已知各倉(cāng)庫(kù)點(diǎn)的物資儲(chǔ)量和災(zāi)害點(diǎn)的物資需求量。

（1）假設(shè)條件

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

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

3）不考慮各運(yùn)輸工具的裝卸貨時(shí)間。

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

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

（2）模型參數(shù)

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

B：一級(jí)倉(cāng)庫(kù)點(diǎn)集合，即B=｛b1，b2，…，bm｝。

C：二級(jí)倉(cāng)庫(kù)點(diǎn)集合，即C=｛c1，c2，…，ca｝。

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

BW：一級(jí)物資儲(chǔ)備中心（一級(jí)倉(cāng)庫(kù)）物資信息集合，即BW=｛bw1，bw2，…，bwm｝。

CW：二級(jí)物資儲(chǔ)備中心（二級(jí)倉(cāng)庫(kù)）物資信息集合，即CW=｛cw1，cw2，…，cwn｝。

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

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

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

q為一級(jí)倉(cāng)庫(kù)點(diǎn)和二級(jí)倉(cāng)庫(kù)點(diǎn)間路徑距離矩陣：

l為二級(jí)倉(cāng)庫(kù)點(diǎn)和災(zāi)害點(diǎn)之間的路徑距離矩陣：

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

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

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

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

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

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

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

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

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

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

圖1 各倉(cāng)庫(kù)、災(zāi)害點(diǎn)的運(yùn)輸路徑關(guān)系

表1 一級(jí)各倉(cāng)庫(kù)、二級(jí)各倉(cāng)庫(kù)的運(yùn)輸路徑距離 km

表2 二級(jí)各倉(cāng)庫(kù)、災(zāi)害點(diǎn)的運(yùn)輸路徑距離 km

表3 各倉(cāng)庫(kù)、災(zāi)害點(diǎn)的存儲(chǔ)量與需求量

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

4.1 參數(shù)編碼

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

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

b1代表一級(jí)倉(cāng)庫(kù)點(diǎn)。

c1，c2，c3分別代表3個(gè)二級(jí)倉(cāng)庫(kù)點(diǎn)。

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

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

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

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

μ=（bi，wf，cj）代表一級(jí)的基因序列單元，其中，bi代表一級(jí)倉(cāng)庫(kù)點(diǎn)；wf代表運(yùn)輸物資種類；cj代表目的二級(jí)倉(cāng)庫(kù)點(diǎn)。

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

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

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

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

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

4.2 遺傳算子

遺傳算子具體如下：

（1）基本遺傳算子

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

（2）輔助遺傳操作算子

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

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

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

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

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

4.3 分層獨(dú)立求解

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

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

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

5 算例求解分析

5.1 求解過(guò)程

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5.2 調(diào)度方案

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

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

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

5.3 結(jié)果分析

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

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

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

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

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

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

［4］ 陳子俠，葉慶泰.基于城市配送的單車線路算法研究［J］.計(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］ 張 軍.計(jì)算智能［M］.北京：清華大學(xué)出版社，2009.

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

［14］ 徐宗本，張講社，鄭亞林.計(jì)算智能中的仿生學(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ì)算機(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

國(guó)家自然科學(xué)基金資助項(xiàng)目（61174154）；中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)基金資助項(xiàng)目。

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

2014-09-22

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