魏明，陳學(xué)武，孫博

（1.東南大學(xué)城市智能交通江蘇省重點(diǎn)實(shí)驗(yàn)室，南京210096；2.南通大學(xué)交通學(xué)院，江蘇南通226019）

公交加氣站選址布局優(yōu)化模型和算法

魏明*1,2，陳學(xué)武1，孫博2

（1.東南大學(xué)城市智能交通江蘇省重點(diǎn)實(shí)驗(yàn)室，南京210096；2.南通大學(xué)交通學(xué)院，江蘇南通226019）

針對(duì)不同線路的車輛加氣需求在時(shí)間和空間上的不平衡性，將加氣站抽象為多服務(wù)臺(tái)排隊(duì)系統(tǒng)，綜合考慮車輛行駛、排隊(duì)加氣、加氣站的位置對(duì)公交運(yùn)營的影響等現(xiàn)實(shí)因素，以加氣站的建設(shè)費(fèi)用最小為第一目標(biāo)，以極小化所有公交車的加氣成本為第二目標(biāo)，建立一種多目標(biāo)公交加氣站選址模型.根據(jù)問題特征，利用約束法，將之轉(zhuǎn)化為單目標(biāo)問題，設(shè)計(jì)求解該問題的遺傳算法，定義解的編碼方案、適應(yīng)度函數(shù)、產(chǎn)生初始種群的啟發(fā)式算法等.最后，結(jié)合一個(gè)算例，計(jì)算最佳的公交加氣選址方案，分析加氣站的能力對(duì)其布局的影響程度，從而驗(yàn)證模型和算法的有效性.

城市交通；加氣站選址；車輛排隊(duì)加氣；多目標(biāo)；遺傳算法

1 引言

城市居民出行在時(shí)間和空間上不均衡，以及時(shí)疏散乘客為目標(biāo)，必須統(tǒng)籌與之相匹配的線網(wǎng)密度、車隊(duì)規(guī)模及其運(yùn)營計(jì)劃，因而各線路在不同時(shí)段利用其客流的高平鋒間隙滿足它們顯著差異的加氣需求.若公交加氣站的建設(shè)規(guī)模及布局缺乏科學(xué)規(guī)劃，造成部分加氣站數(shù)量不足導(dǎo)致車輛排起長龍，不能及時(shí)返回車場(chǎng)按計(jì)劃正常運(yùn)營；而部分加氣站數(shù)量過多或布局不當(dāng)，出現(xiàn)土地資源浪費(fèi)、加氣成本上升等問題[1，2].因此，針對(duì)多線路車輛的加氣需求在時(shí)空分布上的特征，如何合理布設(shè)公交加氣站的規(guī)模與數(shù)量，顯得尤為重要.

該問題為公交加氣站選址布局問題（Bus Gas Station Site Layout Problem，BGSSLP），與天燃?xì)?Compressed NaturalGas，CNG)加氣站布點(diǎn)問題類似，均屬于組合優(yōu)化的NP-Hard問題，前者研究較為少見，而后者吸引了眾多國內(nèi)外學(xué)者的關(guān)注.前者研究可借鑒后者的研究思路，主要有二：

首先，科學(xué)計(jì)算最佳CNG加氣站選址方案，該研究較少，童岱等采用定性分析與定量計(jì)算相結(jié)合的方法綜合探討了CNG優(yōu)化布局選址方法[3]；Am ir等人研究車輛進(jìn)入CNG加氣站的排隊(duì)特征并給出布局優(yōu)化方法[4]；趙濤等人研究模擬退火算法在天然氣加氣站選址中的應(yīng)用[5]；吳芳構(gòu)建了一類城市CNG加氣站布點(diǎn)優(yōu)化模型[6]；黃海波等根據(jù)最短路徑理論建立了加氣站和車站車源分配模型[7].

其次，評(píng)價(jià)CNG加氣站布點(diǎn)的合理性，這方面研究相對(duì)成熟，已經(jīng)在該領(lǐng)域綜合運(yùn)用模糊數(shù)學(xué)、色關(guān)聯(lián)分析等[8-11]方法，并開發(fā)軟件推廣應(yīng)用[12].

