随着城市人口增长，城市交通拥堵问题日益严重，构建合理的公共交通系统，倡导公交出行成为缓解这一问题的有效手段。合理的公交线网设计是构建有效公交系统的关键部分，如何根据公交出行需求设计相应的公交线网成为了交通研究热点。

早在1967年，Lampkin等^[1]就对公交线路设计进行了相关研究，他们将问题分为公交线网设计和发车频率设计两个部分，首先设计公交线网然后设计发车频率，其优化目标是在不降低公交服务水平的基础上减少车辆配备。Newell^[2]和Salzborn^[3]基于乘客的角度，在给定的公交资源条件下通过优化发车频率使乘客出行时间最小化。早期的研究都是基于单条线路或小规模路网的路网设计，模型较为简单，且缺乏模型算法研究，很难运用到实际的公交线网设计中。相比于国外，国内对于公交线网研究起步较晚，最早王炜^[4]提出了实用的“逐条布设，优化成网的公交线网规划方法”。张杰林等^[5]提出了城市常规公交线网的“一路一线”布局构想。

文献[6-15]从线网层面，探究了公交线网设计的问题。这些研究集中在运用智能算法解决公交线网设计的问题上，如文献[6-7]构建了公交线网优化模型，并讨论了公交线网设计问题本身的复杂性：当公交线网从线路层面上升至网络层面之后，由于线路之间的相关特性，传统的解析式算法很难应用于该问题的求解，特别是网络规划过大时，传统的算法无法得到有效解。针对网络层面的求解问题，文献[8-15]均提出了相应的智能算法，利用其迭代优化的特性，实现了公交线网模型的求解。总的来说，这些研究对公交线网及发车频率都采用分阶段优化方法，没有考虑两者之间的相关关系，以及公交线网及发车频率的同步优化。

公交线网求解算法研究可以分为两个阶段，早期由于线网设计多是基于单线路或小规模路网，考虑因素较少，模型较为简单，主要采用传统的最优方法求解^[1-3]。随着研究的问题规模扩大，模型越来越复杂，传统的最优化方法计算量过大，有时甚至无法求解，采用智能算法求解模型成为了主流趋势^[10-12]。但这些研究没有考虑线网与发车频率之间的关系，特别是对于如何利用两者关系，改进算法，提高算法效率还缺乏相关研究。

通过上述对公交线网相关研究的回顾，可以发现，现有的研究主要基于乘客和运营商的角度考虑公交线网的设计问题，主要分阶段对公交线网及发车频率进行优化，没有深入考虑公交线网及发车频率之间的相关关系。从现有的研究来看，依据乘客视角进行公交线网规划的主要目标是使乘客出行时间最小化，包括乘客从出发地到达起始站点的时间、等待时间、换乘时间、在车旅行时间和从目的站点到达终点的时间。依据公交运营商的角度进行公交线网规划的主要目标是使运营成本降到最低，运营成本涉及多个方面，包括车辆配置成本、人员配置成本、管理调度成本、燃油消耗成本等。由于两者追求的目标相互矛盾，从管理层面主要是协调两者之间的矛盾。因此，基于乘客视角所构建的模型主要是以给定的公交资源配置条件下，如何使乘客出行时间最小化；基于运营层面的视角所构建的模型主要是在给定的服务水平条件下，如何使总运营成本最小化；基于管理层面视角所构建的模型通常是双目标同时优化。

依据本文主要针对的是已经确定站点布局以及给定的车辆配备条件下的公交线网布设优化问题，涉及到的主要是乘客等待时间、在车旅途时间，以及车辆配备，构建以乘客等待时间和在车旅途时间最小化为目标，以车辆配置数量为约束条件的混合整数规划的公交线网优化模型，实现公交线网及发车频率的同步优化，同时，深入分析公交线网及发车频率的相关关系，对算法进行改进，提高算法的执行效率。

1 模型构建

公交线网及线网发车频率同步优化问题是公交线网优化和发车频率优化问题的组合问题，目的是为了获取规划区域最佳线网布局及与线网中每条线路相匹配的线路发车频率。根据相关研究，模型假设及模型建立如下。

