نوع مقاله : مقاله پژوهشی

نویسندگان

گروه ریاضی کاربردی، دانشکده علوم پایه مهندسی، دانشگاه صنعتی سهند، تبریز، ایران.

10.22105/dmor.2022.287402.1406

چکیده

در این مقاله، مساله مکانیابی مرکز-میانه مسیر استوار روی شبکههای درختی با وزنهای راسی بازهای یکسان برای هر دو مساله میانه مسیر و مرکز مسیر مورد بررسی قرار میگیرد. تابع هدف استفاده شده در این مقاله، جمع ساده تابع هدف مساله میانه مسیر و مرکز مسیر است. در کارهایی که در ادبیات تحقیقی صورت گرفته است، وزن رئوس برای هر دو مساله مکانیابی میانه مسیر و مرکز مسیر مجزا در نظر گرفته شده است. رویکرد استفاده شده برای محاسبه جواب استوار، رویکرد مینیماکس پشیمانی است. با استفاده از رویکرد مینیماکس پشیمانی، یک الگوریتم ترکیبیاتی با زمان اجرای O(n^5) برای محاسبه جواب استوار مساله مرکز-میانه مسیر استوار روی شبکههای درختی ارائه میشود. در این مقاله، با استفاده از سناریوهای بدترین حالت مسائل مرکز مسیر و میانه مسیر، سناریوهای بدترین حالت مساله مرکز-میانه مسیر استوار پیدا شده و با استفاده از آن، یک جواب استوار برای مساله مورد نظر محاسبه میشود.

کلیدواژه‌ها

موضوعات

عنوان مقاله [English]

The robust path centdian problem with interval vertex weights on tree networks

نویسندگان [English]

  • Fahimeh Baroughi
  • Soudabeh Seyyedi Ghomi

Department of Applied Mathematics, Faculty of Basic Sciences, Sahand University of Technology, Tabriz, Iran.

چکیده [English]

In this paper the robust path centdian problem is investigated on tree networks with the same interval vertex weights for the both path center and path median problems. The used objective function in this paper is the simple sum of path median and path center problems. In the past research works the vertex weights for the both path median and path center location problems are disjoint. The used approach to compute the robust solution is the minmax regret criterion. In this method for any selected path on the tree, the maximum value of regret is minimized for all possible events of vertex weights. Using the minmax regret criterion, an algorithm with O(n^5) time complexity is presented to obtain a robust solution of the robust path centdian problem on tree networks. In this paper using the worst case scenarios for the path median and path center we obtain the worst case scenarios of robust centdian problem. Then we obtain a robust solution for this problem.

کلیدواژه‌ها [English]

  • optimization
  • Path location
  • Centdian problem
  • Minmax regret criterion
