|
|
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 |
|
|
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.
|
Received: 07 July 2020
Published: 09 March 2021
|
|
Fund: 国家重点研发计划资助项目(2018YFB1308100);浙江省重点研发计划资助项目(2018C01003);浙江省自然科学基金资助项目(LY15G010009) |
基于改进混合蛙跳算法的多约束车辆路径优化
针对多中心分布式企业存在的产品成本差异化问题,建立包括产品成本、多车场、多车型在内的多约束车辆路径模型,并设计求解该模型的改进混合蛙跳算法. 根据问题特性,改进聚类算法并结合邻近矩阵构造初始青蛙种群;提出子群概念,设计自内而外的交流演化模式;定义远离矩阵,对青蛙进行引导性邻域搜索. 将所设计的算法进行多组不同的对比实验,结果表明,所设计的算法通用性强,实用性高,与遗传算法、蚁群算法这类传统经典算法相比,具有更好的收敛速度与求解精度,可以有效解决此类问题;考虑产品成本的调度方案总成本平均减少6%,占产品总成本的13%,可以为企业提供更合理的车辆配送方案.
关键词:
产品成本,
混合蛙跳算法,
多车场,
多车型,
车辆路径
|
|
[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.
|
|
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
|
Shared |
|
|
|
|
|
Discussed |
|
|
|
|