共同配送选址-路径问题及大邻域搜索算法

doi:10.16182/j.issn1004731x.joss.20-0685

系统仿真学报 ›› 2021, Vol. 33 ›› Issue (10): 2518-2531.doi: 10.16182/j.issn1004731x.joss.20-0685

• 国民经济仿真 • 上一篇

共同配送选址-路径问题及大邻域搜索算法

李珍萍¹, 赵雨薇^1,2, 张煜炜^1,3, 邢立宁⁴, 任腾^5,*

1.北京物资学院信息学院,北京 101149;
2.北京化工大学经济管理学院,北京 100029;
3.首都经济贸易大学管理工程学院,北京 100070;
4 国防科技大学信息系统与管理学院,湖南长沙 410003;
5.中南林业科技大学物流与交通学院,湖南长沙 410004

收稿日期:2020-09-10 修回日期:2020-11-22 出版日期:2021-10-18 发布日期:2021-10-18
通讯作者: 任腾(1988-),男,博士,副教授,研究方向为物流工程与管理、复杂系统建模与仿真。E-mail: chinarenteng@163.com
作者简介:李珍萍(1966-),女,博士,教授,研究方向为物流网络优化、智能算法。E-mail：lizhenping66@163.com
基金资助:
国家自然科学基金(71771028),北京自然科学基金(9212004, Z180005),北京市属高校高水平科研创新团队建设项目(IDHT20180510)

Joint Distribution Location-routing Problem and Large Neighborhood Search Algorithm

Li Zhenping¹, Zhao Yuwei^1,2, Zhang Yuwei^1,3, Xing Lining⁴, Ren Teng^5,*

1. School of Information, Beijing Wuzi University, Beijing 101149, China;
2. School of Economics and Management, Beijing University of Chemical Technology, Beijing 100029,China;
3. School of Management Engineering, Capital University of Economics and Business, Beijing 100070, China;
4. School of Information System and Management, University of National Defense Science and Technology, Changsha 410003, China;
5. School of Logistics and transportation, Central South University of Forestry and Technology, Changsha 410004, China

Received:2020-09-10 Revised:2020-11-22 Online:2021-10-18 Published:2021-10-18

摘要/Abstract

摘要： 结合城市物流共同配送体系两层级、多中心、多车型等特点,研究了两层级共同配送选址-路径问题。以总成本极小化为目标,建立该问题混合整数规划模型,设计求解模型的自适应大邻域搜索算法。算法应用多种删除操作符和插入操作符生成邻域解,根据每次迭代得到的邻域解优劣调整相应操作符的选择概率,加快收敛速度。利用选址-路径问题的标准测试集生成若干算例,分别利用自适应大邻域搜索算法和Gurobi软件进行求解,通过对比分析验证自适应大邻域搜索算法的快速有效性。

关键词: 两层级共同配送, 选址-路径问题, 混合整数规划, 自适应大邻域搜索, 模拟退火

Abstract: Based on the characteristics of two-echelon, multi-center, and heterogeneous fleets in urban logistics joint distribution system, the two-echelon joint distribution location routing problem is studied. The problem is formulated into a mixed integer programming model to minimize the total costs. An adaptive large neighborhood search algorithm (ALNS) for solving the model with multiple deletion and insertion operators is proposed to obtain neighborhood solution. The selection probability of each operator is adjusted according to the neighborhood solution to accelerate the convergence speed. Several test examples are generated based on the benchmark of location-routing problem. Both ALNS algorithm and Gurobi software are used to solve the problem respectively, and the fast effectiveness of the ALNS algorithm is verified by comparative analysis.

Key words: two-echelon joint distribution, location-routing problem, mixed integer programming, adaptive large neighborhood search, simulated annealing

中图分类号:

TP391.9

李珍萍, 赵雨薇, 张煜炜, 邢立宁, 任腾. 共同配送选址-路径问题及大邻域搜索算法[J]. 系统仿真学报, 2021, 33(10): 2518-2531.

Li Zhenping, Zhao Yuwei, Zhang Yuwei, Xing Lining, Ren Teng. Joint Distribution Location-routing Problem and Large Neighborhood Search Algorithm[J]. Journal of System Simulation, 2021, 33(10): 2518-2531.

参考文献

