基于客户满意度的车辆路径问题的混合蝙蝠算法
|
摘要
车辆路径问题对现实有着良好的指导意义,自提出以来便吸引了企业界和学术界的广泛关注。然而,传统车辆路径问题仅仅将车辆行驶里程最短作为目标,忽视良好的客户体验对于企业的重要性。考虑客户满意度这一目标,建立以客户满意度和车辆行驶里程最短为目标的多目标优化模型,根据车辆路径问题的具体特征,改变基本蝙蝠算法的编码方式。为克服基本蝙蝠算法求解精度低、易陷入局部最优的缺陷,加入贪婪随机自适应启发式算法提高求解精度,引入病毒进化机制以增强蝙蝠算法跳出局部最优的能力。算例分析表明:病毒进化混合蝙蝠算法相比于基本蝙蝠算法,在求解精度上有较大幅度提高,是一种有效求解车辆路径问题的方法。
The vehicle routing problem has a good guiding significance for the reality and has attracted extensive attention from the business community and academia since it was proposed. However, the traditional vehicle routing problem only takes the shortest vehicle mileage as the target, ignoring the logistics and transportation industry, and neglecting the importance of good customer experiences for enterprises. Considering the goal of customer satisfaction, a multi-objective optimization model with the goals of both the customer satisfaction and the shortest vehicle mileage was established. According to the specific characteristics of the vehicle routing problem, the coding mode of the basic bat algorithm was changed. In order to overcome the disadvantages of the basic bat algorithm, such as low accuracy and being easy to get into local optimization, the greedy randomized adaptive search procedure was added to improve the solution accuracy, and the virus evolution mechanism was introduced to enhance the ability of the bat algorithm to jump out of local optimization. The results show that compared with the basic bat algorithm, the virus evolution hybrid bat algorithm is more accurate and is an effective method to solve the vehicle routing problem.
The vehicle routing problem has a good guiding significance for the reality and has attracted extensive attention from the business community and academia since it was proposed. However, the traditional vehicle routing problem only takes the shortest vehicle mileage as the target, ignoring the logistics and transportation industry, and neglecting the importance of good customer experiences for enterprises. Considering the goal of customer satisfaction, a multi-objective optimization model with the goals of both the customer satisfaction and the shortest vehicle mileage was established. According to the specific characteristics of the vehicle routing problem, the coding mode of the basic bat algorithm was changed. In order to overcome the disadvantages of the basic bat algorithm, such as low accuracy and being easy to get into local optimization, the greedy randomized adaptive search procedure was added to improve the solution accuracy, and the virus evolution mechanism was introduced to enhance the ability of the bat algorithm to jump out of local optimization. The results show that compared with the basic bat algorithm, the virus evolution hybrid bat algorithm is more accurate and is an effective method to solve the vehicle routing problem.
引文
[1]DANTZIG G B,RAMSER J H.The truck dispatching problem[J].Management Science,1959,6(1):80-91.
[2]SAVELSBERGH M W P.Local search in routing problems with time windows[J].Annals of Operations Research,1985,4(1):285-305.
[3]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.
[4]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.
[5]DING Q L,HU X P,SUN L J,et al.An improved ant colony optimization and its application to vehicle routing problem with time windows[J].Neurocomputing,2012,98:101-107.
[6]张勇.基于改进蚁群算法物流配送路径优化的研究[J].控制工程,2015,22(2):252-256.
[7]何小锋,马良.带时间窗车辆路径问题的量子蚁群算法[J].系统工程理论与实践,2013,33(5):1255-1261.
[8]刘云,张惠珍.多目标带时间窗的车辆路径问题的单亲遗传混合蚁群算法[J].公路交通科技,2016,33(6):95-100,106.
[9]王超,穆东.基于模拟退火算法求解VRPSPDTW问题[J].系统仿真学报,2014,26(11):2618-2623.
[10]MARINAKIS Y,MARINAKI M,DOUNIAS G.A hybrid particle swarm optimization algorithm for the vehicle routing problem[J].Engineering Applications of Artificial Intelligence,2010,23(4):463-472.
[11]徐杰,黄德先.基于混合粒子群算法的多目标车辆路径研究[J].计算机集成制造系统,2007,13(3):573-579,584.
[12]温惠英,孙博.基于离散粒子群算法的协同车辆路径问题[J].公路交通科技,2011,28(1):149-153.
[13]YANG X S.A new metaheuristic bat-inspired algorithm[M]//GONZáLEZ J R,PELTA D A,CRUZ C,et al.Nature Inspired Cooperative Strategies for Optimization(NICSO 2010).Berlin Heidelberg:Springer,2010:65-74.
[14]LIN J H,CHOU C W,YANG C H,et al.A chaotic levy flight bat algorithm for parameter estimation in nonlinear dynamic biological systems[J].Computer and Information Technology,2012,2(2):56-63.
[15]NAKAMURA R Y M,PEREIRA L A M,COSTA K A,et al.BBA:a binary bat algorithm for feature selection[C]//Proceedings of the 2012 25th SIBGRAPIConference on Graphics,Patterns and Images.Ouro Preto,Brazil:IEEE,2012:291-297.
[16]刘长平,叶春明.具有混沌搜索策略的蝙蝠优化算法及性能仿真[J].系统仿真学报,2013,25(6):1183-1188,1195.
[17]马祥丽,张惠珍,马良.蝙蝠算法在物流配送车辆路径优化问题中的应用[J].数学的实践与认识,2015,45(24):80-86.
[18]殷亚,张惠珍.易腐生鲜货品车辆路径问题的改进混合蝙蝠算法[J].计算机应用,2017,37(12):3602-3607.
[19]FEO T A,RESENDE M G C.Greedy randomized adaptive search procedures[J].Journal of Global Optimization,1995,6(2):109-133.
[2]SAVELSBERGH M W P.Local search in routing problems with time windows[J].Annals of Operations Research,1985,4(1):285-305.
[3]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.
[4]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.
[5]DING Q L,HU X P,SUN L J,et al.An improved ant colony optimization and its application to vehicle routing problem with time windows[J].Neurocomputing,2012,98:101-107.
[6]张勇.基于改进蚁群算法物流配送路径优化的研究[J].控制工程,2015,22(2):252-256.
[7]何小锋,马良.带时间窗车辆路径问题的量子蚁群算法[J].系统工程理论与实践,2013,33(5):1255-1261.
[8]刘云,张惠珍.多目标带时间窗的车辆路径问题的单亲遗传混合蚁群算法[J].公路交通科技,2016,33(6):95-100,106.
[9]王超,穆东.基于模拟退火算法求解VRPSPDTW问题[J].系统仿真学报,2014,26(11):2618-2623.
[10]MARINAKIS Y,MARINAKI M,DOUNIAS G.A hybrid particle swarm optimization algorithm for the vehicle routing problem[J].Engineering Applications of Artificial Intelligence,2010,23(4):463-472.
[11]徐杰,黄德先.基于混合粒子群算法的多目标车辆路径研究[J].计算机集成制造系统,2007,13(3):573-579,584.
[12]温惠英,孙博.基于离散粒子群算法的协同车辆路径问题[J].公路交通科技,2011,28(1):149-153.
[13]YANG X S.A new metaheuristic bat-inspired algorithm[M]//GONZáLEZ J R,PELTA D A,CRUZ C,et al.Nature Inspired Cooperative Strategies for Optimization(NICSO 2010).Berlin Heidelberg:Springer,2010:65-74.
[14]LIN J H,CHOU C W,YANG C H,et al.A chaotic levy flight bat algorithm for parameter estimation in nonlinear dynamic biological systems[J].Computer and Information Technology,2012,2(2):56-63.
[15]NAKAMURA R Y M,PEREIRA L A M,COSTA K A,et al.BBA:a binary bat algorithm for feature selection[C]//Proceedings of the 2012 25th SIBGRAPIConference on Graphics,Patterns and Images.Ouro Preto,Brazil:IEEE,2012:291-297.
[16]刘长平,叶春明.具有混沌搜索策略的蝙蝠优化算法及性能仿真[J].系统仿真学报,2013,25(6):1183-1188,1195.
[17]马祥丽,张惠珍,马良.蝙蝠算法在物流配送车辆路径优化问题中的应用[J].数学的实践与认识,2015,45(24):80-86.
[18]殷亚,张惠珍.易腐生鲜货品车辆路径问题的改进混合蝙蝠算法[J].计算机应用,2017,37(12):3602-3607.
[19]FEO T A,RESENDE M G C.Greedy randomized adaptive search procedures[J].Journal of Global Optimization,1995,6(2):109-133.