随着中国城市化、机动化的发展，城市交通拥堵越发严重，公共交通虽然可以缓解交通压力，但无法解决“最后一公里”问题。公共自行车作为新型的交通方式，以其灵活便捷、易与其他公共交通方式连接的特性，可以有效弥补传统交通方式的不足。

公共自行车主要服务于短距离出行，特别是作为公共交通的换乘方式解决远距离出行问题。因此，许多学者对公共自行车与公共交通的接驳展开研究。朱从坤, 等^[1]将轨道交通站点处的公共自行车使用者分为接驳和非接驳两类，研究站点处的客流量预测问题。周强和吴戈^[2]通过调查问卷分析苏州公共自行车作为地铁接驳手段的使用特征。甘勇华^[3]对自行车与城市轨道交通换乘客流空间分布特性、衔接的必要性、衔接设施布局模式等方面进行探讨。陈景旭和王炜^[4]以轨道交通站点为接驳中心，提出分层分级布设公共自行车租赁点的布局方法。作为公共自行车系统成功的关键因素之一，站点选址问题在国内外被广泛研究。HE, 等^[5]从出行方式分担交通分配的角度研究区域出行成本最小的自行车站点布局方案。此外，不少学者针对用户需求变化^[6]、公共自行车系统的战略规划及长期运营等角度研究公共自行车站点的选址问题^[7]。为保障自行车用户的通行权，韩强和周勇^[8]提出以自行车出行率、自行车和机动车用户均衡为上下层模型对公共自行车路网进行规划。为提高公共自行车系统的服务水平，LIN和YANG^[9]将站点规模和用户服务水平作为影响公共自行车站点选址布局的因素，设计基于贪婪思想的启发式算法确定站点和自行车道的选址。在此基础上，ASKARI, 等^[10]更多关注公共自行车系统的安全性问题，建立以建设成本以及安全性水平为多目标的自行车网络规划模型。

从上述研究可知，目前对公共自行车的接驳研究主要集中为在轨道交通方面，较少考虑公共自行车与公交车的接驳问题，并且对公共自行车系统的网络规划主要考虑站点的布局，很少考虑自行车道的规划。基于上述研究现状，笔者从公共自行车与公交车接驳的角度，对公共自行车系统的站点选址布局和专用道设置问题进行研究。首先构建模型，在比较传统模型基础上，通过分析问题特性基于禁忌搜索的智能算法求解问题。最后，通过大量仿真实验，验证模型及算法的有效性，通过敏感性分析实验进一步为构建合理公共自行车网络提供参考依据。

1 问题描述及模型构建

研究公共自行车站点选址问题旨在公交站点和周围区域设置公共自行车站点，以解决公共交通的短距离接驳问题，满足出行者较长距离的出行。与现有自行车站点选址问题不同，研究自行车站点选址问题还考虑在自行车站点之间设置自行车道，提高公共自行车出行比率，保障自行车用户出行的安全性、舒适性和快捷性。因此，对基于公交车接驳的公共自行车站点选址及专用道设置问题进行研究，即在投资成本有限情况下，通过合理选址自行车站点和设置自行车专用道，最大化满足用户的出行需求。

1.1 基本假设

为更好地研究自行车站点选址问题，做出如下假设。1)每个候选站点的自行车出行需求量已知。2)设置在2个公交站点处的公共自行车站点之间的距离不能小于一定的距离。3)为实现公共自行车的短距离接驳，设置在公交站点处的公共自行车站点和周围区域的公共自行车站点的距离不能超过最大距离。4)自行车专用道设置在公交站点和其周围的公共自行车站点之间。笔者考虑的公共自行车主要用于公共交通出行的末端接驳，因此自行车站点设置在公交站位置及周围临近区域。

1.2 符号及变量定义

为了清晰明确地构建问题模型，定义参数和变量如下。令I表示公交站点集合，J_i表示公交站点i附近的自行车候选站点集合，f_i(或f_j)表示在点i(或点j)处设置公共自行车站点的费用，c_ij表示在点i和j之间设置自行车专用车道的费用，M表示建设公共自行车网络的总投资成本。r_ij表示点i和j之间的距离。d_j和d′_j分别表示有自行车专用道连接和未有自行车专用道连接点j时的自行车出行需求。λ表示选址在不同公交站处的公共自行车站点之间的最小距离。R表示公交站点与其周围选址的公共自行车站点间的最大距离。决策变量x_i、y_j、z_ij均为0—1整数变量，其中x_i(或y_j)表示是否在点i(或点j)处设置自行车站点，z_ij表示是否在点i和j之间设置自行车专用车道。

