动态航班信息下机场需求响应接驳车辆路径优化

刘勇杰，李树民 LIU Yongjie， LI Shumin

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

需求响应式运输模式作为新兴出行方式在机场接驳中起着重要作用，然而航班的延误使得机场整体接驳的效率与质量不高，给乘客带来额外的时间损失。随着互联网时代的发展，目前国内各大航空公司提供了航班动态查询功能，因此，有必要结合动态航班信息进行接驳车辆的行车计划决策，提高接驳效率，满足乘客对出行品质的要求。

国外针对需求响应式接驳运输的研究比较早，内容相对比较丰富。Perera[1]提出一种对乘客需求作出快速反应的需求响应系统，实时响应乘客需求。Charisis[2]针对城市交通最后一公里问题，提出DRT 数学模型，并应用遗传算法求解。Sun Bo[3]根据乘客选择的地铁时刻以及服务时间窗口，提出一类考虑个性化出行的混合整数线性规划模型。Shen J[4]提出考虑服务提供者和用户的两阶段路径优化模型。随着国内出行模式智能化的发展，定制公交、网约车等响应式运输模式逐渐走向成熟。彭巍[5]考虑区间路网阻抗信息对机场定制巴士的路径优化进行了研究。孙博[6-7]提出一类需求响应型接驳公交调度模型。阮冠轩[8]根据乘客支付意愿，研究了需求响应型接驳公交路径规划问题。郑汉[9]提出考虑混合车型的需求响应公交定制服务方法。本文所提出的需求响应接驳模式，是结合互联网根据机场旅客的实时航班延误信息，为旅客提供动态延误下的接驳路径服务，满足旅客出行时间要求。

考虑研究问题属于带有软时间窗的动态车辆路径优化问题[10]。关于动态车辆路径研究，文献[11-13]提出两阶段求解算法对动态车辆优化问题进行求解，将问题处理为基于时间轴下的一系列静态子问题，为此本文采用以上方法，构建基于时间轴的混合整数动态规划模型，通过计算不同时刻发生延误下的最优车辆安排方案，达到减少旅客时间损失的目的。

1 问题描述

依照需求响应系统给出乘客预约请求，其中预约请求包括乘客要求的上车地点、期望上车时间窗、航班时刻信息等，运营公司根据以上信息合理安排出发时间以及行驶路径，在满足乘客服务质量情况下减少企业运营成本；由于航班延误信息动态出现，当航班发生延误时，未完成服务乘客的期望接驳时间窗以及航班起飞时间发生改变，原先制定的行驶方案可能出现质量低劣情况，因此需结合当前信息对此时网络进行重新优化，得到发生延误下的最优行驶方案，保证接驳服务质量；即在整个优化阶段，制定的车辆行驶路径分为发车前的初始路径和发车后的实时优化路径。

为将动态问题静态化，通过引入时间轴和关键点[12-13]，将问题处理成一系列静态子问题。实时优化阶段，关键点为在发生航班延误时车辆到达或正在前往的乘客节点，此时关键点可被视为虚拟的配送中心，只能发出一辆车，车辆的容量为动态更新后的车载容量，问题变为多配送中心的车辆路径问题；在发车前阶段，起始车场视为关键点。

2 模型建立

2.1 相关符号定义。集合：Gt表示t时刻网络中的所有关键点；Wt表示t时刻机场、未被服务的预约乘客；Mt表示t时刻未被服务的预约乘客；Nt表示t时刻所有未被服务的预约乘客、关键点、机场。

参数与变量：Ut表示t时刻航班信息下的起飞时间；为t时刻下乘客i期望的接驳时间窗表示t时刻车辆e已行驶的距离；Dmax为车辆行驶的最大距离；Tmax为车辆最长行驶时间；为时刻t车辆k已行驶时间；TW为乘客下车之后赶上飞机所需花费的时间；tij为节点i、j之间的路段阻抗值；tik为车辆k到达节点i的时刻；qik为车辆到达节点i的载客人数；F表示机场；qi表示预约订单的随行人数；Q为车辆容量；dij为节点之间的最短距离；Si为接乘客时的服务时间；β1、β2、β3为目标函数的权重系数。

2.2 基于时间轴的动态规划模型。根据上述研究建立以车辆行驶成本、乘客时间窗惩罚成本、机场到达等待时间成本最小为优化目标的混合整数动态规划模型如下：

式（1） 为目标函数；式（2） 和式（3） 表示接驳车辆从关键点出发到达机场F；式（4） 表示接驳车辆进出流量守恒；式（5） 表示乘客的预约请求都要得到满足；式（6） 表示t时刻安排车辆接送的人数不能超过剩余载客容量；式（7）、式（8） 为

