解读Robust bike-sharing stations allocation and path network design: a two-stage stochastic programming model

摘要

如今，由于私家车的广泛使用所产生的影响，发展可持续交通系统(developing sustainable transport systems)的重要性正在被重新考虑。在这种情况下，自行车变得越来越受欢迎。为了鼓励骑自行车，自行车共享系统已经开发出来。然而，由于安全是人们骑自行车时最关心的问题，自行车共享系统应该是一个不可分割的项目的一部分，这个项目不仅包括停靠站(docking station)，还包括连接它们的专用自行车道网络。建立了一个两阶段随机规划模型，使系统覆盖的出行需求最大化。模型中考虑了一天中不同时段、出行强度和通勤需求水平的各种需求情景，以获得稳健的解决方案。以乌拉圭的蒙得维的亚市为例进行了一个真实世界的案例研究。所得解表明，该模型倾向于发展公交站与普通站之间连通性好的自行车道网络，所得网络具有良好的鲁棒性。

1. introduction

随着私家车数量的增加，交通系统的发展已经成为世界上许多大城市的一个重要问题。经济和时间损失、事故数量增加、交通堵塞、环境破坏和健康问题是以私人交通为导向的发展造成的一些后果(Akinyemi和Zuidgeest，2002年；达尔克曼和坂本2011；陈2019)。在有些情况下，公共交通系统的低效率阻碍了它的使用，并导致更多的私人车辆的使用。为了缓解交通问题，一个解决办法是改善公共交通系统，吸引更多的人使用私人交通工具，因为公共交通在城市空间需求和能源效率方面更有效(冯和谢长廷，2009年)。在这种情况下，自行车共享系统已被证明是短途旅行的绝佳选择，因为它是一种绿色技术、健康、负担得起的模式，并且更有效地利用土地空间(Gavin等人，2016年；Gonzalo-Orden等人，2014年；沙欣、古兹曼和张(2010)。在某些情况下，自行车甚至可能比汽车快，因为前者不受拥堵的影响。

然而，鼓励人们从驾驶私家车转向骑自行车是一项重大挑战，因为人们担心盗窃和停车问题，以及花钱购买自行车。一个关键的问题是安全，尤其是当适当的自行车基础设施没有很好地发展。作为一种解决方案，自行车共享系统已经在许多城市得到发展，为没有自行车的人提供共享自行车骑行。用户通常需要注册，然后收到一张支付旅行费用的卡。同一张卡用于在始发站解锁自行车。用户可以从起点附近的一个车站骑一辆自行车，然后把它送回离目的地不远的另一个车站。车站设计包括锁定自行车的特殊对接设备，以便当用户到达目的地车站时，自行车被锁定，并根据行程的持续时间对他们收费。通常，定价方案鼓励短期租赁(菲什曼，华盛顿和霍沃斯，2013年)，例如前30分钟通常是免费的。利用当前的信息技术，用户可以获得关于车站位置和自行车可用性的实时信息。

自行车共享系统不同于传统的自行车租赁计划，因为用户不需要在同一站归还自行车。因此，它们非常便于单程旅行。因此，自行车共享系统的出现不仅是缓解拥堵和一些交通相关问题的替代方案，如果不是最后一英里问题的可行解决方案，因为它适用于那些通过公交通勤但仍然必须步行才能到达目的地的旅行者。此外，这些系统也适用于观光或商业目的的旅行(佐藤，三和森川，2015年)。由于自行车共享系统要求自行车在特殊的车站被收取和归还，只有当车站靠近它们的起点和目的地时，用户才会使用它们。因此，台站定位对于开发成功的系统非常重要。此外，过去进行的研究一致认为，人们不愿意骑自行车通勤的主要原因是缺乏安全的骑行条件(达拉和昆罗伊特1995；麦克林托克和克利里1996)。菲什曼，华盛顿和霍沃斯(2012)得出结论，墨尔本公共自行车共享系统的用户数量并没有因为缺乏连续的自行车基础设施而增加。另一方面，预计自行车模式份额的增加将导致受伤自行车手人数的增加(Nilsson等人，2017年)。因此，为了鼓励人们骑自行车通勤，并最大限度地减少骑自行车增加的负面影响，在设计自行车共享系统时，应考虑连接车站的专用自行车路径网络。

受设计专用自行车道的自行车共享系统的启发，本文建立了一个优化模型，确定了车站的位置、在哪些路段上应建立自行车道以及每个开放车站应提供多少码头。通过最大化所设计的自行车道网络所能满足的总期望出行需求，所提出的模型生成了在各种出行需求场景下表现良好的鲁棒网络。据作者所知，目前还没有研究同时定位车站和开发自行车道网络，同时考虑其与其他交通方式的整合。因此，本文做出了重要贡献，并可能成为战略层面上的有用工具，因为它具有定位站点和开发考虑不同需求场景的循环路径网络的能力。

本文的其余部分如下。第2节进行了文献综述，第3节介绍了两阶段随机规划模型和线性化技术。第4节介绍了一个基于乌拉圭蒙得维的亚市的案例研究。最后，结论在第5节给出。

2. Literature review

文献综述集中在自行车共享站的最佳位置、车辆重新定位、自行车道网络设计和自行车交通集成。

已经进行了许多关于车辆共享系统的研究。
关于车辆重新定位优化，

• Dell’ Amico等人(2014)提出了四种混合整数线性规划公式(four mixed-integer linear programming formulations)来解决自行车共享再平衡问题，旨在最小化再平衡成本，
• 而Chemla、Meunier和Wolfler Calvo (2013)提出了一种算法来解决多对多的取货和交货问题，其中单容量车辆旨在重新分配一种商品。
• Raviv，Tzur和Forma (2013)提出了一个考虑不满意用户惩罚的成本最小化模型，
• Ho and Szeto(2014)使用迭代禁忌搜索启发式算法解决了静态自行车重新定位问题。
  关于自行车共享站的位置
• Martinez等人(2012)研究了包括普通自行车和电动自行车在内的混合共享系统的设计问题。开发了一个启发式混合整数线性程序，该程序同时优化共享自行车站的位置、车队规模，并测量正常运营日所需的自行车重新定位活动。* Frade和Ribeiro (2015)开发的优化方法采用了最大覆盖需求方法，结合了战略和运营决策。因此，车站的位置、每个车站中可用于最大化需求的自行车数量以及车队规模都得到了确定。
• García-Palomares，Gutiérrez，and Latorre(2012)提出一个基于GIS的方法计算 潜在出行需求的空间分布，使用位置分配模型定位站点，确定站点容量并定义每个站点相对于现有需求的特征。
  路径网络设计
• Lima、Gouvea和Mello提出了一个路径网络设计模型，在该模型中，考虑不同的道路特征，如地形、路面条件和与其他车辆的相对速度，确定了连接五个不同枢纽的最佳路径网络。
• 林和杨(2011)提出了一个整数非线性规划，它同时考虑了站点的位置和连接它们的路径网络。基于成本最小化，该模型试图建立站点的最优位置、连接站点的自行车路径的网络结构以及每个用户的最优出行路径。但是没有考虑再平衡，自行车和免费码头总是有的，没有考虑与公交的整合。

过去已经研究过发展自行车设施和增加自行车旅行需求之间的关系。多数研究得出结论，当提供安全舒适的骑行条件时，自行车通勤者的数量会增加。然而，其他研究人员在这个结论中并不如此明确，也确立了其他因素的重要性。

• 布勒和普彻(2012)分析了90个美国大城市自行车通勤的变化，重点是路径和车道的影响，得出结论认为，这些设施的存在鼓励了自行车运动。
• Ortú zar，Iacobelli和Valeze (2000)研究了智利圣地亚哥的特殊情况，得出结论认为，自行车道公里数的增加会增加愿意骑自行车的人数，但不会显著增加，因为即使在最严重的拥堵情况下，大多数汽车司机也不会选择自行车而不是汽车。
• 麦克林托克和克利里(1996)研究了自行车设施的重要性，以及它们对提高骑车人安全性、增加自行车模式份额的贡献。他们的结论是，特殊设施在自行车运动的吸引力方面发挥着重要作用，尽管作用有限。
• 亨特和亚伯拉罕(2007)研究了影响自行车使用的不同因素之间的关系。在他们的论文中，他们证实了在混合交通中骑自行车的时间被用户认为比在自行车道或路径上骑自行车的时间更繁重。
• 霍普金森和沃德曼(1996)研究了四种替代循环路线中影响循环倾向的因素，发现安全性比时间更受重视。

关于运输模式一体化(transport modes integration)，

• Anaya(2009年)介绍了物理和运营一体化的重要性。介绍了世界各地的不同案例，分析了向通勤者提供综合费用的相关性和智能卡的重要性。
• 以北京为例，赵和李(2017)研究了人们骑自行车往返地铁站的决定因素。强调了将自行车共享站设在地铁站附近以加强一体化的重要性。
• Sagaris and Arora(2016年)分析了可持续交通模式的好处，以及循环巴士一体化如何促进其发展。
• 最后，Bao等人(2017)使用真实的自行车轨迹作为输入数据开发了自行车道分配的优化模型。得出的结论是，由于大多数旅行都是在公交车站开始或结束的，因此将它们与自行车道连接起来是有成本效益的。

3. Model formulation

3.1 model description

由于开发自行车共享系统的可用资金通常有限，开放站点的数量也受到限制。因此，为了最大限度地满足出行需求，优化车站位置非常重要。此外，提供连接这些车站的受保护的自行车道是必要的，因为缺乏安全的乘坐条件是通勤者不骑自行车的主要原因。通过考虑不同的需求场景，在设计过程中也考虑了出行需求的不确定性。提出了一个两阶段随机规划模型，使设计的单车道网络满足的需求最大化。在第一阶段，确定网络布局，确定站点的位置和尺寸，并分配循环路径网络。在第二阶段，在每个需求场景和一天的每个时间段下，确定设计的循环路径网络能够满足的出行需求。因此，可以获得健壮的解决方案，因为它们在不同的需求场景下是可靠的.

自行车网络可以定义为一个图 G = ( N , A ) G=(N,A) G=(N,A)，其中， N N N代表候选的自行车站点的节点集合， A A A表示两个相邻站点之间的自行车道的链路集合。图1显示了自行车站点分配和路径网络设计。候选自行车站和车道如图1(a，b)所示，显示了一个构建的自行车道网络的示例。可以看出，车站2和6分别通过自行车道1-2和 cycle lanes1-6直接连接到中转站(transit station)。车站2和6也通过专用cycle lanes2–6直接相互连接。类似地，车站5和7分别通过cycle paths1-2-5和1-6-7间接连接到中转站。不同的是，沿着他们的路径有一个中间站(intermediate station)。然而，由于相对较低的出行需求和不足的建设预算，车站3和4没有通过自行车道连接。

基于已定义的自行车站和车道网络，提前生成可行的自行车路径(fesible cycle paths)[可以对应于 K w K_w Kw​]，这些自行车路径可以被每对origin-destination(OD)pair可以使用。在本文中，我们将 k k k条最短路径作为可行自行车路径，这些路径可以由Yen (1971)中的算法和Jin等人(2014)中的整数规划方法生成。以图1为例，连接OD对2和6的可行自行车路径包括一条直接路径2–6和两条间接路径2-1-6和2-7-6。

ODpair 为2和6
根据“每个ODpair可以在自行车网络中找到可行的自行车路径paths”，得到直接路径2-6和间接路径2-1-6、2-7-6
因此 K ( 2 , 6 ) = { p a t h 2 − 6 , p a t h 2 − 1 − 6 , p a t h 2 − 7 − 6 } K_{(2,6)}=\{path2-6,path2-1-6,path2-7-6\} K(2,6)​={path2−6,path2−1−6,path2−7−6}

一旦确定了自行车路径网络，我们就可以检查每个可行路径是否完全被专用自行车车道覆盖。因此，可以识别旅行需求是否得到满足。如果有一条自行车道连接其始发站和目的站，并且完全由专用自行车道覆盖，则可以满足出行需求。然而，我们假设最短路径提供了完全的需求满足，而其他较长的路径只能满足总需求的一定比例，因为走弯路会阻碍自行车的使用。例如，对于图1(b)中车站2和6之间的出行需求，如果在连接2–6上修建专用自行车道，则可以满足全部需求。然而，自行车路径2-1-6和2-7-6只能满足一定比例的需求。我们引入了一个参数 β w k \beta_{wk} βwk​，表示自行车路径 k k k满足OD对 w w w的出行需求的占比。如果路径 k k k是最短路径，那么 β k w \beta_{kw} βkw​等于1.0；否则， β w k < 1.0 \beta_{wk}<1.0 βwk​<1.0。请注意，该参数应根据研究区域的实际情况进行预校准。如果没有包含整个专用自行车道的自行车道，则无法满足出行需求。以图1(b)为例，可以满足车站5和6之间的出行需求，但不能满足车站4和6之间的出行需求。

3.2 Mathmatical model

以下是问题表述中使用的决策变量、集合和参数的描述。

基于上述符号，自行车共享站分配和路径网络设计问题可表述为以下两阶段随机规划模型:

max ⁡   E ξ { Q ( ξ ) } (1) \max\ E_{\xi}\{\mathcal{Q}(\xi)\}\tag{1} max Eξ​{Q(ξ)}(1)

Ω \Omega Ω是需求场景集合
T T T是一个小时的时间步长集合
W W W是自行车需求的ODpair的集合
ξ ∈ Ω \xi \in \Omega ξ∈Ω是在时间 t ∈ T t\in T t∈TOD pair w ∈ W w\in W w∈W的行程需求数值
公式（1）是最大化所有需求场景下的满足出行需求 Q ( ξ ) \mathcal{Q}(\xi) Q(ξ)的期望

subject to :

在第一阶段的决策包含了自行车站点位置（ x i 和 z i x_i和z_i xi​和zi​）和自行车车道建设（ y i j 和 δ w k y_{ij}和\delta_{wk} yij​和δwk​）

x i ≥ y i j ∀ ( i , j ) ∈ A (2) x_i \geq y_{ij} \quad \forall(i,j)\in A \tag{2} xi​≥yij​∀(i,j)∈A(2)
x j ≥ y i j ∀ ( i , j ) ∈ A (3) x_j\geq y_{ij} \quad \forall (i,j)\in A \tag{3} xj​≥yij​∀(i,j)∈A(3)

x i ∈ { 0 , 1 } x_i\in \{0,1\} xi​∈{0,1}:如果自行车站点 i ∈ N i\in N i∈N被选择的话，则为1；否则为0【决策变量】
y i j ∈ { 0 , 1 } y_{ij}\in \{0 ,1\} yij​∈{0,1}:如果自行车车道被建立在link ( i , j ) ∈ A (i,j)\in A (i,j)∈A上，则为1.【决策变量】
constraints(2)和(3)利用 x i 和 y i j x_i和y_{ij} xi​和yij​之间的关系确保，一旦link ( i , j ) (i,j) (i,j)被建立(built)，则相应的站点则被选中。

z i ≤ Z m a x x i ∀ i ∈ N (4) z_i\leq Z_{max}x_i \quad \forall i\in N\tag{4} zi​≤Zmax​xi​∀i∈N(4)

z i ≥ 0 z_i\geq 0 zi​≥0:在站点 i ∈ N i\in N i∈N的自行车停泊的数量。【决策变量】
constraint(4)保证码头的数量不能超过上限

∑ ( i , j ) ∈ A α i j w k y i j − L w k ≥ M ( δ w k − 1 ) ∀ w ∈ W , ∀ k ∈ K w (5) \sum_{(i,j)\in A}\alpha^{wk}_{ij}y_{ij}-L_{wk}\geq M(\delta_{wk}-1)\quad \forall w\in W,\forall k\in K_w\tag{5} (i,j)∈A∑​αijwk​yij​−Lwk​≥M(δwk​−1)∀w∈W,∀k∈Kw​(5)

α i j w k \alpha^{wk}_{ij} αijwk​是一个表示link ( i , j ) (i,j) (i,j)和ODpair w ∈ W w\in W w∈W的路径 k k k之间的关系的二进制系数。如果link ( i , j ) (i,j) (i,j)属于ODpair w ∈ W w\in W w∈W的路径 k k k,则为1；否则为0.
L w k L_{wk} Lwk​是ODpair w ∈ W w\in W w∈W的路径 k k k的links的数目。
M M M是一个足够大的常数
δ w k ∈ { 0 , 1 } \delta_{wk}\in \{0,1\} δwk​∈{0,1}:如果自行车车道被建立在ODpair w ∈ W w\in W w∈W的路径 k ∈ K w k\in K_w k∈Kw​的所有links上，则为1；否则为0.
K w K_w Kw​是ODpair w ∈ W w\in W w∈W上的自行车网络中所有的可行路径。
举例： w = O D p a i r ( 2 , 6 ) w=ODpair(2,6) w=ODpair(2,6), k = p a t h 2 − 7 − 6 k=path2-7-6 k=path2−7−6
显然link α 27 w k , α 76 w k \alpha^{wk}_{27},\alpha^{wk}_{76} α27wk​,α76wk​是路径 k = p a t h 2 − 7 − 6 k=path2-7-6 k=path2−7−6上的链接，则值为1.
然后通过 y i j y_{ij} yij​判断link ( 2 , 7 ) , ( 7 , 6 ) (2,7),(7,6) (2,7),(7,6)是否建立了专门的自行车车道(cycle lanes),如果建立了则值为1
因此， ∑ ( i , j ) ∈ A α i j w k y i j \sum_{(i,j)\in A}\alpha^{wk}_{ij}y_{ij} ∑(i,j)∈A​αijwk​yij​在本例中的值最大为2[每个link都建立了cycle lanes] (若考虑对称性，则为4)，最小为0[每个link都没建立cycle lanes]
L w k = 2 L_{wk}=2 Lwk​=2
δ w k \delta_{wk} δwk​=1表明在ODpair w = ( 2 , 6 ) w=(2,6) w=(2,6)上的path k = p a h t 2 − 7 − 6 k=paht2-7-6 k=paht2−7−6上的所有 l i n k ( 2 , 7 ) , l i n k ( 7.6 ) link(2,7),link(7.6) link(2,7),link(7.6)都建立了cycle lanes.