主管：中国科学院
主办：中国优选法统筹法与经济数学研究会
　　　中国科学院科技战略咨询研究院
中国管理科学

中国管理科学 ›› 2007, Vol. 15 ›› Issue (2): 97-103.

• 论文 • 上一篇    下一篇

基于自感应蚁群算法的VRPSDP问题研究

陆琳, 谭清美   

  1. 南京航空航天大学经济与管理学院 江苏南京210016
  • 收稿日期:2005-11-30 修回日期:2007-03-15 出版日期:2007-04-30 发布日期:2007-04-30
  • 作者简介:陆琳(1976- ),男(汉族),山东淄博人,南京航空航天大学管理科学与工程博士研究生,研究方向:物流管理、系统工程.
  • 基金资助:

    江苏省软科学重点项目(BR2004014);江苏省社会科学基金项目(04EYB032)

Vehicle Routing Problem with Simultaneous Delivery and Pick-up Studied Based on Self-telepathy Ant Colony Algorithm

LU Lin, TAN Qing-mei   

  1. Nanjing University of Aeronautics and Astronautics, College of Economics and Management, Nanjing 210016, China
  • Received:2005-11-30 Revised:2007-03-15 Online:2007-04-30 Published:2007-04-30

PDF (PC)

1431

被引次数

77

摘要： 同时供货和取货的车辆路径问题是车辆路径问题的重要组成部分之一,问题的复杂性使得目前的主要求解方法局限于各种插入式启发算法。本文引用了近年来出现的蚁群算法,并通过对蚂蚁行为的深入研究,首次提出了感应因子、期望程度因子、距离性比因子以及加速因子的概念,在信息素更新方面融入了当前路径的距离特征,构建了一种全新的自感应蚁群算法。该方法充分利用全局分布的信息素感应信息,并且根据车辆容量支配值以及节点间距和节点-中心点间距性比进行状态转移,利用信息素更新公式中加速因子的动态调节有效地解决了算法快速收敛与陷入局部最优的矛盾。仿真试验证明了自感应蚁群算法的有效性,同时,该算法也拓展了车辆路径问题的算法空间。

关键词: 自感应蚁群算法, 同时供货和取货的车辆路径问题, 信息素, 算法

Abstract: Vehicle routing problem with simultaneous delivery and pick-up is one of the important compovents of the vehicle routing question,and the complexity of the question makes the present solving methods confined to various kinds of insert heuristics algorithm. By quoting the ant colony algorithm appearing in recent years and the further investigation of ants behavior,the paper puts forward to the definitions of reaction factor,expect degree factor,relative distance quality factor and accelerate factor for the first time, incorporates the distance characteristic of the present route in the field of pheromone upgrading,and finally structures a new self-telepathy ant colony algorithm(STACA).STACA method fully utilizes the overall distributed pheromone to respond to information,shifts the state according to the arranging value of capacity of vehicle and the proportion between nodal interval and the node and interval of central point,and effectively solves the contradiction between fast searching and falling into local optima by utilizing the dynamic regulation accelerate factor in the pheromone newer formula. The artificial test has proved the validity of STACA,meanwhile,this algorithm expanded the algorithm space of VRP too.

Key words: aelf-telepathy ant colony algorithm(STACA), vehicle routing problem with simultaneous delivery and pick-up (VRPSDP), pheromone, algorithm

中图分类号: