高铁站定制性灵活线路接驳巴士路径优化

祁 航， 周和平， 苏贞旅

(长沙理工大学 交通运输工程学院，湖南 长沙 410114)

客运方式之间的接驳已成为热点问题，接驳出行正借助于分享经济模式得到如火如荼的发展，网约专车、顺风车、拼车及定制公交等极大地促进了接驳客运的繁荣。针对新时期接驳运输“高效、公平、低碳、优质”的新要求，定制性灵活线路接驳巴士能有效地实现高铁接驳运输。如：Lin[1]等人研究了利用多目标规划方法的接驳公交路线设计的优化。Tong[2]等人建立联合优化模型，解决了灵活定制公交服务的车辆容量利用率和时间窗等问题。Qiu[3]等人考虑车辆运营成本和运输客户成本，以盐城湖为例，对灵活路线取代固定路线的可行性进行了探索。Liu[4]等人通过中国30个正在运行或正在建设的定制公交系统，分析了定制公交这种新概念的演变。

定制化灵活线路接驳巴士路径优化属于单目的地时变交通信息下开放式带时间窗的动态车辆路径优化问题[5]。Barkaoui[6-7]等人针对动态车辆路径问题，提出了一种新的算法，旨在明确提高客户满意度。

在国外，定制公交服务系统模式和线网设计的研究成果较多,但在中国尚处于对其影响因素进行探讨的层面，对于定制性灵活线路接驳巴士路径优化的研究也较少见。作者拟基于动态路网和动态需求，建立高铁站定制性灵活线路接驳巴士路径优化模型，以提高接驳的运输组织效率。

1 定制性灵活线路接驳巴士路径优化模型

先建立传统动态最短路径模型，用于计算2站点间的时间成本。该模型不再详述[8]。对预约需求和实时需求建立的2个模型[9]为:模型一是预排班模型，针对系统中未服务的预约需求;模型二是实时路径优化模型，针对交通路网上的实时需求。

1.1 相关变量与参数

1) 点集

定义一个无向网络图，G=(V,A)，点集V={s,1,2,…，n,t}，其中：s为起点；t为终点；其他点为乘客的上车点。由于需求是不断变化的，点集会不断扩大。点集Vα(τ)∈V为τ时刻未安排服务预约需求上车站点的集合(即车辆发车预排班得到的接驳站点)，是接驳车辆必经站点集合；点集Vβ(τ)∈V为τ时刻已安排服务预约需求上车站点的集合；点集Vδ(τ)∈V为τ时刻已安排服务而未被服务的预约需求上车站点集合；点集Vλ(τ)∈V为τ时刻实时需求上车站点的集合，车辆可选择是否响应该需求；点集Vc(τ)∈V为τ时刻关键点集合；点集Vu(τ)∈V为τ时刻剩余未被服务需求上车站点集合。

2) 决策变量

(1)

(2)

1.2 预约需求预排班模型

该阶段能够为即将出发车辆在发车前提供初始接驳路径，系统中有多辆车进行服务，且要满足预约需求。通过整体最优，得到了当前车辆的初始接驳路径。

1) 目标函数

系统在即将出发车辆发车前的一定时刻为τ时刻(本研究所涉及的时刻与通常的时刻不同，它表示某个时间切片，如：时间范围8∶00-10∶00，按1 h进行时间切片，则对应2个时刻。系统中未出发的车辆集合为K-K′(τ)(其中：K为系统所有车辆的编号集合，K={1,2,…，k}；K′(τ)为τ时刻发出车辆集合)。考虑此时如何安排接驳车辆在满足约束条件的情况下使得目标函数最优，从而得到当前τ时刻即将出发车辆的初始接驳路径。令k=min (K-K′(τ))，Tk为车辆k的处罚时刻，则有：

(3)

目标函数共包含3个部分：① 考虑车辆运营成本最小；② 考虑乘客的在车时间最小；③ 考虑在站乘客等待时间成本最小。

车辆运营的成本为：

(4)

乘客在车时间的成本为：

(5)

在站乘客等待时间的成本为：

(6)

2) 约束条件

① 接驳服务供给约束。这里的需求包含系统中当前提前预约的未被安排服务的预约需求，该需求必须满足。

(7)

② 站点约束。一趟车辆运营从起点出发，到终点结束，车辆到达中间站点提供接驳服务后又离开中间站点，满足节点进、出守恒。

∀p∈Vα(τ)，k∈K-K′(τ)。

(8)

∀q∈Vα(τ),k∈K-K′(τ)。

(9)

∀q∈Vα(τ),k∈K-K′(τ)。

(10)

③ 车辆容量约束。在提供接驳服务的过程中，车内的乘客数不能超过车辆的容量。

∀k∈K-K′(τ)。

