Please wait a minute...
浙江大学学报(工学版)
Journal of ZheJiang University (Engineering Science)  2023, Vol. 57 Issue (10): 2018-2027    DOI: 10.3785/j.issn.1008-973X.2023.10.011
    
Unmanned logistics distribution route considering customer level and time-varying road conditions
Jia-bi LI1(),Shu-guang HAN2,*()
1. School of Economics and Management, Zhejiang Sci-Tech University, Hangzhou 310018, China
2. School of Science, Zhejiang Sci-Tech University, Hangzhou 310018, China
Download: HTML     PDF(1230KB) HTML
Export: BibTeX | EndNote (RIS)      

Abstract  

A mathematical model for optimizing unmanned vehicle delivery paths was established, addressing the challenges faced by the logistics enterprises such as limited distribution resources, the diverse needs of customers unable to respond in a timely manner, and constantly changing road conditions. The model was related to time-varying road conditions and time windows. Customers were divided into three levels by using a cloud model. The optimization objective function was to minimize the sum of vehicle delivery costs, penalty costs for not meeting customer delivery times, and vehicle charging costs. A hybrid algorithm was constructed based on the genetic algorithm in combination with the simulated annealing algorithm to solve the model and verify the correctness. Nine sets of arithmetic examples of different sizes and types were constructed according to the properties of the model for numerical experiments and to verify the effectiveness of the algorithm. Experimental results showed that the total distribution cost incurred in the distribution process under the hybrid genetic-simulated annealing algorithm could be saved by up to 42.81% and the overall customer satisfaction could be increased by up to 80.23%. The proposed hybrid genetic-simulated annealing algorithm was able to maximise customer satisfaction on the basis of effective cost reduction and was better optimised compared to the two traditional algorithms.

Key words： customer level      time varying road conditions      unmanned logistics distribution      hybrid genetic simulated annealing algorithm      cloud-based model     
Received: 07 December 2022      Published: 18 October 2023
CLC:  O 221.2  
Fund:  国家自然科学基金资助项目（12071436）
Corresponding Authors: Shu-guang HAN     E-mail: 18940904238@163.com;dawn1024@zstu.edu.cn
Service
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
RSS
Articles by authors
Jia-bi LI
Shu-guang HAN
Cite this article:

Jia-bi LI,Shu-guang HAN. Unmanned logistics distribution route considering customer level and time-varying road conditions. Journal of ZheJiang University (Engineering Science), 2023, 57(10): 2018-2027.

URL:

https://www.zjujournals.com/eng/10.3785/j.issn.1008-973X.2023.10.011     OR     https://www.zjujournals.com/eng/Y2023/V57/I10/2018


考虑客户等级和时变路况的无人物流配送路径

针对物流企业因配送资源的有限、无法及时应对客户的多样化需求和道路状况的不断变化等难题，建立时变道路状况和时间窗关联的无人车配送路径优化数学模型。通过云模型将客户划分为3个等级，以车辆配送成本、未满足客户配送时间的惩罚成本、车辆充电成本的总和极小化作为优化目标函数. 在遗传算法的基础上，结合模拟退火算法构造混合算法，对模型进行求解并验证正确性. 根据模型的特性构造9组不同规模和类型的算例进行数值实验，并验证算法的有效性. 实验结果表明，混合遗传-模拟退火算法下配送过程中产生的总配送成本最多能够节省42.81%，整体客户满意度最高提升80.23%，提出混合遗传-模拟退火算法能够在有效降低成本的基础上，最大程度提升客户的满意度，并且相较于2种传统算法，其优化效果更好.


