基于ACS-GA算法的车辆路径问题研究  

An ACS-GA Hybrid Optimization Method to Solve Vehicle Routing Problem

作　　者：赵婉忻[1] 曲仕茹[1] 

机构地区：[1]西北工业大学自动化学院,西安710072

出　　处：《微处理机》2011年第2期56-59,共4页Microprocessors

基　　金：教育部博士点基金(20096102110027);陕西省工业攻关项目(2008KD7-14)

摘　　要：物流配送车辆路径问题是智能交通和商业物流领域中一个重要研究方面。合理规划车辆的行驶路线,减少配送里程,降低物流成本,对提高经济效益具有重要意义。重点分析了带时间窗的物流配送车辆路径问题,建立了兼顾配送时间与配送距离最短的改进数学模型。提出了基于蚁群系统算法和遗传算法相融合的混合算法。该算法利用蚁群系统算法得到初始解,运用遗传算法中复制、交叉、变异操作对解的种群多样性进行扩充,克服了蚁群系统算法的早熟现象,增强了算法的全局搜索能力。基于标准数据集的实验结果表明,该算法与其他优化方法相比较,具有较好的搜索车辆路径最优解的能力。Vehicle routing problem is an important research area in intelligent transportation and business logistics.Planning the vehicle routes reasonably,reducing the delivery mileage and minimizing the cost of logistic distribution are great significance to increase economic efficiency.The paper focuses on vehicle routing problem with time windows in logistic distribution and establishes an improved mathematical model in which the delivery time and delivery distance is shortest.A novel hybrid optimization method integrating ant colony system with genetic algorithm（ACS-GA） is presented.The initial solution is obtained by ant colony system.A genetic algorithm is used to improve the performance of ACS by reproduction,crossover and mutation operations.The ACS-GA hybrid optimization method can overcome the premature phenomenon and enhance the global search ability.Based on the benchmark datasets of vehicle routing problem with time windows,the experimental results demonstrate that the proposed method has a better ability to search the global optimal solution than other optimization methods.

关 键 词：物流配送 车辆路径问题 蚁群系统 遗传算法 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程] U491[自动化与计算机技术—控制科学与工程]