市区行李值机服务移动站点优化方法

胡小兵; 张雪梅; 周航; 马一鸣

doi:10.3963/j.jssn.1674-4861.2022.03.014

市区行李值机服务移动站点优化方法

doi: 10.3963/j.jssn.1674-4861.2022.03.014

胡小兵^{1, 2,},
张雪梅^{1, 2},
周航^{1, 3, ,},
马一鸣^{1, 3}

1.
中国民航大学体系安全和智能决策实验室天津 300300
2.
中国民航大学安全科学与工程学院天津 300300
3.
中国民航大学中欧航空工程师学院天津 300300

基金项目:

国家自然科学基金项目 61472041

天津市教委科研计划项目 2020KJ037

详细信息

作者简介:
胡小兵（1975—），博士，教授. 研究方向：复杂网络系统模型，民航安全与应急管理.E-mail：huxbtg@163.com

通讯作者:
周航（1990—），博士，讲师. 研究方向：计算智能，空管智能决策，计算电磁学.E-mail：enzo-zhouhang@hotmail.com

中图分类号: U121
计量
- 文章访问数: 916
- HTML全文浏览量: 334
- PDF下载量: 22
- 被引次数: 0
出版历程
- 收稿日期: 2021-10-21
- 网络出版日期: 2022-07-25

A Method for Improved Air Luggage Check-in Service Based on Optimized Urban Mobile Stations

HU Xiaobing^{1, 2
,},
ZHANG Xuemei^{1, 2},
ZHOU Hang^{1, 3
, ,},
MA Yiming^{1, 3}

1.
Laboratory of Complex System Safety and Intelligent Decisions, Civil Aviation University of China, Tianjin 300300, China
2.
College of Safety Science and Engineering, Civil Aviation University of China, Tianjin 300300, China
3.
College of Electronic Information and Automation, Civil Aviation University of China, Tianjin 300300, China

摘要

摘要: 为提高航空运输的服务质量和竞争力，克服传统城市候机楼在服务范围有限、成本高和选址难度高等弊端，提出1种基于市区移动站点（UMS）的航空旅客行李值机服务模式。UMS基于乘客的实时位置分布差异来动态调配移动站点在城市的位置，因此需要解决UMS站点布局优化问题。综合考虑乘客到服务站点的平均路径长度和乘客最大可接受距离等2个重要指标，基于服务站点位置、不同时段的客源分布和站点的最大服务容量等限制因素对2个重要指标进行约束，建立基于路网的UMS布局优化的数学模型。为满足UMS服务模式对优化运算时效性的严格要求，提出1种混合智能优化算法，采用涟漪扩散算法（RSA）求解乘客与UMS站点多对多路径优化问题，采用自适应遗传算法（AGA）高效优化UMS位置分布。以天津城市路网的实际案例与随机生成测试案例对市区移动站点和城市候机楼2种模式的各服务时段的服务质量进行比较。结果显示：在相同站点数量的情况下，乘客到服务站点的平均路径长度比城市候机楼模式减小30.9%，超出乘客的可接受路径长度比城市候机楼模式减少43.7%；UMS位置分布优化使用混合算法（RSA-AGA），其平均计算时间为377 s，比城市候机楼模式所需的平均计算时间减少了41.2%；UMS服务模式在不同站点数量和随机生成测试案例中，各项优化目标均优于城市候机楼模式，更符合乘客的实时需求，验证了UMS运营模式的优越性。
- 智能交通 /
- 城市候机楼 /
- 市区移动值机站点 /
- 涟漪扩散算法 /
- 自适应遗传算法 /
- 行李值机服务
Abstract: To enhance the quality and competitiveness of air transport service and overcome the limitations of low service coverage, high costs, and complex site selection of traditional air terminals, this paper proposes a novel method for improved air luggage check-in service based on Urban Mobile Stations (UMS). Specifically, the proposed UMS can adapt the check-in locations to the real-time passenger positions, which is formulated as a UMS dynamic siting optimization problem over the road network. The average distance and the maximal acceptable distance from passengers to UMS are considered, incorporating the constraints on the locations of service, time-varying distribution of passengers, and the service capacity of stations. Then, a hybrid optimization algorithm satisfying the requirement of real-time computation is developed, which combines the ripple spreading algorithm (RSA) and the adaptive genetic algorithm (AGA). The RSA is used to solve the many-to-many path optimization problem of passenger and UMS stations, and the AGA is employed to optimize the UMS locations. Case studies based on the road network of Tianjin City and simulated random road networks are used for the comparison between the proposed method and the traditional method. The results show that the average distances from passengers to stations are reduced by 30.9%, the number of scenarios exceeding the maximum acceptable distance is decreased by 43.7%, and the average running time of solving the UMS optimization problem is shortened by 41.2% when using the proposed method. These facts show the advantages of the proposed UMS method, meeting the real-time passengers' demands.
- intelligent transportation /
- city air terminal /
- urban mobile station /
- ripple spreading algorithm /
- adaptive genetic algorithm /
- luggage check-in service

