A Hybrid Water Flow-Like Algorithm and Variable Neighbourhood Search for Traveling Salesman Problem

Mohamed Rafique Othman, Zulaiha Ali Othman, Ayman Ibraheem Srour, Nor Samsiah Sani

Abstract


Various metaheuristic methods have been proposed earlier and applied for solving the Travelling Salesman Problem (TSP). Water Flow Algorithm (WFA) is one of the recent population-based metaheuristic optimization techniques used for solving this problem. Past research has shown that improving WFA local search strategy has a significant impact on the algorithm performance. Therefore, this paper aims to solve TSP by enhancing WFA searching strategy based on a Variable Neighbourhood Search (VNS) known as hybrid WFA-VNS. It is a mixture of the exploration of WFA and the exploitation capability of VNS. This study is conducted in two stages: Pre-experiment and initial experiment. The objective of doing pre-experiment is to select four neighborhood structures to be used for the initial experiment. At the first stage, three instances are used, and there are five neighborhood structures involved. Those neighborhood structures are two opt, three opt, four opt, swapping, and insertion move. Because of pre-experiment, it discovers four best neighborhood structures, which are two opt, three opt, exchanging and insertion move. These neighborhood structures will be used in the initial experiment, which an improvement approach is employed. In an initial experiment, the performance of the proposed hybrid WFA-VNS is further studied and tested on 26 established benchmarked symmetric TSP datasets using four neighborhood structures selected in pre-experiment earlier. The TSP datasets involved are categorized into three types: small datasets, medium datasets, and large datasets. Selected neighborhood structures obtained in pre-experiment are applied and generated randomly to intensify the initial solution achieved at an earlier stage of hybrid WFA-VNS. The results of the comparison show that this hybrid approach represents an improvement and able to produce competitive results.


Keywords


hybrid algorithm; water flow; variable neighbourhood search; travelling salesman problem; metaheuristic.

Full Text:

PDF

References


Da Silva, R. F., & Urrutia, S. (2010). A General VNS heuristic for the traveling salesman problem with time windows. Discrete Optimization, 7(4).

Frieze, A. M., Galbiati, G., & Maffioli, F. (1982). On the worst‐case performance of some algorithms for the asymmetric traveling salesman problem. Networks, 12(1), 23–39.

Xiong, N., Wu, W., & Wu, C. (2017). An Improved Routing Optimization Algorithm Based on Travelling Salesman Problem for Social Networks. Sustainability, 9(6), 985.

Lin, B. L., Sun, X., & Salous, S. (2016). Solving travelling salesman problem with an improved hybrid genetic algorithm. Journal of computer and communications., 4(15), 98-106.

Xue-hui, L., Ye, Y., & Xia, L. (2008). Solving TSP with Shuffled Frog-Leaping Algorithm. In Proceedings - 8th International Conference on Intelligent Systems Design and Applications, ISDA 2008.

Sakiyama, T., & Arizono, I. (2017). Can the Agent with Limited Information Solve Travelling Salesman Problem?. Complexity, 2017, Article ID 9562125, 6 pages.

Papalitsas, C., Karakostas, P., Andronikos, T., Sioutas, S., & Giannakis, K. (2018). Combinatorial GVNS (General Variable Neighborhood Search) Optimization for Dynamic Garbage Collection. Algorithms, 11(4), 38.

Bostamam, J. M., & Othman, Z. (2016). Hybrid water flow-like algorithm with Tabu search for traveling salesman problem. In AIP Conference Proceedings (Vol. 1761). American Institute of Physics.

Bingüler, A. Hande Erol and Bulkan, Serol (2015). New Variable Neighborhood Search Structure for Travelling Salesman Problems. British Journal of Mathematics & Computer Science 6(5): 422-434, 2015, Article no.BJMCS.2015.088.

Zia, M., Cakir, Z., & Seker, D. Z. (2018). Spatial Transformation of Equality–Generalized Travelling Salesman Problem to Travelling Salesman Problem. ISPRS International Journal of Geo-Information, 7(3), 115.

Yang, X.-S. (2010). Nature-Inspired Metaheuristic Algorithms. Nature-Inspired Metaheuristic Algorithms Second Edition (p. 115).

Dréo, J., Pétrowski, A., & Taillard, E. (2006). Metaheuristics for Hard Optimization. Vasa (p. 382).

Alzaqebah, M., & Abdullah, S. (2015). Hybrid bee colony optimization for examination timetabling problems. Computers and Operations Research, 54, 142–154.

