时变路网下机场接驳车辆-用户共享路径优化

2020-10-24欧阳瑞祥周和平刘静波郭权

交通科学与工程 2020年3期

欧阳瑞祥，周和平，刘静波，郭权

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

民航运输是人们出行不可或缺的方式。目前，机场接驳运输智能化水平较低，而研究机场接驳车辆-用户选择方法有助于构建智慧化民航接驳运输系统。国内外学者对需求响应式接驳进行了深入研究。靳文舟[1]等人通过 K-means 算法，响应公交临时停靠点规划的需求。并基于精英选择遗传算法，选择公交线路规划方案。申婵[2]等人基于可靠性时空网络，建立了定制公交线路优化模型，并采用禁忌搜索算法进行求解。Zheng[3−4]等人研究了可变线路与可变站点的公交模式选择，且提出了一种动态离站时间窗的策略。Sun[5−6]等人考虑了乘客满意度和轨道站点同步换乘的需求响应，建立了接驳公交调度模型。Li[7]等人研究了集成站点选址的需求响应，建立了接驳公交调度模型。

机场接驳车辆-用户选择过程，实质上是考虑新增用户需求的动态车辆路径问题(Dynamic Vehicle Routing Problem，简称为DVRP)，国内外对DVRP进行了许多的研究。Abdallah[8]等人对新增客户需求，构建了带容量约束的DVRP 模型，按时间段将动态需求的车辆路径问题转化成静态车辆路径问题，并采用遗传算法进行求解。Chen[9]等人考虑新增客户需求对车辆容量和时间窗的影响，建立了容量和时间窗约束的DVRP 模型，采用生成初始路径和按时间段定期更新路径的两阶段策略。Ulmer[10]等人将随机顾客请求的多周期车辆路径问题视为马尔可夫决策，以接受服务请求数最大化作为优化目标，提出了一种基于近似动态规划的预期动态策略。祁航[11]等人基于交通网络的动态性及乘客需求的定制性与动态性，建立了高铁站定制性灵活线路接驳巴士路径优化模型，并采用改进的蚁群算法求解。智路平[12]等人先对路段行程时间进行分状态的随机动态预测，然后建立以行程时间可靠性为关键控制变量的三阶段单车辆路径选择模型。作者在时变路网下，对新增用户需求进行实时响应，拟建立共享式机场接驳车辆-用户选择模型，根据约束规划和分枝定界算法，设计了算法并进行求解。以期实现机场接驳运输系统中有限资源的共享，提高接驳效率。

1 问题描述及符号注明

设预排班方案Y=(U,H)，接驳车辆在tp时刻，从车场p出发，接n个预定用户需求点w，去机场e。其中：U为接驳车辆路径集，接驳车辆在预排班方案Y中接驳路径u∈U；H为用户出发时刻集，w用户的出发时刻tw∈H。

在预排班方案Y和时变路网RN=(V,E,M,C)的基础上，对已出发接驳车辆和实时新增用户需求进行匹配，判断接驳车辆能否满足，并生成接驳车辆-用户实时共享方案，如图1 所示。其中，新增用户需求w*是在接驳车辆出发以后，随机出现的；V是道路节点集，路网中任意节点i∈V；E是道路路段集，(i,j)∈E；时间间隔集M={0,1,2,…,m}，任意m表示间隔长度为 Δm的时间间隔[t,t+Δm](如：将10:20-11:20，按每10 分钟，间隔离散，t=0 对应10:20-10:30)；C为路段时间阻抗集，路网中任意路段时间阻抗∈C，表示在m间隔内，路段(i,j)的时间阻抗值；U*是共享路径集，接驳车辆在实时共享方案；中的共享路径中用户出发时刻集。

从图1 可以看出，当4 节点随机产生实时新增用户需求w*时，接驳车辆已行驶到(p,1)路段上。在保证原有预定用户准时到达机场e的情况下，需要快速地判断此接驳车辆能否满足w*需求，并送其到达机场。既找到一条考虑原有用户航班时间以及接驳车辆空余资源等约束，且能满足w*需求的共享路径u*。

图1 时变路网图Fig. 1 Time-varying network diagram

