International Journal of Information Technology and Computer Science (IJITCS)
IJITCS Vol. 7, No. 12, 8 Nov. 2015
Cover page and Table of Contents: PDF (size: 485KB)
Relative Performance of Certain Meta Heuristics on Vehicle Routing Problem with Time Windows
Full Text (PDF, 485KB), PP.40-49
Views: 0 Downloads: 0
Author(s)
Sandhya
1,*
V. Katiyar
1
Index Terms
Vehicle Routing Problem, Time windows, Simulated Annealing, Genetic Algorithm, Ant Colony Optimization
Abstract
Solving Vehicle Routing Problem (VRP) and its variants arise in many real life distribution systems. Classical VRP can be described as the problem of finding minimum cost routes with identical vehicles having fixed capacity which starts from a depot and reaches a number of customers with known demands with the proviso that each route starts and ends at the depot and the demand of each customer does not exceed the vehicle capacity is met. One of the generalizations of standard VRP is Vehicle Routing Problem with Time Windows (VRPTW) with added complexity of serving every customer within a specified time window. Since VRPTW is a NP hard meta heuristics have often been designed for solving it. In this paper we compare the performance of Simulated Annealing (SA), genetic Algorithm (GA) and Ant Colony Optimization (ACO) for solving VRPTW based on their performance using different parameters taking total travel distance as the objective to be minimized. The results indicate that ACO is in general slightly more efficient then SA and GA.
Cite This Paper
Sandhya, V. Katiyar, "Relative Performance of Certain Meta Heuristics on Vehicle Routing Problem with Time Windows", International Journal of Information Technology and Computer Science(IJITCS), vol.7, no.12, pp.40-49, 2015. DOI:10.5815/ijitcs.2015.12.05
Reference
[1]Gendreau, Michel, and Christos D. Tarantilis. Solving large-scale vehicle routing problems with time windows: The state-of-the-art. CIRRELT, 2010.
[2]Hosny, Manar Ibrahim. Investigating heuristic and meta-heuristic algorithms for solving pickup and delivery problems. Diss. Cardiff University, 2010.
[3]Soo, Raymond Kuo Yang, and Yong Haur Tay. "A survey on the progress of research on vehicle routing problem with time window constraints." Symposium on Progress in Information and Communication Technology (SPICT). 2009.
[4]Eksioglu, Burak, Arif Volkan Vural, and Arnold Reisman. "The vehicle routing problem: A taxonomic review." Computers & Industrial Engineering 57.4 (2009): 1472-1483.
[5]Blocho, Miroslaw, and Zbigniew J. Czech. "A parallel memetic algorithm for the vehicle routing problem with time windows."P2P, Parallel, Grid, Cloud and Internet Computing (3PGCIC), 2013 Eighth International Conference on. IEEE, 2013.
[6]Amini, Shahrzad, Hassan Javanshir, and Reza Tavakkoli-Moghaddam. "A PSO approach for solving VRPTW with real case study." Int. J. Res. Rev. Appl. Sci4.3 (2010): 118-126.
[7]QI, Mingyao, et al. "A new two-phase hybrid metaheuristic for vehicle routing problem with time windows." Journal of the Eastern Asia Society for Transportation Studies 10.0 (2013): 880-896.
[8]Nazif, Habibeh, and Lai Soon Lee. "Optimized crossover genetic algorithm for vehicle routing problem with time windows." American journal of applied sciences 7.1 (2010): 95.
[9]Masrom, Suraya, and Arfah Mohd Nasir. "Evaluation of vehicle routing problem with time windows by using metaheuristics algorithms." (2012).
[10]El-Sherbeny, Nasser A. "Vehicle routing with time windows: An overview of exact, heuristic and metaheuristic methods." Journal of King Saud University-Science 22.3 (2010): 123-131.
[11]Yang, Xin-She. "Metaheuristic Optimization: Algorithm Analysis and Open Problems." arXiv preprint arXiv: 1212. 0220 (2012).
[12]Taner, Filip, Ante Gali?, and Ton?i Cari?. "Solving Practical Vehicle Routing Problem with Time Windows Using Metaheuristic Algorithms." PROMET-traffic&Transportation 24.4 (2012): 343-351.
[13]Minocha, Bhawna, and Saswati Tripathi. "Two Phase Algorithm for Solving VRPTW Problem." (2013).
[14]Wu, Xudong. "A two-stage ant colony optimization algorithm for the vehicle routing problem with time windows." IJACT: International Journal of Advancements in Computing Technology 4.1 (2012): 485-491.
[15]Thangiah, Sam R., Ibrahim H. Osman, and Tong Sun. "Hybrid genetic algorithm, simulated annealing and tabu search methods for vehicle routing problems with time windows." Computer Science Department, Slippery Rock University, Technical Report SRU CpSc-TR-94-27 69 (1994).
[16]Chen, Chia-Ho, and Ching-Jung Ting. "A hybrid ant colony system for vehicle routing problem with time windows." Journal of the Eastern Asia Society for Transportation Studies 6 (2005): 2822-2836.
[17]Bansal, Sandhya, Rajeev Goel, and C. Mohan. "Use of Ant Colony System in Solving Vehicle Routing Problem with Time Window Constraints." Proceedings of the Second International Conference on Soft Computing for Problem Solving (SocProS 2012), December 28-30, 2012. Springer India, 2014.
[18]Katiyar, Vijay. "An Enhanced Ant Colony System for Solving Vehicle Routing Problem with Time Window." International Journal of Computer Applications 73 (2013).
[19]Dorigo, Marco, and Thomas Stützle. "Ant colony optimization: overview and recent advances." Handbook of metaheuristics. Springer US, 2010. 227-263.
[20]Garcia-Najera, Abel, and John A. Bullinaria. "An improved multi-objective evolutionary algorithm for the vehicle routing problem with time windows."Computers & Operations Research 38.1 (2011): 287-300.
[21]Ba?os, Raúl, et al. "A multi-start hybrid algorithm for vehicle routing problems with time windows." World Online Conference on Soft Computing in Industrial Applications. 2011.
[22]Nguyen, Khanh Phuong. "Meta-heuristic Solution Methods for Rich Vehicle Routing Problems." (2014).
[23]Moccia, Luigi, Jean-Fran?ois Cordeau, and Gilbert Laporte. "An incremental tabu search heuristic for the generalized vehicle routing problem with time windows." Journal of the Operational Research Society 63.2 (2012): 232-244.
[24]Blum, Christian, and Andrea Roli. "Metaheuristics in combinatorial optimization: Overview and conceptual comparison." ACM Computing Surveys (CSUR) 35.3 (2003): 268-308.
[25]Cari?, Tonc?i, et al. "Empirical analysis of two different metaheuristics for real-world vehicle routing problems." Hybrid Metaheuristics. Springer Berlin Heidelberg, 2007. 31-44.
[26]Singh, Harpreet, and Parminder Kaur. "Website Structure Optimization Model Based on Ant Colony System and Local Search." International Journal of Information Technology and Computer Science (IJITCS) 6.11 (2014): 48.
[27]Kumar, Koushal, and Gour Sundar Mitra Thakur. "Advanced applications of neural networks and artificial intelligence: A review." International Journal of Information Technology and Computer Science (IJITCS) 4.6 (2012): 57.