基于双层规划的老城区自行车专用道网络设计

王 丰，刘昊翔，2

（1.合肥工业大学，汽车与交通工程学院，合肥 230009；2.合肥工业大学，安徽省智慧交通车路协同工程研究中心，合肥 230009）

0 引 言

随着社会经济的迅速发展，私家车的保有量逐年增加，老旧城区的交通拥堵问题变得日益严重。尤其是老城区人口居住量大，有大量的短距离出行需求，比如，出门买菜、接送小孩、“最后一公里”等。国内大部分城市的老城区由于历史和经济原因，道路狭窄且密集，且部分特殊区域，如城中村、传统老街等，由于道路空间的限制，公共交通站点覆盖率较低，导致有限的道路供给无法满足大量的出行需求，很容易造成老城区机非车流混合且极易拥堵的交通状况。已有研究表明[1-3]，在老城区中合理地规划自行车路网，可以提高自行车出行的分担率，同时能减少机动车出行，从而有效地缓解交通拥堵。如何在老城区合理地规划自行车专用设施，是政府部门进行交通规划的难题。

自行车作为一种慢行交通方式，其基础配套设施的规划是城市交通规划领域的重要组成部分，2017 年，刘兰辉等人[4]基于上海南汇新城自行车交通流和自行车道路设施的现场调查和分析，从路网连续性、路面平整度等角度提出了完善自行车交通设施的措施与建议。2018年，李翔[5]提出了由以“车”为本到以“人”为本的理念，并基于这种理念对广州市自行车交通相关的道路规划和设计提出优化建议。2019年，许珂源等人[6]在研究慢行交通中提出在中心城区通过修建自行车专用道可以提供更加便利和绿色的出行方式，自行车可被作为短途通勤和多种出行方式间接驳的重要出行方式之一。杨永平和陈春羽[7]分析了国内外自行车发展及趋势，提出了自行车专用路的设计要点，为后续自行车专用路的发展提供了参考。2020年，黄玥和干宏程[8]从自行车出行路径选择行为影响因素、模型方法、实验调查方法以及应用场景等方面系统梳理了自行车出行路径选择偏好的研究成果。许乃星和陈亮[9]深入分析自行车专用路的网络分级、规划原则、设置形式、宽度与坡度、节点通过方式、出入口与衔接、服务配套等建设技术指标，为自行车专用路规划与建设提供了指导。以上以慢行交通为背景的研究主要从定性研究的角度，从车道宽度、路面平整度、机非隔离带、自行车道的连通性等方面分析了自行车基础配套设施的合理度，并结合实际提出了优化建议。

除了定性研究以外，也有学者从定量的数学建模角度对自行车网络设计问题进行了分析研究。2017 年，宋青等人[10]在对真实骑行者路径选择行为深入分析的基础上，提出了基于Open Street Map 的城市自行车网络的构建方法及基于其上的多判据自行车路径优化的数学模型，并给出了求解该模型的一种基于聚类的最优多判据路径规划方法。Mauttone[11]等人以最小化用户和规划者的费用为目标函数，建立了一个混合整数规划模型，并设计了一个遗传算法对模型进行求解，采用算例分析验证了算法和模型的有效性。2018年，Chen[12]采用网络流技术和数学规划方法，针对现有的自行车网络系统，构建了自行车网络设计模型。该模型的目标是在满足相关运营约束的前提下，使骑自行车者的出行时间最小化，将提出的模型表述为混合整数多商品网络流问题，还提出了一种高效的算法以求解提出的大规模现实问题模型，测试结果表明所提模型和求解算法的有效性。2019 年，Shui 和Chan[13]以最小化所有出行者的出行时间为目标函数，考虑投资预算约束和覆盖所有出行点的约束，建立了一个优化数学模型，并结合遗传算法和两阶段求解方法对问题进行求解。Zuo和Wei[14]考虑自行车的连通性和对其他出行的影响，以最小化系统总阻抗为目标，采用多准则决策分析方法对路网进行决策，算例分析表明该方法能提高出行者选择自行车出行的比率。Liu等[15]建立了一个基于随机用户均衡的自行车网络设计双层规划模型，以最大化系统总效益为目标，考虑投资预算约束建立了数学模型，并通过对数学模型的线性化处理，提出了一个基于混合整数线性规划的全局优化算法，以及一个基于代理模型的全局优化数学启发式算法对问题进行有效求解。2020 年，He 等人[16]基于GPS 提供的共享单车骑行轨迹数据，考虑投资预算、道路长度、效益最大化这三个约束条件，以自行车道的覆盖范围最大化为目标函数建立数学优化模型，旨在为政府提供自行车道的规划方案，并采用贪婪启发式算法对问题进行求解，算例分析结果表明了算法和模型的有效性。Zhu 等人[17]基于时空可达性约束，考虑可达性、建设成本、出行者出行成本预算、交叉点个数等因素，建立了多目标优化数学模型，并遵循两阶段原则设计一个启发式算法对问题进行求解。2021 年，Oliveira 等人[18]综合考虑车道舒适度、安全性、路径客观性、网络连接性、投资预算，利用网络多目标优化和混合整数线性规划的概念，建立自行车专用道网络设计的数学模型，并实现最优策略的求解，结果分析表明自行车专用道的建立可以有效促进自行车替代部分机动车出行。

