Fuzzy Based Parameter Adaptation in ACO for Solving VRP

Fuzzy Based Parameter Adaptation in ACO for Solving VRP

Sandhya (Department of Computer Science and Engineering, Maharishi Markandeswar Deemed to be University Mullana, Ambala, India) and Rajiv Goel (Department of Computer Science, Government College, Naraingarh, Ambala, India)
DOI: 10.4018/IJORIS.2019040104

Abstract

Ant Colony Optimization, a popular class of metaheuristics, have been widely applied for solving optimization problems like Vehicle Routing Problem. The performance of ACO is affected by the values of parameters used. However, in literature, few methods are proposed for parameter adaptation of ACO. In this article, a fuzzy-based parameter control mechanism for ACO has been developed. Three adaptive strategies FACO-1, FACO-2, FACO-3 are proposed for determining values of parameters alpha and beta, and evaporation factor separately as well as for all three parameters simultaneously. The performance of proposed strategies is compared with standard ACS on TSP and VRP benchmarks. Computational results on standard benchmark problems shows the effectiveness of the strategies.
Article Preview
Top

1. Introduction

Vehicle Routing Problem (VRP) is one of the typical examples of combinatorial optimization problems. The problem was first formulated by Dantizg and Ramesher in 1959. VRP is one of the extensively studied problems in operation research because of its wide applications in the area of transportation and logistics. It can also be applied to other applications such as waste collection (Kim et al., 2006), tour planning (Zing & Zhang, 2010) etc. A typical VRP can be described as: a depot that wants to offer services to geographically scattered customers at the lowest tour planning cost. VRP has been proved to be NP Hard problem. Many methods have been proposed to solve VRP. During recent years soft computing techniques like meta heuristics and fuzzy logic have been also used for solving these complex problems in place of traditional methods. Some of the meta heuristics can solve this problem in reasonable time. Ant Colony Optimization (ACO) is one of the meta heuristic which is being used to solve VRP problem. ACO was proposed by Marco Dorigo in 1990 (Dorigo & Di Caro, 1990). ACO is a nature inspired metaheuristic that mimics the behavior of real ant in finding the shortest path to food source from the nest. Till now many variations of ACO have been proposed (Dorigo, 2007). A lot of literature (Dorigo & Birattari, 2011; Afshar, 2015; Sakthipriya & Kalaipriyan, 2015) exists where efforts have been made to improve performance of ACO. One of the important issues in ACO is the parameters value selection. The algorithm starts with the initialization of some parameters that effect the performance of the algorithm used for solving a particular problem. Moreover, the adopted values of parameters also control the balance between exploration and exploitation. In literature, most of the ACO studies, either use static parameters value or use hand tuned parameters value. However, choice of parameters values used at run time significantly affect the performance of the algorithm. Finding the appropriate values of the parameters and their adjustment of those values requires a considerable effort and lot of computation. In fact, parameter tuning and parameter adaptation are the two important research topics in the field of meta heuristics (Stützle et al., 2011; Eiben et al., 1999). Parameter tuning is a process of finding appropriate settings of parameters before the algorithm is actually employed and then running the algorithm with these values. However, this process is error prone, time consuming and human intensive. An alternative to this is parameter adaptation, in which the algorithm adapts the values of the parameter dynamically according to the problem characteristics. In this paper, a fuzzy based parameter adaptation scheme is proposed in ACO for solving VRP problem. The parameters in ACS include alpha IJORIS.2019040104.m01, beta IJORIS.2019040104.m02 and pheromone evaporation rate IJORIS.2019040104.m03. These parameters have relatively more importance than other parameters like number of ants etc.

In this paper fuzzy logic based three adaptive strategies FACO-1, FACO-2, FACO-3 is proposed for parameter adaptation of ACO. FACO-1 determines appropriate values of IJORIS.2019040104.m04 and IJORIS.2019040104.m05while keeping other parameters static. FACO-2 decides the value of evaporation factor (IJORIS.2019040104.m06 while keeping others as constant. FACO-3 determines the values of all three parameters simultaneously. Performance of the proposed three strategies are compared with static ACS for VRP.

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 12: 4 Issues (2021): Forthcoming, Available for Pre-Order
Volume 11: 4 Issues (2020): 2 Released, 2 Forthcoming
Volume 10: 4 Issues (2019)
Volume 9: 4 Issues (2018)
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing