基于離散粒子群算法的應急物資調度系統研究

摘要：應急物資的調度是一個非常重要而實際的研究課題，首要條件是時間最短，在時間最短的基礎上要求費用最低。在此基礎上，建立了時間最短、成本最低的多目標帶約束的數學模型，并利用理想點法將此多目標問題轉化為單目標問題，而后利用粒子群算法中的罰函數法將此帶約束的問題轉化為不帶約束的問題，最后用離散的粒子群算法求解。實驗表明，用粒子群算法求解應急物資調度問題有效可行。

關鍵詞：應急物資；離散粒子群；群體智能

中圖分類號：TP301文獻標識碼：A文章編號：1009-3044(2008)25-1503-03

Research of Emergency Materials' Scheduling Solved by Binary PSO

LIN Hao1， XU Wei-sheng2

(1.School of Software Engineering， Tongji University， Shanghai 201804， China; 2.School of Electronic and Information Engineering， Tongji University， Shanghai 201804， China)

Abstract: Emergency materials' scheduling problem is a very important and practical research task， first of all the shortest time is asked and besides that， the lowest fees is also asked. Thus， the multi-objective constrained mathematic model with the shortest time and the lowest fees is constructed. First， we use ideal point method to convert the multi-objective model to single-objective model; then， we use penalty function method in PSO(Particle Swarm Optimization) to convert constrained model to unconstrained model; at last， we use discrete PSO to resolve the single-objective unconstrained model. As it is seen， these above ways are effective and practical.

Key words: emergency materials; binary pso; swarm intelligence

1 引言

當今世界，突發事件的爆發頻率急劇上升，誘發因素日益多元化，影響領域更加廣泛。如何應對突發事件，做好應急管理工作是政府在新時期面臨的一項艱巨任務。在應對突發事件的過程中，應急資源的高效快速調度是提高防災減災和災害救助的必要條件，也是衡量應急管理能力的一個重要指標。突發事件發生以后，需要大量的救災物資進行緊急調配，這種應急問題最顯著的特點就是時間的緊迫性，其時間效益高于經濟效益。并且在進行物資調度的過程中要盡量做到在限定時間內保障物資供應的同時兼顧費用問題。對于應急物資的調度，許多學者進行了深入的研究，既有以時間最短和出救點最少為目標的相關研究[1]，也有在此基礎之上引入理想點法的考慮成本最小在內的相關研究[2]，但是他們都是采用傳統數學方法求解，本文則采用了群體智能算法中的粒子群優化算法去求解最佳出救點。粒子群優化算法是一種進化計算技術(evolutionary computation)，用在連續實數空間的全局優化問題中。目前已經廣泛用于函數優化、神經網絡、模糊系統控制以及其他遺傳算法的應用領域[3，4，5]。

2 粒子群算法

2.1 基本粒子群算法

PSO模擬鳥群的捕食行為。設想這樣一個場景：一群鳥在隨機搜索食物。在這個區域里只有一塊食物。所有的鳥都不知道食物在哪里。但是他們知道自己當前的位置離食物大概還有多遠。那么最簡單有效的方法就是搜索目前離食物最近的鳥的周圍區域。

PSO從這個模型中得到啟示并用于解決優化問題。PSO中，每個優化問題的解都是搜索空間中的一只鳥。我們稱之為“粒子”。所有的粒子都有一個被優化函數決定的適應值(fitness value)，每個粒子還有一個由速度和位置構成的運動方程。然后每個粒子追尋適應值最好的粒子在解空間中搜索。

PSO初始化為一群隨機粒子，然后通過迭代找到最優解。在每一次迭代中，粒子通過跟蹤兩個“極值”更新自己的位置和速度。第一個就是粒子本身的最優歷史值，這個值記作pbest。另一個極值是整個群體的最優歷史值，這個值記作gbest。

粒子的運動方程[6]為：

（1）

（2）

i代表解的維數，j代表了當前迭代次數。ω為慣性權數，它代表了粒子拓展搜索空間的能力。ω*Vj-1[i]代表了粒子的多樣性能力。如果沒有ω*Vj-1[i]這一項，最后解出的最優解可能是一個局部的最優解。在迭代過程的開始，ω較大，這樣可以讓粒子有更好的探索(exploration)能力，找到最優解的大概位置。隨著迭代的進行，ω逐漸減小，這樣讓粒子有更好的開發(exploitation)能力，在局部找到最優解的精確位置。c1和c2是學習因子，代表了向自己和種群最優粒子的學習能力。rand()和Rand()都是隨機產生一個[0，1]之間的實數的函數。

基本粒子群算法求最優解過程如圖1所示。

