考虑拥堵道路停车惩罚的定制公交调度研究

程仁辉，贾顺平

(北京交通大学 交通运输学院，北京 100044)

定制公交(customized bus，CB)是一种介于价格实惠的常规公交和舒适快捷的网约车之间的一种公交服务模式，服务于特定人群，为处于相同区域、有相近出行时间和相似出行需求的乘客群体量身定制[1]。定制公交有着比常规公交更加复杂且精细的运作流程。首先必须进行需求分析，制定基本的线路开行方案；然后设计产品方案，包括乘客端、司机端和调度端等终端设计；最后招募乘客，编制最终的行车计划和人员排班计划[2]。由于乘客的出行需求是动态变化的，定制公交需要对实时产生的乘客请求进行决策响应和调度安排[3]。

对网约公交的研究是从理论设想逐渐深入实际的。Liu等[4]全面考察了定制公交的背景及其在中国的时空分布，分析了CB的运营规划过程。Tong等[5]从时空网络建模的角度出发，提出了一种基于多商品网络流的优化模型和基于时空棱镜的算法，在满足通过时空窗定义的个性化需求的同时，优化车辆容量的利用率。Lyu等[6]提出了一种面向定制公交系统的公交线路规划框架CB-Planner，并利用中国南京市的出租车轨迹数据验证了优化模型。

对公交车辆调度和路径规划等优化问题，专家学者采用了多种方法来进行模拟求解。对于突尼斯的校车路径规划，Euchi等[7]采用元启发式方法和改进混合人工蚁群算法求解，以使得校车总行驶距离最小化。邵文等[8]考虑混合车型联合调度和乘客满意度对接驳公交路径优化的影响，建立了灵活型接驳公交路径协同优化模型。郑汉等[9]提出使用混合车型的需求响应服务定制方法，构建了需求响应公交服务定制等价分解模型。赵伟忠[10]以乘客在站等待时间、乘客在车等待时间、车辆运行效益为优化目标，建立了实时公交线路生成模型，从可靠性和舒适性两方面来研究需求响应式定制公交线路设计。

目前对定制公交的研究主要集中于路径规划、政策选择、服务水平评价等方面，但是大多数的研究都比较理想化，简单地以总路径最短或者运营成本最小为最优目标，而很少考虑实际条件下道路拥堵条件和乘客对等待时间和费用的接受程度。本文以企业密集的城市产业园区乘客通勤问题为背景，在乘车需求集中区域，研究单一首发站和终点站的定制公交决策安排和车辆调度。考虑到定制公交在拥堵道路停车载客对道路交通的影响，构造合适的拥堵道路停车惩罚函数，以定制公交及乘客的最优成本为目标建立了实时需求响应的定制公交调度决策模型，并采用改进遗传算法和插入算法求解模型。

1 惩罚函数和调度规则

1.1 拥堵道路停车惩罚函数

大城市很多产业园区接近城市边缘，这些区域公共交通覆盖密度低，其服务难以满足乘客个性化需求，园区内主要道路饱和度过高且服务水平低下。推动定制公交替代私人交通出行，可以有效缓解道路拥堵情况。但是定制公交车辆在拥堵道路上多次停车载客会让乘客产生厌烦心理，同时由于道路等级低还会严重阻碍道路交通顺畅。考虑乘客心理和道路交通的影响，对定制公交给予一定的拥堵道路停车载客惩罚。通过停车载客惩罚成本约束定制公交对乘客需求的响应，减少在某些拥堵道路上的停车载客次数，而尽量在负荷度小的道路上进行响应载客，使定制公交能够连续行驶且减少对高负荷道路的压力，维持路网的通畅。

本文考虑公交车辆在不同等级及不同拥堵程度道路上，由于停车次数和人数造成的占用道路构造了式(1)停车惩罚成本函数。

(1)