以上定量研究皆是通过建立最优化数学模型来描述自行车专用道网络设计问题，优化目标包括最小化系统总成本、出行阻抗、投资预算、连通性、多目标优化等，并针对不同的建模方式和问题背景设计不同的求解算法。但是以上众多研究中，还没有学者针对老城区的道路现状，考虑出行者的选择行为提出自行车专用道的设计方法。一般来说，基于双层规划的方法建立数学模型可以在下层模型中考虑出行者的出行选择行为，因此可以更加准确地描述交通系统中出行者与决策部门之间的相互关系。许多学者研究了基于双层规划的交通网络设计问题[19-20]，并在最优定价、公交排班、多目标优化等[21-22]领域取得广泛的应用。

本文在当前的自行车网络设计研究基础上，结合国内城市老城区中短距离出行需求多、道路密、机非混合等特点，考虑到自行车的出行特性可很好地契合老城区的交通环境，有效缓解老城区的交通拥堵的特点，提出一个新的自行车网络设计问题。即采用新建自行车专用道和禁行机动车的方式构建连通的自行车交通网络，目标是提供更为便利的自行车基础设施，以达到促进自行车出行和缓解交通拥堵的目的。建立了双层规划模型描述该问题，上层模型为连通性约束下的决策模型，目标函数为最小化系统总建设成本，下层模型为描述出行者弹性需求的Logit 模型和自行车、机动车的UE 交通分配模型。提出了改进的遗传算法对该双层规划模型进行求解，并在遗传算法中嵌入了自适应平均算法（SRAM）[23]和Frank-Wolfe[24]算法，分别求解Logit 模型和UE 交通分配模型。算例部分对所提出模型和算法的可行性和有效性进行了分析说明。

与已有研究相比，本文的研究贡献如下：

（1）采用新建自行车专用道和利用现有的道路禁行机动车的方式构建自行车网络，并增加自行车网络连通性的约束，可以最大程度地保证自行车出行的便利性和安全性。

（2）所提出的模型中考虑了需求弹性和路径选择，比采用固定需求可以更好地缓解交通拥堵问题。

（3）提出一个改进的遗传算法求解双层规划模型，并嵌入Frank-Wolfe 算法和SRAM 算法有效地求解下层问题。

1 数学建模

政府主导自行车基础设施网络的规划，根据OD 需求和交通网络现状，决策在现有道路网络上如何构建连通的自行车专用道网络，降低系统的交通出行总费用。自行车专用道改造方案主要有两种：一是在道路空间足够的路段上，花费资金建设新的道路作为自行车专用道；二是在道路空间狭小，且平行路段较多的路段上，对机动车道路采取机动车禁行措施。改造目标旨在最小化系统总成本情况下，构建一个连通的自行车专用道网络。即从所有OD 对的起讫点集合中任一点出发均可通过自行车专用道到达起讫点中另一任意点。出行者会随着道路网上的自行车专用道修建情况和OD 对之间阻抗的变化而改变出行模式和路径选择，即考虑选择使用机动车或者自行车出行，并决策所使用的路径。由此可见，政府的决策方案将影响出行者的出行模式和路径选择，而出行者的出行行为也会反过来影响政府决策。因此，本文所提出的问题可以构建为一个双层规划模型，其框架结构如图1所示。