HTML全文

图 1 市区移动站点服务模式

Figure 1. Illustration of the urban mobile station service mode

下载: 全尺寸图片幻灯片

图 2 UMS服务模式在服务时段13：00—15：00的运行过程

Figure 2. Operation process of UMS service mode during service time 13:00—15:00

下载: 全尺寸图片幻灯片

图 3 RSA计算多对多路径优化问题流程图

Figure 3. Flowchart of RSA for calculating many-to-many optimization problem

下载: 全尺寸图片幻灯片

图 4 RSA求解多对多路径优化问题的过程

Figure 4. The process of RSA solving many-to-many path optimization problem

下载: 全尺寸图片幻灯片

图 5 1条染色体结构图（例如：N_UMSt = 3并且选择6、9和21标记的节点作为UMS位置）

Figure 5. Structure of one chromosome (e. g. N_UMSt = 3 and the nodes marked by 6, 9, and 21 are chosen as the UMS locations)

下载: 全尺寸图片幻灯片

图 6 两阶段自适应遗传算法的结构

Figure 6. Illustration of the two-stage adaptive genetic algorithm

下载: 全尺寸图片幻灯片

图 7 改变突变和均匀交叉可能性的两阶段自适应遗传算法的流程图

Figure 7. Flowchart of the two-stage adaptive genetic algorithm varying the mutation and uniform crossover possibilities

下载: 全尺寸图片幻灯片

图 8 2019年4月25日天津市路网及客源位置示意图

Figure 8. Schematic diagram of Tianjin's urban route network and passenger source location on April 25, 2019

下载: 全尺寸图片幻灯片

图 9 随机生成网络和乘客分布的测试中UMS和CAT的最佳站点位置

Figure 9. Optimal station locations of UMS and CAT in a test with randomly generated network and passenger distribution

下载: 全尺寸图片幻灯片

表 1 3种混合方法的平均计算时间

Table 1. Average calculation time of the three hybrid methods

类型	平均计算时间/(s)
类型	RSA-GA	D-GA	A^*-GA
多对多路径优化算法	1 058.0	3 942.0	7 726.0
GA	21.5	23.9	29.1

下载: 导出CSV

表 2 AGA和SA在不同乘客分布情况下进行100次试验结果

Table 2. Results of AGA and SA with 100 different passenger source distributions

类型	C_BOF^f /km	C₁ /km	C₂ /km	计算时间/s
AGA	8.89	6.52	2 370.58	557.85
SA	10.23	6.71	3 529.14	1 612.06

下载: 导出CSV

表 3 具有恒定数量的UMS（N_UMS = 3）的结果

Table 3. Results with a constant number of UMS(N_UMS = 3)

服务时段	C_BOF^f /km	C₁ /km	C₂ /km	计算时间/s
05：00—07：00	4.16	3.08	1 081	389
07：00—09：00	2.78	2.39	392	393
09：00—11：00	2.36	1.79	574	391
11：00—13：00	2.78	2.27	512	378
13：00—15：00	2.23	1.97	262	386
15：00—17：00	3.16	1.76	1 397	392
17：00—19：00	3.19	2.06	1 126	417
19：00—21：00	2.80	2.53	268	387

下载: 导出CSV

表 4 CAT不同站点数量情况下的结果

Table 4. Results of cases with different station numbers of CAT

站点数量	C_BOF^f /km	C₁ /km	C₂ /km	计算时间/s
3	4.48	3.23	1245	663
4	3.07	2.46	613	648
5	2.67	2.38	289	597
6	2.28	2.05	225	617
7	2.00	1.89	111	634
8	1.77	1.71	59	652
9	1.69	1.68	6	679

下载: 导出CSV

表 5 UMS可变数量的结果（C_BOF^f < 3 km和C1 < 2 km）

Table 5. Results with a variable number of UMS (C_BOF^f < 3 km and C₁ < 2 km)

