| Title:
|
Stochastic queue core problem with an efficient length on a tree network (English) |
| Author:
|
Fathali, Jafar |
| Author:
|
Zaferanieh, Mehdi |
| Language:
|
English |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 (print) |
| ISSN:
|
1805-949X (online) |
| Volume:
|
61 |
| Issue:
|
2 |
| Year:
|
2025 |
| Pages:
|
185-201 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
location theory |
| Keyword:
|
core |
| Keyword:
|
$M/G/1$ queue |
| MSC:
|
60K25 |
| MSC:
|
90Bxx |
| DOI:
|
10.14736/kyb-2025-2-0185 |
| . |
| Date available:
|
2025-06-02T09:49:33Z |
| Last updated:
|
2025-06-02 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/152987 |
| . |
| Reference:
|
[1] Zaferanieh, M. Abareshi abd M.: A bi-level capacitated p-median facility location problem with the most likely allocation solution..Transport. Res. Part B: Methodological 123 (2019), 1-20. |
| Reference:
|
[2] Abouee-Mehrizi, H., Baron, O.: State-dependent m/g/1 queueing systems..Queueing Systems 82 (2016), 121-148. MR 3457013, |
| Reference:
|
[3] Adeleke, O. J., Olukanni, D. O.: Facility location problems: models, techniques, and applications in waste management..Recycling 5 (2020), 10. |
| Reference:
|
[4] Alstrup, S., Lauridsen, P. W., Sommerlund, P., Thorup, M.: Finding cores of limited length..In: Algorithms and Data Structures: 5th International Workshop, WADS'97, Halifax 1997, Proceedings 5, Springer, pp. 45-54. |
| Reference:
|
[5] Avella, P., Boccia, M., Sforza, A., Vasilev, snd I.: A branch-and-cut algorithm for the median-path problem..Comput. Optim. Appl. 32 (2005), 215-230. MR 2207845, |
| Reference:
|
[6] Batta, R., Berman, O.: A location model for a facility operating as an m/g/k queue..Networks 19 (1989), 717-728. MR 1013756, |
| Reference:
|
[7] Becker, R. I., Chang, Y. I., Lari, I., Scozzari, A., Storchi, G.: Finding the l-core of a tree..Discrete Appl. Math. 118 (2002), 25-42. MR 1888547, |
| Reference:
|
[8] Berman, 0., Drezner, Z.: The multiple server location problem..J. Oper. Res. Soc. 58 (2007), 91-99. |
| Reference:
|
[9] Berman, 0., Krass, D., Wang, J.: Locating service facilities to reduce lost demand..IIE Trans. 38 (2006), 933-946. |
| Reference:
|
[10] Berman, 0., Larson, R. C., Chiu, S. S.: Optimal server location on a network operating as an m/g/1 queue..Oper. Ress 33 (1985), 746-771. MR 0797884, |
| Reference:
|
[11] Berman, 0., Larson, R. C., Parkan, C.: The stochastic queue p-median problem..Transport. Sci. 21 (1987), 207-216. MR 0909467, |
| Reference:
|
[12] Berman, 0., Mandowsky, R. R.: Location-allocation on congested networks..Europ. J. Oper. Ress 26 (1986), 238-250. MR 0852294, |
| Reference:
|
[13] Chen, C., Yao, B., Chen, G., Tian, Z.: A queuing location allocation model for designing a capacitated bus garage system..Engrg. Optim. 54 (2022), 709-726. MR 4410853, |
| Reference:
|
[14] Chiu, S. S., Berman, O., Larson, R. C.: Locating a mobile server queueing facility on a tree network..Management Sci. 31 (1985), 764-772. MR 0793874, |
| Reference:
|
[15] Fathali, J., Nazari, M., Mahdvar, K.: Semi-obnoxious backup 2-median problem on a tree..J. Appl. Res. Industr. Engrg. 8 (2021), 159-168. |
| Reference:
|
[16] Fathali, J., Zaferanieh, M.: The balanced 2-median and 2-maxian problems on a tree..J. Combinat. Optim. 45 (2023), 69. MR 4554039, |
| Reference:
|
[17] Gavish, B., Sridhar, S.: Computing the 2-median on tree networks in $O(n\log n)$ time..Networks 26 (1995), 305-317. MR 1365024, |
| Reference:
|
[18] Goldman, A. J.: Optimal center location in simple networks..Transport. Sci. 5 (1971), 212-221. MR 0359738, |
| Reference:
|
[19] Hedetniemi, S. M., Cockayne, E., Hedetniemi, S.: Linear algorithms for finding the jordan center and path center of a tree..Transport. Sci. 15 (1981), 98-114. MR 0639598, |
| Reference:
|
[20] Kariv, 0., Hakimi, S. L.: An algorithmic approach to network location problems. i: The p-centers..SIAM J. Appl. Math. 37 (1979), 513-538. MR 0549138, |
| Reference:
|
[21] Kong, Y. X., Shi, G. Y., Wu, R. J., Zhang, Y. C.: k-core: Theories and applications..Physics Rep. 832 (2019), 1-32. MR 4035043, |
| Reference:
|
[22] Kovacs, G., Spens, K. M.: Humanitarian logistics in disaster relief operations..Int. J. Phys. Distribut. Logist. Management 37 (2007), 99-114. |
| Reference:
|
[23] Mohammadi, M., Jolai, F., Rostami, H.: An m/m/c queue model for hub covering location problem..Math. Computer Modell. 54 (2011), 2623-2638. MR 2841808, |
| Reference:
|
[24] Morgan, C. A., Slater, P. J.: A linear algorithm for a core of a tree..J. Algorithms 1 (1980), 247-258. MR 0604866, |
| Reference:
|
[25] Morgan, S. A., Agee, N. H.: Mobile healthcare..Frontiers Health Services Management 29 (2012), 3-10. |
| Reference:
|
[26] Moshtagh, M., Fathali, J., Smith, J. M.: The stochastic queue core problem, evacuation networks, and state-dependent queues..Europ. J. Oper. Res. 269 (2018), 730-748. MR 3790048, |
| Reference:
|
[27] Moshtagh, M., Fathali, J., Smith, J. M., Mahdavi-Amiri, N.: Finding an optimal core on a tree network with m/g/c/c state-dependent queues..Math. Methods Oper. Res. 89 (2019), 115-142. MR 3918542, |
| Reference:
|
[28] Owen, S. H., Daskin, M. S.: Strategic facility location: A review..Europ. J. Oper. Res. 111 (1998), 423-447. |
| Reference:
|
[29] Ozdamar, L., Ekinci, E., Kucukyazici, B.: Emergency logistics planning in natural disasters..Ann. Oper. Res. 129 (2004), 217-245. MR 2072300, |
| Reference:
|
[30] Pourmohammadi, P., Tavakkoli-Moghaddam, R., Rahimi, Y., Triki, C.: 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. MR 4581626, |
| Reference:
|
[31] Slater, P. J.: Locating central paths in a graph..Transport. Sci. 16 (1982), 1-18. |
| Reference:
|
[32] Tamir, A.: An $O(pn^2)$ algorithm for the p-median and related problems on tree graphs..Oper. Res. Lett. 19 (1996), 59-64. MR 1405743, |
| Reference:
|
[33] Tavakkoli-Moghaddam, R., Vazifeh-Noshafagh, S., A., A., Taleizadeh, Hajipour, V., Mahmoudi, A.: Pricing and location decisions in multi-objective facility location problem with m/m/m/k queuing systems..Engrg. Optim. 49 (2017), 136-160. MR 3567728, |
| Reference:
|
[34] Wang, Q., Batta, R., Rump, C. M.: Algorithms for a facility location problem with stochastic customer demand and immobile servers..Ann. Oper. Res. 111 (2002), 17-34. MR 1954660, 10.1023/A:1020961732667 |
| Reference:
|
[35] Zaferanieh, M., Abareshi, M., Fathali, J.: The minimum information approach to the uncapacitated p-median facility location problem..Transport. Lett. 14 (2022), 307-316. |
| Reference:
|
[36] Zaferanieh, M., J, Fathali: Finding a core of a tree with pos/neg weight..Math. Methods Oper. Res. 76 (2012), 147-160. MR 2972611, |
| Reference:
|
[37] Zaferanieh, M., Sadra, M., Basirat, T.: P-facility capacitated location problem with customer equilibrium decisions: a recreational case study in Mazandaran province..J. Modell. Management 19 (2024), 1883-1906. |
| . |
