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

倪 勇，鄭長江，李 銳

（河海大學土木與交通學院，江蘇 南京 210098）

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

倪 勇，鄭長江，李 銳

（河海大學土木與交通學院，江蘇 南京 210098）

隨著國內城市汽車保有量日漸增加，交通壓力變得越來越大。為了妥善處理“最后1公里”的交通出行問題，完善城市地鐵與公共自行車的換乘銜接，構建選址科學，規(guī)劃合理的公共自行車租賃系統顯得尤為重要。按照公共自行車租賃點選址影響要素及布設準則，結合公共自行車租賃點同時存在借車與還車的兩種需求的現實狀況，并借鑒阻抗函數的原理，建立出行總時間最小模型，來構建出公共自行車租賃點雙層規(guī)劃選址模型。最后通過實例計算，來確定地鐵周邊小區(qū)需求點400 m范圍內公共自行車租賃點位置，并進行評價分析。

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

公共自行車作為城市公共交通的一部分，其所具有的機動靈活等特點，在中短距離的交通出行過程中優(yōu)勢明顯，并通過與其他交通方式的銜接，能有效地提高城市居民的出行效率，其選址問題的研究也在得到更多學者的關注。Luigi Dell’Olio等[1]通過使用地理信息系統，構建起租賃點布設模型，在保證可達性的同時使公共自行車與公共交通實現相互銜接；Jean-Rong Lin[2]主要研究考慮自行車存儲的自行車系統租賃站點選址的模型，該模型在原有模型基礎上多考慮了庫存的樞紐位置；李黎輝[3]探討了武漢市的公共自行車租賃點布局規(guī)劃理論，從定性的角度給出了自行車租賃點選址方法；李婷婷[4]的碩士論文主要研究了利用雙層規(guī)劃模型對自行車租賃點進行選址，該模型是以決策者建設成本最小和用戶出行費用最低為上下層規(guī)劃的目標。而本文研究的公共自行車租賃點選址問題，也利用的是主從遞階（或多層）決策[5]，并以決策者建設成本最小和用戶出行時間最少為上下層規(guī)劃的目標，以得出基于城市地鐵換乘的公共自行車租賃點的一般選址規(guī)劃方法。

1 雙層規(guī)劃模型定義

一般來說，雙層規(guī)劃模型具有如下形式：

這個模型的決策機制為：通過上層決策者做出的決策變量x，影響下層的目標函數和約束集；下層決策者在該條件下，做出使自身達到最優(yōu)目標的決策y；同時，作為反饋的下層決策變量y也會影響上層決策問題的目標函數和約束集；通過此過程，上層決策者調整決策x，以實現最優(yōu)目標。雙層規(guī)劃問題作為具有遞階結構的優(yōu)化問題，是一類有兩層決策問題的數學模型。其中稱：

為雙層規(guī)劃問題（1）的上層規(guī)劃問題，其中x稱為上層變量；稱

為下層規(guī)劃問題，y稱為下層變量。

因為雙層規(guī)劃問題是一個NP-hard問題，求解復雜，而雙層規(guī)劃所體現的非凸性、可行域的不連通性及合理反應映射的非單值性等則使求解變得更困難，能夠求出的解通常也只是局部最優(yōu)解。目前，大約已有十多種算法用于求解雙層規(guī)劃問題，將其歸納，一般有下降法、K-T法和非數值優(yōu)化方法。國內外學者多年來都在研究雙層規(guī)劃模型的有效算法，如1992年Fries、Yang等人分別提出模擬退火算法[6]和靈敏度分析法[7]。

綜上分析，非線性雙層規(guī)劃問題的求解算法均是以獲取下層決策變量對上層決策的具體反應函數為核心內容，以實現將很多關于非線性規(guī)劃問題方面的求解算法，能夠較有效地應用于雙層規(guī)劃模型的求解中。

2 基于城市地鐵換乘的公共自行車租賃點雙層規(guī)劃選址模型的建立

在公共自行車租賃點布局優(yōu)化問題中，包含了兩類不同目標的人群：一是政府運營部門通過制定布設方案，使系統總建設成本最低；二是使用者通過調整出行方式和路線，使總出行時間最少。因此基于城市地鐵換乘的公共自行車租賃點布設問題適宜采用雙層規(guī)劃模型。結構圖如圖1所示。