图1 双层规划模型框架图Fig.1 Framework of the bi-lever programming model

为了便于建模和理解做出如下假设：（1）OD对之间总出行需求已知且恒定，自行车与机动车出行需求之间存在弹性；（2）道路类型改变后，OD间的总出行需求不变；（3）自行车与机动车分别只能在自行车专用道与机动车道上行驶；（4）不考虑其他类型车辆对自行车和机动车的影响。

本文符号定义如表1所示。

表1 参数及变量含义Tab.1 Definition of parameters and variables

续表1

1.1 上层自行车专用道规划模型

上层自行车专用道规划模型站在政府管理者的角度，以系统总费用最小为目标函数，以自行车网络连通性为主要约束条件，其数学模型如下：

模型中目标函数（1）旨在最小化系统总费用，其中第一项是自行车专用道的建设费用，第二项是机动车和自行车的出行总阻抗，σ是出行者的时间价值系数。约束（2）表示路段a上新建自行车专用道和禁行机动车策略只能采用其一。约束（3）和（4）均表示从所有的OD 对起讫点集合中任选两个点r和e，在r、e之间均存在连通的自行车专用道相连。最终的决策方案中，所有起讫点的任意两点之间都可以通过自行车专用道相连，这符合连通网络的定义。约束（4）表示连接r、e之间的自行车可行路径上的路段均为自行车专用道，即zrea=1 的前提条件是xa=1 或者ya=1。换句话说，该路段如果是自行车专用道，那么表示新建了自行车专用道，或者采取了机动车禁行措施。约束（5）表示xa、ya、zrea均是0-1变量。

1.2 下层需求方式划分和交通分配模型

考虑到老城区短距离出行需求多，道路空间狭小，公共交通覆盖率不高等情况，故在本文研究中简单地将所有的机动车都视作小汽车处理，模型下层只考虑自行车和小汽车的出行模式。给定一个可行的自行车专用道网络设计方案，在OD 总需求已知的情况下，下层模型可以预测出行者对自行车和小汽车出行模式的选择，进而预测小汽车网络和自行车网络各自的流量分配。假设用户对小汽车出行和自行车出行方式的选择服从Logit 模型，而用户的出行路径选择服从UE 均衡准则，则下层的用户出行行为模型如下所示。

（1）需求划分模型：

约束（6）表示选择机动车和自行车的出行者总和等于OD 对之间总需求；约束（7）用Logit 模型描述出行者选择自行车出行的概率；约束（8）表示OD 对w之间的自行车出行需求。

（2）自行车的UE交通分配模型：

约束（10）表示OD 对之间总需求与各路径流量的守恒关系；约束（11）表示自行车路段流量和路径流量的关系；约束（12）限制了各自行车路径流量都为非负。

在UE 交通分配问题中，我们采用了基于美国联邦公路局（Bureau of public road，BPR）开发的阻抗函数，即BPR[25]函数来描述路段阻抗，其中α和β为模型参数，分别取值0.15 和4。根据已有涉及自行车阻抗的研究，本文为了使自行车的阻抗更加符合实际情况，在BPR 函数中加入了自行车阻抗系数φ（0<φ<1），并且在3.4 小节中对该系数的影响做了分析说明。约束（13）表示自行车阻抗计算公式，xa=1 或者ya=1 表示路段a上有自行车专用道自行车可以通行，否则表示路段上无自行车专用道，自行车无法通行，通行时间为无穷大。

（3）机动车的UE交通分配模型：

机动车的UE 交通分配模型（14）～（18）与自行车出行类似。在约束（18）中，ya=1 表示路段a被禁行，则该路段上机动车的走行时间为无穷大；ya=0 表示未禁行，则采用标准的BPR 函数计算机动车的路段走行时间。

2 求解算法

