0 引言

随着社会经济的发展，城市拥堵也越来越严重，城市公共交通是减缓拥堵的可行方法。作为替代私家车出行的高端公共交通服务的定制公交，主要为出行起讫点、出行时间和服务水平要求相似的人群提供量身定制的交通服务，也称商务班车^[1-3]。定制公交根据乘客出行时间、地点和服务需求设定运行线路，采用一站直达的公交服务模式，具有“定点、定线、定车、定时、定价、定人”等特点^[4-5]。目前定制公交发展迅速，作为影响定制公交服务质量重要指标的定制公交网络规划也引起了国内外诸多学者的研究。

目前国外对于定制公交系统理论的研究方面较早，K. An等^[6]提出了区间不确定性随机理论对公交线网进行了优化研究，N. Nassir等^[7]通过阻抗访问理论对定制公交网络进行了优化，K. Kerkma等^[8]提出了多维空间结合的公交网络优化理论。国内学者对定制公交系统的理论研究还相对较迟，定制公交研究主要集中于空间结构优化^[9]、定制公交车型研究^[10]、定制公交线路研究^[11-12]、定制公交调度研究^[13-15]、定制公交站点布局选址研究^[16-17]。对于系统层面的定制公交网络规划研究较少，程立勤^[18]基于点线面层次分析法研究了定制公交线网布局。徐杨等^[19]以大规模个性化定制模型为基础，从市场需求出发构建了不同的公交线路规划模型。国内外研究几乎没有从网络总体层次对定制公交进行规划研究，存在很多不足，本研究将主要对城市定制公交线网优化设计进行研究。

目前国内外学者多集中于定制公交车辆、线路及站点研究，但对于定制公交线网整体系统研究较少，对于定制公交服务的多种模式没有系统整理研究。鉴于此，我们系统研究了定制公交服务模式，在已知乘客需求的条件下，考虑定制公交需求服务率、平均上座率，结合绿色交通理论，以运营距离成本、运营时间成本、运营环保成本、运营固定成本定制公交总成本3方面最优为目标，建立多种需求响应机制下的绿色定制公交线网优化模型，并提出基于蚁群算法和精确数学算法的分层线网混合求解算法。

1 定制公交线网规划模型 1.1 问题描述

定制公交线网优化问题一般可分为4类问题，即单出发地单目的地(以下称单对单), 单出发地多目的地(以下称单对多)，多出发地单目的地(以下称多对单)，多出发地多目的地(以下称多对多)这4类定制公交线网优化问题。单对单定制公交对应于城市应急车辆、商务班车、旅游班车、临时需求车辆、特殊需求车辆。单对多定制公交对应于单个大型区域至多个目的地的企业通勤车辆、中小学校校车。多对单定制公交对应于多个出发地至单个大型区域的企业、公务员通勤车辆、中小学校车。多对多定制公交对应于多个出发地至多个目的地的企业联合协同、校园联合协同、市政单位联合协同通勤车辆。以上4个问题中除单对单定制公交线网优化问题外，通过整合处理在同一模型下解决。

针对多需求响应的定制公交线网优化问题可描述为：已知若干交通出行小区和若干交通目的小区以及对应的上下车站点，每辆定制公交车从任意上车站点出发，经过若干上车站点，到达若干下车站点，每个下车站点有对应的时间窗要求，满足公交需求、服务率，形成定制公交线网，对其线网进行优化。

1.2 参数设置

