Please wait a minute...
浙江大学学报(工学版)
Journal of ZheJiang University (Engineering Science)  2021, Vol. 55 Issue (2): 259-270    DOI: 10.3785/j.issn.1008-973X.2021.02.006
    
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
Download: HTML     PDF(1763KB) HTML
Export: BibTeX | EndNote (RIS)      

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     
Received: 07 July 2020      Published: 09 March 2021
CLC:  TP 301.6  
Fund:  国家重点研发计划资助项目(2018YFB1308100)；浙江省重点研发计划资助项目(2018C01003)；浙江省自然科学基金资助项目(LY15G010009)
Service
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
RSS
Articles by authors
Jian-sha LU
Wen-qian ZHAI
Jia-feng LI
Wen-chao YI
Hong-tao TANG
Cite this article:

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.

URL:

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


基于改进混合蛙跳算法的多约束车辆路径优化

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


关键词： 产品成本,  混合蛙跳算法,  多车场,  多车型,  车辆路径 
Fig.1 Schematic diagram of vehicle distribution
Fig.2 Four calculation methods of distance
Fig.3 Schematic diagram of ethnic group distribution
Fig.4 Schematic diagram of leapfrog search
Fig.5 Schematic diagram of customer interchange
Fig.6 Schematic 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.1 Optimal vehicle delivery solution
Fig.7 Calculation results for optimal path of IHSFLA
Fig.8 Evolution curve of IHSFLA
Fig.9 Calculation results for optimal path of multi-chromosome genetic algorithm
算法 均值/元 标准差/元
多染色体遗传算法[22] 9178 563
单染色体遗传算法[22] 11804 790
粒子群算法[22] 11015 612
改进混合蛙跳算法 8290 173
Tab.2 Comparison 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.3 Customer 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.4 delivery center information table
Fig.10 Initial solution mass distribution
Fig.11 Evolution 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.5 Optimal vehicle delivery solution
Fig.12 Optimal roadmap considering product costs
Fig.13 Optimal 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.6 Statistics of experimental results of four algorithms
Fig.14 Average 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.
[1] Xiao-feng FU,Li NIU,Zhuo-qun HU,Jian-jun LI,Qing WU. Deep micro-expression spotting network training based on concept of transition frame[J]. Journal of ZheJiang University (Engineering Science), 2020, 54(11): 2128-2137.
[2] DONG Li yan, ZHU Qi, LI Yong li. Model combination algorithm based on consensus maximization[J]. Journal of ZheJiang University (Engineering Science), 2017, 51(2): 416-421.
[3] MIAO Feng, XIE An-huan, WANG Fu-an, YU Feng, ZHOU Hua. Method for multi-stage alternative grouping parallel machines scheduling problem[J]. Journal of ZheJiang University (Engineering Science), 2015, 49(5): 866-872.
[4] NI Guang-yi, ZHANG Xiao-can, SU Cheng, YU Wei-bin. Count adaptive clustering algorithm based on multiple-chromosome evolution[J]. Journal of ZheJiang University (Engineering Science), 2014, 48(6): 980-986.
[5] KONG Yong-qi, PAN Zhi-geng. Segmentation algorithm of recessed image based on vector field of suction[J]. Journal of ZheJiang University (Engineering Science), 2014, 48(6): 1024-1033.
[6] LIU Jia-hai, YANG Mao-lin, LEI Hang, LIAO Yong. Multicore real-time task allocation algorithms with shared resource constraints[J]. Journal of ZheJiang University (Engineering Science), 2014, 48(1): 113-117.
[7] ZHAO Shi-kui, FANG Shui-liang, GU Xin-jian. Genetic algorithm with new initialization mechanism for flexible job shop scheduling[J]. Journal of ZheJiang University (Engineering Science), 2013, 47(6): 1022-1030.
[8] ZHANG Jun-chao, YUE Mao-xiong, LIU Hua-feng. Dynamic PET image reconstruction with Geometrical structure
prior constraints[J]. Journal of ZheJiang University (Engineering Science), 2012, 46(6): 961-966.
[9] LIU Yi, LI Ping, GAO Zeng-liang. Quality prediction of hot metal in blast furnace using improved
support vector regression[J]. Journal of ZheJiang University (Engineering Science), 2012, 46(5): 830-836.
[10] FANG Shui-liang, YAO Yan-fei, ZHAO Shi-kui. Improved genetic algorithm for flexible job shop scheduling[J]. Journal of ZheJiang University (Engineering Science), 2012, 46(4): 629-635.
[11] YU Hai-qing, LIU Yi, CHEN Kun, JI Jun1, LI Ping. Robust recursive kernel learning modeling method with
application to blast furnace[J]. Journal of ZheJiang University (Engineering Science), 2012, 46(4): 705-711.
[12] LIU Jia-hai, YANG Mao-lin. Fair scheduling algorithm on multi-core platforms based platforms[J]. Journal of ZheJiang University (Engineering Science), 2011, 45(9): 1566-1570.
[13] XU Jing-hua, ZHANG Shu-you, YI Guo-dong, TU Li, GUANG Yao. Object variation oriented kinematics optimization design
for manipulator[J]. Journal of ZheJiang University (Engineering Science), 2011, 45(2): 209-216.
[14] NI He, Cheng-Gang, SUN Feng-Rui. Adaptive hybrid evolutionary modeling method and its application[J]. Journal of ZheJiang University (Engineering Science), 2010, 44(8): 1490-1495.
[15] DAI Wen-Zhan, XIONG Wei, YANG Ai-Ping. Grey modeling based on cot (xα) transformation
and background value optimization[J]. Journal of ZheJiang University (Engineering Science), 2010, 44(7): 1368-1372.