由上可知，現(xiàn)有研究沒有考慮加氣站的通行能力對(duì)其布局的影響，也未涉及加氣站的布局如何影響公交運(yùn)營.

針對(duì)現(xiàn)有研究的不足，本文考慮加氣站的選址布局對(duì)公交運(yùn)營的影響，將車輛在加氣站的補(bǔ)充燃料排隊(duì)過程抽象為多服務(wù)臺(tái)排隊(duì)系統(tǒng)，以追求加氣站建設(shè)費(fèi)用和車輛加氣成本最少為目標(biāo)，建立了多目標(biāo)公交加氣站選址布局優(yōu)化模型，并設(shè)計(jì)求解該問題的遺傳算法.最后，通過一個(gè)實(shí)例計(jì)算最佳的公交加氣選址方案，分析加氣站的能力對(duì)其布局的影響程度，檢驗(yàn)本研究的有效性.

2 問題描述及數(shù)學(xué)模型

某區(qū)域總共有S個(gè)站場(chǎng)和M個(gè)候選加氣站地點(diǎn).每個(gè)站場(chǎng)?s∈S經(jīng)營Rs條線路，對(duì)每條線路?j∈Rs，在時(shí)間段離開站場(chǎng)去氣站加氣的車輛數(shù)為nj.根據(jù)公交運(yùn)營的時(shí)間約束，這些車輛在加氣站的排隊(duì)時(shí)間均不超過一定時(shí)間T，要求它們?cè)跁r(shí)間段內(nèi)必須返回站場(chǎng).每個(gè)候選地點(diǎn)?i∈M的土地經(jīng)濟(jì)費(fèi)用為ci元、停車能力約束為li，可購置yi個(gè)加氣設(shè)備（其費(fèi)用為p元），每臺(tái)設(shè)備給車輛加氣的平均時(shí)間為o小時(shí).站場(chǎng)?s∈S和候選地點(diǎn)?i∈M之間距離為ds,i≤D（D為車輛的最大行駛距離），車輛在兩地之間行駛速度為vs,i，單位運(yùn)輸費(fèi)用為r元.線路?j∈Rs（?s∈S）的唯一加氣站點(diǎn)為φ(j)，φ(φ(j),i)表示φ(j)是否為候選地點(diǎn)?i∈M.線路?j∈Rs的車輛一次完整加氣時(shí)間為Tj=2ds,φ(j)/vs,φ(j)+o+ΔTj，包括行駛時(shí)間加氣時(shí)間o和平均等車時(shí)間ΔTj≤T.所有車輛在各個(gè)加氣站?i∈M的車輛排隊(duì)長度為Li≤li.xi表示某個(gè)地點(diǎn)?i∈M是否被選為加氣站.

將加氣站抽象為一個(gè)多服務(wù)臺(tái)排隊(duì)系統(tǒng)，按先進(jìn)先出原則，假設(shè)車輛到達(dá)加氣站服從泊松分布和服務(wù)時(shí)間為負(fù)指數(shù)分布，根據(jù)各個(gè)站場(chǎng)不同線路的車輛加氣需求在時(shí)間和空間上的不平衡性，確定某個(gè)地點(diǎn)是否被選為加氣站，以及其加氣設(shè)備的數(shù)量，考慮最大行駛里程、排隊(duì)長度和等車時(shí)間等現(xiàn)實(shí)約束，追求加氣站的建設(shè)費(fèi)用和所有公交車的加氣成本最小.

綜上所述，本文的數(shù)學(xué)模型如下：

在上述模型中，式(1)–式(2)是問題的目標(biāo)函數(shù).式(1)表示極小化公交加氣站的建設(shè)管理費(fèi)用；式(2)表示各個(gè)站場(chǎng)的車輛去附近加氣站的運(yùn)行成本最少.式(3)–式(8)是約束條件.式(3)表示至少建設(shè)一個(gè)加氣站；式(4)確保任意線路都能在附近加氣站補(bǔ)充燃料；式(5)表示站場(chǎng)和加氣站之間距離小于一定距離；式(6)限制公交車從站場(chǎng)出發(fā)后完成加氣的返回時(shí)間；式(7)表示加氣站的服務(wù)能力約束；式(8)表示車輛在加氣站排隊(duì)等候加氣的平均時(shí)間小于一定值；式(9)表示兩個(gè)決策變量的0–1和整數(shù)約束.

