[1]陈美军,张志胜,史金飞.基于自适应多态蚁群算法的多约束车辆路径问题[J].东南大学学报(自然科学版),2008,38(1):37-42.[doi:10.3969/j.issn.1001-0505.2008.01.008]
 Chen Meijun,Zhang Zhisheng,Shi Jinfei.Vehicle routing problem with multiple constraints using adaptive and polymorphic ant colony algorithm[J].Journal of Southeast University (Natural Science Edition),2008,38(1):37-42.[doi:10.3969/j.issn.1001-0505.2008.01.008]
点击复制

基于自适应多态蚁群算法的多约束车辆路径问题()
分享到:

《东南大学学报(自然科学版)》[ISSN:1001-0505/CN:32-1178/N]

卷:
38
期数:
2008年第1期
页码:
37-42
栏目:
计算机科学与工程
出版日期:
2008-01-20

文章信息/Info

Title:
Vehicle routing problem with multiple constraints using adaptive and polymorphic ant colony algorithm
作者:
陈美军 张志胜 史金飞
东南大学机械工程学院, 南京 211189
Author(s):
Chen Meijun Zhang Zhisheng Shi Jinfei
School of Mechanical Engineering, Southeast University, Nanjing 211189, China
关键词:
车辆路径问题 时间窗 多约束 数学模型 自适应多态蚁群算法
Keywords:
vehicle routing problem time windows multiple constraints mathematical model adaptive polymorphic ant colony algorithm
分类号:
TP301.6
DOI:
10.3969/j.issn.1001-0505.2008.01.008
摘要:
建立了在有客户优先级、路况影响、多车型、时间窗和容量等多约束条件下车辆路径问题(VRPMC)的数学模型.由于该模型是一个NP-hard问题, 目前还没有多项式算法求解,又提出了采用自适应的多态蚁群算法(APACA)来对其进行求解的策略.首先,算法中侦察蚁完成满足约束条件的路径侦察并设置侦察信息素; 其次,搜索蚁利用侦察蚁提供的辅助信息进一步搜索可行路径,通过多态蚂蚁间的协作和自适应调整挥发系数,能更快地搜索到问题的优化解; 最后通过一个实例与节约算法、遗传算法、禁忌搜索算法和基本蚁群算法进行了对比,结果表明:对VRPMC问题,APACA算法比前述算法在算法稳定性、运行距离、计算速度方面更具有优势.
Abstract:
A novel mathematical model has been developed to address the complicated issue of vehicle routing problem with multiple constraints(VRPMC), which includes the client priority levels, traffic condition influences, multi-type vehicle, time windows and capacity constraints. As an NP-hard problem, this model has no solution based on polynomial algorithm at present. Therefore, an adaptive and polymorphic ant colony algorithm(APACA)has been brought forward to solve the VRPMC. First, spy ants fulfill the reconnaissance to the route that satisfies constraint condition and set reconnoitering pheromones on the route. Then, search ants search the feasible path by the auxiliary information from spy ants. The cooperating among polymorphic ants and adaptively adjusting the volatilizing coefficient can significantly improve the speed to find the optimum solution. Finally, a case study is presented to compare APACA with saving algorithm, genetic algorithm, tabu-search algorithm and ant colony optimum. The test results show that the proposed algorithm is of more advantage than fore mentioned algorithms in computational results stability, transport distance and computational speed for VRPMC.

参考文献/References:

[1] 纪寿文,缪立新,李克强,等.货运车辆优化调度方法[J].公路交通科技,2003,20(6):109-112.
  Ji Shouwen,Miao Lixin,Li Keqiang,et al.Optimal truck scheduling method [J]. Journal of Highway and Transportation Research and Development,2003,20(6):109-112.(in Chinese)
[2] 郎茂祥.多配送中心车辆调度问题的模型与算法研究[J].交通运输系统工程与信息,2006,6(5):65-69.
  Lang Maoxiang.Study on the model and algorithm for multi-depot vehicle scheduling problem [J]. Journal of Transportation Systems Engineering and Information Technology,2006,6(5):65-69.(in Chinese)
[3] Bent R,Hentenryck P V.A two-stage hybrid algorithm for pickup and delivery vehicle routing problems with time windows [J].Computers & Operations Research,2006,33(4):875-893.
[4] Russell R A,Chiang W C.Scatter search for the vehicle routing problem with time windows [J]. European Journal of Operational Research,2006,169(2):606-622.
[5] Alba E,Dorronsoro B.Computing nine new best-so-far solutions for capacitated VRP with a cellular genetic algorithm [J].Information Processing Letters,2006,98(6):225-230.
[6] 全惠云,文高进.求解TSP的子空间遗传算法[J].数学理论与应用,2002,22(1):36-39.
  Quan Huiyun,Wen Gaojin.Subspace genetical algorithm for TSP [J].Mathematical Theory and Applications,2002,22(1):36-39.(in Chinese)
[7] Colorni A,Dorigo M,Maniezzo V.Distributed optimization by ant colonies [C] //Proceedings of the First European Conference on Artificial Life.Paris:Elsevier Publishing,1991:134-142.
[8] 刘志硕,申金升,柴跃廷.基于自适应蚁群算法的车辆路径问题研究[J].控制与决策,2005,20(5):562-566.
  Liu Zhishuo,Shen Jinsheng,Chai Yueting.Vehicle routing problem based on an adaptive ant colony algorithm [J]. Control and Decision,2005,20(5):562-566.(in Chinese)
[9] Bullnheimer B,Hartl R,Strauss C.An improved ant system algorithm for the vehicle routing problem [J]. Annals of Operations Research,1999,89(13):319-328.
[10] 王颖,谢剑英.一种自适应蚁群算法及其仿真研究[J].系统仿真学报,2002,14(1):31-33.
  Wang Ying,Xie Jianying.An adaptive ant colony optimization algorithm and simulation [J].Journal of System Simulation,2002,14(1):31-33.(in Chinese)
[11] 陈幼林,王劲恺.带时间窗车辆路径问题的改进蚁群算法研究[J].计算机工程与应用,2006,42(29):218-219.
  Chen Youlin,Wang Jinkai.Improved ant colony algorithm for vehicle routing problem with time windows [J]. Computer Engineering and Application,2006,42(29):218-219.(in Chinese)
[12] Solomon M,Desrosiers J.Time window constrained routing and scheduling problem [J]. Transport Science,1988,22(1):1-11.

相似文献/References:

[1]夏红云,江亿平,赵林度.基于双层规划的应急救援车辆调度模型[J].东南大学学报(自然科学版),2014,44(2):425.[doi:10.3969/j.issn.1001-0505.2014.02.035]
 Xia Hongyun,Jiang Yiping,Zhao Lindu.Emergency rescue vehicle scheduling model based on bi-level programming[J].Journal of Southeast University (Natural Science Edition),2014,44(1):425.[doi:10.3969/j.issn.1001-0505.2014.02.035]

备注/Memo

备注/Memo:
作者简介: 陈美军(1971—),男,博士生; 史金飞(联系人),男,博士,教授,博士生导师,shijf@seu.edu.cn.
基金项目: 国家自然科学基金资助项目(70272046).
引文格式: 陈美军,张志胜,史金飞.基于自适应多态蚁群算法的多约束车辆路径问题[J].东南大学学报:自然科学版,2008,38(1):37-42.
更新日期/Last Update: 2008-01-20