温 冬 张萌萌

（山东交通学院交通与物流工程学院 济南250357）

0 引 言

随着城市化进程的加快，人们的生活节奏逐渐加快，乘坐公交出行成为了人们的生活常态，如何让公交出行变的更加的舒适与高效，是目前各大公交公司所面临的一大挑战，因此，能够为乘客提供1人1座，直达出行服务的定制公交进入到人们的生活，如何设置定制公交的运行线路及站点使其能更好的服务乘客成为了目前公交领域的研究热点。

1998年Harms等[1]在报告中介绍了瑞士2个共享汽车合作社的出现和专业化过程。随后国内外的学者开始进行定制公交相关的研究。与国内相比国外对此方面的研究相对较早，例如，国外的需求响应式公交[2-3]及灵活性公交系统[4-5]等都是定制公交的原型。随着大数据时代的到来，研究人员分别从公交以及出租车GPS定位数据、IC卡刷卡数据等多源数据[6-9]入手对公交的服务能力、人们的出行行为以及市场需求进行了研究分析。目前对于定制公交的研究可以分为线路设计与调度优化2个部分，对于公交线路设计的研究，杨敬锋等[10]从空间角度出发提出了定制公交出行热力图分析模型的构建方法；在公交线路构建与优化方面，李莎[11]综合考虑乘客与公交企业双方的利益，提出了1种基于备选线路集组合生成的方法来进行定制公交线网优化的设计；乘客的出行意愿及出行方式也影响着定制公交线路的布设与优化，靳文舟等[12]提出了1种基于小波神经网络的定制公交目标乘客出行意愿预测模型，以此来对乘客选择哪种交通方式出行进行预测；国内外学者们分别以不同的目标构建了不同的优化函数，通过各种启发式算法对模型进行求解，Li Wenyong等[13]根据最小费用最大流和Dijkstra算法，建立了站点规划的0-1模型，在保证站点数及载客量的约束下，让线路的距离最短以及服务率最高；雷永巍等[14]以需求服务率最大及费用最小为优化目标，通过蚁群算法对所建立的动态网络调度模型进行了求解；对于公交调度的研究，李颖[15]分别从人员条件、车辆条件及道路条件研究，对定制公交的运行规则、预约响应规则、车辆的发车与停车规则进行研究，建立了定制公交的站点规划模型及车辆的静态预约与动态预约调度模型；陶浪等[16]以乘客的出行时间最短及车辆油耗最低作为目标函数，并通过遗传算法对函数进行求解，得到最终的公交线路方案；王健等[17]研究了带时间窗约束的定制公交线路调度方法，以总公交车运营里程最小为目标，以公交站点及公交容量为约束建立公交车调度优化模型，最后通过遗传算法及贪心算法对模型进行求解，找到最优的公交线路方案；张宇宁等[18]以公交运营成本最小为目标建立了线路规划模型，通过lingo软件对模型进行求解，并以虚拟乘客数据进行了案例分析验证了模型的有效性；陈汐等[19]以乘客出行成本及车辆运营成本最小为优化目标，构建了多区域运营模式的通勤定制公交线路规划模型，并通过2阶段启发式算法对构建的模型进行了求解。

在定制公交线路规划与模型构建方面，国内外研究学者进行了较为全面的研究，针对定制公交需求时空分布离散的情况，研究人员采用聚类的方式进行孤立点分析，该方法对孤立的散点有较好效果，但是对于孤立的散点簇效果不好，且只能对点的空间分布进行分析，并未进行时间层面的分析，在线路模型的构建研究中没有考虑出行者到达离开合乘站点及上下车的时间花费。针对上述存在的问题本文利用ArcGis对需求点进行渔网与核密度分析，找出热点时段与热点区域，能够方便快捷的在时空层面对孤立点及孤立点簇进行剔除。通过聚类分析得到了合成站点以及上车与下车2类交通小区，在优化模型构建方面本文考虑了乘客从需求点到目的地的时间花费，以乘客的出行时间作为约束对线路的发车时间进行优化，本文求解得到的线路方案在保证整体服务率的基础上，也很好的保证了每条线路的满载率，使得到的出行线路能够很好的满足公交公司与乘客的利益，让乘客的出行变得更加的高效快捷。

1 出行需求时空分析

1.1 需求热点区域识别

