多区域通勤定制公交线路规划模型及求解算法

陈 汐，王印海，刘剑锋，马晓磊*,1b

(1.北京航空航天大学a.交通科学与工程学院，b.大数据科学与脑机智能高精尖创新中心，北京100191；2.美国华盛顿大学土木和环境工程系，西雅图98195，美国；3.北京城建设计发展集团股份有限公司，北京100071)

0 引 言

近年来，“公交优先”已发展成为应对城市交通问题的主要手段之一，且鼓励构建多元化的公共交通服务模式已经成为城市交通的主流发展方向.在此背景下，定制公交开始在我国投入运营.定制公交是指通过集中整合个体的交通出行需求，为出行起终点、出行时间、服务需求相同或相似的人群提供专门定制的公共交通服务方式[1-2].

定制公交作为一种需求响应式公交服务模式，国内外学者已经对其进行了相关的研究.Liu和Ceder[1]对中国定制公交的发展现状、设计流程及运营模式做出了系统的梳理.线路设计作为定制公交服务设计的重要一环，受到了许多学者的关注.目前研究多以设计优化模型为主，优化目标主要关注乘客的出行和运营成本这两方面.胡郁葱等[2]针对多点对多点运营模式，以运营商成本最小为优化目标构建模型并采用遗传算法求解.Tong等[3]在基于时空可达的定制公交服务模式设计问题的基础上，建立了以最小化不可达乘客数量为目标的规划模型，并采用拉格朗日松弛算法求解.Ma 等[4]以乘客出行成本、运营收入及成本为优化目标建立模型，并设计了遗传算法对定制公交线路方案进行了实证分析.Lyu 等[5]基于乘客的出行选择行为构建了以最大化运营商收益为目标的优化模型，并设计了启发式算法求解.申婵和崔洪军[6]基于可靠性最短路的概念提出了一种定制公交线路优化方法及模型，并设计了禁忌搜索方法进行求解.

综上所述，尽管目前已有研究取得了很多成果，但有以下几个方面依旧值得进一步讨论.首先，乘客出行成本优化方面，在模型构建时应考虑其他出行方式.第二，多数研究中模型为单目标优化模型.实际上，采取多目标优化方法求解Pareto解可以捕获冲突目标之间的变化关系，为运营者提供更多的信息.第三，如何针对通勤这种出行模式的特点构建相应的线路设计模型需进一步讨论.

基于以上考虑，本文提出了一个针对通勤模式的定制公交多目标优化模型，该模型同时考虑了乘客出行成本和定制公交的运营成本.特别针对乘客出行成本，目标函数考虑了乘客选择定制公交的实际出行时间与“最短路时间”之差，这里“最短路”是指出租车服务模式或单点对单点的定制公交运营模式，即两个站点间直达所需时间；并设计了一个两阶段启发式算法求解该模型的Pareto解，最后通过案例验证了模型和方法的有效性.

1 通勤定制公交线路设计模型

1.1 多区域通勤定制公交的运营模式

本文只讨论早高峰通勤定制公交的线路设计问题.通勤者出发地通常为某个小区(居住区)，而目的地为某个工作地点(工作区).因此，通勤定制公交可以视为从居住地区域(多区域)与工作地区域(单区域)之间的线路设计问题.

如图1所示，假设每个居住地区域有若干出发地站点，每个出发地站点为上车站点(不允许下车).工作地区域有若干目的地站点，每个目的地为下车站点(不允许上车).该问题可以描述为：在需求已知的情况下，每一条定制公交线路行车路径中，有若干个上车站点与下车站点.其中，每条线路中各上车站点的目的地必须包含在该线路的下车站点里.且每条线路必须先经过居住区域，再将乘客运送到工作区域.图1描述的情况中包含2条线路(用2辆车运营).

在本文中，每个出行需求p包含4个属性，即出发地o(p)，目的地d(p)，期望出发时间ot(p)，和期望到达时间dt(p).其中乘客上车时间窗满足ω为15～30 min 的缓冲时间参数，且ot(p)+ω ＜dt(p).此外，乘客到达目的地的时间应早于dt(p)以避免迟到；因此，本文研究的问题可以视为PDPTW(Pickup and Delivery Problem with Time-Windows)问题的特殊情形[3].

图1 多区域通勤定制公交运营模式Fig.1 Example of multi-region operation mode for commuting CB

1.2 模型描述

令G=(N,A)为交通网络，N为定制公交备选站点(场站，居住地和工作地)；A为交通网络中的弧，满足A={(i,j):i∈N,j∈N,i≠j}.每个弧(i,j)之间的距离定义为d(i,j)＞0，其中d(i,j)=d(j,i)；车辆在弧(i,j)之间的通行时间定义为T(i,j)＞0.决策变量定义如表1所示.

表1 模型中决策变量含义Table1 Decision variables in the model

模型的假设如下：

(1)出行需求已知，且每个需求p包含乘客的人数为n(p).

(2)若出行需求符合某线路的站点的服务范围，则该需求所对应的乘客会选择该线路出行.