3 求解BGSSLP的遺傳算法

由上可知，BGSSLP屬于任務(wù)分配問題范疇，為一類NP難題[9].針對(duì)很難于構(gòu)建BGSSLP的高效啟發(fā)式算法的缺陷，文中利用遺傳算法(Genetic A lgorithm,GA)[13]求解BGSSLP，借鑒GA求解該復(fù)雜問題的通用框架，根據(jù)問題特征，定義解的編碼方案、適應(yīng)度函數(shù)、產(chǎn)生初始種群的啟發(fā)式算法等，其詳細(xì)過程如下.

3.1 編碼方案

采用自然數(shù)編碼方式,用向量X=(x1,x2,...,xM)表示一個(gè)解的染色體，元素xi≥0為候選地點(diǎn)i的加氣設(shè)備數(shù)量，若xi=0，則該候選站點(diǎn)未被選中.由上可知,任意X都遵守約束式(3)，對(duì)?xi≠0，基于貪婪規(guī)則確定(?s∈S,?j∈Rs)φ(j)=i，將X解碼為各個(gè)加氣站服務(wù)的站場(chǎng)集合，若它滿足約束式(5)–式(9)，則X對(duì)應(yīng)一個(gè)可行解.

例如：染色體X=[1 0 1 0 0 0 3 0]蘊(yùn)含8個(gè)候選站點(diǎn)，1、3和7候選站點(diǎn)被選中，它們建設(shè)加氣設(shè)備的數(shù)量為1、1和3.

3.2 適應(yīng)度函數(shù)的設(shè)計(jì)

在現(xiàn)實(shí)中，交通部門投入建設(shè)氣站費(fèi)用一般是有限的.因此，以f2為主目標(biāo)，將f1轉(zhuǎn)為約束，構(gòu)造BGSSLP的單目標(biāo)規(guī)劃模型[14].

其它約束與原來的相同.式(11)表示交通部門投資建設(shè)公交加氣站的總費(fèi)用不超過一定值c，其中c由政府預(yù)算決定.由式（10）推導(dǎo)可知，加氣站點(diǎn)的總數(shù)量取值在一定范圍內(nèi).

本文以Fit(f)=f2為適應(yīng)度函數(shù)，利用其評(píng)價(jià)個(gè)體的好壞，求解BGSSLP的非劣解.

3.3 產(chǎn)生初始種群的啟發(fā)式算法

BGSSLP的影響因素眾多，隨機(jī)產(chǎn)生的個(gè)體很難滿足全部約束，初始種群的質(zhì)量不高影響GA的求解效率.因此，構(gòu)造啟發(fā)式算法求得不同可行個(gè)體，具體步驟如下.

步驟1根據(jù)S個(gè)站場(chǎng)的坐標(biāo)位置，遵從約束式（5），利用聚類算法，將它們劃分為K個(gè)子區(qū)域S=(S1,S2,…,SK).設(shè)置c'=0.令k=1，轉(zhuǎn)向步驟2.

步驟2對(duì)每個(gè)子區(qū)域Sk，查找可行的候選加氣站集合Vk，轉(zhuǎn)向步驟3.

步驟3從Vk中隨機(jī)選擇加氣站i，計(jì)算車輛到達(dá)率決定ΔTj、Li，根據(jù)li和T確定yi的下限根據(jù)約束式（11）確定yi的上限隨機(jī)產(chǎn)生個(gè)體X的基因轉(zhuǎn)向步驟4.

步驟4對(duì)Sk的全部加氣需求，若加氣站i的設(shè)備滿足約束式（6）–式（8），轉(zhuǎn)向步驟5；否則，根據(jù)約束式（4），基于貪婪原則將Sk的剩余加氣需求并入相鄰子區(qū)域，或單獨(dú)作為一個(gè)子區(qū)域，轉(zhuǎn)向步驟5.

步驟5令k=k+1，若k≤K，轉(zhuǎn)向步驟2；否則，算法終止，輸出可行個(gè)體X.

顯然，根據(jù)上述啟發(fā)式算法獲取的個(gè)體都是BGSSLP的可行解.

3.4 遺傳操作

