یک رویکرد کارآ برای مسأله جایابی تسهیلات غیر مشابه در فضای ناپیوسته

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

نویسندگان

1 کارشناس ارشد مهندسی صنایع دانشگاه صنعتی اصفهان:

2 دانشیار دانشکده مهندسی صنایع دانشگاه صنعتی اصفهان

چکیده

مسأله جایابی تسهیلات (MFLP) مکان‌یابی تعداد معینی تسهیل برای خدمت رسانی به مجموعه‌ای از مشتریان با نیازها و مکان‌های مشخص است. اگر محیط مورد نظر ناپیوسته باشد مسأله به صورت مکان‌یابی تسهیلات در محیط غیر پیوسته (DMFLP) مطرح می‌گرد. در این مقاله حالت خاصی از مسأله DMFLP با هدف استقرار تسهیلات غیر مشابه در محیط ناپیوسته و با درنظرگرفتن تسهیلات موجود مورد بررسی قرار می‌گیرد. مسأله مورد نظر در دو حالت وجود و عدم وجود ارتباط میان تسهیلات قابل بررسی است. در این مقاله یک الگوریتم حل دقیق بر پایه روش شاخه‌وکران و یک الگوریتم ابتکاری برای حل مسأله ارائه شده است. در هر دو حالت وجود و عدم وجود ارتباط، با افزایش تعداد تسهیلات و مکان‌ها زمان حل ‌مسأله برای رسیدن به ‌جواب بهینه به ‌طور قابل توجهی افزایش می‌یابد. بدین ‌لحاظ یک الگوریتم ابتکاری کارآ توسعه داده ‌شده و برای حل مسأله برای هر دو دیدگاه به‌ کار گرفته شد. با تولید مسائل تصادفی کارآیی روش ابتکاری در مقایسه با الگوریتم حل‌ دقیق بررسی و نشان‌ داده ‌شده ‌است.

کلیدواژه‌ها

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

An Efficient Approach to Discrete Multiple Different Facility Location Problem

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

  • Davod Shishebori 1
  • Mehdi Mahnam 1
  • Ali Shahandeh 2
چکیده [English]

The Multiple Facility Location Problem (MFLP) is to locate certain facilities so as to serve a given set of customers, whose locations and requirements are known. When the locations have to be selected from a given set of candidate locations, the problem becomes a Discrete Multiple Facility Location Problem (DMFLP). In this study, a special case of DMFLP is discussed where multiple facilities that are of different type are to be placed (location decision) and assign customers to these facilities (allocation or assignment). Both cases with and without interactions among new facilities are considered in this problem. In this paper, efficient lower and upper bounds are used to propose a branch-and-bound scheme as an exact method. Also, new heuristic method is provided for both cases and compared for large-job sizes. Computational results on randomly generated data in comparison with optimal solutions indicate that the heuristic method is accurate and efficient.

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

  • facility location
  • Branch and Bound
  • Heuristic

مراجع

[1] Drezner Z.; “Facility Location: A Survey of Applications and Methods”, First Edition, New York: Springer, September 11, 1995.
[2] Yuri L.; and Adi B.; “A Heuristic Method for Large- Scale Multi-Facility Location Problems”, Computers & Operations Research, Vol. 31, No. 2, pp. 257–272, 2004.
[3] Domschke, W.; and Krispin, G.; “Location and layout planning, A survey”, ORSpektmm, Vol. 19, pp. 181-
194, 1997.
[4] Francis, R.L.; and white, J.A; “Facility Layout and Location An Analytical Approach”, Second Edition,Pearson Professional, October 1st, 1991.
[5] Daskin M.S.; “Network and Discrete Location: Models, Algorithms and Applications”, Wiley, New York, 1995.
[6] Drezner T., Drezner Z.; and Salhi, S.; “Solving the Multiple Competitive Facilities Location Problem”,European Journal of Operational Research, Vol. 142,No. 1, pp. 138-151, 2002.
[7] ReVelle, C.S.; and Swain, R.; “Central Facilities Location”, Geographical Analysis, Vol. 2, pp. 30–42,1970.
[8] Kariv, O.; and Hakimi, S.; “An Algorithmic Approach to Network Location Problems. II: The P-Medians”,
SIAM Journal on Applied Mathematics, Vol. 37, pp.539–560, 1979.
[9] Christofides, N.; and Beasley, J.E; “A Tree Search Algorithm for the P-Median Problem”, European
Journal of Operational Research, Vol. 10, No. 2, pp.196–204, 1982.
[10] Hanjoul, P.; and Peeters, D.; “A Comparison of Two Dual-Based Procedures for Solving the P-median Problem”, European Journal of Operational Research,Vol. 20, No. 3, pp. 387–396, 1985.
[11] Beasley, J.E.; “Lagrangean Heuristics for Location Problems”, European Journal of Operational Research, Vol. 65, No. 3, pp. 383–399, 1993.
[12] Klose, A.; and Drexl A., “Facility Location Models for Distribution System Design”, European Journal of Operational Research, Vol. 162, No. 1, pp. 4–29, 2005.
[13] Dileep, R.S.; “Manufacturing Facilities Location planning & Design”, Second Edition, Louisiana Tech
university, PWS Publishing, January 26, 1994.
[14] Sahin, G.; and Süral, H.; “A review of hierarchical facility location models”, Computers & Operations
Research, Vol. 34, pp. 2310-2331, 2007.

فایل ها

هم رسانی

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

آمار