动态信息下的机场定制巴士路径优化

郭权，周和平，欧阳瑞祥，刘勇杰

动态信息下的机场定制巴士路径优化

郭权，周和平，欧阳瑞祥，刘勇杰

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

为解决因航班延误而造成旅客候机时间较长问题，考虑现实路网中阻抗不确定性和机场接驳定制化及差异化出行需求，以运营收益最大、车辆出行成本最小和车辆提前到达的时间窗惩罚成本最小为目标函数，建立了动态信息下机场定制巴士路径优化模型，并采用差分进化算法对其进行求解。为避免算法早熟，提出了改进的自适应操作方法，增强算法的全局寻优能力。通过算例计算表明：考虑航班延误和路网实时订单的动态路径优化模型，可以减少旅客26.61%～46.68%的候机时间，该模型具有较强的可靠性和应用价值。

区间路网阻抗；机场接驳路径优化；动态信息；定制性；差分进化算法

随着网络与大数据技术的快速发展，以“线上预约，接送服务”为特点的机场定制巴士具有形式灵活、方便快捷和高效低碳等特点，可以解决出行者多种出行需求，为旅客去机场提供了出行便利。国内外学者针对机场定制巴士路径从模型构建和模型求解展开了深入研究。张文博[1]等人针对带时间窗的车辆路径提出了两阶段规划策略。刘欣萌[2]等人构建了行驶时间最短和客户等待时间最小的双目标优化模型，设计了多智能体进化算法进行求解。王芳[3]等人采用合理范围的区间数对交通需求进行了度量。辛春林[4]等人将不确定性风险数据用区间数的形式来表示，并结合最小最大准则构建了双层危险品运输网络鲁棒规划模型。Desrosiers[5]等人采用精确算法与经典启发式算法进行了早期研究，但只适用求解小规模的网络问题。Bräysy[6]等人采用了智能启发式算法进行了研究。何小峰[7]等人结合量子计算，提出了一种求解VRPTW的量子蚁群算法。靳文舟[8]等人提出了一种精英选择遗传算法进行模型求解，提高了收敛速度和搜索结果。这些研究主要集中于车辆路径模型的不断优化改进和求解，但考虑路径优化中实时动态需求的研究鲜见。因此，本研究拟构建动态信息下机场定制巴士路径优化模型，为乘客提供个性化、定制化的接驳服务，并结合区间路网阻抗信息对车辆行驶路线进行优化。根据乘客航班延误状况和路网实时订单，实时调整路径优化方案，为乘客提供准点到达机场登机服务，避免长时间候机。

1 模型建立

车辆在道路上行驶时会受到交通管制、交通拥堵、天气变化等不确定因素的影响[9]。本研究通过引入区间数[10]，描述现实路网阻抗的不确定性，以保证建立模型的可靠性。机场定制巴士在行驶过程中，除必须提前预约的订单节点外，对实时动态的订单节点可决定是否响应。时刻，若某些订单节点处的乘客航班发生延误，则系统可根据延误信息对车辆排班路径进行实时优化调整。航班发生延误后，乘客可及时通过系统反馈决定是否取消订单。若乘客没有反馈，则系统默认为不取消订单。因此，考虑动态区间路网阻抗变化，建立动态信息下的机场定制巴士路径优化模型。

1.1 目标函数与决策变量

以运营公司收益最大、车辆出行成本最小及车辆提前到达的时间窗惩罚成本最小为目标函数，建立的数学模型为：

1.2 约束条件

机场定制巴士路径优化受到的约束：①流量进出守恒的约束；②考虑提前预约客户的优先权，即接送必须保证完成其服务的优先权，所以还受到供给约束；③考虑一些定量约束，如：车辆容量以及时间窗约束。

1) 站点约束

接驳车辆从起点出发到终点结束，中间节点满足流量进出守恒。

式(4)、(5)表示接驳车辆从起点出发到达终点，式(6)、(7)表示车辆在起点时只出不进，到达终点后只进不出，式(8)表示车辆满足进出流量守恒原则。

2) 供给约束