由于双层规划模型是一个NP-hard 问题[26]，许多学者从求解算法方面对该类模型进行了大量研究[27-33]。本文所提出模型带有连通性的约束条件，并且下层问题包含模式划分和交通分配模型，因此为了有效求解该模型，采用基于遗传算法（Genetic Algorithm, GA）[34]的求解算法框架，并提出检查和更新网络连通性的策略，对下层的Logit模型和UE 交通分配分别采用自适应平均算法（SRAM）及Frank-Wolfe算法进行有效求解。

本文所提出的基于GA 的算法框架如图2 所示，其中嵌入的SRAM 算法和Frank-Wolfe 算法具体流程分别在后面2.2 和2.3 中进行叙述。

图2 算法框架Fig.2 Algorithm framework

遗传算法求解网络设计：

输入：种群规模m、交叉概率pc、变异概率pm、最大迭代次数kmax生成m个初始解（染色体）构成初始种群Φˉ0，初始化迭代次数k = 0用SRAM算法分别对种群Φˉ0中所有个体求解，得到每个个体的目标函数值，可根据目标函数值计算适应度，并置ubest为Φˉ0中的最优解。根据轮盘赌原则按照适应度大小从Φˉ0中挑选出m个个体得到新的一组解Φ0 While k

2.1 遗传算法

遗传算法是通过模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程搜索最优解。从一个初代种群开始，按照适者生存和优胜劣汰的原理，根据个体的适应度选择个体进行组合交叉和变异，逐代演化产生出越来越好的解。遗传算法中的种群由多个个体，即染色体组成，每个染色体由一组基因构成。在本文中，每个染色体代表模型的一个解，即自行车的网络设计方案。染色体上的基因表示解中每个路段是否有专用道，是新建专用道还是禁行小汽车，本文中基因的取值有0、1、2三种情况，0表示小汽车禁行（相当于ya= 1），1表示新建自行车专用道（相当于xa= 1），2 表示仍是小汽车道（相当于xa+ya=0）。例如，图3给出了一个有15个基因的染色体，该染色体共有6 条路段为新建专用道，4 条路段为小汽车禁行，5条路段仍是小汽车专用道。

图3 染色体示例Fig.3 Chromosome example

2.1.1 解的初始化

在遗传算法开始时，首先要产生一组种群大小为K的初始解，即K个连通的自行车专用道设计方案，其中，每个可行解均由以下两个步骤产生。

首先，产生连通的自行车基础网络。为了便于描述，将给定的m个OD 对标上序号，即第一对OD对为O1D1，第二对为O2D2，…，第m对为OmDm。从第一个起点O1中找到一条连到终点D1的路径，该路径为当前小汽车最短路或者次短路，当O1D1间有大于2条以上路径时，则随机采用最短路或者次短路。然后再从已连接专用道的节点中选一个点J，使J离下一个起点O2最近，找到J到起点O2的最短路径，再从起点O2按照同样的方法找一条连到终点D2的路径，接下来再去连接第三个起点O3，从O3连到D3后，再去连第4个起点O4……这样循环直到把所有的OD对都覆盖到。这样即得到了一个所有点都是连通的且OD对之间也是连通的一个解。

其次，在当前连通的路网上，设置自行车专用道和禁行路段。设置初始概率P0，针对上一步产生的路网当中的每一个路段a随机产生一个概率pa，若pa>P0,则该路段采用禁行措施，否则新建自行车专用道。

执行以上两个步骤可以得到一组可行解。再从所有OD 对的起点中选O2O2作为起点，分别找到O2D2的路径再连到O3，找到O3D3的路径连到O4…找到OmDm的路径，连到O1，这可以得到另一组可行解。重复执行同样的操作，直到得到K个初始可行解。