1.1 模型假设

1) 乘客采用公交出行时选择换乘最少，出行时间最短的公交线路；

2) 乘客选择第一辆能够满足其出行需求的公交车辆；

3) 乘客的公交出行OD(起终点间的交通出行量)已知；

4) 规划区域的站点布局，及规划线路数量、车辆配置总量已知；

5) 假设乘客客流随机到达，乘客的平均等待时间为发车间隔的0.5倍；

6) 假设站点间的运行时间已知且为固定值。

1.2 公交线网及发车频率同步优化模型构建

依据公交线网优化相关研究分析，构建在给定的公交资源的条件下，以出行时间最小化为目标的公交优化模型，模型及相关说明如下。

$\quad\quad\begin{split}{\min } \ {Z = \displaystyle\sum\limits_{o \in {D_o}} {\sum\limits_{d \in {D_d}} {{D_{od}}({T_{od}} + {W_{od}})} } }\text{。}\end{split}$

(1)

${T_{od}}{\rm{ = }}\frac{{\sum\limits_{l \in {L_s}} {{\rm{RT}}_{od}^l} {f_l}T_{od}^l + 1}}{{{\rm{N}}{{\rm{R}}_{od}} + \sum\limits_{l \in {L_s}} {{\rm{RT}}_{od}^l{f_l}} }}(1 - {\rm{N}}{{\rm{R}}_{od}}) + \left( {\frac{{\sum\limits_{l \in {L_s}} {{\rm{RT}}_{ok}^l} {f_l}T_{ok}^l + 1}}{{\sum\limits_{l \in {L_s}} {{\rm{RT}}_{ok}^l{f_l}} }} + } \right.{\rm{ }}\left. {\frac{{\sum\limits_{l \in {L_s}} {{\rm{RT}}_{kd}^l} {f_l}T_{kd}^l + 1}}{{\sum\limits_{l \in {L_s}} {{\rm{RT}}_{kd}^l{f_l}} }}} \right){\rm{N}}{{\rm{R}}_{od}}$

(2)

$\begin{split}\quad\quad{T_{ik}^l = {c_{ik}}{x_{ikl}} + \sum\limits_{j \in {L_o} \cup {L_m},j \ne i \cap j \ne k} {{x_{ijl}}{\rm{RT}}_{jk}^l} (T_{jk}^l + {c_{ij}} + s)}, \\ i \in {L_o} \cup {L_m},k \in {L_d} \cup {L_m},k \ne i,l = 1, \cdots, L\text{。}\end{split}$

(3)

$\begin{split}\quad\quad{{\rm{RT}}_{ik}^l }= & {{x_{ikl}} + \sum\limits_{j \in {L_o} \cup {L_m},j \ne i,j \ne k} {{x_{ijl}}} {\rm{RT}}_{jk}^l}, \\ & {i \in }{L_o} \cup {L_m},k \in {L_m},k \ne i,l = 1, \cdots, L\text{。}\end{split}$

(4)

$\begin{split}\quad\quad{{{\rm{NR}}_{od}} = \displaystyle\prod\limits_{l = 1}^L {(1 - {\rm{RT}}_{od}^l} )}, {o \in} {L_o}, \end{split}d \in {L_d}\text{。}$

(5)

$\quad\quad\begin{split}& {\rm{s.t}}\\& {\sum\limits_{n \in {L_o}} {{x_{nml}}} = 1}, {l = 1, \cdot \cdot \cdot ,}L\end{split}\text{；}$

(6)

$\quad\quad\begin{split}{\displaystyle\sum\limits_{n \in {L_d}} {{x_{nml}}} = 1}, {l = 1}\end{split}, \cdot \cdot \cdot ,L\text{；}$

(7)

$\begin{split}\quad\quad{\displaystyle\sum\limits_{n \in {L_o} \cup {L_m}} {{x_{nml}} {\text{≤}} 1} }, {l = 1}\end{split}, \cdots, L\text{；}$

(8)

$\begin{split}\quad\quad{\displaystyle\sum\limits_{m \in {L_d} \cup {L_m}} {{x_{nml}} {\text{≤}} 1} }, {l = 1}\end{split}, \cdot \cdot \cdot ,L\text{；}$

