邵澤軍 陳凡紅 呂曉娜 郭慧敏

摘要：針對(duì)多資源應(yīng)急調(diào)度問(wèn)題，建立了多資源時(shí)間-成本調(diào)度模型。為了避免標(biāo)準(zhǔn)粒子群算法陷入局部的最優(yōu)解，有效提高算法的搜索精度，通過(guò)鄰域重疊，慣性因子線性變化等方法，提出了全局和局部混合模式的改進(jìn)粒子群算法。通過(guò)數(shù)值算例驗(yàn)證了模型的合理性和算法的可行性和有效性，算例結(jié)果并與其它算法進(jìn)行了比較，結(jié)果表明，所提算法能夠有效降低調(diào)度成本，是解決應(yīng)急資源調(diào)度的一種有效方法。

Abstract： In view of the multi resource emergency scheduling problem， a multi-resource time-cost scheduling model is established. In order to avoid the standard particle swarm optimization algorithm falling into the local optimal solution and effectively improve the search accuracy of the algorithm， an improved particle swarm optimization algorithm with global and local mixed mode is proposed by means of neighborhood overlap. linear change of inertia factor and other methods is used. The rationality of the model and the feasibility and effectiveness of the algorithm are verified by numerical examples. The results of the examples are compared with other algorithms. The results show that the proposed algorithm can effectively reduce the scheduling cost and is an effective method to solve the emergency resource scheduling.

關(guān)鍵詞：應(yīng)急物資;資源調(diào)度;時(shí)間成本調(diào)度模型;粒子群算法

Key words： emergency supplies;resource scheduling;time-cost scheduling model;particle swarm optimization

中圖分類號(hào)：O221;N945;TP301.6? ? ? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文章編號(hào)：1006-4311（2020）10-0243-03

0? 引言

近年來(lái)，世界各地的各種事故災(zāi)害，公共安全災(zāi)害和自然災(zāi)害層出不窮，我國(guó)在2003年發(fā)生的SARS，2008年汶川地震等災(zāi)害都對(duì)人們的生產(chǎn)生活造成了嚴(yán)重的危害。在事故和災(zāi)害發(fā)生時(shí)，怎樣在短時(shí)間內(nèi)，合理安排救援人員和救災(zāi)物資的調(diào)度，使災(zāi)害造成的傷害降到最低，這是國(guó)內(nèi)外學(xué)者研究的核心問(wèn)題。

Fiedich等[1]提出了時(shí)間和空間上的優(yōu)化資源分配的動(dòng)態(tài)組合優(yōu)化模型;Barbarosoglu G等[2]針對(duì)地震這一自然災(zāi)害中的應(yīng)急物資運(yùn)輸問(wèn)題，提出了需求時(shí)間最小以及成本最小的兩階段隨機(jī)規(guī)劃模型;李建斌[3]建立了機(jī)會(huì)成本最小化為目標(biāo)，提出了緊急求援資源調(diào)度模型，并采用模擬退火算法進(jìn)行了求解;汪勇，金菲[4]建立了多資源-成本調(diào)度模型，采用改進(jìn)的進(jìn)化規(guī)劃算法進(jìn)行了求解;汪欲，何建敏[5]就一次性消耗系統(tǒng)為背景多資源出救方案進(jìn)行了研究。戴更新、達(dá)慶利[6]針對(duì)單個(gè)應(yīng)急點(diǎn)開(kāi)始時(shí)間最早的多種資源應(yīng)急調(diào)度問(wèn)題建立了模型，并給出了算法和調(diào)度方案。魏國(guó)強(qiáng)等[7]針對(duì)出救時(shí)間不確定的連續(xù)消耗應(yīng)急資源調(diào)度問(wèn)題進(jìn)行了研究，建立了連續(xù)性滿足度調(diào)度模型。

針對(duì)應(yīng)急物資的多資源調(diào)度問(wèn)題，本文建立了應(yīng)急時(shí)間和運(yùn)輸成本最低的多目標(biāo)優(yōu)化模型，并采用鄰域重疊和慣性因子線性變化等方法，提出全局和局部混合模式的改進(jìn)的粒子群算法對(duì)其進(jìn)行了求解，并取得較好的運(yùn)算結(jié)果。

1? 問(wèn)題假設(shè)及建立模型

假設(shè)A為受災(zāi)地點(diǎn)，B1，B2，…，Bn為n個(gè)應(yīng)急資源供給點(diǎn)，受災(zāi)點(diǎn)需要救災(zāi)物資種類為m種。其中符號(hào)定義如下：

Qij表示第i個(gè)供給點(diǎn)對(duì)第j種資源的儲(chǔ)備量;

xij表示第i個(gè)供給點(diǎn)對(duì)第j種資源的調(diào)度數(shù)量;

Cij表示第i個(gè)供給點(diǎn)對(duì)第j種資源的單位運(yùn)輸成本;

Cij（t）表示第i個(gè)對(duì)供給點(diǎn)第j種資源的時(shí)間成本系數(shù);

R1，R2，…，Rm分別表示需求點(diǎn)對(duì)m種資源需求量，其中 ;

