Please wait a minute...
浙江大学学报(工学版)
浙江大学学报(工学版)  2023, Vol. 57 Issue (10): 2018-2027    DOI: 10.3785/j.issn.1008-973X.2023.10.011
计算机技术、自动化技术     
考虑客户等级和时变路况的无人物流配送路径
李家碧1(),韩曙光2,*()
1. 浙江理工大学 经济管理学院，浙江 杭州 310018
2. 浙江理工大学 理学院，浙江 杭州 310018
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
 全文: PDF(1230 KB)   HTML
摘要：

针对物流企业因配送资源的有限、无法及时应对客户的多样化需求和道路状况的不断变化等难题，建立时变道路状况和时间窗关联的无人车配送路径优化数学模型。通过云模型将客户划分为3个等级，以车辆配送成本、未满足客户配送时间的惩罚成本、车辆充电成本的总和极小化作为优化目标函数. 在遗传算法的基础上，结合模拟退火算法构造混合算法，对模型进行求解并验证正确性. 根据模型的特性构造9组不同规模和类型的算例进行数值实验，并验证算法的有效性. 实验结果表明，混合遗传-模拟退火算法下配送过程中产生的总配送成本最多能够节省42.81%，整体客户满意度最高提升80.23%，提出混合遗传-模拟退火算法能够在有效降低成本的基础上，最大程度提升客户的满意度，并且相较于2种传统算法，其优化效果更好.
关键词： 客户等级;  时变路况;  无人物流配送;  混合遗传-模拟退火算法;  云模型    
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
收稿日期: 2022-12-07 出版日期: 2023-10-18
CLC:  O 221.2  
基金资助: 国家自然科学基金资助项目（12071436）
通讯作者: 韩曙光     E-mail: 18940904238@163.com;dawn1024@zstu.edu.cn
作者简介: 李家碧（1998—），女，硕士生，从事无人城市物流的模型与算法研究. orcid.org/0000-0002-0079-5566. E-mail： 18940904238@163.com
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
作者相关文章　　
李家碧
韩曙光

引用本文:

李家碧,韩曙光. 考虑客户等级和时变路况的无人物流配送路径[J]. 浙江大学学报(工学版), 2023, 57(10): 2018-2027.

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.

链接本文:

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

图 1  考虑客户等级和时变路况的城市无人物流配送示意图
图 2  配送客户的价值评价指标体系
客户等级 普通客户 主要客户 VIP客户
评价值区间 [0, 5] [5, 8] [8, 10]
评价云模型 （2.5, 0.833, 0.1） （6.5, 0.5, 0.1） （9, 0.333, 0.1）
表 1  客户等级评价云模型相关数字特征值
图 3  遗传-模拟退火算法的优化流程图
图 4  车辆在不同时间段的行驶速度
测试算例 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
表 2  不同方法以成本最小为目标的优化结果
测试算例 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
表 3  不同方法考虑客户满意度的优化结果
图 5  车辆数对成本优化结果的影响
图 6  不同路况对成本与满意度的优化影响
图 7  客户满意度对成本优化结果的影响
图 8  电动车辆的路径结果
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
[1] 裴卉宁,谭昭芸,刘鑫宇,田保珍. 基于单值中智集和云聚类的产品造型设计决策方法[J]. 浙江大学学报(工学版), 2022, 56(12): 2367-2378.
[2] 颉芳弟,翟强,顾伟红. 基于动态贝叶斯网络的TBM卡机风险预测[J]. 浙江大学学报(工学版), 2021, 55(7): 1339-1350.
[3] 许翔, 黄侨, 任远. 局部变权和云理论在悬索桥综合评估中的应用[J]. 浙江大学学报(工学版), 2017, 51(8): 1544-1550.