Evolutionary Ant Colony Algorithm Using Firefly Based Transition for Solving Vehicle Routing Problems: EAFA for VRPs

Evolutionary Ant Colony Algorithm Using Firefly Based Transition for Solving Vehicle Routing Problems: EAFA for VRPs

Rajeev Goel (Ambala College of Engg. and Applied Research, Ambala, India) and Raman Maini (Punjabi University, Patiala, India)
Copyright: © 2019 |Pages: 15
DOI: 10.4018/IJSIR.2019070103

Abstract

Vehicle routing problems are a classical NP-hard optimization problem. In this article we propose an evolutionary optimization algorithm which adapts the advantages of ant colony optimization and firefly optimization to solve vehicle routing problem and its variants. Firefly optimization (FA) based transition rules and a novel pheromone shaking rule is proposed to escape local optima. Whereas the multi-modal nature of FA explores the search space, pheromone shaking avoids the stagnation of pheromones on the exploited paths. This is expected to improve working of an ant colony system (ACS). Performance of the proposed algorithm is compared with the performance of some of other currently available meta-heuristic approaches for solving vehicle routing problems (VRP) by applying it to certain standard benchmark datasets. Results show that the proposed approach is consistent and its convergence rate is faster. The results also demonstrate the superiority of the proposed approach over some of the other existing FA-based approaches for solving such type of discrete optimization problems.
Article Preview
Top

1. Introduction

Nature inspired optimization algorithms have now become an important tool for solving complex real-life optimization problems. Several nature-inspired computing paradigms have been developed in the last three decades for solving optimization problems arising in different areas of real life (Dorigo et al., 1991; Iztok et al., 2013). It has been observed that soft computing-based approaches such as neural networks, fuzzy logic, PSO, Artificial immune systems can play important roles for the solution of NP-hard problems (Toth & Vigo, 2014). Soft computing approach primarily aims to develop the systems that have the ability to learn and adapt to the environment. It works in an incremental manner. Use of bio inspired algorithms such as artificial neural networks (ANN), genetic algorithms (GA) and swarm intelligence (S.I.) for solving a variety of complex realm optimization problems has grown rapidly. Evolutionary computing refers to the mechanism that deals with the collective behavior of the swarms such as ants, worms, bees, birds etc. The individuals in a swarm, based on their certain traits arrive at decisions such as where to forage, where to reproduce etc. Ants and bees use this type of information to locate and reach new food sources. Similarly worms such as termites etc. are able to build sophisticated nests using intelligence which emerges out of their collective behavior. Firefly algorithm (FA), BAT algorithm, Cuckoo Search etc. are some of the swarm intelligence-based approaches which have been used for solving complex real life optimization problems (Izotok et al., 2013; Goel & Maini, 2018).

Evolutionary computing has also found wide spread applicability in solution of many real-world NP-hard problems such as vehicle routing problem (VRP), Graph coloring problem, Job-Scheduling problem and Bin-packing problems etc. Exact methods for solving such problems can only be used in case of small/medium size problems (Baldacci et al., 2008; Baldacci et al., 2012; Goel & Maini, 2017). VRP problem is NP-hard. Therefore, exact methods are not possible for large sized problems. For solving such NP-Hard problems meta-heuristics are often designed that ensure escape from local optima and try to preserve the good solutions as these are generated using elitist strategy (Dorigo et al., 1991; Iztok et al., 2013).

Simulated annealing SA, Genetic algorithms GA, Tabu Search TS, Ant colony Approach ACS are some of the commonly used meta-heuristics which have been used in the recent decades for solving VRP.

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
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