基于雙層規(guī)劃的公共電動(dòng)自行車租賃點(diǎn)選址模型*

胡郁蔥 陳枝偉? 黃靖翔

(1.華南理工大學(xué) 土木與交通學(xué)院， 廣東 廣州 510640； 2.現(xiàn)代城市交通技術(shù)江蘇高校協(xié)同創(chuàng)新中心， 江蘇 南京 210000)

基于雙層規(guī)劃的公共電動(dòng)自行車租賃點(diǎn)選址模型*

胡郁蔥1,2陳枝偉1,2?黃靖翔1,2

(1.華南理工大學(xué) 土木與交通學(xué)院， 廣東 廣州 510640； 2.現(xiàn)代城市交通技術(shù)江蘇高校協(xié)同創(chuàng)新中心， 江蘇 南京 210000)

建設(shè)公共電動(dòng)自行車系統(tǒng)是有效利用資源、滿足居民經(jīng)濟(jì)低碳出行需求的可行途徑之一.文中提出了公共電動(dòng)自行車網(wǎng)絡(luò)系統(tǒng)的概念，并采用出行鏈對(duì)其進(jìn)行分析.在此基礎(chǔ)上，建立雙層規(guī)劃模型解決該網(wǎng)絡(luò)系統(tǒng)中的租賃點(diǎn)選址問(wèn)題.上層模型考慮政府的目標(biāo)，為系統(tǒng)最優(yōu)模型；下層模型考慮用戶的目標(biāo)，為用戶均衡模型.上層模型采用混合粒子群優(yōu)化算法求解，下層模型采用Frank-Wolfe算法求解.算例結(jié)果表明，文中算法能夠同時(shí)確定站點(diǎn)選址和站點(diǎn)規(guī)模，收斂性能較好.

公共電動(dòng)自行車；選址模型；雙層規(guī)劃；混合粒子群優(yōu)化

近年來(lái)，公共自行車在許多城市取得了較大發(fā)展[1].但自行車出行耗費(fèi)體力，騎行距離有限，騎行體驗(yàn)受環(huán)境影響較大，正日益被更為舒適、省力、低碳、騎行距離長(zhǎng)的電動(dòng)自行車所代替.在此背景下，發(fā)展公共電動(dòng)自行車，無(wú)疑是有效利用資源、滿足居民經(jīng)濟(jì)低碳出行需求的可行途徑之一.

租賃點(diǎn)選址是建立公共電動(dòng)自行車系統(tǒng)的重要環(huán)節(jié)，其合理與否直接決定系統(tǒng)建設(shè)的成敗.與自行車不同，電動(dòng)自行車需要充電，因此充電樁的配置對(duì)租賃點(diǎn)的選址具有重要影響.此外，電費(fèi)是系統(tǒng)運(yùn)營(yíng)成本的主要部分，這使得未考慮充電問(wèn)題的公共自行車租賃點(diǎn)選址理論并不直接適用于公共電動(dòng)自行車租賃點(diǎn)的選址實(shí)踐，因此，有必要對(duì)公共電動(dòng)自行車租賃點(diǎn)的選址模型進(jìn)行研究.

目前國(guó)內(nèi)外在公共自行車租賃點(diǎn)選址方面的研究成果較多，主要包括經(jīng)驗(yàn)選址法[2]、考慮庫(kù)存的樞紐位置選址模型[3]、中心弧選址模型[4]、排隊(duì)論模型[5]、雙層規(guī)劃模型[6]、OR模型[7]等.盡管公共自行車租賃點(diǎn)選址模型不斷完善和發(fā)展，但一些關(guān)鍵問(wèn)題仍未解決：①一般對(duì)“步行、借車、騎行、還車、步行”這一完整的公共自行車使用過(guò)程考慮不足；②未能綜合考慮出行時(shí)間和租賃費(fèi)用給用戶帶來(lái)的出行成本等.國(guó)內(nèi)外目前尚無(wú)對(duì)公共電動(dòng)自行車租賃點(diǎn)選址模型的研究，特別是沒(méi)有考慮電動(dòng)自行車的充電問(wèn)題.

