Imprecise covering ring star problem
DOI:
https://doi.org/10.31181/dmame0323062022sKeywords:
Ring Star Problem · Median Cycle Problem · Covering Salesman Problem · Genetic AlgorithmAbstract
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.
Baldacci. R. & Dell’Amico. (2010) M., Heuristic algorithms for the multi-depot ring star problem, European Journal of Operational Research 203 (1) 270-281.
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.
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.
Current, J.R., & Schilling, D.A., (1989). The covering salesman problem. Transportation Science, 23(3), 208-213.
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).
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.
Helsgaun, K., (2000) Effective implementation of the Lin-Kerninghan traveling salesman heuristic, European Journal of Operational Research 126 106–130.
Kedad-Sidhoum, S. & Nguyen, V.H., (2010) An exact algorithm for solving the ring star problem, Optimization 59 (1) 125-140.
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.
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.
Mukherjee, A., Panigrahi, G., & Kar, S., (2019) Constrained covering solid travelling salesman problems in uncertain environment, Journal of Ambient Intelligence and Humanized Computing, 10(2), 125-141.
Mukherjee, A., Barma, P.S., Dutta, J., Panigrahi, G., Kar, S., & Maiti, M., (2019a) 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.
Salari, M., & Naji-Azimi, Z. (2012) An integer programming-based local search for the covering salesman problem, Computers & Operations Research, 39, 2594-2602.
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.
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.
Sundar, K. & Rathinam, S. (2017) Multiple depot ring star problem: a polyhedral study and an exact algorithm, Journal of Global Optimization, 67, 527. 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
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2023 Decision Making: Applications in Management and Engineering
This work is licensed under a Creative Commons Attribution 4.0 International License.
