改进蚁群算法研究及其在车辆调度中的应用
|
摘要
随着市场经济的发展，作为“第三利润源泉”的物流对经济活动的影响日益明显，越来越引起了人们的高度重视，已成为当前“最重要的竞争领域”之一。未来的市场竞争，物流将起到举足轻重的作用。物流配送中的车辆调度优化方法和系统，是实现快速、准确和低成本物流配送的重要手段和途径，是现代物流系统必不可少的重要部分。
然而，现有的物流系统大多采用人工或计算机辅助的方法进行车辆调度，因此，不仅调度时间长，而且，不可能综合多目标多约束调度需求进行科学的量化分析和优化处理。因此，研究物流配送中的车辆调度需求，建立多目标多约束环境下的车辆调度数学模型，提出有效的、对一般车辆调度问题具有一定适用性的智能优化方法，并研制车辆调度系统具有重要的理论意义和实用价值。
本文的主要工作和贡献在于：
1、在对智能路径优化算法进行分析对比的基础上，深入研究了基本蚁群算法的基本原理、模型、实现方法及其仿真效果，分析了基本蚁群算法的优点及其不足。
2、针对基本蚁群算法存在的计算时间长、易于陷入局部最优等缺点，提出和实现了基于模式学习的动态小窗口蚁群算法(DLWACAPL)和融入遗传算法的DLWACAPL(HACAGA)，并通过案例测试，证明了上述两种改进蚁群算法的有效性和适应性。
3、研究了面向能力约束的车辆路径问题(CVRP)和面向时间窗的车辆路径问题(VRPTW)数学模型、求解方法以及车辆调度的多目标优化策略，包括多目标体系、数学模型和多目标的综合优化方法。
4、基于本文提出的改进蚁群算法(DLWACAPL和HACAGA)进行了车辆调度系统的研制，包括车辆调度系统的主要功能设计、软硬件环境配置和关键算法的编码与实现。
5、对多目标多约束车辆调度工程问题进行了测试，验证了本文提出的改进蚁群算法的有效性和适应性。
ABSTRACTWith the development of market economy, it has been paid more attention that logistics, taken as the third profit resource, has obviously affected the economy activity. As the most important competitive field, it will play an important role in the future market competition. The vehicle scheduling optimization and system of logistics delivery is one of important approaches that implement fast, accurate and low-cost logistics delivery. And they are indispensable parts of modern logistics system.In current logistics system, manual or computer-aided approaches are mostly adopted. On one hand, it will cost much time, on the other hand it is hardly to synthesize multi-objective and multi-constraint scheduling demands to perform scientific quantitative analysis and optimization disposal. So it is desired for theory and practice to present effective and adaptable intelligent optimization for general vehicle scheduling problems, research on vehicle scheduling requirement in logistics delivery, establish the mathematical model of vehicle scheduling in complicated environment with multi-objective and multi-constraint. The main contributions of this thesis include:1．The theory, model, tool and simulation of basic ant colony algorithm are discussed in details by analyzing and comparing intelligent routing optimizations.2．Two novel intelligent optimizations, named Dynamic Little Window Ant Colony Algorithm based on Pattern Learning (DLWACAPL) and DLWACAPL integrated Genetic Algorithm (HACAGA), are proposed to avoid the deficiency of basic Ant Colony Algorithm which often costs long time and get into the local optimization easily. And the validations and adaptation of the two intelligent optimizations have been performed with benchmark.3．The mathematical models and approaches of two typical vehicle scheduling problems on Capacitated Vehicle Routing Problems (CVRP) and Vehicle Routing Problems with Time Windows (VRPTW) are investigated. Furthermore, the multi-objective optimization strategies on vehicle scheduling including multi-objective framework, mathematics model and multi-objective comprehensive optimization are researched.4．Vehicle scheduling system based on the improved ant colony algorithms (DLWACAPL and HACAGA) has been developed, including the design of main function models, the configuration of software and hardware as well as coding and realization of the key algorithms.5．A study of how these meta-heuristics perform is carried out on the engineering benchmark. And the experimental results have indicated the validation and adaptation of the improved ant colony algorithm proposed in this thesis.Lan Shihai (Mechanical and Electrical Engineering)Supervised by
然而，现有的物流系统大多采用人工或计算机辅助的方法进行车辆调度，因此，不仅调度时间长，而且，不可能综合多目标多约束调度需求进行科学的量化分析和优化处理。因此，研究物流配送中的车辆调度需求，建立多目标多约束环境下的车辆调度数学模型，提出有效的、对一般车辆调度问题具有一定适用性的智能优化方法，并研制车辆调度系统具有重要的理论意义和实用价值。
本文的主要工作和贡献在于：
1、在对智能路径优化算法进行分析对比的基础上，深入研究了基本蚁群算法的基本原理、模型、实现方法及其仿真效果，分析了基本蚁群算法的优点及其不足。
2、针对基本蚁群算法存在的计算时间长、易于陷入局部最优等缺点，提出和实现了基于模式学习的动态小窗口蚁群算法(DLWACAPL)和融入遗传算法的DLWACAPL(HACAGA)，并通过案例测试，证明了上述两种改进蚁群算法的有效性和适应性。
3、研究了面向能力约束的车辆路径问题(CVRP)和面向时间窗的车辆路径问题(VRPTW)数学模型、求解方法以及车辆调度的多目标优化策略，包括多目标体系、数学模型和多目标的综合优化方法。
4、基于本文提出的改进蚁群算法(DLWACAPL和HACAGA)进行了车辆调度系统的研制，包括车辆调度系统的主要功能设计、软硬件环境配置和关键算法的编码与实现。
5、对多目标多约束车辆调度工程问题进行了测试，验证了本文提出的改进蚁群算法的有效性和适应性。
ABSTRACTWith the development of market economy, it has been paid more attention that logistics, taken as the third profit resource, has obviously affected the economy activity. As the most important competitive field, it will play an important role in the future market competition. The vehicle scheduling optimization and system of logistics delivery is one of important approaches that implement fast, accurate and low-cost logistics delivery. And they are indispensable parts of modern logistics system.In current logistics system, manual or computer-aided approaches are mostly adopted. On one hand, it will cost much time, on the other hand it is hardly to synthesize multi-objective and multi-constraint scheduling demands to perform scientific quantitative analysis and optimization disposal. So it is desired for theory and practice to present effective and adaptable intelligent optimization for general vehicle scheduling problems, research on vehicle scheduling requirement in logistics delivery, establish the mathematical model of vehicle scheduling in complicated environment with multi-objective and multi-constraint. The main contributions of this thesis include:1．The theory, model, tool and simulation of basic ant colony algorithm are discussed in details by analyzing and comparing intelligent routing optimizations.2．Two novel intelligent optimizations, named Dynamic Little Window Ant Colony Algorithm based on Pattern Learning (DLWACAPL) and DLWACAPL integrated Genetic Algorithm (HACAGA), are proposed to avoid the deficiency of basic Ant Colony Algorithm which often costs long time and get into the local optimization easily. And the validations and adaptation of the two intelligent optimizations have been performed with benchmark.3．The mathematical models and approaches of two typical vehicle scheduling problems on Capacitated Vehicle Routing Problems (CVRP) and Vehicle Routing Problems with Time Windows (VRPTW) are investigated. Furthermore, the multi-objective optimization strategies on vehicle scheduling including multi-objective framework, mathematics model and multi-objective comprehensive optimization are researched.4．Vehicle scheduling system based on the improved ant colony algorithms (DLWACAPL and HACAGA) has been developed, including the design of main function models, the configuration of software and hardware as well as coding and realization of the key algorithms.5．A study of how these meta-heuristics perform is carried out on the engineering benchmark. And the experimental results have indicated the validation and adaptation of the improved ant colony algorithm proposed in this thesis.Lan Shihai (Mechanical and Electrical Engineering)Supervised by
引文
[1]李军，郭耀煌．物流配送车辆优化调度理论与方法．北京：中国物资出版社，2001：2～3
[2]叶怀珍．现代物流学．北京：高等教育出版社，2003：1～3
[3]Dantizig G, Ramser J. The Truck Dispatching Problem. Management Science, 1959:81～89
[4]Bodin L, Golden B L, Assad A and Ball M. Routing and Scheduling of Vehicles and Crews: The State of The Art. Computers & Operations Research, 1983, 10(2):63～193
[5]Christofides N. Vehicle Routing in the Traveling Salesman Problem: A Guide Tour of Combinatorial Optimization, Wile, Chichester, 985
[6]Golden B L, Assad A. Vehicle Routing: Methods and Studies. Amsterdam: Elsevier Science Publishers, 1988
[7]Altinkemer K, Lavish B. Parallel Savings Based Heuristic for the Delivery Problem. Operations Research, 1991, 39:456～469
[8]Laporte G. The Vehicle Routing Problem: An Overview of Exact and Approximate Algorithms. European Journal of Operational Research 1992, 59:345～358
[9]Salhi S, Rand G K. Incorporating Vehicle Routing into Vehicle Fleet Composition Problem. European Journal Operational Research, 1993,323～330
[10]Oliver L M, Smith D J, Holland J R C.A Study of Permutation Crossover Operators on the Traveling Salesman Problem. Proceedings of the Second International Conference on Genetic Algorithm, Lawrence Erlbaum Associates, 1987, 224～230
[11]Dorigo M,Gambardella L M. Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem.IEEE Transaction on Evolutio nary Computation, 1997,1 (1):53～66
[12]Longo H et al. Solving capacitated arc routing problems using a transformation to the CVRP.Computers & Operations Research, 2006,33:1823-1837
[13] Tavakkoli-Moghaddam R, Safaei N and Gholipour Y.A hybrid simulated annealing for capacitated vehicle routing problems with the independent route length. Applied Mathematics and Computation, 200,176:445-454
[14] Ombuki B, Ross B J and Hanshar F. Multi-Objective Genetic Algorithms for Vehicle Routing Problem with Time Windows. Applied Intelligence, 2006,24:17-30
[15] Russell R A, Chiang W C. Scatter search for the vehicle routing problem with time windows. European Journal of Operational Research, 2006,169:606-622
[16] Alvarenga G B et al.A Hybrid Approach for the Dynamic Vehicle Routing Problem with Time Windows. Proceedings of the Fifth International Conference on Hybrid Intelligent Systems,2005
[17] Potvin J Y, Xu Y and Benyahia I. Vehicle routing and scheduling with dynamic travel times. Computers & Operations Research,2006,33:1129-1137
[18] Fabri A, Recht P. On dynamic pickup and delivery vehicle routing with several time windows and waiting times. Transportation Research Part B,2006,40:335-350
[19] Bent R, Hentenryck P V. A two-stage hybrid algorithm for pickup and delivery vehicle routing problems with time windows. Computers & Operations Research 2006,33:875-893
[20] Nagy G, Salhi S. Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries. European Journal of Operational Research,2005,162:126～141
[21] Wasner M, Zapfel G. An integrated multi-depot hub-location vehicle routing model for network planning of parcel service. International Journal of Production Economics,2004,90:403-419
[22] Fu Ce, Wang Hui, Zhu LiYing. Solving the Vehicle Routing Problem with Stochastic Demands and Customers. Proceedings of the Sixth International Conference on Parallel and Distributed Computing, Applications and Technologies,2005
[23] Wade A C, Salhi S. An investigation into a new class of vehicle routing problem with backhauls. The International Journal of Management Science,2002,30:479-487
[24] Zhong Y J, Cole M H.A vehicle routing problem with backhauls and time windows :a guided local search solution. Transportation Research Part E, 2005,41:131-144
[25] Taniguchi E, Ando N. An Experimental Analysis on Probabilistic Vehicle Routing and Scheduling with ITS. Journal of the Eastern Asia Society for Transportation Studies,2005,6:3052 ～ 3061
[26] Angelelli E, Speranza M G. The periodic vehicle routing problem with intermediate facilities. European Journal of Operational Research, 2002, 137:233-247
[27] Magnantj T L. Combinational Optimization and Vehicle Fleet Planning: Perspectives and Prospects.Networks, 1981,11:179-213
[28] Bodin L D, Golden B L, Assad A A, Ball M. Routing and Scheduling of Vehicles and Crews: The State of Art. Computers & Operations Research, 1983,10:63-211
[29] Golden B L. Introduction to Recent Advances in Vehicle Routing Methods.Transportation Planning Models, 1984
[30] Laporte G. The Vehicle Routing Problem: An Overview of Exact and Approximate Algorithms. European Journal of Operational Research, 1992,59:345-358
[31] Laporte G, Osman I H. Routing Problem: a Bibliography, Ann. Operations Research, 1992,61:227-26
[32] Basnet C, Foulds and Wilson. Heuristic for Vehicle Routing on Tree-Like Networks. Journal of Operational Research Society, 1999,50 (6) :627～635
[33] James P K, Xu Jiefeng. A Set-Partitioning-Based Heuristic for the VSP. Journal on Computing, 1999,11 (2) :161～172
[34] Bramel J, Simchi-levi D.A Location Based Heuristic for General Operations Research, 1995,43:649-660
[35] Desrochers M,Verhoog T W.A New Heuristic for the Fleet Size and Mix Vehicle Routing Problem. Computers & Operations Research,1991,18: 263-274
[36] Evans S R, Norback J PA Heuristic Method for Solving Time Sensitive Routing Problem. Journal Operational Research Society,1984,35(5) :407～414
[37] Ropke S, Pisinger D.A unified heuristic for a large class of Vehicle Routing Problems with Backhauls, European Journal of Operational Research,2006,171:750-775
[38] Hong S C, Park Y B.A heuristic for bi-objective vehicle routing with time window Constraints. International Journal of Production Economics,1999,62:249-258
[39] Tan K C, Lee L H, Ou K. Artificial intelligence heuristics in solving vehicle routing problems with time window constraints. Engineering Applications of Artificial Intelligence,2001,14:825-837
[40] Clarke G, Wright J W. Scheduling of Vehicles from a Central Depot to a Number of Delivery Points. Operations Research,1964,12:568～581
[41] Gillett B, Miller L.A heuristic for the vehicle dispatching problem. Operations Research, 1974,22:340-349
[42] Solomon M M. On the Worst-Case Performance of Some Heuristics for the Vehicle Routing and Scheduling Problem with Time Window Constraints.Network, 1986,16:161-174
[43] Mole R H, Jameson S R.A Sequential Route-building Algorithm Employing Generalized Savings Criterion. Operational Research Quarterly, 1976,27:503-511
[44] Lin S. Computer solutions of the traveling salesman problem. Bell System Computer Journal, 1965,44:2245-2269
[45] Lin S, Kernighan B W. An effective heuristic algorithm for the traveling salesman problem. Operation Research,1973,21:498～516
[46] Potvin J Y, Rousseau J M. An Exchange Heuristic for Routing Problems with Time Windows, Journal of Operational Research Society, 1995,46:1433～1446
[47]Taillard E et al.A Tabu Search Heuristic For The Vehicle Routing Problem With Soft Time Windows. Transportation Science, 1997,31:170～186
[48]Or I. Traveling salesman problem-type combinatorial optimization problems and their relation to the logistics of regional blood banking. Northwestern University, Evansion Ⅱ, 1976
[49]Osman I. Metastrategy Simulated Annealing and Tabu Search Algorithms for the Vehicle Routing Problem. Annals of Operations Research, 1993,41:421～451
[50]Glover F. New Ejection Chain and Alternating Path Methods for Traveling Salesman Problems. In O. Balci, R. Sharda and S. Zenios (eds.),Computer Science and Operations Research-New Developments in their Interfaces Pergamon Press, 1992,491～508
[51]Gendreau M, Hertz A, Laporte G. New Insertion and Postoptimization Procedures for the Traveling Salesman Problem. Operations Research, 1992, 40(6): 1086～1094
[52]钱敏平，龚光鲁．从数学角度看计算智能．科学通报，1998，16：1681～1695
[53]Glover F. Future Paths for Integer Programming and Links to Artificial Intelligence. Computers and Operations Research,1986,13:533～549
[54]Metropolis N, Rosenbluth A, Rosenbluth M, et al. Equation of state calculations by fast computing machines. Journal of Chemical Physics, 1953, 21:1087～1092
[55]Holland J H. Adaptation in Natural and Artificial Systems. Ann Arbor: The University of Michigan Press, 1975
[56]Kennedy J, Eberhart R. Particle swarm optimization. Proceedings of the IEEE International Conference on Neural Networks, 1995,1942～1948
[57]Colorni A,Dorigo M, Maniezzo V, et al. Distributed optimization by ant colonies. Proceedings of the 1st European Conference on Artificial Life, 1991, 134～142
[58]Fermin Alfredo Tang Montané, Roberto Diéguez Galvao. A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service. Computers & Operations Research,2006,33:595～619
[59]Brandao J. A new tabu search algorithm for the vehicle routing problem with backhauls. European Journal of Operational Research,2006,173:540～555
[60]Tavakkoli-Moghaddam R, Safaei N, Gholipour Y.A hybrid simulated annealing for capacitated vehicle routing problems with the independent route length. Applied Mathematics and Computation,2006,176:445～454
[61]Breedam A V. Improvement heuristics for the Vehicle Routing Problem based on Simulated Annealing. European Journal of Operational Research, 1995, 86:480～490
[62]Li N, Zou T, De-bao S. Particle Swarm Optimization for Vehicle Routing Problem. Journal of Systems Engineering,2004,19(6):596～600
[63]Chen Ai-ling, Yang Gen-ke, Wu Zhi-ming. Hybrid discrete particle swarm optimization algorithm for capacitated vehicle routing problem. Journal of Zhejiang University SCIENCE A,2006,7(4):607～614
[64]Alba E, Dorronsoro E. Computing nine new best-so-far solutions for Capacitated VRP with a cellular Genetic Algorithm. Information Processing Letters,2006, 98:225～230
[65]Ombukib B, Ross B J, Hanshar F. Multi-Objective Genetic Algorithms for Vehicle Routing Problem with Time Windows. Applied Intelligence,2006, 24, 17～30
[66]Bell J E, McMullen P R. Ant colony optimization techniques for the vehicle routing problem. Advanced Engineering Informatics,2004,18:41～48
[67]Mazzeo S, Loiseau I. An Ant Colony Algorithm for the Capacitated Vehicle Routing. Electronic Notes in Discrete Mathematics,2004,18:181～186
[68]段海滨．蚁群算法原理及其应用．北京：科学出版社，2005
[69]Dorigo M,Gambardella L M. Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem. IEEE Transaction on Evolutionary Computation, 1997,1 (1):53～66
[70]Walter J, Gutjahr.A Graph-based Ant System and its convergence. Future Generation Computer System,2000,16:837～888
[71]Chang C S, Tian L, Wen F S. A new approach to fault section estimation in power system using ant system. Electric Power System Research, 1999, 49:63～70
[72]Dorigo M, Bonabeau E, Theraulaz G. Ant Algorithms and Stigmergy. Future Generation Computer System,2000,16(8):851～871
[73]王小平，曹立明．遗传算法——理论，应用与软件实现．西安：西安交通大学出版社，2002
[74]Dorigo M, Maniezzo V, Colorni A. The Ant System: optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man and Cybernetics, Part B.1996,26 (1):1～41
[75]Dorigo M, Caro G D, Gambardella L M. Ant algorithm for discrete optimization. Artificial Life,1999,5(2):137～172
[76]郝晋．蚁群优化算法及其在电力系统短期发电计划中的应用研究．重庆：重庆大学硕士学位论文，2002
[77]朱海梅，朱庆保，胡勇．具有自适应杂交特征的蚁群算法．计算机工程与应用，2004(22)，81～83
[78]叶志伟，郑肇葆．蚁群算法中参数α、β、ρ设置的研究——以TSP问题为例．武汉大学学报，2004，29(7)：597～601
[79]王剑，李平，杨春节．蚁群算法的理论与应用．机电工程，2003，20(5)：126～129
[80]张纪会，徐心和．一种新的进化算法——蚁群算法．系统工程理论与实践，1999．3，86～87
[81]Byung Joo Park et al. A hybrid genetic algorithm for the job shop scheduling problems. Computers & Industrial Engineering,2003,45:597～613
[82]Gambardella L M, Dorigo M. Ant-Q: a reinforcement learning approach to the traveling salesman problem. Proceedings of the 12th International Conference on Machine Learning, 1995,252～260
[83]Dorigo M,Gambardella L M.A study of some properties of Ant-Q. Proceedings of the 4th International Conference on Parallel Problem Solving from Nature, 1996,656～665
[84]Stützle T, Hoos H H.MAX-MIN ant system. Future Generation Computer Systems, 2000,16(8):889～914
[85]覃刚力，杨家木．自适应调整信息素的蚁群算法．信息与控制，2002，31(3)：198～201
[86]吴庆洪，张纪会，徐心和．具有变异特征的蚁群算法．计算机研究与发展，1999，36(10)：1240～1245
[87]徐精明，曹先彬，王煦法．多态蚁群算法．中国科学技术大学学报，2005，31(1)：59～65
[88]黄国锐，曹先彬，王煦法．基于信息素扩散的蚁群算法．电子学报，2004，32(5)：865～868
[89]李勇，段正澄．动态蚁群算法求解TSP问题．计算机工程与应用，2003，17：103～106
[90]李炳宇，萧蕴诗．小窗口蚁群算法．计算机工程，2003，29(20)：143～145
[91]萧蕴诗，李炳宇，吴启迪．求解TSP问题的模式学习并行蚁群算法．控制与决策，2004，19(8)：885～888
[92]勒藩，范俊波，谭永东．神经网络与神经计算机．成都：西南交通大学出版社，1991，375～377
[93]李明海，邢桂华．用MATLAB实现中国旅行商问题的求解．微计算机应用，2004，25(2)：218～222
[94]伍文城，肖建．基于蚁群算法的中国旅行商问题满意解．计算机与现代化，2004，8：6～11
[95]燕忠，袁春伟．用蚁群优化算法求解中国旅行商问题．电路与系统学报，2004，9(3)：122～126
[96]王攀，商海燕，潘利群等．基于混合遗传算法的中国旅行商问题满意解．航空计算技术，2000，30(1)：19～21
[97]杨利英，覃征，贺升平等．改进的演化近似算法求解TSP问题．微电子学与计算机，2004，21(6)：126～128
[98]http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/
[99]陈烨．带杂交算子的蚁群算法．计算机工程，2001，27(12)：74～76
[100]丁建立，陈增强，袁著祉．遗传算法与蚂蚁算法的融合．计算机研究与发展，2003，40(9)：1351～1356
[101]翁国栋．蚁群算法与遗传算法对TSP的一种融合．福建电脑，2006，2：115～116
[102]孙力娟，王良俊，王汝传．改进的蚁群算法及其在TSP中的应用研究．通信学报，2004，25(10)：111～116
[103]张建勇，郭耀煌，李军．基于客户满意度的多目标模糊车辆优化调度问题研究．铁道学报，2003，25(2)：15～17
[104]廖洁君，陈燕．城市物流中多目标配送模型．大连海事大学学报，2003，30(4)：82～85
[105]潘志铭，林少聪，李霞．带运力限制车辆路径问题的简易蚁群算法实现．深圳大学学报，2005，22(3)：221～225
[106]张炯，郎茂祥．有时间窗配送车辆调度问题的禁忌搜索算法．北方交通大学学报，2004，28(2)：103～106
[107]贾永基．车辆调度问题优化算法研究．上海：上海交通大学博士学位论文，2004
[108]张潜，高立群，胡祥培，吴畏．物流配送路径多目标优化的聚类——改进遗传算法．控制与决策，2003，18(4)：418～422
[109]冯辉宗，陈勇，刘飞．基于遗传算法的配送车辆优化调度．重庆邮电学院学报，2005，17(1)：93～96
[110]郎茂祥，胡思继．用混合遗传算法求解物流配送路径优化问题的研究．中国管理科学，2002，10(5)：51～56
[111]刘志硕，柴跃廷，申金升．蚁群算法及其在有硬时间窗的车辆路径问题中的应用．计算机集成制造系统，2006，12(4)：596～602
[112]李宁，邹彤，孙德宝．带时间窗车辆路径问题的粒子群算法．系统工程理论与实践，2004，4：130～135
[2]叶怀珍．现代物流学．北京：高等教育出版社，2003：1～3
[3]Dantizig G, Ramser J. The Truck Dispatching Problem. Management Science, 1959:81～89
[4]Bodin L, Golden B L, Assad A and Ball M. Routing and Scheduling of Vehicles and Crews: The State of The Art. Computers & Operations Research, 1983, 10(2):63～193
[5]Christofides N. Vehicle Routing in the Traveling Salesman Problem: A Guide Tour of Combinatorial Optimization, Wile, Chichester, 985
[6]Golden B L, Assad A. Vehicle Routing: Methods and Studies. Amsterdam: Elsevier Science Publishers, 1988
[7]Altinkemer K, Lavish B. Parallel Savings Based Heuristic for the Delivery Problem. Operations Research, 1991, 39:456～469
[8]Laporte G. The Vehicle Routing Problem: An Overview of Exact and Approximate Algorithms. European Journal of Operational Research 1992, 59:345～358
[9]Salhi S, Rand G K. Incorporating Vehicle Routing into Vehicle Fleet Composition Problem. European Journal Operational Research, 1993,323～330
[10]Oliver L M, Smith D J, Holland J R C.A Study of Permutation Crossover Operators on the Traveling Salesman Problem. Proceedings of the Second International Conference on Genetic Algorithm, Lawrence Erlbaum Associates, 1987, 224～230
[11]Dorigo M,Gambardella L M. Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem.IEEE Transaction on Evolutio nary Computation, 1997,1 (1):53～66
[12]Longo H et al. Solving capacitated arc routing problems using a transformation to the CVRP.Computers & Operations Research, 2006,33:1823-1837
[13] Tavakkoli-Moghaddam R, Safaei N and Gholipour Y.A hybrid simulated annealing for capacitated vehicle routing problems with the independent route length. Applied Mathematics and Computation, 200,176:445-454
[14] Ombuki B, Ross B J and Hanshar F. Multi-Objective Genetic Algorithms for Vehicle Routing Problem with Time Windows. Applied Intelligence, 2006,24:17-30
[15] Russell R A, Chiang W C. Scatter search for the vehicle routing problem with time windows. European Journal of Operational Research, 2006,169:606-622
[16] Alvarenga G B et al.A Hybrid Approach for the Dynamic Vehicle Routing Problem with Time Windows. Proceedings of the Fifth International Conference on Hybrid Intelligent Systems,2005
[17] Potvin J Y, Xu Y and Benyahia I. Vehicle routing and scheduling with dynamic travel times. Computers & Operations Research,2006,33:1129-1137
[18] Fabri A, Recht P. On dynamic pickup and delivery vehicle routing with several time windows and waiting times. Transportation Research Part B,2006,40:335-350
[19] Bent R, Hentenryck P V. A two-stage hybrid algorithm for pickup and delivery vehicle routing problems with time windows. Computers & Operations Research 2006,33:875-893
[20] Nagy G, Salhi S. Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries. European Journal of Operational Research,2005,162:126～141
[21] Wasner M, Zapfel G. An integrated multi-depot hub-location vehicle routing model for network planning of parcel service. International Journal of Production Economics,2004,90:403-419
[22] Fu Ce, Wang Hui, Zhu LiYing. Solving the Vehicle Routing Problem with Stochastic Demands and Customers. Proceedings of the Sixth International Conference on Parallel and Distributed Computing, Applications and Technologies,2005
[23] Wade A C, Salhi S. An investigation into a new class of vehicle routing problem with backhauls. The International Journal of Management Science,2002,30:479-487
[24] Zhong Y J, Cole M H.A vehicle routing problem with backhauls and time windows :a guided local search solution. Transportation Research Part E, 2005,41:131-144
[25] Taniguchi E, Ando N. An Experimental Analysis on Probabilistic Vehicle Routing and Scheduling with ITS. Journal of the Eastern Asia Society for Transportation Studies,2005,6:3052 ～ 3061
[26] Angelelli E, Speranza M G. The periodic vehicle routing problem with intermediate facilities. European Journal of Operational Research, 2002, 137:233-247
[27] Magnantj T L. Combinational Optimization and Vehicle Fleet Planning: Perspectives and Prospects.Networks, 1981,11:179-213
[28] Bodin L D, Golden B L, Assad A A, Ball M. Routing and Scheduling of Vehicles and Crews: The State of Art. Computers & Operations Research, 1983,10:63-211
[29] Golden B L. Introduction to Recent Advances in Vehicle Routing Methods.Transportation Planning Models, 1984
[30] Laporte G. The Vehicle Routing Problem: An Overview of Exact and Approximate Algorithms. European Journal of Operational Research, 1992,59:345-358
[31] Laporte G, Osman I H. Routing Problem: a Bibliography, Ann. Operations Research, 1992,61:227-26
[32] Basnet C, Foulds and Wilson. Heuristic for Vehicle Routing on Tree-Like Networks. Journal of Operational Research Society, 1999,50 (6) :627～635
[33] James P K, Xu Jiefeng. A Set-Partitioning-Based Heuristic for the VSP. Journal on Computing, 1999,11 (2) :161～172
[34] Bramel J, Simchi-levi D.A Location Based Heuristic for General Operations Research, 1995,43:649-660
[35] Desrochers M,Verhoog T W.A New Heuristic for the Fleet Size and Mix Vehicle Routing Problem. Computers & Operations Research,1991,18: 263-274
[36] Evans S R, Norback J PA Heuristic Method for Solving Time Sensitive Routing Problem. Journal Operational Research Society,1984,35(5) :407～414
[37] Ropke S, Pisinger D.A unified heuristic for a large class of Vehicle Routing Problems with Backhauls, European Journal of Operational Research,2006,171:750-775
[38] Hong S C, Park Y B.A heuristic for bi-objective vehicle routing with time window Constraints. International Journal of Production Economics,1999,62:249-258
[39] Tan K C, Lee L H, Ou K. Artificial intelligence heuristics in solving vehicle routing problems with time window constraints. Engineering Applications of Artificial Intelligence,2001,14:825-837
[40] Clarke G, Wright J W. Scheduling of Vehicles from a Central Depot to a Number of Delivery Points. Operations Research,1964,12:568～581
[41] Gillett B, Miller L.A heuristic for the vehicle dispatching problem. Operations Research, 1974,22:340-349
[42] Solomon M M. On the Worst-Case Performance of Some Heuristics for the Vehicle Routing and Scheduling Problem with Time Window Constraints.Network, 1986,16:161-174
[43] Mole R H, Jameson S R.A Sequential Route-building Algorithm Employing Generalized Savings Criterion. Operational Research Quarterly, 1976,27:503-511
[44] Lin S. Computer solutions of the traveling salesman problem. Bell System Computer Journal, 1965,44:2245-2269
[45] Lin S, Kernighan B W. An effective heuristic algorithm for the traveling salesman problem. Operation Research,1973,21:498～516
[46] Potvin J Y, Rousseau J M. An Exchange Heuristic for Routing Problems with Time Windows, Journal of Operational Research Society, 1995,46:1433～1446
[47]Taillard E et al.A Tabu Search Heuristic For The Vehicle Routing Problem With Soft Time Windows. Transportation Science, 1997,31:170～186
[48]Or I. Traveling salesman problem-type combinatorial optimization problems and their relation to the logistics of regional blood banking. Northwestern University, Evansion Ⅱ, 1976
[49]Osman I. Metastrategy Simulated Annealing and Tabu Search Algorithms for the Vehicle Routing Problem. Annals of Operations Research, 1993,41:421～451
[50]Glover F. New Ejection Chain and Alternating Path Methods for Traveling Salesman Problems. In O. Balci, R. Sharda and S. Zenios (eds.),Computer Science and Operations Research-New Developments in their Interfaces Pergamon Press, 1992,491～508
[51]Gendreau M, Hertz A, Laporte G. New Insertion and Postoptimization Procedures for the Traveling Salesman Problem. Operations Research, 1992, 40(6): 1086～1094
[52]钱敏平，龚光鲁．从数学角度看计算智能．科学通报，1998，16：1681～1695
[53]Glover F. Future Paths for Integer Programming and Links to Artificial Intelligence. Computers and Operations Research,1986,13:533～549
[54]Metropolis N, Rosenbluth A, Rosenbluth M, et al. Equation of state calculations by fast computing machines. Journal of Chemical Physics, 1953, 21:1087～1092
[55]Holland J H. Adaptation in Natural and Artificial Systems. Ann Arbor: The University of Michigan Press, 1975
[56]Kennedy J, Eberhart R. Particle swarm optimization. Proceedings of the IEEE International Conference on Neural Networks, 1995,1942～1948
[57]Colorni A,Dorigo M, Maniezzo V, et al. Distributed optimization by ant colonies. Proceedings of the 1st European Conference on Artificial Life, 1991, 134～142
[58]Fermin Alfredo Tang Montané, Roberto Diéguez Galvao. A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service. Computers & Operations Research,2006,33:595～619
[59]Brandao J. A new tabu search algorithm for the vehicle routing problem with backhauls. European Journal of Operational Research,2006,173:540～555
[60]Tavakkoli-Moghaddam R, Safaei N, Gholipour Y.A hybrid simulated annealing for capacitated vehicle routing problems with the independent route length. Applied Mathematics and Computation,2006,176:445～454
[61]Breedam A V. Improvement heuristics for the Vehicle Routing Problem based on Simulated Annealing. European Journal of Operational Research, 1995, 86:480～490
[62]Li N, Zou T, De-bao S. Particle Swarm Optimization for Vehicle Routing Problem. Journal of Systems Engineering,2004,19(6):596～600
[63]Chen Ai-ling, Yang Gen-ke, Wu Zhi-ming. Hybrid discrete particle swarm optimization algorithm for capacitated vehicle routing problem. Journal of Zhejiang University SCIENCE A,2006,7(4):607～614
[64]Alba E, Dorronsoro E. Computing nine new best-so-far solutions for Capacitated VRP with a cellular Genetic Algorithm. Information Processing Letters,2006, 98:225～230
[65]Ombukib B, Ross B J, Hanshar F. Multi-Objective Genetic Algorithms for Vehicle Routing Problem with Time Windows. Applied Intelligence,2006, 24, 17～30
[66]Bell J E, McMullen P R. Ant colony optimization techniques for the vehicle routing problem. Advanced Engineering Informatics,2004,18:41～48
[67]Mazzeo S, Loiseau I. An Ant Colony Algorithm for the Capacitated Vehicle Routing. Electronic Notes in Discrete Mathematics,2004,18:181～186
[68]段海滨．蚁群算法原理及其应用．北京：科学出版社，2005
[69]Dorigo M,Gambardella L M. Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem. IEEE Transaction on Evolutionary Computation, 1997,1 (1):53～66
[70]Walter J, Gutjahr.A Graph-based Ant System and its convergence. Future Generation Computer System,2000,16:837～888
[71]Chang C S, Tian L, Wen F S. A new approach to fault section estimation in power system using ant system. Electric Power System Research, 1999, 49:63～70
[72]Dorigo M, Bonabeau E, Theraulaz G. Ant Algorithms and Stigmergy. Future Generation Computer System,2000,16(8):851～871
[73]王小平，曹立明．遗传算法——理论，应用与软件实现．西安：西安交通大学出版社，2002
[74]Dorigo M, Maniezzo V, Colorni A. The Ant System: optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man and Cybernetics, Part B.1996,26 (1):1～41
[75]Dorigo M, Caro G D, Gambardella L M. Ant algorithm for discrete optimization. Artificial Life,1999,5(2):137～172
[76]郝晋．蚁群优化算法及其在电力系统短期发电计划中的应用研究．重庆：重庆大学硕士学位论文，2002
[77]朱海梅，朱庆保，胡勇．具有自适应杂交特征的蚁群算法．计算机工程与应用，2004(22)，81～83
[78]叶志伟，郑肇葆．蚁群算法中参数α、β、ρ设置的研究——以TSP问题为例．武汉大学学报，2004，29(7)：597～601
[79]王剑，李平，杨春节．蚁群算法的理论与应用．机电工程，2003，20(5)：126～129
[80]张纪会，徐心和．一种新的进化算法——蚁群算法．系统工程理论与实践，1999．3，86～87
[81]Byung Joo Park et al. A hybrid genetic algorithm for the job shop scheduling problems. Computers & Industrial Engineering,2003,45:597～613
[82]Gambardella L M, Dorigo M. Ant-Q: a reinforcement learning approach to the traveling salesman problem. Proceedings of the 12th International Conference on Machine Learning, 1995,252～260
[83]Dorigo M,Gambardella L M.A study of some properties of Ant-Q. Proceedings of the 4th International Conference on Parallel Problem Solving from Nature, 1996,656～665
[84]Stützle T, Hoos H H.MAX-MIN ant system. Future Generation Computer Systems, 2000,16(8):889～914
[85]覃刚力，杨家木．自适应调整信息素的蚁群算法．信息与控制，2002，31(3)：198～201
[86]吴庆洪，张纪会，徐心和．具有变异特征的蚁群算法．计算机研究与发展，1999，36(10)：1240～1245
[87]徐精明，曹先彬，王煦法．多态蚁群算法．中国科学技术大学学报，2005，31(1)：59～65
[88]黄国锐，曹先彬，王煦法．基于信息素扩散的蚁群算法．电子学报，2004，32(5)：865～868
[89]李勇，段正澄．动态蚁群算法求解TSP问题．计算机工程与应用，2003，17：103～106
[90]李炳宇，萧蕴诗．小窗口蚁群算法．计算机工程，2003，29(20)：143～145
[91]萧蕴诗，李炳宇，吴启迪．求解TSP问题的模式学习并行蚁群算法．控制与决策，2004，19(8)：885～888
[92]勒藩，范俊波，谭永东．神经网络与神经计算机．成都：西南交通大学出版社，1991，375～377
[93]李明海，邢桂华．用MATLAB实现中国旅行商问题的求解．微计算机应用，2004，25(2)：218～222
[94]伍文城，肖建．基于蚁群算法的中国旅行商问题满意解．计算机与现代化，2004，8：6～11
[95]燕忠，袁春伟．用蚁群优化算法求解中国旅行商问题．电路与系统学报，2004，9(3)：122～126
[96]王攀，商海燕，潘利群等．基于混合遗传算法的中国旅行商问题满意解．航空计算技术，2000，30(1)：19～21
[97]杨利英，覃征，贺升平等．改进的演化近似算法求解TSP问题．微电子学与计算机，2004，21(6)：126～128
[98]http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/
[99]陈烨．带杂交算子的蚁群算法．计算机工程，2001，27(12)：74～76
[100]丁建立，陈增强，袁著祉．遗传算法与蚂蚁算法的融合．计算机研究与发展，2003，40(9)：1351～1356
[101]翁国栋．蚁群算法与遗传算法对TSP的一种融合．福建电脑，2006，2：115～116
[102]孙力娟，王良俊，王汝传．改进的蚁群算法及其在TSP中的应用研究．通信学报，2004，25(10)：111～116
[103]张建勇，郭耀煌，李军．基于客户满意度的多目标模糊车辆优化调度问题研究．铁道学报，2003，25(2)：15～17
[104]廖洁君，陈燕．城市物流中多目标配送模型．大连海事大学学报，2003，30(4)：82～85
[105]潘志铭，林少聪，李霞．带运力限制车辆路径问题的简易蚁群算法实现．深圳大学学报，2005，22(3)：221～225
[106]张炯，郎茂祥．有时间窗配送车辆调度问题的禁忌搜索算法．北方交通大学学报，2004，28(2)：103～106
[107]贾永基．车辆调度问题优化算法研究．上海：上海交通大学博士学位论文，2004
[108]张潜，高立群，胡祥培，吴畏．物流配送路径多目标优化的聚类——改进遗传算法．控制与决策，2003，18(4)：418～422
[109]冯辉宗，陈勇，刘飞．基于遗传算法的配送车辆优化调度．重庆邮电学院学报，2005，17(1)：93～96
[110]郎茂祥，胡思继．用混合遗传算法求解物流配送路径优化问题的研究．中国管理科学，2002，10(5)：51～56
[111]刘志硕，柴跃廷，申金升．蚁群算法及其在有硬时间窗的车辆路径问题中的应用．计算机集成制造系统，2006，12(4)：596～602
[112]李宁，邹彤，孙德宝．带时间窗车辆路径问题的粒子群算法．系统工程理论与实践，2004，4：130～135