基于啟發式算法的應急物資儲備點選址模型研究

裴姝藝，葉曉飛，洪 鋼，周義雄，鄭彭軍

（1.寧波大學 海運學院，浙江 寧波 315211；2.寧波中通物流集團有限公司，浙江 寧波 315211）

0 引 言

隨著世界經濟的快速發展和科學技術的進步，重大突發事件的數量、經濟損失的數量和受災人口的百分比顯著增加。在緊急情況下，人們需要應急醫療援助和應急物資，因此需要盡快將這些資源和救援人員從救援中心運送到受影響地區。在此情況下，如何設計和選擇應急物資儲備點作為關鍵的應急物資配送節點就成為一個備受關注的問題，具有寶貴的理論意義和應用價值。

應急物資儲備點選址問題涉及如何選擇潛在儲備點的選址，以及如何通過儲備點運輸產品，從而將總相關成本降至最低。目前已經有許多學者提出了幾種經典算法來實現該問題，可分為定性方法和定量方法兩類。定性方法包括層次分析法[1]、專家選擇[2]、比較分析法[3]和模糊評價[4]。這些方法可以解決部分選址問題，但也包含著一些主觀因素。定量方法包括重力法[5]、混合整數規劃[6]、雙層規劃[7]和魯棒優化算法[8]。

但是，當問題規模較大時，鑒于NP難（多項式復雜程度的非確定性問題）的性質，解決問題變得更加困難，線性規劃方法已經較難滿足現實需要。由于精確技術有限，人們已經投入了相當多的精力來開發有效的元啟發式算法（或混合元啟發式算法），這些算法可以為大規模問題提供近乎最優的解決方案，如粒子群算法[9]、禁忌搜索算法，模擬退火算法、可變鄰域搜索、帝國主義競爭算法和遺傳算法等。

本文為更好地解決應急物資儲備點選址問題，構建了數學模型，盡可能降低建造、儲備和調運成本，并考慮儲備點最大容量的限制。同時本文求解采用啟發式模擬退火算法和啟發式遺傳算法，并對兩種方法進行比較，得出較優方法。從而得出的最優成本與精確解進行比較，來判斷算法所得解的可靠性，并對比兩個算法的運算速度和收斂情況。

1 應急物資儲備點選址考慮因素

應急物資儲備點模型通常以系統總成本最低為目標函數，建立模型時主要應對以下四項費用進行考慮。

1.1 應急物資儲備點建設成本

應急物資儲備點建設成本包括建筑物、設備和土地征用等費用，與應急物資儲備點的位置和規模有關。

1.2 應急物資儲備點經營成本

經營費用是應急物資儲備點在經營過程中發生的費用，如物資儲備費用、進出庫費、保管維護費等，與應急物資儲備點的經營規模有關。

1.3 調運成本

調運成本是應急物資運輸過程中所產生的費用，主要包括運價、物資運送折損費用等，與應急物資儲備點的位置有關。

1.4 其他成本

應急物資儲備點的員工工資、固定資產折舊等費用。

為了將問題簡化，本文僅考慮建造投資成本、物資儲備成本和物資調運成本。

2 建模與分析

2.1 模型的建立

本模型假設已有n個應急物資儲備可選點，從中選擇q個作為新建物資儲備點，并確定儲備點的儲備量。新建物資儲備點的總建設存儲費用和最大容量有限制（作為約束條件）。目標是在滿足應急物資需求量（作為約束條件）的前提下，盡可能降低建造、儲備和調運成本。

可選擇新建應急物資儲備點的點集合S={si|i=1，2，...，q，...，n}。應急物資需求點集合為F={Fj|j=1，2，...，m}。

為了不斷優化和完善數值模式的中小尺度預報能力,需要對微物理參數化方案進行對比研究,以便找到影響某一區域強降水過程預報能力的主要微物理過程。因此本文利用中尺度WRF數值模式,分別采用Morrison和Milbrandt-Yau雙參微物理方案對遼寧省的一次強降水過程進行數值模擬,通過對地表累積降水量、降水強度和云中微物理量以及微物理過程的分析,對比研究了以上兩種雙參云微物理方案對強降水的預報效果,并找到降水預報差異的具體云微物理過程。

2.1.1 構建目標函數

zi為物資儲備點i的儲備物資量，i=1，2，...，q，...，n；

cbi為物資儲備點i的建設成本，i=1，2，...，q，...，n；

cs為物資儲備點的倉儲成本，統一為2萬元/萬件；

ct為運輸成本，統一為0.012 5萬元/萬件*公里；

aij為物資儲備點i向需求點j提供的物資數量，i=1，2，...，q，...，n；j=1，2，...，m；

dij為物資儲備點i到需求點j的最短距離，i=1，2，...，q，...，n；j=1，2，...，m。

如果物資儲備點i未被選中，則該點無儲備量，也不向需求點提供物資，即：

其中，r為全部需求點對應急物資的需求總量。

非負約束，Xi為0—1變量，其他所有變量≥0。

2.2 模型的求解

根據需求點的需求量、點i到點j的運輸距離、單位運輸成本以及儲備點的建設和倉儲成本等條件，按照2.1中構建的模型求解應急物資儲備點最優的位置與儲備量。

求解采用啟發式模擬退火算法和啟發式遺傳算法。

2.2.1 模擬退火算法

模擬退火算法（Simulated Annealing，SA）是一種模擬金屬緩慢冷卻的優化方法，其特征是原子運動逐漸減少，從而降低晶格缺陷的密度，直至達到最低能量狀態。以類似的方式，在每個虛擬退火溫度下，模擬退火算法根據預定義的標準，通過改變當前狀態來為所考慮的問題生成新的潛在解決方案。然后，新狀態基于預定義的標準判斷是否保留，并且此過程迭代直到收斂。

