王來軍，胡大偉，高 揚

(長安大學(xué)汽車運輸安全保障技術(shù)交通行業(yè)重點實驗室，陜西西安710064)

0 引言

場景規(guī)劃是一類針對多種可能發(fā)生情況進行綜合決策的方法，可用于求解隨機規(guī)劃問題.場景規(guī)劃方法在應(yīng)用時，通常先由決策者提出幾種未來可能發(fā)生的情形，這些情形被稱為場景，然后再針對這些場景做出問題的決策，決策目標是找出在所有場景下均能運作良好的方案.需要注意的是，決策時所有的場景都是沒有發(fā)生的，但通常能確定各場景的發(fā)生概率.場景規(guī)劃法有定性和定量兩種應(yīng)用方法.筆者將運用定量的場景規(guī)劃理論研究、解決隨機型的設(shè)施定位問題，且該類型問題同時屬于容量受限的多設(shè)施定位問題.

多設(shè)施定位問題(Multi-Facility Location Problem，MFLP)是常見的組合優(yōu)化問題，其顯著特點就是針對一定的需求量需要選擇確定多個設(shè)施作為服務(wù)點［1］.在MFLP中，如果設(shè)施點和需求點之間還滿足一對多的對應(yīng)服務(wù)關(guān)系，則該問題屬于多覆蓋問題(Multiple Coverage Problems，MCP)［2］.MFLP 研究的重點在于大規(guī)模問題，如Jia等［3］(2007年)曾針對醫(yī)療供給領(lǐng)域的大規(guī)模定位問題進行了研究，并考慮了多覆蓋情形.Kü?ükdeniz［4］(2012 年)針對一類具體的需求點固定的多設(shè)施定位問題進行了研究，提出了一種模糊c-均值叢集算法.

容量受限的設(shè)施定位問題(Capacitated Facility Location Problem，CFLP)則是生產(chǎn)規(guī)劃及通信網(wǎng)絡(luò)規(guī)劃領(lǐng)域的常見問題，多用于相關(guān)設(shè)施的選址，其典型約束就是在滿足所有需求的前提下每個設(shè)施的供給量是受限制的［5］.

對設(shè)施定位問題，如果費用、需求或其它方面涉及不確定或隨機因素，則稱之為隨機型設(shè)施定位問題(SFLP).Rawls and Turnquist［6］(2010 年)對緊急情況下SFLP在供應(yīng)鏈中的應(yīng)用進行了研究，Murali等［7］(2012年)研究了大城市基于距離覆蓋的醫(yī)療點分布問題，該問題主要考慮不同區(qū)域醫(yī)療需求的隨機性［7］.

基于對MFLP、CFLP和SFLP三類問題的分析，筆者針對交通運輸系統(tǒng)中的客運樞紐規(guī)劃問題進行研究，在保證實際應(yīng)用效果的基礎(chǔ)上，充分考慮問題的需求隨機性和站場容量約束，提出一類隨機型的容量受限多設(shè)施定位問題(SCMFLP)，并建立問題模型、設(shè)計問題求解算法，最終給出應(yīng)用結(jié)果及相關(guān)分析.

1 建立模型

問題描述:對給定區(qū)域，給定潛在的設(shè)施集合以及需求點集合，假定每個潛在設(shè)施點的供給量受到限制且設(shè)施位置給定，但各個需求點的需求量并不確定.從這些潛在的設(shè)施點中按照一定的范圍選擇位置來建立滿足容量約束的多個設(shè)施，使得在各個需求點的需求都能得到滿足的前提下，總體費用達到最小.

筆者之所以研究這類問題，是因為現(xiàn)實中常遇到類似的樞紐選址問題，這一點在后面的應(yīng)用部分有具體案例來說明.基于場景規(guī)劃理論，針對需求量不確定情形，給出場景集合 E={e1，e2，…，eS}，表示未來系統(tǒng)運行狀態(tài)存在S種情形或場景.每個場景es(1≤s≤S)都會按照一定的概率發(fā)生，而es發(fā)生的概率可通過一定途徑獲得，不妨表示為qs，則所有場景的發(fā)生概率滿足:=1.對于交通運輸系統(tǒng)中的樞紐規(guī)劃，將上述場景規(guī)劃方法運用，得到極小化問題模型如下:決策變量中:xsij表示在場景s下需求點i對設(shè)施j的分配量;yj是0-1變量，在設(shè)施點j建立設(shè)施取1，反之為0;Vj表示j的建設(shè)容量，其取值可通過約束條件(4)實現(xiàn).

其它量中，I表示需求點的集合;J表示潛在設(shè)施點的集合;cij表示從i到j(luò)的單位費用;fj表示在潛在施點j建立設(shè)施時的產(chǎn)生的綜合費用，它是包括征地費用、建設(shè)費用和運營費用等在內(nèi)的綜合性費用度量指標;dsi表示在場景s下需求點i的需求量.