1.3 模型构建

根据定义的参数和变量，可将公共自行车站点及车道选址优化问题构建如下模型P。

$ \sum\limits_{i \in I} x_{i} \sum\limits_{j \in J_{i}} y_{j}\left(d_{j}\left(1-z_{i j}\right)+d_{j}^{\prime} z_{i j}\right), $

(1)

$ \text { s.t. } \quad \sum\limits_{i \in I}\left(f_{i} x_{i}+\sum\limits_{j \in J_{i}} f_{j} y_{j}\right)+\sum\limits_{i \in I}\sum\limits_{{j} \in J_{i}} c_{i j} z_{i j} \leqslant M, $

(2)

$ x_{i}+x_{i}^{\prime} \leqslant 1, \forall i, i^{\prime} \in I, i \neq i^{\prime}, d_{i i^{\prime}} \leqslant \lambda, $

(3)

$ y_{j}\left(r_{i j}-R\right) \leqslant 0, \forall i \in I, \forall j \in J_{i}, $

(4)

$ y_{j} \leqslant x_{i}, \forall i \in I, \forall j \in J_{i}, $

(5)

$ 2 z_{i j} \leqslant x_{i}+y_{j}, \forall i \in I, \forall j \in J_{i}, $

(6)

$ x_{i} \in\{0, 1\}, \forall i \in I, $

(7)

$ y_{j} \in\{0, 1\}, \forall j \in J_{i}, i \in I, $

(8)

$ z_{i j} \in\{0, 1\}, \forall i \in I, \forall j \in J_{i}. $

(9)

目标函数(1)为最大化满足自行车用户的需求。当点j处有设置自行车站点，可满足需求d_j，若点j处还有自行车道与其连接，可满足需求增至d′_j。约束(2)表示建设公共自行车网络的总成本(包括自行车站点和专用车道的建设费用)不能超过投资成本M。约束(3)表示不能在临近的2个公交站(之间距离不超过λ)同时设置自行车站点。约束(4)表示只能在与接驳公交站点距离R的范围内设置公共自行车站点。约束(5)表示只有在接驳公交站点处设置公共自行车站点后，才有必要在其周围设置公共自行车站点。为保证用户骑行的安全性以及舒适性，约束(6)限定自行车专用车道设置在2个自行车站点之间。约束(7)—(9)表明决策变量是0—1整数变量。

将模型P中自行车道变量z_ij的值设置为0，可得到如下只考虑站点选址的模型P′。

$ \max \sum\limits_{i \in I} x_{i} \sum\limits_{j \in J_{i}} x_{j} d_{j}, $

(10)

$ \text { s.t. } \sum\limits_{i \in I}\left(f_{i} x_{i}+\sum\limits_{j \in J_{i}} f_{j} y_{j}\right) \leqslant M, $

(11)

显然模型P′是P的特殊情形。由于P′不考虑建设自行车专用车道，在同样投资成本下可以(比P)建设更多的自行车站点。但另一方面，由于自行车车道的缺少，可能导致潜在自行车出行需求的流失。是否需要建自行车道以及如何分配资金建设站点和专用道将是规划者需要决策的重要问题。

2 算法设计

在研究公共自行车站点选址的基础上，还考虑自行车道的设置，它是一个NP-难问题。该问题的复杂性会随着问题规模增大呈指数增长，通常难以在合理的时间内求出问题的最优解。因此针对问题特性设计性能优越的元启发式算法获得高质量解是解决该问题的一种有效思路。

禁忌搜索算法作为一种高效的元启发式算法，在过去的几十年中被广泛成功应用于求解旅行商问题^[11-12]、设施选址问题^[13-14]、选址路径问题^[15-16]等各种复杂优化问题。不同于其它元启发式算法^[17-18]，禁忌搜索由Glover于1986年提出^[19]，它在邻域搜索思想的基础上引入特有的存储结构——禁忌表来记忆过去的搜索信息，以避免搜索陷入局部最优，同时通过特赦准则赦免一些被禁忌的优良状态，从而引导搜索趋于全局最优解。下面将结合所研究问题的特性，构造基于禁忌搜索算法的问题求解方法。

2.1 初始解

初始解由x_i、y_j、z_ij这3类变量构成，下面分别确定它们的取值。首先，随机选定一组满足约束(3)的x_i作为接驳公交站。其次，选定一组公交站点周围的自行车站点y_j，并检验是否满足约束条件(4)和(5)，否则重新选择新的站点位置。由于自行车专用道设置在公交站和自行车站点之间，先根据x_i和y_j的取值及约束(6)将所有可能的路段设置为自行车专用道。若所有设置自行车站点和专用道的总成本满足投资成本约束(2)，则得到初始解；否则根据(d′_j-d_j)/c_ij，按升序排列逐条减少性价比低的专用道，直至满足约束(2)，从而得到z_ij的取值。

2.2 移动、邻域解

当前解的邻域由一系列邻域解构成。这些邻域解是对当前解进行“移动”操作所获得。由于问题的3类变量属于不同层次的决策，所以移动操作涉及的对象不是当前解的全部变量，而仅仅是选址变量x_i, i∈I，具体而言是将移动操作定义为公交站点i设置状态的改变。为表述方便，令(x_i, y_j, z_ij)表示当前解，则公交站集合I根据当前状态可被划分为未设置自行车站点的公交站集合I_c={i∈I|x_i=0}和已开设自行车站点的公交站集合I_o={i∈I|x_i=1}。根据说明，定义close、open和swap3种类型的移动，准则如下：1)将已开设的自行车站点关闭，即将I_o的一个元素移入到I_c；2)新开设一个自行车站点，即将I_c的一个元素移入到I_o；3)同时新设一个站点以及关闭一个已设站点，即交换I_c和I_o的各一个元素。

根据上述定义，经过移动操作后可首先确定邻域解中设置自行车站点的公交站x_i的位置。此外，还需进一步确定其周围自行车站点y_j的位置及自行车专用道z_ij的设置信息。由于问题的目标最大化满足出行需求受到投资成本制约，在设置自行车站点和自行车道时考虑它们的“性价比”，即需求成本值。对每一个可设置自行车站点的位置j，计算其d_j/f_j，表示在点j设置自行车站点单位成本所满足的需求。此外，若有自行车专用道连接点j，其需求成本值计算公式为d′_j/(f_j+c_ij)。将上述所有自行车站点和自行车道的性价比降序排列，在满足投资成本约束条件下，逐个设置性价比最高的站点和自行车道，直至剩余资金不足以新设一个自行车站点或一条自行车道。注意对于设置自行车站点的位置j，要么设置有专用道与其连接，要么没有设置，只能是两者中一种情况。所以对于同一个j，只能选择d_j/f_j(表示在点j处设置自行车站点，但没有设置专用道与其连接)或者d′_j/(f_j+c_ij)(表示在点j处设置自行车站点，且设置专用道与其连接)。

这样，对于close或open移动，首先根据移动的定义确定设置自行车站点的公交站的位置，然后计算剩余资金，再根据贪婪思想按照性价比选择原则确定在公交站周围设置的自行车站点及自行车道。对于swap移动，可看成是close和open移动的复合，依次计算关闭、开放公交站位置的自行车站点后的资金变化，再根据剩余资金和性价比选择原则确定邻域解。

根据上述定义的3类移动，对当前解进行每一个移动操作，都可获得一个可行邻域解。其中，open移动可增加目标值，使得当前解向最优解的方向移动；close移动虽然会降低目标值，但是搜索的空间更广，易于跳出局部解。通过close和open2种移动的操作，使得设置自行车站点的公交站达到一个合适的数量。此外，swap移动通过调整设置自行车站点的公交站的集合，可使邻域解趋向最优解。

2.3 最佳邻域解、特赦准则

为进行下一次迭代，需要在邻域中选择最佳的邻域解，用其更新当前解。根据禁忌搜索的思想，在最近若干次迭代过程中的一部分邻域移动是禁忌的，避免搜索陷入局部最优。另一方面，搜索过程是寻找全局最优解，若邻域解优于当前最好解，即使它是禁忌的，可以使用特赦准则取消禁忌，选取该邻域解作为最佳，从而使得搜索趋近于全局最优解。因此在当前解的邻域中选择最佳的邻域解不能简单地通过比较目标值得到，还需要考虑邻域解的禁忌状态。

通常做法是将所有的邻域解按照目标值升序或降序排列，然后根据目标值以及禁忌状态选择最佳邻域解。尽管排序算法的时间复杂度是多项式的(通常为O(n²)，其中n为邻域解的个数)，为节省计算时间，不对邻域解进行排序，而是记录最佳目标值以及禁忌状态。具体地，若邻域解的目标值优于当前最好目标值，则标记该邻域解为最佳邻域解并更新当前最好目标值；否则当前最好解不能被更新，需要找到目标值最佳的非禁忌邻域解。这样，当遍历一次所有的邻域解，便能找到最佳邻域解，时间复杂度为O(n)。

2.4 禁忌表