Wang, X., Mu, A. & Zhu, S. (2013) ISPO: A New Way to Solve Traveling Salesman Problem. Intelligent Control and Automation, 4, 122-125.

Yang, F. C., & Wang, Y. P. (2007). Water flow-like algorithm for object grouping problems. Journal of the Chinese Institute of Industrial Engineers, 24(6), 475–488.

Wu, T.H., Chung, S.H., And Chang, C.C., "A Water Flow-Like Algorithm For Manufacturing Cell Formation Problems". European Journal Of Operational Research, Vol. 205, No. 2, pp. 346-360, 2010.

Shahnazari-Shahrezaei, P., Tavakkoli-Moghaddam, R., Azarkish, M., & Sadeghnejad-Barkousaraie, A. (2012). a Differential Evolution Algorithm Developed for a Nurse Scheduling Problem. South African Journal of Industrial Engineering, 23(3), 68–90.

Srour, A., (2014). Water flow-like algorithm for travelling salesman problem and web service selection problem,” Ph.D thesis, University Kebangsaan Malaysia.

Abdullah, S., Burke, E. K., & Mccollum, B. (2005, July). An investigation of variable neighbourhood search for university course timetabling. In The 2nd Multidisciplinary International Conference on Scheduling: Theory and Applications (MISTA) (pp. 413-427).

Burke, E. K., Causmaecker, P. D., Petrovic, S., & Berghe, G. V. (2001). Fitness evaluation for nurse scheduling problems. Proceedings of the 2001 Congress on Evolutionary Computation (IEEE Cat. No.01TH8546), 2, 1139–1146.

Hansen, P., & Mladenovic, N. (1997). Variable neighbourhood search. Computers and Operations Research, 24(11), 1097–1100.

Crispim, J., & Brandao, J. (2001, July). Reactive tabu search and variable neighborhood descent applied to the vehicle routing problem with backhauls. In Proceedings of the 4th Metaheuristics International Conference, Porto (Vol. 1101, pp. 631-636).

Crainic, T., & Centre for Research on Transportation (Montréal, Québec). (2003). Parallel variable neighborhood search for the p-median. Montréal: Groupe d'études et de recherche en analyse des décisions.

Othman, Z.A., Al-Dhwai, NH, Srour, A., Yi, Wudi., “Water Flow-Like Algorithm with Simulated Annealing for Travelling Salesman Problems’’. Int. J. Advanced Science, Engineering and Information Technology, Vol. 7, No. 2, pp. 669-675, 2017.

Srour, A., Othman, Z. A., & Hamdan, A. R. (2014). A water flow-like algorithm for the travelling salesman problem. Advances in Computer Engineering, 2014, 1–14.

Hansen, P., Mladenović, N., & Moreno Pérez, J. A. (2008). Variable neighbourhood search: Methods and applications. 4OR, 6(4), 319–360.

Hansen, P., Mladenović, N., & Moreno Pérez, J. A. (2010). Variable neighbourhood search: Methods and applications. Annals of Operations Research, 175(1), 367–407.

Chen, S., Chen, R., & Gao, J. (2017). A Modified Harmony Search Algorithm for Solving the Dynamic Vehicle Routing Problem with Time Windows. Scientific Programming, 2017, Article ID1021432, 13 pages

Rincon-Garcia, N., Waterson, B., & Cherrett, T. (2017). A hybrid metaheuristic for the time-dependent vehicle routing problem with hard time windows. International Journal of Industrial Engineering Computations, 8(1), 141-160.

Othman, Z. A., Srour, A. I., Hamdan, A. R., & Ling, P. Y. (2013). Performance water flow-like algorithm for TSP by improving its local search. International Journal of Advancements in Computing Technology, 5(14), 126.

Cruz-Chávez, M. A., Martínez-Oropeza, A., del Carmen Peralta-Abarca, J., Cruz-Rosales, M. H., & Martínez-Rangel, M. (2014, June). Variable Neighborhood Search for Non-deterministic Problems. In International Conference on Artificial Intelligence and Soft Computing (pp. 468-478). Springer, Cham.

Kralev, V. (2017). An Analysis of a Recursive and an Iterative Algorithm for Generating Permutations Modified for Travelling Salesman Problem. International Journal on Advanced Science, Engineering and Information Technology, 7(5), 1685-1692.




DOI: http://dx.doi.org/10.18517/ijaseit.9.5.7957

Refbacks

  • There are currently no refbacks.



Published by INSIGHT - Indonesian Society for Knowledge and Human Development