[1] 任腾, 李姝萱, 周忠宝, 等.基于满意度BLP-DEA的区域可持续发展系统效率评价研究[J/OL]. 中国管理科学: 1-13 [2020-11-22]. https://doi.org/10.16381/j. cnki.issn1003-207x.2020.0080.
Ren Teng, Li Shuxuan, Zhou Zhongbao, et al.Study on Efficiency Evaluation of Regional Sustainable Development System Based on BLP-DEA and Satisfaction Degree[J/OL]. Chinese Journal of Management Science. [2020-11-22]. https://doi.org/ 10.16381/j.cnki.issn1003-207x.2020.0080.
[2] 任腾, 陈玥, 向迎春, 等. 考虑客户满意度的低碳冷链车辆路径优化[J]. 计算机集成制造系统, 2020, 26(4): 1108-1117.
Ren Teng, Chen Yue, Xiang Yingchun, et al.Optimization of Low Carbon Cold Chain Vehicle Path Considering Customer Satisfaction[J]. Computer Integrated Manufacturing System, 2020, 26(4): 1108-1117.
[3] 彭春, 李金林, 王珊珊, 等. 多类应急资源配置的鲁棒选址-路径优化[J]. 中国管理科学, 2017, 25(6): 143-150.
Peng Chun, Li Jinlin, Wang Shanshan, et al.Multiple Relief Resources Robust Location-Routing Optimization[J]. Chinese Journal of Management Science, 2017, 25(6): 143-150.
[4] Li H, Wang H, Chen J, et al.Two-echelon Vehicle Routing Problem with Time Windows and Mobile Satellites[J]. Transportation Research Part B: Methodological (S0191-2615), 2020, 138: 179-201.
[5] 唐金环, 戢守峰, 姜力文, 等. 顾客有限“碳行为”偏好对选址-路径-库存联合优化的影响[J]. 中国管理科学, 2016, 24(7): 110-119.
Tang Jinhuan, Ji Shoufeng, Jiang Liwen, et al.The Effect of Consumers Bounded “Carbon Behavior” Preference on Location-Routing-Inventory Optimization[J]. Chinese Journal of Management Science, 2016, 24(7): 110-119.
[6] Wang Y, Assogba K, Liu Y, et al.Two-echelon Location-routing Optimization with Time Windows Based on Customer Clustering[J]. Expert Systems with Applications (S0957-4174), 2018, 104: 244-260.
[7] Pichka K, Bajgiran A H, Petering M E H, et al. The Two Echelon Open Location Routing Problem: Mathematical Model and Hybrid Heuristic[J]. Computers & Industrial Engineering (S0360-8352), 2018, 121: 97-112.
[8] Demir E, Bektas T, Laporte G.An Adaptive Large Neighborhood Search Heuristic for the Pollution-routing Problem[J]. European Journal of Operational Research (S0377-2217), 2012, 223(2): 346-359.
[9] 郭鹏辉, 朱建军, 王翯华. 考虑异质物资合车运输的灾后救援选址-路径-配给优化[J]. 系统工程理论与实践, 2019(9): 2345-2360.
Guo Penghui, Zhu Jianjun, Wang Hehua.Location-routing-allocation Problem with Consolidated Shipping of Heterogeneous Relief Supplies in Post-disaster Rescue[J]. Systems Engineering-Theory & Practice, 2019(9): 2345-2360.
[10] Yu Y, Wang S, Wang J, et al.A Branch-and-price Algorithm for the Heterogeneous Fleet Green Vehicle Routing Problem with Time Windows[J]. Transportation Research Part B: Methodological (S0191-2615), 2019, 122: 511-527.
[11] Koç Ç, Bektaş T, Jabali O, et al.The Impact of Depot Location, Fleet Composition and Routing on Emissions in City Logistics[J]. Transportation Research Part B: Methodological (S0191-2615), 2016, 84: 81-102.
[12] Koç Ç, Bektaş T, Jabali O, et al.The Fleet Size and Mix Location-routing Problem with Time Windows: Formulations and a Heuristic Algorithm[J]. European Journal of Operational Research (S0377-2217), 2016, 248(1): 33-51.
[13] Zhao Q, Wang W, De Souza R.A Heterogeneous Fleet Two-echelon Capacitated Location-routing Model for Joint Delivery Arising in City Logistics[J]. International Journal of Production Research (S1366-588X), 2018, 56(15): 5062-5080.
[14] 石兆, 符卓. 配送选址-多车型运输路径优化问题及求解算法[J]. 计算机科学, 2015, 42(5): 245-250.
Shi Zhao, Fu Zhuo.Distribution Location-routing Problem of Heterotypic Vehicles and its Algorithms[J]. Computer Science, 2015, 42(5): 245-250.
[15] Govindan K, Jafarian A, Khodaverdi R, et al.Two-echelon Multiple-vehicle Location-routing Problem with Time Windows for Optimization of Sustainable Supply Chain Network of Perishable Food[J]. International Journal of Production Economics (S0925-5273), 2014, 152(6): 9-28.
[16] Clarke G, Wright J W.Scheduling of Vehicles From a Central Depot to a Number of Delivery Points[J]. Operations Research (S0030-364X), 1964, 12(4): 568-581.
[17] Hemmelmayr V C, Cordeau J F, Crainic T G.An Adaptive Large Neighborhood Search Heuristic for Two-echelon Vehicle Routing Problems Arising in City Logistics[J]. Computers & Operations Research (S0305-0548), 2012, 39(12): 3215-3228.
[18] Ropke S, Pisinger D.An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows[J]. Transportation Science (S0041-1655), 2006, 40(4): 455-472.
[19] Ropke S, Pisinger D.A Unified Heuristic for a Large Class of Vehicle Routing Problems with Backhauls[J]. European Journal of Operational Research (S0377-2217), 2006, 171(3): 750-775.
[20] Prodhon C.The Location-routing Problem[D]. Troyes: Troyes University of Technology, 2006.

共同配送选址-路径问题及大邻域搜索算法

Joint Distribution Location-routing Problem and Large Neighborhood Search Algorithm

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 14

编辑推荐

Metrics

本文评价

[1]	李珍萍, 杨光, 韩倩倩. 考虑工作量均衡的成品油二次配送车辆路径问题[J]. 系统仿真学报, 2022, 34(2): 221-233.
[2]	邵良杉, 王振, 李昌明. 基于模拟退火与改进粒子群的矿井通风优化算法[J]. 系统仿真学报, 2021, 33(9): 2085-2094.
[3]	陆嘉波, 程培星, 黄羿, 姚进强, 杨雪梦, 马新强, 刘勇. 用于时敏目标打击链快速构建的智能方法[J]. 系统仿真学报, 2021, 33(2): 346-357.
[4]	蔡敏, 王艳, 纪志成. 基于多策略融合量子粒子群算法的MOFFJSP研究[J]. 系统仿真学报, 2021, 33(11): 2615-2626.
[5]	沈鹏, 王艳, 纪志成, 张建华. 超启发式DE算法求解零等待发酵工艺调度[J]. 系统仿真学报, 2020, 32(11): 2235-2243.
[6]	赵文清, 覃智补. 采用改进型智能水滴算法的电力环境经济调度[J]. 系统仿真学报, 2018, 30(8): 3213-3218.
[7]	刘炜, 许嘉轩, 王沛沛, 刘瑞龙, 唐靖坤. 基于模拟退火算法的列车节能操纵研究[J]. 系统仿真学报, 2018, 30(6): 2320-2327.
[8]	王长涛, 孙晓彤, 韩忠华, 朱毅. 基于自适应模拟退火PSO算法建筑管道布置研究[J]. 系统仿真学报, 2018, 30(5): 1941-1949.
[9]	吉卫喜, 蔡酉勇, 张朝阳, 彭威. 异常事件驱动的离散制造车间重调度决策[J]. 系统仿真学报, 2018, 30(11): 4043-4052.
[10]	陈超, 王艳, 严大虎, 纪志成. 面向能耗的柔性作业车间动态调度研究[J]. 系统仿真学报, 2017, 29(9): 2168-2175.
[11]	许世鹏, 吴定会, 孔飞, 纪志成. 基于改进鸡群算法的柔性作业车间调度问题求解[J]. 系统仿真学报, 2017, 29(7): 1497-1505.
[12]	蒋莹莹, 纪志成. 基于混合量子粒子群算法的DFIG参数辨识[J]. 系统仿真学报, 2016, 28(5): 1054-1062.
[13]	李小霞, 黄小毛, 刘建晓, 刘峰. 面向低制造能耗的车间作业调度优化仿真[J]. 系统仿真学报, 2016, 28(1): 114-120.
[14]	熊最, 王可人, 金虎, 冯辉. 一种基于干扰对齐的多跳网络吞吐量优化模型[J]. 系统仿真学报, 2015, 27(6): 1240-1246.