3种邻域移动对是否在公交站处设置自行车站点(即变量x_i, i∈I)进行操作，将这些相关的变量设置为禁忌对象。具体而言，若选中的最佳邻域解是由当前解经过open移动得到，则将该移动中新设自行车站点的公交站位置变量x_o, o∈I记录在禁忌表；若最佳邻域解是通过close移动得到，则将该移动中关闭自行车站点的公交站位置变量x_c, c∈I记录在禁忌表；若最佳邻域解是通过swap移动得到，将该移动中相关的变量x_c和x_o, o, c∈I同时记录在禁忌表，并更新禁忌表。在后续的若干次迭代中，禁忌表中的变量为禁忌状态，相应的邻域移动是禁止的(除非使用特赦准则)，直至变量变为解禁状态。

2.5 算法终止条件

与大多数迭代搜索类似，当算法完成最大迭代次数即被终止。此外，若当前最好解在一定迭代次数内未改进，为避免搜索陷入局部最优，对算法进行初始化，生成新的当前解。

综上基于禁忌搜索的求解方法总结为如下算法1。

算法1：

1) 初始化：设置当前最好解未改进的最大迭代次数impMax、未改进当前次数impIter=0、禁忌表；生成初始解，并赋给当前解、当前最优解。

2) 令impIter=impIter + 1。

3) 由当前解定义邻域移动，并求得邻域解及其目标值。

4) 对每一个邻域解：

  a) 如果邻域解优于当前最优解：更新当前最优解、最佳邻域解。令impIter=0。

  b) 如果当前最优解未被更新：如果邻域解优于最佳邻域解且为非禁忌状态，则更新最佳邻域解。

5) 更新当前解、禁忌表。

6) 如果impIter > impMax，重新产生当前解。

7) 如果满足终止条件，输出当前最好解以及目标值；否则转入步骤2。

3 仿真实验

采用MATLAB 2016a编写禁忌搜索算法，通过大量算例来评估算法1。仿真实验的计算机环境为Intel(R)Core(TM) i5-4590 CPU，8 GB RAM，Windows 7系统。实验共测试28组(5个/组)随机产生的算例，实验结果均为每组5个算例的均值。

为表述方便，用|I|、|J|、M分别表示公交站点个数、公共自行车候选站点个数、投资成本；用ZP(TP)、ZP′(TP′)、ZT(TT)分别表示采用模型P、模型P′、禁忌搜索算法得到的目标函数值(计算时间，单位s)，其中P为构建的自行车站点及自行车道联合选址模型，P′是仅考虑自行车站点选址的模型。实验结果呈现在表 1~4。

为验证设置自行车专用道的有效性，实验首先采用软件Lingo对非线性模型P和P′进行求解比较，实验结果如表 1。可以发现对于不同规模的算例1~6，模型P的目标值ZP均优于P′的ZP′，最大差距为算例1的1.22(= 123/101)倍。ZP的均值为543，是ZP′均值的1.17(= 543/466)倍。此外，模型P的求解时间均不超过10 s，均值为3 s，是TP′均值的0.30(= 3/10)倍。从实验结果可以发现，相比较模型P′仅考虑站点的选址，模型P还考虑自行车道的建设，可以为自行车用户提供较为安全、舒适的骑行环境，吸引更多潜在用户，因此模型P是优于P′的，能够更加有效提高公共自行车系统的用户满足程度。比较实验结果可以发现，尽管模型P′设置的自行车站点数少于模型P的结果，但是通过决策专用道的设置，其目标函数值以及计算时间均更优越。由此可见，对于构建公共自行车系统的网络设施，在布局自行车站点的同时，合理设置自行车专用道能够吸引更多潜在用户，从而更加有效提高公共自行车系统的用户需求满足程度。

为评估基于禁忌搜索的算法1的性能，实验2不仅与Lingo比较8组不同规模的算例求解结果，还与常见的模拟退火(SA, simulate anneal)、遗传算法(GA, genetic algorithm)进行比较。为公平地比较各方法，SA、GA的搜索迭代次数与算法1大体相同，且SA、GA的初始解(种群)、迭代搜索的算子操作采用算法1中类似操作。令TA(ZA)、TG(ZG)、TT(ZT)分别表示SA、GA、算法1的目标值(求解时间，s)，GA、GG、GT则表示各方法与Lingo的最优目标值的相对差，结果见表 2。从目标函数来看，算法1的目标值与Lingo的结果十分相近，相对差GT在0.41%~0.98%之间，平均相对差为0.69%，SA和GA的平均相对差为3.33%和2.79%。从求解的整体效率来看，算法1效率最高，平均求解时间为18 s，只有Lingo的0.78倍，SA和GA的求解效率均明显劣于算法1。当求解算例14时，Lingo由于内存问题已无法求解该问题，而其余3种算法均能求解，且算法1在解的质量以及效率方面均优于SA和GA。从表 2可以看出随着公交站点和自行车站点的增加，算例规模逐渐增大，算法1能够高效可靠地求解各类规模大小的问题。综上，在此实验中禁忌搜索算法的性能最为优越，目标值及计算时间均最优。SA与GA相比，计算效率较好，但是结果不如GA。通过上述3种算法的比较，可以看出SA性能受初始温度、降温速率等参数影响较大；GA性能主要依赖于受染色体编码、遗传算子等操作；禁忌搜索主要与邻域结构相关，这是与问题结构、特性密切相关的。可见，设计性能优越的算法需要分析问题结构，采用适合问题特性的求解策略。

