基于双层规划模型的公共自行车租赁点选址研究

倪 勇，郑长江，李 锐

（河海大学土木与交通学院，江苏 南京 210098）

基于双层规划模型的公共自行车租赁点选址研究

倪 勇，郑长江，李 锐

（河海大学土木与交通学院，江苏 南京 210098）

随着国内城市汽车保有量日渐增加，交通压力变得越来越大。为了妥善处理“最后1公里”的交通出行问题，完善城市地铁与公共自行车的换乘衔接，构建选址科学，规划合理的公共自行车租赁系统显得尤为重要。按照公共自行车租赁点选址影响要素及布设准则，结合公共自行车租赁点同时存在借车与还车的两种需求的现实状况，并借鉴阻抗函数的原理，建立出行总时间最小模型，来构建出公共自行车租赁点双层规划选址模型。最后通过实例计算，来确定地铁周边小区需求点400 m范围内公共自行车租赁点位置，并进行评价分析。

公共自行车；租赁点；规划选址；双层规划模型

公共自行车作为城市公共交通的一部分，其所具有的机动灵活等特点，在中短距离的交通出行过程中优势明显，并通过与其他交通方式的衔接，能有效地提高城市居民的出行效率，其选址问题的研究也在得到更多学者的关注。Luigi Dell’Olio等[1]通过使用地理信息系统，构建起租赁点布设模型，在保证可达性的同时使公共自行车与公共交通实现相互衔接；Jean-Rong Lin[2]主要研究考虑自行车存储的自行车系统租赁站点选址的模型，该模型在原有模型基础上多考虑了库存的枢纽位置；李黎辉[3]探讨了武汉市的公共自行车租赁点布局规划理论，从定性的角度给出了自行车租赁点选址方法；李婷婷[4]的硕士论文主要研究了利用双层规划模型对自行车租赁点进行选址，该模型是以决策者建设成本最小和用户出行费用最低为上下层规划的目标。而本文研究的公共自行车租赁点选址问题，也利用的是主从递阶（或多层）决策[5]，并以决策者建设成本最小和用户出行时间最少为上下层规划的目标，以得出基于城市地铁换乘的公共自行车租赁点的一般选址规划方法。

1 双层规划模型定义

一般来说，双层规划模型具有如下形式：

这个模型的决策机制为：通过上层决策者做出的决策变量x，影响下层的目标函数和约束集；下层决策者在该条件下，做出使自身达到最优目标的决策y；同时，作为反馈的下层决策变量y也会影响上层决策问题的目标函数和约束集；通过此过程，上层决策者调整决策x，以实现最优目标。双层规划问题作为具有递阶结构的优化问题，是一类有两层决策问题的数学模型。其中称：

为双层规划问题（1）的上层规划问题，其中x称为上层变量；称

为下层规划问题，y称为下层变量。

因为双层规划问题是一个NP-hard问题，求解复杂，而双层规划所体现的非凸性、可行域的不连通性及合理反应映射的非单值性等则使求解变得更困难，能够求出的解通常也只是局部最优解。目前，大约已有十多种算法用于求解双层规划问题，将其归纳，一般有下降法、K-T法和非数值优化方法。国内外学者多年来都在研究双层规划模型的有效算法，如1992年Fries、Yang等人分别提出模拟退火算法[6]和灵敏度分析法[7]。

综上分析，非线性双层规划问题的求解算法均是以获取下层决策变量对上层决策的具体反应函数为核心内容，以实现将很多关于非线性规划问题方面的求解算法，能够较有效地应用于双层规划模型的求解中。

2 基于城市地铁换乘的公共自行车租赁点双层规划选址模型的建立

在公共自行车租赁点布局优化问题中，包含了两类不同目标的人群：一是政府运营部门通过制定布设方案，使系统总建设成本最低；二是使用者通过调整出行方式和路线，使总出行时间最少。因此基于城市地铁换乘的公共自行车租赁点布设问题适宜采用双层规划模型。结构图如图1所示。

图1 基于双层规划模型的公共自行车租赁点选址结构图Fig.1 Diagram of the public bicycle rental point location based on the bi-level programming model

2.1 模型的假设条件

本文的选址模型是针对通借通还的公共自行车租赁系统而构建，因而有需求点和租赁点。其中，需求点作为租赁点选址的第一要素，为降低模型的复杂度，本文有如下假定：

假设1：小区的需求集中在需求生成点，其不一定位于小区的重心；

假设2：将规划区域按地理条件、用地性质细分成若干个小区，地铁站点作为一个特殊的交通小区，提供足够的产生和吸引量；