目標函數(shù)式(1)中，第一部分表示將要發(fā)生的交通運輸費用的期望值，第二部分表示實際產(chǎn)生的綜合建設(shè)費用.約束條件中，式(2)表示給定需求點分配給所有設(shè)施點的需求量之和等于自身的總需求量;式(3)是對需要建立的站場總數(shù)量進行限制使之在一定的范圍之內(nèi)，其中，Nl，Nu分別表示下限和上限;式(4)表示站場的容量務(wù)必大于或等于它所要處理的需求點的需求量之和;式(5)是潛在設(shè)施點站場的容量(規(guī)模)限制，即任一設(shè)施點所建站場的處理能力都是限定的，筆者以分別表示其上下限，為已知量，具體應(yīng)用時可根據(jù)站場級別來處理;式(6)表明決策變量的取值范圍，同時表明模型屬于混合整數(shù)規(guī)劃.

事實上，具體應(yīng)用時，如果需求量相對集中，可以簡單地選取片區(qū)的重心作為需求點，并約定每個需求點單獨分配給某個設(shè)施點.這點可通過決策變量的設(shè)置來實現(xiàn)，從而將模型轉(zhuǎn)換為全整數(shù)規(guī)劃(0-1規(guī)劃).當每個需求點單獨分配給某個設(shè)施點時，則模型(1)～(6)可轉(zhuǎn)化為

此處決策變量為 xij，yj，Vj.其中，xij同前面的含義完全不同，它表示是否將需求點i整體分配給設(shè)施j，如分配，值為1，反之為0.同模型(1)～(6)相比，由于目標函數(shù)的計算難度降低、約束條件減少，模型(7)～(12)的計算量將大大減少，但代價是前期相對更大的調(diào)研量.

2 算法設(shè)計

SCMFLP問題屬于NP-Hard問題.求解此類問題，通常可以采用拉格朗日松弛等方法［8］，如Benat［9］(2003 年)等.但如果要求解規(guī)模較大的實際問題，近似算法則更實用，如 Ahuja［10］(2002年)等.筆者選擇了一種啟發(fā)式算法—遺傳算法，來求解本文的問題.選擇遺傳算法，除了算法自身的優(yōu)點外，主要是因為模型的約束條件可通過遺傳算子的針對性設(shè)計而得到完全滿足.根據(jù)問題特點，設(shè)計遺傳算子如下.

(1)編碼.筆者采用符號編碼方式，即如果一個設(shè)施點被選中建立站場，則標識為符號“1”;否則，標識“0”.這種編碼策略非常簡單明了，且可以有效地縮小遺傳搜索空間，降低算法的計算復(fù)雜性.具體形式如下所示.

圖1 染色體編碼圖例Fig.1 Illustration of coding

注意，染色體“1”的數(shù)量必須加以控制，以免不滿足(3)或(9)而產(chǎn)生無效染色體.

(2)交叉.為避免交叉導(dǎo)致染色體無效，可采取一定措施.如圖2將染色體分成3段，限定1，3段基因位中符號“1”的個數(shù)為1～2個，限定2段為2～3個.此時，各段中符號“1”的個數(shù)是限定的，所以交叉時只需將分段點作為交叉點，就可以保證交叉后個體編碼中各段、進而整體中符號“1”的個數(shù)保持不變，即保持染色體有效.

圖2 染色體分段交叉示例Fig.2 Illustration of sectional crossing

(3)變異.采用“成對變異”策略［11］.比如圖 3中，當4號基因位發(fā)生變異時，則非4號基因位(這里隨機選取7號基因位)發(fā)生相反變異.

圖3 染色體變異圖例Fig.3 Illustration ofmutation

(4)適應(yīng)度.適應(yīng)度函數(shù)形式如下:

式中:M為某個給定充分大正數(shù);f為目標函數(shù).f的計算是基于一定分配原則進行的.分配原則就是將客源需求點的需求量分配給站場要建立的設(shè)施的規(guī)則.通常，可采用就近原則，對于模型(1)～(6)，分配量滿足:

式中:k表示對站場j而言的分配輪次，初次分配時令 k=1，Vj，0=0.在同代計算中，每個站場的被分配次數(shù)不盡相同，取值最小為0，表示它沒有被分配客源，最大為達到該站場容量上限時的數(shù)值或所有客源均被分配完時的數(shù)值.

對于模型(7)～(12)，分配量滿足:

不同于式(14)，式(15)中不含有分配輪次k，因為需求點被一次性分配給某站場.

(5)全局收斂性.為了保證算法的全局收斂性，采用了最優(yōu)保留策略以及進化策略［11-13］.