针对多需求响应定制公交线网优化问题，已知n个交通出行小区A_i, i=1, 2, …, n，m个交通目的小区B_j, j=1, 2, …, m，q(A_iB_j)为交通出行小区A_i到交通目的小区B_j的交通出行量，每个出行小区分别对应于上车站点A_i, i=1, 2, …, n，每个目的小区分别对应于下车站点B_j, j=1, 2, …, m，每个站点服务周边1 km范围内的交通出行量或交通吸引量、上车站点、下车站点位于道路路网上。上车站点A_i的坐标为(x₁, y₁), (x₂, y₂), …, (x_i, y_i), 下车站点B_j的坐标为(x₁¹, y₁¹), (x₂¹, y₂¹), …, (x_j¹, y_j¹), 点间距离为考虑城市交通组织和路网结构的车辆行驶距离和运行时间距离，相应的行驶距离矩阵和时间距离矩阵分别用L和T表示，L={l(A_i, A_j, B_p, B_q), i, j=1, 2, …, n, p, q=1, 2, …, m}，T={t(A_i, A_j, B_p, B_q), i, j=1, 2, …, n, p, q=1, 2, …, m}，各个站点间的时间距离和行驶距离已知，上车站点A_i至下车站点B_j的行驶距离、时间距离分别为l(A_i, B_j)，t(A_i, B_j)，定制公交线网的线路RL={A_i, …, A_k→B_j, …, B_q, i, k=1，2, …, n, j, q=1，2, …, m}，即，线路流量，线路RL的上座率为，T_RL为线路RL所采用的定制公交车型，C_TRL即为该车型的容量，f_RL为线路RL的发车频次。定制公交线路定制公交线网的总里程距离，定制公交线路里程距离为L(RL_c)，定制公交线路里程时间距离为T(RL_c)，分别表示为：

(1)

(2)

(3)

(4)

式中，l(A_ci, A_c(i+1))为两个站点间的距离；l(A_ck, B_cj)为上车站点和下车站点间的距离; l(B_cj+B_c(j+1))为两个下车站点间的距离；t(A_ci, A_c(i+1))为两个上车站点间的时间距离；t(A_ck, B_cj)为上车站点和下车站点间的时间距离；t(B_cj+B_c(j+1))为两个下车站点间的时间距离；v(A_ci, A_c(i+1))为两个站点间道路的运行速度，v₀(A_ci, A_c(i+1))为两个站点间的设计运行速度；Q(A_ci, A_c(i+1))为两个站点间的设计通行能力；q(A_ci, A_c(i+1))为两个站点间的实际流量，可由百度、高德等地图实时得到。

线路c中定制公交到达下车站点B_j的距离为L(RL_cBj)，定制公交线网总里程时间T(R)=，在线路c中到达下车站点B_j的时间为T(RL_cBj)，给定出发时刻t₀，下车站点B_j规定到达的最迟时间t_dBj，下车站点B_j规定到达的最早时间t_bBj，t_bBj≤t₀+T(RL_cBj)≤t_dBj。

1.3 模型建立 1.3.1 定制公交线网优化总模型(多对多定制公交线网优化模型)

由以上参数构建定制公交线网总模型，从公交企业、乘客、社会3方面综合考虑建立如下优化目标模型：

(1) 定制公交需求服务率最大，由于路网需求分布原因，定制公交线网规划不可能满足所有用户需求，但使需求服务覆盖率最大，剩余需求在后期解决。

(5)

式中，为线路RL的服务需求总量；为交通出行小区A_i至交通目的小区B_j的出行需求总量。

(2) 定制公交线网的平均上座率最高，即定制公交的资源利用率最大，节约社会成本，公交资源配置最优。

(6)

式中r(RL_c)为上座率。

(3) 定制公交总成本最小，即定制公交公司投入成本最小，使定制公交线网更加节约高效。

(7)

式中，Z为总成本；Z₁为运营距离成本；Z₂为运营时间总成本；Z₃为运营环保成本；Z₄为运营固定成本；ω₁，ω₂，ω₃，ω₄分别为各成本的权重。

(8)

式中，Z₁为运营距离成本，可以用运输成本来表示，主要包括车辆固定成本、驾驶员费用、油耗成本等；E_TRL为定制公交车型为T_RL时每辆定制公交车每公里的油耗成本；Q_RLc为线路RL_c的线路流量；C_TRL为线路RL_c所采用的定制公交车型容量；f_RLc为线路RL_c的线路发车频次；L(RL_c)为线路RL_c的实际运营距离。本研究对固定成本单独计算。运营距离成本通过油耗成本来简化计算，其他固定费用归入固定成本中计算。

(9)