圖1 基于雙層規(guī)劃模型的公共自行車租賃點選址結構圖Fig.1 Diagram of the public bicycle rental point location based on the bi-level programming model

2.1 模型的假設條件

本文的選址模型是針對通借通還的公共自行車租賃系統而構建，因而有需求點和租賃點。其中，需求點作為租賃點選址的第一要素，為降低模型的復雜度，本文有如下假定：

假設1：小區(qū)的需求集中在需求生成點，其不一定位于小區(qū)的重心；

假設2：將規(guī)劃區(qū)域按地理條件、用地性質細分成若干個小區(qū)，地鐵站點作為一個特殊的交通小區(qū)，提供足夠的產生和吸引量；

假設3：出行者時間成本相同，且選擇最近租賃點，故出行者到租賃點的單位費用設為常數；

假設4：公共自行車租賃點費用包括建設、運營和設備等方面，由政府提供且為常數。

2.2 雙層模型的構造

城市地鐵換乘處的公共自行車租賃點選址規(guī)劃是指在一定的規(guī)劃區(qū)域內進行對租賃點的位置選擇和需求分配優(yōu)化，并形成最終布設方案。圖2為選址規(guī)劃示意圖。

2.2.1 上層模型

上層模型既要考慮經濟素，也要考慮社會和自然環(huán)境因素。本文首要考慮決策者需求，將經濟因素作為主要考慮因素，而社會和自然環(huán)境因素不作主要考慮。因此，政府的決策目標為：滿足規(guī)劃區(qū)域內需求點的需求量，并制定最優(yōu)的租賃點布設方案使總建設成本最小。

本文利用離散工廠選址模型用于上層規(guī)劃，建模如下：

圖2 基于軌道交通換乘的公共自行車租賃點選址規(guī)劃示意圖Fig.2 Schematic diagram of public bicycle rental point location planning based on rail transit transfer

式中：m為待選租賃點數量；

n為需求點數量；

c1，c2為公共自行車和停車樁的單位費用；

Pj為租賃點j的自行車數量；

Qj租賃點j的停車樁數量；

f為租賃點的固定建造費用，可以假設為定值；

Yj為如果在j處建設租賃點，則其值為1，否則為0；

wij—dij≤d0，則wij=1，表示需求點i被租賃點j覆蓋，否則為0。

dij為租賃點j到需求點i的距離，d0為集散點步行覆蓋范圍；

Dij為需求點i在待選租賃點j的還車次數；

Qij為需求點i在待選租賃點j的租車次數；

βj為租賃點j的停車樁周轉率；

αj為租賃點j的自行車周轉率。

上層模型的目標函數主要考慮決策者目標，為使系統固定建設費用最小。第一個約束條件確保各需求點至少被一個租賃點覆蓋；第二個約束條件為變量的0-1約束。在此需指出，上層規(guī)劃模型中涉及到Dij，Qij的通過下層規(guī)劃模型求得。

2.2.2 下層模型

下層模型主要考慮公共自行車租借者，在地鐵換乘過程中，為使出行效率最大化，本文選取出行時間作為主要考慮因素。目標函數以租賃者總出行耗時T最小為準。

本文借鑒阻抗函數的基本原理，構建待選租賃點的時間阻抗函數。根據定義，阻抗函數反映了路網的擁護效應，是車輛行程時間與道路交通條件之間的函數關系，作為一項關鍵的基礎技術運用于交通量分配工作中[8-9]。

根據我國城市普遍存在機非混行的交通現狀，國內很多學者提出了阻抗函數的經驗模型：

式中：α1，β1，α2，β2是回歸參數；tα本方向路段α上的行駛時間；xα1，xα2表示路段α上的機動車流量；Cα1，Cα2表示非機動車在路段α上的通行能力。

因此，結合公共自行車租賃點同時存在借車與還車的這兩種需求的實際情況下，本文運用經驗模型公式（5）的基本原理，得到改進的公共自行車待選租賃點的時間阻抗函數，建立出行耗時最小模型：