3 應(yīng)用案例

3.1 模型及場景選擇

案例為中國西部某城市的國家級客運樞紐選址規(guī)劃問題，且規(guī)劃區(qū)有兩個特點:①規(guī)劃區(qū)經(jīng)濟發(fā)展不均衡，出行人口影響因素多，出行量變化規(guī)律性較差.②出行人口分布廣，且規(guī)劃區(qū)地形成狹長狀，根據(jù)宏觀政策和行政區(qū)域劃分，擬規(guī)劃建設(shè)3～7個客運樞紐站場.

根據(jù)特點①，本案例選擇隨機優(yōu)化策略.根據(jù)特點②，并考慮到前期數(shù)據(jù)調(diào)查的充分性，選擇模型(7)～(12).

場景選擇方面，根據(jù)行政區(qū)域劃分結(jié)合人口數(shù)量統(tǒng)計，設(shè)定30個需求點，然后對需求點的需求量(日均出行人口數(shù)量)，給出三類場景，相關(guān)數(shù)據(jù)見表1.表1中，場景S1對應(yīng)正常預(yù)測所得的需求量，S2和S3分別對應(yīng)經(jīng)濟發(fā)展增速和放緩情況下的需求量.

表1 三類場景下的需求量數(shù)據(jù)表Tab.1 Demand data under three scenarios

3.2 數(shù)據(jù)及參數(shù)處理

本案例數(shù)據(jù)均源自實際統(tǒng)計，并經(jīng)過了合理的單位換算或取整等簡單處理.基于當?shù)卣块T的總體建設(shè)規(guī)劃，結(jié)合當?shù)氐牡匦蔚孛驳龋景咐薪o出了10個潛在設(shè)施點(規(guī)劃客運站場).假定廣義距離(可達距離結(jié)合路況等)同單位交通運輸費用成正比，所以用廣義距離乘以一定的系數(shù)λ，可得到從30個需求點i到10個設(shè)施點j的單位交通運輸費用.廣義距同實際距離數(shù)據(jù)間進行了1∶1 000的比例縮放.假定站場每年使用350 d，每人次單位廣義距離出行費用0.5元，則系數(shù)λ=350×0.5.詳細的廣義距離表可參見文獻［11］.

進一步地，假定潛在設(shè)施點的建站規(guī)模或等級同投資費用成正比，但是如果是對已有站點進行改造或擴建，則另行對待.

在算法參數(shù)的設(shè)置方面，根據(jù)地形地貌及當?shù)匚飪r，10個潛在站場的固定建設(shè)費(含土地征用、建設(shè)或改擴建、運營等全部費用)及算法相關(guān)參數(shù)設(shè)置見表2.根據(jù)投資費用及改擴建情況可確定站場等級.

表2 算法及站場相關(guān)參數(shù)設(shè)置Tab.2 A lgorithm and station parameters setting

3.3 算法步驟

鑒于案例的規(guī)模并不太大，采用基本遺傳算法.事實上，筆者嘗試對算法加入了一些改進措施［12］，但對求解速度和最終結(jié)果無影響.本文算法步驟類似于文獻［11］.

3.4 結(jié)果及分析

按照上述步驟，建立了基于VB環(huán)境的計算程序，并對3種場景情形的問題進行了求解，得到主要結(jié)果如表3和圖4所示.

表3的結(jié)果是進行了多次計算得到的穩(wěn)定結(jié)果.事實上，當對表2的部分遺傳參數(shù)進行調(diào)整時，雖然運算速度變化較大，但最終的最優(yōu)解和最優(yōu)目標值都是確定的.表3表明，最終的決策方案為分別在2，4，6，8這4個潛在場址建立3個1級站和1個2級站，站場建設(shè)費用結(jié)合表2可知總計:2千萬+3.5千萬+4千萬+2千萬=11.5千萬，其中2號場址屬于擴建，所以雖然是1級站但投資費用僅為2千萬.基于此，容易得到總體交通費用(出行費用)大小為:23.07千萬 -11.5千萬=11.57千萬.

表3 優(yōu)化的結(jié)果Tab.3 The results of optim ization

圖4中，小黑點代表需求點(客源)，小圓圈代表潛在設(shè)施點(站場)，五角星代表從潛在設(shè)施點中優(yōu)選的擬建或擬改擴建的站場.與最優(yōu)費用相比較，隨機給出一種可行解，如在2，3，5，6，9 建站，對應(yīng)的總費用29 069.15萬元;對初始群體進行平均，對應(yīng)的總費用為28 553.28萬元.可見，本文的模型和算法合理實用，優(yōu)化效果明顯.

圖4 擬建站場示意圖Fig.4 View of the planned stations