定制公交出行需求是企业通过网络向乘客征集的，需求空间分布离散，在进行线路设计时要对需求进行筛选以此排除异常数据及时间空间偏差大的需求，找到可服务的出行需求，本文提出通过渔网与核密度分析的方式找到出行需求的热点时段与热点区域，最后将对应区域的出行需求进行提取，实现数据的筛选。

定制公交需求数据包括乘客的上车点（名称及经纬度）、下车点（名称及经纬度）、上车时间、下车时间等属性要素。根据研究区域的空间范围基于Gis构建能够覆盖整个区域的渔网图，网格的大小根据研究的精度，设置为边长为L的正方形网格。通过将构建的渔网与需求点进行空间连接得到每个网格区域的出行热度。

需求点核密度分析用于计算栅格像元周围点要素的密度，认为每1个点上都覆盖着1个平滑曲面，曲面最中心的位置值最高，随着离中心的距离增大曲面的值逐渐变小，当达到搜索半径的距离时值为零，曲面叠加位置的值为曲面对应位置值的权重之和。

式中：density为对应位置的核密度；radius为密度搜索的最大半径距离；poph为需求点对应的重要度；disth为需求点h与所求密度位置点的距离。

根据公交站点的辐射范围，调整密度搜索的最大半径。对需求的上车与下车点进行核密度分析，通过将密度分析与渔网分析的结果进行对比来判断热点区域识别的准确性。

1.2 需求点聚类分析

对渔网分析后提取出的需求数据进行线路设计，需要为乘车需求设置相应的合乘站点以及乘车小区，合乘站点的选取要能够满足人们所能接受的最远出行距离，因此需要对需求点进行聚类分析。

本文采用层次聚类与K-means聚类相结合的方式，对需求数据进行聚类分析，避免了层次聚类与K-means聚类所分别存在的聚类缺陷。

1）层次聚类。通过计算需求点之间的欧式距离将聚类结果展示为1棵有层次的嵌套聚类树，每1层都对应着1个距离标准。

2）K-means聚类。要随机的在需求点中选k个点作为聚类点，通过欧式距离进行类的判别，通过均值更新聚类中心反复迭代，得到最终的分类结果。

首先，通过层次聚类得到各个需求点与距离的聚类树，从而找到对应距离下需求点被分的类别数；然后，按照得到的类别数进行K-means聚类，从而得到需求点的最终类别。需求点通过上述聚类操作后得到对应的合乘站点，再将得到的合乘站点按照此方法再次进行聚类得到对应的乘车区域类别。假设定制公交每个站点的辐射距离为f，交通小区的辐射半径为r，通过聚类，将需求点聚类得到P个聚类中心站点与Z个服务交通小区。

2 时空分层优化模型构建

优化模型的构建分为2个部分：①空间优化模型，以乘客的出行时间作为目标函数，以线路长度、公交容量作为约束条件，进行线路构建；②时间优化模型，以乘客出行总延误作为优化目标函数，以乘客预约的上车与下车时间作为约束，对线路的发车时间进行调整，从而得到最终的线路方案。

进行空间优化，构建的空间优化模型见式（2）～（4）。

式中：ni为站点i的上车或下车人数；t上车或下车为单个乘客上车或者下车所消耗的时间，s/人；lsi，ljx分别为每1个乘客上车需求点s到达其上车的合成站点i的距离，m，以及每1个乘客下车合成点j到达对应下车目的地x的距离，m；g，p分别为上车人数与下车人数；v乘客为乘客的行走速度，m/s。第一层优化的目标函数见式（4）。

本层目标函数中，首先，从公交公司的角度考虑了线路运行的时间花费U1；其次，从乘客的角度出发考虑了每1个乘客的上下车时间花费及每1个乘客从需求站点到合乘站点、从合成站点到目的地的时间花费U2；最后，将2类时间花费求和得到最终的优化目标U。

模型结合每个乘客的发起点、需求点与合乘站点的空间位置，考虑了乘客到达与离开站点的时间以及每个站点乘客的上下车的时间，结合本文设置的约束条件，使得求解得到的公交线路更具人性化。

所构建的空间优化模型式（2）～（3）满足以下约束条件。

2）定制公交线路长度应小于等于线路中最远OD点对距离的1.4倍，满足公交线路的非直线系数为1.4，即

式中：lk为线路k的长度为线路中最远OD点对i和j之间的距离。

3）所有的站点都要有线路通过，即要满足

式中：ki，kj分别为第k条线路的上车点跟下车点；N为上车区域跟下车区域的站点总数。

4）站点的访问顺序，即车辆要先访问需求OD的上车站点再访问其下车站点，即

