郑乐1,高良鹏2,沈金星3,李文权4
(1. 南京邮电大学 现代邮政学院,南京 210003;2. 福建工程学院 交通运输学院, 福州 350108; 3. 河海大学 土木与交通学院,南京 210098;4. 东南大学 交通学院, 南京 210089)
摘要:
为了提高乘客出行需求不确定条件下可变线路式公交的运行服务能力,提出了动态离站时间窗策略以及待选站点策略两种运行优化策略。首先对策略应用背景下可变线路式公交运行方式进行了详述,并将其划分为两阶段的优化问题。然后采用混合整数规划模型对该问题进行建模,第1阶段的优化目标为最大化被服务的乘客数量,第2阶段的优化目标是最小化被接受乘客的总出行时间。针对所构建的模型,提出了一种改进的文化基因算法,对该模型进行求解。基于实际案例的仿真结果表明:两种策略从时间以及空间的维度打破了原有运行方式的固定站点离站时间约束以及乘客上下车点的空间约束,从而提高了可变线路式公交路径规划的灵活性,可以在不增加任何运营成本的情况下显著降低乘客预约请求被拒绝的比例,并且在同时应用时可以实现优势互补,至多可减少22%的乘客被拒绝率。
关键词: 交通工程 可变线路式公交 服务能力 车辆路径问题 文化基因算法
DOI：10.11918/202012031
分类号:U492.2
文献标识码:A
基金项目:国家自然科学基金(7,1)； 南京邮电大学引进人才科研启动基金(NY220170)
Operational service capability optimization strategies for flex-route transit service
ZHENG Yue1,GAO Liangpeng2,SHEN Jinxing3,LI Wenquan4
(1. School of Modern Posts, Nanjing University of Posts and Telecommunications, Nanjing 210003, China; 2. School of Transportation, Fujian University of Technology, Fuzhou 350108, China; 3. College of Civil and Transportation Engineering, Hohai University, Nanjing 210098, China; 4. School of Transportation, Southeast University, Nanjing 210089, China）
Abstract:
To improve the operational service capacity of flex-route transit under uncertain travel demand, a slack arrival strategy and a meeting point strategy were proposed. First, the operating mechanism of flex-route transit service under the proposed strategies was described in detail, and the process was divided into a two-stage optimization problem. Then, mixed integer programming (MIP) was employed to formulate the problem with a twofold objective: to maximize the number of accepted requests in the first stage and to minimize the total trip time of the accepted passengers in the second stage. A memetic algorithm was proposed to solve the model in a reasonable amount of time. Simulation experiments based on a real-life flex-route transit service were conducted to evaluate the proposed strategies. Results show that the two strategies, which relaxed the departure time constraints of checkpoints and the space constraints of reserved pick-up and drop-off locations, could improve the routing flexibility of flex-route transit service and significantly reduce the passenger rejection rate without any additional operating cost. Besides, when the two strategies were applied at the same time, the rejection rate could be reduced by up to 22%.
Key words: traffic engineering flex-route transit service capability vehicle routing problem memetic algorithm
郑乐, 高良鹏, 沈金星, 李文权. 可变线路式公交运行服务能力优化策略[J]. 哈尔滨工业大学学报, 2021, 53(9): 107-115. DOI: 10.11918/202012031.
ZHENG Yue, GAO Liangpeng, SHEN Jinxing, LI Wenquan. Operational service capability optimization strategies for flex-route transit service[J]. Journal of Harbin Institute of Technology, 2021, 53(9): 107-115. DOI: 10.11918/202012031.
基金项目 国家自然科学基金(51808187，52102381)；南京邮电大学引进人才科研启动基金(NY220170) 作者简介 郑乐(1990—)，男，讲师 通信作者 高良鹏，LiangpengGao.Acad@gmail.com 文章历史 收稿日期: 2020-12-10
Abstract Full text Figures/Tables PDF
可变线路式公交运行服务能力优化策略
郑乐1, 高良鹏2
, 沈金星3, 李文权4 1. 南京邮电大学 现代邮政学院，南京 210003;
2. 福建工程学院 交通运输学院，福州 350108;
3. 河海大学 土木与交通学院，南京 210098;
4. 东南大学 交通学院，南京 210089
收稿日期: 2020-12-10
基金项目: 国家自然科学基金(51808187，52102381)；南京邮电大学引进人才科研启动基金(NY220170)
作者简介: 郑乐(1990—)，男，讲师
通信作者: 高良鹏，LiangpengGao.Acad@gmail.com
摘要: 为了提高乘客出行需求不确定条件下可变线路式公交的运行服务能力，提出了动态离站时间窗策略以及待选站点策略两种运行优化策略。首先对策略应用背景下可变线路式公交运行方式进行了详述，并将其划分为两阶段的优化问题。然后采用混合整数规划模型对该问题进行建模，第1阶段的优化目标为最大化被服务的乘客数量，第2阶段的优化目标是最小化被接受乘客的总出行时间。针对所构建的模型，提出了一种改进的文化基因算法，对该模型进行求解。基于实际案例的仿真结果表明: 两种策略从时间以及空间的维度打破了原有运行方式的固定站点离站时间约束以及乘客上下车点的空间约束，从而提高了可变线路式公交路径规划的灵活性，可以在不增加任何运营成本的情况下显著降低乘客预约请求被拒绝的比例，并且在同时应用时可以实现优势互补，至多可减少22%的乘客被拒绝率。
关键词: 交通工程 可变线路式公交 服务能力 车辆路径问题 文化基因算法
Operational service capability optimization strategies for flex-route transit service
ZHENG Yue1, GAO Liangpeng2
, SHEN Jinxing3, LI Wenquan4 1. School of Modern Posts, Nanjing University of Posts and Telecommunications, Nanjing 210003, China;
2. School of Transportation, Fujian University of Technology, Fuzhou 350108, China;
3. College of Civil and Transportation Engineering, Hohai University, Nanjing 210098, China;
4. School of Transportation, Southeast University, Nanjing 210089, China
Abstract: To improve the operational service capacity of flex-route transit under uncertain travel demand, a slack arrival strategy and a meeting point strategy were proposed. First, the operating mechanism of flex-route transit service under the proposed strategies was described in detail, and the process was divided into a two-stage optimization problem. Then, mixed integer programming (MIP) was employed to formulate the problem with a twofold objective: to maximize the number of accepted requests in the first stage and to minimize the total trip time of the accepted passengers in the second stage. A memetic algorithm was proposed to solve the model in a reasonable amount of time. Simulation experiments based on a real-life flex-route transit service were conducted to evaluate the proposed strategies. Results show that the two strategies, which relaxed the departure time constraints of checkpoints and the space constraints of reserved pick-up and drop-off locations, could improve the routing flexibility of flex-route transit service and significantly reduce the passenger rejection rate without any additional operating cost. Besides, when the two strategies were applied at the same time, the rejection rate could be reduced by up to 22%.
Keywords: traffic engineering flex-route transit service capability vehicle routing problem memetic algorithm
近年来，随着城市化进程的加快，越来越多的城市新区逐步形成。这些地区由于尚未形成稳定的客流走廊，其公交系统在成本效益和服务水平两方面难以达到合理平衡。传统的常规公交系统由于运营线路固定且发车频率较低，导致乘客的等车时间以及步行时间较长，因此运营效率低下。需求响应式公交[1]没有严格的站点、线路及时刻表，可以为乘客提供门到门的出行服务，但运营费用高昂，通常仅局限于针对老年人和残疾人的特殊公交服务。
灵活式公交融合了常规公交的高成本效益以及需求响应式公交的灵活性，在北美的很多低人口密度区域应用广泛。文献[2-3]的调查研究表明，可变线路式公交是目前使用最为广泛的一种灵活式公交运营方式。国外的实际运营表明，可变线路式公交相比于需求响应式公交更为经济高效[4]，相比于比常规公交乘客满意度更高[5]。
到目前为止，可变线路式公交的研究大多集中在对其系统参数的设计及调度算法研究方面。文献[6]对可变线路式公交沿基准线路运行速度的上下界进行了评估。文献[7-8]分别针对静态预约需求和动态实时需求了评估，分别提出了相应的可变线路式公交调度算法。文献[9]分析了可变线路式公交车运行周期与服务区域的长、宽之间的关系。文献[10]利用概率近似理论对可变线路式公交最优服务周期进行了估计。文献[11]针对可变线路公交设计了一种可以同时处理静态预约需求和实时动态需求的两阶段车辆调度模型。文献[12]考虑了可变线路式公交车型和车载容量的影响，构建了多车型系统的优化调度模型。
在以上研究以及可变线路式公交的实际运行过程中，站点间额外分配用于服务乘客预约请求的松弛时间被视为定值，且乘客的上下车点必须为其所预约的位置。这些限制条件导致该服务在实际运行过程中受乘客需求的波动影响非常大[13]。当松弛时间不足以满足实际过高的乘客需求时，一些预约请求可能会被拒绝。而当实际需求低于预期时，车内乘客可能会在固定站点经历相当长的空等时间。这两种情况都会显著降低可变线路式公交系统的服务水平，长此以往甚至会导致客流的流失。为了提高乘客需求波动条件下系统的运行服务能力，本文分别从时间以及空间维度出发，提出了可变线路式公交的动态离站时间窗策略和待选站点策略。这两种策略打破了原有运行模式下的强制离站时间以及上下车位置的约束，可以在不影响服务周期且不增加任何运营成本的情况下服务更多的乘客。
1 系统描述 1.1 服务区域及乘客分类如图 1所示，假设可变线路式公交的服务区域为宽度为W，长度为L的矩形。在服务区域内有C个固定站点。每个服务班次，车辆从一个首末站出发，经过所有的固定站点及可服务的预约站点，到达另一个首末站结束。每个固定站点都设有自身的固定离站时间。
Fig. 1
图 1 可变线路式公交示意 Fig. 1 Diagram of flex-route transit service 根据乘客的上下车的位置是否在固定站点，乘客可分为4种类型：1)上车点和下车点都在固定站点，即第1类乘客；2)上车点在固定站点，下车点不在固定站点，即第2类乘客；3)上车点不在固定站点，下车点在固定站点，即第3类乘客；4)上车点和下车点都不在固定站点，即第4类乘客。每类乘客所占比例分别为η1，η2，η3，η4。
第1类乘客无需提前预定，在固定站点候车即可，视为常规乘客。其他3类乘客为需求响应型乘客，出行前需要通过电话或网络进行预约。相邻固定站点之间都分配有一定的松弛时间以服务需求响应型乘客的需求，其值等于相邻固定站点间时刻表所分配的运行时间减去沿基准线路的直接行驶时间。松弛时间的大小通常根据乘客的预期需求水平来确定，在松弛时间的限制范围内，服务车辆允许偏离基准线路去接送预约的需求响应型乘客。
1.2 运行服务能力优化策略可变线路式公交的运行服务能力定义为在一个运行班次中服务乘客预约需求的能力，主要的衡量指标是乘客预约需求被拒绝的比例。在实际运行过程中，如何更加充分地利用站点间的松弛时间，减小由于乘客需求不确定性导致的部分乘客被拒绝现象，是当前亟待解决的问题[14]。针对该问题，本节提出了动态离站时间窗策略以及待选站点策略，两种策略分别从时间以及空间维度出发，对原有的约束进行了松弛，从而增加站点间松弛时间利用的灵活性。
1.2.1 动态离站时间窗策略动态离站时间窗策略对固定站点的离站时间约束进行了松弛，允许车辆在一定的时间窗范围内都可以离站。具体而言，假设车辆到达固定站点i的时间为t_arri，停站时间为t0，该站点的计划离站时间为t_sdi。动态离站时间窗策略放宽了在t_sdi时刻离站的约束，允许车辆在时间窗[t_sdi, t_sdi+ε]内都可以离站。车辆的实际离站时间t_depi可根据下式进行确定：
$t_{-} \mathrm{dep}_{i}=\left\{\begin{array}{l}t_{-} \mathrm{sd}_{i}, t_{-} \mathrm{arr}_{i}+t_{0}<t_{-} \mathrm{sd}_{i} \\t_{-} \mathrm{arr}_{i}+t_{0}, t_{-} \mathrm{sd}_{i} \leqslant t_{-} \mathrm{arr}_{i}+t_{0} \leqslant t_{-} \mathrm{sd}_{i}+\varepsilon\end{array}\right.$ (1)
动态离站时间窗策略通过动态重新分配站点间的松弛时间，可以达到减少拒绝乘客数量以及车辆空等时间的目的。但同时也存在一定负面影响，如在固定站点等待上车的乘客可能会因为到站时间延误而等待更长时间。此外在固定站点下车乘客的乘车时间也可能会被相应地延长。在低出行密度区域，乘客相对更容易接受一个较小范围内的到站时间延误，尤其是当乘客被提前告知车辆的离站时间范围以后。例如，若原先固定站点的计划离站时间为t_sdi，当分配2 min的时间窗宽度后，该站点等候的乘客知道车辆一定会在[t_sdi, t_sdi+2 min]内离站，因此他们只需像往常一样在t_sdi之前到达该站点，并经历至多2 min的等待时间。
1.2.2 待选站点策略待选站点策略对乘客预约的上下车站点约束进行了松弛。如图 2所示，实际应用时运营商需要提前在服务区域内布设一定数量的待选站点，待选站点通常布设在方便车辆停靠以及司乘相互识别的位置。乘客在预约时除了需要提供其理想的上下车点之外(预约站点)，还需要提供其可接受步行距离。调度中心会根据每个班次的实际乘客需求规划车辆的行车计划。对乘客而言，实际的上下车点的位置既可能是其预约站点，也可能是其可接受步行范围内的待选站点。当乘客接受到调度中心反馈的上下车点信息后，步行至相应的待选站点即可。
Fig. 2
图 2 可变线路式公交待选站点策略示意 Fig. 2 Diagram of flex-route transit service with meeting point strategy 待选站点策略的引入不仅可以将部分乘客分配到待选站点以减少车辆的绕行距离[15]，还可以在实际需求过高时，令多名乘客可以在同一待选站点上下车，从而减少车辆的停站次数，节省由于车辆加减速以及上下客所消耗的时间。待选站点策略通过动态调整乘客的实际上下车点以降低需求波动的影响，其代价是部分乘客需要步行少量的距离。
1.3 运行方式及优化目标如图 3所示，系统在处理接收到的预约请求时，会执行一个两阶段的处理过程。在第1阶段，当调度中心接受到乘客的需求后，会立即反馈该乘客是否能被该班次服务，该判断综合考虑了在时间窗范围内车辆的延误到达以及将部分乘客上下车点分配到待选站点的可能。为体现公平性，在第1阶段采取先到先服务的原则，即较早预定的乘客被拒绝的可能性更低。
Fig. 3
图 3 优化策略应用下的系统运行方式示意图 Fig. 3 Diagram of system operation mode under the optimization strategies 在预约截止时间之后，调度中心会对所有能够被服务乘客的需求进行全局优化(第2阶段)。该阶段的主要任务是在能够满足所有乘客需求的基础上，以最小化所有乘客的总出行时间(步行时间+等待时间+车内时间)为目标，生成车辆最优的行车计划方案。
该两阶段反馈过程可以视为一个字典序的两阶段的优化问题，其首要目标是尽可能多地满足更多的乘客预约需求，次要目标是最小化被接受乘客的总出行时间。
2 模型构建针对上述两阶段的优化问题，本文采用混合整数规划模型进行建模，第1阶段用于判断乘客的预约能否被接受，第2阶段用于构建车辆的最优行车计划。这两个阶段的优化问题除目标函数不同外，模型结构几乎完全相同。因此，本节只讨论所有被接受的乘客已确定后的最优车辆路径规划问题。
对于任意预约站点i，定义站点群Si=Mi∪{i}用于表示所有可行的乘客上下车点。其中，Mi为预约站点i可接受步行距离内的所有待选站点集合。定义有向图G=N, A, T来表示车辆的路径规划网络，其中N表示所有的可选站点集合，A=N2表示所有可选站点所构成的边集，T=(tij) 为每条边所对应的车辆行程时间集合，可通过站点间距离以及车辆的平时行驶速度计算得到。该问题的目标可以总结为：在不违反固定站点离站时间窗约束的条件下，确定一条通过所有站点群，且每个站点群只访问其中一个站点的最优路径。
2.1 模型参数模型中的参数定义如下：C为固定站点的数量；N0为固定站点集合，N0={1, 2, …, C}；K为所有被接受的乘客需求集合，K=K1∪K2∪K3∪K4，其中K1~K4分别代表第1类到第4类被接受的乘客需求集合；TC为车辆需要访问的站点总数，TC=C+|K2|+|K3|+2×|K4|；Nn为乘客预约的需求响应型站点集合，Nn={C+1, …, TC}；MP为服务区域内的待选站点集合；rMP为服务区域内的待选站点总数，rMP=|MP|；Si为需求响应型站点i所对应的站点群；N为所有的可选站点集合，N=S1∪S2…STC，其中S1={{1}}，…，SC={{C}}；r为所有可选站点总数，r=|N|；A为所有可选站点所构成的边集；t_sdi为固定站点i的计划离站时间，?i∈N0；t_wki为站点i步行至对应预约站点的时间，?i∈N；tij为站点i至站点j的车辆行驶时间，?i, j∈N；tn为车辆在需求响应型站点的停站时间；t0为车辆在固定站点的停站时间；ps(k)为需求k所对应的上车点；ds(k)为需求k所对应的下车点；Dwalking为预约乘客的可接受步行距离；ε为固定站点的离站时间窗宽度。
模型中所有的决策变量定义如下：xij为0或1，若最优路径包含路段(i, j)，则为1，否则为0；yi为0或1，若最优行驶路径经过站点i，则为1，否则为0；t_depi为站点群Si中所选站点的离站时间；t_arri为站点群Si中所选站点的到站时间；pk为需求k所对应的上车时间；dk为需求k所对应的下车时间。
2.2 模型建立基于以上参数定义，该路径优化问题可以用以下的混合整数规划模型来表示，其中ωVH，ωWK，ωWT分别为车内时间、步行时间以及等待时间的权重。
$\begin{aligned}\min Z=& \omega_{\mathrm{VH}} \sum\limits_{k \in K}\left(d_{k}-p_{k}\right)+\omega_{\mathrm{WK}} \sum\limits_{i=1}^{r} t_{-} \mathrm{wk}_{i} y_{i}+\\& \omega_{\mathrm{WT}} \sum\limits_{k \in K_{1} \cup K_{2}}\left(p_{k}-t_{-} \mathrm{sd}_{p s(k)}\right)\end{aligned}$ (2)
$\text { s.t.: } \quad \sum\limits_{i \in S_{h}} y_{i}=1, h=1,2, \cdots, T C$ (3)
$\sum\limits_{j=1}^{r} x_{1 j}=1, \sum\limits_{j=1}^{r} x_{j 1}=0$ (4)
$\sum\limits_{j=1}^{r} x_{C{j}}=0, \sum\limits_{j=1}^{r} x_{j C}=1$ (5)
$\sum\limits_{j=1}^{r} x_{j i}=\sum\limits_{j=1}^{r} x_{i j}=y_{i}, i=N /\{1, C\}$ (6)
$x_{i i}=0, \forall i \in N$ (7)
$\sum\limits_{i, j \in V} x_{i j} \leqslant|V|-1$ (8)
其中V?N, 且满足与至少1个至多TC－1个站点群的交集为空。
$t_{-} \mathrm{sd}_{i} \leqslant t_{-} \mathrm{dep}_{i} \leqslant t_{-} \mathrm{sd}_{i}+\varepsilon, \forall i \in N_{0} $ (9)
$\begin{gathered}t_{-} \mathrm{arr}_{i} \geqslant t_{-} \mathrm{dep}_{j}+\sum\limits_{p \in S_{i}} \sum\limits_{q \in S_{j}} x_{p q} t_{p q}-M\left(1-\sum\limits_{p \in S_{i}} \sum\limits_{q \in S_{j}} x_{p q}\right), \\i, j=1,2, \cdots, T C \end{gathered}$ (10)
$t_{-} \mathrm{dep}_{i}=t_{-} \mathrm{arr}_{i}+t_{\mathrm{n}}, i=C+1, \cdots, T C$ (11)
$t_{-} \mathrm{dep}_{i} \geqslant t_{-} \mathrm{arr}_{i}+t_{0}, \forall i \in N_{0} /\{1\}$ (12)
$p_{k}=t_{-} \mathrm{dep}_{p s(k)}, \forall k \in K $ (13)
$d_{k}=t_{-} \mathrm{arr}_{d s(k)}, \forall k \in K $ (14)
$d_{k}>p_{k}, \forall k \in K$ (15)
式(2)为目标函数，优化目标是乘客的总出行时间Z最小，包括乘客的车内时间、步行时间以及由于车辆延误到达造成的第1及第2类乘客的等待时间。约束(3)表示对于任意一个站点群而言，车辆有且仅可以访问其中的一个站点。约束(4)和(5)对首末站的特殊情形进行了讨论，对于首发站而言，入度为0，出度为1；对于终点站而言，入度为1，出度为0。对于除首末站外的任意一个中间站点，约束(6)确保了若站点为对应站点群中的所选站点，其入度和出度均为1；否则，其入度和出度均为0。约束(7)保证了所有站点不会存在自连接的情况。约束(8)确保了在车辆路径中不会出现回路的情况。约束(9)保证了车辆在固定站点的离站时间必须在离站时间窗的范围内。约束(10)为模型的核心约束，表示若两个站点群之间存在连接(即先后被车辆服务)，站点群j中所选站点的到达时间不会早于站点群i中所选站点的离站时间加上在两个站点之间的行驶时间，当两个站点群之间不存在连接时，采用大M法令此约束无效。约束(11)保证了站点的离站时间等于车辆到达该站点的时间加上停站服务时间。由于车辆在固定站点可能存在部分空等时间，因此约束(12)保证了车辆在固定站点的离站时间要晚于车辆的到达该站点时间加上在停站服务时间。约束(13)为每个乘客需求的上车时间与其对应站点的车辆离站时间之间建立了等式关系。同理，约束(14)为每个乘客需求的下车时间与其对应站点的车辆到站时间之间建立了等式关系。约束(15)保证了乘客的下车时间要晚于其上车时间。
3 模型求解上述问题可以看作是一类带有时间窗约束的广义旅行商问题(GTSP)，该问题是公认的NP-hard问题。在问题规模较小的情况下，可以采用分支定界法或者割平面法等精确算法进行求解[16]，但其求解复杂度会随着问题规模的增大呈指数方式增长。本文所提的两阶段反馈过程都对求解时间有着较为严格的要求，因此精确算法难以适用。
鉴于此，采用文化基因算法对该模型进行求解[17]。文化基因算法是一种混合型算法，该算法结合了遗传算法和局部搜索算法的优点，能够在合理的计算时间内得到高质量的近似最优解。具体的算法流程如图 4所示。
Fig. 4
图 4 文化基因算法流程 Fig. 4 Flow chart of the memetic algorithm 3.1 染色体编码本文采用自然排列编码的方式对车辆的行驶路径进行染色体编码，染色体的生成必须满足以下两个条件：1)每个站点群只能选择一个站点纳入到染色体中；2)染色体的第一个和最后一个元素必须对应可变线路式公交的首末站。
3.2 适应度函数适应度值由两部分构成，第1部分与混合整数规划模型的目标函数值相同，第2部分为惩罚值，用于表征可行解对固定站点的离站时间窗约束的遵守情况，可通过式(16)和式(17)计算得到。
$\text { Penalty }=\sum\limits_{i=2}^{C} \mathrm{Sig}\left(t_{-} \mathrm{dep}_{i}-\left(t_{-} \mathrm{sd}_{i}+\varepsilon\right)\right)$ (16)
$\mathrm{Sig}(x)=\left\{\begin{array}{l}\lambda_{1} x+\lambda_{2}, x>0 \\0, x \leqslant 0\end{array}\right.$ (17)
其中：λ1为用于衡量超出离站时间窗上界部分的惩罚系数，λ2为固定惩罚系数。
对于第1阶段的乘客预约请求的处理，可以通过查看最优解是否存在惩罚值来判断该需求能否得到满足。如果惩罚值等于0，则该预约需求可以被服务；否则，拒绝该请求。
3.3 初始种群生成初始种群由于包含了构造最优解所需的大部分信息，因此对于算法的性能影响极大。本研究中，初始种群的染色体数量设置为5TC。对于每条染色体，其初始点P1设为可变线路式公交的第1个固定站点。对于其后任意一个站点Pk，k∈{2, …, TC-1}，首先对其所在站点群进行选择，每个站点群被选择的概率与其距离前一个站点的距离成反比(选择乘客预约站点作为该站点群的代表用于计算距离)，然后再从该站点群中随机选择一个站点放入该条染色体中。染色中的最后一个点PTC设置为可变线路式公交的最后一个固定站点。
3.4 遗传操作在本研究中，40%的种群直接通过从上一代种群中选择得到，40%的种群通过交叉产生，剩下的20%通过变异产生。这些遗传操作的具体描述为：1)选择操作，采用精英策略，将上一代种群中适应度较高的一部分个体作为父代染色体；2)交叉操作，采用PMX交叉方法，通过交换父代部分染色体信息从而生成两个子代染色体，随机生成交换起点位置a以及交换长度l，最终染色体交换位置的区间可以表示为[a, a+l]；3)变异操作，作用于单个染色体，随机将染色体的一部分移除，然后再将移除部分插入到剩余部分中的任意随机位置中。移除部分的长度从2到TC/2不等。
3.5 局部搜索遗传算法是对种群进行全局广域搜索，而局部搜索是对种群中的个体进行局部深度搜索，从而提高单个染色体的适应度值。每当生成一个新的染色体(初始种群或通过交叉、变异操作产生)，都会先后执行“插入”和“k邻域交换”操作以提高单个染色体的质量。
1) 插入操作。首先将染色体中站点群Si对应的节点删除，然后通过枚举的方式尝试站点群Si中所有的站点和插入位置的组合，最后将适应度值提高最多的新染色替换原来的染色体。对于每条染色体，共执行TC-C次插入操作，以保证所有的待选站点在局部优化时都得到了考虑。
2) k邻域交换操作。首先选择染色体中k个相邻的节点，然后对这k个节点对应站点群所有可能的全排列进行逐个尝试，最后将适应度值最低的染色体替换当前染色体。对于每条染色体，算法会随机遍历所有k个相邻的节点的组合。为保证算法的精度，本文研究采用4邻域交换操作。
3.6 终止条件当达到迭代次数Imax或者连续Idlemax次迭代最优解的适应度值未发生改变时，算法终止。终止条件可以根据具体问题的规模来设定，本研究中终止条件参数设置为Imax=30，Idlemax=5。
4 结果分析 4.1 系统参数设置以美国洛杉矶646路公交为例进行仿真案例研究。646路公交是一个典型的可变线路式公交系统并广泛被国内外学者用作案例分析[6-8, 11, 14]，其具体公交线路图可参考文献[18]。研究假设所有乘客的预约站点以及待选站点在服务区域内服从均匀分布；公交车辆行驶规则采用方格路网，即先沿X方向行驶，再沿Y方向到达停靠点[19]。站点间的行驶时间以及乘客的步行时间可以通过车辆的平均行驶速度Vb以及乘客平均步行速度Vwk计算得到。
系统的参数取值设定如下：服务区域的长度L=16 km，宽度W=1.6 km；基准线路上设有3个固定站点(C=3)；服务区域内的待选站点总数rMP=80；乘客的可接受步行距离Dwalking=0.48 km；车辆的平均行驶速度Vb=40 km/h；乘客的平均步行速度Vwk=4.8 km/h；车辆在固定站点的停站时间t0=1 min；车辆在需求响应型站点的停站时间tn=0.3 min；4类出行乘客比例设为η1=0.1，η2=0.4，η3=0.4，η4=0.1；惩罚系数λ1=10，λ2=50；车内时间、步行时间以及等待时间的权重设为ωVH=ωWK=ωWT=1；固定站点的离站时间窗宽度ε=2 min；系统的预期乘客需求δ=12人/班次，根据文献[20]所提出的理论模型，可以得到单程运行时间Tr=40 min。
4.2 算法对比为了验证所采用的启发式算法的有效性，本文对比了不同乘客需求下文化基因算法以及采用CPLEX求解MIP模型的计算结果。对比指标包括3项：1)第1阶段系统最多能服务的乘客数量；2)第2阶段系统的目标函数值；3)算法的计算时间。由于可变线路式公交通常服务于低人口密度区域，因此假设乘客需求不超过25人/班次。从表 1可以看出，采用CPLEX求解的计算时间随着乘客需求的增加呈指数方式增长。当乘客需求为25人/班次时，需要10 h以上的计算时间。因此，采用精确算法进行求解难以满足可变线路式公交在实际运行中实时性的要求。相比之下，除了乘客需求为25人/班次之外，文化基因算法在所有需求场景下的计算结果都与最优解相同，且计算时间相较精确算法大幅度缩短。这表明该启发式算法无论在求解质量还是计算时间方面都具有较好的性能，能够满足实际应用的需要。因此，后续的仿真计算均采用文化基因算法进行求解。
表 1
表 1 文化基因算法与CPLEX计算结果对比 Tab. 1 Comparison between results calculated by CPLEX and memetic algorithm 乘客需求/(人/班次) 文化基因算法计算结果CPLEX计算结果 接受的乘客数 目标函数/min 时间/s 接受的乘客数 目标函数/min 时间/s
5 5 80.74 1.07 5 80.74 4.48
10 10 179.50 1.42 10 179.50 15.57
15 15 276.88 9.46 15 276.88 136.26
20 18 365.43 38.68 18 365.43 1 945.38
25 21 427.45 156.60 21 425.93 37 236.52
表 1 文化基因算法与CPLEX计算结果对比 Tab. 1 Comparison between results calculated by CPLEX and memetic algorithm
4.3 优化策略的影响分析本文通过仿真对比了4类运行模式下的系统性能。分别为：1)传统的可变线路式公交系统(下文中称为Flex)；2)动态离站时间窗策略下的系统(下文中称为Flex-slack)；3)待选站点策略下的系统(下文中称为Flex-MP)；4)两种策略同时应用下的系统(下文中称为Flex-slack-MP)。为模拟实际运行中乘客需求的波动性，对不同乘客需求水平下的场景进行仿真。对于每个场景，共进行100个运行班次的仿真以保证结果的可靠性。
系统性能的评估指标包括：1)拒绝率Rej，即乘客预约请求被系统拒绝的比例；2)乘车时间RD，即乘客的平均乘车时间，包括车辆行驶时间以及站点的服务时间；3)空等时间ID，即车辆提前到达固定站点时，车上乘客在固定站点的平均等候时间；4)等车时间WT，即由于车辆延误到达，乘客在固定站点的平均等待时间；5)步行时间WK，即乘客从出发点步行至待选站点以及从待选站点步行至目的地的平均步行时间。
图 5为不同需求水平下的拒绝率的变化趋势。可以看出随着实际出行需求的增加，传统的可变线路式公交拒绝率增长迅速。动态离站时间窗策略以及待选站点策略分别在时间和空间维度增加了车辆路径规划的灵活性，能够显著的降低系统的拒绝率。当实际乘客需求较高时，由于待选站点策略可以通过将两个甚至多个需求匹配到同一个站点完成上下车，因此对于拒绝率降低效果更为明显。图 6为不同需求水平下Flex-MP运行模式待选站点的使用情况，可以看出随着乘客需求的增加，待选站点的使用比例以及多个需求匹配在同一站点的比例都会逐渐增加。
Fig. 5
图 5 不同需求水平下的系统拒绝率 Fig. 5 Rejection rates under different demand levels Fig. 6
图 6 不同需求水平下待选站点需求匹配数量比例分布 Fig. 6 Percentages of single, double, and three or more matches under different demand levels Flex-slack-MP融合两种策略的优势并在应用过程中可以相互补充，因此在拒绝率控制方面相较于单一策略的使用效果更为显著，从图 5可以看出，随着实际乘客需求的增加，Flex-slack-MP系统对于拒绝率的抑制作用逐渐提升，至多可减少22%的系统的拒绝率。
图 7为不同需求水平下各类乘客出行时间的变化趋势。随着实际出行需求水平的增加，可以看出：1)在Flex-slack运行模式下，乘客的乘车时间有所增加，但由于松弛时间利用率的提高，空等时间显著减少，由于车辆存在晚于预计到达的情况，因此在固定站点候车乘客会存在少量等车时间；2)在Flex-MP运行模式下，由于部分乘客需要步行至附近的待选站点完成上下车，因此存在一定的步行时间，并且平均步行时间会随出行需求的增加而显著增加；3)在Flex-slack-MP运行模式下，部分乘客可能需要经历一定的等车时间及步行时间，当乘客需求相对较少时，系统会优先应用离站时间窗策略来减少系统拒绝率，但随着需求量的进一步增加，待选站点策略应用的比重会逐步增加。
Fig. 7
图 7 不同需求水平下的乘客出行时间 Fig. 7 Passenger trip time under different demand levels 总体而言，所提出的3种运行模式能够很好地提高需求不确定性下可变线路式公交的服务可靠性，减少乘客频繁被拒绝以及在站点空等所造成的满意度下降。尽管乘客的总出行时间会有所提高，但由于时间窗的宽度以及可接受的步行距离都存在上限，因此并不会造成单个乘客出行时间的大幅增加。就其适用环境而言，Flex-slack运行模式适用于乘客对步行更加敏感而对车辆到站时间可靠性要求不高的情形，如步行环境较差，夜间环境等。而Flex-MP运行模式更加适用于对到站时间可靠性关注度较高但能接受少量步行的情形，如需要在固定站点进行换乘，步行环境较好等。Flex-slack-MP运行模式则适用于乘客对步行以及到站时间可靠性均不敏感的情形。
4.4 灵敏度分析本文对预期乘客需求下(δ=12人/班次)不同运行模式的参数灵敏度进行了分析。分析参数包括两类：1)时间窗宽度ε；2)服务区域内待选站点总数rMP。
从表 2可以看出，在Flex-slack运行模式下，随着时间窗宽度ε的增加，系统的拒绝率从12.83%急剧下降至2.25%并呈现逐步放缓的趋势，乘客的空等时间也有所减少。但与此同时，乘客的平均等待时间以及车内乘客的乘车时间也有所提高。尽管时间窗宽度的增加能够进一步地增强路径规划的灵活性，但在实际应用过程中，时间窗宽度的设置不宜过大，否则会降低车辆到站时间的稳定性，造成客流流失。
表 2
表 2 不同运行优化策略下的参数灵敏度分析 Tab. 2 Sensitivity analysis over different operational strategies 运行方式 策略参数及取值 Rej/% RD /min ID /min WT /min WK /min Flex 无 12.83 15.06 0.92 0 0
ε=1 min 7.25 15.59 0.69 0.02 0
Flex-slack ε=2 min 4.42 15.69 0.68 0.04 0
ε=3 min 2.25 15.82 0.66 0.06 0
rMP=40 7.58 15.23 0.87 0 0.35
Flex-MP rMP=80 5.75 15.16 0.86 0 0.49
rMP=120 3.67 15.12 0.82 0 0.68
ε=1 min, rMP=40 3.75 15.51 0.69 0.02 0.25
Flex-slack-MP ε=2 min, rMP=80 1.08 15.74 0.67 0.05 0.22
ε=3 min, rMP=120 0.33 15.87 0.65 0.06 0.11
表 2 不同运行优化策略下的参数灵敏度分析 Tab. 2 Sensitivity analysis over different operational strategies
在Flex-MP运行模式下，随着待选站点数量的增加，系统的拒绝率显著降低，乘客的平均乘车时间以及空等时间也都有所减少。但由于待选站点使用比例的上升，乘客的平均步行时间也随之增加。在实际应用中，运营商应结合服务区域的实际土地利用特性以及路网条件尽可能多地布设更多的待选站点以增加路径规划的灵活性。
在Flex-slack-MP运行模式下，拒绝率下降更为显著，至多可将拒绝率降至0.33%。但同时乘客也不可避免地会经历一定的等待时间和步行时间。由于该种运行模式能够有效地抑制需求不确定性的影响，因此对于乘客需求时空波动较大的区域应优先考虑实施。
5 结论1) 在当前可变线路式公交运行模式中，所有固定站点的离站时间是确定的，并且乘客的上下车点必须为其预约的位置，这种运行模式在实际路径规划中由于缺乏一定的灵活性，在乘客需求波动较大的情况下会造成乘客在固定站点空等以及部分乘客被拒绝的现象。针对此问题，分别从时间以及空间维度出发，提出了动态离站时间窗策略和待选站点策略，用以提高乘客需求波动情况下的可变线路式公交的运行服务能力。并在此基础上，建立了策略应用背景下的两阶段混合整数规划模型以及相应的启发式求解算法。
2) 研究结果表明，这两种策略的实施可以显著地减少乘客被拒绝现象，使得松弛时间得到更加充分的利用，其代价是部分乘客可能需要经历少量的等待时间和步行时间。研究还发现，当两种策略联合使用时能够更好地控制系统的拒绝率，实现有效的互补。
3) 在策略实际实施过程中，为了减少车辆的到站时间延误以及步行至待选站点给乘客带来的不便，运营商可以开发具备显示车辆实时位置以及步行导航功能的手机客户端，以帮助用户更快地适应新策略的实施。另外，对于需要步行至待选站点的乘客，运营商应考虑在票价方面给予一定的补偿以弥补其由于步行而产生的不便。最后，由于几乎所有的灵活式公交服务都会受到站点间松弛时间以及乘客上下车位置的限制，因此所提出的动态离站时间窗策略及待选站点策略除了可应用于可变线路式公交之外，对于提升其他类型灵活式公交的运行服务能力同样可以发挥作用。
参考文献
[1] HUANG Di, TONG Weiping, WANG Lumeng, et al. An analytical model for the many-to-one demand responsive transit systems[J]. Sustainability, 2020, 12(1): 298.
[2] KOFFMAN D. Operational experiences with flexible transit services: a synthesis of transit practice[R]. Washington DC: Transportation Research Board, 2004
[3] POTTS J F, MARSHALL M A, CROCKETT E C, et al. A guide for planning and operating flexible public transportation services[R]. Washington DC: Transportation Research Board, 2010
[4] FITTANTE S R, LUBIN A. Adapting the Swedish service route model to suburban transit in the United States[J]. Transportation Research Record: Journal of the Transportation Research Board, 2015, 2536: 52.
[5] BECKER J, TEAL R, MOSSIGE R. Metropolitan transit agency's experience operating general-public demand-responsive transit[J]. Transportation Research Record: Journal of the Transportation Research Board, 2013, 2352: 136. DOI:10.3141/2352-16
[6] QUADRIFOGLIO L, HALL R W, DESSOUKY M M. Performance and design of mobility allowance shuttle transit services: bounds on the maximum longitudinal velocity[J]. Transportation Science, 2006, 40(3): 351. DOI:10.1287/trsc.1050.0137
[7] QUADRIFOGLIO L, DESSOUKY M M, ORDó?EZ F. Mobility allowance shuttle transit (MAST) services: MIP formulation and strengthening with logic constraints[J]. European Journal of Operational Research, 2008, 185(2): 481. DOI:10.1016/j.ejor.2006.12.030
[8] QUADRIFOGLIO L, DESSOUKY M M, PALMER K. An insertion heuristic for scheduling mobility allowance shuttle transit (MAST) services[J]. Journal of Scheduling, 2007, 10(1): 25. DOI:10.1007/s10951-006-0324-6
[9] ZHAO Jiamin, DESSOUKY M. Service capacity design problems for mobility allowance shuttle transit systems[J]. Transportation Research Part B: Methodological, 2008, 42(2): 135. DOI:10.1016/j.trb.2007.07.002
[10] CRAINIC T G, ERRICO F, MALUCELLI F, et al. Designing the master schedule for demand-adaptive transit systems[J]. Annals of Operations Research, 2012, 194(1): 151. DOI:10.1007/s10479-010-0710-5
[11] 邱丰, 李文权, 沈金星. 可变线路式公交的两阶段车辆调度模型[J]. 东南大学学报(自然科学版), 2014, 44(5): 1078.
QIU Feng, LI Wenquan, SHEN Jinxing. Two-stage model for flex-route transit scheduling[J]. Journal of Southeast University (Natural Science Edition), 2014, 44(5): 1078.
[12] 王正武, 赵振于, 何煦. 多车型MAST的调度优化及关键参数分析[J]. 交通科学与工程, 2018, 34(2): 85.
WANG Zhengwu, ZHAO Zhenyu, HE Xu. Scheduling optimization and key parameter analysis of multi-class vehicle mobility allowance shuttle transit[J]. Journal of Transport Science and Engineering, 2018, 34(2): 85. DOI:10.3969/j.issn.1674-599X.2018.02.015
[13] VELAGA N R, NELSON J D, WRIGHT S D, et al. The potential role of flexible transport services in enhancing rural public transport provision[J]. Journal of Public Transportation, 2012, 15(1): 111. DOI:10.5038/2375-0901.15.1.7
[14] QIU Feng, LI Wenquan, ZHANG Jian. A dynamic station strategy to improve the performance of flex-route transit services[J]. Transportation Research Part C: Emerging Technologies, 2014, 48: 229. DOI:10.1016/j.trc.2014.09.003
[15] STIGLIC M, AGATZ N, SAVELSBERGH M, et al. The benefits of meeting points in ride-sharing systems[J]. Transportation Research Part B: Methodological, 2015, 82: 36. DOI:10.1016/j.trb.2015.07.025
[16] YUAN Yuan, CATTARUZZA D, OGIER M, et al. A branch-and-cut algorithm for the generalized traveling salesman problem with time windows[J]. European Journal of Operational Research, 2020, 286(3): 849. DOI:10.1016/j.ejor.2020.04.024
[17] SALES L P A, MELO C S, BONATES T O, et al. Memetic algorithm for the heterogeneous fleet school bus routing problem[J]. Journal of Urban Planning and Development, 2018, 144(2): 04018018. DOI:10.1061/(ASCE)UP.1943-5444.0000454
[18] 邱丰. 可变线路式公交运营调度与模式优化研究[D]. 南京: 东南大学, 2015
QIU Feng. Study of scheduling and operating mode optimization for flex-route transit service[D]. Nanjing: Southeast University, 2015
[19] QUADRIFOGLIO L, DESSOUKY M M, ORDó?EZ F. A simulation study of demand responsive transit system design[J]. Transportation Research Part A, 2008, 42: 718.
[20] ZHENG Yue, LI Wenquan, QIU Feng. A slack arrival strategy to promote flex-route transit services[J]. Transportation Research Part C: Emerging Technologies, 2018, 92: 442. DOI:10.1016/j.trc.2018.05.015
