In this paper, we have conducted a literature review on the recent developments and publications involving the vehicle routing problem and its variants, namely vehicle routing problem with time windows (VRPTW) and the capacitated vehicle routing problem (CVRP) and also their variants. The VRP is classified as an NP-hard problem. Hence, the use of exact optimization methods may be difficult to solve these problems in acceptable CPU times, when the problem involves real-world data sets that are very large. The vehicle routing problem comes under combinatorial problem. Hence, to get solutions in determining routes which are realistic and very close to the optimal solution, we use heuristics and meta-heuristics. In this paper we discuss the various exact methods and the heuristics and meta-heuristics used to solve the VRP and its variants.
G. Dantzig and J. Ramser, “The Truck Dispatching Problem,” Management Science, Vol. 6, No. 1, 1959, pp. 80-91. doi:10.1287/mnsc.6.1.80
G. Clarke and J. R. Wright, “Scheduling of Vehicle Routing Problem from a Central Depot to a Number of Delivery Points,” Operations Research, Vol. 12, No. 4, 1964, pp. 568- 581. doi:10.1287/opre.12.4.568
G. Laporte, “The Vehicle Routing Problem: An Overview of Exact and Approximate Algorithms,” European Journal of Operational Research, Vol. 59, No. 3, 1992, pp. 345-358. doi:10.1016/0377-2217(92)90192-C
M. Gendreau, G. Laporte and J.-Y. Potvin, “Metaheuristics for the VRP,” In: P. Toth and D. Vigo, Eds., The Vehicle Routing Problem, SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, 2002, pp. 129-154. doi:10.1137/1.9780898718515.ch6
J.-F. Cordeau, M. Gendreau, A. Hertz, G. Laporte and J. S. Sormany, “New Heuristics for the Vehicle Routing Problem,” In: A. Langevi and D. Riopel, Eds., Logistics Systems: Design and Optimization, Springer, New York, 2005, pp. 279-297. doi:10.1007/0-387-24977-X_9
M. Solomon, “Algorithms for the Vehicle Routing and Scheduling Problem with Time Window Constraints,” Operations Research, Vol. 35, No. 2, 1987, pp. 254-265. doi:10.1287/opre.35.2.254
F. M. Andres, “An Iterative Route Construction and Improvement Algorithm for the Vehicle Routing Problem with Soft Time Windows,” Transportation Research Part B, Vol. 43, No. 4, 2010, pp.438-447.
P. Toth and D. Vigo, “An Overview of Vehicle Routing Problems,” SIAM Monographs on Discrete Mathematics and Applications, 2002, pp.1-26. doi:10.1137/1.9780898718515.ch1
R. Baldacci, E. Hadjiconstantinou and A. Mingozzi, “An Exact Algorithm for the Capacitated Vehicle Routing Problem Based on a Two-Commodity Network Flow Formulation,” Operations Research, Vol. 52, No. 5, 2004, pp. 723- 738. doi:10.1287/opre.1040.0111
J. K. Lenstra and A. H. G. Rinnooy Kan, “Complexity of Vehicle and Scheduling Problems,” Networks, Vol. 11, No. 2, 1981, pp. 221-227. doi:10.1002/net.3230110211
J. Homberger and H. Gehring, “A Two-Phase Hybrid Meta-Heuristic for the Ve-hicle Routing Problem with Time Windows,” European Jour-nal of Operational Research, 2005, Vol. 162, No. 1, pp. 220-238. doi:10.1016/j.ejor.2004.01.027
J.-Y. Potvin, T. Kervahut, B.-L. Garcia and J.-M. Rousseau, “The Vehicle Routing Problem with Time Windows Part I: Tabu Search,” INFORMS Journal on Computing, Vol. 8, No. 2, pp. 158- 164. doi:10.1287/ijoc.8.2.158
E. Taillard, P. Badeau, M. Gendreau, F. Guertin and J.-Y. Potvin, “A Tabu Search Heuristic for the Vehicle Routing Problem with Soft Time Windows,” Transportation Sci- ence, Vol. 31, No. 2, 1997, pp. 170-186. doi:10.1287/trsc.31.2.170
W. C. Chiang and R. Russell, “Simulated Annealing Meta-Heuristics for the Vehicle Routing Problem with Time Windows,” Annals of Operations Research, Vol. 93, No. 1, 1996, pp. 3-27. doi:10.1007/BF02601637
S. R. Thangiah, K. E. Nygard and P. L. Juell, “GIDEON: A Genetic Algorithm System for Vehicle Routing with Time Windows,” Proceedings of the Seventh IEEE Conference on Artificial Intelligence Applications, Miami Beach, 24-28 February 1991, pp. 322-328. doi:10.1109/CAIA.1991.120888
J.-Y. Potvin and S. Bengio, “The Vehicle Routing Problem with Time Windows Part II: Genetic Search,” INFORMS Journal on Computing, Vol. 8, No. 2, 1996, pp. 165-172. doi:10.1287/ijoc.8.2.165
J. Homberger and H. Gehring, “Two Evolutionary Meta-Heuristics for the Vehicle Routing Problem with Time Windows: Meta-Heuristics for Location and Routing Problems,” Information Systems and Operational Research (Special issue), Vol. 37, 1999, pp. 297-318.
P. Shaw, “Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems,” Principles and Practice of Constraint Programming—CP98, Lecture Notes in Computer Science, Springer-Verlag, New York, 1998, pp. 417-431.
P. Kilby, P. Prosser and P. Shaw, “Guided Local Search for the Vehicle Routing Problems with Time Windows: Meta-heuristics: Advances and Trends in Local Search for Op-timization,” Academic Publishers, Boston, 1999, pp. 473-486.
S. Masrom, A. M. Nasir, Siti. Z. Z. Abidin and A. S. A. Rahman, “Software Framework for Vehicle Routing Problem with Hybrid Metaheuristic Algorithms,” Proceedings of the Applied Computing Conference, Angers, 17-19 November 2011, pp. 55-61.
G. Kontoravdis and J. Bard, “A GRASP for the Vehicle Routing Problem with Time Windows,” INFORMS Journal of Computing, Vol. 7, No. 1, 1995, pp. 10-23. doi:10.1287/ijoc.7.1.10
F.-H. Liu and S.-Y. Shen, “The Fleet Size and Mix Vehicle Routing Problem with Time Windows,” Journal of the Operational Research Society, Vol. 50, No. 7, 1999, pp. 721- 732.
L. M. Gambardella, E. Taillard and G. Agazzi, “MACS- VRPTW: A Multiple Ant Colony Sys-tem for Vehicle Routing Problems with Time Windows New: Ideas in Optimization,” McGraw-Hill, London, 1999.
S. Ropke, J.-F. Cordeau, M. Iori and D. Vigo, “Branch-and-Cut-and-Price for the Capacitated Vehicle Routing Problem with Two-Dimensional Loading Constraints,” Proceedings of ROUTE, Jekyll Island, 13 May 2007.
G. Gutiérrez-Jarpa, G. Desaulniers, G. Laporte and V. Marianov, “A Branch-and-Price Algorithm for the Vehicle Routing Problem with Deliveries, Selective Pickups and Time Windows,” European Journal of Operational Research, Vol. 206, No. 12, 2010, pp. 341-349. doi:10.1016/j.ejor.2010.02.037
N. Azi, M. Gendreau and J.-Y. Potvin, “An Exact Algorithm for a Vehicle Routing Problem with Time Windows and Multiple Use of Vehicles,” European Journal of Operational Research, Vol. 202, No. 3, 2010, pp. 756-763. doi:10.1016/j.ejor.2009.06.034
A. G. Qureshi, E. Taniguchi and T. Yamada, “An Exact Solution Approach for Vehicle Routing and Scheduling Problems with Soft Time Windows,” Transportation Research Part E: Logistics and Transportation Review, Vol. 45, No. 6, 2009, pp. 960-977. doi:10.1016/j.tre.2009.04.007
M. L. Ballinski and R. E. Quandt, “On Integer Program for a Delivery Problem,” Operations Research, Vol. 12, No. 2, 1964, pp. 300-304. doi:10.1287/opre.12.2.300
Y. Agarwal, K. Mathur and H. M. Salkin, “A set-partitioning-based algorithm for the vehicle routing problem,” Networks, Vol. 19, No. 7, 1989, pp. 731-749. doi:10.1002/net.3230190702
G. Laporte, “Fifty Years of Vehicle Routing,” Transportation Science, Vol. 43, No. 4, 2009, pp. 408-416.
G. B. Alvarenga, G. R. Mateus and G. de Tomi, “A Genetic and Set Partitioning Two-Phase Approach for the Vehicle Routing Problem with Time Windows,” Computers and Operations Research, Vol. 34, No. 6, 2007, pp. 1561-1584. doi:10.1016/j.cor.2005.07.025
N. Christofides, A. Min-gozzi and P. Toth, “Exact algorithm for the Vehicle Routing Problem Based on Spanning Tree and Shortest Paths Relaxations,” Mathematical Programming, Vol. 20, No. 1, 1981, pp. 255-282. doi:10.1007/BF01589353
F. J. Bard, G. Kontoravdis and G. Yu, “A Branch-and-Cut Procedure for the Vehicle Routing Problem with Time Windows,” Transportation Science, Vol. 36, No. 2, 2002, pp. 250-269. doi:10.1287/trsc.36.2.250.565
M. Fisher and R. Jaikumar, “A Generalized Assignment Heuristic for Vehicle Routing,” Networks, Vol. 11, No. 2, 1981, pp. 109-124. doi:10.1002/net.3230110205
B. M. Baker and J. Sheasby, “Extensions to the Generalised Assignment Heuristic for Vehicle Routing,” European Journal of Operational Research, Vol. 119, No. 1, 1999, pp. 147-157. doi:10.1016/S0377-2217(98)00348-8
M. Gandreau, F. Guertin, J.-Y. Potvin and R. Seguin, “Neighborhood Search Heuristics for a Dynamic Vehicle Dis- patching Problem with Pick-Ups and Deliveries,” Transportation Research Part E: Logistics and Transportation Review, Vol. 14, No. 3, 2006, pp. 157-174.
X. Chen, W. S. Wan and X. H. Xu, “The Real-Time Time-Dependent Vehicle Routing Problem,” Transportation Research Part E: Logistics and Transportation Re- view, Vol. 42, No. 5, 2006, pp. 383-408. doi:10.1016/j.tre.2005.01.003
N. Yuichi and B. Olli, “A Powerful Route Minimization Heuristic for the Vehicle Routing Problem with Time Windows,” Operations Research Letters, Vol. 37, No. 5, 2009, pp. 333-338. doi:10.1016/j.orl.2009.04.006
K.-W. Peng, “An Adaptive Parallel Route Construction Heuristic for the Vehicle Routing Problem with Time Windows Constraints,” Expert Systems with Applications, Vol. 38, No. 9, 2011, pp. 11939-11946.
B. Patr?cia, T. Hugo and Y. Yoshida, “Scatter Search for a Real-Life Heterogeneous Fleet Vehicle Routing Problem with Time Windows and Split Deliveries in Brazil,” European Journal of Operational Research, Vol. 199, 2009, pp. 750-758. doi:10.1016/j.ejor.2008.08.003
J. L. Blanton and R. L. Wainwright, “Multiple Vehicle Routing with Time and Capacity Constraints Using Genetic Algorithms,” Proceedings of the Fifth International Conference on Genetic Algorithms, San Francisco, 17 July 1993, pp. 452-459.
J. Berger, M. Salois and R. A. Begin, “Hybrid Genetic Algorithm for the Vehicle Routing Problem with Time Windows,” Lecture Notes in Artificial Intelligence 1418, Springer, Berlin, 1998, pp. 114-127.
S. R. Thangiah, I. H. Osman and T. Sun, “Hybrid Genetic Algorithms, Simulated Annealing and Tabu Search Methods for Vehicle Routing Problems with Time Windows,” Technical Report UKC/OR94/4, Institute of Mathematics and Statistics, University of Kent, Canterbury, 1995.
H. Wee Kit, J. Chin and A. Lim, “A Hybrid Search Algo- rithm for the Vehicle Routing Problem with Time Windows,” International Journal on Artificial Intelligence Tools, Vol. 10, No. 3, 2001, pp. 431-449. doi:10.1142/S021821300100060X
J. Berger, Barkaoui, M. and Br?ysy, O. A, “Route-directed Hybrid Genetic Approach for the Vehicle Routing Problem with Time Windows,” INFOR, Vol. 41, No. 2, 2003, pp. 179-194.
C. L. Hoong, M. Sim and K. M. Teo, “Vehicle Routing Problem with Time-Windows and a Limited Number of Vehicles,” European Journal of Operational Research, Vol. 148, No. 3, 2003, pp. 559-569. doi:10.1016/S0377-2217(02)00363-6
R. Montemanni, L. M. Gambardella, A. E. Rizzoli and A. V. Donati, “Ant Colony System for a Dynamic Vehicle Routing Problem,” Journal of Combinatorial Optimization, Vol. 10, No. 4, 2005, pp. 327-343. doi:10.1007/s10878-005-4922-6
Y.-J. Cho and S.-D. Wang, “A Threshold Accepting Meta- Heuristic for the Vehicle Routing Problem with Backhauls and Time Windows,” Journal of the Eastern Asia Society for Transportation Studies, Vol. 6, 2005, pp. 3022- 3037. http://www.easts.info/on-line/journal_06.htm
E. Alba and B. Dorronsoro, “The Exploration/Exploitation Tradeoff in Dynamic Cellular Genetic Algorithms,” IEEE Transactions on Evolutionary Computation, Vol. 9, No. 2, 2005, pp. 126-142. doi:10.1109/TEVC.2005.843751
A. Le Bouthillier and T. G. Crainic, “A Cooperative Parallel Meta-Heuristic for the Vehicle Routing Problem with Time Windows,” Computers & Operations Research, Vol. 32, No. 7, 2005, pp. 1685-1708. doi:10.1016/j.cor.2003.11.023
X. Zhang and L. Tang, “A New Hybrid Ant Colony Optimization Algorithm for the Vehicle Routing Problem,” Pattern Recognition Letters, Vol. 30, No. 9, 2009, pp. 848- 855.
M. David and O. Br?ysy, “Active Guided Evolution Strategies for Large-Scale Vehicle Routing Problems with Time Windows,” Computers & Operations Re-search, Vol. 32, No. 6, 2005, pp. 1593-1614. doi:10.1016/j.cor.2003.11.017
R. A. Russell and W.-C. Chiang, “Scatter Search for the Vehicle Routing Problem with Time Windows,” European Journal of Operational Research, Vol. 169, No. 2, 2006, pp. 606-622. doi:10.1016/j.ejor.2004.08.018
C. Benoit., J.-F. Cordeau and G. Laporte, “The Multi-Depot Vehicle Routing Problem with Inter-Depot Routes,” European Journal of Operational Research, Vol. 176, No. 2, 2007, pp. 756-773. doi:10.1016/j.ejor.2005.08.015
G.-N. Abel and Bullinaria John A, “An Improved Multi-Objective Evolutionary Algorithm for the Vehicle Routing Problem with Time Windows,” Computers & Operations Research, Vol. 38, No. 1, 2011, pp. 287-300. doi:10.1016/j.cor.2010.05.004
E. Aziz, “An Algorithm for the Vehicle Problem () International Journal of Advanced Robotic Systems,” Vol. 7, No. 2, 2010, pp.125-132.
Yu Bin, Yang Zhong Zhen, “An ant colony optimization model: The period vehicle routing problem with time windows,” Transportation Research Part E, Vol. 47, 2011, pp.166–181. doi:10.1016/j.tre.2010.09.010
Balseiro, S.R., Loiseau. I. and Ramone. J, “An Ant Colony algorithm hybridized with insertion heuristics for the Time Dependent Vehicle Routing Problem with Time Windows,” Computers & Operations Re-search, Vol. 38, 2011, pp. 954-966. doi:10.1016/j.cor.2010.10.011
De Backer, B. and Furnon, V, “Meta-heuristics in Constraint Programming Experiments with Tabu Search on the Vehicle Routing Problem,” Proceedings of the Second International Conference on Meta-heuristics (MIC’97), Sophia Antipolis, France, 1997.