时变网络环境下车辆调度问题研究
|
摘要
我国十一五规划中将现代物流业作为今后重点发展领域,提出到2010年全社会物流成本下降2-3个百分点。运输配送是影响物流总成本的重要因素,大约占物流成本的60%。作为物流系统优化中关键的一环,物流配送车辆的优化调度问题成为研究的热点。在以往的静态车辆调度问题(vehicle routing problem,简写VRP)研究中,车辆路径安排大部分都是基于确定性的信息,其中包括需求确定、车辆位置确定和车辆在路途的行驶时间确定,尤其考虑车辆在任意两节点(顾客或车场)间的运行成本(时间)只取决于节点间的距离,通常被认为是已知且静态的常量。但在实际的车辆行驶过程中,由于交通管理、交通流量、交通事故、天气变化、上下班高峰期等因素的影响,车辆的行驶速度总是处在不断变化之中,从而导致了路网中各个路段上的运行成本(时间)也相应地发生变化。这种动态变化的情况,静态VRP问题的理论和方法已无法适用,这就使得对时变网络VRP问题的研究成为迫切需要。本论文主要以时变网络VRP的三类子问题作为研究对象,分别是基于时段的时间依赖型旅行商问题(time dependenttraveling salesman problem,简写TDTSP)、基于具体位置的TDTSP问题和时间依赖型车辆调度问题(time dependent vehicle routing problem,简写TDVRP)。主要研究内容如下:
第1章首先介绍了论文所要研究问题的来源及研究目的,进而分析了时变网络VRP问题的背景和研究意义,并描述了本文即将讨论的三类子问题的研究特点,最后指出了本文的技术路线和主要研究工作。
第2章在对大量相关文献进行总结提炼的基础上,综述时变网络VRP问题的研究现状。描述了目前对时变网络问题的研究情况,并对已研究的时变网络VRP问题进行分类,总结了时变网络特性处理方法的研究现状。在求解算法方面,对静态VRP问题和时变网络VRP问题的求解算法进行综述,并引入本文将用于求解时变网络VRP问题的大规模邻域(very large scale neighborhood,简写VLSN)搜索技术,最后指出现有文献中存在的问题及进一步需要研究的方向。
第3章以基于时段的TDTSP问题作为研究对象,描述该问题的特征与性质,提出一种满足先入先出(first in first out,简写FIFO)准则的时变网络特征处理方法,建立问题的数学模型,并给出传统的动态规划启发式算法求解策略。在求解算法上,采用一种基于VLSN搜索技术的动态搜索算法求解该问题。通过实验比较不同算法的性能,并对算法性能进行分析。
第4章以基于位置的TDTSP问题作为研究对象,描述该问题的特征与性质,建立问题的数学模型。在求解算法上,同样采用一种基于VLSN搜索技术的动态搜索算法求解该问题。通过实验比较不同算法的性能,并对算法性能进行分析。
第5章以TDVRP问题作为研究对象,描述该问题的特征与性质,提出一种满足FIFO准则的时变网络特性处理方法,建立问题的数学模型,并给出传统的最近邻算法求解策略。在求解算法上,采用一种基于VLSN搜索技术的动态规划启发式算法和环状交换算法分别求解该问题,共有五类策略。通过实验比较不同算法的性能,并对算法性能进行分析。
第6章以成都某物流企业的配送作为背景,收集实际数据,建立该企业配送的数学模型。通过实际数据分析,对配送环境进行合理假设,得出不同情形下的最优配送路线,该路线同样也是本论文中所提算法的计算结果。该实际案例为本文所提算法的有效性提供了一个很好的实际验证背景,为企业配送作出满意决策。
结论部分对论文内容进行了全面的总结,指出了进一步研究的方向。
In China's 11th Five-Year Plan, we take modern logistics industry as a key development area in future, and put forward that by 2010 the whole societal logistics cost would be reduced 2-3 percentage points. Transportation and logistics distribution are the main factors that affect the total logistics cost, which account for the logistics cost of around 60%. As a key role of logistics optimization, the vehicle's optimal scheduling problem has become the hot research topics. In the past static vehicle routing problem (VRP) study, vehicle routing arrangements are mostly based on certain information, including the certain demand, the certain vehicle location and the certain driving time of vehicles. Especially the operating cost (time) between any two points (customers or depot) of vehicles is considered depending on the distance between points, which is usually regarded as known and constant. While in the actual traffic process, traffic management, traffic flow, traffic accidents, weather changes, and the rushing hours will change the driving speed continually, it leads the operating cost(time) in the road network correspondingly vary. So the theory and methods for static VRP are unable to apply to the dynamic environment, this makes the study of VRP in time-varying network urgent and necessary. In the dissertation, we take the three sub-problems of time-varying VRPs as study objects. They are time dependent traveling salesman problem (TDTSP) based on time period, TDTSP based on point position and time dependent vehicle routing problem (TDVRP). The main contents of this dissertation are listed as follows:
In chapter 1, we first introduce the source and purpose of the studying problem, then analyze the background and significance of VRP in time-varying network, and describe the characteristics of the three sub-problems to be discussed. Finally we conclude the technical line and the main research work.
In chapter 2, we summarize the study status quo of time-varying VRP, based on the large number of relevant literature, by classifying the studied time-varying VRPs, and summing up the methods for dealing with time-varying characteristics. We also review the algorithm for solving the static VRP and time-varying VRP, and introduce the very large scale neighborhood (VLSN) search technology issues to be used for time-varying VRPs in this dissertation. Finally we conclude the deficiency of the existing literatures and the further necessary research direction.
In chapter 3, we take TDTSP based on time period as a research object, describing the characteristics and the nature of the problem, and developing an approach to deal with time-varying characteristics which satisfies first in first out (FIFO) property. Based on it, we establish the mathematical model, and give the traditional dynamic programming heuristic strategy, and then we adopt the dynasearch algorithm based on VLSN search technology for solving the problem. Through experiments we compare the performance of different algorithms, and analyze the algorithm performance.
In chapter 4, we take TDTSP based on the point position as a research object, describing the characteristics and the nature of the problem, and establishing the mathematical model. Based on it, we also adopt the dynasearch algorithm based on VLSN search technology to solve the problem. Through experiments we compare the performance of different algorithms, and analyze the algorithm performance.
In chapter 5, we take TDVRP as a research object, describing the characteristics and the nature of the problem, and developing an approach for dealing with time-varying characteristics which satisfies FIFO property. Based on it, we establish the mathematical model, and give the traditional nearest neighborhood heuristic. For the algorithm, we adopt the dynamic programming heuristics and cyclic transfer algorithm based on VLSN search technology to solve the problem. There are all five solving strategies. Through experiments we compare the performance of different algorithms, and analyze the algorithm performance.
In chapter 6, we take the distribution operation of one logistics enterprise in Chengdu as a background, by collecting the actual data and establishing the enterprise distribution model. Through the actual collection data and analysis, we give some reasonable assumptions for distribution. Based on it, we get the optimal distribution routes in various situations, which is also the result of algorithms mentioned in this dissertation. The case provides a good actual background for verifying the algorithms' efficiency. From it, we can make the satisfactory decision for the enterprise.
In conclusion, we summarize the dissertation content and prospect the future orientation of the problem.
第1章首先介绍了论文所要研究问题的来源及研究目的,进而分析了时变网络VRP问题的背景和研究意义,并描述了本文即将讨论的三类子问题的研究特点,最后指出了本文的技术路线和主要研究工作。
第2章在对大量相关文献进行总结提炼的基础上,综述时变网络VRP问题的研究现状。描述了目前对时变网络问题的研究情况,并对已研究的时变网络VRP问题进行分类,总结了时变网络特性处理方法的研究现状。在求解算法方面,对静态VRP问题和时变网络VRP问题的求解算法进行综述,并引入本文将用于求解时变网络VRP问题的大规模邻域(very large scale neighborhood,简写VLSN)搜索技术,最后指出现有文献中存在的问题及进一步需要研究的方向。
第3章以基于时段的TDTSP问题作为研究对象,描述该问题的特征与性质,提出一种满足先入先出(first in first out,简写FIFO)准则的时变网络特征处理方法,建立问题的数学模型,并给出传统的动态规划启发式算法求解策略。在求解算法上,采用一种基于VLSN搜索技术的动态搜索算法求解该问题。通过实验比较不同算法的性能,并对算法性能进行分析。
第4章以基于位置的TDTSP问题作为研究对象,描述该问题的特征与性质,建立问题的数学模型。在求解算法上,同样采用一种基于VLSN搜索技术的动态搜索算法求解该问题。通过实验比较不同算法的性能,并对算法性能进行分析。
第5章以TDVRP问题作为研究对象,描述该问题的特征与性质,提出一种满足FIFO准则的时变网络特性处理方法,建立问题的数学模型,并给出传统的最近邻算法求解策略。在求解算法上,采用一种基于VLSN搜索技术的动态规划启发式算法和环状交换算法分别求解该问题,共有五类策略。通过实验比较不同算法的性能,并对算法性能进行分析。
第6章以成都某物流企业的配送作为背景,收集实际数据,建立该企业配送的数学模型。通过实际数据分析,对配送环境进行合理假设,得出不同情形下的最优配送路线,该路线同样也是本论文中所提算法的计算结果。该实际案例为本文所提算法的有效性提供了一个很好的实际验证背景,为企业配送作出满意决策。
结论部分对论文内容进行了全面的总结,指出了进一步研究的方向。
In China's 11th Five-Year Plan, we take modern logistics industry as a key development area in future, and put forward that by 2010 the whole societal logistics cost would be reduced 2-3 percentage points. Transportation and logistics distribution are the main factors that affect the total logistics cost, which account for the logistics cost of around 60%. As a key role of logistics optimization, the vehicle's optimal scheduling problem has become the hot research topics. In the past static vehicle routing problem (VRP) study, vehicle routing arrangements are mostly based on certain information, including the certain demand, the certain vehicle location and the certain driving time of vehicles. Especially the operating cost (time) between any two points (customers or depot) of vehicles is considered depending on the distance between points, which is usually regarded as known and constant. While in the actual traffic process, traffic management, traffic flow, traffic accidents, weather changes, and the rushing hours will change the driving speed continually, it leads the operating cost(time) in the road network correspondingly vary. So the theory and methods for static VRP are unable to apply to the dynamic environment, this makes the study of VRP in time-varying network urgent and necessary. In the dissertation, we take the three sub-problems of time-varying VRPs as study objects. They are time dependent traveling salesman problem (TDTSP) based on time period, TDTSP based on point position and time dependent vehicle routing problem (TDVRP). The main contents of this dissertation are listed as follows:
In chapter 1, we first introduce the source and purpose of the studying problem, then analyze the background and significance of VRP in time-varying network, and describe the characteristics of the three sub-problems to be discussed. Finally we conclude the technical line and the main research work.
In chapter 2, we summarize the study status quo of time-varying VRP, based on the large number of relevant literature, by classifying the studied time-varying VRPs, and summing up the methods for dealing with time-varying characteristics. We also review the algorithm for solving the static VRP and time-varying VRP, and introduce the very large scale neighborhood (VLSN) search technology issues to be used for time-varying VRPs in this dissertation. Finally we conclude the deficiency of the existing literatures and the further necessary research direction.
In chapter 3, we take TDTSP based on time period as a research object, describing the characteristics and the nature of the problem, and developing an approach to deal with time-varying characteristics which satisfies first in first out (FIFO) property. Based on it, we establish the mathematical model, and give the traditional dynamic programming heuristic strategy, and then we adopt the dynasearch algorithm based on VLSN search technology for solving the problem. Through experiments we compare the performance of different algorithms, and analyze the algorithm performance.
In chapter 4, we take TDTSP based on the point position as a research object, describing the characteristics and the nature of the problem, and establishing the mathematical model. Based on it, we also adopt the dynasearch algorithm based on VLSN search technology to solve the problem. Through experiments we compare the performance of different algorithms, and analyze the algorithm performance.
In chapter 5, we take TDVRP as a research object, describing the characteristics and the nature of the problem, and developing an approach for dealing with time-varying characteristics which satisfies FIFO property. Based on it, we establish the mathematical model, and give the traditional nearest neighborhood heuristic. For the algorithm, we adopt the dynamic programming heuristics and cyclic transfer algorithm based on VLSN search technology to solve the problem. There are all five solving strategies. Through experiments we compare the performance of different algorithms, and analyze the algorithm performance.
In chapter 6, we take the distribution operation of one logistics enterprise in Chengdu as a background, by collecting the actual data and establishing the enterprise distribution model. Through the actual collection data and analysis, we give some reasonable assumptions for distribution. Based on it, we get the optimal distribution routes in various situations, which is also the result of algorithms mentioned in this dissertation. The case provides a good actual background for verifying the algorithms' efficiency. From it, we can make the satisfactory decision for the enterprise.
In conclusion, we summarize the dissertation content and prospect the future orientation of the problem.
引文
1 丁俊发.我国物流业进入快速协调发展轨道[J].中国合作经济.2006,(4):17-20
2 Canen AG,Scott LG.Bridging theory and practice in VRP[J].The Journal of the Operational Research Society.1995,46(1):1-8
3 李军,郭耀煌.物流配送:车辆优化调度理论与方法[M].北京:中国物资出版社,2001
4 Dantzig GB,Ramser KB.The truck dispatch problem[M].Management Science.1959,10(6):80-91
5 谢秉磊.随机车辆路径问题研究[D].博士学位论文,西南交通大学.2003
6 谢秉磊,郭耀煌,郭强.动态车辆路径问题:现状与展望[J].系统工程理论方法应用.2002,11(2):116-120
7 肖增敏,李军.动态网络车辆路径问题:研究现状及展望[J].系统工程.2004,22(7):68-71
8 石建军,宋延,程世东.车辆实时调度中的城市路网及交通描述模型[J].公路交通科技.2005,22(5):128-131
9 宋延,王海忠,石建军,许国华.基于ITS技术构建物流车辆调度信息平台[J].交通标准化.2005,1:77-80
10 肖增敏.动态网络车辆路径问题研究[D].硕士学位论文,西南交通大学.2005
11 Malandraki C,Daskin MS.Time dependent vehicle routing problems:formulations,properties and heuristic algorithms[J].Transportation Science.1992,26:185-200
12 Larson RC,Odoni AR.Urban operations research[M].Prentice-Hall,Englewood Cliffs,1981
13 Malandraki C.Time dependent vehicle routing problem:formulations,solution algorithms and computations experiments[D].Doctor Degree Dissertation,Northwestern University.1989
14 Ahn BH,Shin JY.Vehicle-routing with time windows and time-varying congestion[J].Journal of the Operational Research Society.1991,42(5):393-400
15 Hill AV,Mabert VA,Montgomery DW.A decision support system for the courier vehicle scheduling problem[J].Omega.1988,44(16):333-345
16 Hill AV,Benton WC.Modeling intra-city time-dependent travel speeds for vehicle scheduling problems[J].Journal of the Operational Research Society.1992,43(4): 343-351
17 Malandraki C, Dial RB. A restricted dynamic programming heuristic algorithm for the time dependent traveling salesman problem[J]. European Journal of Operational Research.1996,90:45-55
18 Horn MET. Efficient modeling of travel in networks with time-varying link: speeds[J].Networks. 2000, 36(2): 80-90
19 Ichoua S, Gendreau M, Potvin JY. Vehicle dispatching with time-dependent travel times[J].European Journal of Operational Research. 2003, 144(2): 379-396
20 Fleischmann B, Gietz M, Gnutzmann S. Time-varying travel times in vehicle routing[J].Transportation Science. 2004, 38(2): 160-173
21 Jung S. A genetic algorithm for vehicle routing problem with time dependent travel times[D]. Doctor Degree Dissertation, Graduate Student Department of Civil Engineering University of Maryland College Park, Maryland. 2000
22 Jung S, Haghani A. Genetic algorithm for the time-dependent vehicle routing problem[J].Transportation Research Record. 2001, 2001(1771): 164-171
23 Haghani A, Jung S. A dynamic vehicle routing problem with time-dependent travel times[J].Computer & Operations Research. 2005, 32(11): 2959-2986
24 Li FY. Modeling and solving variants of the vehicle routing problem: algorithms, test problems, and computational results[D]. Doctor Degree Dissertation, Faculty of the Graduate School of the University of Maryland. 2005
25 Park YB. A solution of the bicriteria vehicle scheduling problems with time and area-dependent travel speeds[J]. Computers & Industrial Engineering. 2000, 38(1):173-187
26 Hashimoto H, Yagiura M, Ibaraki T. An iterated local search algorithm for the time-dependent vehicle routing problem with time windows[R]. Department of Applied Mathematics & Physics, Kyoto University Technical Report. 2007-013
27 Fox KR. Production scheduling on parallel lines with dependencies[D]. Doctor Degree Dissertation, Johns Hopkins University. 1973
28 Fox KR, Gavish B, Graves SC. A n-constraint formulation of the (time-dependent) traveling salesman problem[J]. Operations Research. 1980,28(4): 1018-1021
29 Picard JC, Queryranne M. The time-dependent traveling salesman problem and its application to the tardiness problem in one-machine scheduling[J]. Operations Research. 1978,26(1):86-110
30 Lucena A.Time-dependent traveling salesman problem-the deliveryman case[J].Networks.1990,66(20):753-763
31 Bianco L,Mingozzi A,Ricciardelli S.The traveling salesman problem with cumulative cost[J].Networks.1993,23(2):81-91
32 Wiel RJV,Sahinidis NV.Heuristic bounds and test problem generation for the time-dependent traveling salesman problem[J].Transportation Science.1995,29(22):167-183
33 Ford LR,Fulkerson DR.Constructing maximal dynamic flows from static flows[J].Operations Research.1958,6(3):419-433
34 Cooke KL,Halsey E.The shortest route through a network with time-dependent intemodal transit times[J].Journal of Mathematical Analysis and Applications.1966,14:492-498
35 Dreyfus SE.An appraisal of some shortest-path algorithms[J].Operations Research.1969,17(3):395-412
36 Orda A,Rom R.Shortest path and minimum-delay algorithms in networks with time-dependent edge-length[J].Journal of the ACM.1990,37(3):607-625
37 王江晴,康立山.动态车辆路径问题中的实时最短路径算法研究[J].武汉理工大学学报(交通科学与工程版).2007,31(1):46-49
38 Marguier P,Ceder A.Passenger waiting strategies for overlapping bus routes[J].Transportation Science.1984,18(3):207-230
39 Hickman MD,Bernstein DH.Transit service and path choice models in stochastic and time-dependent networks[J].Transportation Science.1997,31(2):129-146
40 Bowman,EH.Production scheduling by the transportation method of linerar programming[J].Operations Research.1956,4(1):100-103
41 Miller CE,Tucker AW,Zemlin RA.Integer programming formulation of traveling salesman problems[J].Journal of the ACM.1960,7(4):326-329
42 Hadley G.Nonlinear and dynamic programming[M].Addison-Wesley Publishing Co.,Inc.,Reading,MA.1964
43 王正国,工红卫,刘会新.双目标时变速度车辆路径问题的模型及算法[J].华中科技大学学报(自然科学版).2005,12:94-97
44 王正国,刘振元,王红卫.适应性禁忌搜索算法求解带回程的时变速度车辆路径问题[J].计算机集成制造系统.2006,12(9):1453-1458
45 Christos A.State space partitioning methods for stochastic shortest path problems[J].Networks.1997,30(1):9-21
46 张岩,贺国光.一类新的动态车辆调度问题的建模与算法[J].控制工程.2007,5:562-565
47 Brown GG,Ellis CJ,Graves GW,Ronen D.Real-time,wide area dispatch of mobil tank trucks[J].Interfaces.1987,17:107-120
48 Fisher ML,Greenfield AJ,Jaikuman R,Lester JT.A computerized vehicle routing application[J].Interfaces.1982,12(4):42-52
49 Hill AV,Mabert V,Montgomory D.A decision support system for the courier vehicle scheduling problem[J].Omega.1988,16(44):333-345
50 Rousseau JM,Roy S,Rao.Répartition assistée par ordinateur:la description d'un prototype[D].Doctor Degree Dissertation,Centre de recherche sur les transports,Universit de Montral,Canada.1988
51 Shen Y,Potvin JY.A computer assistant for vehicle dispatching with learning capabilities[J].Operations Research.1995,61(1):189-211
52 Bentner J,Bauer G,Obermair GM,Morgenstern I,Schneider J.Optimization of the time-dependent traveling salesman problem with monte carlo methods[J].Physica Review.2001,64(3):036701
53 Schneider J.The time-dependent traveling salesman problem[J].Physica A:Statistical Mechanics and its Applications.2002,314(1-4):151-155
54 Ziliaskopoulos AK,Mahmassani HS.Time dependent,shortest-path algorithm for real-time intelligent vehicle highway system applications[J].Transportation research record.1993,1408:94-100
55 Ziliaskopoulos AK.Optimum path algorithms on multidimensional networks:analysis,design,implementation and computational experience[D].Doctor Degree Dissertation,University of Texas at Austin.1994
56 Chabini I.Fastest routes in temporal networks revisited[J].Optimization Days,Montreal.1996
57 Chabini I.A new algorithm for shortest paths in discrete dynamic networks[A].Proceedings of the IFAC Symposium on Transportation Systems.1997
58 Nachtigall K.Time depending shortest-path problems with applications to railway networks[J].European Journal of Operational Research.1995,83(1):154-166
59 Donati AV, Gambardella LM, Casagrande N, Montemanni R, Rizzoli AE. Time dependent vehicle routing problem with an ant colony system[A]. Istituto Dalle Molle di Studi sull'Intelligenza Artificiale (IDSIA) Galleria 2, 6928 Manno, Switzerland. 2003
60 Donati AV, Montemanni R, Gambardella LM, Casagrande N, Rizzoli AE. Integeration of a robust shortest path algorithm with a time dependent vehicle routing model and applications[A]. International Symposium on Computational Intelligence for Measurement Systems and Applocation Lugano, Switzerland. 2003
61 Donati AV, Montemanni R, Casagrande N, Rizzoli AE, Gambardella LM. Time dependent vehicle routing problem with a multi ant colony system[J]. European Journal of Operational Research. 2008, 185(3): 1174-1191
62 Halpern J. Shortest route with time dependent length of edges and limited delay possibilities in nodes[J]. Mathematical Methods of Operations Research (ZOR). 1977,21(3): 117-124
63 Palma D, Hansen P, Labbe M. Commuters' paths with penalties for early or late arrival time[J]. Transportation Science. 1990, 24(4): 276-286
64 Hall RW. The fastest path through a network with random time-dependent travel times[J].Transportation science. 1986, 20(33): 182-188
65 Hickman MD, Wilson NHM. Passenger travel time and path choice implications of real-time transit information[J]. Transportation Research. 1995, 3(4): 211-226
66 Psaraftis HN, Tsitsiklis JN. Dynamic shortest paths in acyclic networks with markovian arc costs[J]. Operations Research. 1993,41(1): 91-101
67 Bertsimas DJ, Simchi-Levi D. A new generation of vehicle routing research: Robust algorithms, addressing uncertainty[J]. Operations Research. 1996, 44(2):286-304
68 Van Woensel T, Kerbache L, Peremans H, Vandaele N. A queueing framework for routing problems with time-dependent travel times[J]. Journal of Mathematical Modelling and Algorithms. 2007,6(1):151-173
69 Van Woensel T, Kerbache L, Peremans H, Vandaele N. Vehicle routing with dynamic travel times: A queueing approach[J]. European Journal of Operational Research. 2008, 186(3):990-1007
70 Laporte G, Mercure H, Nobert Y. An exact algorithm for the asymmetrical capacitated vehicle routing problem[J]. Networks. 1986,16:33-46
71 Christofides N, Mingozzi A, Toth P. Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations[J].Mathematical Programming.1981,20:255-282
72 Fisher ML.Optimal solution of vehicle routing problems using minimum k-trees[J].Operations Research.1994,42(4):626-642
73 Eilon S,Watson-Gandy CDT,Christofides N.Distribution management:mathematical modelling and practical analysis[M].Griffin,London.1971
74 Christofides N,Mingozzi A,Toth P.State space relaxation procedures for the computation of bounds to routing problems[J].Networks.1981,11:145-164
75 Balinsk M,Quandi R.On an integer program for a delivery problem[J].Operations Research.1964,12(2):300-304
76 Rao MR,Ziont S.Allocation of transportation units to alternative trips-a column generation scheme with out-of-kilter sub-problems[J].Operations Research.1968,15(1):52-63
77 Agarwal Y,Mathur K,Salkin HM.A set-partitioning-based exact algorithm for the vehicle routing problem[J].Networks.1989,19(7):731-749
78 Desrosiers J,Soumis F,Desrochers N.Routing with time windows by column generation[J].Networks.1984,14(44):545-565
79 Clarke G,Wright JW.Scheduling of vehicles from a central depot to a number of delivery points[J].Operations Research.1964,12(4):568-581
80 Desrochers M,Verhoog T.A matching based algorithm for the vehicle routing problem[A].Cahiers du GERAD.1989
81 Altinkemer K,Gavish B.Parallel savings based heuristics for the delivery problem[J].Operations Research.1991,39(3):456-469
82 Gillett B,Miller L.A heuristic algorithm for the vehicle dispatch problem[J].Operations Research.1974,22(2):340-349
83 Fisher ML,Jaikumar R.A generalized assignment heuristic for vehicle routing[J].Networks.1981,11(2):109-124
84 Ryan DM,Hjorring C,Glover F.Extensions of the petal method for vehicle routing[J].The Journal of the Operational Research Society.1993,44(3):289-296
85 Beasley JE.Route first-cluster second methods for vehicle routing[J].Omega.1983,11(4):403-408
86 Lin S,Kernighan B.An effective heuristic algorithm for the traveling salesman problem[J].Operations Research.1973,21(2):498-516
87 Thompson PM, Psaraftis HN. Cyclic transfer algorithms for multivehicle routing and scheduling problems[J]. Operations Research. 1993, 41(5): 935-946
88 Breedam AV. An analysis of the behavior of heuristics for the vehicle routing problem for a selection of problems with vehicle-related and time-related constraints[D]. Doctor Degree Dissertation, University of Antwerp. 1994
89 Kinderwater GAP, Savelsbergh MWP. Vehicle routing: Handling edge exchanges[A]. In Aarts EHL and Lenstra JK, editors, Local Search in Combinatorial Optimization, Wiley,Chichester, UK, 1997: 337-360
90 Bullnheimer B, Haiti RF, Strauss C. An improved ant system algorithm for the vehicle routing problem[R]. Technical Report POM-10/97. Institute of Management Science,University of Vienna. 1997
91 Gambardella LM, Taillard ED, Agazzi G. New ideas in optimization[M]. London:McGraw-Hill, 1999: 63-76
92 Oliver IM, Smith DJ, Holland RC. A study of permutation crossover operatiors on the travelling salesman problem[A]. Proceedings of the Third International Conference on Genetic Algorithms. 1989
93 Fogel DE. Applying evolutionary programming approach to selected TSPs[J]. Cybern and syst: An International Journal. 1993, 24: 27-36
94 Berthold K, Gillotineabel BP. A genetic approach[J]. European Journal of Operational Research. 1995, 84: 645-661
95 Malmborg C. Genetic algorithm for service level based vehicle scheduling[J]. European Journal of Operational Research. 1996, 93(1):121-134
96 Ochi LS, Vianna DS, Drummond LMA. Parallel evolutionary algorithm for the vehicle routing problem with heterogeneous fleet[J]. Future Generation Computer Systems. 1998,14(5-6): 285-292
97 Osman IH. Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem[J]. Annals of Operations Research. 1993, 41(4): 421-451
98 Van BA. Improvement heuristics for the vehicle routing problem based on simulation annealing[J]. European Journal of Operational Research. 1995, 86(3): 480-490
99 Gendreau M, Hertz A, Laporte G. A tabu search heuristic for the vehicle routing problem[J].Management Science. 1994,40(10): 1276-1289
100 Jiefeng X,James PK.A network flow-based tabu search heuristic for the vehicle routing problem[J].Transportation Science.1996,30(4):379-393
101 Duhamel C,Potvin JY,Rousseau JM.Tabu search heuristic for the vehicle routing problem with backhauls and time windows[J].Transportation Science.1997,31(1):49-59
102 Barbarosoglu G,Ozgur D.A tabu search algorithm for the vehicle routing problem[J].Computers and Operations Research.1999,26(3):255-270
103 Nygard KE,Juell P,Kadaba N.Neural networks for selecting vehicle routing heuristics[J].ORSA Journal on Computing.1990,2(4):353-364
104 Torki A,Somhon S,Enkawa T.A competitive neural network algorithm for solving vehicle routing problem[J].Computers and Industrial Engineering.1997,33(3):473-476
105 Fischetti M,Laporte G,Martello S.The delivery man problem and cumulative matroids[J].Operations Research.1993,41(6):1055-1064
106 郑成武,刘冬梅.时变网络中物流车辆调度问题的研究[J].天津师范大学学报(自然科学版).2007,27(3):76-80
107 周长峰,谭跃进,廖良才.可变行驶时间的动态车辆路径与调度[J].交通运输系统工程与信息.2006,6(6):91-95
108 Ahuja RK,Ergum O,Orlin JB,Punnen AP.A survey of very large-scale neighborhood search techniques[J].Discrete Applied Mathematics.2002,123(1-3):75-102
109 Tang LX,Potts CN.The optimal and iterated local search algorithms for the scheduling problems[R].The Technical Report at the Department of Operational Research of Faculty of Mathematical Studies,University of Southampton,Southampton,UK.2001
110 Potts CN,Van De Velde SL.Dynasearch-iterative local improvement by dynamic programming:part Ⅰ,The traveling salesman problem[M].Reprint,Faculty of Mathematical Studies,University of Southampton,Southampton,UK.1995
111 Congram RK.Polynominally searchable exponential neighbourhoods for sequencing;problems in combinatorial optimization[D].Doctor Degree Dissertation,University of Southampton.2000
112 Glover F.Ejection chains,reference structures,and alternating path algorithms for the traveling salesman problem[R].Research Report,University of Colorado Boulder,Graduate School of Business.1992
113 Thompson PM,Orlin JB.The theory of cyclic transfers[Z].Working Paper,No.OR 200-89 Operations Research Center,MIT,Cambridge,MA.1989
114 Ahuja RK, Orlin JB, Sharma D. Very large-scale neighborhood search[J]. International Transactions in Operational Research. 2000, 7(4-5):301 -317
115 Ahuja RK, Orlin JB, Sharma D. New neighborhood search structures for the capacitated minimum spanning tree problem[Z]. Working paper, Sloan School of Management, MIT,Cambridge, MA, Mathematical Programming. 2000
116 Congram RK, Potts CN, Van de Velde SL. An iterated dynasearch algorithm for the single machine total weighted tardiness scheduling problem[Z]. Working paper. 1998
117 Potts CN, Van de Velde SL. Dynasearch-iterative local improvement by dynamic programming. part I. the traveling salesman problem[R]. Technical Report, University of Twente, The Netherlands. 1995
118 Carlier J, Villon P. A new heuristic for the traveling salesman problem[J]. RAIRO Operations Research. 1990, 24: 245-253
119 Gilmore P, Lawler E, Shmoys D. Well-solved Special Cases[A]. In Lawler et al.(eds.),The Traveling SalesmanProblem. A Guided Tour of Combinatorial Optimization. Wiley,Chichester. 1985:87-143
120 Sarvanov VI, Doroshko NN. Approximate solution of the traveling salesman problem by a local algorithm with scanning neighbourhood of factorial cardinality in cubic time, Software:Algorithms and Programs[J]. Mathematics Institute of the Belorussia Academy of Science,Minsk. 1981,31:11-13
121 Deineko V, Woeginger GJ. A study of exponential neighborhoods for the traveling salesman problem and the quadratic assignment problem[R]. Report Woe-05, Technical Univerisity Graz. 1997
122 Taillard ED. Heuristic methods for large centroid clustering problems[R]. Technical Report IDSIA-96-96, Lugano. 1996
123 OR I. Traveling salesman-type combinatorial problems and their relation to the logistics of blood banking[D]. Doctor Degree Dissertation, Evanston: Northwestern University. 1976
124 Croes GA. A method for solving traveling salesman problems[J]. Operations Research.1958, 6(6): 791-812
125 Lin S. Computer solutions to the traveling salesman problem[J]. Bell System Technology Journal. 1965, 44 : 2245-2269
126 Stewart WR. Accelerated branch exchange heuristics for symmetric traveling salesman problem[J]. Networks. 1987, 17(4): 423-437
127 Johnson DS,Mcgeoch LA,Rothberg EE.Near-optimal solutions to very large traveling salesman problem[A].Presented at TIMX/ORSA,New Orleans.1987
128 Psaraftis HN,K-interchange procedure for local search in a precedence-constrained routing problem[J].European Journal of Operations Research.1983,13(4):391-402
129 Savelsbergh MWP.Local search in routing problems with time windows[J].Annals Operations Research.1985,4(1):285-305
2 Canen AG,Scott LG.Bridging theory and practice in VRP[J].The Journal of the Operational Research Society.1995,46(1):1-8
3 李军,郭耀煌.物流配送:车辆优化调度理论与方法[M].北京:中国物资出版社,2001
4 Dantzig GB,Ramser KB.The truck dispatch problem[M].Management Science.1959,10(6):80-91
5 谢秉磊.随机车辆路径问题研究[D].博士学位论文,西南交通大学.2003
6 谢秉磊,郭耀煌,郭强.动态车辆路径问题:现状与展望[J].系统工程理论方法应用.2002,11(2):116-120
7 肖增敏,李军.动态网络车辆路径问题:研究现状及展望[J].系统工程.2004,22(7):68-71
8 石建军,宋延,程世东.车辆实时调度中的城市路网及交通描述模型[J].公路交通科技.2005,22(5):128-131
9 宋延,王海忠,石建军,许国华.基于ITS技术构建物流车辆调度信息平台[J].交通标准化.2005,1:77-80
10 肖增敏.动态网络车辆路径问题研究[D].硕士学位论文,西南交通大学.2005
11 Malandraki C,Daskin MS.Time dependent vehicle routing problems:formulations,properties and heuristic algorithms[J].Transportation Science.1992,26:185-200
12 Larson RC,Odoni AR.Urban operations research[M].Prentice-Hall,Englewood Cliffs,1981
13 Malandraki C.Time dependent vehicle routing problem:formulations,solution algorithms and computations experiments[D].Doctor Degree Dissertation,Northwestern University.1989
14 Ahn BH,Shin JY.Vehicle-routing with time windows and time-varying congestion[J].Journal of the Operational Research Society.1991,42(5):393-400
15 Hill AV,Mabert VA,Montgomery DW.A decision support system for the courier vehicle scheduling problem[J].Omega.1988,44(16):333-345
16 Hill AV,Benton WC.Modeling intra-city time-dependent travel speeds for vehicle scheduling problems[J].Journal of the Operational Research Society.1992,43(4): 343-351
17 Malandraki C, Dial RB. A restricted dynamic programming heuristic algorithm for the time dependent traveling salesman problem[J]. European Journal of Operational Research.1996,90:45-55
18 Horn MET. Efficient modeling of travel in networks with time-varying link: speeds[J].Networks. 2000, 36(2): 80-90
19 Ichoua S, Gendreau M, Potvin JY. Vehicle dispatching with time-dependent travel times[J].European Journal of Operational Research. 2003, 144(2): 379-396
20 Fleischmann B, Gietz M, Gnutzmann S. Time-varying travel times in vehicle routing[J].Transportation Science. 2004, 38(2): 160-173
21 Jung S. A genetic algorithm for vehicle routing problem with time dependent travel times[D]. Doctor Degree Dissertation, Graduate Student Department of Civil Engineering University of Maryland College Park, Maryland. 2000
22 Jung S, Haghani A. Genetic algorithm for the time-dependent vehicle routing problem[J].Transportation Research Record. 2001, 2001(1771): 164-171
23 Haghani A, Jung S. A dynamic vehicle routing problem with time-dependent travel times[J].Computer & Operations Research. 2005, 32(11): 2959-2986
24 Li FY. Modeling and solving variants of the vehicle routing problem: algorithms, test problems, and computational results[D]. Doctor Degree Dissertation, Faculty of the Graduate School of the University of Maryland. 2005
25 Park YB. A solution of the bicriteria vehicle scheduling problems with time and area-dependent travel speeds[J]. Computers & Industrial Engineering. 2000, 38(1):173-187
26 Hashimoto H, Yagiura M, Ibaraki T. An iterated local search algorithm for the time-dependent vehicle routing problem with time windows[R]. Department of Applied Mathematics & Physics, Kyoto University Technical Report. 2007-013
27 Fox KR. Production scheduling on parallel lines with dependencies[D]. Doctor Degree Dissertation, Johns Hopkins University. 1973
28 Fox KR, Gavish B, Graves SC. A n-constraint formulation of the (time-dependent) traveling salesman problem[J]. Operations Research. 1980,28(4): 1018-1021
29 Picard JC, Queryranne M. The time-dependent traveling salesman problem and its application to the tardiness problem in one-machine scheduling[J]. Operations Research. 1978,26(1):86-110
30 Lucena A.Time-dependent traveling salesman problem-the deliveryman case[J].Networks.1990,66(20):753-763
31 Bianco L,Mingozzi A,Ricciardelli S.The traveling salesman problem with cumulative cost[J].Networks.1993,23(2):81-91
32 Wiel RJV,Sahinidis NV.Heuristic bounds and test problem generation for the time-dependent traveling salesman problem[J].Transportation Science.1995,29(22):167-183
33 Ford LR,Fulkerson DR.Constructing maximal dynamic flows from static flows[J].Operations Research.1958,6(3):419-433
34 Cooke KL,Halsey E.The shortest route through a network with time-dependent intemodal transit times[J].Journal of Mathematical Analysis and Applications.1966,14:492-498
35 Dreyfus SE.An appraisal of some shortest-path algorithms[J].Operations Research.1969,17(3):395-412
36 Orda A,Rom R.Shortest path and minimum-delay algorithms in networks with time-dependent edge-length[J].Journal of the ACM.1990,37(3):607-625
37 王江晴,康立山.动态车辆路径问题中的实时最短路径算法研究[J].武汉理工大学学报(交通科学与工程版).2007,31(1):46-49
38 Marguier P,Ceder A.Passenger waiting strategies for overlapping bus routes[J].Transportation Science.1984,18(3):207-230
39 Hickman MD,Bernstein DH.Transit service and path choice models in stochastic and time-dependent networks[J].Transportation Science.1997,31(2):129-146
40 Bowman,EH.Production scheduling by the transportation method of linerar programming[J].Operations Research.1956,4(1):100-103
41 Miller CE,Tucker AW,Zemlin RA.Integer programming formulation of traveling salesman problems[J].Journal of the ACM.1960,7(4):326-329
42 Hadley G.Nonlinear and dynamic programming[M].Addison-Wesley Publishing Co.,Inc.,Reading,MA.1964
43 王正国,工红卫,刘会新.双目标时变速度车辆路径问题的模型及算法[J].华中科技大学学报(自然科学版).2005,12:94-97
44 王正国,刘振元,王红卫.适应性禁忌搜索算法求解带回程的时变速度车辆路径问题[J].计算机集成制造系统.2006,12(9):1453-1458
45 Christos A.State space partitioning methods for stochastic shortest path problems[J].Networks.1997,30(1):9-21
46 张岩,贺国光.一类新的动态车辆调度问题的建模与算法[J].控制工程.2007,5:562-565
47 Brown GG,Ellis CJ,Graves GW,Ronen D.Real-time,wide area dispatch of mobil tank trucks[J].Interfaces.1987,17:107-120
48 Fisher ML,Greenfield AJ,Jaikuman R,Lester JT.A computerized vehicle routing application[J].Interfaces.1982,12(4):42-52
49 Hill AV,Mabert V,Montgomory D.A decision support system for the courier vehicle scheduling problem[J].Omega.1988,16(44):333-345
50 Rousseau JM,Roy S,Rao.Répartition assistée par ordinateur:la description d'un prototype[D].Doctor Degree Dissertation,Centre de recherche sur les transports,Universit de Montral,Canada.1988
51 Shen Y,Potvin JY.A computer assistant for vehicle dispatching with learning capabilities[J].Operations Research.1995,61(1):189-211
52 Bentner J,Bauer G,Obermair GM,Morgenstern I,Schneider J.Optimization of the time-dependent traveling salesman problem with monte carlo methods[J].Physica Review.2001,64(3):036701
53 Schneider J.The time-dependent traveling salesman problem[J].Physica A:Statistical Mechanics and its Applications.2002,314(1-4):151-155
54 Ziliaskopoulos AK,Mahmassani HS.Time dependent,shortest-path algorithm for real-time intelligent vehicle highway system applications[J].Transportation research record.1993,1408:94-100
55 Ziliaskopoulos AK.Optimum path algorithms on multidimensional networks:analysis,design,implementation and computational experience[D].Doctor Degree Dissertation,University of Texas at Austin.1994
56 Chabini I.Fastest routes in temporal networks revisited[J].Optimization Days,Montreal.1996
57 Chabini I.A new algorithm for shortest paths in discrete dynamic networks[A].Proceedings of the IFAC Symposium on Transportation Systems.1997
58 Nachtigall K.Time depending shortest-path problems with applications to railway networks[J].European Journal of Operational Research.1995,83(1):154-166
59 Donati AV, Gambardella LM, Casagrande N, Montemanni R, Rizzoli AE. Time dependent vehicle routing problem with an ant colony system[A]. Istituto Dalle Molle di Studi sull'Intelligenza Artificiale (IDSIA) Galleria 2, 6928 Manno, Switzerland. 2003
60 Donati AV, Montemanni R, Gambardella LM, Casagrande N, Rizzoli AE. Integeration of a robust shortest path algorithm with a time dependent vehicle routing model and applications[A]. International Symposium on Computational Intelligence for Measurement Systems and Applocation Lugano, Switzerland. 2003
61 Donati AV, Montemanni R, Casagrande N, Rizzoli AE, Gambardella LM. Time dependent vehicle routing problem with a multi ant colony system[J]. European Journal of Operational Research. 2008, 185(3): 1174-1191
62 Halpern J. Shortest route with time dependent length of edges and limited delay possibilities in nodes[J]. Mathematical Methods of Operations Research (ZOR). 1977,21(3): 117-124
63 Palma D, Hansen P, Labbe M. Commuters' paths with penalties for early or late arrival time[J]. Transportation Science. 1990, 24(4): 276-286
64 Hall RW. The fastest path through a network with random time-dependent travel times[J].Transportation science. 1986, 20(33): 182-188
65 Hickman MD, Wilson NHM. Passenger travel time and path choice implications of real-time transit information[J]. Transportation Research. 1995, 3(4): 211-226
66 Psaraftis HN, Tsitsiklis JN. Dynamic shortest paths in acyclic networks with markovian arc costs[J]. Operations Research. 1993,41(1): 91-101
67 Bertsimas DJ, Simchi-Levi D. A new generation of vehicle routing research: Robust algorithms, addressing uncertainty[J]. Operations Research. 1996, 44(2):286-304
68 Van Woensel T, Kerbache L, Peremans H, Vandaele N. A queueing framework for routing problems with time-dependent travel times[J]. Journal of Mathematical Modelling and Algorithms. 2007,6(1):151-173
69 Van Woensel T, Kerbache L, Peremans H, Vandaele N. Vehicle routing with dynamic travel times: A queueing approach[J]. European Journal of Operational Research. 2008, 186(3):990-1007
70 Laporte G, Mercure H, Nobert Y. An exact algorithm for the asymmetrical capacitated vehicle routing problem[J]. Networks. 1986,16:33-46
71 Christofides N, Mingozzi A, Toth P. Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations[J].Mathematical Programming.1981,20:255-282
72 Fisher ML.Optimal solution of vehicle routing problems using minimum k-trees[J].Operations Research.1994,42(4):626-642
73 Eilon S,Watson-Gandy CDT,Christofides N.Distribution management:mathematical modelling and practical analysis[M].Griffin,London.1971
74 Christofides N,Mingozzi A,Toth P.State space relaxation procedures for the computation of bounds to routing problems[J].Networks.1981,11:145-164
75 Balinsk M,Quandi R.On an integer program for a delivery problem[J].Operations Research.1964,12(2):300-304
76 Rao MR,Ziont S.Allocation of transportation units to alternative trips-a column generation scheme with out-of-kilter sub-problems[J].Operations Research.1968,15(1):52-63
77 Agarwal Y,Mathur K,Salkin HM.A set-partitioning-based exact algorithm for the vehicle routing problem[J].Networks.1989,19(7):731-749
78 Desrosiers J,Soumis F,Desrochers N.Routing with time windows by column generation[J].Networks.1984,14(44):545-565
79 Clarke G,Wright JW.Scheduling of vehicles from a central depot to a number of delivery points[J].Operations Research.1964,12(4):568-581
80 Desrochers M,Verhoog T.A matching based algorithm for the vehicle routing problem[A].Cahiers du GERAD.1989
81 Altinkemer K,Gavish B.Parallel savings based heuristics for the delivery problem[J].Operations Research.1991,39(3):456-469
82 Gillett B,Miller L.A heuristic algorithm for the vehicle dispatch problem[J].Operations Research.1974,22(2):340-349
83 Fisher ML,Jaikumar R.A generalized assignment heuristic for vehicle routing[J].Networks.1981,11(2):109-124
84 Ryan DM,Hjorring C,Glover F.Extensions of the petal method for vehicle routing[J].The Journal of the Operational Research Society.1993,44(3):289-296
85 Beasley JE.Route first-cluster second methods for vehicle routing[J].Omega.1983,11(4):403-408
86 Lin S,Kernighan B.An effective heuristic algorithm for the traveling salesman problem[J].Operations Research.1973,21(2):498-516
87 Thompson PM, Psaraftis HN. Cyclic transfer algorithms for multivehicle routing and scheduling problems[J]. Operations Research. 1993, 41(5): 935-946
88 Breedam AV. An analysis of the behavior of heuristics for the vehicle routing problem for a selection of problems with vehicle-related and time-related constraints[D]. Doctor Degree Dissertation, University of Antwerp. 1994
89 Kinderwater GAP, Savelsbergh MWP. Vehicle routing: Handling edge exchanges[A]. In Aarts EHL and Lenstra JK, editors, Local Search in Combinatorial Optimization, Wiley,Chichester, UK, 1997: 337-360
90 Bullnheimer B, Haiti RF, Strauss C. An improved ant system algorithm for the vehicle routing problem[R]. Technical Report POM-10/97. Institute of Management Science,University of Vienna. 1997
91 Gambardella LM, Taillard ED, Agazzi G. New ideas in optimization[M]. London:McGraw-Hill, 1999: 63-76
92 Oliver IM, Smith DJ, Holland RC. A study of permutation crossover operatiors on the travelling salesman problem[A]. Proceedings of the Third International Conference on Genetic Algorithms. 1989
93 Fogel DE. Applying evolutionary programming approach to selected TSPs[J]. Cybern and syst: An International Journal. 1993, 24: 27-36
94 Berthold K, Gillotineabel BP. A genetic approach[J]. European Journal of Operational Research. 1995, 84: 645-661
95 Malmborg C. Genetic algorithm for service level based vehicle scheduling[J]. European Journal of Operational Research. 1996, 93(1):121-134
96 Ochi LS, Vianna DS, Drummond LMA. Parallel evolutionary algorithm for the vehicle routing problem with heterogeneous fleet[J]. Future Generation Computer Systems. 1998,14(5-6): 285-292
97 Osman IH. Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem[J]. Annals of Operations Research. 1993, 41(4): 421-451
98 Van BA. Improvement heuristics for the vehicle routing problem based on simulation annealing[J]. European Journal of Operational Research. 1995, 86(3): 480-490
99 Gendreau M, Hertz A, Laporte G. A tabu search heuristic for the vehicle routing problem[J].Management Science. 1994,40(10): 1276-1289
100 Jiefeng X,James PK.A network flow-based tabu search heuristic for the vehicle routing problem[J].Transportation Science.1996,30(4):379-393
101 Duhamel C,Potvin JY,Rousseau JM.Tabu search heuristic for the vehicle routing problem with backhauls and time windows[J].Transportation Science.1997,31(1):49-59
102 Barbarosoglu G,Ozgur D.A tabu search algorithm for the vehicle routing problem[J].Computers and Operations Research.1999,26(3):255-270
103 Nygard KE,Juell P,Kadaba N.Neural networks for selecting vehicle routing heuristics[J].ORSA Journal on Computing.1990,2(4):353-364
104 Torki A,Somhon S,Enkawa T.A competitive neural network algorithm for solving vehicle routing problem[J].Computers and Industrial Engineering.1997,33(3):473-476
105 Fischetti M,Laporte G,Martello S.The delivery man problem and cumulative matroids[J].Operations Research.1993,41(6):1055-1064
106 郑成武,刘冬梅.时变网络中物流车辆调度问题的研究[J].天津师范大学学报(自然科学版).2007,27(3):76-80
107 周长峰,谭跃进,廖良才.可变行驶时间的动态车辆路径与调度[J].交通运输系统工程与信息.2006,6(6):91-95
108 Ahuja RK,Ergum O,Orlin JB,Punnen AP.A survey of very large-scale neighborhood search techniques[J].Discrete Applied Mathematics.2002,123(1-3):75-102
109 Tang LX,Potts CN.The optimal and iterated local search algorithms for the scheduling problems[R].The Technical Report at the Department of Operational Research of Faculty of Mathematical Studies,University of Southampton,Southampton,UK.2001
110 Potts CN,Van De Velde SL.Dynasearch-iterative local improvement by dynamic programming:part Ⅰ,The traveling salesman problem[M].Reprint,Faculty of Mathematical Studies,University of Southampton,Southampton,UK.1995
111 Congram RK.Polynominally searchable exponential neighbourhoods for sequencing;problems in combinatorial optimization[D].Doctor Degree Dissertation,University of Southampton.2000
112 Glover F.Ejection chains,reference structures,and alternating path algorithms for the traveling salesman problem[R].Research Report,University of Colorado Boulder,Graduate School of Business.1992
113 Thompson PM,Orlin JB.The theory of cyclic transfers[Z].Working Paper,No.OR 200-89 Operations Research Center,MIT,Cambridge,MA.1989
114 Ahuja RK, Orlin JB, Sharma D. Very large-scale neighborhood search[J]. International Transactions in Operational Research. 2000, 7(4-5):301 -317
115 Ahuja RK, Orlin JB, Sharma D. New neighborhood search structures for the capacitated minimum spanning tree problem[Z]. Working paper, Sloan School of Management, MIT,Cambridge, MA, Mathematical Programming. 2000
116 Congram RK, Potts CN, Van de Velde SL. An iterated dynasearch algorithm for the single machine total weighted tardiness scheduling problem[Z]. Working paper. 1998
117 Potts CN, Van de Velde SL. Dynasearch-iterative local improvement by dynamic programming. part I. the traveling salesman problem[R]. Technical Report, University of Twente, The Netherlands. 1995
118 Carlier J, Villon P. A new heuristic for the traveling salesman problem[J]. RAIRO Operations Research. 1990, 24: 245-253
119 Gilmore P, Lawler E, Shmoys D. Well-solved Special Cases[A]. In Lawler et al.(eds.),The Traveling SalesmanProblem. A Guided Tour of Combinatorial Optimization. Wiley,Chichester. 1985:87-143
120 Sarvanov VI, Doroshko NN. Approximate solution of the traveling salesman problem by a local algorithm with scanning neighbourhood of factorial cardinality in cubic time, Software:Algorithms and Programs[J]. Mathematics Institute of the Belorussia Academy of Science,Minsk. 1981,31:11-13
121 Deineko V, Woeginger GJ. A study of exponential neighborhoods for the traveling salesman problem and the quadratic assignment problem[R]. Report Woe-05, Technical Univerisity Graz. 1997
122 Taillard ED. Heuristic methods for large centroid clustering problems[R]. Technical Report IDSIA-96-96, Lugano. 1996
123 OR I. Traveling salesman-type combinatorial problems and their relation to the logistics of blood banking[D]. Doctor Degree Dissertation, Evanston: Northwestern University. 1976
124 Croes GA. A method for solving traveling salesman problems[J]. Operations Research.1958, 6(6): 791-812
125 Lin S. Computer solutions to the traveling salesman problem[J]. Bell System Technology Journal. 1965, 44 : 2245-2269
126 Stewart WR. Accelerated branch exchange heuristics for symmetric traveling salesman problem[J]. Networks. 1987, 17(4): 423-437
127 Johnson DS,Mcgeoch LA,Rothberg EE.Near-optimal solutions to very large traveling salesman problem[A].Presented at TIMX/ORSA,New Orleans.1987
128 Psaraftis HN,K-interchange procedure for local search in a precedence-constrained routing problem[J].European Journal of Operations Research.1983,13(4):391-402
129 Savelsbergh MWP.Local search in routing problems with time windows[J].Annals Operations Research.1985,4(1):285-305
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |