Solution of capacitated vehicle routing problem with invasive weed and hybrid algorithms

Abstract: The vehicle routing problem is widespread in terms of optimization, which is known as being NP-Hard. In this study, the vehicle routing problem with capacity constraints is solved using cost- and time-efficient metaheuristic methods: an invasive weed optimization algorithm, genetic algorithm, savings algorithm, and hybridized variants. These algorithms are tested using known problem sets in the literature. Twenty-four instances evaluate the performance of algorithms from P and five instances from the CMT data set group. The invasive weed algorithm and its hybrid variant with savings and genetic algorithms are used to determine the best methodology regarding time and cost values. The proposed hybrid approach has found optimal P group problem instances with a 2% difference from the best-known solution on average. Similarly, the CMT group problem is solved with about a 10% difference from the best-known solution on average. That the proposed hybrid solutions have a standard deviation of less than 2% on average from BKS indicates that these approaches are consistent.

How to cite this paper

 Yıldırım, � & Kuvvetli, Y. (2021). Solution of capacitated vehicle routing problem with invasive weed and hybrid algorithms.International Journal of Industrial Engineering Computations , 12(4), 441-456.

Refrences

Ahmed, A., & Sun, J. U. (2018). Bilayer local search enhanced particle swarm optimization for the capacitated vehicle routing problem. Algorithms, 11, 31.
Arnold, F., Gendreau, M., & Sörensen, K. (2019). Efficiently solving very large-scale routing problems. Computers & operations research, 107, 32-42.
Augerat, P., Belenguer, J. M., Benavent, E., Corberán, A., Naddef, D., & Rinaldi, G. (1995). Computational results with a branch and cut code for the capacitated vehicle routing problem (Vol. 34): IMAG.
Benrahou, F., & Tairi, A. (2019). Capacitated Vehicle Routing Problem for Collection Waste Lube Oil in Algiers. Fresenius Environ. Bull, 28, 4500-4505.
Boyzer, Z., Alkan, A., & Fığlalı, A. (2014). Cluster-first, then-route based heuristic algorithm for the solution of capacitated vehicle routing problem. International Journal of Informatics Technologies, 7, 29-37.
Cheng, R., Gen, M., & Tsujimura, Y. (1999). A tutorial survey of job-shop scheduling problems using genetic algorithms, part II: hybrid genetic search strategies. Computers & Industrial Engineering, 36, 343-364.
Christofides, N., Mingozzi, A., & Toth, P. (1979). The vehicle routing problem. In A. M. N. Christofides, P. Toth, C. Sandi (Eds.) (Ed.), Combinatorial Optimization (pp. 315-338). Chichester, UK: Wiley.
Clarke, G., & Wright, J. W. (1964). Scheduling of vehicles from a central depot to a number of delivery points. Operations research, 12, 568-581.
Dantzig, G. B., & Ramser, J. H. (1959). The Truck Dispatching Problem. Management Science, 6, 80-91.
Davis, L. (1991). Handbook of genetic algorithms, (Vol. 115). New York: Van Nostrand Reinhold.
Jahangir, H., Mohammadi, M., Pasandideh, S. H. R., & Nobari, N. Z. (2019). Comparing performance of genetic and discrete invasive weed optimization algorithms for solving the inventory routing problem with an incremental delivery. Journal of Intelligent Manufacturing, 30, 2327-2353.
Jang, J.-S. R., Sun, C.-T., & Mizutani, E. (1997). Neuro-fuzzy and soft computing-a computational approach to learning and machine intelligence [Book Review]. IEEE Transactions on automatic control, 42, 1482-1484.
Koç, İ., Nureddin, R., & Kahramanlı, H. (2018). Implementation of GSA (Gravitation Search Algorithm) and IWO (Invasive Weed Optimization) for the prediction of the energy demand in Turkey using linear form. Selcuk University Journal of Engineering Science and Techology, 6, 529-543.
Mehrabian, A. R., & Lucas, C. (2006). A novel numerical optimization algorithm inspired from weed colonization. Ecological Informatics, 1, 355-366.
Mohammadi, M., Razmi, J., & Tavakkoli-Moghaddam, R. (2013). Multi-Objective Invasive Weed Optimization For Stochastic Green Hub Location Routing Problem With Simultaneous Pick-Ups And Deliveries. Economic Computation & Economic Cybernetics Studies & Research, 47.
Mulloorakam, A. T., & Nidhiry, N. M. (2019). Combined objective optimization for vehicle routing using genetic algorithm. Materials Today: Proceedings, 11, 891-902.
Nabiyev, V. V. (2005). Artificial Intelligence: Problems, Methods, Algorithms. Seckin Pub. Co., Ankara.
Nath, S., Chakravarty, A. K., Ghosh, S., & Sarkar, S. K. (2017). Invasive weed optimization approach to VLSI routing. In 2017 Devices for Integrated Circuit (DevIC) (pp. 615-619): IEEE.
Normasari, N. M. E., Yu, V. F., & Bachtiyar, C. (2019). A simulated annealing heuristic for the capacitated green vehicle routing problem. Mathematical Problems in Engineering, 2019.
Pahlavani, P., Delavar, M. R., & Frank, A. U. (2012). Using a modified invasive weed optimization algorithm for a personalized urban multi-criteria path optimization problem. International Journal of Applied Earth Observation and Geoinformation, 18, 313-328.
Pichpibul, T., & Kawtummachai, R. (2012). An improved Clarke and Wright savings algorithm for the capacitated vehicle routing problem. ScienceAsia, 38, 307-318.
Pisinger, D., & Ropke, S. (2007). A general heuristic for vehicle routing problems. Computers & operations research, 34, 2403-2435.
Rojas-Cuevas, I.-D., Caballero-Morales, S.-O., Martinez-Flores, J.-L., & Mendoza-Vazquez, J.-R. (2018). Capacitated vehicle routing problem model for carriers. Journal of Transport and Supply Chain Management, 12, 1-9.
Shrestha, S., & Manogharan, G. (2017). Optimization of binder jetting using Taguchi method. Jom, 69(3), 491-497.
Sur, C., & Shukla, A. (2013). Discrete invasive weed optimization algorithm for graph based combinatorial road network management problem. In 2013 International Symposium on Computational and Business Intelligence (pp. 254-257): IEEE.
Tarantilis, C. D., Ioannou, G., & Prastacos, G. (2005). Advanced vehicle routing algorithms for complex operations management problems. Journal of Food Engineering, 70, 455-471.
Toffolo, T. A., Vidal, T., & Wauters, T. (2019). Heuristics for vehicle routing problems: Sequence or set optimization? Computers & operations research, 105, 118-131.
Wang, L., & Lu, J. (2019). A memetic algorithm with competition for the capacitated green vehicle routing problem. IEEE/CAA Journal of Automatica Sinica, 6, 516-526.
Wedyan, A. F., & Narayanan, A. (2014). Solving capacitated vehicle routing problem using intelligent water drops algorithm. In 2014 10th International Conference on Natural Computation (ICNC) (pp. 469-474): IEEE.
Yücenur, G. N., & Demirel, N. Ç. (2011). A hybrid algorithm with genetic algorithm and ant colony optimization for solving multi-depot vehicle routing problems. Sigma Journal of Engineering and Natural Sciences, 29, 340-350.
Zhang, S., Gajpal, Y., & Appadoo, S. (2018). A meta-heuristic for capacitated green vehicle routing problem. Annals of Operations Research, 269, 753-771.
Zhao, Y., Leng, L., Qian, Z., & Wang, W. (2016). A discrete hybrid invasive weed optimization algorithm for the capacitated vehicle routing problem. Procedia Computer Science, 91, 978-987.