注意，由于目標函數(shù)主要包括兩部分:出行費用、建設(shè)費用，在實際操作中應(yīng)該注意要控制兩部分費用的相對大小，以便保持兩部分費用對總體優(yōu)化效果影響的均衡.比如，在仿真過程中，給系數(shù)λ乘以5，仿真結(jié)果沒有變化，但當乘以500時，即使優(yōu)化模型及其它參數(shù)沒有任何變化，但優(yōu)化結(jié)果發(fā)生了變化，選擇的站場變化為1，4，6，8，站場的建設(shè)費用也增加了.出現(xiàn)這種狀況是因為此時的出行費用數(shù)以千億計，站場建設(shè)所差的一兩千萬對總體優(yōu)化的影響已經(jīng)非常微弱.

另外，筆者對3種場景下的確定型優(yōu)化問題進行了求解，即假定僅僅發(fā)生某個場景.結(jié)果表明，除了第二種場景外，最終費用都比隨機優(yōu)化要少，這是合理的，因為計算中沒有考慮站場容量不足所導(dǎo)致的“損失”，即沒有考慮其它場景發(fā)生時總體需求沒有得到全部滿足時帶來的相應(yīng)損失，這個損失類似于存貯問題中的缺貨損失.

4 結(jié)論

針對隨機型的多設(shè)施容量受限的設(shè)施定位問題，采用場景規(guī)劃方法對其進行了研究.首先，運用場景規(guī)劃方法對該問題的需求隨機性進行了處理，并據(jù)此建立了兩類優(yōu)化模型，通過約束條件的限制體現(xiàn)了站場總體規(guī)劃思想，使得模型更能反映實際情況.筆者對模型的各部分含義進行了分析、討論，對比兩類模型的優(yōu)缺點.進一步地，針對所建模型的NP屬性和構(gòu)造特點，設(shè)計了求解模型的符號編碼遺傳算法，該編碼方法非常直觀地體現(xiàn)了問題的特點并使得問題的求解規(guī)模得到有效控制.最后，通過具體的案例應(yīng)用及結(jié)果分析，表明了筆者所建優(yōu)化模型的正確性和求解算法的有效性.研究結(jié)果對解決實際的樞紐規(guī)劃問題具有重要參考價值.

［1］ ANDREASK，ANDREASD.Facility location models for distribution system design［J］.European Journal of Operational Research，2005，162(1):4-29.

［2］ In MIRCHANDANIPB，F(xiàn)RANCISR L，Discrete location theory［M］.New York:Wiley-Interscience，1990:263-304.

［3］ JIA H，ORDONEZ F，DESSOUKY MM.Solution approaches for facility location of medical supplies for large-scale emergencies［J］.Computers and Operations Research，2007，52:257-276.

［4］ Kü?ükdeniz T，ALP BARAY，ECERKALE K，et al.Integrated use of fuzzy cmeans and convex programming for capacitated multi-facility location problem［J］.Expert Systems with Applications，2012，39:4306-4314.

［5］ KLOSE A，GORTZ S.A branch-and-price algorithm for the capacitated facility location problem［J］.European Journal of Operational Research，2007，179:1109-1125.

［6］ RAWLSC G，TURNQUISTMA.Prepositioning of emergency supplies for disaster response［J］.Transport Research Part B，2010，44:521-534.

［7］ MURALIA P，Ordó?ezb F，DESSOUKY M.Facility location under demand uncertainty:Response to a large-scale bio-terror attack［J］.Socio-Economic Planning Sciences，2012，46:78-87.

［8］ FAN Y，LIU C.Solving stochastic transportation network protection problems using the progressive hedging-based method［J］.Networks and Spatial Economics，2010，10(2):193-208.

［9］ BENAT S.An improved branch＆ bound method for the uncapacitated competitive location problem［J］.Annals of Operations Research，2003，122(1/4):43-58.

［10］ AHUJA R K，ORLIN JB，PALLOTTINO S，et al.A multi-exchange heuristic for the single-source capacitated facility location problem［R］.MIT Sloan School of Management，Working Paper No.438702，October 2002.http://ssrn.com/abstract_id=337621.

［11］王來軍，胡大偉，史忠科.開放型設(shè)施定位問題的理論模型和應(yīng)用研究［J］.西北大學(xué)學(xué)報:自然科學(xué)版，2007，27(4):556-560.

［12］胡大偉，陳誠，王來軍.帶硬時間窗車輛路線問題的混合遺傳啟發(fā)式算法［J］.交通運輸工程學(xué)報，2007，7(5):112-117.

［13］楊麗娜，劉剛，王秋生.一種改進的遺傳算法及其應(yīng)用［J］.鄭州大學(xué)學(xué)報:工學(xué)版，2005，26(3):98-101.