Improved ant colony optimization for multi-depot heterogeneous vehicle routing problem with soft time windows  

求解带软时间窗多车场多车型车辆路径问题的一种改进蚁群算法(英文)

作　　者：汤雅连[1] 蔡延光[1] 杨期江[2] 

机构地区：[1]广东工业大学自动化学院,广州510006 [2]华南理工大学机械与汽车工程学院,广州510641

出　　处：《Journal of Southeast University(English Edition)》2015年第1期94-99,共6页东南大学学报（英文版）

基　　金：The National Natural Science Foundation of China(No.61074147);the Natural Science Foundation of Guangdong Province(No.S2011010005059);the Foundation of Enterprise-University-Research Institute Cooperation from Guangdong Province and Ministry of Education of China(No.2012B091000171,2011B090400460);the Science and Technology Program of Guangdong Province(No.2012B050600028);the Science and Technology Program of Huadu District,Guangzhou(No.HD14ZD001)

摘　　要：Considering that the vehicle routing problem （VRP） with many extended features is widely used in actual life, such as multi-depot, heterogeneous types of vehicles, customer service priority and time windows etc., a mathematical model for multi-depot heterogeneous vehicle routing problem with soft time windows （MDHVRPSTW） is established. An improved ant colony optimization （IACO） is proposed for solving this model. First, MDHVRPSTW is transferred into different groups according to the nearest principle, and then the initial route is constructed by the scanning algorithm （SA）. Secondly, genetic operators are introduced, and crossover probability and mutation probability are adaptively adjusted in order to improve the global search ability of the algorithm. Moreover, the smooth mechanism is used to improve the performance of the ant colony optimization （ACO）. Finally, the 3-opt strategy is used to improve the local search ability. The proposed IACO was tested on three new instances that were generated randomly. The experimental results show that IACO is superior to the other three existing algorithms in terms of convergence speed and solution quality. Thus, the proposed method is effective and feasible, and the proposed model is meaningful.考虑实际生活中带多种扩展特征(如多车场、多车型、客户服务优先级、时间窗等)的车辆路径问题应用广泛,建立带软时间窗多车场多车型车辆路径问题的数学模型,并提出一种改进的蚁群优化算法(IACO)求解该模型.首先,根据就近原则将客户分组,并通过扫描算法构造初始路径;其次,通过引入遗传算子并自适应地调整交叉概率和变异概率来提高算法的全局收敛能力,且采用平滑机制来提高蚁群优化算法的性能;最后,采用3-opt策略来提高算法的局部搜索能力.将提出的算法应用在3个随机产生的实例中,仿真表明提出的IACO在收敛速度和解质量两方面都优于现有的3种算法,证明提出的算法是有效可行的,且提出的模型具有一定的实际意义.

关 键 词：vehicle routing problem soft time window improved ant colony optimization customer service priority genetic algorithm 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]