假设3：出行者时间成本相同，且选择最近租赁点，故出行者到租赁点的单位费用设为常数；

假设4：公共自行车租赁点费用包括建设、运营和设备等方面，由政府提供且为常数。

2.2 双层模型的构造

城市地铁换乘处的公共自行车租赁点选址规划是指在一定的规划区域内进行对租赁点的位置选择和需求分配优化，并形成最终布设方案。图2为选址规划示意图。

2.2.1 上层模型

上层模型既要考虑经济素，也要考虑社会和自然环境因素。本文首要考虑决策者需求，将经济因素作为主要考虑因素，而社会和自然环境因素不作主要考虑。因此，政府的决策目标为：满足规划区域内需求点的需求量，并制定最优的租赁点布设方案使总建设成本最小。

本文利用离散工厂选址模型用于上层规划，建模如下：

图2 基于轨道交通换乘的公共自行车租赁点选址规划示意图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约束。在此需指出，上层规划模型中涉及到Dij，Qij的通过下层规划模型求得。

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 模型求解算法

本文双层规划模型中上层是用离散变量表示租赁点布设方案的非线性优化问题，当待选点很多时，计算求得该问题的精确解需花费较长时间。因此，本文针对下层模型中约束条件公式（8）的特殊形式，利用启发式算法进行求解[10]。在下层规划模型Pj中，通过分析，wij和Yj已知时，若至少一个为0，则Cij=0，即约束失效；若wij=1且Yj=1的条件下，则Cij≤M，其中M取充分大整数，则该约束条件恒成立，可不考虑。

因此，本文将约束条件不等式右侧减去松弛变量Zij以化为等式，即

若Yj=0，利则可直接得Cij，Zij的值；若Yj=1，先利用已有方法求解下层模型，以求解在稳定条件下各待选租赁点租还车数的需求分布Cij，经过反推可以得到Zij*。则反应函数为Cij=MwijYj-Zij*，其中i=1，2，…，n，j= 1，2，…，m，Zij*为松弛变量，把该反应函数公式带回上层的目标函数，然后通过分枝定界法求解上层规划。把求得的最优解再用到下层规划中，通过上述方法求出各待选点在稳定条件下的租还车次数需求分布，循环求解得模型最优解。计算过程如下：

步骤1：首先设定选址方案的一个初始解Yj0，令迭代次数t=0；

步骤2：对于给定的Yjt，计算下层规划模型得Cijt；

步骤3：计算得松弛变量Zij*，将Cij带回上层规划中求解，得到一组新的Yjt+1值；

3 算例分析

本文将双层规划模型实际应用于以杭州市轨道交通4号线钱江路站为中心的一个规划区域，以研究该区域内换乘轨道交通的公共自行车租赁点的选址规划。

根据公共自行车租赁点布局准则及交通小区道路空间条件，在各小区需求点400 m范围内设置初始租赁点，见图3中用带自行车的白色圆圈表示。其中，需求点和各租赁点之间的距离见表1。

图3 规划区域需求点和待选租赁点分布图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万，加上锁止器、软件、监控系统等，单个租赁点造价约为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软件对下层规划模型求解，得到租借者的租赁次数Cij分布。

第二步：由反应函数Cij＝MwijYj-Zij*计算得松弛变量Zij*，把上一步骤求得的Cij带回上层规划模型中，再利用LINGO软件来解答，算得新值：Yj1=（1，1，1，1，1，1，0，1，1，1，1，1，1，1，1，0，1）；

第三步：把得到的Yj1从开始步骤计算，假设t=1，反复上面的步骤，经历两次迭代从而得出模型最优解，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 结论

本文以地铁站及其周边小区来规划公共自行车租赁点的选址问题，利用双层规划模型计算得到该区域内换乘地铁的公共自行车租赁点布设方案；对比现有情况，提升了以地铁站点为中心区域内的公共自行车布点的科学性及可靠性。因会受到车辆的调度问题等的多方面要素的影响，仍需考察各个租赁点位置处的实际使用状况，分析出行者使用自行车时长，以优化调整公共自行车租赁点的选址与规模。

[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]李黎辉，陈华，孙小丽，等．武汉市公共自行车租赁点布局规划[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]孙会君，高自友．考虑路线安排的物流配送中心选址双层规划模型及求解算法[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—），男，硕士，主要研究方向为交通运输规划与管理。

指导老师：郑长江（1966—），男，教授，博士，主要从事交通控制与管理方面的研究。