为鼓励乘客提前预定，针对提前预定的乘客优先得到服务，可建立供给约束为：

3) 车辆容量约束

车内的乘客数不能超过车辆的额定载客量。

式中：为车辆的额定载客量；Q为时刻时已经上车人数。

4) 时间窗约束

车辆到达终点的时刻是由车辆出发时刻和车辆行驶时间决定的，所有车辆到达终点的时刻不能超过车辆最晚到达时间窗。其中，车辆服务乘客的时间暂时忽略不计。

2 算法设计

动态信息下的机场定制巴士路径优化属于VRPTW问题[11−13]。差分进化算法(differential evolution，简称为DE)对搜索空间中最优解可能存在的区域有良好发现能力，具有求解高效特点。适用于求解VRPTW问题，所以采用差分进化算法对其进行求解。为避免算法早熟，本研究提出了一种改进的自适应操作方法，增强其在全局当中的寻优能力。

2.1 个体编码

采用实数编码，如：路网中包含起点、终点、个乘客订单节点和辆车，则个体生成：[1,2,…,a]，a为实数，满足1≤a≤+1，其中，a代表订单节点。通过(a)函数对实数a进行取整，车辆(a)对相应乘客进行接送。a的大小决定车辆访问顺序，数值小的先被访问。若数值相等，则按照个体从左到右先后出现顺序进行排列。

2.2 初始种群的生成

设初始种群为Z,0=(Z,1,Z,2,…,Z,V)，=(1, 2,3,…,)，Z,0为第0代第条个体，为初始种群的规模，为Z,0的维数。初始种群{Z,0|1≤Z,0≤+1}随机产生。

2.3 变异操作

为种群进化代数，为缩放系数，0＜＜1。因为经过变异，个体“基因”值可能会超出边界范围，所以对此进行边界条件的处理，将不符合边界条件“基因”值通过初始种群生成方法重新产生。

2.4 交叉操作

为增加种群多样性，防止算法早熟，对代种群目标个体Z,n和变异个体V,n通过交叉操作，产生实验个体L,n。为保证实验个体能够继承父代变异个体的优良结构，通过随机选择第i位“基因”作为交叉操作后L,n的第i位等位“基因”，剩下基因通过交叉概率选择由Z,n或V,n来贡献：

2.5 选择操作

为避免算法早熟收敛，对缩放系数增加自适应变异操作，设计方法为：

式中：min为缩放系数的最小值；max为缩放系数的最大值；为调整系数，控制的下降速度。

该缩放系数为一个动态的概率参数，数值区间为 [0,1]。

2.6 计算步骤

1) 设置迭代次数=0；对参数进行初始化；

2) 根据设定的规则对初始种群进行编码操作，随机生成满足条件的初始种群；

3) 令=+1，种群目标个体索引号=1；

4) 选定目标个体Z,i，随机从初代种群中选取2个不同个体；

5) 根据缩放系数计算公式进行更新初始化，执行变异操作，获得变异个体V,i；

6) 对变异后的个体实施交叉操作，获得实验个体L,i；

7) 计算个体L,i适应函数值，并执行选择操作；

8) 目标个体索引号更新=+1，返回步骤4，直至=，否则进入步骤9；

9) 当迭代次数=0大于最大的迭代次数max时，循环结束并输出获得此时计算信息，否则返回步骤3继续迭代。

3 算例分析

假设某机场定制接驳巴士系统，运营公司的车场为，考虑到车辆在机场高速上行驶时不能随意更改路线，所以将终点设置为机场高速入口处，并预留出车辆在机场高速行驶时间，车辆在机场高速上行驶时所需时间为20 min。机场定制接驳巴士采用16座型的巴士，乘客到达机场后至登机所需时间为60 min，=2.5元/人，=50元/辆，0=1 元/km，=0.5元/min。算法中涉及的参数设定为：初始种群规模=150，最大的进化代数G=120，交叉概率值=0.6，min=0.3，max=0.9，=100。现有24位乘客提前进行了预约，具体信息见表1。

表1 提前预约旅客订单信息