式中，Z₂为运营时间成本，即运营时间成本与拥堵后产生的额外运营拥堵成本之和(即对社会造成的拥堵成本)；F_TRL为定制公交车型为T_RL时每辆定制公交车单位时间的时间成本；Q_RLc为线路RL_c的线路流量；C_TRL为线路RL_c所采用的定制公交车型容量；f_RLc为线路RL_c的发车频次；T(RL_c)为线路RL_c的实际运营时间；G_TRL为定制公交车型为T_RL时每辆定制公交车单位时间的拥堵时间成本；T(RL_c)为线路RL_c的正常道路情况下的行驶时间。

(10)

式中，Z₃为运营环保成本，即污染成本；W_a单位污染物排放量的环境污染成本；H_TRL为定制公交车型为T_RL时每辆定制公交车每小时排放的污染物排放量；Q_RLc为线路RL_c的线路流量；C_TRL为线路RL_c所采用的定制公交车型容量；f_RLc为线路RL_c的线路发车频次；T(RL_c)为线路RL_c的实际运营时间。

(11)

式中，Z₄为运营固定成本，包含驾驶员工资、公交车日常维修费用、公交公司日常管理费用等；I_TRL为定制公交车型为T_RL时每辆定制公交车每天的固定运营成本；Q_RLc为线路RL_c的线路流量；C_TRL为线路RL_c所采用的定制公交车型容量；f_RLc为线路RL_c的线路发车频次。

约束条件：

(1) 任意线路的上座率满足最低的定制公交上座率：

(12)

式中r_min为考虑企业成本的最低上座率。

(2) 任意线路的定制公交到达任意下车站点符合任意下车站点的时间要求：

(13)

式中，t_cdBj为线路c中任意下车站点B_j规定到达的最迟时间；t_c0为线路c定制公交的出发时间；T(RL_cBj)为线路c中定制公交到达任意下车站点B_j的实际运行时间；t_cbBj为线路c中任意下车站点B_j规定到达的最早时间。

(3) 任意线路的任意上车站点到达任意下车站点的距离不大于该上车站点直达下车站点距离的α倍，保证定制公交比普通公交的优越性:

(14)

(4) 任意线路的任意上车站点到达任意下车站点的时间不大于该上车站点直达下车站点时间的β倍，保证定制公交比普通公交的优越性:

(15)

从而构建定制公交线网优化的总模型(多对多)：

(16)

(17)

(18)

(19)

(20)

(21)

(22)

(23)

(24)

(25)

(26)

1.3.2 单对多定制公交线网优化模型

若n=1，就转化为单对多定制公交线网优化问题，总模型即转化为单对多的定制公交线网优化模型。

1.3.3 多对单定制公交线网优化模型

若m=1，就转化为多对单定制公交线网优化问题，总模型即转化为多对单的定制公交线网优化模型。

2 定制公交线网规划模型算法

定制公交线网规划模型算法拆分为3个部分解决，即分为上车线网与下车线网连接、上车线网规划、下车线网规划3个部分。

2.1 上车线网与下车线网连接算法

上车线网与下车线网连接算法，可得到上车点区域与下车点区域的两区域的最近两个站点，通过聚类分析得到上车点区域距离下车点区域的最近一个站点C和下车点区域距离上车点区域的最近一个站点D。

上车站点A_i的坐标为(x₁, y₁), (x₂, y₂), …, (x_i, y_i), 下车站点B_j的坐标为(x₁¹, y₁¹), (x₂¹, y₂¹), …, (x_j¹, y_j¹), 上车站点A_i到下车站点B_j的欧式距离, 通过聚类分析得到上车站点区域与下车站点区域的两个最近的上车站点C到下车站点D间的距离及它们的坐标C(x_c, y_c), D(x_d¹, y_d¹)。

通过遍历每个点寻找两个区域之间最短的两个点。

2.2 上车线网规划算法

上车线网规划算法，通过上车站点C、下车站点D、上车点区域A与下车站点D之间的上车线网规划问题，得到上车线网路径，同时满足车型容量约束和上座率约束，得到上车线网的成本。

对于上车线网规划问题，即为NP-hard问题，实质是为求解最优排列的问题，蚁群算法在求解路径寻优问题上有明显优势，本研究采用蚁群算法求解。

2.2.1 上车线网模型结构分析