式中：index(i)，index(j)分别为需求OD的上车站点i的索引与下车站点j的索引。

5）若线路中包含某个OD点对的上车点，那么其必须包含其对应的下车点，即i，j∈Ak，其中i和j分别为OD点对对应的上车与下车站点，Ak为OD点对所在的线路k的站点集合。

6）每条线路的上车人数等于下车人数，ci=cj。

7）每1个上车区域跟所有的下车区域进行1次匹配。

在进行第二层时间优化函数T的构建时考虑了乘客的出行时间窗，以乘客预约的上下车时间及公交线路的到达时间作为约束条件，以线路乘客的总延误最小作为优化目标，来进行公交发车时间的优化，构建的目标函数见式（5）。

通过上述构建的双层优化模型可以得到区域间的公交线路、发车时间、线路里程，以及载客容量等线路信息。

3 模型求解算法

针对2节构建的分层优化模型，采用遗传算法对模型进行求解。

3.1 线路算法流程

1）将上车站点与下车站点按照设定的辐射距离进行聚类，将上车站点划分为Y个区域，下车站点划分为X个区域，进行区域与区域间的线路设计。

2）将上车需求进行存储，每个上车需求包括的字段有：上车站点与下车站点编号、上车区域与下车区域编号、预期的上车与下车时。

3）按照区域的编号，提取上车区域跟下车区域（进行区域间的线路设计）。

4）按照上车区域各个站点乘客需求的上车时间对乘客分类；按照设定的时段a对需求点进行再分类。

5）寻找出每个阶段的上车需求分别对应的上车点，对这些点进行应用遗传算法进行线路的求解。

6）1个时间段结束后自动跳转到下1个时间段，然后重复5）。

7）1对上下车区域求解全部结束后，再进行另外区域的线路求解，返回4）～6）。

8）当所有的上车与下车区域全部匹配完成以后，结束第1层优化模型。

9）根据时间调节函数对每个区域对之间形成的线路进行时间调节。

算法的计算流程见图1。

图1 算法流程Fig.1 Algorithm flow

3.2 遗传算法构造与求解

遗传算法应用在某个上下车区域对的不同的时间段中，以其中1对上下车区域为例，对遗传算法的具体的运算流程进行说明。

采用自然数编码的规则，1个站点作为1个基因，不同站点的组合构成1条染色体，过程如下。

1）以生成的随机线路的第1个站点作为线路起点，其下车点作为终点，1个上车站点都是对应的多个下车站点，其所对应的下车站点的排列顺序按照离上车点距离的由近到远进行排列。

2）容量约束，看上车点的乘客数量是否超出车辆的容量，若超出容量则在上车点后加0，若满足条件则去查看其是否满足非直线系数的约束，若不满足就在起点后加0，若满足条件就去检验线路的第2个起点。

3）同样当线路中有2个起点后，首先要去验证加上第2个起点之后，第1个起点的各个约束条件是否还能满足，若不满足，就在第1个起点后面加0，单独的作为1条线路，将第2个上车点作为新的起点去重复1）、2）、3）；若满足条件则验证加入的起点2是否满足2个约束条件的限制。

4）对生成的每1个排列方案都进行约束条件的检查，使得每1个组合方案都是可行解。

5）最后将每1组的染色体长度按照每组最长的染色体补全，具体方法就是在短的染色体长度后面加0，让所有染色体长度相等。

种群选择的规则如下。

1）根据建立的优化函数U，计算每个个体的函数值。

2）计算种群中每个个体遗传到下1代中的概率。

3）计算累计频率。

4）根据生成随机数选择对应个体。

交叉规则：按照自然数编码的规则，将种群中的个体随机的两两配对，设置好对应的交叉概率。利用随机函数产生每条染色体中参与交叉的基因的个数：[1，染色体长度/2]，再利用随机函数产生参与交叉的基因的索引位置。

变异规则：同交叉操作相似，随机确定参与变异的基因个数与位置索引，将选到的基因进行随机排序后填充到对应染色体空缺的位置。

3.3 线路发车时间优化

步骤1。输入第一层算法得到的公交线路方案。

步骤2。根据每个站点之间的距离以及公交车的运行速度得到每个站点之间的时间长度。

步骤3。以线路所处发车时段的起点为第1种发车时间，并以tmin为间隔枚举得到所处时段内的所有的发车方案。

步骤4。依次计算每种发车方案下线路的时间调节函数的值，取最小值对应的发车时间为线路的最终发车时间。

