Home   >   CSC-OpenAccess Library   >    Manuscript Information
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 
A. Chabrier, “Vehicle Routing Problem with Elementary Shortest Path based Column Generation.” Computers and Operations Research, vol. 33(10), pp. 2972-2990, 2006.
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.
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.
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.
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.
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.
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].
G.B. Dantzig and J. H.Ramser, “The Truck Dispatching Problem”, Management Science,vol. 6 (1), pp. 80–91, 1959.
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.
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
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
J. H. Holland, “Adaptation in Natural and Artificial System”. Ann Arbor, Michigan: The University of Michigan Press, 1975.
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.
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.
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.
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.
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
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.
M. M. Solomon, “Algorithms for Vehicle Routing and Scheduling Problems with Time Window Constraints”, Operations Research, vol. 35(2), pp. 254-265, 1987
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
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.
O. Bräysy and M. Gendreau, “Vehicle routing problem with time windows, Part II:Metaheuristics “, Transportation Science, vol. 39, pp. 119–139, 2005
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
P.J. van Laarhoven and E.H. Aarts, “Simulated Annealing” U.S.A : Dordrecht and Boston and Norwell, MA, 1987.
S. Ropke and D. Pisinger, “A General Heuristics for Vehicle Routing Problems”, Computers & Operations Research, vol. 34(8), pp. 2403-2435, 2007
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.
Y. Rochat and E. Taillard, “Probabilistic Diversification and Intensification in Local Search for Vehicle Routing” Journal of Heuristics vol. 1, pp. 147-167, 1995.
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.
Mr. Bhawna Minocha
Amity School of Computer Sciences Noida - India
bminocha@amity.edu
Associate Professor Saswati Tripathi
Indian Institute of Foreign Trade Kolkata - India


CREATE AUTHOR ACCOUNT
 
LAUNCH YOUR SPECIAL ISSUE
View all special issues >>
 
PUBLICATION VIDEOS