图4 演示了有3个OD 对需求的初始解生成过程，图中所有路段皆可通行。给三个OD 对随机排序：O1D1为1→9（蓝色）、O2D2为2→8（绿色）、O3D3为3→7（红色），如图4（a）所示。首先，要找O1到D1的连通路径，采用最短路和次短路的方法可以找到O1到D1间有两条路径，假设随机选用了次短路，该路径为1→4→5→8→9，如图4（b）所示。其次，找到1、4、5、8、9 节点中距第二个OD 对的起点2 最近的点，假设这个点是5，则连接5→2 之间的最短路径，如图4（c）所示；再按照最短路和次短路的方法找到OD 对2→8 之间的路径，假设随机选取了2→8 间的最短路，该路径为2→5→8，如图4（d）所示。此时已连接专用道的节点有1、2、4、5、8、9，再从这些节点中找到离第三个OD对的起点3最近的点，假设找到的这个点为2，则连接2→3 之间的最短路径，如图4（e）所示；再按照最短路和次短路的方法找到OD 对3→7 之间的路径，假设随机选取了3→7 间的最短路，该路径为3→2→5→8→7，如图4（f）所示。注，图中某些节点之间有多条不同颜色的路径，如图4（f）中的2→5节点间，有三种不同的颜色，这表示该路段上只有一条自行车专用道，这条自行车专用道被多个OD 对同时使用，而不是在这个路段上修建了多条自行车专用道。

完成以上步骤后可得到一个满足连通性条件的自行车道网络，再对连通网络上的每一个路段a按照随机概率的方式，即可确定每个路段是采用新建自行车专用道还是禁行机动车道，至此可以得到一个完整可行的自行车专用道网络作为第一个初始解。按照同样的方式，从第二个OD 对的起点开始执行操作，可以得到第二个初始解，重复以上操作，直到得到K个初始解。

2.1.2 选择操作

在遗传算法的迭代过程中，每计算完一组解的目标函数值后，需要通过选择操作，从当前这组解中选出一组新的解。本文采用轮盘赌的方法，以每个解的目标函数的倒数作为适应度，这样目标函数值较小的解被选中的概率更大，可以保证更优的解被选中加入到下一代种群中。以Sr表示每个解被选中的概率，Or表示每个解的目标函数值，m表示种群的规模，即解的数量，则Sr可表示如下：

2.1.3 交叉操作

为了保证解的收敛速度更快以及不陷入局部最优解，在选择操作结束后，需要对得到的染色体分别进行交叉操作。针对本文所提出的模型设计了一个最短路交叉算子：在两个父代染色体φ1、φ2中任选一个相同的OD 对，分别找到两个染色体中该OD对之间的自行车最短路径pwφ1、pwφ2，然后交换两个最短路径中的路段所对应的解的片段，这样即得到两个新的染色体；在K个解的交叉操作中，分别选取第1个解与第2个解交叉，第3个解与第4个解交叉……第K个解与第1个解交叉。

图5和图6以一个9节点网络为例说明了最短路交叉算子的具体执行过程。该9 节点网络包含两个OD 对，分别是1→9 和3→7，其中蓝线和红线表示连通各OD 对的自行车专用道路径（包括新建专用道和机动车禁行道路），其余黑线表示机动车道。图5 中（a）、（b）两图分别表示两个不同的解，左边表示父代染色体为1 时,右边表示父代染色体为2 时。在父代染色体1 中，OD 对1→9 之间的路径为1→2→5→8→9，OD 对3→7 之间的路径为3→2→5→4→7；在父代染色体2 中，OD 对1→9 之间的路径为1→4→5→8→9，OD 对3→7 之间的路径为3→6→9→8→7。选取OD 对1→9 为例，交换其自行车最短路径所包含的路段对应的解的片段，即将父代染色体1 中蓝线与父代染色体2 中蓝线交换可得图6所示的子代染色体。注意，图6（a）在交叉算子执行后产生了不连通的自行车专用道网络。

图5 父代染色体图Fig.5 Parent chromosomes

图6 子代染色体图Fig.6 Children chromosomes

2.1.4 检查和修正操作

为了保证解的可行性，在交叉算子执行后，必须检查每个染色体的自行车网络连通性，以保证解的可行性。因此，设计了相应的连通性检查和修正算子如下：按照OD 对顺序，检查每一个OD 对的起点是否能连通到网络上OD 对起讫点中的任意点，若所有起点均能连通到其他点，则该网络满足连通性约束；否则找到这个不连通的点，并找到与不连通点相连的自行车专用道中离起点最近的节点，将该节点与起点用自行车专用道连接起来，专用道随机采用禁行或者新建的策略，再从每一个OD 对的起点开始检查，直到网络连通。

