改进智能水滴算法求解混合时间窗车辆路径问题
|
摘要
针对多目标车辆路径问题,研究车载量、配送里程、混合时间窗等限制约束条件下,以最小配送费用和最少配送车辆数为目标建立多目标数学模型。在分析智能水滴算法求解类似离散问题时存在的局限性基础上,运用多种方式对其进行改进,引入遗传算法选择、交叉及重组算子提高其性能,构建出两种改进智能水滴遗传混合算法,并运用Solomon标准对测试算例和实际算例进行验证。比较结果显示,改进后的混合算法能够有效解决离散问题,在持续寻优能力上较传统智能水滴算法和遗传算法更优,并且竞争选择改进智能水滴遗传混合算法求解算例效果最优。
For multi-objective vehicle routing problem,considering the constraints of vehicle volume,delivery mileage and mixed time windows,this paper establishes a multi-objective mathematical model to minimize the cost of distribution and the minimum number of vehicles.Based on the analysis of the limitations of intelligent drop algorithm in solving similar discrete problems,various ways are used to improve it,and the selection,crossover and recombination operators of the genetic algorithm are introduced to improve its performance,two improved intelligent drop genetic hybrid algorithms are constructed,and practical example is designed and compared.The results of the example test show that:the improved intelligent water droplet genetic hybrid algorithm is an effective method to solve the discrete problem,compared with the basic intelligent water drop algorithm,the improved intelligent droplet genetic hybrid algorithm has higher computing efficiency and continuous optimization capability,and the competition selection improves the intelligent droplet genetic hybrid algorithm is the best solution of the example.
For multi-objective vehicle routing problem,considering the constraints of vehicle volume,delivery mileage and mixed time windows,this paper establishes a multi-objective mathematical model to minimize the cost of distribution and the minimum number of vehicles.Based on the analysis of the limitations of intelligent drop algorithm in solving similar discrete problems,various ways are used to improve it,and the selection,crossover and recombination operators of the genetic algorithm are introduced to improve its performance,two improved intelligent drop genetic hybrid algorithms are constructed,and practical example is designed and compared.The results of the example test show that:the improved intelligent water droplet genetic hybrid algorithm is an effective method to solve the discrete problem,compared with the basic intelligent water drop algorithm,the improved intelligent droplet genetic hybrid algorithm has higher computing efficiency and continuous optimization capability,and the competition selection improves the intelligent droplet genetic hybrid algorithm is the best solution of the example.
引文
[l]DANTZIG G B,RAMSER R H.The truck dispatching problem[J].Management Science,1959,10(1):80-91.
[2]SOLOMON M M.Algorithms for the vehicle routing and scheduling problems with time window constraints[J].Operations Research,1987,35(2):254-265.
[3]张媛媛,李建斌.动态车队组合优化模型及精确算法[J].系统工程理论与实践,2007,27(2):83-91.
[4]URSANI Z,ESSAM D,CORNFORTH D,et al.Localized genetic algorithm for vehicle routing problem with time windows[J].Applied Soft Computing,2011,11(8):5375-5390.
[5]GHOSEIRI K,GHANNADPOUR S F.Multi-objective vehicle routing problem with time windows using goal programming and genetic algorithm[J].Applied Soft Computing,2010,10(4):1096-1107.
[6]王旭坪,詹红鑫,孙自来,等.基于蚁群禁忌混合算法的成品油多舱配送路径优化研究[J].系统工程理论与实践,2017,37(12):3215-3226.
[7]陈迎欣.基于改进蚁群算法的车辆路径优化问题研究[J].计算机应用研究,2012,29(6):2031-2034.
[8]李阳,范厚明,张晓楠,等.求解模糊需求车辆路径问题的两阶段变邻域禁忌搜索算法[J].系统工程理论与实践,2018,38(2):522-531.
[9]RENAUD J,LAPORTE G,BOCTOR F F.A tabu search heuristic for the multi-depot vehicle routing problem[J].Computers&Operations Research,1996,23(3):229-235.
[10]YANG X S.A new metaheuristic bat-inspired algorithm[J].Computer Knowledge and Technology,2010,284:65-74.
[11]殷亚,张惠珍.求解带硬时间窗的多目标车辆路径问题的多种混合蝙蝠算法[J].计算机应用研究,2017,(12):1-8.
[12]李妍峰,高自友,李军.基于实时交通信息的城市动态网络车辆路径优化问题[J].系统工程理论与实践,2013,33(7):1813-1819.
[13]李峰,魏莹.易腐货物配送中时变车辆路径问题的优化算法[J].系统工程学报,2010,25(4):492-519.
[14]XIAO Y Y,ZHAO Q H,KAKU I,et al.Development of a fuel consumption optimization model for the capacitated vehicle routing problem[J].Computers&Operations Research,2012,39(7):1419-1431.
[15]SHAH-HOSSEINIH.Problem solving by intelligent water drops[C]//IEEE.2007 IEEE Congress on Evolutionary Computation.Piscataway:IEEE,2007:3226-3231.
[16]王奕璇,陈荔,王涛.基于改进智能水滴算法的混合时间窗电商物流路径优化研究[J].科技管理研究,2018,38(11):211-218.
[17]HOLLAND J H.Adaptation in natural and artificial systems[M].Ann Arbor:University of Michigan Press,1975.
[18]EBERHART R C,KENNEDY J.A new optimizer using particle swarm theory[C]//IEEE.Sixth International Symposium on Micro Machine and Hmm Science(Nagoya,Japan).Piscataway:IEEE,1995:39-43.
[19]马向国,刘同娟,杨平哲,等.基于随机需求的冷链物流车辆路径优化模型[J].系统仿真学报,2016,28(8):1824-1832,1840.
[2]SOLOMON M M.Algorithms for the vehicle routing and scheduling problems with time window constraints[J].Operations Research,1987,35(2):254-265.
[3]张媛媛,李建斌.动态车队组合优化模型及精确算法[J].系统工程理论与实践,2007,27(2):83-91.
[4]URSANI Z,ESSAM D,CORNFORTH D,et al.Localized genetic algorithm for vehicle routing problem with time windows[J].Applied Soft Computing,2011,11(8):5375-5390.
[5]GHOSEIRI K,GHANNADPOUR S F.Multi-objective vehicle routing problem with time windows using goal programming and genetic algorithm[J].Applied Soft Computing,2010,10(4):1096-1107.
[6]王旭坪,詹红鑫,孙自来,等.基于蚁群禁忌混合算法的成品油多舱配送路径优化研究[J].系统工程理论与实践,2017,37(12):3215-3226.
[7]陈迎欣.基于改进蚁群算法的车辆路径优化问题研究[J].计算机应用研究,2012,29(6):2031-2034.
[8]李阳,范厚明,张晓楠,等.求解模糊需求车辆路径问题的两阶段变邻域禁忌搜索算法[J].系统工程理论与实践,2018,38(2):522-531.
[9]RENAUD J,LAPORTE G,BOCTOR F F.A tabu search heuristic for the multi-depot vehicle routing problem[J].Computers&Operations Research,1996,23(3):229-235.
[10]YANG X S.A new metaheuristic bat-inspired algorithm[J].Computer Knowledge and Technology,2010,284:65-74.
[11]殷亚,张惠珍.求解带硬时间窗的多目标车辆路径问题的多种混合蝙蝠算法[J].计算机应用研究,2017,(12):1-8.
[12]李妍峰,高自友,李军.基于实时交通信息的城市动态网络车辆路径优化问题[J].系统工程理论与实践,2013,33(7):1813-1819.
[13]李峰,魏莹.易腐货物配送中时变车辆路径问题的优化算法[J].系统工程学报,2010,25(4):492-519.
[14]XIAO Y Y,ZHAO Q H,KAKU I,et al.Development of a fuel consumption optimization model for the capacitated vehicle routing problem[J].Computers&Operations Research,2012,39(7):1419-1431.
[15]SHAH-HOSSEINIH.Problem solving by intelligent water drops[C]//IEEE.2007 IEEE Congress on Evolutionary Computation.Piscataway:IEEE,2007:3226-3231.
[16]王奕璇,陈荔,王涛.基于改进智能水滴算法的混合时间窗电商物流路径优化研究[J].科技管理研究,2018,38(11):211-218.
[17]HOLLAND J H.Adaptation in natural and artificial systems[M].Ann Arbor:University of Michigan Press,1975.
[18]EBERHART R C,KENNEDY J.A new optimizer using particle swarm theory[C]//IEEE.Sixth International Symposium on Micro Machine and Hmm Science(Nagoya,Japan).Piscataway:IEEE,1995:39-43.
[19]马向国,刘同娟,杨平哲,等.基于随机需求的冷链物流车辆路径优化模型[J].系统仿真学报,2016,28(8):1824-1832,1840.