有时间窗车辆路径问题的模型及算法
|
摘要
配送是物流系统中很重要的一个环节,是一系列狭义的物流活动的集成,它要求在规定的时间内以一定的方式将确定的货物送到指定的地点。而车辆路径问题是研究货物运输成本最小的物流配送问题。车辆路径问题是运输组织优化中的核心问题,由于它将运筹学理论与生产实践紧密地结合,因此近几十年取得了丰富的研究成果,并且被称为“最近几十年运筹学领域最成功的研究之一”。
本文分析和总结了车辆路径问题的历史和研究现状,以及常用模型、时间复杂度,以综合性能的角度对求解VRPTW问题的算法进行了一定的归纳和分析,并在此基础上确定了本文的研究方法和目标。同时结合实际提出了本文的研究问题——带时间窗的车辆路径问题(VRPTW),建立了以车辆容量和客户需求等为约束条件,以配送运输成本为目标函数的VRPTW数学模型。提出了一种两步优化的实现策略。第一步,选取动态的push forward insertion heuristics(StochasticPFIH)算法产生机制构建问题的初始解,保证了初始解的多样性,同时在产生的初始解中设置了限制条件,实现对初始解的筛选,为第二阶段路径优化提供了高质量的初始解;以改进的大规模邻域搜索为新解产生机制,并将模拟退火算法和大规模邻域搜索算法混合来进行路径优化,得到问题的最优解,该混合算法充分利用了两种算法的优点,克服了它们的缺点。第二步,提出一种时间窗修正规则来调整时间窗,使得车辆在每个客户的等待时间为零,真正实现了路径的优化,节省了成本,并给出了理论证明。最后通过VC++编程在计算机上实现,以Solomon的标准数据中的C101系列数据进行数值实验,实验结果验证了本文算法的有效性。
Distribution plays an important role in logistic system, it is the integration of a series of logistic campaign in a narrow sense, and logistic distribution requires delivering the right commodities to the right place by the right method at the right time. Vehicle routing problem involves the design of a set of minimum-cost vehicle routes, delivering the right commodities to the right location by the very method at the very time. So vehicle routing problem represents a very important part of any logistic distribution systems and they are named as one of the most successful areas in Operations Research in the past decades.
In this dissertation, the main research work and innovative points as follows:We firstly describe the characteristics and classification of these problems, and the state-of-the-art in the solution algorithms. On the base of reality, we purpose the research problem—vehicle routing problem with time window (VRPTW) and construct a mathematical model: defines an objective function. Meanwhile,we give a review of the past research on vehicle routing problems and their solution methods, establishing the base of algorithm in this dissertation. In this paper,we propose a two-stage optimization strategy for VRPTW. In the first step, for constructing a good initial solution ,this work used the stochastic PFIH, which based on the algorithm known as Push-Forward Insertion Heuristic (PFIH), guaranteeing the diversity of the initial solution,at the same time , give a limit in the process of the constructing initial solution, realizing the filtration of initial solution. The producing mechanism of the new solution is betterment of large neighbor search, then a different hybrid system based on the combination of SA and LNS is proposed to optimize the initial solution .In the second step,a regression iterative strategy is put forward to tune time windows for the customers and figure out the best time for each vehicle departing, it can make the total waiting time zero. Finally, this method is implemented on computer in VC++. It is proved by the experiment that the hybrid strategy can solve VRPTW efficiently and quickly .Comparing with other algorithms, it has practicality and effectiveness, simultaneously, author provide an efficient algorithm to solve VRPTW.
本文分析和总结了车辆路径问题的历史和研究现状,以及常用模型、时间复杂度,以综合性能的角度对求解VRPTW问题的算法进行了一定的归纳和分析,并在此基础上确定了本文的研究方法和目标。同时结合实际提出了本文的研究问题——带时间窗的车辆路径问题(VRPTW),建立了以车辆容量和客户需求等为约束条件,以配送运输成本为目标函数的VRPTW数学模型。提出了一种两步优化的实现策略。第一步,选取动态的push forward insertion heuristics(StochasticPFIH)算法产生机制构建问题的初始解,保证了初始解的多样性,同时在产生的初始解中设置了限制条件,实现对初始解的筛选,为第二阶段路径优化提供了高质量的初始解;以改进的大规模邻域搜索为新解产生机制,并将模拟退火算法和大规模邻域搜索算法混合来进行路径优化,得到问题的最优解,该混合算法充分利用了两种算法的优点,克服了它们的缺点。第二步,提出一种时间窗修正规则来调整时间窗,使得车辆在每个客户的等待时间为零,真正实现了路径的优化,节省了成本,并给出了理论证明。最后通过VC++编程在计算机上实现,以Solomon的标准数据中的C101系列数据进行数值实验,实验结果验证了本文算法的有效性。
Distribution plays an important role in logistic system, it is the integration of a series of logistic campaign in a narrow sense, and logistic distribution requires delivering the right commodities to the right place by the right method at the right time. Vehicle routing problem involves the design of a set of minimum-cost vehicle routes, delivering the right commodities to the right location by the very method at the very time. So vehicle routing problem represents a very important part of any logistic distribution systems and they are named as one of the most successful areas in Operations Research in the past decades.
In this dissertation, the main research work and innovative points as follows:We firstly describe the characteristics and classification of these problems, and the state-of-the-art in the solution algorithms. On the base of reality, we purpose the research problem—vehicle routing problem with time window (VRPTW) and construct a mathematical model: defines an objective function. Meanwhile,we give a review of the past research on vehicle routing problems and their solution methods, establishing the base of algorithm in this dissertation. In this paper,we propose a two-stage optimization strategy for VRPTW. In the first step, for constructing a good initial solution ,this work used the stochastic PFIH, which based on the algorithm known as Push-Forward Insertion Heuristic (PFIH), guaranteeing the diversity of the initial solution,at the same time , give a limit in the process of the constructing initial solution, realizing the filtration of initial solution. The producing mechanism of the new solution is betterment of large neighbor search, then a different hybrid system based on the combination of SA and LNS is proposed to optimize the initial solution .In the second step,a regression iterative strategy is put forward to tune time windows for the customers and figure out the best time for each vehicle departing, it can make the total waiting time zero. Finally, this method is implemented on computer in VC++. It is proved by the experiment that the hybrid strategy can solve VRPTW efficiently and quickly .Comparing with other algorithms, it has practicality and effectiveness, simultaneously, author provide an efficient algorithm to solve VRPTW.
引文
[1]戴锡.车辆路线问题的二阶段启发式算法及其在现代物流配送中的应用.博士论文.上海;复旦大学,2004
[2]张文修,梁怡。遗传算法的数学基础.西安交通大学出版社.[M]2000.
[3]郭耀煌等.运筹学与工程分析.中国建筑工业出版社,[M]2002,188-245.
[4]Taillard,E.,P.Badeau,M.Gendreau,F.Guertin,J.Y.Potvin.A Tabu Search Heuristics for the Vehicle Routing with Soft Time Windows.Transportation Science,1997,31(3);170-168.
[5]DANTZIG G B,RAMSER K B.The truck dispatch Problem Management Science[J].Management Science,1959; 12(1);80-91.
[6]Christofides N.Mingozzi A.Toth P.The Vehicle Routing Problem[C].Combinational Optimization,New York'Johnly Wiley,1979.
[7]LBodin,B.L.Golden,A.Assad and M.Bal.Routing And Scheduling of Vehicles And Crews;The State of The Art.Computers & Operations Research,Vol.10,No.2;63-193.
[8]E.K.Baker(1983).An Exact Algorithm For The Time-constrained Traveling Salesman Problem.Operations Reaearch 1983(31);938-945.
[9]M.Solomon.On the Worst-Case Performance of Some Heuristics for the Vehicle Routing and Scheduling Problem with Time Window Constraints.[J]Networks 1986(16);161-174.
[10]AWJ Kolen,Kan AHG Rinnooy and HWJM Trienekens.Vehicle Routing With Time Windows.[J]Operations Research 1987(35);266-273.
[11]M.M.Solomon.Algorithms For The Vehicle Routing And Scheduling Problems With Time Windows Constraints.[J]Operations Research 1987(35);254-265.
[12]M.Desrochers,J.Desrosiers and M.M.Solomon.A New Optimization Algorithm For The Vehicle Routing Problem With Time Windows.[J]Operations Research 1992(40);342-354.
[13]M.L.Fisher.Optimal Solution of Vehicle Routing Problems Using Minimum K-Trees.[J]Operations Research1994(42);626-642.
[14]N.Kohl and OBG Madsen.An Optimization Algorithm For The Vehicle Routing Problem With Time Windows Based On Lagrangian Relaxation.[J]Operations Research 1997(45);395-406.
[15]G.Clarke and J.V.Wright.Scheduling of vehicles from a central depot to a number of delivery points.[J]Operations Research,1964(12);568-581.
[16]B.L.Garcia,J.Y.Potvin and J.M.Rousseau.A Parallel Implementation of The Tabu Search Heuristic For Vehicle Routing Problems With Time Windows Constraints.[J]Computers &Operations Research,1994(21);1025-1033.
[17] Y. Rochat and E. Taillard. Probabilistic Diversification and Intensification in Local Search for Vehicle Routing. [J]Journal of Heuristics,1995(1): 147-167.
[18] S.R.Thangiah, K.E. Nygard and P.L.Juell. GIDEON:A Genetic Algorithm System for Vehicle Routing with Time Windows. [J]Proceedings of Seventh IEEE Conference on Artificial Intelligence Applications, IEEE Computer Society Press, Los Alamitos.1991, 322-328.
[19] R.H.Mole and S.R.Jameson. A sequential route-building algorithm employing a generalized savings criterion. [J]Operational Research Quarterly, 1976 (27):503～511.
[20] B.Gillett and L.R.Miller. A heuristic algorithm for the vehicle dispatch problem. [J]Operations Research, 1974(22):340～349.
[21] S.Lin.Computer Solutions of the Traveling Salesman Problem. [J] Bell System Technical Journal ,1965(44):2245～2269.
[22] R.Russell .An Effective Heuristic for the M-tour Traveling Salesman Problem with Some Side Conditions. [J] Operations Research, 1977(25): 517-524.
[23] E.K.Baker and J.R.Schaffer. Solution Improvement Heuristics for the Vehicle Routing and Scheduling Problem with Time Window Constraints. [J] American Journal of Mathematical Management Sciences, 1986(6):261～300.
[24] J.Y.Potvin and J.M Rousseau.An Exchange Heuristic For Routing Problems With Time Windows. [J]Journal of Operational Research Society. 1995(46): 1433-1446.
[25] E.Taillard et al .A Tabu Search Heuristic For The Vehicle Routing Problem With Soft Time Windows. [J] Transportation Science, 1997(31): 170-186.
[26] F.Glover.New Ejection Chain and Alternating Path Methods for Traveling Salesman Problems. [J]Computer Science and Operations Research: New Developments in Their Interfaces.O.R. Balci Sharda, and S. Zenios (eds), Pergamon Press, Oxford .1992: 449-509.
[27] M.Gendreau, A.Hertz and GLaporte. New Insertion And Postoptimization Procedures For The Traveling Salesman Problem. [J] Operations Research, 1992(40):1086～1094.
[28] P.M.Thompson and H.N. Psaraftis. Cyclic Transfer Algorithms for Multivehicle Routing and Scheduling Problems. [J]Operations Research,1993(41): 935-946.
[29] J.Homberger and H.Gehring.Two Evolutionary Metaheuristics For The Vehicle Routing Problem With Time Windows. [J] INFOR1999(37):297～318.
[30] H.Gehring and J. Homberger. A Parallel Hybrid Evolutionary Metaheuristic for the VehicleRouting Problem with Time Windows. [J]Proceedings of EUROGEN99, K.Miettinen, M.Makela and J. Toivanen (eds), University of Jyvaskyla, Finland. 1999,57-64.
[31] M.L. Fisher and R. Jaikumar. A generalized assignment heuristic for the vehicle routing problem".[J] Networks, 1981(11):109～124.
[32] J. Bramel and D. Simchi-Levi. A location based heuristic for general routing problems. [J]Operations Research, 1995(43):649～660.
[33] N. Christofides, A.Mingozzi, and P.Toth. The vehicle routing problem. In: N. Christofides, A.Mingozzi, P.Toth.et al. eds. Combinatorial Optimization, Chichester: Wiley, 1979. 315-338.
[34] N.Christofides. The vehicle routing problem. [J]RAIRO, 1976(10):55～70.
[35] D.M. Ryan, C. Hjorring, and F. Glover. Extensions of the petal method for vehicle routing. [J] Journal of Operational Research Society, 1993(44): 289-296.
[36] M. Balinski and R.Quandt. On an integer program for a delivery problem. [J]Operations Research, 1964(12): 300-304.
[37] B.A. Foster and D.M. Ryan. An integer programming approach to the vehicle scheduling problem. [J]Operations Research, 1976(27): 367-124.
[38] J. Renaud, F.F. Boctor, and G. Laporte. An improved petal heuristic for the vehicle routing problem. [J] Journal of Operational Research Society, 1996(47):329～336.
[39] J.E.Beasley. Route-first cluster-second methods for vehicle routing. [J] Omega, 1983(11):403-408.
[40] H.Gehring and J.Homberger. Parallelization of a Two-Phase Meta-heuristic for Routing Problems with Time Windows. [J] Asia-Pacific Journal of Operational Research 2001(18): 35-47.
[41] M.Haimovich and A.H.GRinnooy Kan. Bounds and heuristics for capacitated routing problems. [J] Mathematics of Operations Research, 1985(10):527～542.
[42] W.Chiang and R.Russell. Simulated Annealing Metaheuristics For The Vehicle Routing Problem With Time Windows. [J] Annals of Operations Research .1996(63):3～27.
[43] K.C.Tan, L.H. Lee and K.Q. Zhu. Heuristic Methods for Vehicle Routing Problem with Time Windows. [J]Proceedings of the 6~(th) International Symposium on Artificial Intelligence &Mathematics, Ft. Lauderdale, Florida.2000.
[44] H.Li, A.Lim, J.Huang. Local Search with Annealing-like Restarts to solve the VRPTW. [J] European Journal of Operational Research 2003,Vol.150,P115.
[45] L.M.Gambardella, E. Taillard and G. Agazzi. MACS-VRPTW: A Multiple Ant Colony System for Vehicle Routing Problems with Time Windows. [J] New Ideas in Optimization,,D. Come, M. Dorigo and F. Glover (eds), McGraw-Hill, London. 1999:63-76.
[46] P.Kilby, P. Prosser and P. Shaw. Guided Local Search for the Problem with Time Windows. [J]META-HEURISTICS Advances and Treads in Local Search Paradigms for Optimization, S.Voss,S.Martello,I.H.Osman and C.Roucatirol(eds), Kluwer Academic Publishers, Boston., 1999, 473-486.
[47] G.Kontoravdis and J.Bard, A GRASP For The Vehicle Routing Problem With Time Windows, [J]Journal on Computing 7,10-23.
[48]O.Braysy,and M.Gendreau,Evolutionary Algorithms for the Vehicle Routing Problem with Time Windows.[J]Working paper,SINTEF Applied Mathematics,Department of Optimization,Norway.2002.
[49]O.Braysy,and,G.Hasle and W.Dullaert.A Fast Local Search Algorithm for the Vehicle Routing Problem with Time Windows.[J]Working paper,SINTEF Applied Mathematics,Department of Optimization,Norway.2002.
[50]http;//web.cba.neu.edu/～msolomon/problems.htm
[51]Leong H W,Liu M.A multi-agent algorithm for vehicle routing problem with time window[J].ACM 2006;106-111.
[52]Alvarenga G B,Mateus G R.A two-phase genetic and set partitioning approach for the vehicle routing problem with time windows[J].Proc 4th International Conference on Hybrid Intelligent Systems,2004;428-433.
[53]Andrew Lim,Fan Wang.A Smoothed Dynamic Tabu Search Embedded GRASP for m-VRPTW.[J]Proceedings of the 16th IEEE International Conference on Tools with Artificial Intelligence(ICTAI2004).
[54]Alvarenga G B,Mateus G R.A two-phase genetic and set partitioning approach for the vehicle routing problem with time windows[J].Proc 4th International Conference on Hybrid Intelligent Systems,2004;428-433.
[55]Oliveira,H.C.B.,Vasconcelos,G.C.,Alvarenga,G.B.Reducing traveled distance in the vehicle routing problem with time windows using a multi-start simulated annealing.[J]2006 International Joint Conference on Neural Networks Sheraton Vancouver Wall Center Hotel,Vancouver,BC,Canada 2006(7);16-21.
[56]李大卫,王莉,王梦光.一个求解带有时间窗口约束的车辆路径问题的启发式算法[J].系统工程,1998,16(4);20-29.
[57]谢秉磊,李军,郭耀煌.有时间窗的非满载车辆调度问题的遗传算法[J].系统工程学报,2000,15(3);290-294。
[58]宋厚冰,蔡远利.有时间窗约束的车辆路径问题的改进遗传算法[J].交通与计算机,2003,21(4);25-27.
[59]刘小兰等.有时间窗的车辆路径问题的近似算法研究[J].计算机集成制造系统,2004,10(7);825-831.
[60]吴璟莉,李陶深.遗传算法与禁忌搜索算法的混合策略在VRPTW问题上的应用[J].计算机工程与应用2004(18);54-57.
[61]王德东,陈术山,郑丕谔.确定车辆数的有时间窗车辆选径问题的混合算法[J].计算机应用,2006 26(2);482-484.
[62]占书芳.并行算法在带软时间窗车辆路径问题中的应用研究.硕士学位论文.武汉;武汉理工大学,2006
[2]张文修,梁怡。遗传算法的数学基础.西安交通大学出版社.[M]2000.
[3]郭耀煌等.运筹学与工程分析.中国建筑工业出版社,[M]2002,188-245.
[4]Taillard,E.,P.Badeau,M.Gendreau,F.Guertin,J.Y.Potvin.A Tabu Search Heuristics for the Vehicle Routing with Soft Time Windows.Transportation Science,1997,31(3);170-168.
[5]DANTZIG G B,RAMSER K B.The truck dispatch Problem Management Science[J].Management Science,1959; 12(1);80-91.
[6]Christofides N.Mingozzi A.Toth P.The Vehicle Routing Problem[C].Combinational Optimization,New York'Johnly Wiley,1979.
[7]LBodin,B.L.Golden,A.Assad and M.Bal.Routing And Scheduling of Vehicles And Crews;The State of The Art.Computers & Operations Research,Vol.10,No.2;63-193.
[8]E.K.Baker(1983).An Exact Algorithm For The Time-constrained Traveling Salesman Problem.Operations Reaearch 1983(31);938-945.
[9]M.Solomon.On the Worst-Case Performance of Some Heuristics for the Vehicle Routing and Scheduling Problem with Time Window Constraints.[J]Networks 1986(16);161-174.
[10]AWJ Kolen,Kan AHG Rinnooy and HWJM Trienekens.Vehicle Routing With Time Windows.[J]Operations Research 1987(35);266-273.
[11]M.M.Solomon.Algorithms For The Vehicle Routing And Scheduling Problems With Time Windows Constraints.[J]Operations Research 1987(35);254-265.
[12]M.Desrochers,J.Desrosiers and M.M.Solomon.A New Optimization Algorithm For The Vehicle Routing Problem With Time Windows.[J]Operations Research 1992(40);342-354.
[13]M.L.Fisher.Optimal Solution of Vehicle Routing Problems Using Minimum K-Trees.[J]Operations Research1994(42);626-642.
[14]N.Kohl and OBG Madsen.An Optimization Algorithm For The Vehicle Routing Problem With Time Windows Based On Lagrangian Relaxation.[J]Operations Research 1997(45);395-406.
[15]G.Clarke and J.V.Wright.Scheduling of vehicles from a central depot to a number of delivery points.[J]Operations Research,1964(12);568-581.
[16]B.L.Garcia,J.Y.Potvin and J.M.Rousseau.A Parallel Implementation of The Tabu Search Heuristic For Vehicle Routing Problems With Time Windows Constraints.[J]Computers &Operations Research,1994(21);1025-1033.
[17] Y. Rochat and E. Taillard. Probabilistic Diversification and Intensification in Local Search for Vehicle Routing. [J]Journal of Heuristics,1995(1): 147-167.
[18] S.R.Thangiah, K.E. Nygard and P.L.Juell. GIDEON:A Genetic Algorithm System for Vehicle Routing with Time Windows. [J]Proceedings of Seventh IEEE Conference on Artificial Intelligence Applications, IEEE Computer Society Press, Los Alamitos.1991, 322-328.
[19] R.H.Mole and S.R.Jameson. A sequential route-building algorithm employing a generalized savings criterion. [J]Operational Research Quarterly, 1976 (27):503～511.
[20] B.Gillett and L.R.Miller. A heuristic algorithm for the vehicle dispatch problem. [J]Operations Research, 1974(22):340～349.
[21] S.Lin.Computer Solutions of the Traveling Salesman Problem. [J] Bell System Technical Journal ,1965(44):2245～2269.
[22] R.Russell .An Effective Heuristic for the M-tour Traveling Salesman Problem with Some Side Conditions. [J] Operations Research, 1977(25): 517-524.
[23] E.K.Baker and J.R.Schaffer. Solution Improvement Heuristics for the Vehicle Routing and Scheduling Problem with Time Window Constraints. [J] American Journal of Mathematical Management Sciences, 1986(6):261～300.
[24] J.Y.Potvin and J.M Rousseau.An Exchange Heuristic For Routing Problems With Time Windows. [J]Journal of Operational Research Society. 1995(46): 1433-1446.
[25] E.Taillard et al .A Tabu Search Heuristic For The Vehicle Routing Problem With Soft Time Windows. [J] Transportation Science, 1997(31): 170-186.
[26] F.Glover.New Ejection Chain and Alternating Path Methods for Traveling Salesman Problems. [J]Computer Science and Operations Research: New Developments in Their Interfaces.O.R. Balci Sharda, and S. Zenios (eds), Pergamon Press, Oxford .1992: 449-509.
[27] M.Gendreau, A.Hertz and GLaporte. New Insertion And Postoptimization Procedures For The Traveling Salesman Problem. [J] Operations Research, 1992(40):1086～1094.
[28] P.M.Thompson and H.N. Psaraftis. Cyclic Transfer Algorithms for Multivehicle Routing and Scheduling Problems. [J]Operations Research,1993(41): 935-946.
[29] J.Homberger and H.Gehring.Two Evolutionary Metaheuristics For The Vehicle Routing Problem With Time Windows. [J] INFOR1999(37):297～318.
[30] H.Gehring and J. Homberger. A Parallel Hybrid Evolutionary Metaheuristic for the VehicleRouting Problem with Time Windows. [J]Proceedings of EUROGEN99, K.Miettinen, M.Makela and J. Toivanen (eds), University of Jyvaskyla, Finland. 1999,57-64.
[31] M.L. Fisher and R. Jaikumar. A generalized assignment heuristic for the vehicle routing problem".[J] Networks, 1981(11):109～124.
[32] J. Bramel and D. Simchi-Levi. A location based heuristic for general routing problems. [J]Operations Research, 1995(43):649～660.
[33] N. Christofides, A.Mingozzi, and P.Toth. The vehicle routing problem. In: N. Christofides, A.Mingozzi, P.Toth.et al. eds. Combinatorial Optimization, Chichester: Wiley, 1979. 315-338.
[34] N.Christofides. The vehicle routing problem. [J]RAIRO, 1976(10):55～70.
[35] D.M. Ryan, C. Hjorring, and F. Glover. Extensions of the petal method for vehicle routing. [J] Journal of Operational Research Society, 1993(44): 289-296.
[36] M. Balinski and R.Quandt. On an integer program for a delivery problem. [J]Operations Research, 1964(12): 300-304.
[37] B.A. Foster and D.M. Ryan. An integer programming approach to the vehicle scheduling problem. [J]Operations Research, 1976(27): 367-124.
[38] J. Renaud, F.F. Boctor, and G. Laporte. An improved petal heuristic for the vehicle routing problem. [J] Journal of Operational Research Society, 1996(47):329～336.
[39] J.E.Beasley. Route-first cluster-second methods for vehicle routing. [J] Omega, 1983(11):403-408.
[40] H.Gehring and J.Homberger. Parallelization of a Two-Phase Meta-heuristic for Routing Problems with Time Windows. [J] Asia-Pacific Journal of Operational Research 2001(18): 35-47.
[41] M.Haimovich and A.H.GRinnooy Kan. Bounds and heuristics for capacitated routing problems. [J] Mathematics of Operations Research, 1985(10):527～542.
[42] W.Chiang and R.Russell. Simulated Annealing Metaheuristics For The Vehicle Routing Problem With Time Windows. [J] Annals of Operations Research .1996(63):3～27.
[43] K.C.Tan, L.H. Lee and K.Q. Zhu. Heuristic Methods for Vehicle Routing Problem with Time Windows. [J]Proceedings of the 6~(th) International Symposium on Artificial Intelligence &Mathematics, Ft. Lauderdale, Florida.2000.
[44] H.Li, A.Lim, J.Huang. Local Search with Annealing-like Restarts to solve the VRPTW. [J] European Journal of Operational Research 2003,Vol.150,P115.
[45] L.M.Gambardella, E. Taillard and G. Agazzi. MACS-VRPTW: A Multiple Ant Colony System for Vehicle Routing Problems with Time Windows. [J] New Ideas in Optimization,,D. Come, M. Dorigo and F. Glover (eds), McGraw-Hill, London. 1999:63-76.
[46] P.Kilby, P. Prosser and P. Shaw. Guided Local Search for the Problem with Time Windows. [J]META-HEURISTICS Advances and Treads in Local Search Paradigms for Optimization, S.Voss,S.Martello,I.H.Osman and C.Roucatirol(eds), Kluwer Academic Publishers, Boston., 1999, 473-486.
[47] G.Kontoravdis and J.Bard, A GRASP For The Vehicle Routing Problem With Time Windows, [J]Journal on Computing 7,10-23.
[48]O.Braysy,and M.Gendreau,Evolutionary Algorithms for the Vehicle Routing Problem with Time Windows.[J]Working paper,SINTEF Applied Mathematics,Department of Optimization,Norway.2002.
[49]O.Braysy,and,G.Hasle and W.Dullaert.A Fast Local Search Algorithm for the Vehicle Routing Problem with Time Windows.[J]Working paper,SINTEF Applied Mathematics,Department of Optimization,Norway.2002.
[50]http;//web.cba.neu.edu/～msolomon/problems.htm
[51]Leong H W,Liu M.A multi-agent algorithm for vehicle routing problem with time window[J].ACM 2006;106-111.
[52]Alvarenga G B,Mateus G R.A two-phase genetic and set partitioning approach for the vehicle routing problem with time windows[J].Proc 4th International Conference on Hybrid Intelligent Systems,2004;428-433.
[53]Andrew Lim,Fan Wang.A Smoothed Dynamic Tabu Search Embedded GRASP for m-VRPTW.[J]Proceedings of the 16th IEEE International Conference on Tools with Artificial Intelligence(ICTAI2004).
[54]Alvarenga G B,Mateus G R.A two-phase genetic and set partitioning approach for the vehicle routing problem with time windows[J].Proc 4th International Conference on Hybrid Intelligent Systems,2004;428-433.
[55]Oliveira,H.C.B.,Vasconcelos,G.C.,Alvarenga,G.B.Reducing traveled distance in the vehicle routing problem with time windows using a multi-start simulated annealing.[J]2006 International Joint Conference on Neural Networks Sheraton Vancouver Wall Center Hotel,Vancouver,BC,Canada 2006(7);16-21.
[56]李大卫,王莉,王梦光.一个求解带有时间窗口约束的车辆路径问题的启发式算法[J].系统工程,1998,16(4);20-29.
[57]谢秉磊,李军,郭耀煌.有时间窗的非满载车辆调度问题的遗传算法[J].系统工程学报,2000,15(3);290-294。
[58]宋厚冰,蔡远利.有时间窗约束的车辆路径问题的改进遗传算法[J].交通与计算机,2003,21(4);25-27.
[59]刘小兰等.有时间窗的车辆路径问题的近似算法研究[J].计算机集成制造系统,2004,10(7);825-831.
[60]吴璟莉,李陶深.遗传算法与禁忌搜索算法的混合策略在VRPTW问题上的应用[J].计算机工程与应用2004(18);54-57.
[61]王德东,陈术山,郑丕谔.确定车辆数的有时间窗车辆选径问题的混合算法[J].计算机应用,2006 26(2);482-484.
[62]占书芳.并行算法在带软时间窗车辆路径问题中的应用研究.硕士学位论文.武汉;武汉理工大学,2006