以图6 为例检查网络连通性。首先以子代染色体2 为例，从第一个OD 对的起点1 开始检查，1可以连接到点3、7、9；再以第二个OD 对的起点3开始检查，3 可以连接到1、7、9。检查完所有OD对的起点，每个起点均连通，因此该自行车网络满足连通性要求。

再以子代染色体1 为例，从第一个OD 对起点1 开始检查，1 连接不到3，因此找到与3 相连的某一点D′，与起点1 相连的某一点O′，使O′→D′距离最短。以图6 为例假设D′为2，O′为5，则将2→5用自行车专用道连接起来，连通性修正后如图7所示，此时1—3 之间则满足连通性的要求。为了保证其他点也完全相连，每检查并更新一次连通性后，需要再次按照OD 对顺序的起点开始检查。因此再次从第一个OD 对起点1 开始检查，1 可以连接到3、7、9；再检查第二个OD 对起点3，3 可以连接到1、7、9。此时检查完毕，整个自行车专用道设计满足连通性要求，则父代两条染色体经过交叉后得到满足连通性条件的子代染色体1和2。

图7 连通的子代染色体Fig.7 Connected children chromosome

2.1.5 变异操作

变异操作可以产生新的基因，扩大解的搜索范围，有助于避免陷入局部最优解。考虑到交叉操作后得到的部分解中会存在冗余的自行车专用道，因此本文提出了两种变异算子。变异算子（1）：在当前染色体中，随机找一个OD 对，检查该OD 对之间是否存在2 条以上的自行车专用道路径，若有则更改次短路上的所有路段为机动车道，具体更改方式如图8的描述所示，次短路由K短路的方法产生，然后检查和更新自行车专用道网络的连通性，方法与2.1.4 所述相同；若无则在该OD对之间执行变异算子（2）。变异算子（2）：设定一个初始概率P0，在当前染色体中随机选择一个OD对之间的最短自行车专用道路径。在当前路径的每条路段上，对每一条路段a产生一个0-1 之间的随机数pa，若pa>P0,则当前路段发生变异。变异规则为：若当前路段为新建自行车道，则改为禁行；若当前路段为禁行，则改为新建自行车道。该算子的设计方式不仅可以保证解的可行性，还可以更大程度地减少一些不必要的自行车道，从而可以减少建设成本和提高机动车的通行效率。

图8展示了变异算子（1）的执行过程。该道路网络上有3 个OD 对，分别是1→9、3→4、3→7。假设当前变异找到的OD对为1→9，变异前如图8（a）所示。可知1→9有两条路径分别是最短路1→2→5→8→9 和次短路1→2→5→6→9。因此，将1→2→5→6→9 从自行车网络上删去，因为1→2→5 也包含于路径1→2→5→8→9中，因此仅删除5→6→9 即可，然后得到图8（b）。再采用2.1.4 中检查和更新网络连通性的方法，可得到变异后最终的结果，如图8（c）所示。

图8 变异前、变异中、变异后的道路网络Fig.8 Road networks before,during and after mutation

2.2 自适应平均算法

自适应平均算法（SRAM）是经Liu等[23]改进相继平均算法得到的求解随机用户均衡分配的有效算法。该算法对相继平均算法中的迭代步长做出了改进，相比于给定的迭代步长，自适应平均算法中的迭代步长与当前解决方案和可行解决方案的距离有关。避免了相继平均算法在迭代初期由于步长过大导致的目标函数值到一定的迭代次数后才下降的缺陷，修正了相继平均算法在经过多次迭代后，迭代步长非常小而使得收敛速度变慢的问题。

为了得到自行车和机动车之间出行模式划分的比例，本文采用自适应平均算法对Logit 模型进行求解。自适应平均算法主要包含两个重要步骤：一是确定搜索下降方向与迭代步长；二是更新路段流量方案。算法计算步骤如下所示：

自行车和机动车需求分配的SRAM算法：