表2 初始路径方案

图1 初始路径方案

根据表2中各车辆到达终点的时间和所有乘客到达终点的最晚时间等信息进行计算，可得到在初始路径方案中，乘客的平均等候时间为18.51 min至35.77 min。当=8:15时，车辆1即将接上节点2处乘客，车辆2已经接上节点1处乘客，车辆3已经接上或即将接上节点3处乘客，车辆4即将出发前往节点6处。此时，起飞时刻为10:45的航班延误45 min，更新为11:30起飞，则乘客的平均等候时间变为33.16 min至50.42 min，通过系统反馈航班发生延误的乘客均未取消订单。航班实时延误信息代入模型中，由差分进化算法求解获得考虑航班延误后的实时路径优化方案见表3。

表3 考虑航班延误信息的实时路径优化方案

由表3可知，系统针对当前的航班延误信息得到了优化后的路径方案，其中，车辆4的出发时间作出了相应的推迟调整。通过计算可得，乘客的平均等候时间优化为22.12 min至38.74 min，与优化前相比，乘客的最短等候时间减少了33.29%，最长等候时间减少了23.17%。

当=8:19时，此时车辆1已经接上或即将接上节点2处乘客，车辆2已经接上或即将接上节点6处乘客，车辆3已经接上节点3处乘客，车辆4暂未出发。此时，路网中新增了4个实时订单，具体订单信息见表4。路网中新增实时订单信息代入模型中，由差分进化算法求解获得考虑航班延时和实时订单信息的实时路径优化方案，具体见表5。

表4 实时旅客订单信息

表5 考虑航班延误和实时订单信息的实时路径优化方案

由表5可知，系统针对航班延误和路网实时订单信息给出了新的路径优化方案。其中，车辆4的出发时间作出了相应调整，实时订单26、27、28得到了响应接驳。通过计算可得到乘客的平均等候时间为17.68 min至37.00 min，较上一次优化有所减少。新的车辆实时路径优化方案，满足了乘客需求，得到了进一步的优化，乘客的最小等候时间减少了46.68%，最大等候时间减少了26.61%，整体客座率也得到了提高。

4 结语

考虑区间路网阻抗的影响，将动态问题转化为一系列不同时刻下的静态子问题，进而以系统收益最大、车辆出行成本最小以及车辆提前到达的时间窗惩罚成本最小为目标，建立了动态信息下的机场定制巴士动态路径优化模型，解决了航班延误下乘客候机时间较长的问题。采用差分进化算法，求解所提模型。为避免算法早熟，通过增加参数的自适应操作，提高了算法在全局当中的寻优能力。通过算例分析可得，本模型在保障多目标成本最小的前提下，可以最大减少旅客46.68%候机时间，充分满足了人们个性化以及差异化的出行需求，为旅客提供了更优良的服务，具有广阔的应用前景。

[1] 张文博,苏秦,程光路.基于动态需求的带时间窗的车辆路径问题[J].工业工程与管理,2016,21(6):68−74. (ZHANG Wen-bo,SU Qin,CHENG Guang-lu.Vehicle routing problem with time windows based on dynamic demands[J]. Industrial Engineering and Management, 2016, 21(6): 68−74.(in Chinese))

[2] 刘欣萌,何世伟,陈胜波,等.带时间窗VRP问题的多智能体进化算法[J].交通运输工程学报,2014,14(3):105−110. (LIU Xin-meng, HE Shi-wei, CHEN Sheng-bo, et al. Multi-agent evolutionary algorithm of VRP problem with time window[J].Journal of Traffic and Transportation Engineering, 2014, 14(3): 105−110. (in Chinese))

[3] 王芳.区间需求下鲁棒交通分配研究[D].长沙:长沙理工大学,2015.(WANG Fang. Study on the robust traffic assignment under interval demand[D].Changsha: Changsha University of Science & Technology, 2015. (in Chinese))

