Home   >   CSC-OpenAccess Library   >    Manuscript Information
Full Text Available

(296.7KB)
This is an Open Access publication published under CSC-OpenAccess Policy.
Publications from CSC-OpenAccess Library are being accessed from over 74 countries worldwide.
Two Phase Algorithm for Solving VRPTW Problem
Bhawna Minocha, Saswati Tripathi
Pages - 1 - 16     |    Revised - 15-01-2013     |    Published - 28-02-2013
Volume - 4   Issue - 1    |    Publication Date - April 2013  Table of Contents
MORE INFORMATION
KEYWORDS
Vehicle Routing Problem with Time Windows, Genetic Algorithm, Random Search Algorithm, Simulated Annealing
ABSTRACT
Vehicle Routing Problem with Time Windows (VRPTW) is a well known NP hard combinatorial scheduling optimization problem in which minimum number of routes have to be determined to serve all the customers within their specified time windows. Different analytic and heuristic approaches have been tried to solve such problems. In this paper we propose a two phase method which utilizes Genetic algorithms as well as random search incorporating simulated annealing concepts to solve VRPTW problem in various scenarios.
CITED BY (3)  
1 Katiyar, V. (2015). Relative Performance of Certain Meta Heuristics on Vehicle Routing Problem with Time Windows. International Journal of Information Technology and Computer Science (IJITCS), 7(12), 40.
2 Han, Z. (2015). Truckload Carrier Selection, Routing and Cost Optimization.
3 Johar, F., Potts, C., & Bennell, J. (2015). Vehicle Routing Problem with Time Constraints. Malaysian Journal of Fundamental and Applied Sciences, 11(4).
1 Google Scholar 
2 CiteSeerX 
3 refSeek 
4 Scribd 
5 SlideShare 
6 PdfSR 
1 J. Berger and M. Barkaoui, “A parallel hybrid genetic algorithm for the vehicle routing problem with time windows” Computer Operation Research, vol. 31, pp. 2037-2053, 2004.
2 J. L. Blanton and R. L.Wainwright, “Multiple vehicle routing with time and capacity constraints using genetic algorithms”. Proceedings of the 5th International Conference on Genetic Algorithms, USA, pp. 452-459, June 1993.
3 O. Bräysy and M. Gendreau, “Vehicle routing problem with time windows, Part II:Metaheuristics “, Transportation Science, vol. 39, pp. 119–139, 2005
4 A. Chabrier, “Vehicle Routing Problem with Elementary Shortest Path based Column Generation.” Computers and Operations Research, vol. 33(10), pp. 2972-2990, 2006.
5 J. F. Cordeau, G. Laporte and A., Mercier, “A Unified Tabu Search for Vehicle Routing Problem with Time Windows”, Journal of the Operational Research Society vol. 52 pp. 928-936, 2001
6 J. F. Cordeau, G. Desaulniers, J. Desrosiers, M.M. Solomon and F. Soumis, “The VRP with Time Windows” , In: The Vehicle Routing Problem, SIAM Monographs on Discrete Mathematics and Applications, Toth, P. and D. Vigo (Eds.), Philadelphia, USA, pp. 157-193,2001
7 L. M. Gambardella, E. Taillard, G. Agazzi, " MACS-VRPTW: A Multiple Ant Colony System for Vehicle Routing Problems with Time Windows", New Ideas in Optimization, London:McGraw-Hill, pp. 63-76, 1999.
8 J. H. Holland, “Adaptation in Natural and Artificial System”. Ann Arbor, Michigan: The University of Michigan Press, 1975.
9 J. Hömberger, H. Gehring, “A Two-Phase Hybrid Metaheuristic for the Vehicle Routing Problem with Time Windows”, European Journal of Operations Research, vol. 162(1), pp.220-238, 2005.
10 B. Kallehauge, J. Larsen, and O. B. G. Madsen, "Lagrangean duality and non-differentiable optimization applied on routing with time windows ." Computers and Operations Research,vol. 33(5),pp. 1464-1487,2006.
11 N. Kohl, J. Desrosiers, O. B. G. Madsen, M.M. Solomon and F. Soumis, "2-Path Cuts for the Vehicle Routing Problem with Time Windows," Transportation Science, vol. 33 (1) , pp.101-116 ,1999.
12 J. Larsen "Parallelization of the vehicle routing problem with time windows." Ph.D. Thesis IMM-PHD-1999-62, Department of Mathematical Modelling, Technical University of Denmark,Lyngby, Denmark, 1999.
13 B. Ombuki, B.J. Ross, and F. Hansher, “Multi-objective Genetic Algorithm for Vehicle Routing Problem with Time Windows”, Applied Intelligence, vol. 24(1), pp. 17-30, 2006.
14 B. Minocha and S. Tripathi, “Vehicle Routing Problem with Time Windows: An Evolutionary Algorithmic Approach”, Algorithmic Operations Research, vol. 1(2), pp. 1-15, 2006.
15 J. Potvin and S. Bengio, “The Vehicle Routing Problem with Time Windows part II: Genetic Search. INFORMS Journal on Computing, vol. 8(2), pp. 165-172, 1996.
16 Y. Rochat and E. Taillard, “Probabilistic Diversification and Intensification in Local Search for Vehicle Routing” Journal of Heuristics vol. 1, pp. 147-167, 1995.
17 S. Ropke and D. Pisinger, “A General Heuristics for Vehicle Routing Problems”, Computers & Operations Research, vol. 34(8), pp. 2403-2435, 2007
18 P. Shaw, “Using Constraint Programming and Local Search Methods to solve Vehicle Routing Problems”, Principles and Practice of Constraint Programming, Springer-Verlag ,pp. 417-431, 1998
19 M. M. Solomon, “Algorithms for Vehicle Routing and Scheduling Problems with Time Window Constraints”, Operations Research, vol. 35(2), pp. 254-265, 1987
20 E. D. Taillard, P. Badeau, M. Gendreau, F. Guertin and J. Potvin, “A Tabu Search Heuristics for the Vehicle Routing Problem with Soft Time Windows”. Transportation Science vol. 31,pp. 170-186, 1997.
21 K. C. Tan, L. H. Lee, K. Ou, “Hybrid Genetic Algorithms in Solving Vehicle Routing Problems with Time Window Constraint”, Asia-Pacific Journal of Operation Research 18:121-130,2001
22 S. Thangiah, “Vehicle Routing with Time Windows using Genetic Algorithms”, In Application Handbook of Genetic Algorithms: New Frontiers, vol. 2, Lance Chambers (Ed.): CRC Press,Boca Raton, 1995, pp. 253-277.
23 G.B. Dantzig and J. H.Ramser, “The Truck Dispatching Problem”, Management Science,vol. 6 (1), pp. 80–91, 1959.
24 G.B. Alvarenga, G.R. Mateus and G. De. Tomi, “Finding near optimal Solutions for Vehicle Routing Problems with Time Windows using Hybrid Genetic Algorithm”, Internet:http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.11.46&rep=rep1&type=pdf , 2003,[Jan. 25, 2005].
25 Moccia, L., Cordeau, J.F. and Laporte, G., 2011. “An incremental tabu search heuristic for the generalized vehicle routing problem with time windows” Journal of the Operational Research Society, advance online publication 4 May 2011; doi: 10.1057/jors.2011.25
26 Chen, C. H., Ting, C.J. “ A Hybrid Ant Colony System for Vehicle Routing Problem with Time Windows.” Journal of the Eastern Asia Society for Transportation Studies, 2005, 6:2822-2836.
27 Zhang, Q., Zhen, T., Zhu, Y., Zhang, W. and Ma, Z., 2010. A Hybrid Intelligent Algorithm for the Vehicle Routing with Time Windows. 2010 International Forum on Information Technology and Applications, IEEE, pp. 47-54.
28 P.J. van Laarhoven and E.H. Aarts, “Simulated Annealing” U.S.A : Dordrecht and Boston and Norwell, MA, 1987.
Mr. Bhawna Minocha
Amity School of Computer Sciences Noida - India
bminocha@amity.edu
Associate Professor Saswati Tripathi
Indian Institute of Foreign Trade Kolkata - India