基于改進粒子群算法的多資源應急調度研究

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

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

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.

關鍵詞：應急物資;資源調度;時間成本調度模型;粒子群算法

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

中圖分類號：O221;N945;TP301.6? ? ? ? ? ? ? 文獻標識碼：A? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文章編號：1006-4311（2020）10-0243-03

0? 引言

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

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

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

1? 問題假設及建立模型

假設A為受災地點，B1，B2，…，Bn為n個應急資源供給點，受災點需要救災物資種類為m種。其中符號定義如下：

Qij表示第i個供給點對第j種資源的儲備量;

xij表示第i個供給點對第j種資源的調度數(shù)量;

Cij表示第i個供給點對第j種資源的單位運輸成本;

Cij（t）表示第i個對供給點第j種資源的時間成本系數(shù);

R1，R2，…，Rm分別表示需求點對m種資源需求量，其中 ;

tij表示為第i個供應點第j種資源的運輸時間;

t0表示第j種資源運輸?shù)綉秉c的最短時間;

C0表示該供給點的單位條件的運輸成本;

C0/t0表示該供應點的單位時間內的運輸成本;

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

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

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

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

2? 改進粒子群算法求解

2.1 基本粒子群算法

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

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

2.2 改進粒子群算法（Improved PSO IPSO）

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

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

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

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

2.3 改進粒子群算法（IPSO）步驟

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

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

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

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

⑤如果沒有達到最大的迭代數(shù)或得到足夠好的適應值，則返回Step2。

3? 算例分析

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

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

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

4? 結論

本文針對一個受災地點，多種物資需要調度的應急資源調度問題，構造了時間-成本應急資源調度模型。采用改進的粒子群算法，并對模型進行了求解。通過數(shù)值算例結果表明，所提算法能夠有效降低調度成本，是解決應急資源調度的一種有效方法。

參考文獻：

[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ā)事件緊急救援關鍵技術研究[D].西安：長安大學，2012：101-121.

[4]汪勇，金菲.應急資源調度問題的改進進化算法研究[J].運籌與管理，2012，21（4）：29-33.

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

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

[7]魏國強，余超.出救時間不確定的連續(xù)消耗應急資源調度[J].計算機應用，2012，232（6）：1745-1748.

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