# [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] 点击复制 基于自适应多态蚁群算法的多约束车辆路径问题() 分享到： var jiathis_config = { data_track_clickback: true };

38

2008年第1期

37-42

2008-01-20

## 文章信息/Info

Title:
Vehicle routing problem with multiple constraints using adaptive and polymorphic ant colony algorithm

Author(s):
School of Mechanical Engineering, Southeast University, Nanjing 211189, China

Keywords:

TP301.6
DOI:
10.3969/j.issn.1001-0505.2008.01.008

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]