為解決上述問(wèn)題，文中定義了公共電動(dòng)自行車網(wǎng)絡(luò)系統(tǒng)，引入出行鏈的概念，考慮公共電動(dòng)自行車系統(tǒng)規(guī)劃者和用戶之間的互動(dòng)作用，分別從系統(tǒng)最優(yōu)和用戶均衡的角度建立上、下層模型，從而構(gòu)建起公共電動(dòng)自行車租賃點(diǎn)選址的雙層規(guī)劃模型.

1 公共電動(dòng)自行車網(wǎng)絡(luò)系統(tǒng)

公共電動(dòng)自行車網(wǎng)絡(luò)系統(tǒng)由不同的公共電動(dòng)自行車出行鏈和出行鏈上的公共電動(dòng)自行車租賃點(diǎn)構(gòu)成.

1.1 出行鏈和廣義出行成本

出行鏈?zhǔn)侵赣脩魪钠瘘c(diǎn)到訖點(diǎn)的單向出行過(guò)程，包括5個(gè)階段：①?gòu)慕煌ㄐ^(qū)r步行至借車點(diǎn)m；②在借車點(diǎn)m借車；③使用公共電動(dòng)自行車從借車點(diǎn)m騎行至還車點(diǎn)n；④在還車點(diǎn)n還車；⑤從還車點(diǎn)n步行至交通小區(qū)s.用戶使用公共電動(dòng)自行車的成本不僅包括騎行時(shí)間，還包含步行時(shí)間和在租賃點(diǎn)的逗留時(shí)間.此外，租賃費(fèi)用也是出行成本的一部分.因此，用戶在OD對(duì)(r,s)間的第k條出行鏈的廣義出行成本為

(1)

(2)

1.2 公共電動(dòng)自行車租賃點(diǎn)和逗留時(shí)間

公共電動(dòng)自行車租賃點(diǎn)由充電樁和公共電動(dòng)自行車構(gòu)成.充電樁應(yīng)具有刷卡借還車功能(無(wú)刷卡借還車功能可配備獨(dú)立的智能租賃終端).租賃點(diǎn)的規(guī)模由充電樁數(shù)量ux和配備的公共電動(dòng)自行車數(shù)量bx確定,

(3)

式中：φpile,x為租賃點(diǎn)x的充電樁周轉(zhuǎn)率；φbike,x為租賃點(diǎn)x的自行車周轉(zhuǎn)率；qx為租賃點(diǎn)x的公共電動(dòng)自行車流量，

公共電動(dòng)自行車租賃點(diǎn)的3個(gè)因素對(duì)租賃點(diǎn)的選址具有決定性的影響：

1)高密度的租賃點(diǎn)布局需要大量的投資且會(huì)導(dǎo)致租賃點(diǎn)服務(wù)范圍的大量重疊,因此，兩個(gè)租賃點(diǎn)之間距離不宜過(guò)近,其最小距離等于兩個(gè)租賃點(diǎn)服務(wù)半徑之和.

2)電動(dòng)自行車一次充電后的續(xù)航里程決定了借車點(diǎn)和還車點(diǎn)之間的最大距離.

3)用戶在借還公共電動(dòng)自行車的過(guò)程中，可能會(huì)由于車輛充電而產(chǎn)生等待時(shí)間，因此充電效率是影響逗留時(shí)間(等待時(shí)間和借/還車時(shí)間之和)的一個(gè)重要因素.公共電動(dòng)自行車租賃點(diǎn)可以視作M/M/c排隊(duì)系統(tǒng).在假設(shè)顧客到達(dá)服從泊松流、各充電樁服務(wù)時(shí)間服從負(fù)指數(shù)分布且工作相互獨(dú)立的條件下，租賃點(diǎn)x的逗留時(shí)間的計(jì)算公式為

(4)

1.3 步行時(shí)間和騎行時(shí)間

