贪婪随机自适应蝙蝠算法在车辆路径问题中的应用

数学理论与应用 ›› 2017, Vol. 37 ›› Issue (1): 90-99.

贪婪随机自适应蝙蝠算法在车辆路径问题中的应用

孙奇, 张惠珍

上海理工大学管理学院,上海,200093

出版日期:2017-03-30 发布日期:2020-09-25

Solving Vehicle Routing Problems with the Greedy Randomized Adaptive Bat Algorithm

Sun Qi ,Zhang Huizhen

Business School,University of Shanghai for Scienceand Technology,Shanghai 200093,China

Online:2017-03-30 Published:2020-09-25

摘要/Abstract

摘要： 车辆路径问题(Vehicle Routing Problem,VRP)在物流与供应链领域是一个非常有研究价值的NP-Hard问题.蝙蝠算法(Bat Algorithm,BA)是一种新兴的智能优化算法,有着广阔的应用前景.然而它不能直接用于求解离散问题,并且如同大多数智能优化算法一样,容易陷入局部最优,后期收敛速度慢.本文针对VRP问题的具体特性,重新定义了蝙蝠的编码方式并利用GRASP启发式算法生成蝙蝠算法初始种群来改进算法,然后应用于求解VRP问题.

关键词: 蝙蝠算法, GRASP算法, 车辆路径问题, 编码方式

Abstract:

The Vehicle Routing Problem(VRP)is a worth researching NP-Hard problem in logistic and supply chain.The Bat Algorithm (BA)is a new intelligent optimization algorithm having broad application prospect. But it can’t use to solve discrete problem directly,and just like most intelligent optimization algorithms, it may easily fall into local optimum and its convergence rate is very slow in the late stage of the algorithm.In this paper,in view of the specific characteristics of the VRP,we redefine the coding mode and use GRASP to generate the initial population of BA to improve the algorithm,and then apply it to solve the VRP.

Key words: Bat algorithm, GRASP algorithm, Vehicle routing problem, Coding mode

孙奇, 张惠珍. 贪婪随机自适应蝙蝠算法在车辆路径问题中的应用[J]. 数学理论与应用, 2017, 37(1): 90-99.

Sun Qi , Zhang Huizhen.

Solving Vehicle Routing Problems with the Greedy Randomized Adaptive Bat Algorithm [J]. Mathematical Theory and Applications, 2017, 37(1): 90-99.