基于时空聚类的定制公交需求响应机制

薛浩楠，王 佳

(1. 长沙理工大学 交通运输工程学院，湖南 长沙 410114；2. 新疆交通规划勘察设计研究院，新疆 乌鲁木齐 830000)

0 引言

为了迎合乘客差异化、高品质的出行需求，客运市场出现了诸如定制公交、预约出租车、定制商务巴士等新型城市客运模式。定制公交是这种新型模式的典型代表，它根据乘客的个性化出行需求，为目的地和时间相同或相近的人群提供量身定制的出行服务，是介于常规公交与出租车之间的准公共产品[1]。

目前定制公交的研究是热点问题，胡列格、安桐等针对定制公交合乘站点的合理布局问题设计了基于密度的孤立点检测算法[2]。马继辉、王飞等提出利用k-means聚类算法规划定制公交站点，并建立了定制公交线路规划模型[3]。阮冠轩、靳文舟等研究了如何确认需求响应式公交乘客出行的中心点，并构建了接驳公交的调度模型用于检验站点和孤立点的确认方法[4]。何民、李沐轩等考虑定制公交的可靠性和舒适性，提出了一种基于乘客出行需求的定制公交线路设计模型[5]。Rahul Nair等基于乘客的出行需求数据构建了平衡网络设计模型，该模型能够实现站点位置、车辆及站点容量的最佳配置，从而使得效益最大化[6]。Li Z和Song R构建了基于乘客的出行时间窗的定制公交线路优化模型，并以小规模网络为例进行分析，结果表明该模型对定制公交的运营有一定的指导意义[7]。

综上，现在的研究侧重于定制公交的站点布局和线路规划，对需求响应机制的研究相对匮乏，而合理的需求响应机制是整个定制公交系统成功运营的重要保证。从各城市的具体实施情况来看，对于乘客需求的响应往往是依靠经验确定，存在着主观性，缺少相关的定量研究[8-10]。

现有关于需求响应机制的研究是对乘客出行需求数据进行线下的调查分析，缺乏乘客与运营者的信息交互[11-12]。随着互联网技术的高速发展，定制公交服务可以根据乘客在平台上发布信息获得乘车需求[13-14]。其他一些相关研究是利用k-means等基于划分的聚类算法从乘客出行的空间维度进行分析，未考虑乘客出行的时间维度，也没有考虑基于划分的聚类算法易受孤立点的影响，需要提前确定类簇个数，较难处理非球形簇数据等缺陷[15-16]。

目前为止，定制公交需求响应机制主要分为响应全部需求和有选择地响应部分需求两种类型。若响应全部需求，由于采集的预约需求点在时空上分散，往往造成运输的不经济；而在响应部分需求的机制中，主要是根据经验来判断是否响应某个需求，会出现因满足部分孤立的特殊的出行需求而引发上座率低的问题，降低了定制公交的吸引力[17-18]。较为理想的响应机制是充分考虑乘客的实际出行需求，为大众化的定制需求提供服务，适当剔除孤立的出行需求。因此，有必要研究一种定量的基于时空聚类的定制公交需求响应机制，通过分析乘客出行数据的时空特性，选用合适的聚类算法得到时空趋同的定制需求。

1 响应机制的构建思路

运输企业利用互联网平台发布和采集定制公交需求，将采集到的信息称为预约需求点。若预约需求点在时空上集中，运输企业会为之提供量身定制的出行服务，这称之为需求响应。确定是否为预约需求点提供出行服务的响应机制至关重要。

该机制一般遵循以下原则：充分权衡运输企业与乘客之间的利益，尽量响应出行时间、地点集中，乘客人数较多的“大众化需求”，适当剔除出行时间、地点分散，乘客人数较少的“特殊需求”。

根据上述原则，针对预约需求点的时空分布特性，对预约需求点进行分步响应，采取“先时间维度，后空间维度”两步来实现，每个步骤均通过预响应、再响应来剔除时空分散的预约需求点，如图1所示。时间指预约需求点的出行时间，包括出发时间段和到达时间段；空间指预约需求点的空间位置，包括出发地位置和到达地位置。具体步骤如下：