假設(shè)交通小區(qū)出行需求均勻分布，則OD對(duì)(r,s)之間的出行可看成從r的形心到s的形心的過(guò)程.因此，步行時(shí)間的計(jì)算公式如下：

(5)

式中，Srm為從r的形心到借車點(diǎn)m的距離，Sns為從還車點(diǎn)n到s的形心的距離，vw為步行速度.

騎行時(shí)間為用戶使用公共電動(dòng)自行車在借車點(diǎn)m和還車點(diǎn)n之間騎行的時(shí)間.由于電動(dòng)自行車車速較低，所以同一出行鏈的騎行時(shí)間主要受行程距離的影響.此外，電動(dòng)自行車專用道可以使得電動(dòng)自行車獲得獨(dú)立路權(quán)并實(shí)現(xiàn)恒速行駛.綜上所述，騎行時(shí)間計(jì)算公式為

(6)

式中：t0mn為從借車點(diǎn)m到還車點(diǎn)n的電動(dòng)自行車自由流的行駛時(shí)間；Cmn為借車點(diǎn)m和還車點(diǎn)n之間路段的實(shí)際通行能力；α、β為待標(biāo)定參數(shù)；Smn為借車點(diǎn)m和還車點(diǎn)n之間的距離；ξ為速度折減系數(shù)(當(dāng)設(shè)置電動(dòng)自行車專用道時(shí)ξ=1，否則ξ<1)；vc為自由騎行速度；qmn為m和n之間的公共電動(dòng)自行車流量，

2 公共電動(dòng)自行車租賃點(diǎn)選址的雙層規(guī)劃模型

2.1 模型的假設(shè)條件

根據(jù)以上分析，文中所建模型的假設(shè)條件如下：①出行鏈?zhǔn)菃蜗虻?；同一租賃點(diǎn)在兩條反向出行鏈中功能相反；②各租賃點(diǎn)的電動(dòng)自行車供應(yīng)量充足，不考慮公共電動(dòng)自行車的平衡問(wèn)題；③出行需求在交通小區(qū)內(nèi)均勻分布，因此將小區(qū)形心視作出行需求點(diǎn);④用戶到達(dá)服從泊松分布；各充電樁工作相互獨(dú)立且服務(wù)時(shí)間服從負(fù)指數(shù)分布；⑤電網(wǎng)能力能夠滿足公共電動(dòng)自行車系統(tǒng)的建設(shè)運(yùn)營(yíng)要求.

2.2 雙層規(guī)劃模型構(gòu)建

文中所述租賃點(diǎn)選址問(wèn)題兼顧政府和系統(tǒng)用戶的兩層目標(biāo)，因此選用雙層規(guī)劃模型來(lái)建模.

在建設(shè)公共電動(dòng)自行車系統(tǒng)時(shí)，政府部門希望系統(tǒng)的效益最大化，即出行者出行成本之和最小.因此，上層模型為系統(tǒng)最優(yōu)問(wèn)題，需要滿足的約束條件是：①兩租賃點(diǎn)之間的距離滿足最小、最大距離的限制；②至少選擇一個(gè)借車點(diǎn)；③至少選擇一個(gè)還車點(diǎn)；④各租賃點(diǎn)建設(shè)運(yùn)營(yíng)資金之和不大于投資總額上限；⑤各出行鏈上的公共電動(dòng)自行車出行量之和等于小區(qū)之間的電動(dòng)自行車出行需求量；⑥各出行鏈上的公共電動(dòng)自行車出行量為非負(fù)值.

(7)

s.t.

式中，dmin、dmax分別為兩租賃點(diǎn)之間的最小距離和最大距離，I為投資總額上限，ix為租賃點(diǎn)x的建設(shè)運(yùn)營(yíng)費(fèi)用.其余參數(shù)定義見(jiàn)第2部分.

公共電動(dòng)自行車用戶總是希望花費(fèi)在出行上的時(shí)間盡可能少，所以他們總是尋找最短路出行.因此，下層模型為用戶均衡模型.