为进一步验证模型P的有效性，对模型的参数做敏感性分析。表 3呈现的是参数R(即在公交站点周围设置公共自行车站点与其的最大距离)对目标值的敏感性分析实验结果。将R=5作为参照基准值，同时分别选取R=3和R=7作为较小的数值和较大的数值进行比较。当R变化时，公交站点周围的自行车候选站点总数与公交站点总数的比值|J|/|I|相应变化。从表 3的实验结果可以发现当R=5时用户的满足程度最大，目标函数的平均值为2 930；当R=3时，目标函数的平均值为2 580；当R=7时，用户的满足程度最小，目标函数的平均值为1 780。从表 3的实验结果可以发现当R=5时的平均用户满足程度为2 930，明显优于R=3和R=7时的满足程度。由此可见，公共自行车接驳公交的距离对自行车用户的满足程度产生较大的影响，二者之间的距离不宜过长或过短，这与公共自行车作为公共交通的短距离接驳工具的特点是相符的。接驳距离过短，单位面积的站点过多，会导致单个站点的覆盖用户人数较少，浪费资源；接驳距离过长，站点分布稀疏，导致用户还车站点离最终目的地较远，降低用户采用公共自行车出行的意愿。规划者在设置站点间隔距离时，应该在充分调查数据及分析研究的基础上，确定自行车接驳公交的合理距离范围。

此外，实验还对自行车道的建设成本c_ij进行敏感性分析。对同一规模的算例，测试2种建设成本类型的专用道。类型一自行车道的单位成本为7~9，类型二自行车道的单位成本为10~12。类型一自行车道成本低，但安全性和舒适度低，类型二自行车道则反之。CL、CB分别表示最终方案中建设公共自行车站点花费的资金、建设自行车道花费的资金；p_L(= CL/M)，表示建设专用车道的资金占总投资成本的比值。

实验结果如表 4所示，对同一规模算例，随着专用道建设成本的增加，建设专用道的数量会减少，目标函数值相应降低。当建设类型一的自行车道时，自行车道的建设资金占总成本的0.27~0.30，平均值为0.28。当建设类型二的自行车道时，建设自行车专用车道的资金比例在0.22~0.27，平均值为0.24。可见，当建设自行车系统网络的成本一定时，即使不同规模的自行车网络，用于自行车道的建设资金比例都趋于一定范围。上述实验结果表明，面对不同规模的网络以及单位建设成本，规划者应合理地规划公共自行车站点和自行车道的投资比例，使得在有限的资金状况下，构建的公共自行车系统形成“点”、“线”相连的网络结构，提高公共自行车系统的服务人群。

4 结语

近年来，公共自行车系统得到较快发展，公共自行车系统的网络规划问题得到广泛关注。从“公共自行车公交车”接驳的角度，研究公共自行车的站点选址及自行车道设置的网络规划问题。通过运用运筹优化的思想，构建自行车网络非线性规划模型，通过决策公共自行车站点选址和站点间自行车道的设置，使得规划的自行车网络最大化满足自行车用户的需求。通过MATLAB软件实现基于禁忌搜索算法。并通过大量仿真实验表明，构建考虑自行车专用道的选址模型优于仅考虑站点布局的选址模型；在求解问题的计算时间和目标值方面，设计基于禁忌搜索的算法优于规划软件Lingo、模拟退火算法和遗传算法，充分验证模型和算法的可靠性和有效性。此外，通过对模型参数进行敏感性分析发现：a)公共自行车接驳公交的距离要在合理距离范围内以提高用户需求；b)自行车道是公共自行车网络的重要部分，合理规划站点与车道的投资比例，能够满足更多用户的出行需求。

公共自行车的发展促进低碳出行的发展，在后续研究中，可将减少碳排放因素考虑到公共自行车网络构建中，使得公共自行车系统更加符合可持续发展的目标。