式中，Froad为拥堵道路停车惩罚成本，N为道路R上累计停车载客的人数，LR为道路等级修正系数(本文对次干路和支路分别取1.2和0.9)，C为道路负荷度，p为停车次数，m、n为参数。从式(1)可以看出，停车惩罚成本和载客人数成正比关系，与停车次数呈指数关系。

1.2 乘客时间窗成本惩罚函数

在实际情况下，乘客对等待公交车辆的时长具有一定的忍耐程度，但随着等待时间的增加，乘客的不满意度会急剧上升。考虑用时间成本函数来对车辆违反乘客时间窗进行惩罚，惩罚成本会随着违反时间的增加呈指数趋势增长。式(2)为乘客时间窗的时间成本惩罚函数[11]。

(2)

1.3 调度规则

定制公交开行方案由两方面的乘客需求确定，一是提前预约的乘客静态需求，二是实时网约的乘客动态请求，定制公交需要对车辆进行调度和响应决策来满足乘客的预约和网约需求。主要有以下几个原则：

(1)乘客静态需求的优先级高于乘客动态需求，即一个调度周期内应首先根据提前预约的客流需求制定调度计划，其次实行动态调整。

(2)对于提前预约的乘客，需要满足其时间窗要求；对于临时网约的乘客，如果响应则应尽量减少其等待时间，并告知乘客需要等待的时间。

(3)假设乘客在其预约时间点上到达服务点，等车忍耐时长为5 min。

(4)为减少使用的车辆数，制定的车辆调度周期在满足乘客时间窗的前提下应有冗余时间循环服务。

(5)通过对车等人、人等车的时间成本惩罚，避免车辆长时间的停靠等待和掉头接客，避免乘客等车时间过长。

根据调度规则，制定了如图1所示的一个周期定制公交静、动态两阶段调度流程。第一阶段为带时间窗的静态车辆路径问题(SVRP)，首先根据预定需求制定静态开行方案，并对实时产生的网约请求进行判断。第二阶段为动态车辆路径问题(DVRP)，通过路径插入，对局部成本变动进行比较后作出决策，若当前班次选择响应实时请求，则形成新的路径，若选择不进行响应，则继续原来的开行方案。

图1 定制公交基本调度流程图

2 定制公交调度模型

2.1 问题描述

研究的某区域内，定制公交有唯一起终点和多个沿途公交服务点，起点首发站停车场和终点位置均已确定，沿途公交服务站点则根据乘客需求进行决策确定。预先确定公交发车周期以及基准线路，对提前预约和实时网约的乘客进行定制服务。一个运行周期具有一定的松弛时间，公交可以在约束条件下偏离基准线路响应实时需求载客，通过其灵活可变的时空范围来更好地完成车辆的调度计划。

2.2 模型假设

建立的模型需要满足乘客的软时间窗要求，减少乘客等待时间，并在调度车辆的服务路径中考虑停车惩罚，尽量减少在饱和度过高道路上的停车载客次数。为方便建立模型，本文给出以下的假设。

(1)在服务范围内，乘客动态请求是随机的，且符合空间和时间上的均匀分布。将服务站点乘客上下车的时间成本考虑进拥堵道路停车惩罚成本中计算。

(2)定制公交在行程中基本匀速行驶，不受交通条件和道路条件的限制。

(3)公交车辆采用单方向行驶，即每个站点只经过一次，基准路线上不允许掉头和下客。

(4)定制公交停靠点设为始发点，开行前公交车辆都在始发站点处等待，公交终点为某一固定的地铁站，但是沿途服务点为服务区域范围内自由选择。

(5)车内乘客数量不超过规定公交车型的额定座位数。

2.3 模型建立

模型参数及其含义如表1所示。

表1 模型参数及其含义

本文综合考虑乘客需求、公交车辆运行成本和拥堵道路停车成本及乘客时间窗惩罚成本，以系统总成本最小建立了定制公交车辆调度模型，如式(3)所示。

