基于双边匹配的城市地铁多级配送选址-路径研究

doi:10.19678/j.issn.1000-3428.0068518

摘要/Abstract

摘要：

城市化进程的推进促进了城市物流的快速发展, 城市配送出现多层级的新特性, 但随之出现了交通拥堵和环境污染等问题。基于地铁货运探讨城市多级配送的选址-路径问题, 在物流节点与需求点的分配问题中引入双边匹配理论, 构建以最小化运营成本和最大化匹配满意度为目标的多目标0-1型整数规划模型。设计以地铁站的中心性、配送距离和货运量为基础的匹配偏好指标, 设计需求点与城内中转站匹配满意度的计算方法, 并提出NSGA-Ⅱ与Gale-Shapley算法匹配机制相结合的混合算法对问题进行求解。以上海市部分地铁线路的数据为基础构建案例进行分析, 求得Pareto最优解集合, 通过熵权TOPSIS法来确定目标权重和最优解, 并对城内中转站最大服务能力进行敏感性分析, 结果表明, 同时考虑匹配满意度和运营成本可以获得兼顾“稳定性”和“满意性”的选址-路径方案。此外, 该研究对于建立大都市圈的物流配送体系、缓解城市交通压力以及增强城市物流配送能力都有重要的参考意义。

关键词: 综合交通运输, 选址-路径问题, 地铁货运, 多级配送, Gale-Shapley双边匹配算法

Abstract:

Urbanization advancement has promoted the rapid development of urban logistics, and multi-level new features have emerged in urban distribution. However, problems such as traffic congestion and environmental pollution, have also arisen. This study discusses the location-path problem of urban multi-level distribution based on subway freight transportation. The bilateral matching theory is introduced into the allocation problem of logistics nodes and demand points, and a multi-objective 0-1 integer programming model is constructed to minimize operating costs and maximize matching satisfaction. A matching preference index based on the centrality of subway stations, delivery distance, and freight volume is designed, and a calculation method for the matching satisfaction between demand points and urban transfer stations is established. Additionally, a hybrid algorithm combining the NSGA-Ⅱ and the Gale-Shapley algorithm matching mechanism is proposed to solve the problem. Finally, based on data from some subway lines in Shanghai, a case study is constructed for analysis, and the Pareto optimal solution set is obtained. The entropy weight TOPSIS method is used to determine the target weight and optimal solution, and the maximum service capacity of urban transfer stations is analyzed for sensitivity. The results show that considering both matching satisfaction and operating costs can achieve a location-path scheme that balances ″stability″ and ″satisfaction.″ In addition, the study findings provide important reference significance for establishing a logistics distribution system in metropolitan areas, alleviating urban traffic pressure, and enhancing urban logistics distribution capabilities.

Key words: integrated transportation, location-path problem, subway freight, multi-level distribution, Gale-Shapley bilateral matching algorithm

舒达, 梁承姬, 王钰, 孙苗苗. 基于双边匹配的城市地铁多级配送选址-路径研究[J]. 计算机工程, 2024, 50(11): 369-379.

SHU Da, LIANG Chengji, WANG Yu, SUN Miaomiao. Research on Multi-Level Distribution Location-Route of Urban Subway Based on Bilateral Matching[J]. Computer Engineering, 2024, 50(11): 369-379.

https://www.ecice06.com/CN/Y2024/V50/I11/369

图/表 13

图1 基于城市地铁的多级配送和传统物流配送示意图

Fig.1 Schematic drawing of multilevel distribution and traditional logistics distribution based on urban subway

图2 双边匹配决策示意图

Fig.2 Schematic diagram of bilateral matching decision

图3 NSGA-Ⅱ与GS混合算法流程

Fig.3 Procedure of NSGA-Ⅱ and GS hybrid algorithm

图4 上海地铁1、2号线各站点中心性值

Fig.4 Centrality value of each station of line 1 and 2 in Shanghai metro

图5 Pareto最优解集

Fig.5 Pareto solution set

图6 基于上海市地铁1、2号线的多级配送路径

Fig.6 Multi-level distribution route based on Shanghai metro line 1 and 2

图7 运营成本与匹配满意度的变化

Fig.7 Changes in operating costs and matching satisfaction

参考文献 24

1	DAMPIER A, MARINOV M. A study of the feasibility and potential implementation of metro-based freight transportation in Newcastle upon Tyne. Urban Rail Transit, 2015, 1 (3): 164- 182. doi: 10.1007/s40864-015-0024-7
2	SANCHEZ-DIAZ I. Modeling urban freight generation: a study of commercial establishments' freight needs. Transportation Research Part A: Policy and Practice, 2017, 102, 3- 17. doi: 10.1016/j.tra.2016.06.035
3	PAN Y, LIANG C J, DONG L. A two-stage model for an urban underground container transportation plan problem. Computers & Industrial Engineering, 2019, 138, 106113. doi: 10.1016/j.cie.2019.106113
4	郑长江, 陈宜恒, 沈金星. 基于地铁的地上地下闭环物流配送路径优化. 华东交通大学学报, 2022, 39 (1): 89- 98.
	ZHENG C J, CHEN Y H, SHEN J X. Distribution routing optimization of ground-underground closed-loop logistics based on metro network. Journal of East China Jiaotong University, 2022, 39 (1): 89- 98.