(8)

s.t.

2.3 模型求解算法

由于粒子群優(yōu)化算法實(shí)現(xiàn)簡(jiǎn)單，收斂速度快，魯棒性強(qiáng)[8]，文中選擇其改進(jìn)算法——混合粒子群優(yōu)化來(lái)求解上層模型.相對(duì)于傳統(tǒng)的用戶均衡模型而言，下層模型的求解規(guī)模更小(每條出行鏈僅有4個(gè)節(jié)點(diǎn)且租賃點(diǎn)數(shù)目有限)，所以文中選用傳統(tǒng)的Frank-Wolfe算法來(lái)求解下層模型.

根據(jù)模型的數(shù)學(xué)特性，發(fā)現(xiàn)通過(guò)在上層模型和下層模型之間反復(fù)迭代可以逐漸逼近雙層規(guī)劃模型的最優(yōu)解，具體流程如下.

步驟4 判斷結(jié)果是否滿足迭代停止條件

式中，ε為可接受誤差.

若滿足，則輸出全局最優(yōu)解；若不滿足，令z=z+1，返回步驟2繼續(xù)求解.

3 算例分析

3.1 算例背景

以華南理工大學(xué)五山校區(qū)的兩個(gè)交通小區(qū)(M和N)為例說(shuō)明文中研究的模型在公共電動(dòng)自行車租賃點(diǎn)選址決策中的應(yīng)用.根據(jù)與地鐵站距離、重要集散點(diǎn)位置等因素初步篩選得到9個(gè)備選公共電動(dòng)自行車租賃點(diǎn)，如圖1所示.兩個(gè)交通小區(qū)之間的高峰小時(shí)公共電動(dòng)自行車潛在需求量為1 000次/時(shí).距離信息如表1、2所示，成本信息和其他相關(guān)參數(shù)如表3所示.

圖1 備選公共電動(dòng)自行車租賃點(diǎn)

Table 1 Distance from centroids of traffic zones to candidate sites km

表2 租賃點(diǎn)到租賃點(diǎn)的距離

Table 2 Distance from pick-up stations to drop-off stations km

表3 租賃點(diǎn)成本信息及相關(guān)參數(shù)

Table 3 Cost information of electric bicycle stations and other relevant parameters

參數(shù)取值說(shuō)明參數(shù)取值說(shuō)明電動(dòng)自行車價(jià)格cb/(元·車-1)1800根據(jù)市場(chǎng)調(diào)查得到的平均價(jià)格充電樁價(jià)格cp/(元·樁-1)4000根據(jù)市場(chǎng)調(diào)查得到的平均價(jià)格c/(元·h-1)1.5電動(dòng)自行車的電費(fèi)/(元·h-1)50根據(jù)2015年廣州市人均工資估算日建設(shè)費(fèi)用ci/(元·天-1)500根據(jù)廣州公共自行車系統(tǒng)的成本數(shù)據(jù)估算(考慮電費(fèi))年運(yùn)營(yíng)費(fèi)用(含電費(fèi))co/(元·站-1·年-1)4200根據(jù)廣州公共自行車系統(tǒng)的成本數(shù)據(jù)估算(考慮電費(fèi))α0.05根據(jù)參考文獻(xiàn)數(shù)據(jù)調(diào)整[10]β1根據(jù)參考文獻(xiàn)數(shù)據(jù)調(diào)整[10]租賃點(diǎn)的年平均費(fèi)用i=cbbm+cpum+365ci+coξ0.9根據(jù)參考文獻(xiàn)數(shù)據(jù)調(diào)整[10]vw/(km·h-1)3.96人類平均步行速度Cmn1500實(shí)地調(diào)查獲取vc/(km·h-1)15平均電動(dòng)車騎行速度dmin/km1服務(wù)半徑[11]φpile/(樁·h-1)30根據(jù)廣州公共自行車系統(tǒng)的數(shù)據(jù)估算φ車/(車·h-1)36根據(jù)廣州公共自行車系統(tǒng)的數(shù)據(jù)估算dmax/km25電動(dòng)自行車充滿電后的續(xù)航里程[12]I/百萬(wàn)元0.3華南理工大學(xué)基建處工作人員估算