遺傳操作包括選擇、交叉和變異，其中選擇運(yùn)算采用輪盤賭選擇法和精英保留法組合的策略，從父代種群中優(yōu)選出下一代個(gè)體；交叉運(yùn)算采用單點(diǎn)交叉策略，以一定概率選擇交叉點(diǎn)，交換一組染色體對(duì)應(yīng)基因段，產(chǎn)生一組新解；變異運(yùn)算直接使用基本位變異策略，依據(jù)變異概率，判斷個(gè)體的每一個(gè)基因座是否為變異點(diǎn)，并對(duì)之做相關(guān)運(yùn)算，進(jìn)而產(chǎn)生出新個(gè)體.

顯然，交叉和變異操作可能破壞解的可行結(jié)構(gòu)，舍棄這些新產(chǎn)生的不可行個(gè)體.

3.5 終止原則

種群完成預(yù)先給定的進(jìn)化代數(shù).

4 算例分析

某城市區(qū)域有14個(gè)站場(chǎng)和10個(gè)候選加氣地點(diǎn)，其網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)如圖1所示，不同站場(chǎng)經(jīng)營21條線路在加氣高峰時(shí)段的最大需求如表1，候選地點(diǎn)的基本信息如表2，其它參數(shù)為p=50 000元/個(gè)、T=10m in、D=6 km、o=5m in和r=22元/h.

圖1 站場(chǎng)和候選地點(diǎn)的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)Fig.1 Network topology network topology between busand gas stations

在MATLAB中，利用Sheffield的GA工具箱函數(shù)編寫求解BGSSLP的仿真程序，設(shè)置相關(guān)參數(shù)為迭代次數(shù)10 000、染色體數(shù)100、交叉率0.7和變異率0.05，在政府預(yù)算c=3 800 000情形下計(jì)算機(jī)運(yùn)行實(shí)例10次，獲得該問題的最優(yōu)氣站布局方案如表3所示，從表中可知：針對(duì)21條線路在加氣高峰時(shí)段的時(shí)空分布需求，總投資3 650 000元，建設(shè)5個(gè)加氣站和購買13套加氣設(shè)備，這些線路的128輛車加氣運(yùn)營費(fèi)用為741.8元，共行駛579 km，其用時(shí)2 845.4m in（等車時(shí)間占14.84%）.

表1 各線路在加氣高峰時(shí)段的最大需求Table 1 The num ber ofeach line's fuelling vehicles in aerated peak periods

表2 候選地點(diǎn)的基本信息Table 2 Basic information of candidate gas stations

由上可知，當(dāng)某加氣站的公交車到達(dá)率較高時(shí)，若其服務(wù)水平低，此時(shí)加氣站的服務(wù)強(qiáng)度較大，致使車輛等待時(shí)間（排隊(duì)長度）較長，各線路的車輛在加完氣后可能不能按規(guī)定時(shí)間返回車場(chǎng).雖然增加一定數(shù)量的加氣設(shè)備數(shù)可以縮短車輛運(yùn)營時(shí)間，這確保為下一階段的公交運(yùn)營提供運(yùn)力支撐，但與加氣設(shè)備的使用率矛盾，故綜合考慮公交運(yùn)營、加氣站的通行能力和加氣設(shè)備閑置之間最佳聯(lián)系，計(jì)算結(jié)果和直觀分析一致.

此外，考察c、D和T對(duì)BGSSLP的影響，如表4和表5所示，從表中可知：

（1）當(dāng)加氣設(shè)備數(shù)不低于某值時(shí)才滿足所有車輛的加氣需求，隨著c的變小，布局方案偏向于ci較小的候選地點(diǎn)或減少加氣站數(shù)，這可能引起空駛距離增大，故f1和f2分別逐步變小和變大.

表3 最優(yōu)公交加氣站選址布局方案Table 3 Optim al layoutscheme for bus gas stations

表4 不同c的最優(yōu)公交加氣站選址布局方案Table 4 Optimal layoutscheme for bus gas stations under differentvalues of c

（2）隨著D的變小，各個(gè)加氣站輻射公交站場(chǎng)的范圍縮小，必須增加一定數(shù)量的公交站點(diǎn)才滿足所有車輛的加氣需求，因而所有車輛在站場(chǎng)和氣站之間總行駛里程減少，故f1和f2分別逐步變大和變小.

