[發(fā)明專利]一種混合多目標粒子群算法解決應急調(diào)度問題方法

在審

• 申請?zhí)枺?/td>: 201410592896.7
• 申請日: 2014-10-28
• 公開（公告）號: CN104392099A
• 公開（公告）日: 2015-03-04
• 發(fā)明（設計）人: 宋曉宇;王守金;曹陽;趙明
• 申請（專利權）人: 沈陽建筑大學
• 主分類號: G06F19/00
• 分類號: G06F19/00
• 代理公司: 沈陽杰克知識產(chǎn)權代理有限公司 21207
• 代理人: 楊乃力

技術領域

本發(fā)明屬于優(yōu)化調(diào)度技術領域，尤其是一種應急物資調(diào)度問題求解方法，特點適用于非線性連續(xù)消耗應急物資調(diào)度問題方面。?

背景技術

大規(guī)模突發(fā)性公共事件除了具有一般突發(fā)事件的突然性、危害性、不確定性、衍生性等特征以外,更具有受災面積大、影響范圍廣、持續(xù)時間長、受災人群多、應急需求點多、應急物資需求量大、應急物資供應不足的特點。這些特點決定了大規(guī)模突發(fā)事件應急物資的調(diào)度的復雜性遠遠超出一般規(guī)模的突發(fā)事件,不僅要考慮單出救點到多需求點的調(diào)度,還要考慮多出救點到多需求點的調(diào)度；不僅要考慮不同應急階段應調(diào)度不同種類的應急物資,還要考慮不同階段應采用不同的調(diào)度方式。盡管應急物資調(diào)度已由單一優(yōu)化目標發(fā)展到如今多個優(yōu)化目標,但是以應急點滿意度為優(yōu)化目標構建的應急物資調(diào)度模型還比較少見.此外,目標權重由決策者的偏好決定，如何科學地確定目標權重也有一定地難度。?

何建敏等針對線性連續(xù)消耗應急物資調(diào)度問題,建立了單應急點的應急物資調(diào)度模型,并給出模型的解決方法,實現(xiàn)應急物資一次性消耗向連續(xù)性消耗的轉(zhuǎn)變,但是現(xiàn)實生活中應急物資往往是非線性連續(xù)消耗的,恒定的消耗速度與應急物資調(diào)度的實踐有一定的差距.隨著大規(guī)模自然災害的頻繁發(fā)生,單應急點的調(diào)度模型難以完成大規(guī)模的應急物資調(diào)度.李進等在滿足物資量限制、配送時間約束的情況下,能夠解決多應急點、多出救點的應急物資調(diào)度問題,但是忽略了各個應急點的實際災情,要制定切實可行的應急物資調(diào)度方案,必須考慮應急點的差異性.應急點對應急物資調(diào)度的滿意程度已經(jīng)成為當今應急決策首要考慮的關鍵因素.王旭平等重點研究了災民對救援時間的感知滿意度衡量方?法。?

發(fā)明內(nèi)容

本發(fā)明就是針對上述問題提出來的，目的是提供非線性連續(xù)消耗應急物資調(diào)度問題求解方法，為決策者提供一種應急物資調(diào)度的方法。?

一種混合多目標粒子群算法解決應急調(diào)度問題方法，包括以下步驟：?

步驟1:設置算法的相關參數(shù),生成規(guī)模為M的初始粒子群,評價粒子群中所有個體,并將當前各個個體的位置和目標值保存到各個體的個體最優(yōu)值pt?ib中；?

相關參數(shù)：初始化個體飛行速度為0,初始化種群的迭代代數(shù)t＝0。?

步驟2:根據(jù)帶約束的Pareto支配關系篩選出初始粒子群中非劣個體,用于初始化外部精英集；?

外部精英集，保存Pareto非劣個體。重新設計粒子群中個體最佳位置的更新方式和全局最佳位置的選取方式，使得粒子群算法能夠求解基于Pareto最優(yōu)解的多目標應急物資調(diào)度問題。?

步驟3:若t<maxgen/3(maxgen迭代代數(shù)),且t％It≠0,則不滿足局部搜索條件,執(zhí)行步驟4,否則轉(zhuǎn)步驟6；?

步驟4:當外部精英集中個數(shù)超過3個的時候,計算每個個體的擁擠距離di,并降序排列外部精英集；?

步驟5:從擁擠距離di較大的備選集中隨機選出全局最佳位置pt?g,調(diào)整速度更新公式中自適應參數(shù),然后更新個體的速度和位置,并轉(zhuǎn)步驟7；?

步驟6:粒子群中個體以概率plser進行非梯度側(cè)步爬山搜索；?

步驟7:產(chǎn)生0～1之間的隨機數(shù),若小于變異概率pMut,則粒子群進行小概?率變異,并維護越界變量；?

步驟8:評價粒子群中所有個體,然后更新個體最優(yōu)值pt?ib和外部精英集,并將t加1,如果t<maxgen,重復步驟3,否則,結(jié)束算法,輸出外部精英集,獲得Pareto解集.?

有益效果：?

(1)該模型將物資調(diào)度總費用(物資運輸費用、物資缺失損失和物資超額費用)最小化和應急點滿意度最大化作為優(yōu)化目標,不僅考慮節(jié)省物資調(diào)度費用,而且更加關注應急點對物資調(diào)度的滿意程度,使得該模型更具實際意義；?

(2)設計了能夠反映物資調(diào)度效果的物資缺失懲罰和滿意度函數(shù),在優(yōu)先供給需求緊迫度較高的應急點的同時,還限制了其他應急點的物資供應時延,確保物資缺失損失是可接受的；?

(3)應急物資調(diào)度需要同時考慮物資調(diào)度總費用和應急點滿意度兩個目標,根據(jù)粒子群算法和非梯度側(cè)步爬山算法各自的優(yōu)勢,將一種改進的粒子群算法與非梯度側(cè)步爬山算法相結(jié)合,提出一種基于Pareto支配的混合多目標粒子群算法用于求解多目標應急物資調(diào)度問題。?

附圖說明

圖1非線性連續(xù)消耗下大規(guī)模應急物資調(diào)度方法過程示意圖；?

圖2多目標應急物資調(diào)度模型的Pareto解的分布實例圖。?

具體實施方式