(1)预约需求点的采集

预约需求点通过网络平台获取，采集的预约需求点主要包含时间、空间和人数等基本属性，它们作为判断是否响应的依据。

(2)预约需求点时间维度的响应

预约需求点时间维度的响应包括预响应和再响应，其中时间维度的预响应是将出发时间段接近的预约需求点保留。常用的层次聚类算法通常用于空间聚类[19]，本研究提出基于时间度量的层次聚类算法，用时间来度量两个类簇之间的距离，将距离较小的两个类簇进行合并。时间维度的再响应是将出发时间段和到达时间段同时存在交集且人数较多的预约需求点保留，经时间维度的响应后得到空间维度响应的备选集合。

(3)预约需求点空间维度的响应

预约需求点空间维度的响应包括预响应和再响应，其中空间维度的预响应是将到达地位置接近的预约需求点保留，空间维度的再响应是将出发地位置接近的预约需求点保留，剔除出发地位置相距较远的预约需求点。由于乘客出行需求数据的空间分布较为冗杂，常用的k-means等基于划分的聚类算法较难处理非球形簇的数据，而DBSCAN(density-based spatial clustering of application with noise)算法能够较好地识别孤立点，不需要提前确定类簇个数，能够处理任意形状类簇的数据，规避了k-means等传统聚类算法的缺陷[20]。因此本研究采用DBSCAN聚类算法实现空间维度的再响应。

图1 响应机制的构建流程Fig.1 Flowchart of constructing response mechanism

2 预约需求点的采集与时间维度的响应

2.1 预约需求点的采集

运输企业利用互联网平台采集到的预约需求点主要包含5个基本属性：出发地位置、出发时间段、到达地位置、到达时间段和乘客人数，如表1所示。

表1 预约需求点的基本属性Tab.1 Basic attributes of reserved demand

表1中，ph为第h个预约需求点；(xph,yph)为第h个预约需求点的出发地位置；(eph,lph)为第h个预约需求点的出发时间段；(x′ph,y′ph)为第h个预约需求点的到达地位置；(e′ph,l′ph)为第h个预约需求点的到达时间段；dph为第h个预约需求点的乘客人数。

2.2 时间维度的预响应

时间维度预响应的主要思路是首先求解预约需求点的出发时间段中值，并按中值进行升序排列，形成新的出发时间序列，然后采用基于时间度量的层次聚类算法形成若干个时间跨度，最后统计每个时间跨度内的预约需求点人数，剔除人数较少的孤立点。具体如下：

(1)

式中，eph为升序排列后第h个预约需求点的最早出发时间；lph为升序排列后第h个预约需求点的最晚出发时间。

(2)针对预约需求点的出发时间段属性，本研究对传统层次聚类算法进行改进，提出基于时间度量的层次聚类算法，将距离较小的两个类簇进行合并，直到满足设定的终止条件时算法结束，具体步骤如下：

步骤1：对升序排列后的出发时间段中值进行搜索，筛选得到中值相同的预约需求点。

步骤2：采用基于时间度量的层次聚类算法进行分析，当各个时间跨度的方差之和最小，见式(2)，并且每个类簇的时间跨度不超过τ时，可归为一个类簇，第h个时间跨度不超过τ见式(3)。

(2)

(3)

步骤3：统计各个时间跨度内的预约需求点人数，当时间跨度内的人数不小于φ时，对该时间跨度内的预约需求点进行响应，见式(4)。

∑dTh≥φ,

(4)

式中，∑dTh为第h个时间跨度内的乘客人数；φ为保留预约需求点的最少乘客人数。

通过对预约需求点时间维度的预响应，得到若干个出发时间段接近的预约需求点，作为时间维度再响应的备选集合。

2.3 时间维度的再响应

时间维度再响应的主要思路是从预约需求点的出发时间段和到达时间段属性入手，若预约需求点的出发和到达时间段同时存在交集，即当同时满足式(5)和式(6)时，将其归为同一个可能响应的类A，当ph∈A时计算类A中的人数，如果满足式(7)则将其保留。

[eph,lph]∩[ep′h,lp′h]≠∅，

(5)

[e′ph,l′ph]∩[e′ph′,l′ph′]≠∅,

(6)

∑Adph≥φ,

(7)

式中，[eph,lph]、[eph′,lph′]为任意两个预约需求点的出发时间段；[e′ph,l′ph]、[e′ph′,l′ph′]为任意两个预约需求点的到达时间段；∑Adph为同一个可能响应的类A中的乘客人数；φ为保留预约需求点的最少乘客人数。

通过对预约需求点时间维度的再响应，得到若干个出行时间集中的预约需求点，作为空间维度响应的备选集合。

3 空间维度的响应

3.1 空间维度的预响应

空间维度预响应的主要思路是从预约需求点的到达地位置属性入手，若两个预约需求点到达地位置之间的距离满足设定的条件值，即当式(8)成立时将其保留。

sph,h′≤ω,

(8)

式中，sph,h′为任意两个预约需求点到达地位置之间的距离；ω为满足到达地位置接近的条件值。

通过对预约需求点空间维度的预响应，得到若干个出行时间集中、到达地位置趋同的预约需求点，作为空间维度再响应的备选集合。

3.2 空间维度的再响应

通过时间维度的响应和空间维度的预响应实现了出行时间接近、目的地趋同，但不能保证出发地位置的接近。本研究采用DBSCAN聚类算法进行空间维度的再响应，主要思路是从预约需求点的出发地位置属性入手，筛选得到出发地位置相对集中的预约需求点，同时剔除出发地位置相对分散且人数少的预约需求点，通过空间维度的再响应得到若干个时空趋同的预约需求点，如图2所示。

图2 空间维度的再响应示意图Fig.2 Schematic diagrams of re-response in spatial dimension

DBSCAN聚类算法的主要思想是从任意一个未被访问的预约需求点开始，计算每个预约需求点的ε邻域，通过密度可达的概念将预约需求点聚类同时标记孤立点，直到所有预约需求点都被访问时算法终止。其中算法的两个输入参数，ε邻域具体指乘客从居住地或工作地步行至上车地点的距离;mindph具体指定制公交上车地点覆盖范围内包含的最少乘客数量。

(1)基本定义

结合DBSCAN聚类算法的基本思想和定制公交的特征，给出以下5个基本定义：

定义1：预约需求点ph的ε邻域。预约需求点∀ph∈p的ε邻域ε(ph)定义为以ph为圆心，ε邻域形成的空间范围内包含的预约需求点的集合，即ε(ph)={qh∈p|s(ph,qh)≤ε}，其中s(ph,qh)表示p中预约需求点ph和qh之间的距离。

定义2：核心预约需求点。给定参数邻域ε和聚类最少包含的乘客数量mindph，对于预约需求点ph，若ph的ε邻域形成的空间范围内包含的预约需求点的乘客人数满足∑εdph≥mindph，则称ph为核心预约需求点。

定义3：预约需求点的密度直达。给定参数ε和mindph，对于预约需求点ph,qh∈p，如果满足ph∈ε(qh)且∑εdph≥mindph，则称ph与qh密度直达。

定义4：预约需求点的密度可达。给定参数ε和mindph，对于预约需求点ph,qh∈p，如果存在预约需求点序列p1,p2,…,pn,q1,q2,…,qn∈p，其中ph=p1，qh=ph，若ph与ph-1密度直达，则称ph与qh密度可达。

图3 DBSCAN聚类算法流程Fig.3 Flowchart of DBSCAN clustering algorithm

定义5：预约需求点的密度相连。给定参数ε和mindph，对于预约需求点ph,qh∈p，若存在一个预约需求点oh与ph，qh，都是密度可达，则称ph与qh密度相连。

(2)算法步骤

预约需求点空间维度再响应的方法采用DBSCAN聚类算法，具体步骤如下：

输入：预约需求点集合p，邻域ε，能够聚为一类的乘客人数下限值mindph。

输出：基于密度的类集合。

步骤1：初始化未被访问的预约需求点集合Pw=p，类序号k=0，类集合Pcl=∅。

步骤2：根据类序号设置并更新其对应的聚类参数邻域ε和能够聚为一类的乘客人数下限值mindph。

