Kybernetika 61 no. 2, 185-201, 2025

Stochastic queue core problem with an efficient length on a tree network

Jafar Fathali and Mehdi ZaferaniehDOI: 10.14736/kyb-2025-2-0185

Abstract:

In this paper, we consider a stochastic queue core ($SQC$) problem on a tree network, aiming to identify a path $P$, called the core, in an $M/G/1$ environment system. Let $T$ be a tree network, the $SQC$ problem on $T$ involves finding a core $P$, with an optimal length, that minimizes the total weighted travel time from all vertices to the core as well as the average response time to the customer demands. We assume that a mobile server traverses the core to provide services to customers, while customers move to their nearest vertex on the core to receive service. Some general properties of the $SQC$ problem on the tree network are represented. Then a polynomial time algorithm is proposed to solve this problem.

Keywords:

core, location theory, $M/G/1$ queue

Classification:

60K25, 90Bxx

paper.pdf

References:

  1. M. Abareshi abd M. Zaferanieh: A bi-level capacitated p-median facility location problem with the most likely allocation solution. Transport. Res. Part B: Methodological 123 (2019), 1-20.   DOI:10.1016/j.trb.2019.03.013
  2. H. Abouee-Mehrizi and O. Baron: State-dependent m/g/1 queueing systems. Queueing Systems 82 (2016), 121-148.   DOI:10.1007/s11134-015-9461-y
  3. O. J. Adeleke and D. O. Olukanni: Facility location problems: models, techniques, and applications in waste management. Recycling 5 (2020), 10.   DOI:10.3390/recycling5020010
  4. S. Alstrup, P. W. Lauridsen, P. Sommerlund and M. Thorup: Finding cores of limited length. In: Algorithms and Data Structures: 5th International Workshop, WADS'97, Halifax 1997, Proceedings 5, Springer, pp. 45-54.   CrossRef
  5. P. Avella, M. Boccia, A. Sforza and snd I. Vasilev: A branch-and-cut algorithm for the median-path problem. Comput. Optim. Appl. 32 (2005), 215-230.   DOI:10.1007/s10589-005-4800-2
  6. R. Batta and O. Berman: A location model for a facility operating as an m/g/k queue. Networks 19 (1989), 717-728.   DOI:10.1002/net.3230190609
  7. R. I. Becker, Y. I. Chang, I. Lari, A. Scozzari and G. Storchi: Finding the l-core of a tree. Discrete Appl. Math. 118 (2002), 25-42.   DOI:10.1016/S0166-218X(01)00254-2
  8. 0. Berman and Z. Drezner: The multiple server location problem. J. Oper. Res. Soc. 58 (2007), 91-99.   DOI:10.1007/s00020-007-1497-x
  9. 0. Berman, D. Krass and J. Wang: Locating service facilities to reduce lost demand. IIE Trans. 38 (2006), 933-946.   DOI:10.1080/07408170600856722
  10. 0. Berman, R. C. Larson and S. S. Chiu: Optimal server location on a network operating as an m/g/1 queue. Oper. Ress 33 (1985), 746-771.   DOI:10.1287/opre.33.4.746
  11. 0. Berman, R. C. Larson and C. Parkan: The stochastic queue p-median problem. Transport. Sci. 21 (1987), 207-216.   DOI:10.1287/trsc.21.3.207
  12. 0. Berman and R. R. Mandowsky: Location-allocation on congested networks. Europ. J. Oper. Ress 26 (1986), 238-250.   DOI:10.1016/0377-2217(86)90185-2
  13. C. Chen, B. Yao, G. Chen and Z. Tian: A queuing location allocation model for designing a capacitated bus garage system. Engrg. Optim. 54 (2022), 709-726.   DOI:10.1080/0305215X.2021.1897800
  14. S. S. Chiu, O. Berman and R. C. Larson: Locating a mobile server queueing facility on a tree network. Management Sci. 31 (1985), 764-772.   DOI:10.1287/mnsc.31.6.764
  15. J. Fathali, M. Nazari and K. Mahdvar: Semi-obnoxious backup 2-median problem on a tree. J. Appl. Res. Industr. Engrg. 8 (2021), 159-168.   CrossRef
  16. J. Fathali and M. Zaferanieh: The balanced 2-median and 2-maxian problems on a tree. J. Combinat. Optim. 45 (2023), 69.   DOI:10.1007/s10878-023-00997-9
  17. B. Gavish and S. Sridhar: Computing the 2-median on tree networks in $O(n\log n)$ time. Networks 26 (1995), 305-317.   DOI:10.1016/0168-1605(94)00136-T
  18. A. J. Goldman: Optimal center location in simple networks. Transport. Sci. 5 (1971), 212-221.   DOI:10.1287/trsc.5.2.212
  19. S. M. Hedetniemi, E. Cockayne and S. Hedetniemi: Linear algorithms for finding the jordan center and path center of a tree. Transport. Sci. 15 (1981), 98-114.   DOI:/10.1287/trsc.15.2.98
  20. 0. Kariv and S. L. Hakimi: An algorithmic approach to network location problems. i: The p-centers. SIAM J. Appl. Math. 37 (1979), 513-538.   DOI:10.1137/0137040
  21. Y. X. Kong, G. Y. Shi, R. J. Wu and Y. C. Zhang: k-core: Theories and applications. Physics Rep. 832 (2019), 1-32.   DOI:10.1007/s40274-019-6058-4
  22. G. Kovacs and K. M. Spens: Humanitarian logistics in disaster relief operations. Int. J. Phys. Distribut. Logist. Management 37 (2007), 99-114.   DOI:10.1108/09600030710734820
  23. M. Mohammadi, F. Jolai and H. Rostami: An m/m/c queue model for hub covering location problem. Math. Computer Modell. 54 (2011), 2623-2638.   DOI:10.1016/j.mcm.2011.06.038
  24. C. A. Morgan and P. J. Slater: A linear algorithm for a core of a tree. J. Algorithms 1 (1980), 247-258.   DOI:10.1016/0196-6774(80)90012-7
  25. S. A. Morgan and N. H. Agee: Mobile healthcare. Frontiers Health Services Management 29 (2012), 3-10.   DOI:10.1097/01974520-201210000-00002
  26. M. Moshtagh, J. Fathali and J. M. Smith: The stochastic queue core problem, evacuation networks, and state-dependent queues. Europ. J. Oper. Res. 269 (2018), 730-748.   DOI:10.1016/j.ejor.2018.02.026
  27. M. Moshtagh, J. Fathali, J. M. Smith and N. Mahdavi-Amiri: Finding an optimal core on a tree network with m/g/c/c state-dependent queues. Math. Methods Oper. Res. 89 (2019), 115-142.   DOI:10.1007/s00186-018-0651-3
  28. S. H. Owen and M. S. Daskin: Strategic facility location: A review. Europ. J. Oper. Res. 111 (1998), 423-447.   DOI:10.1016/S0377-2217(98)00186-6
  29. L. Ozdamar, E. Ekinci and B. Kucukyazici: Emergency logistics planning in natural disasters. Ann. Oper. Res. 129 (2004), 217-245.   DOI:10.1023/b:anor.0000030690.27939.39
  30. P. Pourmohammadi, R. Tavakkoli-Moghaddam, Y. Rahimi and C. Triki: Solving a hub location routing problem with a queue system under social responsibility by a fuzzy meta-heuristic algorithm. Ann. Oper. Res. 324 (2023), 1099-1128.   DOI:10.1007/s10479-021-04299-3
  31. P. J. Slater: Locating central paths in a graph. Transport. Sci. 16 (1982), 1-18.   CrossRef
  32. A. Tamir: An $O(pn^2)$ algorithm for the p-median and related problems on tree graphs. Oper. Res. Lett. 19 (1996), 59-64.   DOI:10.1016/0167-6377(96)00021-1
  33. R. Tavakkoli-Moghaddam, S. Vazifeh-Noshafagh, A. A., Taleizadeh, V. Hajipour and A. Mahmoudi: Pricing and location decisions in multi-objective facility location problem with m/m/m/k queuing systems. Engrg. Optim. 49 (2017), 136-160.   DOI:10.1080/0305215x.2016.1163630
  34. Q. Wang, R. Batta and C. M. Rump: Algorithms for a facility location problem with stochastic customer demand and immobile servers. Ann. Oper. Res. 111 (2002), 17-34.   CrossRef
  35. M. Zaferanieh, M. Abareshi and J. Fathali: The minimum information approach to the uncapacitated p-median facility location problem. Transport. Lett. 14 (2022), 307-316.   DOI:10.1080/19427867.2020.1864595
  36. M. Zaferanieh, J and Fathali: Finding a core of a tree with pos/neg weight. Math. Methods Oper. Res. 76 (2012), 147-160.   DOI10.1007/s00186-012-0394-5:
  37. M. Zaferanieh, M. Sadra and T. Basirat: P-facility capacitated location problem with customer equilibrium decisions: a recreational case study in Mazandaran province. J. Modell. Management 19 (2024), 1883-1906.   DOI:10.1002/ange.19060194415