式中：t（Cij）為待選租賃點j的時間阻抗函數，其公式為

式中：α，β為標定參數；pj為單位時間內待選租賃點j的最大還車數；qj為單位時間內待選租賃點j的最大租車數；t0為一次完整租還車過程的平均耗時。

下層模型是以租賃者出行耗時最少為目標。其中有兩個約束條件，第一個約束條件是各需求點的交通出行需求均能被滿足；第二個約束條件是出行者只選擇在步行距離范圍內且已建成的租賃點。

2.2.3 模型求解算法

本文雙層規(guī)劃模型中上層是用離散變量表示租賃點布設方案的非線性優(yōu)化問題，當待選點很多時，計算求得該問題的精確解需花費較長時間。因此，本文針對下層模型中約束條件公式（8）的特殊形式，利用啟發(fā)式算法進行求解[10]。在下層規(guī)劃模型Pj中，通過分析，wij和Yj已知時，若至少一個為0，則Cij=0，即約束失效；若wij=1且Yj=1的條件下，則Cij≤M，其中M取充分大整數，則該約束條件恒成立，可不考慮。

因此，本文將約束條件不等式右側減去松弛變量Zij以化為等式，即

若Yj=0，利則可直接得Cij，Zij的值；若Yj=1，先利用已有方法求解下層模型，以求解在穩(wěn)定條件下各待選租賃點租還車數的需求分布Cij，經過反推可以得到Zij*。則反應函數為Cij=MwijYj-Zij*，其中i=1，2，…，n，j= 1，2，…，m，Zij*為松弛變量，把該反應函數公式帶回上層的目標函數，然后通過分枝定界法求解上層規(guī)劃。把求得的最優(yōu)解再用到下層規(guī)劃中，通過上述方法求出各待選點在穩(wěn)定條件下的租還車次數需求分布，循環(huán)求解得模型最優(yōu)解。計算過程如下：

步驟1：首先設定選址方案的一個初始解Yj0，令迭代次數t=0；

步驟2：對于給定的Yjt，計算下層規(guī)劃模型得Cijt；

步驟3：計算得松弛變量Zij*，將Cij帶回上層規(guī)劃中求解，得到一組新的Yjt+1值；

3 算例分析

本文將雙層規(guī)劃模型實際應用于以杭州市軌道交通4號線錢江路站為中心的一個規(guī)劃區(qū)域，以研究該區(qū)域內換乘軌道交通的公共自行車租賃點的選址規(guī)劃。

根據公共自行車租賃點布局準則及交通小區(qū)道路空間條件，在各小區(qū)需求點400 m范圍內設置初始租賃點，見圖3中用帶自行車的白色圓圈表示。其中，需求點和各租賃點之間的距離見表1。

圖3 規(guī)劃區(qū)域需求點和待選租賃點分布圖Fig.3 Demand point and alternative rental point distribution map in planning regions

表1 需求點與租賃點之間的距離Tab.1 The distance between the demand points and the rental points m

因需求點與租賃點間以400 m為租賃點服務半徑，可得出需求點A可被租賃點A1、A2覆蓋，需求點B可被租賃點B1～B4覆蓋，需求點C可被租賃點C1～C4覆蓋，需求點D、E同理，由此可得到：

令每完成一次租借行為所需的平均時間t0=60 s，步行平均速度vij=1.1 m/s；根據杭州市車輛購置費，每輛公共自行車380元；自行車鎖柱刷卡系統2 500多元；租賃點建造費一般包括車棚和服務亭兩部分，約為7萬，加上鎖止器、軟件、監(jiān)控系統等，單個租賃點造價約為10萬；取c1=0.04，c2=0.3，f=10。

具體計算步驟如下所示：

第一步：給定初始解Yj0=（1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1），即假設在所有待選點均建設租賃點，并令t=0，應用LINGO軟件對下層規(guī)劃模型求解，得到租借者的租賃次數Cij分布。

第二步：由反應函數Cij＝MwijYj-Zij*計算得松弛變量Zij*，把上一步驟求得的Cij帶回上層規(guī)劃模型中，再利用LINGO軟件來解答，算得新值：Yj1=（1，1，1，1，1，1，0，1，1，1，1，1，1，1，1，0，1）；

