基于自适应多态蚁群算法的多约束车辆路径问题

被引：12

作者：

陈美军

张志胜

史金飞

机构：

[1] 东南大学机械工程学院

来源：

东南大学学报(自然科学版) | 2008年 / 01期

关键词：

车辆路径问题; 时间窗; 多约束; 数学模型; 自适应多态蚁群算法;

D O I：

暂无

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

建立了在有客户优先级、路况影响、多车型、时间窗和容量等多约束条件下车辆路径问题(VRPMC)的数学模型.由于该模型是一个NP-hard问题,目前还没有多项式算法求解,又提出了采用自适应的多态蚁群算法(APACA)来对其进行求解的策略.首先,算法中侦察蚁完成满足约束条件的路径侦察并设置侦察信息素;其次,搜索蚁利用侦察蚁提供的辅助信息进一步搜索可行路径,通过多态蚂蚁间的协作和自适应调整挥发系数,能更快地搜索到问题的优化解;最后通过一个实例与节约算法、遗传算法、禁忌搜索算法和基本蚁群算法进行了对比,结果表明:对VR-PMC问题,APACA算法比前述算法在算法稳定性、运行距离、计算速度方面更具有优势.

引用

页码：37 / 42

页数：6

共 8 条

[1] 多配送中心车辆调度问题的模型与算法研究
郎茂祥
[J]. 交通运输系统工程与信息, 2006, (05) : 65 - 69
[2] 带时间窗车辆路径问题的改进蚁群算法研究
陈幼林
王劲恺
[J]. 计算机工程与应用 , 2006, (29) : 218 - 219+225
[3] 基于自适应蚁群算法的车辆路径问题研究
刘志硕
申金升
柴跃廷
不详
[J]. 控制与决策 , 2005, (05) : 562 - 566
[4] 货运车辆优化调度方法
纪寿文
缪立新
李克强
连小珉
[J]. 公路交通科技, 2003, (06) : 109 - 112
[5] 求解TSP的子空间遗传算法
全惠云
文高进
[J]. 数学理论与应用, 2002, (01) : 36 - 39
[6] 一种自适应蚁群算法及其仿真研究
王颖
谢剑英
[J]. 系统仿真学报, 2002, (01) : 31 - 33
[7] Computing nine new best-so-far solutions for capacitated VRP with a cellular genetic algorithm
Alba, Enrique
Dorronsoro, Bernabe
[J]. INFORMATION PROCESSING LETTERS, 2006, 98 (06) : 225 - 230
[8] An improved ant system algorithm for the vehicle routing problem
Bullnheimer, B
Hartl, RF
Strauss, C
[J]. ANNALS OF OPERATIONS RESEARCH, 1999, 89 (0) : 319 - 328

← 1 →