Alstrup, S., Lauridsen, P. W., Sommerlund, P., & Thorup, M. (1997). Finding cores of limited length. Workshop on algorithms and data structures (pp. 45-54). Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-63307-3_47
Averbakh, I., & Berman, O. (1999). Algorithms for path medi-centers of a tree. Computers and operations research, ‎‎26(14), 1395-1409.‎‎
Averbakh, I., & Berman, O. (2000). Algorithms for the robust 1-center problem on a tree. European journal of operational research, 123(2), 292-302.
Averbakh, I., (2001). On the complexity of a class of combinatorial optimization problems with    uncertainty.  Mathematical programming90(2), 263-272.
Balasubramanian, S., Harini, S., & Rangan, C. P. (2009). Core and conditional core path of specified length in special classes of graphs. International workshop on algorithms and computation (pp. 262-273). Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-00202-1_23
Becker, R. I., Chang, Y. I., & Lari, I. & Scozzari, A. & Storchi, G. (2002a). Finding the l-core of a tree. Discrete applied mathematices, 118(1-2), ‎25-42.‎ https://doi.org/10.1016/S0166-218X(85)80002-0
Becker, R. I., Lari, I., Storchi, G., & Scozzari, A. (2002b). Efficient algorithms for finding the (k, l)-core of tree networks. Networks: an international journal40(4), 208-215.
Becker, RI. & Perl, Y. (1985). Finding the two-core of a tree. Discrete applied mathematices, ‎‎11(2), 103-113.‎‎ https://doi.org/10.1016/S0166-218X(85)80002-0
‎Ben-Tal, A., & Nemirovski, A. (2000). Robust solutions of linear programming problems contaminated with uncertain data. Mathematical programming88(3), 411-424.‎‎ https://doi.org/10.1007/PL00011380
Bertsimas, D., & Sim, M. (2004). The price of robustness. Operations research52(1), 35-53. https://doi.org/10.1287/opre.1030.0065
Bhattacharya, B., Hu, Y., Shi, Q., & Tamir, A. (2006). Optimal algorithms for the path, tree-shaped facility location problems in trees. Algorithmica55(4), 601-618.
Bhattacharya, B., Shi, Q., & Tamir, A. (2009). Optimal algorithms for the path/tree-shaped facility location problems in trees. Algorithmica, 55(4), 601-618.
Dvir, A., & Segal, M. (2008). The (k, l) coredian tree for ad hoc networks. 2008 the 28th international conference on distributed computing systems workshops (pp. 267-272). IEEE.
Ghahremani Nahr, J., & Bathaee, M. (2021). Design of a humanitarian logistics network considering the purchase contract. Journal of decisions and operations research6(3), 423-444. (In Persian). https://doi.org/10.22105/dmor.2021.270988.1311
Hakimi, S. L., Schmeichel, E. F., & Labbé, M. (1993). On locating path‐or tree‐shaped facilities on networks. Networks23(6), 543-555. https://doi.org/10.1002/net.3230230605
Hedetniemi, S. M., Cockayne, E. J., & Hedetniemi, S. T. (1981). Linear algorithms for finding the Jordan center and path center of a tree. Transportation science, 15(2), 98-114.
Hoseinpour, M., & Fakharzadeh Jahromi, A. (2019). The robust optimization model for providing Iranian diet for adjusting optimal glycemic load, Decisions and operations research4(1), 42-53. (In Persian). DOI: 10.22105/dmor.2019.86128.
Kouchaki Tajani, T., Mohtashami, A., & Amiri, M., & Ehtesham Rasi, R. (In Press). A robust possibilistic programming approach to design a comprehensive blood supply chain based on the ABO-RH index. Decisions and operations research. (In Persian).  DOI: 10.22105/dmor.2021.254819.1257
Kouvelis, P., & Yu, G. (1997). Robust discrete optimization and its applications. Kluwer academic Publishers, The Netherlands. DOI: 10.1007/97/978-1-4757-2620-6
Lari, I., Ricca, F., & Scozzari, A. (2008). Comparing different metaheuristic approaches for the median path problem with bounded length.  European journal of operations research, 190(3), 587–597.
Lari, I., Ricca, F., Scozzari, A., & Becker, R. I. (2011). Locating median paths on connected outerplanar graphs. Networks, 57(3), 294-307.
Mulvey, J. M., Vanderbei, R. J., & Zenios, S. A. (1995). Robust optimization of large-scale systems. Operations research43(2), 264-281. https://doi.org/10.1287/opre.43.2.264
Novik, A. (1996). Improved algorithms for locating tree or path shaped facilities on a tree network. Tel-Aviv University.‎‎‎‎‎
Peng, S., & Lo, W. T. (1996). Efficient algorithms for finding a core of a tree with a specified length. Journal of algorithms20(3), 445-458. https://doi.org/10.1006/jagm.1996.0022
Puerto, J., Ricca, F., & Scozzari, A. (2011). Minimax regret path location on trees. Networks, 58(2), 147-158. https://doi.org/10.1002/net.20453
Puerto, J., Ricca, F., & Scozzari, A. (2012). Range minimization problems in path-facility location on trees. Discrete applied mathematics, 160(15), 2294-2305.
Puerto, J., Ricca, F., & Scozzari, A. (2014). Reliability problems in multiple path-shaped facility location on networks. Discrete optimization, 12, 61-72.
Radsar, M., Kazemi, A., & Mehregan, M. (2021). Presenting a robust network data envelopment analysis model with undesirable output to evaluate efficiency in conditions of uncertainty. Decisions and operations research. (In Persian). http://www.journal-dmor.ir/article_136612.html
Richey, M. B. (1990). Optimal location of a path or tree on a network with cycles. Networks20(4), 391-407. https://doi.org/10.1002/net.3230200404
Slater, P. J. (1982). Locating central paths in a graph. Transportation science16(1), 1-18. https://doi.org/10.1287/trsc.16.1.1
Soyster, A. L. (1973). Technical note convex programming with set-inclusive constants and applications to inexact linear programming. Operation research, 21(5), 1154-1157. https://doi.org/10.1287/opre.21.5.1154
Tamir, A., & Lowe, T. J. (1992). The generalized p‐forest problem on a tree network. Networks, 22(3), 217-230. https://doi.org/10.1002/net.3230220302
Tamir, A., Puerto, J., Mesa, J. A., & Rodríguez-Chía, A. M. (2005). Conditional location of path and tree shaped facilities on trees. Journal of algorithms, 56(1), 50-75.
Wang, B. F. (1998). Finding a k-tree core and a k-tree center of a tree network in parallel. IEEE transactions on parallel and distributed systems, 9(2), 186-191. https://doi.org/10.1109/71.663884
Wang, B. F., & Lin, J. J. (2000). Finding a two-core of a tree in linear time. International symposium on algorithms and computation (pp. 467-478). Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-40996-3_40
Wang, B. F., Ye, J. H., & Li, C. Y. (2020). An improved algorithm for the minmax regret path center problem on trees. Journal of computer and system sciences, 114, 36-47. https://doi.org/10.1016/j.jcss.2020.05.002
Ye, J. H., Li, C. Y., & Wang, B. F. (2018). An improved algorithm for the minmax regret path centdian problem on trees. Journal of computer and system sciences, 97, 94-105. https://doi.org/10.1016/j.jcss.2018.05.003
Yousefi Hanoomarvar, A., Amiri, M., Olfat, L., & Naser Aadrabadi, A. (2021). Designing time-cost-quality trade-off model in multimodal PERT network using simulations and NSGA-II and mopso algorithms. Journal of decisions and operations research6(2), 146-173. (In Persian). https://doi.org/10.22105/dmor.2021.265922.1296