Please wait a minute...
浙江大学学报(工学版)
浙江大学学报(工学版)  2021, Vol. 55 Issue (2): 259-270    DOI: 10.3785/j.issn.1008-973X.2021.02.006
机械工程     
基于改进混合蛙跳算法的多约束车辆路径优化
鲁建厦(),翟文倩,李嘉丰,易文超,汤洪涛
浙江工业大学 机械工程学院，浙江 杭州 310023
Multi-constrained vehicle routing optimization based on improved hybrid shuffled frog leaping algorithm
Jian-sha LU(),Wen-qian ZHAI,Jia-feng LI,Wen-chao YI,Hong-tao TANG
College of Mechanical Engineering, Zhejiang University of Technology, Hangzhou 310023, China
 全文: PDF(1763 KB)   HTML
摘要：

针对多中心分布式企业存在的产品成本差异化问题，建立包括产品成本、多车场、多车型在内的多约束车辆路径模型，并设计求解该模型的改进混合蛙跳算法. 根据问题特性，改进聚类算法并结合邻近矩阵构造初始青蛙种群；提出子群概念，设计自内而外的交流演化模式；定义远离矩阵，对青蛙进行引导性邻域搜索. 将所设计的算法进行多组不同的对比实验，结果表明，所设计的算法通用性强，实用性高，与遗传算法、蚁群算法这类传统经典算法相比，具有更好的收敛速度与求解精度，可以有效解决此类问题；考虑产品成本的调度方案总成本平均减少6%，占产品总成本的13%，可以为企业提供更合理的车辆配送方案.
关键词： 产品成本;  混合蛙跳算法;  多车场;  多车型;  车辆路径    
Abstract:

Aiming at the product cost differentiation problem of multi-center distributed enterprises, a multi-constrained vehicle routing model including product cost, multi-depot and heterogeneous vehicle was established, and an improved hybrid shuffled frog leaping algorithm was designed to solve the problem. The initial frog population was constructed by improved clustering algorithm and adjacency matrix according to the characteristics of the problem. The concept of subgroup was proposed to design the evolution model of communication from inside to outside. The guided local search was performed in the subgroups according to the distance matrix. The designed algorithm was subjected to many different sets of comparative experiments. Results show that the designed algorithm is highly versatile and practical. Compared with traditional classical algorithms such as genetic algorithm and ant colony algorithm, it has better convergence speed and accuracy, which can effectively solve the problems. The total cost of the solution considering the product cost was reduced by an average of 6%, accounting for 13% of the total product cost, which can provide more reasonable vehicle distribution plan for enterprises.
Key words: product cost    hybrid shuffled frog leaping algorithm    multi-depot    heterogeneous vehicle    vehicle scheduling
收稿日期: 2020-07-07 出版日期: 2021-03-09
CLC:  TP 301.6  
基金资助: 国家重点研发计划资助项目(2018YFB1308100)；浙江省重点研发计划资助项目(2018C01003)；浙江省自然科学基金资助项目(LY15G010009)
作者简介: 鲁建厦（1963—），男，教授，博导，从事智能物流、物流装备和精益生产研究. orcid.org/0000-0001-5793-3328. E-mail： ljs@zjut.edu.cn
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
作者相关文章　　
鲁建厦
翟文倩
李嘉丰
易文超
汤洪涛

引用本文:

鲁建厦,翟文倩,李嘉丰,易文超,汤洪涛. 基于改进混合蛙跳算法的多约束车辆路径优化[J]. 浙江大学学报(工学版), 2021, 55(2): 259-270.

Jian-sha LU,Wen-qian ZHAI,Jia-feng LI,Wen-chao YI,Hong-tao TANG. Multi-constrained vehicle routing optimization based on improved hybrid shuffled frog leaping algorithm. Journal of ZheJiang University (Engineering Science), 2021, 55(2): 259-270.

链接本文:

http://www.zjujournals.com/eng/CN/10.3785/j.issn.1008-973X.2021.02.006    或    http://www.zjujournals.com/eng/CN/Y2021/V55/I2/259