2.2 離散粒子群算法

基本的粒子群算法自提出以來得到了很多學者的重視，大多數研究者都集中在連續數值優化領域研究。但是許多優化問題都被設置在離散的變量空間中。典型的應用包括需要對離散元素排序的問題，例如調度和路由問題。除了這些純組合優化問題外，研究者經常需要將浮點實數轉化成二進制的形式，然后在離散的空間中解決問題。任何問題，離散的和連續的都能表示成二進制的形式，研究者發現二值函數的優化方法有時是更為可行的。一直到1997年Kennedy和Eberhart提出了PSO算法的離散二進制版本(BPSO:Binary PSO)[7，8]，使粒子群算法進入了離散值優化領域。

BPSO采用二進制編碼形式，例如在做函數優化時，每個變量用5位的二進制數表示，如果這個函數有2個變量，那么每個粒子的二進制編碼長度(維數)就是10。

BPSO與PSO最重要的區別就是粒子的運動方程，BPSO的粒子運動方程如下：

（3）

（4）

（5）

速度公式保持不變，位置公式改變，其中pbest、gbest和x只能為0或1。速度不再是位置的步長，而是決定位置的一種概率。這個概率被約束在[0，1]之間。通過sigmoid函數來約束位置，sigmoid函數曲線圖如圖2。在連續變量空間的PSO中，速度有上限Vmax；在離散變量空間的BPSO中，Vmax仍然存在。Vmax通過sigmoid函數決定了位置為0或為1的概率。如果Vmax=6.0，那么通過sigmoid函數作用，概率被限制在[0.0025，0.9975]之間。一般設置Vmax=6.0。實驗表明，Vmax=6.0的情況所產生的解是可行的。如果Vmax=10.0，實驗表明產生的解不可行。因為Vmax的作用是在粒子聚合之后限制粒子的探索能力，如果Vmax太大，粒子會飛過最優解。在某種意義上，也可以說是控制解向量的最終變異速率或者溫度。注意，盡管高Vmax在連續PSO中能夠增加粒子的探索能力，但是在離散BPSO中小Vmax能夠允許更高的變異速率。由公式(4)可知，x的取值并沒有設定S函數的域值，而是受到S函數概率值的影響，也就是速度較大的時候，x的取值為1的可能性較大，為0的可能性很小。因此這種設置x值的方式本身就隱含了一種變異的方式，可以使粒子拓展搜索范圍，幫助BPSO跳出局部最優。

BPSO的求解過程和PSO一樣，見圖1。

2.3 非固定多段映射罰函數法

罰函數法(PFM: Penalty Function Method)是應用最為廣泛的一種處理約束的方法，其基本思想是通過序列無約束最小化技術(Sequential Unconstrained Minimization Technique)，將約束優化問題轉化為一系列無約束優化問題進行求解，應用起來比較方便。具體的方法是在目標函數上加上一個能夠反映點是否滿足約束的懲罰項，從而構成一個無約束的廣義目標函數，使得算法在懲罰項的作用下找到問題的最優解。

通常，所構造的廣義目標函數具有如下形式：

（6）

其中f(x)代表原目標函數；k是當前迭代的次數，Rn是整個解空間，S為粒子群找到的解。h(k)H(x)成為懲罰項，h(k)表示懲罰力度，H(x)為懲罰因子。在公式(6)中，如果h(k)在求解約束優化(CO:constrained optimization)問題的整個過程中固定不變，則稱之為固定罰函數法(SPFM: Stationary PFM)；反之則稱之為非固定罰函數法(NSPFM: Non-Stationary PFM)。固定罰函數法也稱精確罰函數法，在整個求解過程中只需計算一個目標函數，但懲罰力度h(k)難以選擇，如果太小，則收斂減慢；反之，則會在可行域邊界產生病態，給計算帶來困難。通常NSPFM對CO問題的求解結果總是優于SPFM。

Parsopoulos和Vrahatis[9]較早嘗試用PSO算法求解CO問題。在求解過程中，采用上述的罰函數法處理問題的約束條件，其中h(k)可以被動態調整，H(x)具體定義如下：

（7）

公式(7)中，qi(x)=max{0，gi(x)}，i=1，2，…m。gi(x)表示第i個約束條件，共有m個約束條件。θ(qi(x))是一個多段映射函數。r(qi(x))表示懲罰函數的強度。上述方法稱為非固定多段映射罰函數法。

3 問題模型建立

本文的模型建立在以下假設條件之上：此系統為一次性消耗系統，即指當所有的貨物到達應急地點后才能開始應急活動；運輸過程中沒有意外事件發生，即運輸時間比較準確；應急物資儲備量充足，不需要額外生產和補給。