其中，to为路径中共享起点的出发时刻；为乘客登机缓冲时间；为用户需求点的随行人数；Q为车辆容量；Qu为路径u的总人数；为车辆绕行系数；为用户需求点w在tw时刻自行出发到机场的最小旅行时间；Lmax为最大停靠次数；Tmax为乘客最大候机时间阈值；N0为已过节点集，接驳车辆在新增用户需求出现前已过的节点i∈N0；N为未过节点集，N=V−N0；W：用户需求点集，为车辆从p出发的时刻；为在m间隔内路段(i,j)的时间阻抗；tw为w用户的出发时刻；to为车辆在预排方案中到达机场的时刻；O为共享路径的起点；为车辆在共享方案中到达机场的时刻；为实时新增用户需求；tw为用户的航班时间。

2 模型建立

为响应机场接驳过程中实时出现的新增用户需求，建立时变路网下共享式机场接驳车辆-用户选择模型，并使用该模型对机场接驳车辆路径进行优化。

2.1 假设条件

为方便建立模型和求解，假设：①每个预约用户的出发位置和航班时刻表等信息，可在终端获得。②所有用户的登机缓冲时间相同。③乘客上车时间忽略不计，即接驳车辆到达w节点的时间就是乘客的出发时间。④若接驳车辆在t时刻位于路段(i,j)∈u之间，即ti＜t≤tj，则规定j节点为重新规划的共享起点O。⑤假设系统一次只能判断一个用户需求点，是否可以共享，且判断时间忽略不计；⑥所有路段任意间隔内的时变阻抗已获得，在m间隔内，路段阻抗是相同的。

2.2 目标函数与决策变量

为了快速响应机场接驳过程中实时出现的新增用户需求，以接驳车辆总运行时间最小为目标函数，考虑在满足约束条件的情况下，对机场接驳车辆路径进行优化，生成实时共享路径方案。其目标函数公式为：

2.3 约束条件

1) 流量守恒约束

起终点约束：接驳车辆运营从起点出发，到终点机场结束，需满足节点进、出次数约束。

其中，i=0 表示变量x的起点；i=e表示变量x,y的终点；i=w表示y的起点。

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

必经节点约束：系统中未上车的原有预定用户需求必须被满足。

2) 车辆绕行约束

为使乘客有较好的服务体验感，乘客接受服务的时间，不能超过其自行出发最小旅行时间的(1+ε)倍，本研究ε=1.4。w乘客接受服务的时间为Tw。

3) 容量限制约束

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

4) 航班信息约束

空余时间约束：已出发车辆还有空余时间共享给新增用户。

用户航班约束：不能让w的候机时间过长，Tmax是已经在车上用户最大候机时间的μ倍，本研究中μ=1.5。

5) 最大停靠次数约束

为保证接驳服务的质量，接驳车辆在途中停靠的次数不宜过多，本研究最大停靠次数Lmax=10。

3 算法设计

根据约束规划和分枝定界算法设计，相应求解算法，对新增用户需求进行实时共享判断。通过将分枝定界算法中的分枝策略，运用到计算过程中，从而达到减少存储空间和加快求解速度的目的。其算法流程图如图2 所示。

图2 算法流程Fig. 2 Algorithm flow diagram

4 算例分析

设有13 个提前预约用户，向机场接驳需求响应系统发送请求，提前预约用户需求信息见表1；设置2 组实时预约用户组，每组4 个实时预约用户，多组实时预约用户需求信息见表2。机场接驳车辆采用10座车，从办理登机牌到登机的缓冲时间最少45 min，即 Δt=45 min。时变路网中所有路段的阻抗值是由10:20~12:30 以10 min 为间隔，13 个随机离散值组成的。13 个提前预约用户预排班方案Y见表3，在Y中，只有路径u2，可对表2 中的实时预约用户进行共享，因此，对u2进行重点分析。实时预约用户为1 组时，路径u2的实时共享方案图如图3 所示。

多组实时预约用户共享对比见表4，预约用户2 组通过机场接驳需求响应系统，拒绝6,10 节点的预约请求，得到u2共享路径为p→2→7→15→18→13→14→G→e。

由表4 可知，通过对1,2 组实时预约用户共享进行比较，车辆的满载率均从70%增加到100%，机场接驳系统对用户请求响应率均增加15.3%，候机时间利用率分别提高了66.7%和 58.9%。表明：该共享模型可靠，增加了车辆满载率，减少了运营成本，提高了接驳效率和用户满意度。该模型和算法能处理机场接驳需求响应系统中实时新增用户需求的动态车辆路径优化，具有良好的适用性。