车辆路径问题的研究
|
摘要
随着经济全球化和信息化进程的不断加快,物流作为具有广阔前景和增值功能的新兴服务业,正在全球范围内迅速发展,它对于提高国家经济运行质量和效益、优化资源配置、增强企业竞争力和促进企业生产力的发展具有重要意义。运输服务是物流组成中的重要环节,降低运输成本、提高运输质量和效率成为加快物流发展的有效途径。
车辆路径问题是运输服务优化中的核心问题,它通过对货物的运输线路进行优化,在满足客户需求的前提下,尽量以最低的运输成本将货物送达目的地。在过去几十年间,车辆路径问题得到了广泛的关注和研究,并取得了丰富的研究成果。本文首先对这类问题的构成、分类以及求解算法的研究现状等进行了归纳和概括。
最小-最大车辆路径问题,是与一般车辆路径问题目标不同的一类问题,它要求在整个行车线路中,行程最长的线路行驶距离最短。本文根据这类问题的特点,采用遗传算法和禁忌搜索算法进行了求解。并在禁忌搜索算法中,针对最长的线路生成邻域,将该算法用于标准算例的求解,得到了较好的结果。
在实际的线路计划和执行过程中,往往会出现新的客户请求或客户信息的变化,这时要求系统能快速响应这种信息更新,并重新制定线路计划。这类问题称为动态车辆路径问题。对于基本的动态车辆路径问题,本文研究了相应的处理策略,分析了系统的基本组成,将整个动态问题转换为一系列的静态子问题,对子问题采用禁忌搜索算法进行求解。以整个线路的行驶距离作为目标,采用该算法对9个标准算例进行了测试,与文献中其他算法的计算结果相比较,有3个问题得到了最好解,7个问题得到了最好平均解。
由于交通管制和客户营业时间等实际约束,某些客户只能在某些时间段接受车辆为其提供的服务,即客户有时间窗限制,本文在带时间窗的动态车辆路径问题中,分析了三种线路间局部搜索方法:重定位法,节点交换法和2-opt*法,以及两种线路内局部搜索方法:2-opt法和Or-opt法,并将这些方法的不同组合应用于静态子问题初始解的改进。通过对标准算例的求解结果进行分析和比较得出:在线路间进行局部搜索时,重定位法的效果最好,2-opt*法次之,节点交换法的最差;在线路内进行局部搜索时,2-opt法优于Or-opt法。同时,也分析了客户出现时间的早晚,客户地理位置的分布以及不同的客户时间窗范围对结果线路中使用的车辆数量,整个线路的行驶距离和客户延迟时间的影响。
在带时间窗的动态收取和运送问题中,要求从某一客户的收取点提取货物,送到其相应的运送点。因此要求同一客户的收取点和运送点必须由同一台车辆来执行服务,且必须在访问运送点之前先访问提取点。本文在描述该问题特点的基础上,采用了启发式方法对该问题进行求解,并对基本算例进行了测试。
With rapid development of economic globalization and information technology, logistics has become a new value-added service industry with broad prospect. It is significant to improve operation quality and performance of national economic, optimize resource allocation, enhance competitiveness of enterprises and promote development of productivity. Being an important link in logistics, transportation service is an effective way to accelerate the development of logistics by reducing transportation cost, improving transportation quality and raising transportation efficiency.
Vehicle routing problem is a key problem in the optimization of transportation service, it delivery goods to the destination at lowest cost in the premise of satisfying demand of customers. During the past decades, vehicle routing problem has been paid much attention to and many research results have been obtained. The composition and classification of vehicle routing problem are introduced, and the present situation of algorithms is generalized.
The objective of min-max vehicle routing problem is to minimize travelling distance of the longest route among all routes, so it is different with common vehicle routing problem. Genetic algorithm and tabu search are adopted to solve these problems. Neighbors are created with focus on the longest route in tabu search. Tests are performed on standard instances and good results are found.
In the course of practical route planning and performing, new customer requests may arrive or information may change. A quick response must be made to the updated information and routes should be re-planned. This kind of problem is called dynamic vehicle routing problem. Treatment strategies are studied and system composition are analyzed for basic dynamic vehicle routing problem, and then dynamic problem are partitioned into a series of static sub-problems, which is solved by tabu search. Instances are tested with the objective to minimize total travelling distance of all routes. Compared with results obtained by other algorithms in literature, three best solutions and seven best average solutions have been found among nine instances by tabu search.
Due to actual restrictions such as traffic control and customers business hours, some customers accept service by vehicle only at some time intervals, which is called time window limit. Three inter-route local search approaches including relocation, exchange and 2-opt*, and two intra-route local search approaches including 2-opt and or-opt are introduced. Combination of different approaches is adopted to solve static sub-problems. Results of test instances show that relocation is the best, 2-opt* second and exchange the worst for inter-route local search, and 2-opt is better than or-opt for intra-route local search. Effects of arrival time, distribution of geography location and time-window range on vehicle number, traveling distance and delay of all routes are also analyzed.
In dynamic pickup and delivery problem with time window, the vehicle should pick up goods at pickup location and then transport the goods to the delivery location, so the pickup location of a customer must be visited before its delivery location by the same vehicle. Characteristics are described and heuristics are introduced to solve this problem. Finally basic instances are used for tests.
车辆路径问题是运输服务优化中的核心问题,它通过对货物的运输线路进行优化,在满足客户需求的前提下,尽量以最低的运输成本将货物送达目的地。在过去几十年间,车辆路径问题得到了广泛的关注和研究,并取得了丰富的研究成果。本文首先对这类问题的构成、分类以及求解算法的研究现状等进行了归纳和概括。
最小-最大车辆路径问题,是与一般车辆路径问题目标不同的一类问题,它要求在整个行车线路中,行程最长的线路行驶距离最短。本文根据这类问题的特点,采用遗传算法和禁忌搜索算法进行了求解。并在禁忌搜索算法中,针对最长的线路生成邻域,将该算法用于标准算例的求解,得到了较好的结果。
在实际的线路计划和执行过程中,往往会出现新的客户请求或客户信息的变化,这时要求系统能快速响应这种信息更新,并重新制定线路计划。这类问题称为动态车辆路径问题。对于基本的动态车辆路径问题,本文研究了相应的处理策略,分析了系统的基本组成,将整个动态问题转换为一系列的静态子问题,对子问题采用禁忌搜索算法进行求解。以整个线路的行驶距离作为目标,采用该算法对9个标准算例进行了测试,与文献中其他算法的计算结果相比较,有3个问题得到了最好解,7个问题得到了最好平均解。
由于交通管制和客户营业时间等实际约束,某些客户只能在某些时间段接受车辆为其提供的服务,即客户有时间窗限制,本文在带时间窗的动态车辆路径问题中,分析了三种线路间局部搜索方法:重定位法,节点交换法和2-opt*法,以及两种线路内局部搜索方法:2-opt法和Or-opt法,并将这些方法的不同组合应用于静态子问题初始解的改进。通过对标准算例的求解结果进行分析和比较得出:在线路间进行局部搜索时,重定位法的效果最好,2-opt*法次之,节点交换法的最差;在线路内进行局部搜索时,2-opt法优于Or-opt法。同时,也分析了客户出现时间的早晚,客户地理位置的分布以及不同的客户时间窗范围对结果线路中使用的车辆数量,整个线路的行驶距离和客户延迟时间的影响。
在带时间窗的动态收取和运送问题中,要求从某一客户的收取点提取货物,送到其相应的运送点。因此要求同一客户的收取点和运送点必须由同一台车辆来执行服务,且必须在访问运送点之前先访问提取点。本文在描述该问题特点的基础上,采用了启发式方法对该问题进行求解,并对基本算例进行了测试。
With rapid development of economic globalization and information technology, logistics has become a new value-added service industry with broad prospect. It is significant to improve operation quality and performance of national economic, optimize resource allocation, enhance competitiveness of enterprises and promote development of productivity. Being an important link in logistics, transportation service is an effective way to accelerate the development of logistics by reducing transportation cost, improving transportation quality and raising transportation efficiency.
Vehicle routing problem is a key problem in the optimization of transportation service, it delivery goods to the destination at lowest cost in the premise of satisfying demand of customers. During the past decades, vehicle routing problem has been paid much attention to and many research results have been obtained. The composition and classification of vehicle routing problem are introduced, and the present situation of algorithms is generalized.
The objective of min-max vehicle routing problem is to minimize travelling distance of the longest route among all routes, so it is different with common vehicle routing problem. Genetic algorithm and tabu search are adopted to solve these problems. Neighbors are created with focus on the longest route in tabu search. Tests are performed on standard instances and good results are found.
In the course of practical route planning and performing, new customer requests may arrive or information may change. A quick response must be made to the updated information and routes should be re-planned. This kind of problem is called dynamic vehicle routing problem. Treatment strategies are studied and system composition are analyzed for basic dynamic vehicle routing problem, and then dynamic problem are partitioned into a series of static sub-problems, which is solved by tabu search. Instances are tested with the objective to minimize total travelling distance of all routes. Compared with results obtained by other algorithms in literature, three best solutions and seven best average solutions have been found among nine instances by tabu search.
Due to actual restrictions such as traffic control and customers business hours, some customers accept service by vehicle only at some time intervals, which is called time window limit. Three inter-route local search approaches including relocation, exchange and 2-opt*, and two intra-route local search approaches including 2-opt and or-opt are introduced. Combination of different approaches is adopted to solve static sub-problems. Results of test instances show that relocation is the best, 2-opt* second and exchange the worst for inter-route local search, and 2-opt is better than or-opt for intra-route local search. Effects of arrival time, distribution of geography location and time-window range on vehicle number, traveling distance and delay of all routes are also analyzed.
In dynamic pickup and delivery problem with time window, the vehicle should pick up goods at pickup location and then transport the goods to the delivery location, so the pickup location of a customer must be visited before its delivery location by the same vehicle. Characteristics are described and heuristics are introduced to solve this problem. Finally basic instances are used for tests.
引文
[1]李军,郭耀煌.物流配送车辆优化调度理论与方法.北京:中国物资出版社, 2001
[2] Bodin L.D., Golden B. L. Routing and scheduling of vehicles and crews: the state of art. Computers & Operations Research, 1983, 10(2): 63-211
[3] http://www.chinawuliu.com.cn/bake/uploadFace/2006tj.htm
[4] Dantzig G., Ramser J. The truck dispatching problem. Management Science, 1959, (6): 80-91
[5] Golden B. L., Laporte G., Taillard E. D. An adaptive memory heuristic for a class of vehicle routing problems with minmax objective. Computers & Operations Research, 1997, 24(5): 445-452
[6] Clarke G., Wright J. W. Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, 1964,12: 568-581
[7] Laporte G., Mercure H., Nobert Y. An exact algorithm for the asymmetrical capacitated vehicle routing problem. Networks, 1986,16:33-46
[8] Christofides N., Mingozzi A., Toth P. Exact algorithms for the vehicle routing problem based on spanning the shortest path relaxation. Mathematical Programming, 1981, 20: 255-282
[9] Fisher M. L. Optimal solution of vehicle routing problems using minimum k-trees. Operations Research, 1994, 42(4): 626-642
[10] Eilon S., Watson-Gandy C.D.T. Christofides N. Distribution management: mathematical modeling and practical analysis. London: Griffin, 1971
[11] Kolen A. W. J., Kaan A.H.G. R., Trienekens H.W.J.M. Vehicle routing with time windows. Operations Research, 1987, 35(2): 266-273
[12] Balinski M., Quandt R.On an integer program for a delivery problem. Operations Research, 1962, 12: 300-304
[13] Rao M. R., Ziont S. Allocation of transportation units to alternative trips-A column generation scheme with out-of-kilter subproblems. Operations Research, 1968, 12: 52-63
[14] Fisher M. L., Jaikumar R. A generalized assignment heuristic for vehicle routing. Networks, 1981, 11: 109-124
[15] Laporte G., Nobert Y., Desrocher M. Optimal routing under capacity and distance restritions. Operations Research, 1985, 33: 1050-1073
[16] Desrochers M., Verhoog T. W. A matching based savings algorithm for the vehicle routing problem. Technical Report: Les Cahiers du GERAD G-89-04, Ecole des Hautes Etudes Commerciales de Montreal, Canada, 1989
[17] Altinkemer K., Cavish B. Parallel savings based heuristic for the delivery problem. Operations Research, 1991, 39: 456-469
[18] Wark P., Holt J. A repeated matching heuristic for the vehicle routing problem. Operations Research Society, 1994, 45 (10): 1156-1167
[19] Mole R.H., Jameson S. R. A sequential route-building algorithm employing a generalized savings criterion. Operational Research, 1976, 27: 503-511
[20] Gillett B., Miller L. A heuristic algorithm for the vehicle dispatch problem. Operations Research, 1974, 22: 340-349
[21] Fisher M. L., Jaikumer R. A generalized assignment heuristic for vehicle routing. Networks, 1981, 11: 109-124
[22] Beasley J. E. Route first-cluster second methods for vehicle routing. Omega, 1983, 11(4): 403-408
[23] Arbelaitz O., Rodríguez C., Zamakola I. Low cost parallel solutions for the VRPTW optimization problem. In: Proceedings of 30th International Workshops on Parallel Processing, Spain, 2001: 176-181
[24] Czech Z. J., Czarnas P. Parallel simulated annealing for the vehicle routing problem with time windows. In: Proceedings of 10th Euromicro Workshop on Parallel, Distributed and Network- based Processing, Spain, 2002 (1): 376 -383
[25] Berger J., Barkaoui M., A new hybrid genetic algorithm for the capacitated vehicle routing problem. Journal of the Operational Research Society, 2003, 54 (12): 1254-1262
[26] Tong Z., Li N., Sun D. B. Genetic algorithm for vehicle routing problem with time window with uncertain vehicle number, In: Proceedings of the 5’World Congress onIntelligent Control and Automation, 2004: 15-19
[27] Barbarosoglu G., Ozgur D. A tabu search algorithm for the vehicle routing problem. Computers & Operations Research, 1999, 26: 255-270
[28] Cordeau J-F, Laporte G. Tabu search heuristics for the vehicle routing problem. Technical Report G-2002-15, Group for Research in Decision Analysis (GERAD), Montreal, 2002
[29] Laporte G., Gendreau M., Potvin J-Y, Semet F. Classical and modern heuristics for the vehicle routing problem. International Transaction in Operational Research, 2000, 7: 285-300
[30] Wassan N. A. A reactive tabu search for the vehicle routing problem. Operational Research Society, 2006, 57(1): 111-116
[31] Bell J. E., Mcmullen P. R. Ant colony optimization techniques for the vehicle routing problem. Advanced Engineering Informatics, 2004, 18(1): 41-48
[32] Mazzeo S., Loiseau I. An ant colony algorithm for the capacitated vehicle routing. Electronic Notes in Discrete Mathematics, 2004, 18:181-186
[33] Vakhutinsky A. I., Golden B. L. Solving vehicle routing problems using elastic nets. In: Proceedings of the IEEE Worm Congress on Computational Intelligence, 1994: 4535-4540
[34] Yoshiike N., Takefuji Y. Vehicle Routing Problem Using Clustering Algorithm by Maximum Neural Networks. In: Proceedings of the Second International Conference on Intelligent Processing and Manufacturing of Materials, 1999: 1109 -1113
[35] Gendreau M., Hertza A., Laporte G., A tabu search heuristic for the vehicle routing problem. Management Science, 1994, 40(10): 1276-1289.
[36] Taillard E. Parallel interative search method for vehicle routing problems. Networks, 1993, 23: 661-673
[37] Lawrence S., Mohammad A. Parametric experimentation with a genetic algorithmic configuration for solving the vehicle routing problem. In: Proceedings of Annual Meeting of the Decision Sciences Institute, 1996: 488-490
[38] Nicolas B., Pascal B. Optimization by hybridization of a genetic algorithm withconstraint satisfaction techniques. In: Proceedings of the IEEE Conference on Evolutionary Computation, 1998
[39]张涛,王梦光.遗传算法和3-OPT结合求解带能力约束的VRP.东北大学学报.1999, 20(3): 253-256
[40]邹彤,李宁,孙德宝.不确定车辆数的有时间窗车辆路径问题的遗传算法,系统工程理论与实践, 2004, 24 (6): 134-138
[41] Serna C. R. D., Joaquin P. B., Stefan V. Minmax vehicle routing problems: application to school transport in the province of Burgos. In: Proceedings of International conference on computer-aided scheduling of public transport, 2000
[42] Applegate D., Cook W., Dash S. Solution of a min-max vehicle routing problem. Informs Journal on Computing, 2002, 14(2): 132-143
[43] Arkin E. M., Hassin R., Levin A. Approximations for minimum and min-max vehicle routing problems. Algorithms archive, 2006, 59(1): 1-18
[44] Bell W., Dalberto L. M., Fisher M. L. et al. Improving the distribution of industrial gases with an online computerized routing optimizer. Interfaces, 1983, 13: 4-23
[45] Psaraftis H. N. A dynamic programming solution the single vehicle many-to-many Immediate request dial-a-ride problem. Transportation Science, 1980, 14: 130-154
[46] Larsen A. The Dynamic Vehicle Routing Problem, PHD thesis, 2001
[47] Gendreau M., Guertin F., Potvin J.Y. et al. Tabu search for real-time vehicle routing and dispatching. Technical Report CRT-96-47, 1996
[48] Kilby P., Prosser P., Shaw P. Dynamic VRPs: a study of scenarios. Report APES-06-1998, 1998
[49] Ichoua S., Gendreau M., Potvin J. Y. Diversion issues in real-time vehicle dispatching. Transportation Science, 2000, 34: 426-435
[50] Bianchi L. Notes on Dynamic Vehicle Routing. Technical Report IDSIA-05-01, 2000
[51] Rhalibi A. E. I., Kelleher G. An approach to dynamic vehicle routing, rescheduling and disruption metrics. In: Proceeding of IEEE International Conference on Systems, Man and Cybernetics, 2003, 4: 3613-3618
[52] Montemanni R., Gambardella L. M., Rizzoli A. E. Ant colony system for a dynamicvehicle routing problem. Combinatorial Optimization, 2005, 10: 327–343
[53] Chitty D. M., Hernandez M. L. A hybrid ant. colony optimization technique for dynamic vehicle routing. In: Proceedings of 2004 Genetic and Evolutionary Computation. Conference, 2004: 48-59
[54] Timon C. D., Eldon Y. L., Defrose C. Dynamic vehicle problem for online B2C delivery. The International Journal of Management Science, 2005(33): 33-45
[55] Guilherme B. A., Ricardo M., Geraldo R. M. A hybrid approach for the dynamic routing problem with time windows. In: Proceedings of the Fifth International Conference on Hybrid Intelligent Systems, 2005
[56] Song J. Y., Hu J. M., Tian Y. et al. Re-optimization in dynamic vehicle routing problem based on wasp-like agent strategy. In: Proceedings of the 8th International IEEE on Hybrid Intelligent Transportation Systems, 2005: 688-693
[57] Jih W. R., Jsu J.Y., Dynamic vehicle routing using hybrid genetic algorithms. In: Proceedings of the 1999 IEEE International Conference on Robotics & Automation, 1999: 453-458
[58] 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
[59] Snezana M. M., Ramesh K., Gilbert L. Double-horizon based heuristics for the dynamic pickup and delivery with time windows. Transportation Research Part B, 2004(38): 669-685.
[60]郭耀煌,钟小鹏.动态车辆路径问题排队模型分析.管理科学学报, 2006, 1(9): 33-37
[61]谢秉磊,郭耀煌,郭强.动态车辆路径问题:现状与展望.系统工程理论方法应用,2002, 2(11): 116-120
[62]郭耀煌,谢秉磊.一类随机动态车辆路径问题的策略分析.管理工程学报, 2003, 4(17): 114-115.
[63]肖增敏,李军.动态网络车辆路径问题:研究现状及展望.系统工程, 2004, 7(22): 68-71
[64]祝崇隽,刘民,吴澄.供应链中车辆路径问题的研究进展及前景.计算机集成制造系统, 2001, 11(7): 1-6
[65] Bertsmas D. J., Simchi-Levid D. A new generation of vehicle routing research: robust algorithms, addressing uncertainty. Operations Research, 1996, 44(2): 286-304
[66] Bertsimas D. J. A vehicle routing problem with stochastic demand. Operations Research, 1992, 40(3): 574-585
[67] Gendreau M., Laporte G. A tabu search heuristic for the vehicle routing problem with stochastic demands and customers. Operations Research, 1996, 44(3): 469-477
[68] Laporte G., Louveaux F., Mercure H. Models and exact solutions for a class of stochastic location routing problems. European Journal of Operational Research, 1989, 39: 71-78
[69] Stewart W. R., Golden B. L. Stochastic vehicle routing: a comprehensive approach. European Journal of Operational Research, 1983,14:371-385
[70] Dror M., Trudeau P. Stochastic vehicle routing with modified savings algorithm. European Journal of Operational Research, 1986, 23: 228-235
[71] Secomandi N. Reoptimization approaches for the vehicle routing problem with stochastic demand. TEPPER-CART-05-107, 2005
[72] Bertsimas D. Probabilistic combinatorial optimization problems. PHD thesis: Massachusetts Institute of Technology, 1988
[73] Waters C. Vehicle scheduling problems with uncertainty and omitted customers. Operational Research Society, 1989, 40(5): 1099-1108
[74] Gendreau M., Laporte G., Seguin R. Stochastic vehicle routing. European Journal of Operational Research, 1996, 88(1): 3-12
[75] Bertsimas D., Jaillet P., Odoni A. A priori optimization. Operations Research, 1990, 38(6): 1019-1033
[76] Jezequel A. Probabilistic vehicle routing problems. PHD thesis: Cambridge, 1985
[77] Jaillet P., Odoni A. The probabilistic vehicle routing problem: vehicle routing methods and studies. Amsterdam: NorthHolland, 1988
[78] Gendreau M., Laporte G., Seguin R. An exact algorithm for the vehicle routing problem with stochastic customers and demands. Transportation Science, 1995, 29(2): 143-155
[79] Surajit K. D. Developing state-dependent routes for the vehicle routing problem under uncertainty, 2004
[80]谢秉磊.随机车辆路径问题研究.博士学位论文:西南交通大学,2003
[81] Malandraki C., Daskin M.S. Time dependent vehicle routing problems: formulations, properties and heuristic algorithms. Transportation Science, 1992, 26(3)
[82] Malandraki C., Dial R. B. A restricted dynamic programming heuristic algorithm for the time dependent traveling salesman problem. European Journal of Operational Research, 1996, 90: 45-55
[83] Ahn B. H., Shin J. Y. Vehicle routing with time windows and time-varying congestion. Operational Research Society, 1991, 42(5): 393-400
[84] Ichoua S., Gendreau M., Potvin J.Y. Vehicle dispatching with time-dependent travel times. Operational Research, 2003, 144(2): 379-396.
[85] Donati A. V., Montemanni R., Casagrande N. et al. Time dependent vehicle routing problem with an ant colony system, Switzerland, IDSIA-02-03, 2003
[86] Donati A. V., Montemanni R., Casagrande N. et al. Time dependent vehicle routing problem with an multi ant colony system. IDSIA, 2003
[87] Donati A. V., et al. Integeration of a robust shortest path algorithm with a time dependent vehicle routing model and applications. In: Proceedings of 2003 International Symposium on Computational Intelligence for Measurement Systems and Application, Switzerland, 2003
[88] Jung S. A genetic algorithm for vehicle routing problem with time dependent travel times. PHD thesis: University of Maryland, 2000
[89] Potvin J. Y., Xu Y., Benyahia I. Vehicle routing and scheduling with dynamic travel times. Computers & Operations Research, 2006, 33: 1129-1137
[90] Zeimpekis V., Giaglis G.. M., Minis I. A dynamic real-time fleet management system for incident handling in city logistics. In: Proceedings of the 61st IEEE Vehicular Technology Conference, Sweden, 2005
[91] Taniguchi E., Shimamoto H. Intelligent transportation system based dynamic vehicle routing and scheduling with variable travel times. Transportation Research, 2004, 12: 235-250
[92]符卓,开放式车辆路径问题及其应用研究,博士学位论文:中南大学, 2003
[93]丁源,李引珍.带有能力约束的VRP的一种遗传算法.兰州交通大学学报, 2005, 24(6): 123-126
[94]吕树红,姚丹霖,何文强等.车辆路径问题的一种遗传算法求解方法.计算机应用, 2005, 25: 134-135
[95]吴兴华,田森平.确定车辆数的有时间窗车辆路径问题的遗传算法.交通与计算机, 2006, 24(3): 96-98
[96]范军涛,谢红兵,陈恩鹏.车辆路径问题的改进遗传算法.哈尔滨理工大学学报, 2004, 9(5): 118-120
[97]张丽萍,柴跃廷,曹瑞.有时间窗车辆路径问题的改进遗传算法.计算机集成制造系统, 2002, 8(6): 451-454
[98]王凌.智能优化算法及应用.北京:清华大学出版社, 2001
[99]元霞.物流配送中车辆路径优化问题的研究,博士学位论文:东南大学,2004
[100] Chichestofides N., Mingozzi A., Toth P. Combinatorial Optimization. Chichester: Wiley, 1979
[101] Ghiani G., Guerriero F., Laporte G. et al. Real-time vehicle routing: solution concepts, algorithms and parallel computing strategies. European Journal of Operational Research, 2003, 151(1): 1-11
[102] Braeysy O., Gendreau M. Vehicle routing problem with time windows, part i: route construction and local search algorithms. Transportation Science, 2005, 39: 104-118
[2] Bodin L.D., Golden B. L. Routing and scheduling of vehicles and crews: the state of art. Computers & Operations Research, 1983, 10(2): 63-211
[3] http://www.chinawuliu.com.cn/bake/uploadFace/2006tj.htm
[4] Dantzig G., Ramser J. The truck dispatching problem. Management Science, 1959, (6): 80-91
[5] Golden B. L., Laporte G., Taillard E. D. An adaptive memory heuristic for a class of vehicle routing problems with minmax objective. Computers & Operations Research, 1997, 24(5): 445-452
[6] Clarke G., Wright J. W. Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, 1964,12: 568-581
[7] Laporte G., Mercure H., Nobert Y. An exact algorithm for the asymmetrical capacitated vehicle routing problem. Networks, 1986,16:33-46
[8] Christofides N., Mingozzi A., Toth P. Exact algorithms for the vehicle routing problem based on spanning the shortest path relaxation. Mathematical Programming, 1981, 20: 255-282
[9] Fisher M. L. Optimal solution of vehicle routing problems using minimum k-trees. Operations Research, 1994, 42(4): 626-642
[10] Eilon S., Watson-Gandy C.D.T. Christofides N. Distribution management: mathematical modeling and practical analysis. London: Griffin, 1971
[11] Kolen A. W. J., Kaan A.H.G. R., Trienekens H.W.J.M. Vehicle routing with time windows. Operations Research, 1987, 35(2): 266-273
[12] Balinski M., Quandt R.On an integer program for a delivery problem. Operations Research, 1962, 12: 300-304
[13] Rao M. R., Ziont S. Allocation of transportation units to alternative trips-A column generation scheme with out-of-kilter subproblems. Operations Research, 1968, 12: 52-63
[14] Fisher M. L., Jaikumar R. A generalized assignment heuristic for vehicle routing. Networks, 1981, 11: 109-124
[15] Laporte G., Nobert Y., Desrocher M. Optimal routing under capacity and distance restritions. Operations Research, 1985, 33: 1050-1073
[16] Desrochers M., Verhoog T. W. A matching based savings algorithm for the vehicle routing problem. Technical Report: Les Cahiers du GERAD G-89-04, Ecole des Hautes Etudes Commerciales de Montreal, Canada, 1989
[17] Altinkemer K., Cavish B. Parallel savings based heuristic for the delivery problem. Operations Research, 1991, 39: 456-469
[18] Wark P., Holt J. A repeated matching heuristic for the vehicle routing problem. Operations Research Society, 1994, 45 (10): 1156-1167
[19] Mole R.H., Jameson S. R. A sequential route-building algorithm employing a generalized savings criterion. Operational Research, 1976, 27: 503-511
[20] Gillett B., Miller L. A heuristic algorithm for the vehicle dispatch problem. Operations Research, 1974, 22: 340-349
[21] Fisher M. L., Jaikumer R. A generalized assignment heuristic for vehicle routing. Networks, 1981, 11: 109-124
[22] Beasley J. E. Route first-cluster second methods for vehicle routing. Omega, 1983, 11(4): 403-408
[23] Arbelaitz O., Rodríguez C., Zamakola I. Low cost parallel solutions for the VRPTW optimization problem. In: Proceedings of 30th International Workshops on Parallel Processing, Spain, 2001: 176-181
[24] Czech Z. J., Czarnas P. Parallel simulated annealing for the vehicle routing problem with time windows. In: Proceedings of 10th Euromicro Workshop on Parallel, Distributed and Network- based Processing, Spain, 2002 (1): 376 -383
[25] Berger J., Barkaoui M., A new hybrid genetic algorithm for the capacitated vehicle routing problem. Journal of the Operational Research Society, 2003, 54 (12): 1254-1262
[26] Tong Z., Li N., Sun D. B. Genetic algorithm for vehicle routing problem with time window with uncertain vehicle number, In: Proceedings of the 5’World Congress onIntelligent Control and Automation, 2004: 15-19
[27] Barbarosoglu G., Ozgur D. A tabu search algorithm for the vehicle routing problem. Computers & Operations Research, 1999, 26: 255-270
[28] Cordeau J-F, Laporte G. Tabu search heuristics for the vehicle routing problem. Technical Report G-2002-15, Group for Research in Decision Analysis (GERAD), Montreal, 2002
[29] Laporte G., Gendreau M., Potvin J-Y, Semet F. Classical and modern heuristics for the vehicle routing problem. International Transaction in Operational Research, 2000, 7: 285-300
[30] Wassan N. A. A reactive tabu search for the vehicle routing problem. Operational Research Society, 2006, 57(1): 111-116
[31] Bell J. E., Mcmullen P. R. Ant colony optimization techniques for the vehicle routing problem. Advanced Engineering Informatics, 2004, 18(1): 41-48
[32] Mazzeo S., Loiseau I. An ant colony algorithm for the capacitated vehicle routing. Electronic Notes in Discrete Mathematics, 2004, 18:181-186
[33] Vakhutinsky A. I., Golden B. L. Solving vehicle routing problems using elastic nets. In: Proceedings of the IEEE Worm Congress on Computational Intelligence, 1994: 4535-4540
[34] Yoshiike N., Takefuji Y. Vehicle Routing Problem Using Clustering Algorithm by Maximum Neural Networks. In: Proceedings of the Second International Conference on Intelligent Processing and Manufacturing of Materials, 1999: 1109 -1113
[35] Gendreau M., Hertza A., Laporte G., A tabu search heuristic for the vehicle routing problem. Management Science, 1994, 40(10): 1276-1289.
[36] Taillard E. Parallel interative search method for vehicle routing problems. Networks, 1993, 23: 661-673
[37] Lawrence S., Mohammad A. Parametric experimentation with a genetic algorithmic configuration for solving the vehicle routing problem. In: Proceedings of Annual Meeting of the Decision Sciences Institute, 1996: 488-490
[38] Nicolas B., Pascal B. Optimization by hybridization of a genetic algorithm withconstraint satisfaction techniques. In: Proceedings of the IEEE Conference on Evolutionary Computation, 1998
[39]张涛,王梦光.遗传算法和3-OPT结合求解带能力约束的VRP.东北大学学报.1999, 20(3): 253-256
[40]邹彤,李宁,孙德宝.不确定车辆数的有时间窗车辆路径问题的遗传算法,系统工程理论与实践, 2004, 24 (6): 134-138
[41] Serna C. R. D., Joaquin P. B., Stefan V. Minmax vehicle routing problems: application to school transport in the province of Burgos. In: Proceedings of International conference on computer-aided scheduling of public transport, 2000
[42] Applegate D., Cook W., Dash S. Solution of a min-max vehicle routing problem. Informs Journal on Computing, 2002, 14(2): 132-143
[43] Arkin E. M., Hassin R., Levin A. Approximations for minimum and min-max vehicle routing problems. Algorithms archive, 2006, 59(1): 1-18
[44] Bell W., Dalberto L. M., Fisher M. L. et al. Improving the distribution of industrial gases with an online computerized routing optimizer. Interfaces, 1983, 13: 4-23
[45] Psaraftis H. N. A dynamic programming solution the single vehicle many-to-many Immediate request dial-a-ride problem. Transportation Science, 1980, 14: 130-154
[46] Larsen A. The Dynamic Vehicle Routing Problem, PHD thesis, 2001
[47] Gendreau M., Guertin F., Potvin J.Y. et al. Tabu search for real-time vehicle routing and dispatching. Technical Report CRT-96-47, 1996
[48] Kilby P., Prosser P., Shaw P. Dynamic VRPs: a study of scenarios. Report APES-06-1998, 1998
[49] Ichoua S., Gendreau M., Potvin J. Y. Diversion issues in real-time vehicle dispatching. Transportation Science, 2000, 34: 426-435
[50] Bianchi L. Notes on Dynamic Vehicle Routing. Technical Report IDSIA-05-01, 2000
[51] Rhalibi A. E. I., Kelleher G. An approach to dynamic vehicle routing, rescheduling and disruption metrics. In: Proceeding of IEEE International Conference on Systems, Man and Cybernetics, 2003, 4: 3613-3618
[52] Montemanni R., Gambardella L. M., Rizzoli A. E. Ant colony system for a dynamicvehicle routing problem. Combinatorial Optimization, 2005, 10: 327–343
[53] Chitty D. M., Hernandez M. L. A hybrid ant. colony optimization technique for dynamic vehicle routing. In: Proceedings of 2004 Genetic and Evolutionary Computation. Conference, 2004: 48-59
[54] Timon C. D., Eldon Y. L., Defrose C. Dynamic vehicle problem for online B2C delivery. The International Journal of Management Science, 2005(33): 33-45
[55] Guilherme B. A., Ricardo M., Geraldo R. M. A hybrid approach for the dynamic routing problem with time windows. In: Proceedings of the Fifth International Conference on Hybrid Intelligent Systems, 2005
[56] Song J. Y., Hu J. M., Tian Y. et al. Re-optimization in dynamic vehicle routing problem based on wasp-like agent strategy. In: Proceedings of the 8th International IEEE on Hybrid Intelligent Transportation Systems, 2005: 688-693
[57] Jih W. R., Jsu J.Y., Dynamic vehicle routing using hybrid genetic algorithms. In: Proceedings of the 1999 IEEE International Conference on Robotics & Automation, 1999: 453-458
[58] 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
[59] Snezana M. M., Ramesh K., Gilbert L. Double-horizon based heuristics for the dynamic pickup and delivery with time windows. Transportation Research Part B, 2004(38): 669-685.
[60]郭耀煌,钟小鹏.动态车辆路径问题排队模型分析.管理科学学报, 2006, 1(9): 33-37
[61]谢秉磊,郭耀煌,郭强.动态车辆路径问题:现状与展望.系统工程理论方法应用,2002, 2(11): 116-120
[62]郭耀煌,谢秉磊.一类随机动态车辆路径问题的策略分析.管理工程学报, 2003, 4(17): 114-115.
[63]肖增敏,李军.动态网络车辆路径问题:研究现状及展望.系统工程, 2004, 7(22): 68-71
[64]祝崇隽,刘民,吴澄.供应链中车辆路径问题的研究进展及前景.计算机集成制造系统, 2001, 11(7): 1-6
[65] Bertsmas D. J., Simchi-Levid D. A new generation of vehicle routing research: robust algorithms, addressing uncertainty. Operations Research, 1996, 44(2): 286-304
[66] Bertsimas D. J. A vehicle routing problem with stochastic demand. Operations Research, 1992, 40(3): 574-585
[67] Gendreau M., Laporte G. A tabu search heuristic for the vehicle routing problem with stochastic demands and customers. Operations Research, 1996, 44(3): 469-477
[68] Laporte G., Louveaux F., Mercure H. Models and exact solutions for a class of stochastic location routing problems. European Journal of Operational Research, 1989, 39: 71-78
[69] Stewart W. R., Golden B. L. Stochastic vehicle routing: a comprehensive approach. European Journal of Operational Research, 1983,14:371-385
[70] Dror M., Trudeau P. Stochastic vehicle routing with modified savings algorithm. European Journal of Operational Research, 1986, 23: 228-235
[71] Secomandi N. Reoptimization approaches for the vehicle routing problem with stochastic demand. TEPPER-CART-05-107, 2005
[72] Bertsimas D. Probabilistic combinatorial optimization problems. PHD thesis: Massachusetts Institute of Technology, 1988
[73] Waters C. Vehicle scheduling problems with uncertainty and omitted customers. Operational Research Society, 1989, 40(5): 1099-1108
[74] Gendreau M., Laporte G., Seguin R. Stochastic vehicle routing. European Journal of Operational Research, 1996, 88(1): 3-12
[75] Bertsimas D., Jaillet P., Odoni A. A priori optimization. Operations Research, 1990, 38(6): 1019-1033
[76] Jezequel A. Probabilistic vehicle routing problems. PHD thesis: Cambridge, 1985
[77] Jaillet P., Odoni A. The probabilistic vehicle routing problem: vehicle routing methods and studies. Amsterdam: NorthHolland, 1988
[78] Gendreau M., Laporte G., Seguin R. An exact algorithm for the vehicle routing problem with stochastic customers and demands. Transportation Science, 1995, 29(2): 143-155
[79] Surajit K. D. Developing state-dependent routes for the vehicle routing problem under uncertainty, 2004
[80]谢秉磊.随机车辆路径问题研究.博士学位论文:西南交通大学,2003
[81] Malandraki C., Daskin M.S. Time dependent vehicle routing problems: formulations, properties and heuristic algorithms. Transportation Science, 1992, 26(3)
[82] Malandraki C., Dial R. B. A restricted dynamic programming heuristic algorithm for the time dependent traveling salesman problem. European Journal of Operational Research, 1996, 90: 45-55
[83] Ahn B. H., Shin J. Y. Vehicle routing with time windows and time-varying congestion. Operational Research Society, 1991, 42(5): 393-400
[84] Ichoua S., Gendreau M., Potvin J.Y. Vehicle dispatching with time-dependent travel times. Operational Research, 2003, 144(2): 379-396.
[85] Donati A. V., Montemanni R., Casagrande N. et al. Time dependent vehicle routing problem with an ant colony system, Switzerland, IDSIA-02-03, 2003
[86] Donati A. V., Montemanni R., Casagrande N. et al. Time dependent vehicle routing problem with an multi ant colony system. IDSIA, 2003
[87] Donati A. V., et al. Integeration of a robust shortest path algorithm with a time dependent vehicle routing model and applications. In: Proceedings of 2003 International Symposium on Computational Intelligence for Measurement Systems and Application, Switzerland, 2003
[88] Jung S. A genetic algorithm for vehicle routing problem with time dependent travel times. PHD thesis: University of Maryland, 2000
[89] Potvin J. Y., Xu Y., Benyahia I. Vehicle routing and scheduling with dynamic travel times. Computers & Operations Research, 2006, 33: 1129-1137
[90] Zeimpekis V., Giaglis G.. M., Minis I. A dynamic real-time fleet management system for incident handling in city logistics. In: Proceedings of the 61st IEEE Vehicular Technology Conference, Sweden, 2005
[91] Taniguchi E., Shimamoto H. Intelligent transportation system based dynamic vehicle routing and scheduling with variable travel times. Transportation Research, 2004, 12: 235-250
[92]符卓,开放式车辆路径问题及其应用研究,博士学位论文:中南大学, 2003
[93]丁源,李引珍.带有能力约束的VRP的一种遗传算法.兰州交通大学学报, 2005, 24(6): 123-126
[94]吕树红,姚丹霖,何文强等.车辆路径问题的一种遗传算法求解方法.计算机应用, 2005, 25: 134-135
[95]吴兴华,田森平.确定车辆数的有时间窗车辆路径问题的遗传算法.交通与计算机, 2006, 24(3): 96-98
[96]范军涛,谢红兵,陈恩鹏.车辆路径问题的改进遗传算法.哈尔滨理工大学学报, 2004, 9(5): 118-120
[97]张丽萍,柴跃廷,曹瑞.有时间窗车辆路径问题的改进遗传算法.计算机集成制造系统, 2002, 8(6): 451-454
[98]王凌.智能优化算法及应用.北京:清华大学出版社, 2001
[99]元霞.物流配送中车辆路径优化问题的研究,博士学位论文:东南大学,2004
[100] Chichestofides N., Mingozzi A., Toth P. Combinatorial Optimization. Chichester: Wiley, 1979
[101] Ghiani G., Guerriero F., Laporte G. et al. Real-time vehicle routing: solution concepts, algorithms and parallel computing strategies. European Journal of Operational Research, 2003, 151(1): 1-11
[102] Braeysy O., Gendreau M. Vehicle routing problem with time windows, part i: route construction and local search algorithms. Transportation Science, 2005, 39: 104-118