步骤3：任意选择Pw中的一个预约需求点ph，若ph不是核心预约需求点，则执行步骤4；若ph是核心预约需求点，则执行步骤5。

步骤4：将ph标记为孤立点，并从集合Pw中删除。

步骤5：令k=k+1，确定p中所有与ph密度可达的预约需求点，并把ph及其密度可达的预约需求点划分到类Pcl中，并将Pcl中的预约需求点从集合Pw中删除。

步骤6：若Pw=∅，则输出类的集合Pcl={P1,P2,…,Pk}，否则转到步骤3。

步骤7：若该类内预约需求点的人数∑εdph

4 算例分析

4.1 数据准备

模拟采集了54个预约需求点，共包含乘客143人，设研究时段为7:00—9:00，随机分布在方形区域内。各聚类参数值先根据经验设定，τ为6 min，φ为4人，ω为700 m，ε为200 m，mindph为8人，再依据聚类结果进行调整，模拟的预约需求点信息如表2所示。

表2 预约需求点信息Tab.2 Information of reserved demand stations

4.2 根据参数经验值的需求响应

对于模拟的54个预约需求点，首先按照设定的参数经验值进行响应，如下：

(1)时间维度的预响应。根据式(1)，求解54个预约需求点的出发时间段中值，并进行升序排序，筛选得到出发时间段中值相同的20个预约需求点；对剩余34个预约需求点采用基于时间度量的层次聚类算法，剔除不满足式(2)和式(3)的p2和p33；统计各个时间跨度内的人数，剔除不满足式(4)的p1和p9。通过时间维度的预响应共剔除4个出发时间段相对孤立的预约需求点，得到50个出发时间段相同或相近的预约需求点。

(2)时间维度的再响应。根据式(5)和式(6)，判断各个预约需求点的出发和到达时间段是否同时存在交集，若存在则将其归为同一类，剔除不存在交集的p17，p27和p47；根据式(7)计算同一类内的乘客人数，剔除不满足式(7)的p36和p42。通过时间维度的再响应共剔除5个出行时间相差较大预约需求点，得到45个出行时间接近预约需求点。

(3)空间维度的预响应。根据式(8)，计算45个预约需求点到达地位置之间的距离，剔除不满足式(8)的p10，p14，p22和p49。通过空间维度的预响应共剔除4个到达地位置相对分散的预约需求点，得到41个到达地位置接近的预约需求点。

(4)空间维度的再响应。采用DBSCAN聚类算法判断41个预约需求点是否为核心预约需求点，若是则将其保留，其中p7，p11，p13和p51不是核心预约需求点，将其剔除。通过空间维度的再响应共剔除4个出发地位置相对分散的预约需求点，得到37个时空趋同的预约需求点。

根据设定的聚类参数经验值共响应37个预约需求点，包含107人，满足了69%预约需求点和75%乘客的出行请求，剔除的预约需求较多，未能较好地实现尽量响应大众化需求、适当剔除特殊需求的响应原则。根据聚类参数经验值的响应结果如表3所示。

表3 根据聚类参数经验值的响应结果Tab.3 Response result based on empirical clustering parameters

4.3 响应结果的优化

通过调整各聚类参数对响应结果进行优化，设定保留时间跨度的最短时间τ从2 min增加至9 min，保留预约需求点的最少乘客人数φ从1人增加至8人，满足到达地位置接近的条件值ω从400 m增大至1 100 m，DBSCAN聚类算法的输入参数邻域ε从50 m增大到500 m，能够聚为一类的乘客人数下限值mindph从2人增加至11人。分别计算在其他聚类参数按照经验值设定的前提下，各个参数变化后的响应结果，如表4～表8所示。

表4 τ变化时的响应结果 Tab.4 Response result varying with τ

表5 φ变化时的响应结果Tab.5 Response result varying with φ

表6 ω变化时的响应结果Tab.6 Response result varying with ω

表7 ε变化时的响应结果Tab.7 Response result varying with ε

表8 mindph变化时的响应结果Tab.8 Response result varying with mindph

