魏明，陳學武，孫博

（1.東南大學城市智能交通江蘇省重點實驗室，南京210096；2.南通大學交通學院，江蘇南通226019）

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

魏明*1,2，陳學武1，孫博2

（1.東南大學城市智能交通江蘇省重點實驗室，南京210096；2.南通大學交通學院，江蘇南通226019）

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

城市交通；加氣站選址；車輛排隊加氣；多目標；遺傳算法

1 引言

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

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

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

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

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

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

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

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

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

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

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

3 求解BGSSLP的遺傳算法

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

3.1 編碼方案

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

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

3.2 適應度函數(shù)的設計

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

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

本文以Fit(f)=f2為適應度函數(shù)，利用其評價個體的好壞，求解BGSSLP的非劣解.

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

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

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

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

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

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

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

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

3.4 遺傳操作

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

顯然，交叉和變異操作可能破壞解的可行結構，舍棄這些新產生的不可行個體.

3.5 終止原則

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

4 算例分析

某城市區(qū)域有14個站場和10個候選加氣地點，其網絡拓撲結構如圖1所示，不同站場經營21條線路在加氣高峰時段的最大需求如表1，候選地點的基本信息如表2，其它參數(shù)為p=50 000元/個、T=10m in、D=6 km、o=5m in和r=22元/h.

圖1 站場和候選地點的網絡拓撲結構Fig.1 Network topology network topology between busand gas stations

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

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

表2 候選地點的基本信息Table 2 Basic information of candidate gas stations

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

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

（1）當加氣設備數(shù)不低于某值時才滿足所有車輛的加氣需求，隨著c的變小，布局方案偏向于ci較小的候選地點或減少加氣站數(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的變小，各個加氣站輻射公交站場的范圍縮小，必須增加一定數(shù)量的公交站點才滿足所有車輛的加氣需求，因而所有車輛在站場和氣站之間總行駛里程減少，故f1和f2分別逐步變大和變小.

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

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

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

5 研究結論

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

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

[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)化布點方法初探[J].四川工業(yè)學院學報,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]趙濤,夏雨.模擬退火算法在壓縮天然氣加氣站選址中的應用[J].價值工程,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加氣站布點優(yōu)化的混合粒子群算法仿真[J].交通運輸系統(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汽車加氣站布點計算機輔助評價方法[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].交通科技與經濟,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]侯曉,張鵬,陳利瓊.基于模糊綜合法的加氣站風險評價研究[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]陳杰,石超,方來華.基于灰色關聯(lián)分析和IAHP的CNG加氣站安全評價方法研究[J].中國安全科學學報,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ī)劃布局評價方法研究[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加氣站安全評價技術研究及軟件開發(fā)[D].西華大學，2004.[YIN Y L.Software development and safety evaluation study of CNG filling station[D].Xihua University,2004.]

[13]雷英杰,張善文,李續(xù)武,等.Matlab遺傳算法工具箱及應用[M].西安：西安電子科技大學出版社, 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)代應用數(shù)學手冊》編委會.現(xiàn)代應用數(shù)學手冊:運籌學與最優(yōu)化理論卷[M].北京：清華大學出版社,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

國家重點基礎研究發(fā)展計劃（973計劃）資助項目(2012CB725402)；中國博士后科學基金面上項目（2013M540408）；江蘇省高校自然科學研究面上項目(13KJB580008).

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