(3)

(4)

(5)

(6)

(7)

(8)

(9)

模型目标函数Z，包含的4个目标分别为乘客在车时间成本、车辆运行时间成本、违反乘客时间窗惩罚成本和拥堵道路停车惩罚成本，综合以求得最小的系统广义总成本。式(4)表示公交车辆一定会经过线路上的某一服务点；式(5)表示车辆经过某一站点后会离开此站点；式(6)为起点约束，服务点O为起始站点；式(7)为终点约束，服务点n为终点站；式(8)为车辆运行周期时间约束，不超过乘客可容忍的最大的乘车时间；式(9)为载客量约束，不超过车辆额定载客量。

式(3)是根据预约乘客的需求信息建立的SVRP调度模型，而实时网约的乘客动态请求，则是一个DVRP调度问题。是否实时响应产生的动态请求r需要考虑定制公交荷载量约束以及改变原定线路后的成本变化。本文采用插入式算法，采用式(10)成本变动函数进行决策判断。对动态请求仅考虑局部费用，即增加的乘客时间窗惩罚成本和停车载客成本，在去除车票价格fr后，选择最小成本变动者进行响应，将动态请求插入到现有线路中，车辆及时作出调整，规划新的载客方案，而将不满足的请求传给下一班次的车辆进行调度安排。每一车次都会不断地对实时产生的r=r+1个需求进行成本计算和决定是否响应此请求，并及时更新线路，直到到达终点。

min ΔZ=ΔF(t)+ΔFroad-fr。

(10)

2.4 求解方法

因为定制公交路径规划问题是多目标优化难题，随着数据规模的扩大，计算量将呈指数增大，传统方法难以在较短时间内解决。本文采用搜索能力较强的改进遗传算法和插入精确求解法来求解建立的模型，对交叉和变异的概率大小采用自适应化处理，计算公式如下：

(11)

式中，Po为交叉概率，Pv为变异概率,fmax为种群中最大适应值,favg为种群平均适应值,f′为交叉的两个体适应度值较大者,f为个体适应度值,k1、k2、k3、k4为常数。

求解步骤如下：

Step 1：采用实数编码，0表示定制公交出发点，从1开始的自然数表示静态需求点。随机生成染色体创建定制公交调度路径初始种群initpop，经过荷载约束判断后，根据模型计算出每条车辆路径目标函数值，经过函数值变换f=1/f成为最大化问题，得出每条染色体的适应度值。

Step 2：遗传算法的选择、交叉和变异操作。根据染色体的适应度值，采取精英保留策略保存最佳个体后，再使用轮盘赌方式选择优化个体遗传下一代。采用保留精英个体的部分映射交叉和基本位变异算子来产生新的种群newpop。

Step 3：终止条件判断。如果迭代次数(iteration)大于最大进化代数(maxiter)，则终止运算，否则返回Step 2继续迭代。

Step 4：对新增的动态需求r，根据荷载约束条件，插入当前路径求出最小的成本变化ΔZ,来判断是否响应请求。如果响应，则对r=r+1请求继续进行决策，反之，给下一班次进行调度。

3 案例分析

3.1 背景介绍

本文以北京市海淀区软件园为研究背景，验证提出的模型适用性和开通定制公交的可行性。园区乘客由于职住分离，多数人以附近西二旗和新开通的清河地铁站为换乘点，并且员工因为弹性工作制，可以为定制公交带来足够的差异化乘客。软件园区道路情况和定制公交OD位置如图2所示。

图2 园区路网和定制公交车场位置图

园区内路网较为密集，多为低等级次干路和支路，以软件园南街为基准路线。园区西侧为公交起点，终点为东侧轨道交通站点。经调研发现，园区各道路面临交通压力区别较大，软件园南街高峰小时负荷度达0.8，部分路段甚至超过了1，高峰时段拥堵相当严重，而其他道路则为0.5左右。

