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.
Fig.3Schematic diagram of ethnic group distribution
Fig.4Schematic diagram of leapfrog search
Fig.5Schematic diagram of customer interchange
Fig.6Schematic diagram of customer relocation
车辆编号
车辆路径
装载率/%
费用
总费用
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
Tab.1Optimal vehicle delivery solution
Fig.7Calculation results for optimal path of IHSFLA
Fig.8Evolution curve of IHSFLA
Fig.9Calculation results for optimal path of multi-chromosome genetic algorithm
算法
均值/元
标准差/元
多染色体遗传算法[22]
9178
563
单染色体遗传算法[22]
11804
790
粒子群算法[22]
11015
612
改进混合蛙跳算法
8290
173
Tab.2Comparison of cost of optimal path obtained by different algorithms
客户编号
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
Tab.3Customer information table
配送 中心
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
Tab.4delivery center information table
Fig.10Initial solution mass distribution
Fig.11Evolution curve of three ways
车辆编号
车辆路径
装载率/%
费用
总费用
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
Tab.5Optimal vehicle delivery solution
Fig.12Optimal roadmap considering product costs
Fig.13Optimal roadmap without considering product costs
算法
最小值/元
最大值/元
均值/元
标准差/元
时间/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
Tab.6Statistics of experimental results of four algorithms
Fig.14Average evolution curve of four algorithms
[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.