表5 不同D的最優(yōu)公交加氣站選址布局方案Table 5 Optim al layoutschem e for bus gas stations under differentvalues of D

（3）隨著T的變小，進(jìn)一步限制了車輛在某氣站的等待時(shí)間，與該氣站的服務(wù)水平ρi相關(guān)，取決于其車輛到達(dá)率λi和服務(wù)率yiμi，因而增加一定數(shù)量加氣設(shè)備或調(diào)整部分線路的加氣需求至相鄰氣站（相對(duì)較遠(yuǎn)），故f1和f2均逐步變大.

表6 不同T的最優(yōu)公交加氣站選址布局方案Table 6 Optimal layoutscheme for bus gas stations under differentvalues of T

5 研究結(jié)論

本文考慮加氣站的選址布局對(duì)公交運(yùn)營的影響，將車輛在加氣站的補(bǔ)充燃料排隊(duì)過程抽象為多服務(wù)臺(tái)排隊(duì)系統(tǒng)，研究一種多目標(biāo)公交加氣站選址布局優(yōu)化模型及其求解算法，它可計(jì)算一個(gè)適于需求時(shí)空分布不均勻的最佳公交加氣站選址布局方案.該研究對(duì)城市公交加氣站的建設(shè)規(guī)模及布局具有一定的指導(dǎo)意義.

但是本文將公交和出租車分開討論，沒有考慮隨機(jī)到達(dá)的出租車的加氣需求影響公交車補(bǔ)充燃料，僅研究公交加氣站的選址布局問題，若集成它們于一體，加氣站的能力是動(dòng)態(tài)變化的；另外，文中假設(shè)隨機(jī)干擾不影響車輛正常運(yùn)行，隨機(jī)旅行時(shí)間的BGSSLP更具有實(shí)際價(jià)值，這類BGSSLP將是今后進(jìn)一步研究的方向.

[1]David A，Jenny K．Parking demand and responsiveness to supply，pricing and location in the Sydney central business district[J].Transportation Research Part A, 2001,35(1):177-196．

[2]Larson R C．A Hypercube queuing model for facility location and redistricting in urban emergency services[J]. Computersand OperationsResearch,1974,56(1):67-95．

[3]童岱,殷國富,駱勇,等.天然氣汽車加氣站優(yōu)化布點(diǎn)方法初探[J].四川工業(yè)學(xué)院學(xué)報(bào),2002,21(4):17-19.[TONG D,YIN G F,LUO Y,et al.An initial probe into the optimal layout of CNG station in a city[J]. Sichuan University of Science and Technology,2002,21 (4):17-19.]

[4]Amir A S,Meysam H,Farshid A.Hybrid systems modeling in non standard queue and optimization with the simulation approach in CNG stations[J].Research Journal of Applied Sciences,Engineering and Technology,2012,4(14):2110-2119.

[5]趙濤,夏雨.模擬退火算法在壓縮天然氣加氣站選址中的應(yīng)用[J].價(jià)值工程,2010,29(10):121-122. [ZHAO T,XIA Y.The application of simulated annealing algorithm in layout of CNG filling stations[J]. Value Engineering,2010,29(10):121-122.]