3.2 結(jié)果分析

在一臺(tái)裝有Windows 7.0(專業(yè)版)系統(tǒng)的筆記本電腦上采用Matlab語(yǔ)言實(shí)現(xiàn)本算法.其中，上層模型的罰函數(shù)構(gòu)造規(guī)則為：若不符合約束條件①、②或③，罰10 000；若不符合約束條件④，罰30 000；下層模型保證約束條件⑤和⑥會(huì)得到滿足，故無(wú)需對(duì)其構(gòu)造罰函數(shù).混合粒子群優(yōu)化算法的粒子數(shù)取20，最大迭代次數(shù)取100.可接受誤差取0.03.算法運(yùn)行結(jié)果如表4所示，算法收斂性能分別如圖2、3所示.

從表4看到，交通小區(qū)M應(yīng)該建設(shè)租賃點(diǎn) 1(13個(gè)充電樁和18輛公共電動(dòng)自行車)；交通小區(qū)N應(yīng)該建設(shè)租賃點(diǎn)8(26個(gè)充電樁和37輛公共電動(dòng)自行車).租賃點(diǎn)1位于地鐵站附近，使用公共電動(dòng)自行車接駁需求較大.租賃點(diǎn)8靠近區(qū)N的形心，集中了學(xué)生宿舍、學(xué)生食堂、運(yùn)動(dòng)場(chǎng)等生活設(shè)施，是該小區(qū)的交通需求聚集地.因此，采用文中所述模型的租賃點(diǎn)選址結(jié)果與實(shí)際情況較為接近，具有一定的現(xiàn)實(shí)意義.

表4 算法運(yùn)行結(jié)果

圖2 迭代次數(shù)和相對(duì)誤差的關(guān)系

圖3 迭代次數(shù)和運(yùn)行時(shí)間的關(guān)系

從圖2可以看到，在可接受誤差為0.03的條件下，算法迭代153后收斂.qmn、qm和qn的相對(duì)誤差是0.029 74、0.010 18和0.020 16.從圖3可以看到，算法總運(yùn)行時(shí)間42 s. 因此，混合粒子群算法收斂性能好，收斂速度快.

4 結(jié)語(yǔ)

文中在分析了公共自行車租賃點(diǎn)選址方法的研究現(xiàn)狀后，針對(duì)其中的不足提出了基于雙層規(guī)劃的公共電動(dòng)自行車租賃站點(diǎn)選址方法，采用雙層規(guī)劃模型描述該選址問(wèn)題：上層模型從政府的角度出發(fā)，在各種約束前提下，設(shè)計(jì)合理的租賃點(diǎn)布局，使得公共電動(dòng)自行車出行達(dá)到系統(tǒng)最優(yōu)；下層模型則從用戶的角度出發(fā)，采用用戶均衡模型來(lái)描述公共電動(dòng)自行車用戶的出行行為.上層模型采用混合粒子群優(yōu)化算法求解，下層模型采用Frank-Wolfe算法求解.算例的結(jié)果表明，該算法能夠同時(shí)確定站點(diǎn)選址和站點(diǎn)規(guī)模(包括充電樁數(shù)目和配備電動(dòng)自行車的數(shù)目)，算法收斂性能較好，能夠?yàn)檎块T的決策提供科學(xué)的依據(jù).

[1] ELLIOT Fishman.Bikeshare：a review of recent literature [J].Transport Reviews,2015,36(1):92-113.

[2] 朱瑋,何京洋,王德.法國(guó)公共自行車系統(tǒng)布局方法與實(shí)證研究——以巴黎和里昂為例 [J].國(guó)際城市規(guī)劃,2015,30(Z1):64-70. ZHU Wei,HE Jing-yang,WANG De.Methods and empirical research on the distribution of public bicycle systems in France:case study on Paris and Lyon [J].Urban Planning International,2015,30(Z1):64-70.