tij表示為第i個(gè)供應(yīng)點(diǎn)第j種資源的運(yùn)輸時(shí)間;

t0表示第j種資源運(yùn)輸?shù)綉?yīng)急點(diǎn)的最短時(shí)間;

C0表示該供給點(diǎn)的單位條件的運(yùn)輸成本;

C0/t0表示該供應(yīng)點(diǎn)的單位時(shí)間內(nèi)的運(yùn)輸成本;

Tj表示為第j種資源的供應(yīng)量滿足一定應(yīng)急系數(shù)w的時(shí)限，即在Tj時(shí)間內(nèi)，第j種資源的供應(yīng)量達(dá)到wRj。

本文依據(jù)文獻(xiàn)[4]，建立多資源時(shí)間-成本調(diào)度模型。具體模型如下：

其中，f1（x）和f2（x）分別表示時(shí)間成本和運(yùn)輸成本，約束條件中：式（2）表示應(yīng)急點(diǎn)調(diào)運(yùn)的資源應(yīng)該不少于應(yīng)急系數(shù)w條件下的資源需求量，運(yùn)輸時(shí)間不超過(guò);式（3）表示應(yīng)急供給點(diǎn)的資源調(diào)度量要不少于受災(zāi)點(diǎn)的資源需求量;式（4）表示救災(zāi)供應(yīng)點(diǎn)提供的應(yīng)急資源的數(shù)量約束條件。為了便于計(jì)算，將時(shí)間成本系數(shù)Cij（t）與增加的運(yùn)輸時(shí)間通過(guò)式（5）轉(zhuǎn)化為單位運(yùn)輸成本。

式（5）中：增加的單位時(shí)間的運(yùn)輸成本 表示從其它供應(yīng)點(diǎn)調(diào)度資源所產(chǎn)生的成本。

2? 改進(jìn)粒子群算法求解

2.1 基本粒子群算法

Kennedy和Eberhart在1995年通過(guò)模擬飛鳥(niǎo)撲食提出了智能算法-粒子群優(yōu)化算法（PSO）[8]。假設(shè)目標(biāo)搜索空間為D維，群體的粒子數(shù)為n個(gè)，粒子群中的每個(gè)粒子在每一次進(jìn)化中，都是通過(guò)跟蹤自己的兩個(gè)最優(yōu)解來(lái)更新自己位置。一個(gè)是粒子本身所找到的最優(yōu)解pbest，記為 ，一個(gè)是整個(gè)粒子群所找到的最優(yōu)解gbest，記為 。粒子更新粒子的速度和新的位置利用如下的公式：

式中：c1和c2為學(xué)習(xí)因子，ω稱為慣性因子，r1和r2是介于[0，1]之間的隨機(jī)數(shù)，α稱為約束因子。

2.2 改進(jìn)粒子群算法（Improved PSO IPSO）

粒子群算法（PSO）結(jié)構(gòu)簡(jiǎn)單，易于實(shí)現(xiàn)，但是卻容易陷入局部最優(yōu)，且搜索精度不高的缺點(diǎn)。針對(duì)該問(wèn)題，本文提出的改進(jìn)粒子群算法（IPSO）主要從以下三個(gè)方面做了改進(jìn)：

首先，基于鄰域思想，本文提出用全局和局部混合模式的改進(jìn)PSO算法。局部模式的算法同全局模式大體類似，最大的不同點(diǎn)就是利用局部最優(yōu)解pl去替換粒子群中的全局最優(yōu)解pg。其中，局部最優(yōu)解為該粒子鄰域向量空間通過(guò)歷次迭代所能搜索到的最優(yōu)解。公式如下：

其次，根據(jù)粒子群算法中慣性因子的特點(diǎn)，慣性因子ω的設(shè)置，可以調(diào)節(jié)算法的能力，慣性因子ω的取值越大，算法具有的全局搜索能力就越強(qiáng);慣性因子的ω的取值越小，算法的局部搜索能力就越強(qiáng)。鑒于此，本文通過(guò)將變量慣性因子ω設(shè)置為從0.9到0.4隨時(shí)間線性減少這種方法，使算法在搜索初期，粒子更加側(cè)重于全局搜索，從而更容易得到較好的粒子;在算法的搜索后期，粒子更加側(cè)重于區(qū)域的局部搜索，從而使算法更易于收斂于全局最優(yōu)解。

再次，本文提出的改進(jìn)的粒子群算法，算法初期，每個(gè)個(gè)體的鄰域設(shè)置為其自身，在算法搜索中，適應(yīng)度更好的個(gè)體存在于適應(yīng)值較好的點(diǎn)的鄰域范圍內(nèi)，這就使得粒子在搜索過(guò)程中不是開(kāi)始就向全局的最優(yōu)解附近搜索，而是首先向粒子鄰域內(nèi)的最優(yōu)解搜索。由于兩個(gè)相鄰鄰域內(nèi)會(huì)有一部分公共的粒子，公共粒子之間可以通過(guò)兩個(gè)鄰域相互交換各自獲得的信息。算法迭代次數(shù)的不斷增加，使得鄰域逐漸增大，直至覆蓋整個(gè)種群。于是，本文提出的改進(jìn)粒子群算法有效的使粒子跳出局部最優(yōu)解，避免早熟，達(dá)到全局最優(yōu)解。

