胡郁蔥 陳枝偉? 黃靖翔

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

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

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

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

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

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

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

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

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

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

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

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

1.1 出行鏈和廣義出行成本

出行鏈是指用戶從起點到訖點的單向出行過程，包括5個階段：①從交通小區(qū)r步行至借車點m；②在借車點m借車；③使用公共電動自行車從借車點m騎行至還車點n；④在還車點n還車；⑤從還車點n步行至交通小區(qū)s.用戶使用公共電動自行車的成本不僅包括騎行時間，還包含步行時間和在租賃點的逗留時間.此外，租賃費用也是出行成本的一部分.因此，用戶在OD對(r,s)間的第k條出行鏈的廣義出行成本為

(1)

(2)

1.2 公共電動自行車租賃點和逗留時間

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

(3)

式中：φpile,x為租賃點x的充電樁周轉率；φbike,x為租賃點x的自行車周轉率；qx為租賃點x的公共電動自行車流量，

公共電動自行車租賃點的3個因素對租賃點的選址具有決定性的影響：

1)高密度的租賃點布局需要大量的投資且會導致租賃點服務范圍的大量重疊,因此，兩個租賃點之間距離不宜過近,其最小距離等于兩個租賃點服務半徑之和.

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

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

(4)

1.3 步行時間和騎行時間

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

(5)

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

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

(6)

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

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

2.1 模型的假設條件

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

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

文中所述租賃點選址問題兼顧政府和系統(tǒng)用戶的兩層目標，因此選用雙層規(guī)劃模型來建模.

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

(7)

s.t.

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

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

(8)

s.t.

2.3 模型求解算法

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

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

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

式中，ε為可接受誤差.

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

3 算例分析

3.1 算例背景

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

圖1 備選公共電動自行車租賃點

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

表2 租賃點到租賃點的距離

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

表3 租賃點成本信息及相關參數(shù)

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

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

3.2 結果分析

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

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

表4 算法運行結果

圖2 迭代次數(shù)和相對誤差的關系

圖3 迭代次數(shù)和運行時間的關系

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

4 結語

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

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

[2] 朱瑋,何京洋,王德.法國公共自行車系統(tǒng)布局方法與實證研究——以巴黎和里昂為例 [J].國際城市規(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] 李婷婷.城市公共自行車租賃點選址規(guī)劃研究 [D].北京:北京交通大學,2010.

[7] 潘雪.基于多目標優(yōu)化的城市公共自行車租賃點選址研究 [D].沈陽:沈陽工業(yè)大學,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].計算技術與自動化,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ù)標定研究 [D].長沙:中南大學,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] 電動自行車通用條件: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

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

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

? 通信作者: 陳枝偉(1994-),男，主要從事交通運輸規(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