摘要
车辆路线问题是管理科学的一个重要研究课题,其优化技术是现代物流配送
的一项关键技术。本文对车辆路线问题,以带时间窗的车辆路线问题(VRPTW)
为研究对象提出一种二阶段启发式算法,并设计一种结合路线编辑、算法调整及
系统改进的人机交互优化模式;最后对现代物流系统的配送路线问题进行研究。
车辆路线问题研究总成本最小的车辆路线,在合适的时间以合适的方式将正
确的货物运送到正确的地点。物流配送则要求在正确的时间以正确的方式将正确
的货物送到正确的地方。车辆路线问题在物流配送中有着广泛的应用背景。
在各种车辆路线问题中,一个基本问题是带时间窗口的车辆路线问题
(VRPTW)。其主要内容是:以成本最小的目标安排多辆车有序地前往配量给定
的各配送点而构成的配送路线,其中每辆车必须从同一车站出发并最后返回车
站,每个配送点只能安排一个车次在限定的时间窗内配送,且每一条配送路线不
得超过车辆的装载容量和车辆的最后返回时间;如果车辆提前到达配送点,则需
要等待,直到在时间窗内才能配送。
VRPTW 问题属于 NP-难问题,其算法通常采用了从初始状态出发进行邻域
搜索的启发式算法。其中,邻域搜索被定义为以边的替换,或者点的交换或重新
定位等为基本操作的搜索。为了使解不过早地陷入局部最优,现代启发式算法引
入了禁忌搜索、遗传算法、蚁群算法、模拟退火算法等技术。
本文以 VRPTW 问题为研究对象,提出一种二阶段启发式算法。主要内容有:
1)提出一种新的边替换搜索方法。即在搜索的一次操作中替换多条路线的
多条边。其中,限制参与边替换的路线条数、每条路线的被替换边数,以及被替
换边选自解的一个边子集。其特点是:在边子集中可以考虑所有替换组合;如果
选取所有路线的所有边考察其替换选择,则这种搜索方法便是一种穷举优化法。
2)提出一种新的点重新定位搜索方法。即在搜索的一次操作中选取多条路
线的多个点,根据最小成本插入法进行重新定位。其中,限制参与点重新定位的
路线条数、每条路线的被重新定位的点数,以及被重新定位的点选自一个点子集。
3)应用扫除法原理设计 VRPTW 问题的路线构造算法。算法考虑了车辆和
点的优先级配送,并在出现运力不足时用虚拟车辆填补运力缺口。
4)在以上创新性研究的基础上,提出一种二阶段启发式算法。本文应用这
种算法,并采用小邻域搜索的参数设置,对国际上公认的标准测试问题进行计算
试验。结果显示:应用以上两种搜索方法对初始解有显著改进;将计算试验获得
的解与目前世界上公认的最好启发式解相比较,一部分解达到最好启发式解,少
部分解的总路长低于最好启发式解的总路长,其它解则接近最好解。
这种算法的特点适合人机交互优化。通过人机交互,应用这种算法能够进一
步获得更好的解。
车辆路线问题是一类非常复杂的优化问题。在配送决策系统中,采用人机交
互的方式求解车辆路线问题是非常必要的。本文提出了一种结合路线编辑、算法
调整及系统改进的人机交互优化模式。其中,通过点的人工重新定位,进行路线
的编辑;通过路线或点的锁定,限制系统改进的搜索邻域;通过各种启发式方法
的取舍及其参数设置,调整系统改进的算法。采用这种模式,不但可弥补启发式
算法的不足,提高算法的搜索效率,而且可在突发情况下人工参与决策。
最后,本文对现代物流系统的配送路线问题,做了以下研究:
1)在不同配送环境不同配送要求下,对 VRPTW 问题的推广进行启发式方
法的研究。这些推广包括:多车型、多货舱、多品种、混合装卸、多时间窗、拆
分配送、分优先级配送、临时增减配送、跨区域配送、流量分配、运输管制、交
通约束、有限运力、有限库存/库容、工作量平衡以及成本的广义定义。
2)研究配送路线决策系统与 GIS 系统以及物流信息系统的数据交换。
3)研究油品配送、零售配送和快递配送的配送路线问题。它们分别属于散
装品配送、包装品配送和带时间目标的配送。其中,在油品配送中主要研究了宽
时间窗的启发式方法;在零售配送中分析了多仓库配送;而在快递配送中重点研
究了快件收取的车辆路线问题,其中提出三个路线决策准则,并进行模拟试验研
究。
A key element of logistic distribution systems is the routing of vehicles, which have been a
subject of management science. This paper is concerned with the research on vehicle routing
problem in logistic systems, under the research on the heuristic algorithm for the Vehicle Routing
Problem with Time Windows (VRPTW) and the design of interactive solving.
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. And
logistic distribution requires delivering the right commodities to the right place by the right
method at the right time. So vehicle routing problem represents a very important part of any
logistic distribution systems.
VRPTW involves the design of a set of minimum-cost vehicle routes, originating and
terminating at a central depot, for a fleet of vehicles that services a set of customers with known
demands. Each customer is serviced exactly once and, furthermore, all the customers must be
assigned to vehicles without exceeding vehicle capacities. With the allowable pick-up time
windows at each customer location, no vehicle is allowed to arrive too late at a customer location,
and a waiting time is introduced in the route if the vehicle arrives too early. Quite often, a time
window is also added to the depot, in order to define a scheduling horizon.
Belonging to NP-hard problems, VRPTW is usually solved by use of local search heuristic
starting from an initial solution, where the methods include edge exchange, node interchange or
relocation. To avoid local minima and ultimately find the desired solution, Metaheuristics, such as
Tabu Search, Genetic Algorithm, Ant Colony Optimization, Simulated Annealing and et al, have
received a lot of attention in the recent years.
Firstly, this paper presents a two-phase heuristic for solving VRPTW as follows.
1) Introduces an edge exchange operator. That is, replacing multiple edges within each route
of multiple routes by other multiple edges. Where the number of the related routes and the number
of the replaced edges within each route are upper bounded, and the replaced edges belongs to a
subset of the edge set of the current solution.
2) Introduces an node relocation operator. That is, relocating multiple nodes within each
route of multiple routes. Where the number of the related routes and the number of the relocated
nodes within each route are upper bounded, and the relocated nodes belongs to a node subset.
3) Illustrates the sweep heuristics for constructing a feasible solution of VRPTW. Where
virtual vehicle will be introduced if no available vehicle can service the residual nodes.
4) Presents a two-phase heuristic for solving VRPTW based on the above research, and its
computational study. The results is, the local search algorithm based on the above operators
evidently improve the initial solution constructed by the sweep algorithm, and the solutions are
close to the best known solutions identified by heuristics.
Secondly, this paper design a scheme for interactive solving of the vehicle routing problems.
Which includes man-machine interaction dynamically in computer system as follows:
1) Modifying the routes by manual relocation, and using improvement heurictic to improve
the modified solution;
2) Determining the routes that may be improved or modified by locking the other routes.
3) Interactively specifying problem-solving strategies.
Finally, this paper presents the following research on vehicle routing in advanced logistic
distribution systems:
1) Generalizations of the VRPTW, such as: non-identical vehicles, multiple compartments,
multicommodity, mixed pick-up and delivery, multiple time windows, split delivery, routing by
order and vehicle priority, real-time routing, multiple regions, special order assignment,
transportation regulations, traffic constraints, limited capacities, limited storage or available
capacities of warehouses,
引文
[1] K.Altinkemer and B.Gavish(1991), “Parallel Savings Based heuristics For The Delivery
Problem”, Operations Research39:456-469.
[2] J.B.Atkinson(1994), “A Greedy Look-ahead Heuristic For Combinatorial Optimization:An
Application to Vehicle Scheduling With Time Windows”, Journal of The Operational Research
Society 45, 673-684.
[3] J.B.Atkinson(1998), “A Greedy Randomised Search Heuristic For Time-constrained Vehicle
Scheduling And The Incorporation of A Learning Strategy”, Journal of Operations Research
Society 49: 700-708.
[4] J.Antes and U.Derigs(1995), “A New Parallel Tour Construction Algorithm for the Vehicle
Routing Problem with Time Windows”, Working Paper, Department of Economics and Computer
Science, University of K?ln, Germany.
[5] P.Badeau, M.Gendreau, F.Guertin, J.-Y. Potvin and E.Taillard(1997), ”A Parallel Tabu Search
Heuristic for the Vehicle Routing Problem with Time Windows”, Transportation Research C 5,
109?122.
[6] E.K.Baker(1983), “An Exact Algorithm For The Time-constrained Traveling Salesman
Problem”, Operations Research 31: 938-945.
[7] E.K.Baker and J.R.Schaffer(1986), “Solution Improvement Heuristics for the Vehicle Routing
and Scheduling Problem with Time Window Constraints”, American Journal of Mathematical and
Management Sciences 6, 261?300.
[8] B.M.Baker and J.Sheasby(1999), “Extensions To The Generalized Assignment Heuristic For
Vehicle Routing”, European Journal of Operational Research119:147-157.
[9] N.Balakrishnan(1993), “Simple Heuristics for the Vehicle Routeing Problem with Soft Time
Windows”, Journal of the Operational Research Society 44, 279?287.
[10] R.S.Barr, B.L.Golden, J.P.Kelly, M.G.C.Resende and W.R.Stewart(1995), “Designing and
Reporting on Computational Experiments with Heuristic Methods”, Journal of Heuristics 1, 9?32.
[11] D.O.Bausch, G.G.Brown and D.Ronen(1995), “Consolidating and Dispatching Truck
Shipments of Mobil Heavy Petroleum Products”, Interfaces25:2, 1-17,
[12] J.Beasley(1983), “Route First-Cluster Second Methods For Vehicle Routing”,
Omega118:403-408.
[13] J.M.Belenguer, M.C.Martinez and E.Mota(2000), “A Lower Bound For The Split Delivery
Vehicle Routing Problem”, Operations Research 48, P801.
[14] W.J.Bell, L.M.Dalberto, L.M.Fisher, M.L.Greenfield etc(1983), “Improving The Distribution
of Industrial Gases With An On-line Computerized Routing And Scheduling Optimizer”,
Interfaces13:4-23.
[15] R.Bent and P.Van Hentenryck(2001), “A Two-Stage Hybrid Local Search for the Vehicle
Routing Problem with Time Windows”, Technical Report CS-01-06, Department of Computer
Science, Brown University.
[16] J.Berger , M. Barkaoui and O.Br?ysy (2003), ”A Route-directed Hybrid Genetic Approach for
the Vehicle Routing Problem with Time Windows”, INFOR 41, P179.
[17] J.Berger, M.Salois and R.Begin (1998), ”A Hybrid Genetic Algorithm for the Vehicle Routing
113
参考文献
Problem with Time Windows”, Lecture Notes in Artificial Intelligence1418, 114?127.
[18] D.Bertsimas and J.N.Tsitsiklis(1997), “Introduction to Linear Optimization”, Athena
Scientific, Belmont, Massachusetts, 511-512
[19] J.L.Blanton and R.L.Wainwright(1993), ”Multiple Vehicle Routing with Time and Capacity
Constraints using Genetic Algorithms”, in Proceedings of the Fifth International Conference on
Genetic Algorithms, S. Forrest (ed), 452?459, Morgan Kaufmann Publishing, San Francisco.
[20] L.D.Bodin and B.L.Golden(1981), “Classification In Vehicle Routing And Scheduling”,
Networks11:97-108.
[21] L.Bodin, B.L.Golden, A.Assad and M.Ball(1983), “Routing And Scheduling of Vehicles And
Crews: The State of The Art”, Computers & Operations Research, Vol.10, No. 2,, 63-193.
[22]L.Bodin(1990), “Twenty Years of Routing And Scheduling”, Operations Research38:571-579.
[23] J.B.Bramel and D.Simchi-Levi(1995), “A Location Based Heuristic For General Routing
Problems”, Operations Research43:649-660.
[24] J.Bramel and D,Simchi-levi(1996), “Probabilistic Analysis And Practical Algorithms For The
Vehicle Routing Problem with Time Windows”, Operations Research44:501-509.
[25] J.Bramel and D.Simchi-levi(1997), “On The Effectiveness of Set Covering Formulation For
The Vehicle Routing Problem With Time Windows”, Operations Research45:295-301.
[26] O.Br?ysy (2003), ”A Reactive Variable Neighborhood Search for the Vehicle Routing
Problem with Time Windows”, INFORMS Journal on Computing 15, P347.
[27] O. Br?ysy, and M. Gendreau(2001), ”Route Construction and Local Search Algorithms for
the Vehicle Routing Problem with Time Windows”, Working paper, SINTEF Applied Mathematics,
Department of Optimization, Norway.
[28] O.Br?ysy, and M. Gendreau(2001), ”Genetic Algorithms for the Vehicle Routing Problem
with Time Windows”, Working paper, SINTEF Applied Mathematics, Department of Optimization,
Norway.
[29] O.Br?ysy, G. Hasle and W. Dullaert(2002), “A Fast Local Search Algorithm for the Vehicle
Routing Problem with Time Windows”, Working paper, SINTEF Applied Mathematics,
Department of Optimization, Norway.
[30] O.Br?ysy, and M.Gendreau(2002c), ”Evolutionary Algorithms for the Vehicle Routing
Problem with Time Windows”, Working paper, SINTEF Applied Mathematics, Department of
Optimization, Norway.
[31] A.V.Breedam(2001), “Comparing Descent Heuristics And Metaheuristics For The Vehicle
Routing Problem”, Computers & Operations Research 28, P289.
[32] G.Brown and G.Graves(1981), “Real-time Dispatch of Petroleum Tank Trunks”, Management
Science 27, P19.
[33] G.Brown, G.Graves and D.Ronen(1987), “Scheduling Ocean Transportation of Crude Oil”,
Management Science33:335-346.
[34] B.Bullnheimer, R.F.Hartl and C.Strauss(1999), “An Improved ant System Algorithm For The
Vehicle Routing Problem”, Annals of Operations Research89:561-581.
[35] Y.Caseau and F.Laburthe(1999), “Heuristics for Large Constrained Vehicle Routing
Problems”, Journal of Heuristics 5, 281?303.
[36] M.Chao(2002), “A Tabu Search Method For The Truck And Trailer Routing Problem”,
Computers & Operations Research129:33-51.
[37] W.Chiang and R.Russell(1996), “Simulated Annealing Metaheuristics For The Vehicle
114
参考文献
Routing Problem With Time Windows”, Annals of Operations Research63:3-27.
[38] WC Chiang and RA Russell(1997), “A Reactive Tabu Search Metaheuristic For The Vehicle
Routing Problem With Time Windows”, INFORMS J Comp9:417-430.
[39] N.Christofides, A.Mingozzi and P.Toth(1979), “The Vehicle Routing Problem”,In
Combinatorial Optimizations, N.Christofides, R. Mingozzi, P.Toth and C. Sandi(eds.). John Wiley
& Sons, New York.
[40] N.Christofides, A.Mingozzi and P.Toth(1981), “Exact Algorithms For The Vehicle Routing
Problem, Based on Spanning Tree And Shortest Path Relaxations”, Math. Program.20:255-282.
[41] G.Clarke and J.W. Wright(1964), “Scheduling of Vehicles from a Central Depot to a Number
of Delivery Points”, Operations Research 12, 568?581.
[42] J.F.Cordeau, G. Desaulniers, J. Desrosiers, M. M. Solomon and F. Soumis(2001), “The VRP
with Time Windows”, in The Vehicle Routing Problem, SIAM Monographs on Discrete
Mathematics and Applications, P. Toth and D. Vigo (eds), 157?194, SIAM, Philadelphia.
[43] J-F Cordeau, M.Gendreau, G.Laporte, J-Y Potvin and F.Semet(2002), “A Guide to Vehicle
Routing Heuristics”, Journal of Operations Research Society53:512-522.
[44] J-F Cordeau and G.Laporte(1997), “A Tabu Search Heuristic For The Periodic and
Multi-depot Vehicle Routing Problems”, Networks 30:105-119.
[45] J-F Cordeau, G.Laporte and A.Mercier(2001), “A Unified Tabu Search Heuristic For Vehicle
Routing Problems With Time Windows”, Journal of Operations Research Society52:928-936.
[46] R. Cordone and R. Wolfler-Calvo(2001), “A Heuristic for the Vehicle Routing Problem with
Time Windows”, Journal of Heuristics 7, 107?129.
[47] GB Dantzig and JH Ranmse(1959)r, “The Truck Dispatching Problem”, Management
Science6:80-91.
[48] B.De Backer, V.Furnon, P. Prosser, P. Kilby and P. Shaw(1997), “Local Search in Constraint
Programming: Application to the Vehicle Routing Problem”, in Proceedings of CP-97 Workshop
on Industrial Constraint-Directed Scheduling, 1–15, Schloss Hagenberg, Austria.
[49] M.Desrochers, J.Desrosiers and M.M.Solomon(1992), “A New Optimization Algorithm For
The Vehicle Routing Problem With Time Windows”, Operations Research40:342-354.
[50] M.Desrochers, J.K. Lenstra, M.W.P. Savelsbergh and F. Soumis(1988), “Vehicle Routing with
Time Windows: Optimization and Approximation”, in Vehicle Routing: Methods and Studies, B.
Golden and A. Assad (eds), 65–84, Elsevier Science Publishers, Amsterdam.
[51] M.Desrochers, J.K. Lenstra and M.W.P. Savelsbergh (1990), “A Classification Scheme for
Vehicle Routing and Scheduling Problems”, European Journal of Operational Research46,
322–332.
[52] M.Desrochers and F.Soumis(1988), “A Generalized Permanent Labeling Algorithm For The
Shortest Path Problems With Time Windows”, INFOR26:191-212.
[53] M.Desrochers and F.Soumis(1988), “A Re-optimization Algorithm For The Shortest Path
Problem With Time Windows”, European Journal of Operational Research35:242-254.
[54] J.Desrosiers, Y. Dumas, M.M. Solomon and F. Soumis(1995), “Time Constrained Routing
and Scheduling”, in Handbooks in Operations Research and Management Science 8: Network
Routing, M.O. Ball, T.L. Magnanti, C.L. Monma, G.L. Nemhauser (eds), 35–139, Elsevier Science
Publishers, Amsterdam.
[55] J.Desrosiers, J.K.Lenstra and MWP Savelsbergh(1990), “A Classification Scheme For
Vehicle Routing And Scheduling Problems”, European Journal of Operational Research
115
参考文献
46:322-332.
[56] J.Desrosiers, M.Sauve and F.Soumis(1988), “Lagrangean Relaxation Methods For Solving
The Minimum Fleet Size Multiple Traveling Salesman Problem With Time Windows”,
Management Science34:1005-1022.
[57] J.Desrosiers, F.Soumis and M.Desrochers(1984), “Routing With Time Windows by Column
Generation”, Networks14:545-565.
[58] J.Dethloff(2002), “Relation Between Vehicle Routing Problems: An Insertion Heuristic For
The Vehicle Routing Problem With Simultaneous Delivery And Pick-up Applied To The Vehicle
Routing Problem With Backhauls”, The Journal of The Operational Research SocietyVol.53, P115.
[59] M.Dror(1994), “Note on the Complexity of the Shortest Path Models for Column Generation
in VRPTW”, Operations Research 42,977-978.
[60] M.Dror, G.Laporte and and P.Trudeau. (1994), “Vehicle Routing With Split Deliveries”,
Discrete Appl. Math50, 239-254.
[61] Y.Dumas, J.Desrosiers, E.Gelinas and M.M.Solomon(1995), “An Optimal Algorithm For The
Traveling Salesman Problem With Time Windows”, Operations Research43:367-371.
[62] Y.J.Dumas and F.Soumis(1991), “The Pick-up And Delivery Problem With Time Windows”,
European Journal of Operational Research54:7-22.
[63] M.L.Fisher(1981), “The Lagrangian Relaxation Method For Solving Integer
Programming Problems”,Management Science,Vol.27, No.1.
[64] M.L.Fisher(1994), “Optimal Solution of Vehicle Routing Problems Using Minimum
K-Trees”, Operations Research42:626-642.
[65] M.Fisher, R.Greenfield, R.Jaikumar and J.Lester(1982), “A Computerized Vehicle Routing
Application”, Interfaces1:45-52.
[66] M.L.Fisher, Jaikumar and L.N.Van Wassenhove(1986), “A Multiplier Adjustment For The
Generalized Assignment Problem”, Management Science32:1095-1103.
[67] M.Fisher, K.L Jornsten and OBG Madsen(1997), “Vehicle Routing With Time Windows: Two
Optimization Algorithms”, Operations Research45:488-492.
[68] C.Foisy and J.-Y. Potvin(1993)., “Implementing an Insertion Heuristic for Vehicle Routing on
Parallel Hardware. Computers and Operations Research 20, 737?745.
[69] P.W.Frizell and J.W.Giffin(1992), “The Bounded Split Delivery Vehicle Routing Problem
With Grid Networks Distances”, Asia Pacific J. Oper. Res. 9, 101-116
[70] L.M.Gambardella, E. Taillard and G. Agazzi(1999), ”MACS-VRPTW: A Multiple Ant
Colony System for Vehicle Routing Problems with Time Windows”, in New Ideas in Optimization,
D. Corne, M. Dorigo and F. Glover (eds), 63?76, McGraw-Hill, London.
[71] B.L.Garcia, J.Y.Potvin and J.M.Rousseau(1994), “A Parallel Implementation of The Tabu
Search Heuristic For Vehicle Routing Problems With Time Windows Constraints”, Computers &
Operations Research21:1025-1033.
[72] H.Gehring and J. Homberger(1999), ”A Parallel Hybrid Evolutionary Metaheuristic for the
Vehicle Routing Problem with Time Windows”, in Proceedings of EUROGEN99, K. Miettinen, M.
M?kel? and J. Toivanen (eds), 57?64, University of Jyv?skyl?, Finland.
[73] H.Gehring and J.Homberger(2001), ”Parallelization of a Two-Phase Metaheuristic for
Routing Problems with Time Windows”, Asia-Pacific Journal of Operational Research18, 35?47.
[74] M.Gelinas, M.Desrochers, J.Desosiers and M.M.Solomon(1995), “A New-Branching
Strategy For Time Constrained Routing Problems With Application To Backhauling”, Annals of
116
参考文献
Operations Research61:91-109.
[75] M.Gendreau, A.Hertz and G.Laporte(1992), “New Insertion And Postoptimization Procedures
For The Traveling Salesman Problem”, Operations Research40:1086-1094.
[76] M.Gendreau, A.Hertz, G.Laporte amd M.Stan(1998), “A Generalized Insertion Heuristic For
The Traveling Salesman Problem With Time Windows”, Operations Research43:330-335.
[77] M.Gendreau, G.Laporte etc(1999), “A Tabu Search Heuristic For The Heterogeneous Fleet
Vehicle Routing Problem”, Computers & Operations Research Vol.26,1153-1173.
[78] B.Gillett and L.R. Miller(1974), “A Heuristic Algorithm for the Vehicle Dispatch Problem”,
Operations Research 22, 340?349.
[79] F.Glover (1986), ”Future Paths for Integer Programming and Links to Artificial Intelligence”,
Computers and Operations Research 13, 533?549.
[80] F.Glover(1992), ”New Ejection Chain and Alternating Path Methods for Traveling Salesman
Problems”, in Computer Science and Operations Research: New Developments in Their Interfaces,
O. R. Balci Sharda, and S. Zenios (eds), 449?509, Pergamon Press, Oxford.
[81] B.L.Golden and A.A. Assad(1986), “Perspectives on Vehicle Routing: Exciting New
Developments”, Operations Research 34, 803?809.
[82] B.L.Golden and E.A. Wasil(1987), “Computerized Vehicle Routing In The Soft Drink
Industry”, Operations Research35:6-17.
[83] M.Guignard and S.Kim(1987), “Lagrangian Decomposition: A Model Yielding Stronger
Lagrangean Bounds”, MaThematical Programming39:215-228.
[84] K.Halse (1992), “Modeling and Solving Complex Vehicle Routing Problems”, Ph. D. thesis,
Institute of Mathematical Modelling, Technical University of Denmark, Lyngby, Denmark.
[85] A.Hamacher and C. Moll, “A New Heuristic for Vehicle Routing with Narrow Time
Windows”, in Operations Research Proceedings 1996, Selected papers of the symposium
(SOR`96), Braunschweig, Germany, September 3-6th, U. Derigs, W. Gaul, R H. M?hring and K.-P.
Schuster (eds), 301?306, Springer Verlag, New York.
[86] J.Homberger and H.Gehring(1999), “Two Evolutionary Metaheuristics For The Vehicle
Routing Problem With Time Windows”, INFOR37:297-318.
[87] J.Homberger and H. Gehring(2001), “A Parallel Two-Phase Metaheuristic To Routing
Problem with Time Windows”, Asia-Pacific Journal of Operational Research, Vol.18, 35-47.
[88] S.C.Hong and Y.B.Park(1999), “A Heuristic for Bi-objective Vehicle Routing with Time
Window Constraints”, International Journal of Production Economics 62, 249?258.
[89] T.Ibaraki, S. Imahori, M. Kubo, T. Masuda, T. Uno and M. Yagiura(2002), ”Effective Local
Search Algorithms for the Vehicle Routing Problem with General Time Window Constraints”,
Working paper, Department of Applied Mathematics and Physics, Kyoto University, Japan.
[90] S.Ichoua, M.Gendreau and J-Y Potvin(2000), ” Diversion Issues In Real-time Vehicle
Dispatching”, Transportation Science34:426-438.
[91] G.Ioannou, M.Kritikos and G.Prastacos(2001), “A Greedy Look-ahead Heuristic For The
Vehicle Routing Problem With Time Windows”, Journal of The Operational Research Society52,
523-537.
[92] G.Ioannou, M.N.Kritikos and G.P.Prastacos(2002), ”Map-Route: A GIS-based Decision
Support System For Intra-city Vehicle Routing With Time Windows”, Journal of Operational
Research Society53:842-854.
[93] B.Jozsef, G.Gabor and H.Peter(2000), “Analysis of Permutation Routing Algorithms”,
117
参考文献
European Journal of Operational Research Vol.125,P249.
[94] S.Jung and B.-R. Moon(2002), “A Hybrid Genetic Algorithm for the Vehicle Routing
Problem with Time Windows”, in Proceedings of Genetic and Evolutionary Computation
Conference, 1309?1316, Morgan Kaufmann, San Francisco.
[95] J.Jysgaard(1992), “Dynamic Transportation Networks in Vehicle Routing and Scheduling”,
Interfaces 22:3,45-55..
[96] P.Kilby, P. Prosser and P. Shaw (1999), ”Guided Local Search for the Vehicle Routing
Problem with Time Windows”, in META-HEURISTICS Advances and Trends in Local Search
Paradigms for Optimization, S. Voss, S. Martello, I.H. Osman and C. Roucairol (eds), 473?486,
Kluwer Academic Publishers, Boston.
[97] G.F.King and C.F. Mast (1997), “Excess Travel: Causes, Extent and Consequences”,
Transportation Research Record 1111, 126?134.
[98] N.Kohl and OBG Madsen(1997), “An Optimization Algorithm For The Vehicle Routing
Problem With Time Windows Based On Lagrangian Relaxation”, Operations Research 45:
395-406.
[99] AWJ Kolen, Kan AHG Rinnooy and HWJM Trienekens(1987), “Vehicle Routing With Time
Windows”, Operations Research35:266-273.
[100] G.Kontoravdis and J.Bard, “A GRASP For The Vehicle Routing Problem With Time
Windows”, Journal on Computing 7, 10?23.
[101] I.A.Koskosidis, W.B.Powell and M.Solomon(1992), “An Optimization-Based Heuristic For
Vehicle Routing And Scheduling With Time Windows Constraints”, Transportation
Science26(2):69-85.
[102] G.Laporte(1992), “The Traveling Salesman Problem:An Overview of Exact And
Approximate Algorithms”, European Journal of Operational Research59:231-248.
[103] G.Laporte(1992), “The Vehicle Routing Problem: An Overview of Exact And Approximate
Algorithms”, European Journal of Operational Research59:345-358.
[104] G.Laporte and I.H.Osman(1995), “Routing Problems: A Bibliography”, Annals of
Operations Research61:227-262.
[105] J.Larsen (1999), Parallelization of the Vehicle Routing Problem with Time Windows, Ph.D.
thesis, Institute of Mathematical Modelling, Technical University of Denmark, Lyngby, Denmark.
[106] H.C.Lau, M. Sim and K.M. Teo (2003), “Vehicle Routing Problem with Time Windows and
a Limited Number of Vehicles”, European Journal of Operational Research Vol.148, P559.
[107] KJ Lenstra and K.A.Rinnooy(1981), “Complexity of Vehicle Routing And Scheduling
Problems”, Networks11:221-227.
[108] H.Li, A.Lim, J.Huang (2003), ”Local Search with Annealing-like Restarts to solve the
VRPTW”, To Appear in European Journal of Operational Research Vol.150, P115.
[109] S.Lin(1965), “Computer Solutions of the Traveling Salesman Problem”, Bell System
Technical Journal 44, 2245?2269.
[110] F-H Liu and S-Y Shen(1999), “The Fleet Size and Mix Vehicle Routing Problem With Time
Windows”, The Journal of The Operational Research Society50,P721 .
[111] F.F.Liu, S.Y.Shen(1999), “A Route-neighborhood-based Metaheuristic For Vehicle Routing
Problem With Time Windows”, European Journal of The Operational Research 52, 485-504.
[112] R.O.Mason, J.L.Mckenney, W.Carlson and D.Copeland(1997), “Absolutely, Positively
Operations Research: The Federal Express Story”, Interfaces 27:2, 17-36,
118
参考文献
[113] D.Mester (2002), “An Evolutionary Strategies Algorithm for Large Scale Vehicle Routing
Problem with Capacitate and Time Window Restrictions”, Working Paper, Institute of Evolution,
University of Haifa, Israel.
[114] H.Min(1989), “The Multiple Vehicle Routing Problem With Simultaneous Delivery And
Pick-up Points” Transportation Research23:377-386.
[115] G.Mosheiov(1994), “The Traveling Salesman Problem With Pick-up And Delivery”,
European Journal of Operational Research79:299-310.
[116] M.C.Mourao and M.T.Almeida(2000), “Lower-bounding And Heuristic Methods For A
Refuse Collection Vehicle Routing Problem”, European Journal of Operational
Research121(2):420-434.
[117] H.Paessens(1988), “The Savings Algorithm For The Vehicle Routing Problem”, European
Journal Operational Research34:336-344.
[118] T.Paolo And V.Daniele(1999), “A Heuristic Algorithm For The Symmetric And Asymmetric
Vehicle Routing Problems With Backhauls”, European Journal of Operational
Research113(3):528-543.
[119] A.Poot, G.Kant and APM Wagelmans(2002), “A Savings Based Method For Real-life
Vehicle Routing Problems”, Journal of Operational Research Society53:57-68.
[120] J.Y.Potvin and J.M.Rousseau(1993), “A Parallel Route Building Algorithm For The Vehicle
Routing And Scheduling Problem With Time Windows”, European Journal of Operational
Research66:331-340.
[121] J.Y.Potvin and J.M Rousseau(1995), “An Exchange Heuristic For Routing Problems With
Time Windows”, Journal of Operational Research Society46:1433-1446.
[122] J.Y.Potvin, S.Bengio(1996), “The Vehicle Routing Problem With Time Windows Part II:
Genetic Search”, INFORMS J. Comp. 8:165-172.
[123] J.Y.Potvin, T.Kervahut, BL Garcia and JM Rousseau(1996), “The Vehicle Routing Problem
With Time Windows Part I: Tabu Search”, INFORMS J. Comp. 8:158-164.
[124] W.Powell(1995), "Stochastic and Dynamic Networks and Routing," Handbook in
Operations Research and Management Science, Vol. 4, Networks, (M.O. Ball, T.L. Magnanti, C.L.
Monma and G.L. Nemhauser, eds.), pp. 141-295, (with A.R. Odoni and P. Jaillet).
[125] P.Prosser and P. Shaw (1996), “Study of Greedy Search with Multiple Improvement
Heuristics for Vehicle Routing Problems”, Working Paper, University of Strathclyde, Glasgow,
Scotland.
[126] C.Rego(1998), “A Subpath Ejection Method For The Vehicle Routing Problem”,
Management Science44:1447-1459.
[127] J.Renaud, F.F.Boctor and G.Laporte(1996), “An Improved Petal Heuristic For The Vehicle
Routing Problem”, Annals of Operations Research47(2):329-336.
[128] J.Renaud and F.F.Boctor(2002), “A Sweep-based Algorithm For The Fleet Size and Mix
Vehicle Routing Problem”, European Journal of Operational Research140:618-628.
[129] Y. Rochat and E. Taillard (1995), ”Probabilistic Diversification and Intensification in Local
Search for Vehicle Routing”, Journal of Heuristics 1, 147?167.
[130] D.Ronen(1988), “Perspectives On Practical Aspects of Trunk Routing And Scheduling”,
European Journal of Operational Research35:137-145.
[131] R.Russell (1977), “An Effective Heuristic for the M-tour Traveling Salesman Problem with
Some Side Conditions”, Operations Research 25, 517?524.
119
参考文献
[132] R.Russell(1995), “Hybrid Heuristics For The Vehicle Routing Problem With Time
Windows”, Transportation Science29:156-166.
[133] S.Salhi and G.Nagy(1999), “A Cluster Insertion Heuristic For Single and Multiple Depot
Vehicle Routing Problems With Backhauling”, Journal of The Operational Research
Society50:1034-1042.
[134] J.K.Sankaran and R.R.Ubgade(1994), “Routing Tankers for Dairy Milk Pickup”, Interfaces
24:5, 59-66,
[135] MWP Savelsbergh(1985), “Local Search For Routing Problems With Time Windows”,
Annals of Operational Research4:285-305.
[136] MWP Savelsbergh(1990), “An Efficient Implementation Of Local Search Algorithms For
Constrained Routing Problems”,European Journal of Operationan Research47:75-85.
[137] L.Schrage(1981), “Formulation And Structure of More Complex/Realistic Routing And
Scheduling Problems”, Networks11:229-232.
[138] J. Schulze and T. Fahle (1999), ”A Parallel Algorithm for the Vehicle Routing Problem with
Time Window Constraints”, Annals of Operations Research 86, 585?607.
[139] F.Semet and E.D.Taillard(1993), “Solving Real-life Vehicle Routing Problems Efficiently
Using Tabu Search”, Annals of Operations Research41:469-481.
[140] P.Shaw (1997), “A New Local Search Algorithm Providing High Quality Solutions to
Vehicle Routing Problems”, Working Paper, Department of Computer Science, University of
Strathclyde, Glasgow, Scotland.
[141] M.M.Solomon(1986), “On the Worst-Case Performance of Some Heuristics for the Vehicle
Routing and Scheduling Problem with Time Window Constraints”, Networks 16, 161?174.
[142] M.M.Solomon(1987), “Algorithms For The Vehicle Routing And Scheduling Problems With
Time Windows Constraints”, Operations Research35:254-265.
[143] M.M.Solomon and J. Desrosiers (1988), “Time Window Constrained Routing and
Scheduling Problems”, Transportation Science 22, 1?13.
[144] W.R.Stewart and B.L.Golden(1984), “A Lagrangian Relaxation Heuristic For Vehicle
Routing”, European Journal of Operational Research15:84-88.
[145] C.S.Sung and J.M.Hong(1999), “Branch-And-Price Algorithm For Multicast Routing
Problem”, The Journal of The Operational Research Society50, P1168.
[146] E.Taillard(1993), “Parallel Iterative Search Methods For Vehicle Routing Problems”,
Networks23:661-673.
[147] E.Taillard et al(1997), “A Tabu Search Heuristic For The Vehicle Routing Problem With
Soft Time Windows”, Transportation Science31:170-186.
[148] K.C.Tan, L.H. Lee and K.Q. Zhu (2000), ”Heuristic Methods for Vehicle Routing Problem
with Time Windows”, in Proceedings of the 6th International Symposium on Artificial Intelligence
& Mathematics, Ft. Lauderdale, Florida.
[149] K.C.Tan, T.H. Lee, K. Ou and L.H. Lee (2001), “A Messy Genetic Algorithm for the Vehicle
Routing Problem with Time Window Constraints”, in Proceedings of the 2001 Congress on
Evolutionary Computation, 679?686, IEEE Service Center, Pistacaway.
[150] K.C.Tan, T.H. Lee, K. Ou and L.H. Lee (2001b), “A Messy Genetic Algorithm for the
Vehicle Routing Problem with Time Window Constraints”, in Proceedings of the 2001 Congress
on Evolutionary Computation, 679?686, IEEE Service Center, Pistacaway.
[151] K.C.Tan, L. H. Lee and K. Ou (2001a), ”Hybrid Genetic Algorithms in Solving Vehicle
120
参考文献
Routing Problems with Time Window Constraints”, Asia-Pacific Journal of Operational Research
18, 121?130.
[152] S.R.Thangiah, K.E. Nygard and P.L. Juell (1991), “GIDEON: A Genetic Algorithm System
for Vehicle Routing with Time Windows”, in Proceedings of Seventh IEEE Conference on
Artificial Intelligence Applications, 322?328, IEEE Computer Society Press, Los Alamitos.
[153] S.R.Thangiah (1995a), ”Vehicle Routing with Time Windows Using Genetic Algorithms”, in
Application Handbook of Genetic Algorithms: New Frontiers, Volume II, L. Chambers (ed),
253?277, CRC Press, Boca Raton.
[154] P. M.Thompson and H.N. Psaraftis (1993), “Cyclic Transfer Algorithms for Multivehicle
Routing and Scheduling Problems”, Operations Research 41, 935?946.
[155] B.S.Vaidyanathan, J.O.Matson, D.M.Miller and J.E.Matson(1999), “A Capacitated Vehicle
Routing Problem For Just-in-time Delivery”, IEE Transaction 31,1083-1092.
[156] Van Landeghem, H.R.G. (1988), “A Bi-criteria Heuristic for the Vehicle Routing Problem
with Time Windows”, European Journal of Operations Research 36, 217?226.
[157] A.V.Vliet, C.G.E.Boender and A.H.G.R.Kan(1992), “Interactive Optimization of Bulk Sugar
Deliveries”,Interfaces 22:3,4-14.
[158] J.Wahle, O.Annen, C.Schuster, L.Neubert and M.Schreckendberg(2001), “A Dynamic Route
Guidance System Based On Real Traffic Data”, European Journal of Operations
Research131-132:74-80.
[159] P.Wark and J.Holt(1994), “A Repeated Matching Heuristic For The Vehicle Routing
Problem”, Journal of Operations Research Society45:1156-1167.
[160] N.A.Wassan and I.H.Osman(2002), “Tabu Search Variants For The Mix Fleet Vehicle
Routing Problem”, The Journal of The Operational Research Society53:768-782.
[161] H. Wee Kit, J. Chin and A. Lim (2001), ”A Hybrid Search Algorithm for the Vehicle Routing
Problem with Time Windows”, International Journal on Artificial Intelligence Tools 10, 431?449.
[162] D.Weigel and B.Cao(1999), “Applying GIS and OR Techniques to Solve Sears
Technician-Dispatching and Home-Delivery Problems”,Interfaces 29:1,112-130.
[163] T-H Wu , C.Low and J-W Bai(2002), “Heuristic Solutions To Multi-depot Location-routing
Problems”, Computers & Operations Research29:1393-1415.
[164] 邢文训、谢金星,“现代优化计算方法”,清华大学出版社,1999 年版.