摘要
车辆路径问题(vehicleroutingproblem,VRP)是组合优化中一个典型的NP难题,理论上,目前仅能保证一些相对小规模的问题可求得最优解.基于近些年出现的新型智能优化思想:人工蚂蚁系统,给出了一种可快速求解VRP的蚂蚁搜索算法.通过定义基本的人工蚂蚁状态转移概率,并结合局部搜索策略,用迭代次数控制算法的运行时间,从而使该方法具有实用意义和可操作性.经一系列数据测试和验证,并与若干已有的经典算法相比较,获得了较好的结果.
Vehicle routing problem (VRP) is a typical NP_hard problem in combinatorial optimization. Theoretically speaking, only relatively small_sized problems can be solved to get the optimal solution. Based on the recently developed new intelligent optimization idea: artificial ant system, we proposes a quick ant searching algorithm for solving VRP. After defining the basic state transition probabilities of artificial ants and combining the local searching strategy, we uses the number of iterations to control the running time of the algorithm. Therefore, the method can be implemented with practicality. Series of numerical examples were tested and verified, which shows the better performance of the proposed algorithm compared with some classical algorithms.
出处
《系统工程学报》
CSCD
2004年第4期418-422,共5页
Journal of Systems Engineering
基金
上海市曙光计划资助项目(2000SG30).
