王來軍，胡大偉，高 揚(yáng)

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

0 引言

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

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

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

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

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

1 建立模型

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

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

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

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

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

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

2 算法設(shè)計(jì)

SCMFLP問題屬于NP-Hard問題.求解此類問題，通?？梢圆捎美窭嗜账沙诘确椒ǎ?］，如Benat［9］(2003 年)等.但如果要求解規(guī)模較大的實(shí)際問題，近似算法則更實(shí)用，如 Ahuja［10］(2002年)等.筆者選擇了一種啟發(fā)式算法—遺傳算法，來求解本文的問題.選擇遺傳算法，除了算法自身的優(yōu)點(diǎn)外，主要是因?yàn)槟Ｐ偷募s束條件可通過遺傳算子的針對性設(shè)計(jì)而得到完全滿足.根據(jù)問題特點(diǎn)，設(shè)計(jì)遺傳算子如下.

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

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

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

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

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

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

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

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

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

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

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

不同于式(14)，式(15)中不含有分配輪次k，因?yàn)樾枨簏c(diǎn)被一次性分配給某站場.

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

3 應(yīng)用案例

3.1 模型及場景選擇

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

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

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

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

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

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

進(jìn)一步地，假定潛在設(shè)施點(diǎn)的建站規(guī)?；虻燃壨顿Y費(fèi)用成正比，但是如果是對已有站點(diǎn)進(jìn)行改造或擴(kuò)建，則另行對待.

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

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

3.3 算法步驟

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

3.4 結(jié)果及分析

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

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

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

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

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

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

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

4 結(jié)論

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

［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é)報(bào):自然科學(xué)版，2007，27(4):556-560.

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

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