(11)

式中：C为车辆最大载客量。

④ 终点时间窗约束。通过时间窗的约束限制接驳公交到达高铁站的时间，要满足接驳乘客可接受到达高铁站的最晚时间。

∀k∈K-K′(τ)。

(12)

式中：Tmk为车辆k到达高铁站的可接受最晚时间。

⑤ 车辆路径有效性约束。通过控制接驳巴士的行驶时间来体现定制化接驳巴士的服务水平。通过该约束条件限制乘客乘坐接驳巴士到达高铁站的行驶时间不超过其直达行驶时间的(1+θ)倍(其中：θ为最大绕行率)。

∀k∈K-K′(τ)。

(13)

式中：Ts为乘客直达行驶的最短时间。

1.3 实时需求路径优化模型

实时需求路径优化模型是动态实时需求插入模型。在整个交通路网的运行过程中，系统会得到实时的接驳需求。对于这种需求，需要判断是否能够被满足。在接驳途中的车辆需从当前站点出发，而新派的车辆从车场出发。对这些车辆上剩余未被服务的需求和实时需求进行路径优化，得到的结果就是最优的接驳方案。

1) 目标函数

在τ时刻，实时订单产生了。此时需要考虑重新安排路网中的接驳车辆，在满足约束条件的情况下，使得目标函数最优。

C3)+C4。

(14)

(15)

式中：σn为动态请求不被响应的惩罚值。

2) 约束条件

实时需求路径优化模型是从路网中的车辆考虑其未服务的需求集合，且τ时刻的关键点即虚拟车场不止一个，因此，此时的模型为多车场对单目的地。

① 接驳服务供给约束。为了使得接驳目标函数最优和保证在车乘客能够按时到达终点，对于动态实时需求，可以选择不响应；而对于已安排接驳而未被服务的乘客，必须满足。

(16)

(17)

② 中间站点约束。车辆到达中间站点提供接驳服务后，又离开中间站点，满足节点进、出守恒。

∀q∈Vδ(τ),k∈K′(τ)。

(18)

③ 车辆容量约束。优先满足预约需求。当车辆在路上行驶时，有些订单的乘客已经在车上了，因此，剩余的需求只能由剩余容量满足，剩余容量Ck(τ)可以通过第一个模型得到。

(19)

④ 终点时间窗约束。若响应动态需求，车辆运行时间会受到影响，从而影响到乘客，因此，要满足车上所有乘客的终点时间窗约束。

Tmk, ∀k∈K′(τ)。

(20)

⑤ 车辆路径有效性约束。限制乘客乘坐接驳巴士到达高铁站的行驶时间不超过其直达行驶时间的(1+θ)倍。

(1+θ)Ts， ∀k∈K′(τ)。

(21)

2 算法设计

对预约需求预排班模型进行求解时，由于订单是确定的，因此属于静态车辆路径问题。而对于实时需求路径优化模型，引入时间轴和关键点的概念，将求解动态车辆路径问题转化为求解一系列基于时间轴的静态子问题。考虑到车辆路径是多目标组合的优化，涉及参数众多，约束条件繁杂，因此采用改进的蚁群算法求解[10]。为了改善蚁群算法的收敛情况，采用2-opt算法，将蚁群算法每次迭代得到的最优解路径进行优化。

2.1 路径选择

在求解过程中，每只蚂蚁代表1辆车，其经过的路径为该车可行的接驳方案。构造订单选择信息素矩阵ω，并且初始化ω=ones(n,n)(其中：n为订单所在站点、车场及目的地的总数)。构造启发信息矩阵η为启发式期望(可见度)，矩阵η中的元素ηpq=1/Tpq，表示p站点到q站点之间的行驶时间倒数。将τ时刻满足约束条件的订单放入可选订单集allowk中，并选择订单。在选择路径时，按照特定的转移概率选择要服务的下一个站点。

2.2 信息素更新策略

1) 局部更新

当每只蚂蚁结束一次路径搜索、需要更新信息素矩阵时，采用自适应局部更新规则。在迭代的过程中，根据状态的变化，不断地调整初始信息素量Q。设经过p站点的车辆数为R，经过(p,q)的车辆数为r，并设Q(τ)=Q·(1-r/R)，当R=0时，Q(τ)=Q，则局部更新计算式为：

ωpq(τ+1)=(1-ρ)·ωpq(τ)+

Δωpq(τ,τ+1)。

(22)

(23)

(24)

2) 全局更新

在一次迭代结束、每辆车对所有订单完成一次接驳后，选取最优路径进行信息素的全局更新，更新计算式为：