(9)

$\quad\quad{{x_{nml}} {\text{≤}} {S_{\max }}}, {n \in {L_o}} \cup {L_m},m \in {L_m} \cup {L_d}\text{；}$

(10)

$\quad\quad\sum\limits_{l = 1}^L {2{f_l}{T_l}} {\text{≤}} B\text{；}$

(11)

$\quad\quad\begin{split}{{f_{\min }} {\text{≤}} {f_l}}, {l = 1, \cdot \cdot \cdot }\end{split},L\text{；}$

(12)

$\quad\quad\sum\limits_{n \in {L_o} \cup {L_m}} {\sum\limits_{m \in {L_d} \cup {L_m}} {{x_{nml}}} } {\text{≤}} {N_{\max }}\text{。}$

(13)

变量符号说明。

1) 集合。

D_o为公交出行需求起始站点集合；

D_d为公交出行需求终点站点集合；

D_od为从起始站点o到达终点站点d的公交出行客流量；

L_o为线路起始站点集合；

L_d为线路终点站点集合；

L_m为线路中间站点集合；

L_s为公交线网线路集合；

2) 上下标。

$o,d,k,i,j,m,n$ 分别为标号 $o,d,k,i,j,m,n$ 的站点；

l表示标号为l的公交线路。

3) 变量。

已知常量：

${c_{ik}}$ 为站点i和站点j的最短旅行时间；

s为车辆在站点的平均停靠时间；

L为线网总线路总条数；

B为线网总配备的车辆总数；

f_min为线路最小发车频率；

N_max为线路中站点数量最大值；

S_max为相邻站点的站点距离最大值；

中间变量：

T_od为站点o到站点d的平均在车旅行时间；

$T_{od}^l$ 为线路l中站点o到站点d的旅行时间；

W_od为站点o到站点d的平均等待时间；

${\rm{RT}}_{od}^l$ 为0, 1变量，线路l是否同时通过站点o和站点d，如果同时通过则取1，否则取0；

${{\rm{NR}}_{od}}$ 为0, 1变量，站点o和站点d是否存在某条线路同时通过，如果存在则取0，否则取1。

决策变量：

f_l为线路l的发车频率；

${x_{ikl}}$ 为0, 1变量，线路l是否连续通过站点i和站点j，如果连续通过则取1，否则取0。

目标函数：

Z为公交线网乘客总的出行时间，即模型的目标函数。

模型说明：式(1)为目标函数，为最小化所有乘客出行时间；式(2)为从站点o到站点d的平均出行时间，其中第1部分分项为从站点o到站点d直达的平均出行时间，第2部分分项为从站点o到站点d换乘的平均出行时间；式(3)为通过线路l从站点o到站点k的出行时间；式(4)是定义 ${\rm{RT}}_{ik}^l$ ，乘客是否可以通过线路l不经换乘从站点i到达站点j，如果可以则取1，如果不行则取0；式(5)是定义 ${{\rm{NR}}_{od}}$ ，乘客是否可以通过线网中任意一条线路不经换乘从站点i到达站点j，如果可以则取1，如果不行则取0；其中式(4)是判断乘客是否可以通过某一特定的单条线路l不经换乘完成出行目的，而式(5)是对所有的线路进行判断，从而得出乘客出行是否需要换乘，式(5)是式(4)的累加效应。式(6)表示每条线路的起点站只能为起点站集合中的任意一站点；式(7)表示每条线路的终点站只能为终点站集合中的任意一站点；式(8)和式(9)表示任意一站点在一条线路中最多允许出现一次；式(10)表示所有线路配备的车辆总数不能超线网最大车辆配备数；式(11)表示任意一条线路的发车频率必须大于预设的最小发车频率；式(12)表示任意一条线路的总站点数不能超过预设的单条线路最大数；式(13)表示任意一条线路的站间距离不能超过预设的站点最大距离。

2 公交线网及发车频率同步优化模型求解算法