由表4可知：在其他聚类参数按经验值设定的前提下，τ从2 min增加至9 min时，得到响应的预约需求点个数和乘客人数逐渐减少。当τ小于3 min时，不再剔除预约需求点，此时，τ的减小将不会再对响应结果造成影响，预约需求点和乘客的最大响应比例分别为76%和80%。随着τ的增大，研究时段内的类个数减少，但每个类中的乘客人数增加，运输企业可考虑在降低发车频率的同时选用较大的车型。

由表5可知：在其他聚类参数按经验值设定的前提下，φ从1人增加至8人时，得到响应的预约需求点个数和乘客人数逐渐减少。当φ小于2人时，不再剔除预约需求点，此时，φ的减小将不会再对响应结果造成影响，预约需求点和乘客的最大响应比例分别为78%和80%。随着φ的增大存在部分人数较多却因出行时间段较为孤立而被剔除的出行需求，运输企业可针对这些需求单独规划线路，从而响应更多的预约需求点。

由表6可知：在其他聚类参数按经验值设定的前提下，ω从400 m增大至1 100 m时，得到响应的预约需求点个数和乘客人数逐渐增加。当ω大于1 000 m 时，不再剔除预约需求点，此时，ω的增大将不会再对响应结果造成影响，预约需求点和乘客的最大响应比例分别为76%和82%。随着ω的减小，预约需求点的响应比例降低，部分出行需求因空间位置较为孤立而被剔除，使得这部分乘客前往站点乘车的步行时间会相应增加。

由表7可知：在其他聚类参数按经验值设定的前提下，ε从50 m增大到500 m时，得到响应的预约需求点个数和乘客人数逐渐增加。当ε大于400 m时不再剔除预约需求点，此时，ε的增大将不会再对响应结果造成影响，预约需求点和乘客的最大响应比例分别为76%和83%。随着ε的减小，预约需求点被划分的类个数增加、空间范围缩小，使得乘客在站点的等车时间增加。

由表8可知：在其他聚类参数按经验值设定的前提下，mindph从2人增加至11人时，得到响应的预约需求点个数和乘客人数逐渐减少。当mindph小于4人时不再剔除预约需求点，此时，mindph的减小将不会再对响应结果造成影响，预约需求点和乘客的最大响应比例分别为76%和83%。随着mindph的增大，预约需求点被划分的类个数减少、类中的乘客人数增加，运输企业可考虑选用较大的服务车辆。

综合表4～表8可知：预约需求点的最大响应比例为78%，乘客的最大响应比例为83%。为满足响应机制的构建原则，设定预约需求点和乘客的响应比例不小于75%和80%，得到其他聚类参数按照经验值设定的前提下各参数的设置条件，如表9所示。

表9 参数设置条件Tab.9 Parameter setting conditions

由表9可知：在其他聚类参数按经验值设定的前提下，τ不大于3 min，φ不大于2人，ω不小于1 000 m，ε不小于400 m以及mindph不大于4人时，预约需求点和乘客的响应比例不小于75%和80%，满足尽量响应大众化定制需求、适当剔除特殊需求的响应原则。

5 结论

(1)定制公交的预约需求在时空范围上分散，若对其全部响应，往往会造成运输的不经济，若对其响应过少，则会降低定制公交的吸引力，因此本文通过对预约需求进行时空范围的聚类来实现定制公交需求响应机制。

(2)按照尽量响应“大众化需求”和适当剔除“特殊需求”的原则，采取“先时间维度，后空间维度”的方式，分别采用基于时间度量的层次聚类算法和DBSCAN聚类算法筛选预约需求点，算例分析结果表明该机制能够通过参数的适当调整满足响应机制的构建原则，对定制公交预约需求的响应具有良好的适用性，可为运输企业开通定制公交线路提供决策依据，对推动定制公交的实际应用有一定的现实意义。

(3)在对定制公交需求响应机制的研究是在理想路网条件下进行的，未考虑实际道路条件能否满足定制公交的需求响应，该因素将在未来的研究中进一步讨论。在算例分析中给出的聚类参数经验值存在一定的主观性，在后续的研究中可以针对参数设置进行进一步优化，从而得到最优的结果。