车辆到达节点时刻的线性化表达式，Z表示极大的固定值；式（9） 表示车辆到达机场的时刻不超过允许时间；式（10） 表示车辆行驶的距离不超过允许最大值； 式（11） 表示乘客在车时间不超过允许最大值。

3 两阶段求解算法设计

第一阶段：在车辆未发出时，关键点位于车场，根据乘客预约信息和动态的航班时刻信息，通过Lingo 求解获得最优行驶路线以及出发时间，得到初始车辆路径安排。

第二阶段：在车辆发出时，将研究问题基于时间轴进行实时优化，通过时间轴不断更新接驳车辆的位置坐标、车载人数、关键点、未服务的乘客等相关信息；当航班出现延误信息时，更新乘客期望接驳时间窗以及旅客航班起飞时间，并对此时的网络进行车辆的路径优化，得到最佳行驶路线，其中位于车场的车辆可调整其出发时间，在途车辆不再调整；当车辆行驶途中未出现航班延误信息，接驳车辆按初始计划路线行驶。

算法设计图如图1 所示。

4 算例分析

设有一机场需求响应接驳系统，运营公司车场编号为0，坐标（0，0 ），机场编号为24，坐标（40 ，0 ）以及23 位乘客预约请求（编号1-23），机场接驳车辆采用12 座的中型巴士，乘客下车之后赶上飞机所花费的时间为60 分钟，车辆最大行驶距离Dmax=70km，最大行驶时间Tmax=70min，β1、β2、β3权重系数分别取值为0.8、0.1、0.1，表1 为预排班乘客的预约信息。

在未发车前，结合乘客预约信息以及当前航班信息，通过Lingo 求解获得初始行车路径。系统运营期间，航班延误动态出现，设在时刻8:20、9:44 发布航班延误信息，延误后航班起飞时间分别为12:00，12:25。8:20 时，接驳车辆均未发出，航班晚点45分钟，系统通过反馈更新乘客期望时间窗，将以上信息带入网络模型中，重新计算，得到航班延误后初始车辆路径安排。初始车辆路径安排和8:20 航班延误后车辆路径安排如表2、表3 和图2、图3 所示。

9:44 时，网络已发出3 辆车，车辆3 还未发车其出发时间可同时在实时阶段下进行优化；系统通过时间轴记录了当前时刻P=9:44 下的相关信息：关键点GP={0，5，6，8}，WP={4，7，9，10，11，12，13，14，15，16，17，18，19，20，21，22，2 3，24 };N P={4，7，9，10，11，12，13，14，15，16，17，18，19，20，21，22，23，24，0，5，6，8} ;MP={4，7，9，10，11，12，13，14，15，16，17，18，19，20，21，22，23}。

图1 算法设计图

表1 乘客预约信息

表2 初始车辆路径安排

表3 8:20 航班延误后车辆路径

更新未完成服务乘客的期望时间窗信息，将更新后的相关信息输入到上述动态网络模型中由Lingo 求解，得到9:44 航班信息发生延误下的最优行驶路径，如表4 和图4 所示。

通过以上结果可以看出：（1） 在航班发生延误状态下乘客期望接驳时间窗以及航班起飞时刻发生改变，原先的行驶路径已不再是最优，使得优化后的车辆路径发生变化，改变了到达乘客节点的接驳时间和机场到达时间。（2） 模型求解得到的满载率和行驶时间都在规定范围内，同时乘客需求都得到了满足，证明了模型的有效性。（3） 延误优化后车辆到达机场时间整体推迟，减少了乘客机场等待时间。

由此可见，两阶段算法可以很好地处理实时延误下的车辆路径优化，具有良好的适用性。

5 结 论

（1） 结合动态航班延误信息，构建了基于时间轴的机场需求响应接驳车辆动态路径优化模型，将动态问题处理为不同时刻下的静态子问题。其以车辆行驶成本、乘客时间窗惩罚成本、乘客机场等待时间成本最小为优化目标，在降低企业运营成本的同时提高了接驳的品质。

图2 初始车辆路径

图3 8:20 航班延误后车辆路径

图4 9:44 航班延误后车辆路径

表4 9:44 航班延误后车辆路径安排

（2） 模型求解方面，利用两阶段求解策略，得到发车前的初始行驶路径以及发车后实时延误下的行驶路径。

（3） 通过研究算例验证了模型与算法的有效性，能够为民航乘客提供更加智能化与便捷化的接驳服务。