[6]吳芳,馬昌喜,李志成.城市CNG加氣站布點(diǎn)優(yōu)化的混合粒子群算法仿真[J].交通運(yùn)輸系統(tǒng)工程與信息,2011,11(5):134-139.[WU F，MA C X，LI Z C.Simulation of hybrid particle swarm algorithm for optimizing urban compressed natural gas station arrangement[J].Journal of Transportation Systems Engineering and Information Technology,2011,11(5): 134-139.

[7]黃海波,殷國富.城市CNG汽車加氣站布點(diǎn)計(jì)算機(jī)輔助評(píng)價(jià)方法[J].天然氣工業(yè),2004,24(2):93-96. [HUANG H B,YIN G F.Computer aided evaluation method for layout of urban CNG filling stations[J]. NaturalGas Industry,2004,24(2):93-96.]

[8]徐晉,梁冠民.基于模糊層次分析法的CNG加氣站選址研究[J].交通科技與經(jīng)濟(jì),2011,65(3):82-84. [XU J,LIANG G M.Based on fuzzy analytic hierarchy process of CNG fueling station location research[J].

Technology&Economy in Areas of Communications, 2011,65(3):82-84.]

[9]侯曉,張鵬,陳利瓊.基于模糊綜合法的加氣站風(fēng)險(xiǎn)評(píng)價(jià)研究[J].天然氣與石油,2009,27(5):14-17. [HOU X,ZHANG P,CHEN L Q.Study on risk evaluation of CNG filling station based on fuzzy comprehensive evaluation method[J].Natural Gas and Oil,2009,27(5):14-17.]

[10]陳杰,石超,方來華.基于灰色關(guān)聯(lián)分析和IAHP的CNG加氣站安全評(píng)價(jià)方法研究[J].中國安全科學(xué)學(xué)報(bào),2009,19(6):159-164.[CHEN J,SHIC,FANG L H.Study on safety evaluation of CNG filling station based on the grey correlation method and IAHP[J]. China Safety Science Journal,2009,19(6):159-164.]

[11]王琢玉.城市LPG加氣站規(guī)劃布局評(píng)價(jià)方法研究[J].城市公共交通,2006,5(2):217-230.[WANG Z Y.Study on the evaluation methods for the layout of urban LPG stations[J].City Transportation,2006,5(2): 217-230.]

[12]尹燕莉.CNG加氣站安全評(píng)價(jià)技術(shù)研究及軟件開發(fā)[D].西華大學(xué)，2004.[YIN Y L.Software development and safety evaluation study of CNG filling station[D].Xihua University,2004.]

[13]雷英杰,張善文,李續(xù)武,等.Matlab遺傳算法工具箱及應(yīng)用[M].西安：西安電子科技大學(xué)出版社, 2005,62-94.[LEIY J，ZHANG SW，LIX W,et al．MATLAB genetic algorithm toolbox and its applications[M].Xian：Xidian University Press,2005:62-94.]

[14]《現(xiàn)代應(yīng)用數(shù)學(xué)手冊(cè)》編委會(huì).現(xiàn)代應(yīng)用數(shù)學(xué)手冊(cè):運(yùn)籌學(xué)與最優(yōu)化理論卷[M].北京：清華大學(xué)出版社,2004,318-323.[Modern application math manual editorial board.modern application math manual operational research and optimization theory[M]. Beijing:Tsinghua University Press,2004,318-323.]

Model and Algorithm for Bus Gas Station Site Layout Optimization Problem

WEIM ing1,2,CHEN Xue-wu1,SUN Bo2

(1.Jiangsu Key Laboratory of Urban ITS,SoutheastUniversity,Nanjing 210096,China; 2.Schoolof Transportation,Nantong University,Nantong 226019,Jiangsu,China)

For the imbalance in time and space of refueling vehicleswhich belonged to different routes,a multiple objective model is studied for bus gas station site layout optim ization to meet many realistic constraints such as vehicle’s travel,lining up to fuelatgas station,and influence of gas station’s location on bus operation,etc.,by assuming that each gas station is looked as amulti-server queuing system.Previous objective is tom inimize a total of cost for building gas stations,and secondary objective aims atminimizing fueling fee for all vehicles.According to characteristic of themodel,it is converted into a single objective programming problem with constraintmethod.A design of genetic algorithm,which redesigns a solution coding,heuristic procedure to initialize chromosomes random ly,etc.,is proposed to obtain themodel’s noninferior solutions.Finally,a numerical example is taken to calculate itsbestscheme and analyze influence of gasstation’s fueling capacity on them,which showsmodeland itsalgorithm’correctnessand effectiveness.

urban traffic;gas station site layout;all vehicles queuing for fueling at stations;multiple objective;genetic algorithm

1009-6744（2015）03-0160-06

TP301.6，U116.2

A

2014-09-05

2015-01-15錄用日期：2015-03-11

國家重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃（973計(jì)劃）資助項(xiàng)目(2012CB725402)；中國博士后科學(xué)基金面上項(xiàng)目（2013M540408）；江蘇省高校自然科學(xué)研究面上項(xiàng)目(13KJB580008).

魏明(1984-)，男，安徽蕪湖人，講師，博士后.＊通信作者：mingtian911@163.com