مسئله مکان‌یابی هاب تک تخصیصی با در نظر گرفتن تقاضاهای غیرقطعی صفر و یک

نوع مقاله : مقاله صنایع

نویسندگان

1 گروه مهندسی صنایع-دانشگاه صنعتی ارومیه

2 گروه مهندسی صنایع- دانشگاه تبریز

چکیده

مسائل مکان‌یابی هاب جهت تعیین بهترین مکان برای تاسیس تسهیلات هاب از بین تمام گره‌های شبکه و نحوه تخصیص سایر گره‌های شبکه به هاب‌ها با توجه به مفروضات مختلف می‌باشد. هاب‌ها تسهیلات ویژه‌ای هستند که در بسیاری از سیستم‌های توزیع به عنوان نقاط تعویض، جابجایی و طبقه‌بندی بکار گرفته می‌شوند. تسهیلات‌ هاب در یک شبکه، جهت کاهش تعداد جریان‌های مستقیم بین هر زوج مبدأ– مقصد ایجاد می‌شوند که نقش ایستگاه‌های واسط در شبکه را دارند. در اکثر تحقیقات انجام شده در خصوص مسائل مکان‌یابی هاب، تقاضاها (جریان‌های درون شبکه) بصورت قطعی در نظر گرفته شده است در حالیکه در دنیای واقعی تقاضا یک پارامتر غیرقطعی است. در این مقاله، مسئله مکان‌یابی‌ هاب تک تخصیصی با تقاضای غیرقطعی بصورت صفر و یک (تقاضای بین هر زوج مبدأ– مقصد یک متغیر تصادفی برنولی با احتمال مشخص p) توسعه داده شده است همچنین در صورت تکمیل شدن ظرفیت هاب،‌ برون سپاری برخی از تقاضاها نیز در نظر گرفته شده است که تاکنون در مسائل مکان‌یابی هاب، عدم قطعیت تقاضا بصورت برنولی و برون ‌سپاری تقاضا در صورت تکمیل ظرفیت هاب مورد بررسی قرار نگرفته‌اند. یک مدل ریاضی جدیدی از نوع برنامه‌ریزی عدد صحیح مختلط توسعه داده شده است که با استفاده از نرم افزار GAMS حل شده است. نتایج حاصل از حل مسائل در نمونه‌های مختلف با استفاده از اطلاعات فرودگاه‌های ایالات آمریکا (Civil Aeronautics Board) که به مجموعه داده CAB معروف است بررسی شده و تاثیر پارامترهای مختلف بر روی جواب بهینه مسئله نیز مورد بررسی قرار گرفته است.

کلیدواژه‌ها

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

Single allocation hub location problem considering zero-one uncertain demands

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

  • Saeed Pasbani Asl 1
  • Nader Ghaffarinasab 2
  • Farid Momayezi 1
1 Department of Industrial Engineering Urmia University of Technology
2 Department of Industrial Engineering, University of Tabriz
چکیده [English]

Hubs are special facilities used as switching, transferring, and sorting points in many distribution systems. Instead of serving each origin-destination pair directly, the hub facility concentrates flow to take advantage of the resulting economic savings. Flows from the same source combine with different destinations on their path to a hub and combine with flows that have different sources but have the same destination. The accumulation of flows takes place in the path from the origin to the hub and from the hub to the destination, as well as between the hubs. These types of systems, commonly known as hub-and-spoke, are studied in the form of hub location problems.
In this paper, we develop the single allocation hub location problem with uncertain zero-one demands, in which the amount of demand between each origin-destination pair is considered as a Bernoulli random variable with a definite probability p. Due to the fact that this problem has not been studied in the literature so far, a new mathematical model of mixed integer programming type is developed for the problem and is solved using GAMS software. Also, the results of solving different test problems from the CAB data set are examined and the effect of different parameters on the optimal solution of the problem is examined.

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

  • Hub Location Problem
  • Bernoulli Demand
  • Transportation Network

مراجع

[1] M. E. O'Kelly, "Activity levels at hub facilities in interacting networks", Geographical Analysis, Vol. 18, No. 4, 1986, pp.343-356.
[2] J. F. Campbell, "Integer programming formulations of discrete hub location problems" European Journal of Operational Research, Vol. 72, No. 2, Jan 1994, pp.387-405.
[3] R. Z. Farahani, M. Hekmatfar, A. B. Arabani, and E. Nikbakhsh, "Hub location problems: A review of models, classification, solution techniques, and applications", Computers and Industrial Engineering, Vol. 64, No. 4, Apr 2013, pp.1096-109.
]4[ مهدی بشیری و محمدرضا یعقوبی،"مدلسازی ریاضی مسئله مکان‌یابی P‏مرکز با در نظر گرفتن سلسله مراتب لانه‌ای و کاربرد الگوریتم بهینه‌سازی گروهی ذرات در حل آن"، نشریه مدل سازی در مهندسی، دوره چهاردهم، شماره 47، زمستان 1395، صفحه 187-197.
]5[ فرشاد حکیم پور، سیامک طلعت اهری و ابوالفضل رنجبر، "ارزیابی و مقایسه الگوریتم های بهینه سازی ژنتیک، شبیه‌سازی تبرید و فاخته‌ها در مکان‌یابی رقابتی تسهیلات (مطالعه موردی: بانکها) نشریه مدل سازی در مهندسی، دوره پانزدهم، شماره 48، بهار 1396، صفحه 231-246.
[6] S. L. Hakimi, and S. N. Maheshwari, "Optimum locations of centers in networks", Operations Research, Vol. 20, No. 5, 1972, pp.967-73.
[7] R. S. Toh, and R. G. Higgins, "The impact of hub and spoke network centralization and route monopoly on domestic airline profitability", Transportation journal, July 1985 , pp.16-27.
[8] D. Skorin-Kapov, J. Skorin-Kapov, and M. O'Kelly, "Tight linear programming relaxations of uncapacitated p-hub median problems", European journal of operational research, Vol. 94, No. 3, November 1996, pp.582-593.
[9] A. T. Ernst, and M.Krishnamoorthy, "Efficient algorithms for the uncapacitated single allocation p-hub median problem", Location science, Vol. 4, No. 3, October 1996, pp.139-54.
[10] J. G. Klincewicz, "Hub location in backbone/tributary network design: a review", Location Science, Vol. 6, No. 1-4, 1998, pp. 307-335.
[11] B. Yetiş Kara, "Modeling and analysis of issues in hub location problem", PhD diss, Bilkent University, 1999.
[12] D. L. Bryan, and M. E. O'kelly, "Hubandspoke networks in air transportation: an analytical review", Journal of regional science, Vol. 39, No. 2, 1999, pp. 275-295
[13] J. Ebery, M. Krishnamoorthy, A. Ernst, and N. Boland, "The capacitated multiple allocation hub location problem: Formulations and algorithms", European journal of operational research, Vol. 120, No. 3, February, pp.614-631.
[14] M. W. Horner, and M. E. O'Kelly, "Embedding economies of scale concepts for hub network design" Journal of Transport Geography, Vol. 9, No. 4, December 2000, pp.255-65.
[15] B. Y. Kara, and B. C. Tansel, "The single-assignment hub covering problem: Models and linearizations, Journal of the Operational Research Society, Vol. 54, No. 1, January 2003, pp 59-64.
[16] G. Carello, F. Della Croce, M. Ghirardi, and R.Tadei, "Solving the hub location problem in telecommunication network design: A local search approach", Networks: An International Journal, Vol. 44, No. 2, September 2004, pp.94-105.
[17] H Yaman, and G.Carello, "Solving the hub location problem with modular link capacities" Computers and operations research, Vol. 32, No. 12, December 2005, pp.3227-3245.
[18] H. Yaman, "Star p-hub median problem with modular arc capacities", Computers and Operations Research, Vol. 35, No. 9, September 2008, pp.3009-3019.
[19] I. Racunica, and L.Wynter, "Optimal location of intermodal freight hubs" Transportation Research Part B: Methodological, Vol. 39, No. 5, June 2005, pp.453-77.
[20] A. Kimms, "Economies of scale in hub & spoke network design models: We have it all wrong", Perspectives on operations research, pp. 293-317.
[21] I. Contreras, E. Fernández, and A. Marín, "Tight bounds from a path based formulation for the tree of hub location problem", Computers and Operations Research, Vol. 36, No. 12, December 2009, pp.3117-3127.
[22] I. Correia, S. Nickel, and F.Saldanha-da-Gama, "The capacitated single-allocation hub location problem revisited: A note on a classical formulation", European Journal of Operational Research, Vol. 207, No. 1, November 2010, pp.92-6.
[23] A. Saboury, N. Ghaffari-Nasab, F. Barzinpour, and M. S. Jabalameli, "Applying two efficient hybrid heuristics for hub location problem with fully interconnected backbone and access networks" Computers and Operations Research, Vol. 40, No. 10, October 2013, pp.2493-507.
[24] I. Rodríguez-Martín, J. J. Salazar-González, and H. Yaman, "A branch-and-cut algorithm for the hub location and routing problem", Computers and Operations Research, Vol. 50, October 2014, pp.161-74.
[25] M. Tanash, I. Contreras, and N. Vidyarthi, "An exact algorithm for the modular hub location problem with single assignments", Computers and Operations Research, Vol. 85, September 2017, pp.32-44.
[26] N. Ghaffarinasab, and R.Atayi, "An implicit enumeration algorithm for the hub interdiction median problem with fortification", European Journal of Operational Research, Vol. 267, No. 1, May 2018, pp.23-39.
[27] S. Alumur, and B. Y. Kara, "Network hub location problems: The state of the art, European journal of operational research, Vol. 190, No. 1, Ocober 2008, pp.1-21.
[28] J. F. Campbell, and M. E. O'Kelly, "Twenty-five years of hub location research", Transportation Science, Vol. 46, No. 2, May 2012, PP.153-69.
[29] I. Contreras, and M. O’Kelly, "Hub location problems", Location science, 2019, Springer, Cham, pp. 327-363.
[30] S. A. Alumur, J. F. Campbell, I. Contreras, B. Y. Kara, V. Marianov, and M. E. O’Kelly, "Perspectives on Modeling Hub Location Problems", European Journal of Operational Research, October 2020.
[31] V. Marianov, D. Serra, "Location models for airline hubs behaving as M/D/c queues", Computers and Operations Research, Vol. 30, No. 7, Jun 2003, pp.983-1003.
[32] S. Elhedhli, F. X. Hu, "Hub-and-spoke network design with congestion", Computers and Operations Research, Vol. 32, No. 6, Jun 2005, pp.1615-32.
[33] M. Mohammadi, F. Jolai, and H. Rostami, "An M/M/c queue model for hub covering location problem", Mathematical and Computer Modelling, Vol. 54, No. 11-12, December 2011, pp.2623-38.
[34] S. A. Alumur, S. Nickel, and F.Saldanha-da-Gama, "Hub location under uncertainty", Transportation Research Part B: Methodological, Vol. 46, No. 4, May 2012, pp.529-43.
[35] F. Parvaresh, S. H. Golpayegany, S. M. Husseini, and B. Karimi, "Solving the p-hub median problem under intentional disruptions using simulated annealing", Networks and Spatial Economics, Vol. 13, No. 4, December 2013, pp.445-70
]36[ عباس کاری مجیدآباد، مرضیه مظفری و علی نعیمی صدیق، "تعادل استکلبرگ- نش در بازی مکان‌یابی رقابتی تسهیلات میان یک امتیاز دهنده و دو سرمایه‌گذار"'، نشریه مدل سازی در مهندسی، دوره هفدهم، شماره 57، تابستان 1398، صفحه 111-125.
[37] A. Adibi, and J. Razmi, "2-Stage stochastic programming approach for hub location problem under uncertainty: A case study of air network of Iran", Journal of Air Transport Management, Vol. 47, August 2015, pp.172-178.
[38] N. Ghaffari-Nasab, M. Ghazanfari, and E.Teimoury, "Robust optimization approach to the design of hub-and-spoke networks", The International Journal of Advanced Manufacturing Technology, Vol. 76, No. 5-8, February 2015, pp.1091-1110.
[39] M. Meraklı, and H. Yaman, "A capacitated hub location problem under hose demand uncertainty", Computers and Operations Research, Vol. 88, December 2017, pp.58-70.
[40] Z. Qin, and Y. Gao, "Uncaacitated p-hub location roblem with fixed costs and uncertain flows", Journal of Intelligent Manufacturing, Vol. 28, No. 3, March 2017, pp.705-716..
[41] I. Correia, S. Nickel, and F.Saldanha-da-Gama, "A stochastic multi-period capacitated multiple allocation hub location problem: Formulation and inequalities", Omega, Vol. 74, Jan 2018, pp.122-34.
 
[42] F. Momayezi, S. K. Chaharsooghi, M. M. Sepehri, and A. H. Kashan, "The capacitated modular single-allocation hub location problem with possibilities of hubs disruptions: modeling and a solution algorithm", Operational Research, Vol. 17, November 2018, pp.1-28.
[43] N. Ghaffarinasab, "An efficient matheuristic for the robust multiple allocation p-hub median problem under polyhedral demand uncertainty", Computers and Operations Research, Vol. 97, September 2018, pp.31-47.
[44] X. Shang, K. Yang, W. Wang, W. Wang, H. Zhang, and S. Celic, "Stochastic hierarchical multimodal hub location problem for cargo delivery systems: formulation and algorithm", IEEE Access, Vol. 8, March 2020, pp.55076-55090.
[45] B Rostami, N Kämmerling, J Naoum-Sawaya, C Buchheim, U.Clausen, "Stochastic single-allocation hub location", European Journal of Operational Research, Vol. 289, No. 3, March 2021, pp.1087-1106.
مدل سازی در مهندسی
دوره 19، شماره 66
مهر 1400
صفحه 157-173

فایل ها

سابقه مقاله

  • تاریخ دریافت: 25 فروردین 1400
  • تاریخ بازنگری: 31 خرداد 1400
  • تاریخ پذیرش: 08 تیر 1400

هم رسانی

ارجاع به این مقاله

آمار