The vehicle routing path (VRP) is non-deterministic polynomial-time hard (NP-hard) and therefore difficult to solve. The fact that VRP is both of theoretical and practical interest (owing to its real-world applications), explains the amount of attention given to the VRP by researchers during past years. Research on the development of heuristics for the VRP has made considerable progress since the first algorithms were proposed in the early 1960s. Several families of heuristics have been proposed for the VRP. The purpose of this paper is to review some of the most important families of heuristics for the VRP. At the end, the survey presents the solution method used for a small-scale case study in a logistic company in Turkey.
TsengY. Y.YueW. L.TaylorM. A. P.The role of transportation in logistics chain. Proc. East. Asia Soc. Transpn Stud., 2005, 5, 1657–1672.
3.
MachadoP.TavaresJ.PereiralF.CostaE.Vehicle routing problem: Doing it the evolutionary way. In GECCO: Proceedings of the Genetic and evolutionary computation conference 2002, USA, 9–13 July 2002, p. 690.
4.
BeckJ. C.ProsserP.SelenskyE.On the reformulation of vehicle routing problems and scheduling problems. Technical Report APES-442002, 2002 (APES Research Group).
5.
FisherM. L.Optimal solution of vehicle routing problems using minimum K-trees. Operations Res., 1994, 42, 626–642.
LysgaardJ.LetchfordA. N.EgleseR. W.A new branch-and-cut algorithm for capacitated vehicle routing problems. Math Program, 2004, Ser. A100, 423–445.
8.
AlbaE.DorronsoroB.Computing nine new best-so-far solutions for capacitated VRP with a cellular genetic algorithm. Inf. Processing Lett., 2005, 98, 225–230.
9.
MoghaddamR. T.SafaeiN.GholipourY.A hybrid simulated annealing for capacitated vehicle routing problems with the independent route length. Appl. Math Comput., 2006, 176, 445–454.
KindervaterG. A. P.SavelsberghM. W. P.Vehicle routing: Handling edge exchanges. In Local search in combinatorial optimization (Eds AartsE. H.LenstraJ. K.), 1997, pp. 311–336 (Wiley, Chichester).
12.
MukaiN.FengJ.WatanabeT.Heuristic approach based on lambda-interchange for VRTPR-tree on specific vehicle routing problem with time windows. Ind. Engng Applic. Artif. Intell. Expert Syst., 2004, 3029, 224.
13.
RenaudJ.BoctorF. F.A sweep-based algorithm for the fleet size and mix vehicle routing problem. Eur. J. Opl Res., 2002, 140, 618–628.
14.
MontemanniR.BartaJ.GambardellaL. M.Heuristic and preprocessing techniques for the robust traveling salesman problem with interval data. Technical Report IDSIA-01-06, 2006 (Istituto Dalle Molle di Studi Sull'Intelligenza Arlificiale).
15.
GronaltM.HartlR. F.ReimannM.New savings based algorithms for time constrained pickup and delivery of full truckloads. Eur. J. Opl Res., 2003, 151, 520–535.
16.
RochatY.Taillardã%. D.Probabilistic diversification and intensification in local search for vehicle routing. J. Heuristics, 1995, 1, 147–167.
17.
XuJ.KellyJ.A network flow-based tabu search heuristic for the vehicle routing problem. Transpn Sci., 1996, 30, 379–393.
18.
Taillardã%. D.BadeauP.GendreauM.GuertinF.PotvinJ.-Y.A tabu search heuristic for the vehicle routing problem with soft time windows. Transpn Sci., 1997, 31, 170–186.
19.
ArchettiC.SperanzaM. G.A tabu search algorithm for the split delivery vehicle routing problem. Transpn Sci., 2006, 40, 64–73.
20.
AlfredoF.MontaneT.GalvaoR. D.A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service. Comput. Ops Res., 2006, 33, 595–619.
21.
TothP.VigoD.The granular tabu search (and its application to the vehicle routing problem). Technical Report, 1998 (Dipartimento di Elettronica, Informatica e Sistemistica, Universitã di Bologna, Italy).
22.
ShawP.Using constraint programming and local search methods to solve vehicle routing problems. In Proceedings of the Fourth International Conference on Principles and practice of constraint programming (CP '98) (Ed. MaherM.PugetJ.-F.) 1998, pp. 417–431, (Springer-Verlag).
23.
RousseauM.GendreauM.PesantG.FocacciF.Solving VRPTWs with constraint programming based column generation. Ann. Operation Res., 2004, 130, 199–216.
24.
GambardellaL. M.TaillardE.AgazziG.MACSVRPTW: A multiple ant colony system for vehicle routing problems with time windows. In New ideas in optimization (Eds CorneD.DorigoM.GloverF.), 1999, pp. 63–76. (McGraw-Hill, London).
25.
MazzeoS.LoiseauI.An ant colony algorithm for the capacitated vehicle routing. Electronic Notes in Discrete Math., 2004, 18, 181–186.
26.
ReimannM.DoernerK.HartlR. F.D-ants: Savings based ants divide and conquer the vehicle routing problem. Comput. Ops Res., 2004, 31, 563–59.
27.
LaporteG.PalekarU.Some applications of the clustered traveling salesman problem. J. Opl Res. Soc., 2002, 53, 972–976.
28.
LaporteG.Asef-VaziriA.SriskandarajahC.Some applications of the generalized traveling salesman problem. J. Opl Res. Soc., 1996, 47, 1461–1467.
29.
BlaisM.LaporteG.Exact solution of the generalized routing problem through graph transformation. J. Opl Res. Soc., 2003, 54, 906–910.
30.
OppenJ.LokketangenA.Arc routing in a node routing environment. Comput. Ops Res., 2006, 33, 1033–1055.
31.
ThangiahS. R.Vehicle routing with time windows using genetic algorithms. In Application and book of genetic algorithms: New frontiers (Ed. ChambersL.), 1995, Vol. 2, pp. 253–277 (CRC Press, Boca Raton).
32.
ZhuK.A new genetic algorithm for VRPTW. In Proceedings of International Conference on Artificial intelligence, 2000, Las Vegas, USA.
33.
LouisS.YinX.YuanZ.Multiple vehicle routing with time windows using genetic algorithms. In Proceedings of the Congress on Evolutionary computation, 1999, pp. 1804–1808.
34.
HolmbergK.YuanD.A Lagrangian heuristic based branch-and-bound approach for the capacitated network design problem. Ops Res., 2000, 48(3), 461–481.
35.
CordeauJ.-F.SoumisF.DesrosiersJ.A Benders decomposition approach for the locomotive and car assignment problem. Transpn Sci., 2000, 34(2), 133–149.
36.
YanoC.NewmanA. M.Scheduling trains and containers with due dates and dynamic arrivals. Transpn Sci., 2001, 35(2), 181–191.
37.
BallouR.Business logistics management, planning, organizing and controlling the supply chain, 4th Edition, 1999 (Prentice Hall, Englewood Cliffs, New Jersey).