服务时间段	站点数量	C_BOF^f/km	C₁ /km	C₂ /km	计算时间/s
05：00—07：00	6	1.94	1.92	16	369
07：00—09：00	4	1.93	1.81	115	353
09：00—11：00	3	2.36	1.79	569	382
11：00—13：00	4	1.96	1.58	384	411
13：00—15：00	3	2.20	1.94	261	396
15：00—17：00	4	1.71	1.42	288	393
17：00—19：00	4	2.10	1.77	329	362
19：00—21：00	5	1.91	1.91	0	347

下载: 导出CSV

表 6 UMS和CAT的调查和运营成本

Table 6. Investigation and operation costs of UMS and CAT

类型	城市候机楼		市区移动站点
资本投资（单个站点）/百万元	38.1~317.9（建造成本：5 000~40 000 m²）	6.4~25.6（年租金：2 000~10 000 m²）	2（特种车辆价格）
年度运营成本（单个站点）/百万元	6.4~63.6	3.2~16.4	≈0.6
站点数量	3~6	3~6	12~18
总成本（20年）/百万元	498.3~9 539.4	576.0~5 040.0	168.0~252.0

下载: 导出CSV

表 7 具有恒定数量的UMS和随机乘客分布的结果(N=3)

Table 7. Results with constant number of UMS with random passenger distributions (N=3)

模式		C_OF /(km)	C₁ /(km)	C₂ /(km)	计算时间/(s)
市区移动站点	服务时段1	5.70	4.48	1215	639
	服务时段2	5.61	4.31	1298	627
	服务时段3	5.67	4.34	1330	637
	服务时段4	5.82	4.45	1371	641
	服务时段5	5.55	4.31	1236	648
	服务时段6	5.57	4.34	1229	638
	服务时段7	5.35	4.15	1204	631
	服务时段8	5.53	4.29	1239	637
	平均	5.60	4.33	1265	637
城市候机楼		7.48	4.56	2918	681

下载: 导出CSV

参考文献(20)