输入：参数δ、γ、ε令Γ =[T w b , ∀w ∈w]，初始化一个分配的起始概率Γ0（本文中初始化Γ0=0.3），设置迭代次数n=1，根据Frank-Wolfe计算得到Γ1，令下降方向G0=Γ1, β0=1 While‖ ‖Gn - 1 >ε do根据Γn计算机动车和自行车的需求d nb 、d n v，然后再用Frank-Wolfe算法计算自行车与机动车各自的UE交通分配，得临时概率Γ'n，既有下降方向Gn=Γ'n -Γn If‖ ‖Gn ≥‖ ‖Gn-1 then βn=βn-1+δ Else βn=βn-1+γ End if确定步长μn=1/βn更新Γn+1=Γn+μnGn置n=n+1 End while输出：路段阻抗和Γn

2.3 Frank-Wolfe算法

本文将Frank-Wolfe算法嵌入自适应平均算法中分别计算自行车与小汽车各自的UE 交通分配。Frank-Wolfe 算法是Frank 和Wolfe（1956）[24]提出的求解线性约束下的非线性规划问题的一种算法。

Frank-Wolfe 算法应用在UE 交通分配时计算流程如下：

输入：精度ε>0基于所有路段的自由流走行时间，做全有全无交通分配，得到初始的路段流量s0，置迭代次数k = 0 while G(sk) >ε do以sk为输入，做全有全无交通分配，得到路段流量s'k置可行下降方向dk = s'k - sk进行一维搜索得到最优步长λk更新路段流量sk + 1 = sk + λkdk置k = k + 1 end while输出：sk

该算法在初始化过程中用最短路做全有全无交通分配的时候，自行车和小汽车路段的阻抗均采用阻抗函数中的自由流时间计算。在UE 交通分配问题的求解过程中，采用式（20）所示的间隙函数（Gap Function）来评价解的精度：

3 算例分析

采用算例分析对提出算法和模型的准确性及有效性进行分析，以Sioux Falls 网络为例进行测试。假设网络上所有的路段都既可以禁行也可以新建机动车专用道，网络包含了24 个节点和76 条路径、20个OD对，见图9所示。

图9 Sioux Falls网络Fig.9 Sioux Falls road network

OD 对之间的需求如表2 所示，每条路段上机动车的自由流走行时间、路段建设费用如表3 所示。本文提出的所有算法均采用C#编程。在遗传算法中，设置种群规模大小为70，交叉概率为0.7，变异概率为0.3，选择第一种和第二种变异的概率都分别为0.5，在变异过程中，新建自行车道变为禁行道和禁行道变为新建自行车道的概率都分别为0.5，自行车专用道的通行能力Qb为1600，机动车道的通行能力Qv为1850，最大迭代次数通过实验可设置为3 000 次，自行车的阻抗系数为0.3，时间价值系数为0.3，θ值为1。在SRAM 算法中，设置初始的自行车出行概率为0.3，参数δ= 1.5,γ= 0.01,ε= 0.2。

表2 各OD对之间的出行需求Tab.2 Travel demandsof different OD pairs

表3 Sioux Falls网络中各路段信息Tab.3 Road segments information in the sioux falls network

3.1 模型结果

Sioux Falls 网络求解的结果如图10 所示，红色的为禁行路段，蓝色的为新建自行车专用道路段，包括8 条禁行道路和48 条新建自行车道。从图10 中可以看出，自行车专用道网络覆盖到了OD 对所有的起讫点。

图10 连通的自行车专用道网络Fig.10 Connected bike network

图11 展示了目标函数的收敛过程。遗传算法在前1 200 次的迭代过程中，结果收敛较快，之后保持不变，最终收敛在313 765.60 百元处，整个收敛过程耗时约10 min。

图11 目标函数收敛图Fig.11 Objective function convergence

3.2 模型对比

表4对比了自行车网络规划前、后路网拥挤程度和总阻抗的变化。第二列展示了自行车网络规划前的结果，第三列展示了考虑固定需求的模型规划自行车网络的结果，即各OD 对之间的出行需求是固定的，第四列展示了本文所提出模型的结果。

表4 路网拥挤程度和机动车总阻抗对比Tab.4 Road network congestion and total vehicle impedance

本文采用的对整个网络路段的机动车平均拥挤程度的评价指标公式表示为：

式中：fa表示路段a上的机动车流量；ca表示路段a上机动车的通行能力；A表示路网上机动车道的总数量。自行车平均拥挤程度评价指标同理。