ωpq(τ+1)=(1-ρ)·ωpq(τ)+Δωpq(τ,

(25)

(26)

(27)

式中：ρ为信息素挥发系数；C为车辆携带的初始信息素量；Lk为蚂蚁k搜索所行走的路径长度，该路径记为Tk；Lopt为搜索完成后得出的最优路径，该路径记为Topt；σ为可调参数。

2.3 算法步骤

1) 初始化。包括启发因子和信息素挥发系数等参数初始化，设置迭代次数N=1和最大迭代次数Nm，初始化信息素矩阵ω=ones(n,n)，将m只蚂蚁放到车场s，建立禁忌表Tabu。

2) 根据模型中提到的约束条件，包括时间窗约束等来搜索蚂蚁能够服务的下一个订单所在q站点，并把符合要求的订单添加到allowk。

3) 按照路径选择中采用的规则得到车辆要进行服务的订单站点，并在禁忌表Tabu中增加这个站点。

4) 将未被服务的订单集更新，同时更新可选订单集allowk。

5) 若allowk不为空，返回3)；否则，继续。

6) 记录每只蚂蚁所获得的路径、总成本及各代的最优解。

7) 利用2-opt算法，对各代的最优解进行优化。

8) 将信息素矩阵更新，迭代次数加1，N←N+1。

9) 若N≤Nm，返回2)，继续迭代；否则，输出结果，算法终止。

3 算例分析

3.1 模型参数输入

设有一个高铁站定制性灵活线路接驳系统，接驳巴士车场s运营时间为8∶00-22∶00。为了便于计算，将时间进行转换。令8∶00为时刻τ=0，每小时为1，则22∶00为τ=14，车场内有最大载客量为10人的接驳车辆若干。某天，接驳系统中已有预约订单20个，后续预约订单3个，实时订单2个。各订单均有接驳时间窗和最晚到达时间限制。各订单分布位置信息如图1所示(图中数字代表订单所在站点编号，其中，实时预约订单所在站点为24和25)。在图1中，接驳起点坐标为(0,0)，接驳终点坐标为(40,0)。假设各参数的取值：单位时间在车等候成本σ0取4元/h；单位距离收益B取1元/km；单位时间在站候车成本σw取6元/h；车辆最大载客量C取10人；车辆行驶单位时间成本σv取100元/h；动态请求不被响应的惩罚值σn取20元/人；最大绕行率θ为0.5。蚁群蚂蚁数量m为50；初始信息素量Q为500；信息素衰减系数ρ为0.75；可调参数σ为0.7；最大迭代次数为100。

图1 订单位置分布Fig.1 Distribution of order locations

3.2 算例求解

根据所设计的模型和改进蚁群算法，结合已知约束条件，输入原始数据，运用MATLAB编写程序。根据初始预约和后续预约订单，通过计算，得到每辆车发车前的预排班接驳路径，如图2所示。

图2 发车前预排班接驳路径Fig.2 Pre-arrangement schedules

针对系统中出现的实时订单，通过计算，判断订单是否使原有车辆目标函数最优。若是，则予以响应；否则，不予响应。坐标为(18,2)的第24个订单被安排至第2辆车时会在满足约束条件的情况下使得目标函数最优，因此，响应该订单；而坐标为(33,3)的第25个订单则不予响应。最终实时路径优化接驳路径如图3所示，最终接驳路径数据见表1。

图3 车辆最终接驳路径Fig.3 Final vehicle access routes

车辆编号发车时刻接驳路径满载率/%接驳总时间/h绕行率/%10.23s-2-8-13-18-20-t901.42106.520.43s-3-5-24-12-15-23-16-t1001.5611730.79s-21-4-7-10-11-17-t901.62121.541.59s-1-6-9-22-14-19-t901.80135

3.3 结果分析

在系统出现的25个订单中，除了第25个实时需求订单不予响应外，其他均满足目标最优，给予响应，并给出优化接驳路径。从表1中可以看出，接驳车辆的满载率、行驶时间及绕行情况等结果均较好。根据车辆到站时间和乘客时间窗的对比分析，接驳车辆满足了大部分订单的接驳时间窗要求，体现了接驳巴士的灵活性和便捷性。

4 结论

1) 针对预约订单和实时订单，分别建立了优化模型。对于系统中的预约订单，模型一能够求解出初始路径。当实时订单产生时，模型二能够通过最小化目标函数判断是否响应该需求。若响应，则将该订单加入系统进行路径再优化。2种模型的结合能够在保证接驳服务水平的基础上满足接驳需求。

2) 针对所提出模型的特点，设计改进的蚁群算法并对其进行求解。该算法将蚁群算法与2-opt算法结合起来，有效地解决求解时间长的难题，以便该模型能够适用于实际运营环境中。

3) 通过本研究所提出的模型，采用虚拟交通网络进行算例求解，验证了该模型和算法的有效性。