上车线网模型结构由定制公交线路数量、每条线路采用的车型、每条线路的行车路径、每个站点节点的上车人数4个部分构成。行车路径由节点路径表示，为定制公交车辆经上车站点的有序组合，如RL_c={T_RLc; A_c1, A_c2, …, A_cn; q(A_c1), q(A_c2), …, q(A_ck)}, 定制公交线路c选择定制公交车型T_RLc，该上车线路的行驶路径选择为A_c1→A_c2→…→A_ck→D, 在第i个上车点的上车人数为q(A_ci)，线路c的乘客数量为，上座率为，即，上车线路总长度，上车线路总时间T(RL_c)=。

2.2.2 上车线网算法搜索设计

(1) 上车点排序。将所有上车点按与最近下车点D的距离远近排序，选择最远上车点为可行搜索的起始点，在最远点满足需求的情况下，以第2远点为起始点，以此类推。

(2) 禁忌表。作为蚁群算法核心的禁忌表决定蚁群搜索的原则和方向，本算法禁忌表包含距离、时间、容量3方面内容，分别对应上车线网的距离约束、时间约束、容量约束。

节点全集为TS，假设蚁群搜索当前线路记为RL_c，当前服务节点为A_ci，需求已被完全服务的节点集为DS，需求未被完全服务的节点集为NS，存在：DS+NS=TS。

蚁群当前已加入路径的节点集为SS，DS⊆SS。

禁忌表为Tabu，对于任意节点A_ck，A_ck∈NS，若

(27)

则将A_ci加入Tabu，加入该节点后路径超出长度约束，无法满足定制公交出行需求。

若节点A_ci满足长度约束，若

(28)

则将A_ci加入Tabu，加入该节点后路径超出时间约束，无法满足定制公交出行需求。

若节点A_ci满足长度约束与时间约束，同时A_ci当前剩余未被服务的需求q(A_ci)，满足

(29)

式中，q_RLc为线路RL_c目前已服务的需求总量。节点A_ci能被线路RL_c服务的需求量必然小于该线路采用最大定制公交车型时的剩余容量，即其可被线路RL_c服务的需求量为：

(30)

若节点A_ci被选择为下个服务点，则其剩余未被服务的需求量为：

(31)

若q(A_ci)=0，则将节点A_ci置入节点集DS。线路RL_c的服务需求总量更新为：

(32)

同时，线路RL_c的车型更改为最合适的车型，即：

(33)

如此，蚁群搜索直至NS=Φ为空集时，迭代结束。

2.2.3 信息素更新

为防止出现无效解，在蚁群搜索时，对于未满足线路开通条件的需求也以线路的形式服务，在进行解码的同时，剔除未满足上座率的需求点，再计算定制公交方案的服务率。

在搜索得到完整解后，需要进行模型目标函数值计算。按最优解的路径更新全局信息素。对多目标模型，通过归一化处理判断解优越性。

(1) 对于最大化目标。假定f_b和f_w分别为到目前为止搜索到的单个目标函数的最优解和最差解，评价任意解f_i的适应性o_i:

(34)

(2) 对于最小化目标。假定f_b和f_w分别为到目前为止搜索到的单个目标函数的最优解和最差解，评价任意解f_i的适应性o_i：

(35)

蚁群i搜索到的解的总适应性o_si为：

(36)

式中，o_sqi为需求目标下的适应性；o_szi为上座率目标下的适应性；o_zi为成本目标下的适应性。

每次迭代完成，进行适应性从大到小排序，选择适应性排名前5位解进行路径信息素迭代。迭代方法：

(37)

式中，τ(A_ci, A_ck)为节点对(A_ci, A_ck)的信息素浓度；τ₁(A_ci, A_ck)为更新后节点对(A_ci, A_ck)的信息素浓度；η为挥发系数；Q为迭代留下的信息量；p_q(A_ci, A_ck)表示若路径A_ci→A_ck存在于解q中，则p_q(A_ci, A_ck)=1，否则p_q(A_ci, A_ck)=0。

2.2.4 上车线网算法步骤

不固定蚁群数量，每次增加1只蚂蚁，直至该蚂蚁完成其路径搜索，若剩余总需求量不满足结束条件，则继续增加蚁群数量。迭代结束的条件为NS=Φ。从而得到蚁群算法求解定制公交上车线网规划模型的完整步骤为：

