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

（1.寧波大學(xué) 海運(yùn)學(xué)院，浙江 寧波 315211；2.寧波中通物流集團(tuán)有限公司，浙江 寧波 315211）

0 引 言

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

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

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

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

1 應(yīng)急物資儲(chǔ)備點(diǎn)選址考慮因素

應(yīng)急物資儲(chǔ)備點(diǎn)模型通常以系統(tǒng)總成本最低為目標(biāo)函數(shù)，建立模型時(shí)主要應(yīng)對(duì)以下四項(xiàng)費(fèi)用進(jìn)行考慮。

1.1 應(yīng)急物資儲(chǔ)備點(diǎn)建設(shè)成本

應(yīng)急物資儲(chǔ)備點(diǎn)建設(shè)成本包括建筑物、設(shè)備和土地征用等費(fèi)用，與應(yīng)急物資儲(chǔ)備點(diǎn)的位置和規(guī)模有關(guān)。

1.2 應(yīng)急物資儲(chǔ)備點(diǎn)經(jīng)營(yíng)成本

經(jīng)營(yíng)費(fèi)用是應(yīng)急物資儲(chǔ)備點(diǎn)在經(jīng)營(yíng)過程中發(fā)生的費(fèi)用，如物資儲(chǔ)備費(fèi)用、進(jìn)出庫(kù)費(fèi)、保管維護(hù)費(fèi)等，與應(yīng)急物資儲(chǔ)備點(diǎn)的經(jīng)營(yíng)規(guī)模有關(guān)。

1.3 調(diào)運(yùn)成本

調(diào)運(yùn)成本是應(yīng)急物資運(yùn)輸過程中所產(chǎn)生的費(fèi)用，主要包括運(yùn)價(jià)、物資運(yùn)送折損費(fèi)用等，與應(yīng)急物資儲(chǔ)備點(diǎn)的位置有關(guān)。

1.4 其他成本

應(yīng)急物資儲(chǔ)備點(diǎn)的員工工資、固定資產(chǎn)折舊等費(fèi)用。

為了將問題簡(jiǎn)化，本文僅考慮建造投資成本、物資儲(chǔ)備成本和物資調(diào)運(yùn)成本。

2 建模與分析

2.1 模型的建立

本模型假設(shè)已有n個(gè)應(yīng)急物資儲(chǔ)備可選點(diǎn)，從中選擇q個(gè)作為新建物資儲(chǔ)備點(diǎn)，并確定儲(chǔ)備點(diǎn)的儲(chǔ)備量。新建物資儲(chǔ)備點(diǎn)的總建設(shè)存儲(chǔ)費(fèi)用和最大容量有限制（作為約束條件）。目標(biāo)是在滿足應(yīng)急物資需求量（作為約束條件）的前提下，盡可能降低建造、儲(chǔ)備和調(diào)運(yùn)成本。

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

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

2.1.1 構(gòu)建目標(biāo)函數(shù)

zi為物資儲(chǔ)備點(diǎn)i的儲(chǔ)備物資量，i=1，2，...，q，...，n；

cbi為物資儲(chǔ)備點(diǎn)i的建設(shè)成本，i=1，2，...，q，...，n；

cs為物資儲(chǔ)備點(diǎn)的倉(cāng)儲(chǔ)成本，統(tǒng)一為2萬(wàn)元/萬(wàn)件；

ct為運(yùn)輸成本，統(tǒng)一為0.012 5萬(wàn)元/萬(wàn)件*公里；

aij為物資儲(chǔ)備點(diǎn)i向需求點(diǎn)j提供的物資數(shù)量，i=1，2，...，q，...，n；j=1，2，...，m；

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

如果物資儲(chǔ)備點(diǎn)i未被選中，則該點(diǎn)無(wú)儲(chǔ)備量，也不向需求點(diǎn)提供物資，即：

其中，r為全部需求點(diǎn)對(duì)應(yīng)急物資的需求總量。

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

2.2 模型的求解

根據(jù)需求點(diǎn)的需求量、點(diǎn)i到點(diǎn)j的運(yùn)輸距離、單位運(yùn)輸成本以及儲(chǔ)備點(diǎn)的建設(shè)和倉(cāng)儲(chǔ)成本等條件，按照2.1中構(gòu)建的模型求解應(yīng)急物資儲(chǔ)備點(diǎn)最優(yōu)的位置與儲(chǔ)備量。

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

2.2.1 模擬退火算法

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

根據(jù)應(yīng)急物資儲(chǔ)備點(diǎn)選址模型，本文算法的參數(shù)分別為：外層迭代次數(shù)為2 000次，內(nèi)層迭代次數(shù)為350次，初始溫度為100℃，溫度衰減系數(shù)為0.99。

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

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

圖1 模擬退火算法流程圖

2.2.2 遺傳算法

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

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

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

圖2 遺傳算法流程圖

3 案例介紹

本文算例以四川省作為分析對(duì)象。設(shè)定應(yīng)急物資需求點(diǎn)共15個(gè)，包括汶川、綿竹、北川等地。擬定應(yīng)急物資儲(chǔ)備點(diǎn)備選點(diǎn)有4個(gè)，包括成都、綿陽(yáng)等地，從中選擇數(shù)個(gè)作為新建物資儲(chǔ)備點(diǎn)。需求點(diǎn)及儲(chǔ)備點(diǎn)地理位置如圖3所示。

圖3 需求點(diǎn)及儲(chǔ)備點(diǎn)地理位置圖

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

表1 應(yīng)急物流中心備選點(diǎn)建設(shè)成本

表2 需求點(diǎn)應(yīng)急物資需求

表3 需求點(diǎn)與應(yīng)急物流中心備選點(diǎn)距離

4 結(jié)果對(duì)比分析

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

根據(jù)計(jì)算，精確解為2 849.237 5萬(wàn)元。選取的應(yīng)急物資儲(chǔ)備點(diǎn)為成都、綿陽(yáng)、眉山。其中，成都儲(chǔ)備點(diǎn)對(duì)應(yīng)的需求點(diǎn)為汶川、茂縣、都江堰、彭州、資陽(yáng)，總物資數(shù)為271萬(wàn)件；綿陽(yáng)儲(chǔ)備點(diǎn)對(duì)應(yīng)的需求點(diǎn)為綿竹、北川、青川、安縣、平武、江油、德陽(yáng)，總物資數(shù)為292萬(wàn)件；眉山儲(chǔ)備點(diǎn)對(duì)應(yīng)的需求點(diǎn)為雅安、樂山、寶興，總物資數(shù)為176萬(wàn)件。對(duì)應(yīng)連接圖如圖4所示。

圖4 應(yīng)急物資儲(chǔ)備點(diǎn)與對(duì)應(yīng)需求點(diǎn)連接圖

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

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

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

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

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

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

5 結(jié) 論

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