5	ZHAO L J, LI H Y, LI M C, et al. Location selection of intra-city distribution hubs in the metro-integrated logistics system. Tunnelling and Underground Space Technology Incorporating Trenchless Technology Research, 2018, 80, 246- 256. doi: 10.1016/j.tust.2018.06.024
6	周芳汀, 张锦, 周国华. 带时间窗的地铁配送网络路径优化问题. 交通运输系统工程与信息, 2018, 18 (5): 88- 94. doi: 10.16097/j.cnki.1009-6744.2018.05.014
	ZHOU F T, ZHANG J, ZHOU G H. Subway-based distribution network routing optimization problem with time windows. Journal of Transportation Systems Engineering and Information Technology, 2018, 18 (5): 88- 94. doi: 10.16097/j.cnki.1009-6744.2018.05.014
7	XU Y X, DONG J J, REN R, et al. The impact of metro-based underground logistics system on city logistics performance under COVID-19 epidemic: a case study of Wuhan, China. Transport Policy, 2022, 116, 81- 95. doi: 10.1016/j.tranpol.2021.10.020
8	SUN X L, HU W J, XUE X L, et al. Multi-objective optimization model for planning metro-based underground logistics system network: Nanjing case study. Journal of Industrial and Management Optimization, 2023, 19 (1): 170. doi: 10.3934/jimo.2021179
9	LI Z J, SHALABY A, ROORDA M J, et al. Urban rail service design for collaborative passenger and freight transport. Transportation Research Part E: Logistics and Transportation Review, 2021, 147, 102205. doi: 10.1016/j.tre.2020.102205
10	LENG K J, LI S H. Distribution path optimization for intelligent logistics vehicles of urban rail transportation using VRP optimization model. IEEE Transactions on Intelligent Transportation Systems, 2022, 23 (2): 1661- 1669. doi: 10.1109/TITS.2021.3105105
11	SHAN M, HWANG B G, WONG K S N. A preliminary investigation of underground residential buildings: advantages, disadvantages, and critical risks. Tunnelling and Underground Space Technology Incorporating Trenchless Technology Research, 2017, 70, 19- 29. doi: 10.1016/j.tust.2017.07.004
12	CHEN Z L, DONG J J, REN R. Urban underground logistics system in China: opportunities or challenges?. Underground Space, 2017, 2 (3): 195- 208. doi: 10.1016/j.undsp.2017.08.002
13	CUI J Q, DODSON J, HALL P V. Planning for urban freight transport: an overview. Transport Reviews, 2015, 35 (5): 583- 598. doi: 10.1080/01441647.2015.1038666
14	ROTH A E. Common and conflicting interests in two-sided matching markets. European Economic Review, 1985, 27 (1): 75- 96. doi: 10.1016/0014-2921(85)90007-8
15	李铭洋, 李博, 曹萍萍, 等. 考虑匹配稳定性的多属性双边匹配决策方法. 系统工程, 2017, 35 (11): 153- 158.
	LI M Y, LI B, CAO P P, et al. Method for multiple attribute two-sided matching decision making considering the stability of matching problem. Systems Engineering, 2017, 35 (11): 153- 158.
16	周芳汀, 周国华, 张锦. 基于地铁开展城市配送的选点-路径问题. 控制与决策, 2018, 33 (7): 1247- 1254. doi: 10.13195/j.kzyjc.2017.0353
	ZHOU F T, ZHOU G H, ZHANG J. Point-routing problem of urban distribution based on subway. Control and Decision, 2018, 33 (7): 1247- 1254. doi: 10.13195/j.kzyjc.2017.0353
17	BADER D A , KINTALI S , MADDURI K , et al. Approximating betweenness centrality. Berlin, Germany: Springer, 2007.
18	BORGATTI S P, EVERETT M G. A Graph-theoretic perspective on centrality. Social Networks, 2006, 28 (4): 466- 484.
19	NEWMAN M E J . Mathematics of networks. London, UK: Palgrave Macmillan, 2008.
20	VAN BINSBERGEN A, BOVY P. Underground urban goods distribution networks. Innovation: the European Journal of Social Science Research, 2000, 13 (1): 111- 128.
21	刘博宇, 梁承姬, 王钰. 特大型城市地下物流多层级网络优化研究. 计算机工程, 2023, 49 (12): 311- 320. doi: 10.19678/j.issn.1000-3428.0066023
	LIU B Y, LIANG C J, WANG Y. Research on multi-level network optimization of urban underground logistics in the megalopolis. Computer Engineering, 2023, 49 (12): 311- 320. doi: 10.19678/j.issn.1000-3428.0066023
22	戴卓. 三层物流网络选址—路径优化及混合启发式算法研究. 计算机应用研究, 2017, 34 (8): 2349- 2354. doi: 10.3969/j.issn.1001-3695.2017.08.026
	DAI Z. Study on optimization and hybrid heuristic algorithm for location-routing of three-layer logistics network. Application Research of Computers, 2017, 34 (8): 2349- 2354. doi: 10.3969/j.issn.1001-3695.2017.08.026
23	GALE D, SHAPLEY L S. College admissions and the stability of marriage. The American Mathematical Monthly, 2013, 120 (5): 386. doi: 10.2307/2312726
24	唐家俊, 吴晓刚, 张思, 等. 基于Gale-Shapley算法的虚拟电厂与分布式资源匹配机制. 电力系统自动化, 2022, 46 (18): 65- 73. doi: 10.7500/AEPS20211007001
	TANG J J, WU X G, ZHANG S, et al. Matching mechanism for virtual power plants and distributed energy resources based on Gale-Shapley algorithm. Automation of Electric Power Systems, 2022, 46 (18): 65- 73. doi: 10.7500/AEPS20211007001

选择文件类型/文献管理软件名称

选择包含的内容