(3)两个站点间的通行时间T(i,j)=d(i,j)v，其中，v为车辆的平均行驶速度(km/h).

(4)场站为虚拟站点.为简化模型，车辆k的出发点b(k)(场站)与第一个上车站点之间，以及最后一个下车站点与车辆k的到达点e(k)(场站)之间的线路成本为0.

1.3 模型建立

在实际运营中，根据出行需求，一个上车站点可能会对应不同的下车站点；相似地，一个下车站点也可能会对应不同的上车站点.因此，需要将上下车站点拆分以使得起终点一一对应[7].经过处理，需求所对应的上车站点集合为H={h1,h2,…,hn}，上车站点所对应的下车站点集合为W={w1,w2,…,wn}.因此，乘客的出行需求点可用集合R=H⋃W表示.

本文的优化目标是兼顾乘客与运营商两方面效益，即最小化乘客出行时间成本和定制公交运营成本两个目标.

(1)乘客的出行成本.

第一个优化目标为最小化乘客的出行成本，包含两部分：第一部分为乘客乘坐定制公交的实际出行时间与“最短路时间”之差，这里“最短路”是指出租车服务模式，即两个站点间直达所需时间.第二部分为乘客的等待时间，这里等待的时间是乘客期望到达时间dt(p)与实际到达目的地时间之差.以上两个指标目的是提升出行效率，减少出行时间的浪费.

首先，令hkt(i)为车辆k在上车站点i接载乘客后的出发时间为

式中：si为站点上下车的服务时间.因此，对于每个需求p，从居住地i[o(p)]到工作地j[d(p)]的出行时间成本指标为

因此，第一个目标函数F1为最小化全体乘客的平均出行时间成本为

(2)运营成本.

第二个优化目标F2为最小化运营车辆数，即使用尽可能少的车辆来服务所有乘客需求，达到降低运营成本的目的.

本文假定定制公交的服务车型相同，即每辆车的载客人数相同.

(3)约束条件.

首先，每个乘客只能由一辆车服务，即

第二，定制公交服务过程中不允许换乘行为，即

式(6)和式(7)表明乘客p被车辆k在上车站点i接载后由同一辆车k送到目的地n+i.

第三，乘客需在dt(p)之前到达目的地.

第四，车辆k应先访问乘客p的居住地再访问工作地.

第五，线路中相邻站点间的通行时间关系应满足

式中：G为一个充分大的数.

第六，定制公交需保证乘客“一人一座”[1].因此，车辆到达站点接载乘客后车内乘客数量应满足：

式中：Lk(i)为车辆k经过站点i后的累计客流，rp(j)为后继站点j的乘客数，C(k)为车型的载客容量.

第七，决策变量取值范围为

2 求解算法

由于多目标优化模型各目标之间会存在冲突，因此求解的目标是找到Pareto 解集[8].然而，由于PDPTW类问题属于典型的NP-hard 问题，且在处理实际问题中规模较大，因此采用启发式算法求解问题是主要的手段之一[3].本文设计了一种两阶段启发式算法求解模型，第一阶段生成初始Pareto 解集；第二阶段采用邻域搜索算子更新Pareto解集.

2.1 生成初始解

首先，本文采用sweep-based算法生成初始线路集[7,9].该算法的主要思路是将出行需求按“多点对单点”的运营模式进行线路设计，具体步骤如下.

Step 1对于同一个时间段dt(p)到达同一个目的地d(p)的乘客，令其出发地集合为lo={l1,l2,…,li,…,ln}.在车辆k从起点b(k)出发之后，从l0中随机选择一个乘客的出行起点li.这样，由车辆k服务的线路可以初始化定义为Vk：b(k)-S1-d(p)-e(k)，其中，S1=li.

Step 2从l0中选择站点lj继续插入到Vk中，选择站点的原则按照与前一个站点的距离大小来进行，即优先选择离前继站点距离最近的站点，并且满足：

式(17)和式(18)表示选择插入的站点li+1要尽可能离目的地越来越近.

Step 3判断新插入的站点lj是否满足约束条件式(8)～式(13).如果满足，将站点放入车辆k所服务的线路Vk之中，并更新线路.更新之后将lj从l0中删除.否则，返回Step 2 直到选择一个可行的站点插入.

Step 4重复Step 2和Step 3直到没有站点可以添加到Vk之中，这样由车辆k运送的线路Vk被确定.

Step 5重复Step 1～Step 4 直至到达d(p)的每个需求都被覆盖，对于每个目的地站点都按该方法进行线路的初始化，这样就得到一个初始的线路集合TR，线路集中每条线路都是多点对单点的运营模式，如图2所示.

图2 多点对单点模式线路示例Fig.2 Example of route for multi-origin to one destination

接下来引入了一个插入算子尝试将线路集中某个线路中的站点分配到其他的线路中，以达到削减车辆数，减少车辆成本的目的.由Pareto 解的定义，式(4)的目标函数中每减少一辆车，就可能出现一个新的Pareto解.因此，经过该算子的操作，得到初始Pareto 解集Ypareto.具体步骤如下，如图3所示.令TR={TR1,TR2,…,TRn}是由sweep-based算法产生的初始线路集合.