[3] LIN Jenn-rong,YANG Ta-hui.Strategic design of public bicycle sharing systems with service level constraints [J].Transportation Research Part E,2011,47(2):284-294.

[4] CAMPBEL James,ERNST Andreas,KRISHNAMOORTHY Mohan.Hub arc location problems:Part II-formulations and optimal algorithms [J].Management,2005,51(10):1556-1571.

[5] GEORGE David,XIA Cathy.Fleet-sizing and service availability for a vehicle rental system via closed queueing networks [J].European Journal of Operational Research,2011,51(10):198-207.

[6] 李婷婷.城市公共自行車租賃點(diǎn)選址規(guī)劃研究 [D].北京:北京交通大學(xué),2010.

[7] 潘雪.基于多目標(biāo)優(yōu)化的城市公共自行車租賃點(diǎn)選址研究 [D].沈陽(yáng):沈陽(yáng)工業(yè)大學(xué),2016.

[8] ZHANG Yun-dong,WANG Shui-hua,JI Gen-lin.A comprehensive survey on particle swarm optimization algorithm and its application [J].Mathematical Problems in Engineering,2015,2015(1):1-38.

[9] 薛峰,陳剛,高尚.求解0-1整數(shù)規(guī)劃的混合粒子群優(yōu)化算法 [J].計(jì)算技術(shù)與自動(dòng)化,2011,30(1):86-89. XUE Feng,CHEN Gang,GAO Shang.Solving 0-1 integer programming problem by hybrid particle swarm optimization algorithm [J].Computing Technology and Automation,2011,30(1):86-89.

[10] 張巧.混合交通流條件下城市路段BPR函數(shù)參數(shù)標(biāo)定研究 [D].長(zhǎng)沙:中南大學(xué),2013.

[11] GUO Tang-yi,ZHANG Ping,SHAO Fei,et al.Allocation optimization of bicycle-sharing stations at scenic spots [J].Journal of Central South University,2014,21(8):3396-3403.

[12] 電動(dòng)自行車通用條件:GB17761—1999 [S].

Location Model for Public Electric Bicycle Rent Based on Bi-Level Programming

HUYu-cong1,2CHENZhi-wei1,2HUANGJing-xiang1,2

(1.School of Civil Engineering and Transportation, South China University of Technology, Guangzhou 510640, China;2.Jiangsu Province Collaborative Innovative Center of Modern Urban Traffic Technologies, Nanjing 210000, Jiangsu, China)

Developing public electric bicycle systems is a feasible way to making full use of resources and meeting people’s increasing demand for low-carbon trips. This paper first proposes a public electric bicycle network system based on trip chain analysis, and then establishes a bi-level programming model to solve the station location problem of such systems. In this model, the upper part considers the government’s goal for system optimization, while the lower part shows respect for system users’interests and user equilibrium. The upper model is solved by using the hybrid particle swarm optimization algorithm and the lower one is solved by using Frank-Wolfe algorithm.Numerical results show that the proposed programming model can determine both the optimal location and the size of stations in the public electric bicycle network system with good convergence.

public electric bicycle; station location model; bi-level programming; hybrid particle swarm optimization

2016-06-01

國(guó)家自然科學(xué)基金資助項(xiàng)目(51408237);國(guó)家級(jí)大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練計(jì)劃項(xiàng)目(201510561102) Foundation items: Supported by the National Natural Science Foundation of China(51408237) and the National College Students Innovation and Business Plan(201510561102)

胡郁蔥(1970-)，女，博士，副教授，主要從事交通運(yùn)輸規(guī)劃與管理研究.E-mail:ychu@scut.edu.cn

? 通信作者: 陳枝偉(1994-),男，主要從事交通運(yùn)輸規(guī)劃與管理研究.E-mail：c.zw02@scut.edu.cn

1000-565X(2017)04-0118-06

U 491.2

10.3969/j.issn.1000-565X.2017.04.017