图 1  车辆配送示意图
图 2  距离的4种计算方式
图 3  族群分配示意图
图 4  蛙跳搜索示意图
图 5  客户互换示意图
图 6  客户搬迁示意图
车辆编号 车辆路径 装载率/% 费用 总费用
31 A-A 0 0 8019
32 A-8-7-16 72.31 794 8019
33 A-A 0 0 8019
34 B-6-14-10-11-3-B 94.62 1586 8019
35 B-15-17-5-21-B 73.85 830 8019
36 B-13-24-19-29-9-B 95.38 1322 8019
37 C-12-25-22-1-C 86.92 1178 8019
38 C-23-18-27-26-C 96.67 1303 8019
39 C-28-C 23.00 200 8019
40 C-2-20-4-30-C 92.31 806 8019
表 1  最优车辆配送方案
图 7  IHSFLA最优路径计算结果
图 8  IHSFLA计算进化曲线
图 9  多染色体遗传算法计算结果
算法 均值/元 标准差/元
多染色体遗传算法[22] 9178 563
单染色体遗传算法[22] 11804 790
粒子群算法[22] 11015 612
改进混合蛙跳算法 8290 173
表 2  不同算法求得的最优路径的费用比较
客户编号 r X Y 客户编号 r X Y
1 37 52 7 26 27 68 7
2 49 49 30 27 30 48 15
3 52 64 16 28 43 67 14
4 20 26 9 29 58 48 6
5 40 30 21 30 58 27 19
6 21 47 15 31 37 69 11
7 17 63 19 32 38 46 12
8 31 62 23 33 46 10 23
9 52 33 11 34 61 33 26
10 51 21 5 35 62 63 17
11 42 41 19 36 63 69 6
12 31 32 29 37 32 22 9
13 5 25 23 38 45 35 15
14 12 42 21 39 59 15 14
15 36 16 10 40 5 6 7
16 52 41 15 41 10 17 27
17 27 23 3 42 21 10 13
18 17 33 41 43 5 64 11
19 13 13 9 44 30 15 16
20 57 58 28 45 39 10 10
21 62 42 8 46 32 39 5
22 42 57 8 47 25 32 25
23 16 57 16 48 25 55 17
24 8 52 10 49 48 28 18
25 7 38 28 50 56 37 10
表 3  客户信息表
配送
中心 		X Y h 车辆
类型 		Ch βh αh Qh
A 20 20 51 Ⅰ 10 7 5 70
A 20 20 52 Ⅱ 11 8 5 80
A 20 20 53 Ⅲ 12 9 5 90
B 30 40 54 Ⅱ 11 8 6 80
B 30 40 55 Ⅱ 11 8 6 80
B 30 40 56 Ⅰ 10 7 6 70
B 30 40 57 Ⅲ 12 9 6 90
C 50 30 58 Ⅰ 10 7 7 70
C 50 30 59 Ⅱ 11 8 7 80
C 50 30 60 Ⅱ 11 8 7 80
D 60 50 61 Ⅱ 11 8 8 80
D 60 50 62 Ⅲ 12 9 8 90
D 60 50 63 Ⅱ 11 8 8 80
表 4  配送中心信息表
图 10  初始解质量分布图
图 11  3种方式的进化曲线图
车辆编号 车辆路径 装载率/% 费用 总费用
51 A-37-15-33-45-44-A 97.14 856.6 10743
52 A-42-19-40-41-13-A 98.75 1037.4 10743
53 A-4-18-12-17-A 91.11 936.1 10743
54 B-23-24-43-7-26-48-B 100.00 1358.1 10743
55 B-32-22-2-11-46-B 92.50 997.2 10743
56 B-27-8-31-28-1-B 100.00 993.4 10743
57 B-6-14-25-47-B 98.89 1162.5 10743
58 C-34-21-50-16-9-C 100.00 908.7 10743
59 C-10-39-30-C 47.50 693.2 10743
60 C-38-5-49-C 67.50 689.7 10743
61 D-29-20-3-36-35-D 91.25 1110.1 10743
62 D-D 0 0 10743
63 D-D 0 0 10743
表 5  最优车辆配送方案
图 12  考虑产品成本的最优路线图
图 13  不考虑产品成本的最优路线图
算法 最小值/元 最大值/元 均值/元 标准差/元 时间/s
IHSFLA 10743 11140 10860 124 78.2
SFLA 12329 12931 12690 228 90.3
SRCLBFO 11308 11824 11512 189 84.3
EACO 11041 11536 11307 158 66.8
表 6  4种算法实验结果统计
图 14  4种算法的平均进化曲线
1 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
2 FLORIAN A, KENNETH S Knowledge-guided local search for the vehicle routing problem[J]. Computers and Operations Research, 2019, 105: 32- 46
doi: 10.1016/j.cor.2019.01.002
3 SALHI S, SARI M A multi-level composite heuristic for the multi-depot vehicle fleet mix problem[J]. European Journal of Operational Research, 1997, 103 (1): 95- 112
doi: 10.1016/S0377-2217(96)00253-6
4 SALHI S, WASSAN N, HAJARAT M The fleet size and mix vehicle routing problem with backhauls: formulation and set partitioning-based heuristics[J]. Transportation Research Part E: Logistics and Transportation Review, 2013, 56: 22- 35
doi: 10.1016/j.tre.2013.05.005
5 SUNDAR K, VENKATACHALAM S, RATHINAM S. Formulations and algorithms for the multiple-depot, fuel-constrained, multiple vehicle routing problem [C]// American Control Conference 2016. Boston: ACC, 2016: 66-91.
6 LUO J, CHEN M R Multi-phase modified shuffled frog leaping algorithm with extremal optimization for the MDVRP and the MDVRPTW[J]. Computers and Industrial Engineering, 2014, 72: 84- 97
doi: 10.1016/j.cie.2014.03.004
7 DAYARIAN I, CRAINIC T G, GENDREAU M, et al A column generation approach for a multi-attribute vehicle routing problem[J]. European Journal of Operational Research, 2015, 241 (3): 888- 906
doi: 10.1016/j.ejor.2014.09.015
8 CALVET L, FERRER A, GOMES M, 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- 104
doi: 10.1016/j.cie.2016.01.016
9 DE OLIVEIRA F B, ENAYATIFA R, SADAEI H J, et al A cooperative coevolutionary algorithm for the multi-depot vehicle routing problem[J]. Expert System with Applications, 2016, 54: 398- 402
doi: 10.1016/j.eswa.2016.02.037
10 CALVET L, WANG D, JUAN A, et al Solving the multidepot vehicle routing problem with limited depot capacity and stochastic demands[J]. International Transactions in Operation Research, 2019, 26 (2): 458- 484
doi: 10.1111/itor.12560
11 杨烨. 带时间窗的单车场多车型满载车辆调度问题研究[D]. 淄博: 山东理工大学, 2013.
YANG Ye. Study on single-depot, multi-type vehicle and full-loads vehicle routing problem with time window [D]. Zibo: Shandong University of Technology, 2013.
12 叶勇, 张惠珍 多配送中心车辆路径问题的狼群算法[J]. 计算机应用研究, 2017, 34 (9): 2590- 2593
YE Yong, ZHANG Hui-zhen Wolf pack algorithm for multi-depot vehicle routing problem[J]. Application Research of Computers, 2017, 34 (9): 2590- 2593
doi: 10.3969/j.issn.1001-3695.2017.09.006
13 马宇红, 姚婷婷, 张芳芳 多车场多车型车辆调度问题及其遗传算法[J]. 数学的实践与认识, 2014, 44 (2): 107- 114
MA Yu-hong, YAO Ting-ting, ZHANG Fang-fang Multi-depot heterogeneous vehicle scheduling problem based on genetic algorithm[J]. Mathematics in Practice and Theory, 2014, 44 (2): 107- 114
doi: 10.3969/j.issn.1000-0984.2014.02.013
14 刘丽姣. 考虑碳排放的多车场多车型VRP模型及算法研究[D]. 深圳: 深圳大学, 2017.
LIU Li-jiao. Considering carbon emission for multi-depot heterogeneous VRP model and algorithmsresearch [D]. Shenzhen: Shenzhen University, 2017.
15 何东东, 李引珍 多车型绿色车辆路径问题优化模型[J]. 计算机应用, 2018, 38 (12): 3618- 3624
HE Dong-dong, LI Yin-zhen Optimization model of green multi-type vehicles routing problem[J]. Journal of Computer Applications, 2018, 38 (12): 3618- 3624
16 BARADARAN V, SHAFEEI A, HOSSEINIAN A H Stochastic vehicle routing problem with heterogeneous vehicles and multiple prioritized time windows: mathematical modeling and solution approach[J]. Computers and Industrial Engineering, 2019, 131: 187- 199
doi: 10.1016/j.cie.2019.03.047
17 杨翔, 范厚明, 徐振林, 等 模糊需求下多中心开放式车辆路径优化[J]. 计算机集成制造系统, 2019, 25 (2): 469- 479
YANG Xiang, FAN Hou-ming, XV Zhen-lin, et al Optimization of open multi-depot vehicle routing problemwith fuzzy demand[J]. Computer Integrated Manufacturing Systems, 2019, 25 (2): 469- 479
18 鲁建厦, 洪欢蕾, 陈青丰 考虑供给商品价格的多车场车辆路径问题[J]. 浙江工业大学学报, 2016, 44 (5): 553- 558
LU Jian-sha, HONG Huan-lei, CHEN Qing-feng Model and algorithm for multiple-depot vehicle routing problem with different supply costs[J]. Journal of Zhejiang University of Technology, 2016, 44 (5): 553- 558
doi: 10.3969/j.issn.1006-4303.2016.05.017
19 ARNOLD F, SORENSEN K What makes a VRP solution good? The generation of problem-specific knowledge for heuristics[J]. Computers and Operations Research, 2019, 106: 280- 288
doi: 10.1016/j.cor.2018.02.007
20 EUSUFF M M, LANSEY K E Optimization of water distribution network design using the shuf?ed frog leaping algorithm[J]. Journal of Water Resources Planning and Management, 2003, 129 (3): 210- 225
doi: 10.1061/(ASCE)0733-9496(2003)129:3(210)
21 LUO J, LI X, CHEN M R, et al A novel hybrid shuffled frog leaping algorithm for vehicle routing problem with time windows[J]. Information Sciences, 2015, 316: 266- 292
doi: 10.1016/j.ins.2015.04.001
22 杨冬婧, 雷德明 新型蛙跳算法求解总能耗约束FJSP[J]. 中国机械工程, 2018, 29 (22): 2682- 2689
YANG Dong-jing, LEI De-ming A novel shuffled frog-leaping algorithm for FJSP with total energy consumption constraints[J]. China Mechanical Engineering, 2018, 29 (22): 2682- 2689
doi: 10.3969/j.issn.1004-132X.2018.22.005
23 GIOSA I D, TANSINI I L, VIERA I O New assignment algorithms for the multi-depot vehicle routing problem[J]. Journal of the Operational Research Society, 2002, 53 (9): 977- 984
doi: 10.1057/palgrave.jors.2601426
24 陈呈频, 韩胜军, 鲁建厦, 等 多车场与多车型车辆路径问题的多染色体遗传算法[J]. 中国机械工程, 2018, 29 (2): 218- 223
CHEN Cheng-pin, HAN Sheng-jun, LU Jian-sha, et al Multi-chromosome genetic algorithm for multi-depot and multi-type vehicle routing problems[J]. China Mechanical Engineering, 2018, 29 (2): 218- 223
doi: 10.3969/j.issn.1004-132X.2018.02.014
25 李小川, 刘媛华, 王影歌 求解多目标带时间窗VRP的文化狼群算法[J]. 计算机应用研究, 2020, 37 (4): 1025- 1029
LI Xiao-chuan, LIU Yuan-hua, WANG Ying-ge Cultural wolf pack algorithm for solving multi-objective VRP with time window[J]. Application Research of Computers, 2020, 37 (4): 1025- 1029
26 骆剑平, 李霞, 陈泯融 混合蛙跳算法的Markov模型及其收敛性分析[J]. 电子学报, 2010, 38 (12): 2875- 2880
LUO Jian-pin, LI Xia, CHEN Min-Rong The Markov model of shuffled frog leaping algorithm and its convergence analysis[J]. Acta Electronica Sinica, 2010, 38 (12): 2875- 2880
27 韩胜军. 多车场多车型车辆路径问题的多染色体遗传算法[D]. 杭州: 浙江工业大学, 2017.
HAN Sheng-jun. Multi-chromosome genetic algorithm for multi-depot and multi-type vehicle routing problems [D]. Hangzhou: Zhejiang University of Technology, 2017.
28 孟凯露, 尚俊娜, 岳克强 混合蛙跳算法的最优参数研究[J]. 计算机应用研究, 2019, 36 (11): 3321- 3324
MENG Kai-lu, SHANG Jun-na, YUE Ke-qiang Research on optimal parameters of shuffled frog leaping algorithm[J]. Application Research of Computers, 2019, 36 (11): 3321- 3324
29 胡蓉, 李洋, 钱斌, 等. 结合聚类分解的增强蚁群算法求解复杂绿色车辆路径问题[J/OL]. 自动化学报, 2020: 1-16 [2020-08-14]. https://doi.org/10.16383/j.aas.c190872.
HU Rong, LI Yang, QIAN Bin, et al. An enhanced ant colony algorithm combined with clustering decomposition for solving complex green vehicle routing problem [J/OL]. Acta Automatica Sinica, 2020: 1-16 [2020-08-14]. https://doi.org/10.16383/j.aas.c190872.
[1] 付晓峰,牛力,胡卓群,李建军,吴卿. 基于过渡帧概念训练的微表情检测深度网络[J]. 浙江大学学报(工学版), 2020, 54(11): 2128-2137.
[2] 董立岩, 朱琪, 李永丽. 基于最大共识的模型组合算法[J]. 浙江大学学报(工学版), 2017, 51(2): 416-421.
[3] 苗峰,谢安桓,王富安,喻峰,周华. 多阶段可替换分组并行机调度问题的求解[J]. 浙江大学学报(工学版), 2015, 49(5): 866-872.
[4] 倪广翼, 章孝灿, 苏程, 俞伟斌. 基于多染色体演化的自适应类别数聚类方法[J]. 浙江大学学报(工学版), 2014, 48(6): 980-986.
[5] 孔勇奇, 潘志庚. 基于抽风矢量场的深度凹陷图像分割算法[J]. 浙江大学学报(工学版), 2014, 48(6): 1024-1033.
[6] 刘加海,杨茂林,雷航,廖勇. 共享资源约束下多核实时任务分配算法[J]. J4, 2014, 48(1): 113-117.
[7] 赵诗奎, 方水良, 顾新建. 柔性车间调度的新型初始机制遗传算法[J]. J4, 2013, 47(6): 1022-1030.
[8] 张俊超, 岳茂雄, 刘华锋. 结构先验约束的动态PET图像重建[J]. J4, 2012, 46(6): 961-966.
[9] 刘毅,李平,高增梁. 用于高炉铁水质量预报的改进支持向量回归[J]. J4, 2012, 46(5): 830-836.
[10] 方水良, 姚嫣菲, 赵诗奎. 柔性车间调度的改进遗传算法[J]. J4, 2012, 46(4): 629-635.
[11] 喻海清, 刘毅, 陈坤, 纪俊, 李平. 鲁棒的递推核学习建模方法在高炉过程的应用[J]. J4, 2012, 46(4): 705-711.
[12] 刘加海,杨茂林. 基于多核处理器平台的公平调度算法[J]. J4, 2011, 45(9): 1566-1570.
[13] 徐敬华, 张树有, 伊国栋, 屠立, 光耀. 面向目标变异的操作臂运动学优化设计[J]. J4, 2011, 45(2): 209-216.
[14] 倪何, 程刚, 孙丰瑞. 基于混合演化的自适应建模及其应用[J]. J4, 2010, 44(8): 1490-1495.
[15] 戴文战, 熊伟, 杨爱萍. 基于函数cot (xα)变换及背景值优化的灰色建模[J]. J4, 2010, 44(7): 1368-1372.