Imprecise covering ring star problem

Anupam  Mukherjee; Partha Sarathi  Barma; Joydeep  Dutta; Sujit Das; Dragan Pamucar

doi:10.31181/dmame0323062022s

Anupam Mukherjee School of Applied Science and Humanities, Haldia Institute of Technology, Haldia, India
Partha Sarathi Barma Center for Distance and Online Education, University of Burdwan, Burdwan, India
Joydeep Dutta Department of Computer Science Kazi Nazrul University, Asansol, India
Sujit Das National Institute of Technology Warangal, India
Dragan Pamucar Department of Operations Research and Statistics, Faculty of Organizational Sciences, University of Belgrade, Belgrade, Serbia https://orcid.org/0000-0001-8522-1942

DOI: https://doi.org/10.31181/dmame0323062022s

Keywords: Ring Star Problem · Median Cycle Problem · Covering Salesman Problem · Genetic Algorithm

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

Download data is not yet available.

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.

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.

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.

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, 15(4), 1-10.

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.

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.

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.

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., (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.

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.

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

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, 6(1), 97-102.