4 案例分析

以济南市定制公交的需求数据为例，按照本文提出的时空双层优化方案进行定制公交站点以及线路的设计，对比了以线路里程作为目标函数的算法求解得到的线路，以及对本文算法得到的线路方案进行评价。

4.1 方案设计

通过网络收集得到的人们出行需求数据见表1。

表1 定制公交需求数据Tab.1 Demand data of customized buses

获得的需求数据包括乘客的公交卡账户、上车点与下车点及其经纬度坐标、期望的上车与下车时间。对需求点进行渔网与核密度分析，得到上车与下车的热点区域，进行数据的初步筛选，对应得到核密度与渔网分析的结果见图2～4。

图2 需求点核密度Fig.2 Kernel density of demand points

图3 上车需求渔网图Fig.3 Hot spot map of boarding demand

通过对需求点进行核密度分析与渔网分析验证了所选的热点区域的有效性，为接下来的工作做好准备。

图4 下车需求渔网图Fig.4 Hot spot map of alighting demand

对筛选得到的需求点进行聚类分析，一共聚类得到113个上车站点与17个下车站点共130个站点，具体的站点路网分布结果见图5。

图5 站点分布图Fig.5 Site distribution

再对上述的站点进行空间聚类，将上述113个上车站点划分为5个区域，将17个下车站点划分为4个区域，得到的分类数据，见表2。进行上车区域与下车区域的线路设计，本实例中选择30 min为1个时段，对该时段内的需求进行线路方案的设计。

表2 需求分类统计Fig.2 Demand classification statistics

按照本文方法以分类得到的上车区域2与下车区域3为例，进行公交线路设计，并对结果的可行性进行验证，2个区域不同时段的乘客需求见表3。

表3 区域间不同时段需求人数Tab.3 Number of people needed in different periods between regions

对上述区域之间的乘客需求，按照常用的定制公交线路的求解方法，以最短路作为线路设计的目标函数，没有从公交公司以及乘客的角度出发进行线路优化，该方法得到的线路方案见表4。

表4 普通算法求解的定制公交线路Tab.4 Customized bus routes solved by the common algorithm

按照本文提出的双层优化模型中的第一层优化函数，将乘客的出行时间距离以及上下车时间加入到目标函数中，通过遗传算法求解得到的定制公交的线路方案见表5。

表5 本文算法求解的定制公交线路Tab.5 Customized bus route solved by the algorithm proposed in the work

通过对比上述2种结果可以得出，本文提出的优化模型在考虑了乘客需求后，得到的公交线路里程比未考虑时得到的线路里程整体更短，且本优化算法从公交公司的角度出发，在保证整体服务率的基础上去除了服务乘客少的线路，从而保证了每条线路的满载率。

按照本文优化模型的第二层，对得到的公交线路按照乘客出行时间需求在时间层面进行优化，从而得到每一条线路的具体的发车时间见表6。

表6 定制公交线路方案Tab.6 Customized bus-route schemes

4.2 方案评价

针对上述得到的线路方案，现在分别从服务率、人均节省时间以满载率对方案进行相关评价，具体评价结果见表7。

表7 线路方案评价表Tab.7 Evaluation of route schemes

通过表7可以看出，区域将的公交的平均服务率为96%，可以保证乘客1人1座保证乘车的舒适性；不同时段人均节省时间及车辆满载率分别为：06：00—06：30平均每个乘客节省时34.3 min，满载率为80%，06：30—07：00平均每个乘客节省时间7分钟，满载率93%，07：00—07：30平均每个乘客节省时间5 min，满载率92%，07：30—08：00平均每个乘客节省时间16 min，满载率93%。

5 结束语

1）本文以定制公交的站点及线路设计为研究对象，综合考虑了乘客需求点的空间分布以及时间分布特性，以线路长度、线路容量以及乘客的出行时间作为约束条件，构建了公交线路设计的双层优化模型，在空间与时间的角度同时对线路进行求解。

2）通过利用遗传算法对构建定制公交模型进行求解最终得到不同时段每条线路的途径站点、服务率以及线路的发车时间等信息。通过对结果进行对比分析可知通过本模型求解得到的公交线不仅提升了服务率，乘客的出行时间都得到了节省并且公交的满载率较高。

3）本文通过构建时间与空间的双层优化模型，在第一层模型构建时没有将时间约束添加到模型中，在后续的研究中考虑将时间因素与空间因素进行直接的融合，构建单层优化模型对线路进行求解。