Step 1从TR中随机选择一个线路TRi，尝试将TRi中的站点分配到其他线路中.

Step 2从TR{TRi}中再选择一个线路TR*，检测TRi中的目的地是否与TR*中的目的地一样.如果不一致，算子将尝试在TR*中搜索可以插入的位置.

Step 3在TR*中搜索可以插入的位置，将TRi中的站点分配到TR*中.如果TR*中没有可以插入的位置，那么算子返回Step 2继续搜索可以插入的线路.

Step 4重复Step 2和Step 3 直到TRi中的站点全部被分配到其余站点.如果TRi中的站点全部被分配到其余站点，则削减了一个车辆数，更新线路集与Pareto 解集，并从TR中删除TRi和TR*；否则，TR与TRi保持不变.

Step 5重复Step 1～Step 4 直到TR中的线路数(车辆数)不能进一步减少，这样得到新的线路集合.

图3 插入算子操作步骤Fig.3 Relocation operator procedure

2.2 更新Pareto解集

第二阶段采用邻域搜索方法进一步改进初始解[6].本文设计了两种邻域搜索算子对初始Pareto解集进行更新.

(1)Relocate算子.

该算子随机选择某Pareto 解对应线路集中的一条线路，并在该线路中随机选择两个站点并置换位置，如图4所示.

(2)Swap算子.

该算子随机选择某个Pareto 解中的对应线路集中的两条线路，并交换两个线路中的目的地站点及其对应的出发地站点，如图5所示.

图4 Relocate 算子示例Fig.4 Example of relocate operator

综上所述，本文提出的启发式算法的操作步骤如表2所示.

图5 Swap 算子示例Fig.5 Example of swap operator

表2 两阶段启发式算法步骤Table2 Overview of two-stage heuristic

3 案例分析

本文通过几组算例验证模型和算法的有效性.论文中其他参数如下.车辆在每个停靠站点的服务时间按以下方式计算.首先，对于每个上车站点，服务时间[7](单位：s)为

式中：ni为在站点i服务的乘客总数.类似地，对于每个下车站点，服务时间为

假定车型载客量为45人/辆；定制公交的行驶速度为40 km/h[1]；出租车行驶速度为45 km/h[1].

本文采用了三种算例，每种算例有不同的出行需求.图6 给出了其中一个算例的信息，该研究区域有两个居住地区域和一个工作地区域，每个区域有若干个上车或下车站点[7].该算例中包含175个上车站点(居住地)，5个下车站点(工作地).本文案例中乘客的期望出发时间在集中在区间[6:30,10:30]，期望到达时间集中在区间[07:00,11:00].

图6 算例示意图Fig.6 Benchmark instance

表3给出了3组算例的基本信息、Pareto解中最优乘客出行成本和最小车辆数两种线路方案集所对应的目标函数值，以及所有Pareto 解的平均值.结果表明，随着车辆数的增加乘客的出行成本会显著降低，这是由于车辆数的增加会减少线路中间站点的个数从而减少出行成本.图7给出了案例1中所得到的Pareto解的前沿面，也代表了不同的线路方案集.根据Pareto解的定义[8]，每个解均处于非支配地位，每个解所对应的目标函数值不同，即每个方案侧重于不同的优化目的.因此，本文所提出的算法为决策者提供了不同的可行方案，可根据实际情况灵活选择.

本文进一步分析了乘客选择定制公交所产生的出行成本，并与出租车进行了比较.比较的指标包括出行时间，票价(出租车为车费)与总成本.这里的总成本为票价成本与时间价值成本之和.其中定制公交和出租车票价计算参照文献[1].时间价值成本根据年人均收入和年平均工作时间计算[4]，根据已有资料，人均时间价值成本按0.85元/min计算.因此，本文将乘客的出行时间和提前到达的等待时间换算为时间价值成本.

图7 算例Pareto 解(前沿面)Fig.7 Pareto solutions of benchmark problem

表3 模型的Pareto 解Table3 Model results with Pareto solutions

对于每个算例，计算了全部Pareto解中每个乘客出行需求的出行时间，票价与总成本，并对所有乘客的计算结果求平均值.图8给出了每组案例中乘客选择定制公交与出租车所产生的出行成本的比较结果.相比于出租车，选择定制公交会多出30%左右的出行时间成本，但是费用可以节省70%左右，并且总成本上定制公交也具有一定的优势.因此，可以看出，定制公交可作为公共交通服务模式中一种很好的补充形式，为出行者提供更多的选择.

4 结 论

本文提出了一种针对通勤定制公交的线路设计方法，以多区域到单区域的定制公交运营模式为基础，构建了多目标线路规划模型，综合考虑了乘客出行成本与运营成本两个方面.同时设计启发式算法求解该模型并利用案例进行了验证，并给出了定制公交不同线路中乘客的出行成本，并与出租车进行对比，结果体现了定制公交可作为多元化公共交通服务模式中的一种补充形式，在未来研究中可将模型推广至其他类型的定制公交，以期为定制公交的线路设计方法提供相关理论依据.