Bi-objective covering salesman problem with uncertainty
DOI:
https://doi.org/10.31181/jdaic10015082023tKeywords:
covering salesman problem, memetic algorithm, local search, interval type 2 fuzzyAbstract
Humanitarian relief transportation and mass fatality management activities are the most strenuous tasks after a natural or artificial disaster. A feasible and realistic transport model is essential for accomplishing the tasks in a planned way. Covering Salesman Problem (CSP) is a variant of Traveling Salesman Problem (TSP) which has been used in many application areas, including disaster management. In this paper, we consider a bi-objective CSP in an uncertain environment where Interval Type 2 fuzzy numbers represent the costs of the edges. A new local search technique is introduced in the memetic algorithm, which has been used to solve the problem. A computational experiment on a set of instances indicates the effectiveness of the introduced local search technique along with the proposed methodology.
Downloads
References
Arkin, E.M., & Hassin, R. (1994). Approximation algorithms for the geometric covering salesman problem. Discrete Applied Mathematics, 55(3), 197-218.
Avila-Torres, P., Caballero, R., Litvinchev, I., Lopez-Irarragorri, F., & Vasant, P. (2018). The urban transport planning with uncertainty in demand and travel time: a comparison of two defuzzification methods. Journal of Ambient Intelligence and Humanized Computing, 9(3), 843-856.
Bao, X., & Liu, Z. (2012). An improved approximation algorithm for the clustered traveling salesman problem. Information Processing Letters, 112(23), 908-910.
Biswas, A., Tripathy, S. P., & Pal, T. (2022). On multi-objective covering salesman problem. Neural Computing and Applications, 34(24), 22127–22140.
Chiao, K.P. (2012). Trapezoidal interval type-2 fuzzy set extension of analytic hierarchy process. 2012 IEEE International Conference on Fuzzy Systems (pp. 1-8). Brisbane, QLD, Australia: IEEE.
Current, J. R., & Schilling, D. A. (1989). The covering salesman problem. Transportation science, 23(3), 208-213.
Du, S., Zhang, H., Xu, H., Yang, J., & Tu, O. (2019). To make the travel healthier: a new tourism personalized route recommendation algorithm. Journal of Ambient Intelligence and Humanized Computing, 10, 3551–3562.
Gendreau, M., Laporte, G., & Semet, F. (1997). The covering tour problem. Operations Research, 45(4), 568-576.
Ghafurian, S., & Javadian, N. (2011). An ant colony algorithm for solving fixed destination multi-depot multiple traveling salesmen problems. Applied Soft Computing, 11(1), 1256-1262.
Golden, B., Naji-Azimi, Z., Raghavan, S., Salari, M., & Toth, P. (2012). The generalized covering salesman problem. INFORMS Journal on Computing, 24(4), 534-553.
Gutin, G., & Punnen, A. P. (Eds.). (2006). The traveling salesman problem and its variations (Vol. 12). Springer Science & Business Media.
Jensen, R. A. (1999). Mass fatality and casualty incidents: a field guide. CRC Press.
Karapetyan, D., & Gutin, G. (2012). Efficient local search algorithms for known and new neighborhoods for the generalized traveling salesman problem. European Journal of Operational Research, 219(2), 234-251.
Karnik, N.N., & Mendel, J.M. (2001). Centroid of a type-2 fuzzy set. Information Sciences, 132(1-4), 195-220.
Kim, I.Y., & de Weck, O. (2004). Adaptive weighted sum method for multiobjective optimization. In 10th AIAA/ISSMO multidisciplinary analysis and optimization conference (p. 4322). Albany, New York: American Institute of Aeronautics and Astronautics.
Laporte, G., Asef-Vaziri, A., & Sriskandarajah, C. (1996). Some applications of the generalized travelling salesman problem. Journal of the Operational Research Society, 47(12), 1461-1467.
Lee, L.W., & Chen, S.M. (2008). A new method for fuzzy multiple attributes group decision-making based on the arithmetic operations of interval type-2 fuzzy sets. International Conference on Machine Learning and Cybernetics, vol 6, (pp. 3084-3089). Kunming, China: IEEE.
Lin, S., & Kernighan, B.W. (1973). An effective heuristic algorithm for the traveling-salesman problem. Operations research, 21(2), 498-516.
Marler, R.T., & Arora, J. S. (2010). The weighted sum method for multi-objective optimization: new insights. Structural and multidisciplinary optimization, 41(6), 853-862.
Mendel, J. M. (2011). On centroid calculations for type-2 fuzzy sets. Applied and Computational Mathematics, 10(1), 88-96.
Ni, Y., Shi, Q., & Wei, Z. (2017). Optimizing influence diffusion in a social network with fuzzy costs for targeting nodes. Journal of Ambient Intelligence and Humanized Computing, 8(5), 819-826.
Ozbaygin, G., Yaman, H., & Karasan, O.E. (2016). Time constrained maximal covering salesman problem with weighted demands and partial coverage. Computers & Operations Research, 76, 226-237.
Patterson, R., & Rolland, E. (2003). The cardinality constrained covering traveling salesman problem. Computers & Operations Research, 30(1), 97-116.
Qin, J., & Liu, X. (2015). Multi-attribute group decision making using combined ranking value under interval type-2 fuzzy environment. Information Sciences, 297, 293-315.
Rainer, J. J., Cobos-Guzman, S., & Galán, R. (2018). Decision making algorithm for an autonomous guide-robot using fuzzy logic. Journal of Ambient Intelligence and Humanized Computing, 9(4), 1177-1189.
Salari, M., Reihaneh, M., & Sabbagh, M.S. (2015). Combining ant colony optimization algorithm and dynamic programming technique for solving the covering salesman problem. Computers & Industrial Engineering, 83, 244-251.
Shaelaie, M.H., Salari, M., & Naji-Azimi, Z. (2014). The generalized covering traveling salesman problem. Applied Soft Computing, 24, 867-878.
Stanimirovic, I.P., Zlatanovic, M.L., & Petkovic, M.D. (2011). On the linear weighted sum method for multi-objective optimization. Facta Universitatis, Series: Mathematics and Informatics, 26(4), 49-63.
Tripathy, S. P., Biswas, A., & Pal, T. (2021). A multi-objective covering salesman problem with 2-coverage. Applied Soft Computing, 113, 108024.
Tripathy, S.P., Tulshyan, A., Kar, S., & Pal, T. (2017). A Metameric Genetic Algorithm with New Operator for Covering Salesman Problem with Full Coverage. International Journal of Control Theory and Applications, 10(7), 245-252.
Wang, R., Zhou, J., Yi, X., & Pantelous, A.A. (2019). Solving the green-fuzzy vehicle routing problem using a revised hybrid intelligent algorithm. Journal of Ambient Intelligence and Humanized Computing, 10(1), 321-332.
Wen, X., Xu, Y., & Zhang, H. (2012). Online traveling salesman problem with deadline and advanced information. Computers & Industrial Engineering, 63(4), 1048-1053.
Wu, D., & Mendel, J. M. (2011). On the continuity of type-1 and interval type-2 fuzzy logic systems. IEEE Transactions on Fuzzy Systems, 19(1), 179-192.
Wu, L., Ma, W., Yang, Y., & Wang, K. (2019). A competitive analysis approach for route choice with uncertain travel times and blocked nodes. Journal of Ambient Intelligence and Humanized Computing, 10(1), 345-355.
Zhang, C., Wang, C., Zhang, Z., & Tian, D. (2019). A novel technique for multiple attribute group decision making in interval-valued hesitant fuzzy environments with incomplete weight information. Journal of Ambient Intelligence and Humanized Computing, 10(6), 2417-2433.
Zhao, F., Li, S., Sun, J., & Mei, D. (2009). Genetic algorithm for the one-commodity pickup-and-delivery traveling salesman problem. Computers & Industrial Engineering, 56(4), 1642-1648.
All site content, except where otherwise noted, is licensed under the 