Symbiotic Organism Search (SOS) for Solving the Capacitated Vehicle Routing Problem

Authors: Ruskartina Eki, Vincent F. Yu, Santosa Budi, A. A. N. Perwira Redi

Abstract:

This paper introduces symbiotic organism search (SOS) for solving capacitated vehicle routing problem (CVRP). SOS is a new approach in metaheuristics fields and never been used to solve discrete problems. A sophisticated decoding method to deal with a discrete problem setting in CVRP is applied using the basic symbiotic organism search (SOS) framework. The performance of the algorithm was evaluated on a set of benchmark instances and compared results with best known solution. The computational results show that the proposed algorithm can produce good solution as a preliminary testing. These results indicated that the proposed SOS can be applied as an alternative to solve the capacitated vehicle routing problem.

Keywords: Symbiotic organism search, vehicle routing problem, metaheuristics, Solution Representation.

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

References:

[1] G. B. Dantzig., J. H. Ramser. The truck dispatching problem. Management Science, 6:80, 1959.
[2] Lenstra, J.K., Kan. A.H.G.R. Complexity of vehicle routing and scheduling problems. Networks 11, 221 – 227. 1981.
[3] Toth. P, Vigo. D. The vehicle routing problem. SIAM Monograph on Discrete Mathematics & Application. Philadelphia, PA. 2002
[4] G. Clarke, J.V. Wright. Scheduling of vehicle from a central depot to a number of delivery points. Operation research, 12:568-581, 1964
[5] R.H. Mole, S.R. Jameson. A sequential route-building algorithm employing a generalized saving criterion. Operational Research Quarterly, 27:503-511, 1976.
[6] N. Christofides, A. Mingozzi, P. Toth. The vehicle routing problem. In N. Christofides, A. Mingozzi, P. Toth, C. Sandi, editors, Combinatorial Optimization. Wiley, Chichester, UK, 1979, pp 315-338
[7] B. E. Gillett, L.R. Miller. A heuristic algorithm for vehicle dispatch problem. Operation research, 22:340-349, 1976.
[8] A. Wren, A. Holliday. Computer scheduling of vehicles from one or more depots to a number of delivery points. Operational Research Quarterly, 23:333-334, 1972
[9] M. L. Fisher, R. Jaikumar. A generalized assignment heuristic for vehicle routing problem. Networks, 11:109-124, 1981.
[10] J. Bramel, D. Simche-Levi. A location based heuristic for general routing problems. Operation research, 43:649-660, 1995.
[11] F. Robuste, C. F. Daganzo, R. Souleyrette. Implementing vehicle routing models. Transportation Research B, 24:263-286, 1990.
[12] I.H. Osman. Metastrategy simulated annealing and tabu search algorithm for the vehicle routing problem. Annals of Operations Research, 41:421-451, 1993.
[13] Baker. B. M, Ayechew, M.A. A genetic algorithm for vehicle routing problem. Computer & Operation Research 30:787-800, 2003.
[14] Berger. J, Barkoui. M. A new hybrid genetic algorithm for the capacitated vehicle routing problem. Journal of the Operational Research Society 54:1254-1262, 2003.
[15] Mazzeo. S, Loiseau. Irene. An ant colony algorithm for the capacitated vehicle routing. Electronic Notes in Discrete Mathematics, 18:181-186, 2004.
[16] Szeto. W. Y, Yongzhong Wu, Sin. C. Ho. An artificial bee colony algorithm for the capacitated routing problem. European Journal of Operational Research 215:126-135, 2011.
[17] Ai. T. J, Kachitvichyanukul. V. A particle swarm optimization for capacitated vehicle routing problem. International Journal of Logistics and SCM Systems, 2:50-55, 2007.
[18] Cheng, M. Y, Prayogo, D. Symbiotic organism search: A new metaheuristic optimization. Computers and Structures, 139:98-112, 2014.
[19] Ai. T. J, Kachitvichyanukul. V. Particle swarm optimization and two solution representations for solving the capacitated vehicle routing problem. Computers & Industrial Engineering, 56:380-387, 2009.
[20] Talbi. El-Ghazali. Metaheuristics from design to implementation. Wiley, University of Lille – CNRS – Inria. 2009.
[21] Santosa. Budi, Willy. Paul. Metoda Metaheuristik Konsep dan Implementasi. Surabaya, Indonesia. 2011.