Step 1  初始化蚁群参数和全局信息素。设置蚁群总数G和算法总迭代次数N，当前迭代次数iter=1。

Step 2  当前蚁群序号ag=1。

Step 3  蚁群ag中蚂蚁数量as=1，蚁群置于最远的服务点。

Step 4  对于蚁群ag, 搜索所有需求点，并按式(28)更新该蚁群禁忌表Tabu。

Step 5  对于蚁群ag, 搜索所有需求点，再按式(29)更新该蚁群禁忌表Tabu。

Step 6  结合禁忌表Tabu，按节点间的信息素浓度选择下一需求服务点A_ck，并按式(32)~(36)更新需求点状态和线路状态。

Step 7  若服务点A_ck的剩余需求量为0，则将A_ck加入DS节点集，并从NS节点集中删去A_ck。

Step 8  若NS不为空，且第ag蚁群的禁忌表Tabu为空，则将该蚁群蚂蚁数量as_ag=as_ag+1, 返回Step 4。

Step 9  若NS为空，则蚁群ag的一次迭代结束，记录该蚁群的解，计算模型目标函数值；ag=ag+1。

Step 10  若ag≤G，转Step 3；否则，更新算法最优解，并更新全局信息素。

Step 11  若iter≤N，转Step 2；否则，输出算法最优解。

2.3 下车线网规划算法

通过得到的上车线路，再依据乘客的上车出行需求，得到相应的下车站点及下车人数。对相应的下车站点组合优化得到下车线网路径、下车线网成本及相应下车站点的到达时间。

3 算例

选择杭州市公交集团的定制公交班车客源需求数据为研究数据，本算例研究多对多定制公交问题，进行多对多定制公交线网优化模型及算法的研究。需求分布数据共包含15个交通出行小区和5个交通目的小区，交通出行小区编号为1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15，交通目的小区编号为16, 17, 18, 19, 20。上、下车站点编号及需求数据如图 1，表 1，表 2所示，上、下车站点距离矩阵部分如表 3所示。

通过上车线网与下车线网的连接算法，运用Matlab软件运算得到两区域最近两个上下车站点，编号分别为09, 16。结合专家经验法和实际路网调查数据情况，得到上车线网算法的各项参数：种群数G=10，迭代次数N=200，信息素留存系数η=0.9，信息素增量Q=0.1。上下车站点之间的距离矩阵由其坐标之间的距离得出，上下车站点之间的时间距离矩阵由距离矩阵和速度矩阵得出，速度矩阵由v=v₀Q/q得到。由百度地图的路况信息分级为严重拥堵、拥挤、缓行、畅通，本算例分别简化为q=4.0Q, q=3.0Q, q=2.0Q, q=1.0Q。公交车型为3种，容量为(75, 50, 25)veh，线路运行的条件(企业要求的最低上座率)取0.75。上下车站点间的道路基本通行能力矩阵和实际交通量矩阵如表 4、表 5所示，速度矩阵和时间距离矩阵如表 6、表 7所示。各条定制公交线路流量Q_RLc可通过需求矩阵得出，线路RL_c的线路发车频次f_RLc在本算例中为方便计算定义早高峰1次，通过距离矩阵依据式(34)可得距离成本Z₁，依据式(37)可得运营固定成本Z₄，通过时间距离矩阵依据式(35)可得运营时间成本Z₂，依据式(36)可得运营环保成本Z₃，其中通过调查和专家经验得相应的权重ω₁，ω₂，ω₃，ω₄依次为0.3，0.4，0.2, 0.1，结合得到总成本矩阵，如表 8所示。

通过蚁群算法优化定制公交线网线路，依据上下车站点的距离矩阵和时间距离矩阵，综合得到上下车站点间的综合总成本，再依据线路的最低上车率，搜索得到多需求响应下的城市定制公交绿色线网优化运行方案，如表 9~表 13所示。

3.1 方案对比

从需求点的整体分布来看，可以分为3个大区域，区域内的需求比较集中，蚁群算法搜索的目标就是寻找出行需求集中度高的定制公交线路，实现定制公交尽可能高的服务率和高效的覆盖整体需求。

