On Enhanced Intelligent Water Drops Algorithm for Travelling Salesman Problem under Uncertain Paradigm

Halder, Swapna; Sharma, Haresh Kumar; Biswas, Arindam; Prentkovskis, Olegas; Majumder, Saibal; Skačkauskas, Paulius

doi:10.2478/ttj-2023-0019

Abstract

Travelling salesman problem (TSP) is a well known combinatorial optimization problem which has drawn colossal attention due to its eclectic range of applications. In this article, we have proposed two modified versions of intelligent water drops (IWD) algorithm. The first one is the enhanced IWD (e-IWD) algorithm to solve single objective TSP. In the second modification, e-IWD algorithm has been extended to enhanced multi-objective IWD(e-MIWD) algorithm for solving multi-objective TSP. In order to achieve a better exploration capability in both of the proposed algorithms, the soil and velocity parameters of a randomly selected water drop are updated after every iteration of the algorithm when it traverses all the intermediate vertices for a tour. The proposed algorithms have been compared with some other existing similar algorithms on different benchmark instances of TSPs. Furthermore, we have addressed the TSP for both single and multiple objectives under uncertain environment.

References

1. Alijla B O, Wong, L.-P., Lim, C.P., Khader, A.T. and Al-Betar, M.A. (2014) A modified intelligent water drops algorithm and its application to optimization problems. Expert Systems with Applications, 41(15), 6555–6569. DOI: 10.1016/j.eswa.2014.05.010.
Open DOI Search in Google Scholar Back to article
2. Alijla B O, Wong, L.-P., Lim, C.P., Khader, A.T. and Al-Betar, M.A. (2015) An ensemble of intelligent water drop algorithms and its application to optimization problems. Information Sciences, 325, 175–189. DOI: 10.1016/j.ins.2015.07.023.
Open DOI Search in Google Scholar Back to article
3. Chang, T.S., Wan, Y.W. and Ooi, W.T. (2009) A stochastic dynamic traveling salesman problem with hard time windows. European Journal of Operational Research, 198(3), 748–759. DOI: 10.1016/j.ejor.2008.10.012.
Open DOI Search in Google Scholar Back to article
4. Changdar, C., Mahapatra, G.S. and Pal, R.K. (2014) An efficient genetic algorithm for multi-objective solid travelling salesman problem under fuzziness. Swarm and Evolutionary Computation, 15, 27–37. DOI: 10.1016/j.swevo.2013.11.001.
Open DOI Search in Google Scholar Back to article
5. Çela, E., Deineko, V. and Woeginger, G. J. (2012) The x-and-y-axes travelling salesman problem. European Journal of Operational Research, 223(2), 333–345. DOI: 10.1016/j.ejor.2012.06.036.
Open DOI Search in Google Scholar Back to article
6. Colorni, A., Dorigo, M., Maniezzo, V. and Trubian, M. (1994) Ant system for job-shop scheduling. Belgian Journal of Operations Research, Statistics and Computer Science, 34(1), 39–53.
Search in Google Scholar Back to article
7. Dantzig, G., Fulkerson, R. and Johnson, S. (1954) Solution of a large-scale traveling salesman problem. Journal of the Operations Research Society of America, 2(4), 393–410.
Search in Google Scholar Back to article
8. Dorigo M and Di Caro G. (1999) Ant colony optimization: A new meta-heuristic. In: Proceedings of the 1999 Congress on Evolutionary Computation-CEC 99 (Cat. No. 99TH8406), 06–09 July 1999, Washington, DC, USA: IEEE, 1470–1477.
Search in Google Scholar Back to article
9. Eberhart, R. C. and Shi, Y. (2001) Particle swarm optimization: Developments, applications and resources. In: Proceedings of the 2001 Congress on Evolutionary Computation (Cat. No.01TH8546), 27–30 May, Seoul, Korea (South): IEEE, 81–86.
Search in Google Scholar Back to article
10. Eckenrode, R. T. (1965) Weighting multiple criteria. Management Science, 12(3), 180–192.
Search in Google Scholar Back to article
11. Erdoǧan, G., Cordeau, J.-F. and Laporte, G. (2010) The attractive traveling salesman problem. European Journal of Operational Research, 203(1), 59–69. DOI: 10.1016/j.ejor.2009.06.029.
Open DOI Search in Google Scholar Back to article
12. Focacci, F., Lodi, A. and Milano, M. (2002) A hybrid exact algorithm for the TSPTW. INFORMS Journal on Computing, 14(4), 403–417. DOI: 10.1287/ijoc.14.4.403.2827.
Open DOI Search in Google Scholar Back to article
13. Holland, J. H. (1975) Adaptation in neural and artificial system. Cambridge: University of Michigan Press.
Search in Google Scholar Back to article
14. Karaboga, D. (2005) An idea based on honey bee swarm for numerical optimization. Kayseri: Erciyes University Press.
Search in Google Scholar Back to article
15. Liu, B. (2009) Some research problems in uncertainty theory. Journal of Uncertain Systems, 3(1): 3–10.
Search in Google Scholar Back to article
16. Liu, B. (2007) Uncertainty theory (2nd ed.), Berlin: Springer-Verlag.
Search in Google Scholar Back to article
17. Liu, B. (2010) Uncertainty theory: A branch of mathematics for modeling human uncertainty (2nd ed.). Berlin: Springer-Verlag.
Search in Google Scholar Back to article
18. Liu, B. (2012) Why is there a need for uncertainty theory? Journal of Uncertain Systems, 6(1), 3–10.
Search in Google Scholar Back to article
19. Liu, B. (2015) Uncertainty theory (5th ed.). Beijing: Uncertainty Theory Laboratory.
Search in Google Scholar Back to article
20. Liu, Y. H. (2010) Different initial solution generators in genetic algorithms for solving the probabilistic traveling salesman problem. Applied Mathematics and Computation, 216(1), 125–137.DOI: 10.1016/j.amc.2010.01.021.
Open DOI Search in Google Scholar Back to article
21. Majumdar, J. and Bhunia, A. K. (2011) Genetic algorithm for asymmetric traveling salesman problem with imprecise travel times. Journal of Computational and Applied Mathematics, 235(9), 3063–3078. DOI: 10.1016/j.cam.2010.12.027.
Open DOI Search in Google Scholar Back to article
22. Majumder, S, Saha, B., Anand, P., Kar, S. and Pal, T. (2018b) Uncertainty based genetic algorithm with varying population for random fuzzy maximum flow problem. Expert Systems, 35(4), e12264. DOI: 10.1111/exsy.12264
Open DOI Search in Google Scholar Back to article
23. Majumder, S., Kar, S., and Pal, T. (2019) Uncertain multi-objective Chinese postman problem. Soft Computing, 23(22), 11557–11572. DOI: 10.11007/s00500-018-03697-3
Open DOI Search in Google Scholar Back to article
24. Majumder, S., Barma, P.S., Biswas, B., Banerjee, P., Kumar B., Kar, S., and Ziemba, P. (2022) On multi-objective minimum spanning tree problem under uncertain paradigm. Symmetry, 14(1), 106. DOI: 10.3390/sym14010106
Open DOI Search in Google Scholar Back to article
25. Mestria, M., Ochi, L. S. and Martins, S. L. (2013) GRASP with path relinking for the symmetric Euclidean clustered traveling salesman problem. Computers and Operations Research, 40(12), 3218–3229. DOI: 10.1016/j.cor.2012.10.001.
Open DOI Search in Google Scholar Back to article
26. Moon, C., Ki, J., Choi, G., and Seo, Y. (2002) An efficient genetic algorithm for the traveling salesman problem with precedence constraints. European Journal of Operational Research, 140(3), 606–617. DOI: 10.1016/S0377-2217(01)00227-2.
Open DOI Search in Google Scholar Back to article
27. Nagalakshmi, P., Harish, Y., Kranthi Kumar, R. and Chakravarthi, J. (2011) Combined economic and emission dispatch using intelligent water drops-continuous optimization algorithm. In: International conference on Recent Advancements in Electrical, Electronics and Control Engineering (ICONRAEeCE), 15–17 December 2011; Sivakasi, India: IEEE, 168–173.
Search in Google Scholar Back to article
28. Niu, S. H., Ong, S. K. and Nee, A. Y. C. (2011) An improved intelligent water drops algorithm for achieving optimal job-shop scheduling solutions. International Journal of Production Research, 50(15), 4192–4205. DOI: 10.1080/00207543.2011.600346.
Open DOI Search in Google Scholar Back to article
29. Noferesti, S. and Shah-Hosseini. H. (2012) A hybrid algorithm for solving steiner tree problem. International Journal of Computer Applications, 41(5), 14–20. DOI: 10.5120/5536-7584
Open DOI Search in Google Scholar Back to article
30. Rakke, J. G., Christiansen, M., Fagerholt, K. and Laportei, G. (2012). The traveling salesman problem with draft limits. Computers and Operations Research, 39(9), 2161–2167. DOI: 10.1016/j.cor.2011.10.025.
Open DOI Search in Google Scholar Back to article
31. Rego, C., Gamboa, D., Glover, F. and Osterman, C. (2011) Traveling salesman problem heuristics: Leading methods, implementations and latest advances. European Journal of Operational Research, 211(3), 427–441. DOI: 10.1016/j.ejor.2010.09.010.
Open DOI Search in Google Scholar Back to article
32. Samanlioglu, F., Ferrell, W.G. and Kurz, M.E. (2008) A memetic random-key genetic algorithm for a symmetric multi-objective traveling salesman problem. Computers & Industrial Engineering, 55(2), 439–449. DOI: 10.1016/j.cie.2008.01.005.
Open DOI Search in Google Scholar Back to article
33. Shah-Hosseini, H. (2007) Problem solving by intelligent water drops. In: The 2007 Congress on Evolutionary Computation (CEC 2007), 25–28 September 2007; Singapore: IEEE, 3226–3231.
Search in Google Scholar Back to article
34. Shah-Hosseini, H. (2008) Intelligent water drops algorithm: A new optimization method for solving the multiple knapsack problem. International Journal of Intelligent Computing and Cybernetics, 1(2), 193–212. DOI: 10.1108/17563780810874717.
Open DOI Search in Google Scholar Back to article
35. Shah-Hosseini, H. (2009a) Optimization with the nature-inspired intelligent water drops algorithm. In: Santos W. (eds.) Evolutionary Computations. Federal University of Pernambuco, Brazil, 297–320.
Search in Google Scholar Back to article
36. Shah-Hosseini, H. (2009b) The intelligent water drops algorithm: a nature-inspired swarm-based optimization algorithm. International Journal of Bio-Inspired Computation, 1(2), 71–79. DOI: 10.1504/IJBIC.2009.022775.
Open DOI Search in Google Scholar Back to article
37. Wang, Z., Guo, J., Zheng, M. and Yang, Y. (2015a) A new approach for uncertain multi-objective programming problem based on 𝒫E principle. Journal of Industrial and Management Optimization, 11(1), 13–26. DOI: 10.3934/jimo.2015.11.13.
Open DOI Search in Google Scholar Back to article
38. Wang, Z., Guo, J., Zheng, M. and Wang, Y. (2015b) Uncertain multi-objective traveling salesman problem. European Journal of Operational Research, 241(2), 478–489. DOI: 10.1016/j.ejor.2014.09.012.
Open DOI Search in Google Scholar Back to article
39. Zhou, J., Chen, L. and Wang, K. (2015) Path optimality conditions for minimum spanning tree problem with Uncertain edge weights. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 23(1), 49–71. DOI: 10.1142/S0218488515500038.
Open DOI Search in Google Scholar Back to article