Effects of Introducing Similarity Measures into Artificial Bee Colony Approach for Optimization of Vehicle Routing Problem

Authors: P. Shunmugapriya, S. Kanmani, P. Jude Fredieric, U. Vignesh, J. Reman Justin, K. Vivek

Abstract:

Vehicle Routing Problem (VRP) is a complex combinatorial optimization problem and it is quite difficult to find an optimal solution consisting of a set of routes for vehicles whose total cost is minimum. Evolutionary and swarm intelligent (SI) algorithms play a vital role in solving optimization problems. While the SI algorithms perform search, the diversity between the solutions they exploit is very important. This is because of the need to avoid early convergence and to get an appropriate balance between the exploration and exploitation. Therefore, it is important to check how far the solutions are diverse. In this paper, we measure the similarity between solutions, which ABC exploits while optimizing VRP. The similar solutions found are discarded at the end of the iteration and only unique solutions are passed on to the next iteration. The bees of discarded solutions become scouts and they start searching for new solutions. This process is continued and results show that the solution is optimized at lesser number of iterations but with the overhead of computing similarity in all the iterations. The problem instance from Solomon benchmarked dataset has been used for evaluating the presented methodology.

Keywords: ABC algorithm, vehicle routing problem, optimization, Jaccard’s similarity measure.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1127952

References:

[1] Dantzig GB, Ramser JH, The truck dispatching problem. Manage Sci 1956; 6(1):80–91.
[2] Nabila Azi, Michel Gendreau, Jean-Yves Potvin, An exact algorithm for a single-vehicle routing problem with time windows and multiple routes, European Journal of Operational Research 178 (2007) 755–766
[3] Nallusamy R, Duraiswamy K, Dhanalaksmi R, Parthiban P, Optimization of Multiple Vehicle Routing Problems using Approximation Algorithms, International Journal of Engineering Science and Technology, vol.1(3), 2009, 129 – 135.
[4] Gilbert Laporte, The Vehicle Routing Problem: An overview of Exact and Approximate Algorithms, Invited Review, European Journal of Operational Research 59, 1992, 345-358.
[5] Y. Zare Mehrjerdi, Vehicle Routing Problem: Meta-heuristic Approaches, International Journal of Applied Operational Research, Vol. 2, No. 3, pp. 55-68, 2012.
[6] Yutao Qi, Zhanting Hou, HeLi, Jianbin Huang, Xiaodong Li, A decomposition based memetic algorithm for multi-objective vehicle routing problem with time windows, Computers & Operations Research 62 (2015) 61–77.
[7] Narges Norouzi, Reza Tavakkoli-Moghaddam, Alireza Salamatbakhsh and Mahdi Alinaghian, Solving a novel bi-objective open vehicle routing problem in a competitive situation by multiobjective particle swarm optimization, Journal of Applied Operational Research (2009) 1(1), 15–29 ISSN 1735-8523
[8] Yang Peng, Ye-mei Qian, A particle swarm optimization to vehicle routing problem with fuzzy demands, Journal of Convergence Information Technology Volume 5, Number 6, August 2010
[9] Sumaiya Iqbal, Kaykobad M, Sohel Rahman M, Solving the multi-objective Vehicle Routing Problem with Soft Time Windows with the help of bees, Swarm and Evolutionary Computation 24(2015), 50–64.
[10] Abel Garcia Najera, Multi-Objective Evolutionary Algorithms for Vehicle Routing Problems, A thesis submitted to The University of Birmingham for the degree of Doctor of Philosophy 2010.
[11] D. Karaboga, An Idea Based on Honey Bee Swarm for Numerical Optimization, Technical Report-TR06, Engineering Faculty, Computer Engineering Department, Erciyes University, 2005
[12] M. El-Abd, A cooperative approach to the artificial bee colony algorithm, in: Proceedings of IEEE Congress on Evolutionary Computation, 2010, pp.1–5.
[13] D. Karaboga, B. Basturk, On the performance of Artificial Bee Colony (ABC) algorithm, Applied Soft Computing 8(2008) 687–697.
[14] D. Karaboga, B.Akay, A comparative study of artificial bee colony algorithm, Applied Mathematics and Computation 214(2009)108–132.
[15] L. Bao, J.C. Zeng, Comparison and analysis of the selection mechanism in the artificial bee colony algorithm, in: Proceedings of IEEE Ninth International Conference on Hybrid Intelligent Systems, 2009, pp.411–416.
[16] Abel Garcia-Najera, Preserving population diversity for the multi-objective vehicle routing problem with time windows. GECCO (Companion) 2009: 2689-2692.
[17] Abel Garcia-Najera, John A. Bullinaria, Bi-objective Optimization for the Vehicle Routing Problem with Time Windows: Using Route Similarity to Enhance Performance, Chapter, Evolutionary Multi-Criterion Optimization, Volume 5467 of the series Lecture Notes in Computer Science, 2010, pp 275-289
[18] Abel Garcia-Najera, John A. Bullinaria, An improved multi-objective evolutionary algorithm for the vehicle routing problem with time windows, Computers & Operations Research 38 (2011) 287–300.
[19] Marek Kubiak, Systematic Construction of Recombination Operators for the Vehicle Routing Problem, Foundations of Computing and Decision Sciences, Vol. 29, No. 3, 2004.
[20] Abel Garcia-Najera, John A. Bullinaria, Comparison of Similarity Measures for the Multi-Objective Vehicle Routing Problem with Time Windows, Proceedings of GECCO-2009, July 8–12, 2009.
[21] Lenstra JK, Kan AHGR. Complexity of vehicle routing and scheduling problems, Networks 1981;11:221–7.
[22] P.Shunmugapriya, S.Kanmani, Optimization of stacking ensemble configurations through Artificial Bee Colony algorithm, Swarm and Evolutionary Computation 12 (2013) 24–32.
[23] Arne Lokketangen, Johan Oppen, Jorge Oyola, David L. Woodruff, Attribute Based Similarity Function for VRP Decision Support, Decision Making in Manufacturing and Services Vol. 6 _ 2012 _ No. 2 _ pp. 65–83 Special Issue on Optimization in Supply Chain Management.
[24] VRPTW Benchmark Problems, Last updated: March 24, 2005, http://w.cba.neu.edu/~msolomon/home.htm