由结果可知在路网上建设自行车专用道后可以有效减少系统的总阻抗并降低机动车道的平均拥挤程度。本文所提出的需求划分模型，可以更为准确地预测模式需求，并在此基础之上进一步降低系统总阻抗。

3.3 自行车专用道建设成本的影响分析

下面分析自行车专用道建设成本变化时，自行车专用道网络的设计情况。在自行车专用道原建设成本的基础上，分别以原成本的2 倍、3 倍、4倍、5 倍作为建设成本，规划结果如图12 所示。结果显示，随着建设成本的增加，禁行的机动车道的数量缓慢增加，而新建自行车专用道数量则逐渐减少直至不变。这说明当路段的建设成本较小时，倾向于选择新建专用道，而当路段的建设成本较大时，则倾向于选择禁行机动车的方案。表5展示了不同建设成本下的最优自行车路网规划方案的影响。结果显示，无论是机动车路网的平均拥挤程度，还是机动车和自行车的阻抗均有所增加，这说明自行车专用道的建设费用会对路网以及出行阻抗产生较大影响。

表5 不同建设成本下道路拥挤情况和出行阻抗Tab.5 Road congestion and travel impedance under different construction costs

图12 不同建设成本下的不同建设规划Fig.12 Construction plans under different construction costs

3.4 自行车阻抗系数的影响分析

在其他参数相同的情况下，分别选取自行车阻抗系数φ为0.1、0.3、0.5、0.7、0.9进行自行车专用道网络规划，结果如图13所示。

图13 总阻抗随阻抗系数的变化Fig.13 Variation in the total impedance with impedance coefficient

观察发现，随着系数的增高，自行车和机动车的总阻抗也随之增加。这是因为在自行车阻抗系数和需求划分的Logit 模型共同作用下，由于系数的增加，自行车的阻抗随之增加，Logit模型中选择自行车出行的概率会减小，而选择机动车出行的概率会增大，导致机动车的阻抗也随之增加。由此说明，自行车阻抗权重系数会影响需求划分，进而影响最终的规划结果，因而在实际规划中，需要考虑自行车的阻抗影响。

3.5 交叉和变异概率对目标函数的影响

在遗传算法中，交叉和变异概率过高或者过低都会影响解的收敛。变异概率太小难以产生新的基因，而变异概率太大则会使算法成为随机搜索。染色体的交叉可以产生新的个体，交叉概率较小时，产生新个体的速度较慢，从而收敛较慢；而当交叉概率较大时，会使高适应度的个体很快被破坏，从而导致收敛效果变差。在迭代次数都设为3 000 次，为了保证测试的准确性，同时改变交叉和变异概率的情况下，测试了不同的交叉和变异概率对收敛速度的影响。由图14 可知，在不同的交叉和变异概率下，最小目标函数值存在差异。其中，在变异概率为0.1 而交叉概率为0.3 时，目标函数值最小（值为304 351.31）。因此在本研究中，交叉、变异概率分别取0.3、0.1较为合适。

图14 目标函数值随交叉和变异概率的变化Fig.14 Variation in objective function value with crossover and mutation probabilities

4 总结

本文提出了一个基于双层规划模型的老城区自行车专用道网络设计问题，上层决策专用道的规划，下层分别用Logit 模型和UE 交通分配描述了出行方式选择行为和路径选择行为，并提出嵌入了SRAM 和Frank-Wolfe 的GA 算法对模型准确求解。通过算例分析得到了以下结论：（1）本文所提模型和算法可以有效求解自行车专用道网络设计。（2）与没有需求划分的模型对比可知，本文提出的模型可以有效地降低路网上的总阻抗，从而缓解交通拥堵。（3）自行车路段的建设成本、自行车出行阻抗系数均会影响最终的自行车网络规划方案。（4）交叉和变异概率会影响解的精度，分析表明本文交叉概率取值0.3，变异概率取值0.1较为合适。然而本研究中只考虑了自行车和机动车的出行方式，为了更加符合实际需求，后续可以从多种交通方式组合出行、下层问题基于SUE 交通分配求解等方面展开更多的研究。