根據應急物資儲備點選址模型，本文算法的參數分別為：外層迭代次數為2 000次，內層迭代次數為350次，初始溫度為100℃，溫度衰減系數為0.99。

模擬退火算法首先隨機生成一個初始解決方案，從中探索該初始解決方案的周圍環境，接受更好的解決方案并以某種概率接受較差的解決方案。為了避免出現局部最小值的情況，搜索方向不一定朝向更好；當溫度較高時，得到優解或差解的概率相對較高，這使得算法能夠進行全局搜索。隨著溫度的降低，接收到更高級的溶液，并且接收較差解決方案的概率變得很低，因此它逐漸收斂到最佳狀態。

模擬退火算法包含兩個迭代循環，即退火過程的冷卻過程和Metropolis準則。根據Metropolis準則，粒子在溫度T時趨于平衡的概率為exp(-ΔE/T)，其中E為溫度T時的內能，ΔE為其改變量。用固體退火模擬組合優化問題，將內能E模擬為目標函數值，溫度演化成控制參數。從某個初始解出發，經過大量解的變換后，可以求得給定控制參數值時組合優化問題的相對最優解。然后減小控制參數的值，重復執行Metropolis算法，就可以在控制參數趨于零時，最終求得組合優化問題的整體最優解。模擬退火算法的流程如圖1所示。

圖1 模擬退火算法流程圖

2.2.2 遺傳算法

遺傳算法（Genetic Algorithm，GA）是根據生物進化特性提出的一種算法，根據基因序列組合特性生成新解。

根據應急物資儲備點選址模型，本文算法的參數分別為：種群規模為50，最大迭代次數為2 000次，選擇策略為輪盤賭法，交叉概率為0.5，變異概率為0.4。

遺傳算法是隨機搜索算法，旨在模仿自然選擇和自然遺傳學的機制。遺傳算法在字符串結構上運行，例如生物結構，這些結構通過使用隨機但結構化的信息交換，遵循適者生存規則在時間上進化。遺傳算法的主要步驟包括選擇、交叉和變異。選擇操作從種群中根據一定概率選出優良個體組成新的種群，以繁殖得到下一代個體，個體被選中的概率與適應度值成正相關。本文選擇采用輪盤賭選擇法，也叫適應度比例法，依據個體的適應度值計算每個個體在子代中出現的概率，并按照此概率隨機選擇個體構成子代種群。交叉操作是指從種群中隨機選擇兩個個體，通過兩個染色體的交叉互換組合，把父串的優秀特征遺傳給子串，從而產生新的優秀個體。變異操作是指在種群中隨機選擇個體，基于變異概率對個體進行變異。遺傳算法的流程如圖2所示。

圖2 遺傳算法流程圖

3 案例介紹

本文算例以四川省作為分析對象。設定應急物資需求點共15個，包括汶川、綿竹、北川等地。擬定應急物資儲備點備選點有4個，包括成都、綿陽等地，從中選擇數個作為新建物資儲備點。需求點及儲備點地理位置如圖3所示。

圖3 需求點及儲備點地理位置圖

應急物流中心的建設成本、各區域的應急物資需求量以及與備選點的對應距離[8]分別如下表1、表2和表3所示，各地點的經緯度參考騰訊地圖。

表1 應急物流中心備選點建設成本

表2 需求點應急物資需求

表3 需求點與應急物流中心備選點距離

4 結果對比分析

本文使用較小規模的案例，故而線性規劃方法可行，以便求得精確的成本最小解，并以此來判斷兩種啟發式算法求解的正確程度。

根據計算，精確解為2 849.237 5萬元。選取的應急物資儲備點為成都、綿陽、眉山。其中，成都儲備點對應的需求點為汶川、茂縣、都江堰、彭州、資陽，總物資數為271萬件；綿陽儲備點對應的需求點為綿竹、北川、青川、安縣、平武、江油、德陽，總物資數為292萬件；眉山儲備點對應的需求點為雅安、樂山、寶興，總物資數為176萬件。對應連接圖如圖4所示。

圖4 應急物資儲備點與對應需求點連接圖

本文使用模擬退火算法和遺傳算法各運行4次，得出最優成本、運行時間及收斂情況，分別如圖5、圖6所示。

圖5 模擬退火算法最終解及收斂程度圖

圖6 遺傳算法最終解及收斂程度圖

由圖5、圖6可知，模擬退火算法所得解更精確，4次運算的最優成本皆為2 849.237 5萬元，與前文所得精確解一致，可得該算法所得解可靠性較高。4次運算運行時間平均為35秒左右，且都穩定在迭代900多次后收斂。

而遺傳算法4次運算只有2次最優成本符合精確解，且所得解局部最優缺陷較為明顯。并且運行時間平均為124秒左右，收斂規律也不明顯、變動較大。

因此，本研究結果表明，模擬退火算法與遺傳算法相比，其求得全局最優解的正確率更高，運算速度更快、收斂情況更穩定。

5 結 論

本文在考慮建設、儲備和調度成本最小化的基礎上，建立了應急物資儲備點選址模型，同時還設定了儲備點最大容量約束，使其更符合實際情景。并對四川省進行了算例分析，驗證了所提方法的有效性。求解分別采用啟發式模擬退火算法和遺傳算法，在多次迭代下選取最小成本結果。并在精確解的參考下，判斷了兩種啟發式算法所得最終解的正確情況、運行速度和收斂情況。實驗結果表明：由最小成本化模型得到的最優成本為2 849.237 5萬元；遺傳算法容易陷入局部最優問題，而模擬退火算法求得全局最優解的可靠性較高、運行速度較快、收斂情況也更穩定。