表 9为算法搜索到的总里程最短方案，其实质是挖掘出行需求最集中、聚集性最高的线路，其余较分散的出行需求用未来候补线路的形式解决。该方案中，开通线路的平均上座率为94%，50%的线路满员运行，可见已开通线路的运力得到较大的运用，线路里程最少，但72%的整体服务率表示存在较多的出行需求未被满足。

表 10为算法搜索到的总时间最少的方案，其实质是优化线路路径，寻求最短出行线路，尽可能提高定制公交的快速到达能力，缩短出行的时间，体现定制公交的快捷性、准时性。97%的平均上座率也充分运用了线路的运力，但67%的总体服务率需要有较大的提升，充分满足大众出行需求。

表 11为算法搜索到的服务率最高的方案，其实质是优化运力配置(线路路线、上车点服务量、线路车型选择)尽可能高地满足出行需求。97%的平均上座率，83%的总体服务率表明算法搜索到了较好的运力配置方案，但83%的整体服务率仍然有提升的空间。

表 12为算法搜索到的总成本最少的方案，其实质是挖掘出行需求、优化运力配置、充分考虑企业需求、乘客服务、社会效益的综合成本最低的方案，94%的平均上座率和80%的整体服务率表明了线路很好地满足了上座率、服务率，也同时满足了聚集较高的出行需求和企业的成本要求，剩余的出行需求在未来得以解决。

表 13为算法搜索到的最优方案，其实质是兼顾上座率和服务率，最大限度地发掘聚集性较高的线路，同时优化运力配置，使得服务覆盖尽可能广泛。线路平均上座率97%，总体服务率83%，综合成本仅次于总成本最少方案，总体服务率最高，平均上座率最高，兼顾社会、乘客、企业3方面权益，取得最优方案。剩余的出行需求分布太散，出行需求较少，需要未来候补方案进行解决。

从企业、社会、乘客3方面的权益考虑，同时考虑环境因素，依据实际线路方案中的平均上座率、总体服务率、总里程、总时间、总成本这5个因素，得到最佳方案。

3.2 车型选择

从表 13可以看出，最优方案中实际线路中的平均上座率为0.97，选择车型1的线路共3条，平均服务量为72，选择车型2的线路为1条，服务量为50，总成本1 771.98元，总体服务率为83%，总体服务率居于首位，更好地满足乘客的需求，总成本仅次于总成本最低方案，满足了企业的收益要求，总里程位于所有方案中的第3位，总时间位于所有方案中的第3位，综合满足了社会、乘客、企业3方面因素，同时考虑了环境保护成本和绿色交通，作用显著。

3.3 车型分析

从表 13可以看出，最优方案中未来候选线路只有1条，总体服务率为17%，服务量为55人。从表 12可以看出，未来候选线路选择车型1为1条线路，选择车型3为1条线路，总体服务率20%，服务量分别为55人和10人。从表 10可以看出，未来候选线路中选择车型1为1条线路，选择车型2为1条线路，总体服务率33%，服务量分别为78人和27人。从表 9可以看出，未来候选线路选择车型1为1条线路，车型3为1条线路，总体服务率28%，服务量分别为80人和10人。从中可以看出这些线路的服务量差别较大，采取线路达到开通要求不一定适合所有线路的情况。为提高线路的总体服务率，建议配置更多车型，使线路车型选择更具有灵活性，增强方案对于出行需求分布的适应性。

4 结论

系统研究了针对多种需求响应下的城市绿色交通定制公交线网优化问题，通过案例研究分析确立了模型算法的有效性，得到以下结论：

(1) 针对整个定制公交网络，系统研究了定制公交模式，建立了针对各种需求下的定制公交网络，建立了相应的网络优化模型和多种响应机制，满足定制公交的多种乘客需求。

(2) 结合多种定制公交需求，对应地定制了公交网络优化模型，充分考虑了社会、企业、乘客3方面的因素，充分考虑了城市拥堵，使得定制公交更加准时、便捷。

(3) 引入绿色交通理论，在多种需求响应机制下的定制公交网络优化模型中充分考虑了环境保护成本，将绿色交通理论不断推广。

(4) 配置了多种定制公交车型，对于多种需求响应下的定制公交网络优化有直接的效果，更加灵活高效，同时可提升定制公交总体服务率。