[4] 辛春林,张建文,张艳东.基于最小最大准则的危险品运输网络优化研究[J].中国安全科学学报,2016,26(8): 84−89. (XIN Chun-lin, ZHANG Jian-wen, ZHANG Yan-dong.Hazardous materials transportation network optimization based on Min-max criterion[J]. China Safety Science Journal,2016,26(8):84−89.(in Chinese))

[5] Desrosiers J,Dumas Y,Solomon M M,et al.Chapter 2 Time constrained routing and scheduling[J].Handbooks in Operations Research and Management Science,1995,8: 35−139.

[6] Bräysy O,Gendreau M.Vehicle routing problem with time windows, part I: Route construction and local search algorithms[J]. Transportation Science, 2005, 39(1): 104− 118.

[7] 何小锋,马良.带时间窗车辆路径问题的量子蚁群算法[J].系统工程理论与实践,2013,33(5):1255−1261.(HE Xiao-feng,MA Liang.Quantum-inspired ant colony algorithm for vehicle routing problem with time windows[J].Systems Engineering-Theory & Practice, 2013, 33(5):1255−1261.(in Chinese))

[8] 靳文舟,郭献超,龚隽.基于精英选择遗传算法的需求响应公交规划[J].公路工程,2020,45(2):44−49.(JIN Wen-zhou, GUO Xian-chao, GONG Jun.Based on elitist selection genetic algorithm for demand responsive transit planning[J]. Highway Engineering, 2020, 45(2): 44−49. (in Chinese))

[9] 程旭.考虑变化调整时间及带有时间窗的车辆调度问题研究[D].沈阳:沈阳工业大学,2019.(CHENG Xu. Research on vehicle routing problem with time windows and variable adjustment time[D]. Shenyang: Shenyang University of Technology,2019.(in Chinese))

[10] 周和平,冯轩,彭巍.区间阻抗下的鲁棒最短路算法[J]. 系统工程,2017,35(12):121−125.(ZHOU He-ping, FENG Xuan, PENG Wei. Robust shortest path algorithm under interval impedence[J]. Systems Engineering, 2017, 35(12):121−125.(in Chinese))

[11] Khouadjia M R, Sarasola B, Alba E, et al. A comparative study between dynamic adapted PSO and VNS for the vehicle routing problem with dynamic requests[J]. Applied Soft Computing,2012,12(4):1426−1439.

[12] 章宇.不确定旅行时间环境下带时间限制的路径优化模型与算法[D].沈阳:东北大学,2017.(ZHANG Yu.Time- constrained routing optimization models and algorithms under uncertain travel times[D].Shenyang:Northeastern University, 2017.(in Chinese))

[13] 祁航,周和平,苏贞旅.高铁站定制性灵活线路接驳巴士路径优化[J].交通科学与工程,2018,34(4):71−76.(QI Hang, ZHOU He-ping, SU Zhen-lv.Route optimization of customized flexible line feeder bus for the high-speed rail station[J].Journal of Transport Science and Engineering, 2018,34(4):71−76.(in Chinese))

Route optimization of customized airport bus base on dynamic information

GUO Quan, ZHOU He-ping, OUYANG Rui-xiang, LIU Yong-jie

(School of Traffic and Transportation Engineering, Changsha University of Science & Technology, Changsha 410114, China)

In order to reduce the waiting time caused by the flight delay, an route optimization model for the customized airport bus was established considering the uncertainty of the road network and the trip demand of the customization and differentiated. Then the maximum operating income, the minimum cost of vehicle and the minimum penalty cost for early arrival of vehicles were proposed as objective function, which was solved by differential evolution algorithm. To avoid algorithm premature, an improved adaptive operation method was introduced to enhance the ability of the global optimization. The calculation examples show that the waiting time of passengers can be reduced from 26.61% to 46.68%, when the dynamic path optimization model is used considering the flight delay and the booking of road network. The model is considered as reliable to optimize the route of airport bus.

interval road network impedance; route optimization of airport bus; dynamic information; customization; differential evolution algorithm

U491

A

1674 − 599X(2021)02 − 0085− 06

2020−07−09

湖南省自然科学基金资助项目(2019JJ40311)

郭权(1995−)，男，长沙理工大学硕士生。