[1]	张亚玲, 龙熙华, 穆学文. 求解最大割问题的分枝定界算法[J]. 西安科技大学学报, 2006(4): 541-544. doi: 10.3969/j.issn.1672-9315.2006.04.025 ZHANG Y L, LONG X H, MU X W. The branch-and-bound algorithm for max-cut problem[J]. Journal of Xi'an University of Science and Technology, 2006(4): 541-544. (in Chinese) doi: 10.3969/j.issn.1672-9315.2006.04.025
[2]	张和君, 张跃. 基于模拟退火算法的布局问题研究[J]. 计算机工程与设计, 2006(11): 1985-1988. doi: 10.3969/j.issn.1000-7024.2006.11.023 ZHANG H J, ZHANG Y. Research on packing problem based on simulated annealing algorithm[J]. Computer Engineering and Design, 2006(11): 1985-1988. (in Chinese) doi: 10.3969/j.issn.1000-7024.2006.11.023
[3]	刘景发, 王大文, 颜学明. 面向动态设施布局的禁忌搜索算法[J]. 华中科技大学学报(自然科学版), 2021, 49(2): 44-50. https://www.cnki.com.cn/Article/CJFDTOTAL-HZLG202102006.htm LIU Y F, WANG D W, YAN X M. Tabu search algorithm for dynamic facility layout problem[J]. Journal of Huazhong University of Science and Technology(Natural Science Edition), 2021, 49(2): 44-50. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-HZLG202102006.htm
[4]	陈振, 王伟贤, 李卓群, 等. 基于多因子约束P中值模型的充电桩布局优化研究[J]. 北京交通大学学报, 2021, 45(3): 93-99. https://www.cnki.com.cn/Article/CJFDTOTAL-BFJT202103013.htm CHEN Z, WANG W X, LI Z Q, et al. Study on optimization of charging pile layout based on multi-factor constrained P-median model[J]. Journal of Beijing Jiaotong University, 2021, 45(3): 93-99. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-BFJT202103013.htm
[5]	HAKIMI S L. Optimum distribution of switching centers in a communi cation network and some related graph theoretic problems[J]. Operations Research, 1965, 13(3): 462-475. doi: 10.1287/opre.13.3.462
[6]	MLADENOVIĆ N, BRIMBERG J, HANSEN P, et al. The p-median problem: A survey of metaheuristic approaches[J]. European Journal of Operational Research, 2005, 179(3): 927-939.
[7]	李军, 解超, 王林, 等. 基于轨迹数据的道路客运班车停留站点位置提取方法[J]. 交通信息与安全, 2021, 39(4): 60-67. doi: 10.3963/j.jssn.1674-4861.2021.04.008 LI J, XIE C, WANG L, et al. A method for extracting regular bus parking stops of road passenger transport based on trajectory data[J]. Journal of Transport Information and safety, 2021, 39(4): 60-67. (in Chinese) doi: 10.3963/j.jssn.1674-4861.2021.04.008
[8]	魏明, 陈学武, 孙博. 公交站场选址布局优化模型和算法[J]. 交通运输系统工程与信息, 2015, 15(4): 113-117. doi: 10.3969/j.issn.1009-6744.2015.04.017 WEI M, CHEN X W, Sun B. Model and algorithm for bus parking site layout optimization problem[J]. Journal of Transportation Systems Engineering and Information Technology, 2015, 15(4): 113-117. (in Chinese) doi: 10.3969/j.issn.1009-6744.2015.04.017
[9]	程一一, 郭建华, 蒋欢昕. 基于兴趣点数据的公交站点布局合理度物元分析评价[J]. 交通信息与安全, 2020, 38(6): 63-72. doi: 10.3963/j.jssn.1674-4861.2020.06.009 CHENG Y Y, GUO J H, JIANG H X. An evaluation of bus station layout rationality using matter element analysis based on points of interest data[J]. Journal of Transport Information and safety, 2020, 38(6): 63-72. (in Chinese) doi: 10.3963/j.jssn.1674-4861.2020.06.009
[10]	鲍文仓, 田琼. 基于连续逼近的共享电动汽车站点布局研究[J]. 交通运输系统工程与信息, 2018, 18(增刊1): 21-29. https://www.cnki.com.cn/Article/CJFDTOTAL-YSXT2018S1005.htm BAO W C, TIAN Q. Depot location problem of electric vehicle sharing system: A continuum approximation method[J]. Journal of Transportation Systems Engineering and Information Technology, 2018, 18(S1): 21-29. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-YSXT2018S1005.htm
[11]	刘嘉文, 代颖, 杨斐, 等. 共享单车停放点联合覆盖选址及车辆配置模型[J]. 工业工程与管理, 2020, 25(1): 127-135. https://www.cnki.com.cn/Article/CJFDTOTAL-GYGC202001015.htm LIU J W, DAI Y, YANG F, et al. A cooperative covering model for location of bike sharing stations and its fleet deployment[J]. Industrial Engineering and Management, 2020, 25(1): 127-135. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-GYGC202001015.htm
[12]	ERNST A T, KRISHNAMOORTHY M. Solution algorithms for the capacitated single allocation hub location problem[J]. Annals of perations Research, 1999(86): 141-159.
[13]	GONG D, GEN M, YAMAZAKI G, et al. Hybrid evolutionary method for capacitated location-allocation problem[J]. Computers & Industrial Engineering, 1997, 33(3/4): 577-580.
[14]	BRIMBERG J, HANSEN P, MLADENOVIC N, et al. Improvements and comparison of heuristics for solving the uncapacitated multisource Weber problem[J]. Operations Research. 2000, 48(3): 444-460. doi: 10.1287/opre.48.3.444.12431
[15]	SMED J, HAKONEN H. Algorithms and networking for computer games[M]. Hoboken: Wiley Online Library, 2006.
[16]	SNIEDOVICH M. Dijkstra's algorithm revisited: The dynamic programming connexion[J]. Control and Cybernetics, 2006, 35(3): 599-620.
[17]	HU X B, WANG M, LEESON M S, et al. Deterministic agent-based path optimization method by mimicking the spreading of ripples[J]. Evolutionary Computation, 2016, 24 (2): 319-346.
[18]	胡小兵, 陈树念, 张盈斐, 等. 求解多目标路径优化问题的涟漪扩散算法[J]. 计算机工程与应用, 2021, 57(23): 81-90. https://www.cnki.com.cn/Article/CJFDTOTAL-JSGG202123009.htm HU X B, CHEN S N, ZHANG Y F, et al. New ripple-spreading algorithm for multi-objective path optimization[J]. Computer Engineering and Applications, 2021, 57(23): 81-90. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-JSGG202123009.htm
[19]	顾鹏程. 基于自适应遗传算法的多目标优化研究[D]. 南京: 南京航空航天大学, 2016. GU P C. Research on multi-objective optimization based on adaptive genetic algorithm[D]. Nanjing: Nanjing University of Aeronautics and Astronautics, 2016. (in Chinese)
[20]	China Aviation Ground Service Company. Project report of CAT construction in Tianjin[R]. Beijing: China Aviation Ground Service Company, 2013.