Imprecise covering ring star problem

  • 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 Logistics, University of Defence in Belgrade, Belgrade, Serbia
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. 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

Published
2022-06-23
How to Cite
Mukherjee, A., Barma, P. S., Dutta, J., Das, S., & Pamucar, D. (2022). Imprecise covering ring star problem. Decision Making: Applications in Management and Engineering. https://doi.org/10.31181/dmame0323062022s
Section
Regular articles