假設n個物資儲備點A1，A2，…，An可以向應急地點提A供物資M，且物資M的需求量為G0，每個物資儲備點可以提供的物資量依次為G1，G2，…，Gn(Gi>0， i=1，2，…，n)且Gi≥G0。各物資儲備點達到應急地點A的時間依次為T1，T2，…，Tn(Ti>0， i=1，2，…，n)，達到應急地點A的費用依次為C1，C2，…，Cn(Ci>0， i=1，2，…，n)。

（8）

從n個物資儲備點里選擇若干個，使得時間小于預期T0，并且費用最低。根據題意，可建立公式(8)的數學模型，這是一個典型的多目標優化問題。采用理想點法可將多目標優化問題轉換為單目標優化問題。理想點法基本思想是求出各目標函數的最優值和最劣值，即其正理想點和負理想點，再求出各方案與正負理想點的相對接近度，相對接近度越大，方案越好。

于是，對于本問題須求出T=xiTi和C=xiCi的正負理想點，假設分別為Tmin、Tmax、Cmin和Cmax。

（9）

Rv和rv分別為該方案與正負理想點的接近度。w1和w2分別為關于運輸時間和成本的權重，w1+w2=1。因為這里時間比費用更重要，所以w1比w2大。 ，εv越大方案越好。于是問題模型可以描述成如下：

（10）

公式(10)中是一個帶約束的模型。這里我們采用非固定罰函數法消除約束。新的目標函數為：，其中

h(k)=k，k為當前迭代次數。

，，，，

4 實例分析

2008年初中國南方大部分地區發生罕見雪災，電力供應設備被嚴寒嚴重破壞，導致大部分地區停電。假設某地區急需100萬只蠟燭照明，考慮從其周邊城市若干個蠟燭生產廠緊急調用蠟燭到該地區。各蠟燭生產廠Ai的蠟燭庫存量Gi以及到該地區的時間Ti和費用Ci見表1。

假設要求所有蠟燭到達受災地區的時間不超過6.5小時，即T0=6.5以及公式(9)中的w1和w2分別為0.8和0.2。從表1可知，當生產廠A9被選擇時，此時時間最長且為8.5，所以記Tmax=8.5；當生產廠A1、A2、A3和A4被選擇時，此時時間最短且為5.5，所以記Tmin=5.5；當生產廠A1、A7和A3被選擇時，此時費用最大且為83，所以記Cmax=83；當生產廠A9、A5、A4和A8被選擇時，此時費用最低且為49，所以記Cmin=49。Tmax、Tmin、Cmax和Cmin依次為8.5、5.5、83和49。我們采用之前已經建立的模型去求解，得到的解向量為X={1，0，1，1，0，0，0，0，0}，即最佳出救點是生產廠A1、A3和A4，此時目標函數的適應值最小且為0.7061。本模型采用Visual Studio 2008 C++ compiler在Windows XP上實現。

5 結束語

本論文所作的工作是基于從多個出救點到一個受災點的時間最短費用最低問題，而實際發生突發事件的地點往往不止一個，也就是有多個事發地點。所以做完本論文后，下一個目標就是實現從多個出救點到多個事發地點的最優出救點的選擇，以期達到時間最短費用最低目標。

參考文獻：

[1] 劉春林，何建敏，施建軍.一類應急物資調度的優化模型研究[J].中國管理科學，2001，9(3):29-36.

[2] 劉北林，馬婷.應急救災物資緊急調度問題研究[J].哈爾濱商業大學學報（社會科學版），2007，(3):3-5.

[3] http://www.swarmagents.com/complex/models/algorithm.htm.

[4] 劉勤明，呂文元.旅行商問題的改進粒子群算法[J].計算機應用，2007，27(12):185-187.

[5] 鐘一文，楊建剛，寧正元.求解TSP問題的離散粒子群優化算法[J].系統工程理論與實踐，2006，6(6):88-94.

[6] Eberhart R， Kennedy J. A New Optimizer Using Particle Swarm Theory[C].Micro Machine and Human Science，1995: 39-43.

[7] Eberhart R， Kennedy J. A discrete binary version of the particle swarm algorithm[C]. Systems， Man， and Cybernetics， 1997:4104-4108.

[8] 喬立巖，馬云彤，彭喜元.離散二進制微粒群算法[J].電子測量與儀器學報，2005，增刊:1-5.

[9] KParsopoulos K E， Vrahatis M N.Unified Particle Swarm Optimization for Solving Constrained Engineering Optimization Problems[M].德國海德爾堡: Springer Berlin出版社， 2005.