第三步：把得到的Yj1從開始步驟計算，假設t=1，反復上面的步驟，經歷兩次迭代從而得出模型最優(yōu)解，Yj*=（1，1，1，1，1，1，0，1，1，1，1，1，0，1，1，1，0）。

最后可以得出租賃點的選擇方案，確定選取的待選租賃點有：A1，A2，B1，B2，B3，B4，C1，C2，C3，C4，D1，D2，E1，E2，E3。

4 結論

本文以地鐵站及其周邊小區(qū)來規(guī)劃公共自行車租賃點的選址問題，利用雙層規(guī)劃模型計算得到該區(qū)域內換乘地鐵的公共自行車租賃點布設方案；對比現有情況，提升了以地鐵站點為中心區(qū)域內的公共自行車布點的科學性及可靠性。因會受到車輛的調度問題等的多方面要素的影響，仍需考察各個租賃點位置處的實際使用狀況，分析出行者使用自行車時長，以優(yōu)化調整公共自行車租賃點的選址與規(guī)模。

[1]DELL O L，ANGEL I，LUIS M J．Implementing bike-sharing systems[J]．Municipal Engineer，2011，164：89-101．

[2]LIN J R，YANG T H，CHANG Y C.A hub location inventory model for bicycle sharing system design：Formulation and solution[J]. Computers&Industrial Engineering，2013，65（1）：77-86．

[3]李黎輝，陳華，孫小麗，等．武漢市公共自行車租賃點布局規(guī)劃[J]．城市交通，2009，7（4）：38-44．

[4]劉偉丹．自行車換乘軌道交通影響范圍研究[D]．南昌：華東交通大學，2016．

[5]盛昭瀚.主從遞階決策論一stackclberg問題[M]．北京：科學出版社，1998：114-116．

[6]YANG H，MENG Q.Highway pricing and capacity choice in a road network under a Build-operate-transfer scheme[J].Transportation Research A，2000，34：207-222．

[7]WILLIAM H K，LAM，NING ZHANG and H P L O.An optimal network design tool for additional cross links.Traffic and transportation studies[C].Proceedings of ICTTS’98ASCE，1998：652-661．

[8]孫會君，高自友．考慮路線安排的物流配送中心選址雙層規(guī)劃模型及求解算法[J]．中國公路學報，2003，16（2）：115-119．

[9]王文靜，敬明，劉冬梅，等.基于LOGIT模型和BPR阻抗函數的容量限制－多路徑交通分配研究[J]．公路交通科技，2012，29（S1）：80-86．

[10]韋增欣，梁碧清，羅朝輝.改進的阻抗函數及方式劃分配流模型[J].海南大學學報：自然科學版，2010，28（4）：363-369．

Study on Location of Public Bicycle Rental Points Based on Bi-level Programming Model

Ni Yong，Zheng Changjiang，Li Rui
（College of Civil and Transportation Engineering，Hohai University，Nanjing 210098，China）

With the increasing number of domestic urban car ownership,traffic pressure has become larger.In order to deal with the traffic problem of “the last kilometer”properly，and to improve the transfer between city subway and public bicycles，the scientific construction site and rational planning of public bicycle rental system are particularly important.According to the public bicycle rental location factors and layout criteria,we took into account the situation that there are two kinds of needs for borrowing and returning bikes at the public bicycle rental points,and referred to the principle of impedance function to establish the minimum total travel time model and build up a bi-level planning and location model of public bicycle rental points.Finally,through the calculation of practical examples，we determined the location of public bicycle rental points within the 400m range of the surrounding area of the subway and carried out evaluation and analysis.

public bicycle；rental points；planning location；bi-level programming model

U491

A

1005-0523（2017）03-0046-07

（責任編輯 王建華）

2016－12－13

國家自然科學基金（51508161）

倪勇（1992—），男，碩士，主要研究方向為交通運輸規(guī)劃與管理。

指導老師：鄭長江（1966—），男，教授，博士，主要從事交通控制與管理方面的研究。