根据对公交线网求解的算法研究，本文针对该问题设计相应的遗传算法。不同于以往的算法，本文根据该问题的特点对算法进行了改进，提出公交线网客流换乘比例检验方法，以此减少对不可行解的计算，提高算法的执行效率。

公交线网优化的目标函数是乘客出行时间最小化，出行时间分为在车旅行时间和等待时间。而在设计的算法中，适应度通常用来反映解的好坏，一般的优化问题都以目标函数适应度函数作为适应度函数，但在公交线网设计中，目标函数包含在车旅行时间以及等待时间，涉及到线网设计和发车频率设计两个阶段。如果以目标函数作为适应度函数就需要对所有公交线网进行发车频率的分配，但这种求解方式会增加一些本身不可行解的计算量。因此针对该问题，合理的适应度函数以及相应算法的改进，能够有效地增加求解速度，提高算法效率。

本文的改进策略是首先对线网结构计算客流换乘比例值，记为Lc，评价线网结构优劣。对于线网客流换乘高于换乘比例下界值 $\rm L{c_{\lim }}$ 的线网不进行发车频率设计，以此减少不可行线网的后续计算，加快计算速度。其中线网客流换乘比例计算如下：

$ \quad\quad {\rm{Lc}} = \frac{{\displaystyle\sum\limits_{o \in {D_o}} {\displaystyle\sum\limits_{d \in {D_d}} {{D_{od}}} } (1 - {{\rm{NR}}_{od}})}}{{\displaystyle\sum\limits_{o \in {D_o}} {\displaystyle\sum\limits_{d \in {D_d}} {{D_{od}}} } }}\text{。}$

(14)

Step1 数据输入：通过前期工作确定规划区域站点L_o，L_d，L_m，线路条数L，站点间最短出行时间 ${c_{ik}}$ ，线网客流换乘比例下界值 ${{\rm{Lc}}_{\lim }}$ 等相关数据，作为数据输入。

Step2 初始线网产生：依据约束条件(6)~(10)及Step1的数据输入，产生初始线网。

Step3 线网客流换乘比例判断：依据式(14)对公交线网客流换乘比例进行判断，将公交线网分为满足下界和不满足下界的公交线网。

Step4 分配及优化发车频率：

1)对于线网客流换乘比例Lc＜ ${{\rm{Lc}}_{\lim }}$ 的公交线网分配随机分配发车频率；

2)根据式(1)计算分配了发车频率的线网的目标函数；

3)对发车频率进行局部优化得到该线网的最佳发车频率方案，具体发车频率局部优化方案参照文献[8]。

Step5 判断算法是否停止：对算法的停止条件进行判断，如果满足算法停止条件则停止计算，并输出线网及相应发车频率的设计方案，如果没有满足算法停止条件则转至下一步。

Step6 依据选择规则和设定的交叉变异概率, 选择公交线网进行相关的交叉变异操作, 得到与原种群规模一致的新的公交线网。

Step7 对公交线网子代及其父代按目标函数值大小进行排序, 取目标函数值小的作为新的种群, 并转至Step3。

需要说明的是，本文所针对的问题是单条线路可以覆盖的中小城市的公交线网规划。在这种规模的网络中，换乘比例过高将导致网络结构不合理，因此在算法设计层面不适用于大规模网络及城乡通道性客流较多的公交线网规划。

3 算例分析

1)算例条件说明。

该方法将应用至一个如图1所示包含8个节点线网的站点及道路布局图，其中站点间的运行时间以及站点间客流OD如表1所示，该算例与文献[6]一致。在设计线网时，本算例根据文献[6]的相关研究，规划线路数量为6条，单条线路配备车辆数最少为12辆最多为40辆，每条线路最少站点数为3，最大站点数为4，整个线网车辆配备总数量不超过146辆。

需要说明的是，虽然引用案例选取的是包含8个站点、6条规划线路和146辆车辆的小规模网络进行验证，但涉及到了全部的公交线网规划因素，在对于中小型城市实际较大的网络中，应用该模型和算法也可以得到相应的优化结论。不过随着网络规模的扩大，将会导致算法计算时间的增加。

