Joint Distribution Location-routing Problem and Large Neighborhood Search Algorithm

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

Abstract

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

CLC Number:

TP391.9

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.

References

[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.