2.3 改進(jìn)粒子群算法（IPSO）步驟

①初始化一種群，其中每個(gè)粒子位置向量按照1～m×n之間的數(shù)隨機(jī)取一個(gè)實(shí)數(shù)，每個(gè)速度向量按照-（m×n-1）～（m×n-1）之間實(shí)數(shù)隨機(jī)取， 并將粒子群空間劃分為若干個(gè)兩兩重疊的相鄰粒子群，設(shè)定參數(shù)c1，c2;

②計(jì)算每個(gè)粒子的適應(yīng)值，最優(yōu)解pbest為每個(gè)粒子的初始適應(yīng)值，接著尋求群內(nèi)的全局最優(yōu)解gbest;針對(duì)每個(gè)粒子，把當(dāng)前的適應(yīng)值和其搜索過(guò)的最好位置pbest作比較，若當(dāng)前適應(yīng)值較好，就將作為最好的位置pbest;

③計(jì)算種群中的每個(gè)粒子的鄰域取值范圍，接下來(lái)，比較當(dāng)前適應(yīng)值與其鄰域經(jīng)過(guò)的最好位置lbest，若較差，則通過(guò)重新設(shè)置lbest進(jìn)行搜索，否則，直接采用gbest作為最優(yōu);

④更新下一代的種群的微粒的速度和位置;

⑤如果沒(méi)有達(dá)到最大的迭代數(shù)或得到足夠好的適應(yīng)值，則返回Step2。

3? 算例分析

假設(shè)某地區(qū)A發(fā)生自然災(zāi)害，需要3類應(yīng)急資源，需求量分別為15噸，30噸，50噸，現(xiàn)有5個(gè)應(yīng)急供應(yīng)點(diǎn)，各供應(yīng)點(diǎn)及資源如表1。

本文改進(jìn)粒子群算法所用參數(shù)為：n=30，c1=c2=2.0，子群規(guī)模為3個(gè)粒子，不同子群間的重疊的粒子數(shù)為2個(gè)，算法最大迭代次數(shù)為200，運(yùn)算次數(shù)為10次。

表2中最優(yōu)調(diào)度方案的括號(hào)內(nèi)表示從5個(gè)供應(yīng)點(diǎn)調(diào)度的3種不同資源數(shù)量，與文獻(xiàn)[4]比較，五種算法的調(diào)度成本逐步增加，EPSO、IEP、GA、DE、EP、調(diào)度成本依次為70.18、70.40、73.55、75.46、80.58（萬(wàn)元），從而本文提出的算法有效降低了調(diào)度成本。

4? 結(jié)論

本文針對(duì)一個(gè)受災(zāi)地點(diǎn)，多種物資需要調(diào)度的應(yīng)急資源調(diào)度問(wèn)題，構(gòu)造了時(shí)間-成本應(yīng)急資源調(diào)度模型。采用改進(jìn)的粒子群算法，并對(duì)模型進(jìn)行了求解。通過(guò)數(shù)值算例結(jié)果表明，所提算法能夠有效降低調(diào)度成本，是解決應(yīng)急資源調(diào)度的一種有效方法。

參考文獻(xiàn)：

[1]Fiedich F，Gehbauer F，Rickers U. Optimized resource allocation for emergency response after earthquake disasters[J]. Safety Science， 2000， 35（1-3）： 41-57.

[2]Barbarosoglu G， Arda Y. A two-stage stochastic programming framework for transportation planning in disaster response[J]. Journal of operational research society， 2004， 55： 43-53.

[3]李建斌.高速公路突發(fā)事件緊急救援關(guān)鍵技術(shù)研究[D].西安：長(zhǎng)安大學(xué)，2012：101-121.

[4]汪勇，金菲.應(yīng)急資源調(diào)度問(wèn)題的改進(jìn)進(jìn)化算法研究[J].運(yùn)籌與管理，2012，21（4）：29-33.

[5]汪欲，何建敏.應(yīng)急系統(tǒng)中多資源出救方案的研究[J].東南大學(xué)學(xué)報(bào)（自然科學(xué)版），2002，32（3）：510-513.

[6]戴更新，達(dá)慶利.多資源組合應(yīng)急調(diào)度問(wèn)題的研究[J].系統(tǒng)工程理論與實(shí)踐，2000，20（9）：52-55.

[7]魏國(guó)強(qiáng)，余超.出救時(shí)間不確定的連續(xù)消耗應(yīng)急資源調(diào)度[J].計(jì)算機(jī)應(yīng)用，2012，232（6）：1745-1748.

[8]吳聰，楊建輝.基于改進(jìn)粒子群算法的物流配送車輛調(diào)度優(yōu)化[J].計(jì)算機(jī)工程與應(yīng)用，2015，51（13）：259-262.