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

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

0 引 言

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

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

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

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

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

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

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

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

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

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

1.3 調運成本

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

1.4 其他成本

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

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

2 建模與分析

2.1 模型的建立

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

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

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

2.1.1 構建目標函數

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

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

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

ct為運輸成本，統(tǒng)一為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中構建的模型求解應急物資儲備點最優(yōu)的位置與儲備量。

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

2.2.1 模擬退火算法

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

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

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

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

圖1 模擬退火算法流程圖

2.2.2 遺傳算法

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

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

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

圖2 遺傳算法流程圖

3 案例介紹

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

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

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

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

表2 需求點應急物資需求

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

4 結果對比分析

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

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

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

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

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

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

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

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

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

5 結 論

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