Open Access Open Access  Restricted Access Subscription or Fee Access

Adapted Bat Algorithm for Capacitated Vehicle Routing Problem


(*) Corresponding author


Authors' affiliations


DOI: https://doi.org/10.15866/irecos.v10i6.6512

Abstract


The Capacitated Vehicle Routing Problem (CVRP) is an NP-hard problem and one of the most challenging combinatorial optimization task. This paper presents a new Swarm Algorithm based on bats behavior to solve CVRP. We called it, Adapted Bat Algorithm (ABA). Previous works show that Bat Algorithm (BA) has not yet been applied efficiently to solve CVRP, even though it was successfully used to solve other problems. The approach of ABA allows a large diversity of the population and a balance between global and local search. The simulation of nine benchmark instances shows that our proposed algorithm is effective and feasible. Compared to Genetic Algorithm (GA), ABA can get high precision and exceed some best known values.
Copyright © 2015 Praise Worthy Prize - All rights reserved.

Keywords


Adapted Bat Algorithm; Capacitated Vehicle Routing Problem; Genetic Algorithm; Natural Inspired Algorithm; Swarm Intelligence

Full Text:

PDF


References


G. Dantzig, J. Ramser, The truck dispatching problem, Management Science, vol. 6, pp. 80-91, 1959.
http://dx.doi.org/10.1287/mnsc.6.1.80

X.S. Yang, Nature-Inspired Metaheuristic Algorithms: Second Edition (Luniver Press, 2010).

R.S. Parpinelli, H.S. Lopes, New inspirations in swarm intelligence: a survey, International Journal of Bio-Inspired Computation, vol. 3, n. 1, pp. 1-16, 2011.
http://dx.doi.org/10.1504/ijbic.2011.038700

S.N. Sivanandam, S.N. Deepa, Introduction to Genetic Algorithms (Springer-Verlag Berlin Heidelberg, 2008).
http://dx.doi.org/10.1007/978-3-540-73190-0_2

M. Mitchell, An Introduction to Genetic Algorithms (MIT Press, Cambridge, MA, USA, 1996).
http://dx.doi.org/10.1016/s0092-8240(96)00095-x

M. Dorigo, T. Stutzle, Ant Colony Optimization (Bradford Company Scituate, MA, USA, 2004).

Wang, Y., Research on the vehicle routing problem with time windows by cellular ant algorithm, (2013) International Review on Computers and Software (IRECOS), 8 (1), pp. 390-395.

X.S. Yang, Particle Swarm Optimization, Xin-She Yang, Nature-Inspired Optimization Algorithms (Elsevier, Oxford, 2014, Pages 99-110).
http://dx.doi.org/10.1016/b978-0-12-416743-8.00007-5

R. Kumar, Directed Bee Colony Optimization Algorithm, Swarm and Evolutionary Computation, Vol. 17, pp. 60-73, 2014.
http://dx.doi.org/10.1016/j.swevo.2014.03.001

I. Fister, Jr. Iztok Fister, X.S. Yang, J. Brest, A comprehensive review of firefly algorithms, Swarm and Evolutionary Computation, Vol. 13, pp. 34-46, 2013.
http://dx.doi.org/10.1016/j.swevo.2013.06.001

X.S. Yang, S. Deb, Cuckoo search via Levy flights, in: Proc. of World Congress on Nature & Biologically Inspired Computing (India. IEEE Publications, USA, pp. 210-214, 2009).
http://dx.doi.org/10.1109/nabic.2009.5393690

Manikandan, P., Selvarajan, S., A hybrid optimization algorithm based on cuckoo search and PSO for data clustering, (2013) International Review on Computers and Software (IRECOS), 8 (9), pp. 2278-2287.

S. Das, A. Mukhopadhyay, A. Roy, A. Abraham, B.K. Panigrahi, , Exploratory Power of the Harmony Search Algorithm: Analysis and Improvements for Global Numerical Optimization, Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions, vol. 41, no. 1, pp. 89-106, 2011.
http://dx.doi.org/10.1109/tsmcb.2010.2046035

X.S. Yang, A new metaheuristic Bat-inspired algorithm. Nature inspired cooperative strategies for optimization, Studies in Computational Intelligence, vol. 284, pp. 65-74, 2010.
http://dx.doi.org/10.1007/978-3-642-12538-6_6

L. Liangliang, Z. Yongquan, A novel complex-valued bat algorithm, Neural Computing and Applications, Vol. 25, n. 6, pp. 1369-1381, 2014.
http://dx.doi.org/10.1007/s00521-014-1624-y

S. Sakthivel, R. Natarajan, P. Gurusamy, Application of Bat Optimization Algorithm for Economic Load Dispatch Considering Valve Point Effects, International Journal of Computer Applications, Vol. 67, n. 11, 2013.
http://dx.doi.org/10.5120/11442-7035

E.S. Ali, Optimization of Power System Stabilizers using BAT search algorithm, International Journal of Electrical Power & Energy Systems, Vol. 61, pp. 683-690, 2014.
http://dx.doi.org/10.1016/j.ijepes.2014.04.007

Y. Zhou, J. Xie, H. Zheng, A hybrid bat algorithm with path relinking for capacitated vehicle routing Problem. Mathematical Problems in Engineering, vol. 2013, pp. 10, 2013
http://dx.doi.org/10.1155/2013/392789

Jian Xie, Yongquan Zhou, and Hongqing Zheng, A Hybrid Meta- heuristic for Multiple Runways Aircraft Land-ing Problem Based on Bat Algorithm, Journal of Applied Mathematics, vol. 2013, pp. 8, 2013.
http://dx.doi.org/10.1155/2013/742653

R. Hafezi, J. Shahrabi, E.Hadavandi, A bat-neural network multi-agent system (BNNMAS) for stock price prediction: Case study of DAX stock price, Applied Soft Computing, Vol. 29, pp. 196-210, 2015.
http://dx.doi.org/10.1016/j.asoc.2014.12.028

E. Alba, B. Dorronsoro, Solving the Vehicle Routing Problem by Using Cellular Genetic Algorithms, Evolutionary Computation in Combinatorial Optimization, Vol. 3004, pp. 11-20, 2004.
http://dx.doi.org/10.1007/978-3-540-24652-7_2

P. Augerat, Approche Polyèdrale du Problème de Tournées de Véhicules. PhD thesis, Institut National Polytechnique de Grenoble, 1995.

N. Christodes and S. Eilon, An algorithm for the vehicle dispatching problem, Operational Research Quarterly, vol. 20, pp. 309-318, 1969.
http://dx.doi.org/10.1057/jors.1969.75


Refbacks

  • There are currently no refbacks.


Please send any question about this web site to info@praiseworthyprize.com
Copyright © 2005-2024 Praise Worthy Prize