关键词： 客户等级,  时变路况,  无人物流配送,  混合遗传-模拟退火算法,  云模型 
Fig.1 Schematic diagram of urban unmanned logistics distribution considering customer grade and time-varying road conditions
Fig.2 Value evaluation index system for delivery customer
客户等级 普通客户 主要客户 VIP客户
评价值区间 [0, 5] [5, 8] [8, 10]
评价云模型 （2.5, 0.833, 0.1） （6.5, 0.5, 0.1） （9, 0.333, 0.1）
Tab.1 Customer rating cloud model related digital eigenvalue
Fig.3 Optimization flowchart of hybrid genetic simulated annealing algorithm
Fig.4 Vehicle speed in different time periods
测试算例 GA-SA GA SA GAP1/% GAP2/% GAP3/% GAP4/%
${B_1}$ ${\bar B_1}$ ${B_2}$ ${\bar B_2}$ ${B_3}$ ${\bar B_3}$
C1-25 1624.18 2072.32 1838.61 2271.71 2393.47 2680.41 ?11.66 ?8.78 ?32.14 ?22.69
C1-50 4380.78 5010.68 4729.82 5235.70 5648.66 6287.47 ?7.38 ?4.30 ?22.45 ?20.31
C1-100 15865.97 16028.50 16156.72 16477.42 16392.10 16849.24 ?1.80 ?2.73 ?3.21 ?4.87
R1-25 2564.81 2878.42 2800.74 3126.75 3229.33 3805.56 ?8.42 ?7.94 ?35.84 ?36.49
R1-50 4998.37 5460.09 5565.07 5872.42 8278.14 9245.20 ?10.18 ?7.02 ?30.21 ?29.01
R1-100 15670.87 16164.71 15981.58 16530.93 16363.92 17316.70 ?1.94 ?5.61 ?4.24 ?6.65
RC1-25 2071.81 2416.91 2275.78 2577.36 3622.77 3978.08 ?8.96 ?6.23 ?42.81 ?39.24
RC1-50 5777.58 6563.26 6334.06 7100.76 8806.61 9202.14 ?8.79 ?7.57 ?34.39 ?28.68
RC1-100 15120.79 16018.82 15967.02 16287.75 16445.17 16943.83 ?5.30 ?1.65 ?8.05 ?5.46
Tab.2 Optimization results of different methods aiming at minimizing cost
测试算例 GA-SA GA SA GAP5/% GAP6/% GAP7/% GAP8/%
${U_1}$ ${\bar U_1}$ ${U_2}$ ${\bar U_2}$ ${U_3}$ ${\bar U_3}$
C1-25 0.925 0.846 0.838 0.812 0.680 0.588 10.38 4.13 36.03 43.88
C1-50 0.982 0.898 0.888 0.864 0.610 0.540 10.59 3.95 60.98 66.29
C1-100 0.803 0.768 0.774 0.725 0.692 0.632 3.74 5.93 16.04 21.52
R1-25 0.847 0.819 0.824 0.728 0.685 0.598 2.79 12.41 45.84 57.02
R1-50 0.991 0.908 0.904 0.857 0.708 0.575 9.62 5.94 41.24 71.30
R1-100 0.784 0.706 0.729 0.657 0.654 0.619 7.54 7.46 19.88 14.05
RC1-25 0.999 0.939 0.988 0.934 0.666 0.521 1.11 0.55 50.00 80.23
RC1-50 1.000 0.985 0.981 0.947 0.679 0.583 1.94 4.05 47.28 68.95
RC1-100 0.799 0.713 0.682 0.631 0.486 0.448 17.16 12.30 64.40 59.15
Tab.3 Optimization results of different methods considering customer satisfaction
Fig.5 Influence of vehicle number on cost optimization results
Fig.6 Optimising impact of different road conditions on cost and satisfaction
Fig.7 Influence of customer satisfaction on cost optimization results
Fig.8 Path results of electric vehicles
[1]   浙江省省政府办公厅. 关于印发《浙江省基本公共服务标准体系建设方案(2017-2020年)》的通知[EB/OL]. (2017-07-28)[2022-12-07]. http://jtyst.zj.gov.cn/art/2017/7/28/art_1676763_42409629.html.
[2]   张会云, 张琳琳 后疫情时代的“无接触配送”服务[J]. 综合运输, 2021, 43 (8): 102- 106
ZHANG Hui-yun, ZHANG Lin-lin "Contactless distribution" service in the post epidemic era[J]. Comprehensive Transportation, 2021, 43 (8): 102- 106
[3]   DANTZIG G B, RAMSER J H The truck dispatching problem[J]. Management Science, 1959, 6 (1): 80- 91
doi: 10.1287/mnsc.6.1.80
[4]   刘云忠, 宣慧玉 车辆路径问题的模型及算法研究综述[J]. 管理工程学报, 2005, 19 (1): 124- 130
LIU Yun-zhong, XUAN Hui-yu A survey of vehicle routing problem models and algorithms[J]. Journal of Management Engineering, 2005, 19 (1): 124- 130
doi: 10.3969/j.issn.1004-6062.2005.01.027
[5]   李浩然 车辆路径优化问题综述[J]. 信息与电脑: 理论版, 2022, 34 (3): 27- 30
LI Hao-ran Overview of vehicle routing optimization[J]. Information and Computer: Theoretical Edition, 2022, 34 (3): 27- 30
[6]   SOLOMON M M Algorithms for the vehicle routing and scheduling problems with time window constraints[J]. Operations Research, 1987, 35 (2): 254- 265
doi: 10.1287/opre.35.2.254
[7]   KANG K H, LEE B K, LEE Y H, et al A heuristic for the vehicle routing problem with discrete split deliveries and time windows[J]. European Journal of Operational Research, 2011, 213 (3): 470- 477
doi: 10.1016/j.ejor.2011.03.023
[8]   HOMBERGER J, GEHRING H Two evolutionary metaheuristics for the vehicle routing problem with time windows[J]. Information Systems and Operational Research, 1999, 37 (3): 297- 318
doi: 10.1080/03155986.1999.11732386
[9]   FAN H, REN X X, ZHANG Y G, et al A chaotic genetic algorithm with variable neighborhood search for solving time-dependent green VRPTW with fuzzy demand[J]. Symmetry, 2022, 14 (10): 1- 18
[10]   CONRAD R G, FIGLIOZZI M A The recharging vehicle routing problem[J]. Proceedings of IIE Annual Conference, 2011, 1: 1- 8
[11]   郭戈, 张振琳 电动车辆路径优化研究与进展[J]. 控制与决策, 2018, 33 (10): 1729- 1739
GUO Ge, ZHANG Zhen-lin Research and development of electric vehicle routing optimization[J]. Control and Decision Making, 2018, 33 (10): 1729- 1739
doi: 10.13195/j.kzyjc.2017.1448
[12]   郭放, 杨珺, 杨超 基于货物分类配送的电动汽车路径优化与换电策略研究[J]. 运筹与管理, 2018, 27 (9): 33- 44
GUO Fang, YANG Jun, YANG Chao Research on route optimization and power exchange strategy of electric vehicles based on cargo classification and distribution[J]. Operations Research and Management, 2018, 27 (9): 33- 44
[13]   肖建华, 王超文, 陈萍, 等 基于城市道路限行的多能源多车型车辆路径优化[J]. 系统工程理论与实践, 2017, 37 (5): 1339- 1348
XIAO Jian-hua, WANG Chao-wen, CHEN Ping, et al Multi energy and multi vehicle routing optimization based on urban road restriction[J]. System Engineering Theory and Practice, 2017, 37 (5): 1339- 1348
doi: 10.12011/1000-6788(2017)05-1339-10
[14]   DESAULNIERS G, ERRICO F, IRNICH S, et al Exact algorithms for electric vehiclerouting problems with time windows[J]. Operations Research, 2016, 64 (6): 1388- 1405
doi: 10.1287/opre.2016.1535
[15]   YE C, HE W J, CHEN H Q Electric vehicle routing models and solution algorithms in logistics distribution: a systematic review[J]. Environmental Science and Pollution Research International, 2022, 29 (38): 57067- 57090
doi: 10.1007/s11356-022-21559-2
[16]   ALEXIOU D, KATSAVOUNIS S A multi-objective transportation routing problem[J]. Operational Research, 2015, 15 (2): 199- 211
doi: 10.1007/s12351-015-0173-1
[17]   CALVET L, FERRER A, GOMES M I, et al Combining statistical learning with metaheuristics for the multi-depot vehicle routing problem with market segmentation[J]. Computers and Industrial Engineering, 2016, 94: 93- 10
doi: 10.1016/j.cie.2016.01.016
[18]   马向国, 刘同娟, 杨平哲, 等 基于随机需求的冷链物流车辆路径优化模型[J]. 系统仿真学报, 2016, 28 (8): 1824- 1832
MA Xiang-guo, LIU Tong-juan, YANG Ping-zhe, et al Vehicle routing optimization model of cold chain logistics based on random demand[J]. Journal of System Simulation, 2016, 28 (8): 1824- 1832
doi: 10.16182/j.cnki.joss.2016.08.017
[19]   杨培颖, 唐加福, 于洋, 等 面向最小碳排放量的接送机场服务的车辆路径与调度[J]. 自动化学报, 2013, 4: 367- 369
YANG Pei-ying, TANG Jia-fu, YU Yang, et al Vehicle routing and dispatching for airport service with minimum carbon emissions[J]. Journal of Automation, 2013, 4: 367- 369
[20]   王力锋, 黄斐 考虑客户等级划分的多目标冷链物流配送优化[J]. 计算机仿真, 2022, 39 (9): 492- 496
WANG Li-feng, HUANG fei Multi objective cold chain logistics distribution optimization considering customer hierarchy[J]. Computer Simulation, 2022, 39 (9): 492- 496
[21]   MALANDRAKI C, DASKIN M S Time dependent vehicle routing problems: formulations, properties and heuristic algorithms[J]. Transportation Science, 1992, 26 (3): 185- 200
doi: 10.1287/trsc.26.3.185
[22]   刘长石, 申立智, 盛虎宜, 等 考虑交通拥堵规避的低碳时变车辆路径问题研究[J]. 控制与决策, 2020, 35 (10): 2486- 2496
LIU Chang-shi, SHEN Li-zhi, SHENG Hu-yi, et al Research on low-carbon time-varying vehicle routing problem considering traffic congestion avoidance[J]. Control and Decision, 2020, 35 (10): 2486- 2496
doi: 10.13195/j.kzyjc.2019.0257
[23]   葛显龙, 冉小芬 考虑时变交通拥堵的污染路径优化研究[J]. 工业工程与管理, 2020, 25 (3): 75- 85
GE Xian-long, RAN Xiao-fen Study on pollution path optimization considering time-varying traffic congestion[J]. Industrial Engineering and Management, 2020, 25 (3): 75- 85
doi: 10.19495/j.cnki.1007-5429.2020.03.010
[24]   KESKIN M, CATAY B Partial recharge strategies for three electric vehicle routing problem with time windows[J]. Transportation Review, 2016, 89 (5): 111- 127
[25]   ROBERTI R, WEN M The electric traveling salesman problem with time windows[J]. Transportation Research Part E-Logistics and Transportation Review, 2016, 89 (5): 32- 52
[26]   张晓楠, 王陆宇, 谭昕妮, 等 时变条件下道路网的车辆路径优化[J]. 机械科学与技术, 2023, 42 (2): 1- 9
ZHANG Xiao-nan, WANG Lu-yu, TAN Xin-ni, et al Time-dependent vehicle routing problem under road network[J]. Mechanical Science and Technology, 2023, 42 (2): 1- 9
doi: 10.13433/j.cnki.1003-8728.20220230
[27]   刘秋萍. 考虑客户等级划分的多目标冷链物流配送车辆路径优化[D]. 镇江: 江苏大学, 2019: 1-92.
LIU Qiu-ping. Multi objective cold chain logistics distribution vehicle routing optimization considering customer ranking [D]. Zhenjiang: Jiangsu University, 2019: 1-92.
[28]   范定国, 贺硕, 段富, 等 一种基于云模型的综合评判模型[J]. 科技情报开发与经济, 2003, 12: 157- 159
FAN Ding-guo, HE Shuo, DUAN Fu, et al A comprehensive evaluation model based on cloud-based model[J]. Science and Technology Information Development and Economy, 2003, 12: 157- 159
[29]   刘杰, 王宇, 李文立 基于云模型的商家信誉综合评价方法[J]. 大连理工大学学报: 社会科学版, 2017, 38 (1): 88- 93
LIU Jie, WANG Yu, LI Wen-li Comprehensive evaluation method of business reputation based on cloud-based model[J]. Journal of Dalian University of Technology: Social Science Edition, 2017, 38 (1): 88- 93
[30]   METROPOLIS N, ULAM S The Monte Carlo method[J]. Journal of the American Statistical Association, 1949, 44 (247): 335- 341
doi: 10.1080/01621459.1949.10483310
[31]   HOLLAND J H. Adaptation in nature and artificial systems [M]. Cambridge: MITP, 1992: 1-211.
[32]   贾永基, 丁慧娜, 李嘉, 等 考虑时变速度和动态需求的电动车辆路径问题[J]. 工业工程与管理, 2022, 27 (2): 59- 66
JIA Yong-ji, DING Hui-na, LI Jia, et al Electric vehicle routing problem considering time-varying speed and dynamic demand[J]. Industrial Engineering and Management, 2022, 27 (2): 59- 66
doi: 10.19495/j.cnki.1007-5429.2022.02.008
No related articles found!