2)将算例的已知条件代入至本文构建的公交线网优化模型，并采用Matlab语言编写相关遗传算法程序实现对模型的求解。通过数据实验，对 $\rm L{c_{\lim }}$ 参数进行灵敏度分析，确定 $\rm L{c_{\lim }}$ 的最佳取值，在此基础上得到算例的最优结果如下。

(1) 对 $\rm L{c_{\lim }}$ 参数进行灵敏度分析。

对参数 $\rm L{c_{\lim }}$ 取不同的值，观察计算时间及最优结果与 $\rm L{c_{\lim }}$ 的关系，实验结果如图2。

通过灵敏度分析可知如下结果。

① 随着 ${{\rm{Lc}}_{\lim }}$ 值的减小，计算时间越来越短，当 ${{\rm{Lc}}_{\lim }}$ 取值为1~0.5时计算时间为34.58 min，当 ${{\rm{Lc}}_{\lim }}$ 取值为0.25时计算时间仅为9.43 min，表明 ${{\rm{Lc}}_{\lim }}$ 的取值对计算时间影响非常大，这也说明该算法设置 ${{\rm{Lc}}_{\lim }}$ 取值，提高算法运行效率的合理性。

② 随着 ${{\rm{Lc}}_{\lim }}$ 值减小的同时，最优目标函数整体越来越大， ${{\rm{Lc}}_{\lim }}$ 在提高算法的同时也会对最优结果产生影响，当 ${{\rm{Lc}}_{\lim }}$ 取值在1~0.4之间时，最优目标函数基本没有变化，在取值小于0.4之后，目标函数变化较大，说明在 ${{\rm{Lc}}_{\lim }}$ 提高算法要兼顾考虑算法效率与目标函数，合理对 ${{\rm{Lc}}_{\lim }}$ 取值可以保证算法求解速度的同时得到高质量的最终方案。

③ 在区间1~0.5时计算时间均为34.58 min说明，初始化线网的客流换乘比例Lc均小于0.5，换乘比例下界值 ${{\rm{Lc}}_{\lim }}$ 的设计实际上没有起到任何作用。只有当 ${{\rm{Lc}}_{\lim }}$ 的取值小于0.5时， ${{\rm{Lc}}_{\lim }}$ 的设计才能够提高算法执行效率。

④ 在灵敏度分析图中，换乘比例最小取值为0.25，这是因为当 ${{\rm{Lc}}_{\lim }}$ 的取值小于0.25时，所有初始化线网均不满足Lc＜ ${{\rm{Lc}}_{\lim }}$ ，算法自动停止，且没有可行解产生。

通过对 ${{\rm{Lc}}_{\lim }}$ 参数进行灵敏度分析可知， ${{\rm{Lc}}_{\lim }}$ 的取值会对算法执行效率以及最终优化结果产生影响，在实际问题中对于 ${{\rm{Lc}}_{\lim }}$ 需要兼顾这两个方面，因此其取值应该参考现有的公交服务水平下换乘比例，然后对 ${{\rm{Lc}}_{\lim }}$ 进行相应的取值讨论，最后确定 ${{\rm{Lc}}_{\lim }}$ 的取值。

(2)通过对 ${{\rm{Lc}}_{\lim }}$ 的灵敏度分析，得到 ${{\rm{Lc}}_{\lim }}$ 取值与算法效率及最优方案之间的关系，可知 ${{\rm{Lc}}_{\lim }}$ =0.4时，算法效率得到了显著提高，同时最优解质量没有下降，结合算例本身的初始数据，求解得到算例最终方案如表2。

4 结论

1)本文建立了公交线网优化的混合整数规划模型，可以实现公交线网及相应的发车频率同步优化。并针对该问题设计了改进遗传算法，通过设计客流换乘比例下界值 $\rm L{c_{\lim }}$ 作为线网评价指标，对线网结构不合理不进行发车频率分配及相应的目标函数计算，减少了算法对不可行解的搜索范围，提高了算法执行效率。

2)在实际中小城市公交线网优化及规划过程中，该方法可以对现有的公交线网结构作出相应的评价，并在此基础上，对公交线网结构优化提出相应基于乘客出行时间最小化视角的的线网及发车频率设计方案。