3.2 参数标定

对案例的主要参数标定如表2所示，其中车辆最大的行驶时间为45 min，公交最大载客量为16人。定制公交需要制定合理的发车计划，本文案例设固定发车周期为15 min，使用3辆车来对乘客需求进行载客调度安排。

表2 案例主要参数标定

拥堵停车惩罚函数参数取值为：

乘客时间窗约束惩罚函数参数标定为：

站点的预约人数和预约时刻见表3，这里将时刻表简单化成从0 min开始，站点之间的行驶时间见表4。

表3 各站点的预约人数和预约时间

表4 各站点间旅行时间矩阵表

除了提前预约站点外，在实际运行过程中，定制公交还需要对实时的动态需求进行处理。假设时间在30 min时，公交系统收到5个动态需求r1,r2,…,r5，每个需求的人数均为1，通过采用SVRP调度阶段改进遗传算法和DVRP调度阶段插入式方法进行计算求解，定制公交做出响应决策和调度安排。

3.3 运行结果及分析

对文章案例的计算是在Win10系统电脑上，使用Python语言进行编码求解。在模型约束条件下，遗传算法运行结果如图3所示，目标函数大约在400代达到收敛，运行时间为8.9 s，得出的静态最优解染色体编码为[0, 2, 5, 6, 8, 11, 13, 15, 0, 1,3, 4, 7, 9, 10, 12, 14]，表示2—5—6—8—11—13—15和1—3—4—7—9—10—12—14两条定制公交车辆调度路径。

图3 目标函数求解进化趋势

定制公交在对静态需求进行车辆调度和路径规划之后，对实时产生的乘客需求进行插入计算，进而做出响应决策并动态调整车辆调度。根据计算结果，在不考虑拥堵道路停车载客惩罚情况下，定制公交将对5个动态需求均进行响应，这种结果导致车辆在南街停车次数过多及增加旅行时间，会加大南街的交通压力，对乘客产生负面效果。

而在考虑停车载客惩罚情况下，定制公交根据最优成本做出响应的决策，得出车辆路径图见图4，最终结果见表5。

图4 车辆调度路径图

表5 考虑停车惩罚后定制公交调度结果

定制公交对动态需求中4个请求进行了响应，车辆1和车辆2分别响应了1个和2个请求，同时将请求r4和9插入进后续第3辆车的可能路径中，系统出于满载和惩罚约束以及最优成本原因拒绝了在南街上的r2请求点。

从表5中可以看出，两辆车的行驶时间分别为33和32 min，小于最大的行驶周期45 min，因此车辆有一定的松弛时间。所有乘客平均等待时间分别为2.3和5.8 min，在乘客可接受的时长范围内。满载率分别为93.7%和100.0%，车辆容量利用率较高。目标函数成本为144.8元，拥堵道路停车惩罚的总成本为28.3元，成本控制较好。

从案例静态需求和动态需求的最终调度结果看，此次调度能够基本满足要求。在采用本文建立的定制公交调度模型和求解算法下，定制公交的成本控制、班次时长、满载率以及拥堵停车惩罚等目标均比较满意，系统的运营调度是比较合理的。

4 结论

本文对响应乘客实时需求的定制公交进行了系统分析和调度研究，在考虑实际的路网拥堵条件和乘客候车时长忍耐程度下，标定了拥堵道路停车惩罚成本函数和乘客时间窗惩罚成本函数，建立了考虑拥堵道路停车惩罚的定制公交路径调度最小成本模型。对实例的求解结果表明，提出的定制公交可以在较短时间内做出合理的决策和车辆调度安排，既能解决乘客的出行需求，又能有效降低道路通行压力。

本文建立的惩罚函数和目标模型的各参数需要结合实际路网和城市经济情况进行修正，在某一个更大的城市区域内对较大数量的乘客需求进行分析计算，可以有效地对车辆进行调度优化和缓解道路拥堵问题。