Imprecise covering ring star problem
Abstract
In this paper, we formulate and solve an Imprecise Covering Ring Star Problem (ICRSP), which is a generalization of the Ring Star Problem (RSP). Here the objective of this problem is to find a subset of nodes in a network to minimize the sum of routing costs of interconnecting cycle and assignment costs of the nodes which are out of cycle, to their nearest concentrators such that no assigned node exceeds a predetermined distance (say, covering distance) from the concentrators. The covering distance, as well as the routing and assignments costs, are considered as fuzzy in the proposed ICRSP. A Modified Genetic Algorithm (MGA) is developed and used to solve this model for different confidence levels depending on the corresponding imprecise parameters, reducing it to deterministic form with fuzzy possibility and necessity approaches. Some comparisons with existing benchmark problems are made to justify the performance of the algorithm. As individual cases, some practical ICRSPs are also solved and presented numerically.
Downloads
References
Baldacci. R., Dell’Amico. M. & González. J.S., (2007) The capacitated m-ring star problem, Operations Research 55 (6) 1147-1162. DOI: https://doi.org/10.1287/opre.1070.0432
Baldacci. R. & Dell’Amico. (2010) M., Heuristic algorithms for the multi-depot ring star problem, European Journal of Operational Research 203 (1) 270-281. DOI: https://doi.org/10.1016/j.ejor.2009.07.026
Baldacci. R., Hill. A., Hoshino. E.A. & Lim. A., (2017) Pricing Strategies for Capacitated Ring-Star Problems based on Dynamic Programming Algorithms, European Journal of Operational Research, 262 (3) 879-893. DOI: https://doi.org/10.1016/j.ejor.2017.04.025
Barma, P.S., Dutta, J., Mukherjee, A., Kar, S., (2021) A Multi-Objective Ring Star Vehicle Routing Problem for Perishable Items, Journal of Ambient Intelligence and Humanized Computing, (13) 2355-2380.
Calvete, H.I., Galé, C., & J.A. Iranzo, (2013) An efficient evolutionary algorithm for the ring star problem. European Journal of Operational Research 231 22–33. DOI: https://doi.org/10.1016/j.ejor.2013.05.013
Chakraborty, D., Jana, D. K., & Roy, T. K., (2015) A new approach to solve multi-objective multi-choice multi-item Atanassov's intuitionistic Fuzzy Transportation Problem using chance operator. Journal of Intelligence and Fuzzy Systems 28(2), 843-865.
Current, J.R., & Schilling, D.A., (1989), The covering salesman problem. Transportation Science, 23(3) 208-213. DOI: https://doi.org/10.1287/trsc.23.3.208
Dias, T.C.S., de Sousa Filho, G.F., Macambira, E.M., Cabral, L.A.F., & Fampa, M.H.C., (2006) An efficient heuristic for the ring star problem, in: C. Alvarez, M. Serna (Eds.), Experimental Algorithms, Lecture Notes in Computer Science, Springer Verlag, pp. 24-35 (No. 4007). DOI: https://doi.org/10.1007/11764298_3
Golden, B.L., Naji-Azimi, Z., Raghavan, S., Salari, M., & Toth, P. (2012), The generalized covering salesman problem. INFORMS Journal on Computing, 24(4), 34-553. DOI: https://doi.org/10.1287/ijoc.1110.0480
Helsgaun, K., (2000) Effective implementation of the Lin-Kerninghan traveling salesman heuristic, European Journal of Operational Research 126 106–130. DOI: https://doi.org/10.1016/S0377-2217(99)00284-2
Kedad-Sidhoum, S. & Nguyen, V.H., (2010) An exact algorithm for solving the ring star problem, Optimization 59 (1) 125-140. DOI: https://doi.org/10.1080/02331930903500332
Kundu, P., Kar, M. B., Kar, S., Pal, T. & Maiti, M., (2015) A solid transportation model with product blending and parameters as rough variables, Soft Computing, , 1-10. DOI: https://doi.org/10.1007/s00500-015-1941-9
Labbé, M., Laporte, G., Rodríguez Martín, I., & Salazar González, J.J., (1999) The median cycle problem, Working paper, CRT-99-29, Université de Montréal.
Labbé , M. Laporte, G., Rodríguez Martín, I., & Salazar González, J.J., (2004) The ring star problem: Polyhedral analysis and exact algorithm, Networks 43 (3) 177-189. DOI: https://doi.org/10.1002/net.10114
Lan, G. & DePuy, G. W., (2006) On the effectiveness of incorporating randomness and memory into a multi-start metaheuristic with application to the Set Covering Problem, Computers & Industrial Engineering 51, 362-374. DOI: https://doi.org/10.1016/j.cie.2006.08.002
Liu, Y. H., (2010) Different initial solution generators in genetic algorithms for solving the probabilistic travelling salesman problem, Applied Mathematics and Computation, 216, 125-137. DOI: https://doi.org/10.1016/j.amc.2010.01.021
Moreno J.A., Moreno Pérez, PJ.A., Moreno Vega, J.M., & Rodríguez Martín, I., (2003) Variable neighborhood tabu search and its application to the median cycle problem, European Journal of Operational Research 151 (2) 365-378. DOI: https://doi.org/10.1016/S0377-2217(02)00831-7
Mukherjee, A., Panigrahi, G., & Kar, S., (2019) Constrained covering solid travelling salesman problems in uncertain environment, J Ambient Intell Human Comput. 10, 125-141. DOI: https://doi.org/10.1007/s12652-017-0620-3
Mukherjee, A., Barma, P.S., Dutta, J., Panigrahi, G., Kar, S., & Maiti, M., (2019) A Modified Discrete Antlion Optimizer for the Ring Star Problem with Secondary Sub-depots, Neural Computing and Applications 32, 8143-8156.
Mukherjee, A., Barma, P.S., Dutta, J., Panigrahi, G., Kar, S., & Maiti, M., (2021) A Multi-objective Antlion Optimizer for the Ring Tree Problem with Secondary Sub-depots, Operational Research, https://doi.org/10.1007/s12351-021-00623-8
Naji-Azimi, Z., Salari, Toth, P., (2012) An integer linear programming based heuristic for the capacitated m-ring-star problem, European Journal of Operational Research 217 (1), 17-25. DOI: https://doi.org/10.1016/j.ejor.2011.08.026
Pramanik, S., Jana, D. K., Maiti, M., (2015) A fixed charge multi-objective solid transportation problem in random fuzzy environment, Journal of Intelligent and Fuzzy Systems, 28, 2643-2654. DOI: https://doi.org/10.3233/IFS-151542
Salari, M., & Naji-Azimi, Z., (2012) An integer programming-based local search for the covering salesman problem, Computers & Operations Research, 39, 2594-2602. DOI: https://doi.org/10.1016/j.cor.2012.01.004
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. DOI: https://doi.org/10.1016/j.cie.2015.02.019
Simonetti, L., Frota, Y., & de Souza C.C., (2011) The ring-star problem: a new integer programming formulation and a branch-and-cut algorithm, Discrete Applied Mathematics 159 (16) 1901-1914. DOI: https://doi.org/10.1016/j.dam.2011.01.015
Sundar, K. & Rathinam, S. (2017) Multiple depot ring star problem: a polyhedral study and an exact algorithm, J Glob Optim 67: 527. https://doi.org/10.1007/s10898-016-0431-7 DOI: https://doi.org/10.1007/s10898-016-0431-7
TSPLIB : http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsp
Zadeh, L.A., (1994) Fuzzy logic and soft computing: Issues, contentions and perspectives, In Proceedings of IIZUKA94 Third international conference on fuzzy logic, neural nets and soft computing (Vols. 1-2). Iizuka, Japan
Zhao, F., Sun, J., Li, S., & Liu., W, (2009) A Hybrid Genetic Algorithm for the Traveling Salesman Problem with Pickup and Delivery, International Journal of Automation and Computing, 06(1), 97-102. DOI: https://doi.org/10.1007/s11633-009-0097-4
