مسئلۀ مکان‌یابی تسهیلات نامطلوب در شرایط عدم قطعیت: مدل‌سازی و الگوریتم حل

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

نویسندگان

1 کارشناسی ارشد، دانشکده مهندسی، گروه مهندسی صنایع،دانشگاه بوعلی سینا، همدان،ایران

2 دانشیار، دانشکده مهندسی، گروه مهندسی صنایع، دانشگاه بوعلی سینا، همدان، ایران

چکیده

در مسئلۀ مکان‌یابی تسهیلات نامطلوب برخلافِ تسهیلات مطلوب، تا حد امکان سعی می‌شود تسهیلات دور از مناطق دریافت‌کنندۀ خدمت استقرار یابند. در این پژوهش دربارۀ مسئلۀ مکان‌یابی این قبیل تسهیلات بحث شده است. در این مسائل بر اصطلاح «نه در حیاط خلوت من»، تمرکز و به پدیده‌های اجتماعی اشاره دارد. در این پدیده ساکنان با مکان‌یابی تسهیلات نامطلوب اطراف خانه‌هایشان مخالف‌اند. نمونه‌هایی از این تسهیلات شامل خطوط انتقال برق و مراکز بازیافت است. به‌دلیل اینکه درجۀ آلودگی حاصل از این تسهیلات با عدم‌قطعیت همراه است، در این پژوهش برای نخستین بار عملکرد این مسئله با در نظر گرفتن عدم‌قطعیت احتمالی ارزیابی شده است. این مسئله در فضای گسسته در نظر گرفته شده است. در این مسئله سه حالتِ ممکن برای دامنۀ تغییراتِ این دو پارامتر در نظر گرفته شده است. باتوجه‌به اینکه ارتباط و میزان اختلاف درجۀ آلودگی اصلی و حاشیه‌ای نیز نامشخص است، سناریوها براساس درجۀ اختلاف این دو پارامتر در نظر گرفته شده‌اند. با در نظر گرفتن این سناریوها، اهمیت درجۀ اختلاف این دو پارامتر در مسئلۀ مکان‌یابی تسهیلات نامطلوب بررسی شده است. در این پژوهش مدل ریاضی مسئله، روش‌های مواجهه با عدم‌قطعیت، مدل‌سازی مسائل برنامه‌ریزی تصادفی و روش استفاده‌شده در مسئلۀ درحال مطالعه ارائه شده است. باتوجه‌به NP-hard بودن مسئله، الگوریتم فراابتکاری شبیه‌سازی تبرید برای حل مسئله در ابعاد بزرگ پیشنهاد شده است. آزمایشات عددی برای ارزیابی و اعتبارسنجی مدل ریاضی و الگوریتم پیشنهادی در نظر گرفته شده است و عملکرد الگوریتم پیشنهادی در حل مسائل مختلف با الگوریتم ژنتیک موجود در ادبیات مسئلۀ درحال مطالعه، مقایسه و برتری آن ارائه شده است.

کلیدواژه‌ها

موضوعات


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

Undesirable Facility Location under Uncertainty: Modeling and Algorithm

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

  • Parisima Pakravan 1
  • Javad Behnamian 2
1 MSc, Department of Industrial Engineering, Faculty of Engineering, Bu-Ali Sina University, Hamedan, Iran
2 Associate Professor, Department of Industrial Engineering, Faculty of Engineering, Bu-Ali Sina University, Hamedan, Iran
چکیده [English]

Abstract: In undesirable facility location problem contrary to desirable location, facilities are located far from service receiver facilities as much as possible. The problem of locating such facilities is discussed in this study. This research is focused on the ‘not in my backyard’ (NIMBY) phrase which refers to the social phenomena in which residents are opposed to locate undesirable facilities around their houses. Examples of such facilities include electric transmission lines and recycling centers. Due to the opposition typically encountered in constructing an undesirable facility, the facility planner should understand the nature of the NIMBY phenomena and consider it as a key factor in determining facility location. Because of the adverse effects of these facilities, coupled with the uncertainty in the real world, it is estimated taking into account the potential uncertainty. This problem has been considered in the discrete space. The mathematical model is presented and methods to deal with uncertainty and stochastic programing problems modeling and methods used in the study are presented. According to the NP-hard problem, Simulated Annealing suggested for solving problems in large-scale. Numerical experiments to evaluate and validate the mathematical modeling and proposed algorithm are considered and operation of the proposed algorithm to solve various problems with genetic algorithms available in the literature about the problem is compared.
Introduction: From a general point of view, it is possible to investigate locational issues in two categories of optimal and undesirable facilities. There are many location models available for desirable facilities such as warehouses, service centers, police stations, and more. In such instances, customers are attracted to their facilities. Unlike desirable facilities in the location of undesirable facilities, it attempts to facilities as far away as possible from receiving areas. Undesirable facilities, while providing essential services for the people, at the same time, may have negative consequences for their neighborhoods. The proximity of undesirable facilities to residential areas due to their high pollution and hazardousness, will lead to lower quality of life in these areas and increase the health risk for residents of these areas. This type of problem is formulated in order to minimize the adverse effects of a new facility on existing facilities. Given that the degree of pollution from this facility in the real world is associated with uncertainty, in this paper, the mathematical model for the problem of locating undesirable facilities with uncertainty in degree of pollution parameters is presented. Also, the history of the problem of locating facilities in stochastic conditions and undesirable facilities has been presented. In the following, considering the mathematical model in a deterministic and stochastic manner, the proposed algorithm structure is described.
 
Materials and Methods: The problem of locating the undesirable facilities discussed in this paper is based on the article that focuses on the purpose of the term (not in my backyard). This refers to social phenomena in which residents oppose the placement of undesirable facilities around their homes. Considering the opposition to the creation of undesirable facilities, the facility planner must understand the nature of the NIMBY phenomenona and consider it as a key factor in determining the location of the facility. In this research, the NIMBY phenomenona is directly discussed through the structure of the objective function. The purpose function structure allows the residents to speak of the fact that the hosts hosting these facilities are those who are absorbing environmental costs, while other regions enjoy the benefits of this facility. 
1-                   First, uncertainty in the degree of pollution is considered and different scenarios are considered for it and the problem will be solved.
2-                   According to the mathematical model presented in stochastic mode, the problem is solved for each individual scenario and finally, three scenarios are compared and the objective hope of the target function is obtained for all scenarios. We considered the scenarios based on the degree of difference between these two parameters, which are as follows: The scenario (1): The degree of main contamination (a) 100 times the marginal contamination (b) Scenario (2): both change in close proximity. Scenario (3): The degree of main contamination (a) is 10 times the marginal contamination level (b)
3-                   Because of the NP-hardness of the nature of the problem studied, it is proposed to solve it in large dimensions for the large-scale simulation of Simulated annealing algorithm. A Heuristic method has been used to generate the initial answer to this question. The method of transfer from a solution to its neighboring solution is characterized by a known key factor called the neighborhood structure. Here, four operators for generating neighboring solutions are used in the Simulated annealing algorithm.
 
Results and Discussion: The problem in small and medium sizes in all experimental samples of the Metaheuristic-algorithm has been reached to the optimal solution of the problem Cplex solving software. Due to the fact that the Cplex software was unable to solve test samples for dimensions of 1000 node and larger than this dimension of the problem, the results of numerical tests of the problem were considered by considering 3 scenarios in each sample. Sixteen types of problem in large dimensions are solved with genetic and Simulated annealing meta-heuristic algorithms, and the stopping time of both algorithms is 1 hour. Finally, the results are compared. The genetic algorithm is written according to Sang et al. (Sang et al., 2013). Due to the fact that it was not able to produce feasible answers on large dimensions, the Heuristic method used in the Simulated annealing algorithm to generate the primary solution is also used in this algorithm. In all experimental samples, the Simulated annealing algorithm has the lowest value of the target function in comparison with the genetic algorithm.
 
Conclusion: In this paper, the problem of locating undesirable facilities with a focus on reducing the degree of pollution from these facilities was studied. Considering that in the past and also in the real world, the exact amount of this degree of pollution is uncertain, it was decided to investigate the degree of contamination resulting from this facility in the uncertainty mode. Then, by investigating the methods of dealing with uncertainty and modeling methods of random planning problems, the scenario method was used to consider the uncertainty in this problem and scenarios were designed to take into account the uncertainty in degree of pollution of the facility for the points around them. The problem was solved for various test examples in small to medium size scenarios with Cplex exact solver software and optimal solutions were obtained. Given the complex nature of this problem, a large-scale Simulated annealing algorithm was proposed to solve it in large dimensions and given that the space is large, it is used to generate an initial possible response instead of producing a random solution from an Heuristic method to produce an initial possible answer to this problem. The computational results of Optimal Optimization and Simulated annealing Algorithms in Small and Medium Dimensions were compared. Both methods achieved the optimal response and the difference was during solving these samples. For large dimensions, experimental samples were used using the Simulated annealing, and genetic algorithm available in the literature were compared and the efficiency of  Simulated annealing algorithm in convergence to optimal solution and less time to solve in different samples and scenarios has been proved.
 
References
Song, B. D. Morrison, J. R. Ko, Y. D. (2013). Efficient location and allocation strategies for undesirable facilities considering their fundamental properties. Comput. Ind. Eng., 65: 475–484.
Mirhasani, S. A. (2014). Stochastic Programming. First Edition. Amir Kabir University Publishers.

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

  • Undesirable Facility Location
  • Uncertainty
  • Simulated Annealing
  • Genetic Algorithm

مقدمه

از دیدگاهی کلی مسائل مکان‌یابی در دو دستۀ مکان‌یابی تسهیلات مطلوب و تسهیلات نامطلوب بررسی می‌شوند. مدل‌های مکان‌یابی بسیاری برای تسهیلات مطلوب همچون انبارها، مراکز خدماتی، مراکز پلیس و ... وجود دارند. در این نمونه‌ها، تسهیلات مشتریان را به‌سوی خود جذب می‌کنند. با در نظر گرفتن وجود رابطۀ مستقیم بین مسافت طی‌شده و هزینه‌های سفر در این دسته مسائل، معمولاً مهم‌ترین هدف آن است که تسهیلات به‌نحوی مکان‌یابی شوند که توابعی از مسافت یا به‌طور معادل هزینه‌های سرویس‌دهی برای تسهیلات حداقل شوند؛درحالی‌که در مکان‌یابی تسهیلات نامطلوب برخلاف تسهیلات مطلوب، سعی می‌شود تا حد امکان، تسهیلات دور از مناطق دریافت‌کنندۀ خدمت استقرار یابند. ارائۀ تسهیلات نامطلوب در عین حال که جزءِ خدمات ضروری برای مردم است، ممکن است پیامدهای منفی برای مکان‌های همسایگی آنها داشته باشد؛ بنابراین ساختن یا گسترش چنین تسهیلاتی با مخالفت شدید ساکنان این مناطق مواجه می‌شود (تقوی فرد و همکاران، 1386) این مخالفت معمولاً با اصطلاح (نه در حیاط خلوت من (NIMBY))[i] بیان می‌شود؛ بنابراین هنگام ایجاد تسهیل نامطلوب، تصمیم‌گیرندگان ممکن است با مخالفت شدید ساکنان همسایۀ خود مواجه شوند. راکتورهای هسته‌ای، صنایع نظامی و کارخانجات شیمیایی مثال‌هایی از این دسته‌اند. نزدیک‌بودن تسهیلات نامطلوب به مناطق مسکونی به‌دلیل آلایندگی زیاد و خطرناک‌بودن آنها، موجب پایین‌آمدن کیفیت زندگی در این مناطق و افزایش خطر سلامتی برای ساکنان این مناطق می‌شود (سانگ و همکاران[ii]، 2013)؛ برای اینکه اثرات نامطلوب تسهیل جدید روی امکانات موجود حداقل شود این نوع از مسئله فرموله می‌شود. باتوجه‌به اینکه درجۀ آلودگی حاصل از این تسهیلات در دنیای واقعی همراه با عدم‌قطعیت است (میرحسنی، 1393)، در این مقاله مدلی ریاضی برای مسئلۀ مکان‌یابی تسهیلات نامطلوب همراه با عدم‌قطعیت در پارامترهای درجۀ آلودگی ارائه شده است.

درادامه، پیشینۀ مسئلۀ مکان‌یابی تسهیلات در شرایط تصادفی و تسهیلات نامطلوب آورده شده است. در بخش دوم مدل ریاضی درحالت قطعی و تصادفی ارائه می‌شود. درادامه ساختار الگوریتم پیشنهادی تشریح شده است. در بخش سوم نتایج عددی حل مدل ریاضی در نرم‌افزار سیپلکس و الگوریتم فراابتکاری شبیه‌سازی تبرید با در نظر گرفتن سناریوهای مختلف آمده است. درنهایت نتیجه‌گیری از کاربرد این روش در حل مسئله و پژوهش‌های آتی آمده است.

 

پیشینۀ موضوع

مرور کوتاهی بر ادبیات مکان‌یابی تسهیلات در شرایط تصادفی و مکان‌یابی تسهیلات نامطلوب، زمینۀ لازم برای ورود به بحث نظری دربارۀ آن را فراهم می‌کند؛ ازاین‌رو برخی جنبه‌های مهم و مرتبط با موضوع در بخش‌های بعدی ارائه می‌شوند.

 

مکان‌یابی تسهیلات در شرایط تصادفی

عوامل بسیاری در مکان‌یابی تسهیلات مؤثرند که متغیر و نامشخص‌اند؛ مانند هزینه‌ها، تقاضاها، زمان سفر و دیگر ورودی‌ها. این عوامل باعث می‌شوند مدل‌هایی توسعه یابد که شرایط عدم‌قطعیت در آنها در نظر گرفته شود و عدم‌قطعیت برای بسیاری از پژوهشگران برای بهینه‌سازی استوار و تصادفی اولویت زیادی داشته باشد؛ درواقع تعداد زیادی از این روش‌ها که برای بهینه‌سازی در شرایط عدم‌قطعیت است برای مسائل مکان‌یابی تسهیلات به کار رفته است. بسیاری از پارمترها در مسائلی مانند هزینه، تقاضا و فاصله به‌طور گسترده‌ای نوسان دارند. همچنین ممکن است برآورد پارامترها به‌دلیل خطاهای اندازه‌گیریِ ضعیف و یا گاهی به‌دلیل فرایند مدل‌سازی مانند جمع‌آوری داده‌های مربوط به تقاضا و انتخاب قاعدۀ فاصله با خطا مواجه می‌شود؛ به همین دلیل پژوهشگران درحال توسعۀ مدل‌ها برای مکان‌یابی تسهیلات در شرایط عدم‌قطعیت بوده‌اند (اسنیدر[iii]، 2006). باتوجه‌به بررسی کارهای انجام‌شده در گذشته (در جدول 1 مجموعۀ آنها قرار داده شده است) مسئلۀ مکان‌یابی تسهیلات نامطلوب در شرایط عدم‌قطعیت احتمالی نخستین‌بار در این پژوهش مطالعه شده است. در مطالعات بررسی‌شده، همۀ مقالات از الگوریتم‌های ابتکاری برای حل این مسئله استفاده کرده‌اند و تنها یک مقاله، الگوریتم فراابتکاری را در حل این مسئله به کار گرفته است. در این پژوهش نیز به‌دلیل ناتوان‌بودن نرم‌افزار حل دقیق CPLEX برای حل این مسئله در ابعاد بزرگ، از الگوریتم فراابتکاری شبیه‌سازی تبرید[iv] با استفاده از نرم‌افزار متلب در ابعاد بزرگ استفاده می‌شود. در جدول (1) جمع‌بندی از کارهای انجام‌شده در مکان‌یابی تسهیلات تصادفی آورده شده است.

 

جدول 1- مجموعه کارهای انجام‌شده در مکان‌یابی تسهیلات تصادفی

رویکرد مدل‌سازی عدم‌قطعیت

روش حل

مسئلۀ استفاده‌شده

نویسنده

برنامه‌ریزی سناریو

روش سناریو

PMP

(میرچاندانی و اودنی[v]، 1979)

دومرحله‌ای

برنامه‌ریزی تصادفی دومرحله‌ای

تابع مطلوبیت خطی

(لوویاوکس و تیسه[vi]، 1985)

تابع هدف محدب، توزیع نرمال دومتغیره برای نقاط تقاضا

یک الگوریتم تکرارشونده

مسئلۀ وبر

(کوپر[vii]، 1974)

برنامه‌ریزی سناریو

روش سناریو

مکان‌یابی تسهیلات

(شپارد[viii]، 1974)

برنامه‌ریزی سناریو

الگوریتم براساس شمارش جزیی

مسئلۀ PMP

(میرچاندانی و واودجیت[ix]، 1980)

برنامه‌ریزی سناریو

روش آزادسازی لاگرانژ

مسئلۀ PMP تصادفی

(ویور و چورچ[x]، 1983)

دو مرحله‌ای

الگوریتم تقریبی[xi]

UFLP تصادفی

(راوی و سینها[xii]، 2004)

برنامه‌ریزی سناریو

روش سناریو

مکان‌یابی تک‌تسهیلاته

(برمن و اودنی[xiii]، 1982)

مدل‌سازی با قیود احتمالی

روش ابتکاری

مکان‌یابی تسهیلات ظرفیت‌دار

(کومار و همکاران[xiv]، 2012)

برنامه‌ریزی سناریو

ارائۀ مدل بهینه‌سازی استوار

مکان‌یابی تسهیل ظرفیت‌دار

(روسا و همکاران[xv]، 2014)

بررسی مدل با پارامترهای غیرقطعی

-

مسئلۀ مکان‌یابی وبر

(جمالیان و صلاحی، 2014)

برنامه‌ریزی غیرخطی با محدودیت احتمالی

حل مدل با در نظر گرفتن محدودیت شانس

مسئلۀ مکان‌یابی تصادفی

(گولپمار و همکاران[xvi]، 2013)

برنامه‌ریزی دومرحله‌ای

روش ابتکاری

مسئلۀ مکان‌یابی دوهدفۀ دومرحله‌ای

(هو و همکاران[xvii]، 2017)

تصادفی چندمرحله‌ای

روش ابتکاری لاگرانژ

مسئله‌ی مکان‌یابی تصادفی چندمرحله‌ای

(مارکویک و همکاران[xviii]، 2017)

مدل پیوستۀ غیرخطی با تقاضای غیرقطعی

الگوریتم ابتکاری

مسئلۀ مکان‌یابی- موجودی

(پوگا و همکاران[xix]، 2017)

مکان‌یابی تسهیلات نامطلوب

(ارکات و نیومان[xx]، 1989) بیان کردند که بسیاری از مدل‌های مکان‌یابی تنها فاصله به تسهیلات جدید را حداقل می‌کنند و معمولاً برای تسهیلات خدمت‌دهی مدل مناسبی است؛ اما هنگامی‌که کسی می‌خواهد تسهیل مضری را مکان‌یابی کند (مانند محلی برای انباشتن زباله‌ها یا ایجاد کارخانۀ شیمیایی یا نیروگاه هسته‌ای) ممکن است تابع هدفِ حداقل‌کردنِ فاصله‌ها مناسب نباشد. به‌طور طبیعی این مسائل چندهدفه‌اند؛ برای مثال علاوه بر حداکثرکردن فاصلۀ وزنی- تقاضا، بین نقاط تقاضا و نزدیک‌ترین نقطۀ عرضه، ممکن است هدف حداکثرکردن کمترین فاصلۀ وزنی – تقاضا بین نقاط تقاضا و نزدیک‌ترین نقطۀ عرضه باشد. همان طور که واضح است مناطق شهری و پرجمعیت، زباله و ضایعات بیشتری تولید می‌کنند؛ بنابراین برای کاهش هزینه‌های حمل و نقل باید تسهیلات نامطلوب تا حد امکان به این مناطق نزدیک باشند و این موضوع با تابع هدف اولیه در تضاد است (دوربودن تسهیلان نامطلوب از مناطق پرجمعیت). همچنین مسیریابی در مکان‌یابی تسهیلات نامطلوب موضوع مهمی است؛ زیرا مواد مضر معمولاً مسیری غیر از کوتاه‌ترین فاصله یا کمترین هزینه را طی می‌کنند تا از مواجهه با مراکز پرجمعیت خودداری شود (داسکین[xxi]، 1997). در جدول (2) خلاصه‌ای از ادبیات مکان‌یابی تسهیلات نامطلوب آمده است.

 

جدول 2- جایگاه پژوهش موجود

توضیحات

چندهدفه

احتمالی

فازی

روش حل

نوع تابع هدف

نویسنده

فضای پیوسته

 

-

-

روش هندسی/ کوهن تاکر

غیرخطی

(ملاچرینودیس[xxii]، 1985)

-

 

-

-

الگوریتم ابتکاری

غیرخطی

(ملاچرینودیس و کولینین[xxiii]، 1985)

فضای پیوسته

 

-

-

ارائۀ دو الگوریتم ابتکاری

غیرخطی

(ملاچرینودیس و کولینین، 1986)

-

 

-

-

روش حل ترکیبی

خطی

(ارکت و نیومن، 1989)

فضای پیوسته

 

-

-

-

خطی

(پلاستریا[xxiv]، 1996)

اثرات جانبی

-

-

-

نظریه- مدل ریاضی ارائه نداد

 

(فاربر[xxv]، 1998)

دومعیاره

 

-

-

الگوریتم ابتکاری

غیرخطی

(بریمبرگ و جویل[xxvi]، 1998)

فضای پیوسته

 

 

 

الگوریتم در زمان چندجمله‌ای

خطی

(پلاستریا و کاریزوسا[xxvii]، 1999)

فضای پیوسته

 

-

-

شاخه و کران/ آنالیز فاصله‌ای

غیرخطی

(فرناندز و همکاران[xxviii]، 2000)

دومعیاره

ü

-

-

الگوریتم ابتکاری

غیرخطی

(ملاچرینودیس و زاهاریس[xxix]، 2003)

گسسته

ü

 

ü

نرم‌افزار سیپلکس

خطی

(راکاس و همکاران[xxx]، 2004)

فضای پیوسته

 

-

-

الگوریتم چندجمله‌ای

غیرخطی

(کلبروک و همکاران[xxxi]، 2005)

فضای پیوسته

 

-

-

الگوریتم در زمان چندجمله‌ای

خطی

(ردریگویز و همکاران[xxxii]، 2006)

فضای پیوسته

 

-

-

الگوریتم چندجمله‌ای

غیرخطی

(کلبروک و سیکیلیا[xxxiii]، 2007)

-

-

-

-

ANP

 

(توزکایا و همکاران[xxxiv]، 2008)

 

-

-

-

رویکرد چانه‌زنی

 

(یاماگوچی[xxxv]، 2011)

محدودیت ظرفیت

 

-

-

الگوریتم ژنتیک

خطی

(سانگ و همکاران، 2013)

چندمعیاره

ü

-

-

MCDM

-

(تانگ و همکاران[xxxvi]، 2013)

-

-

-

-

مجموعه رویکرد مبتنی‌برتسلط

 

(آبستنه و همکاران[xxxvii]، 2014)

فضای گسسته

ü

 

ü

روش سلسله مراتبی تحلیلی فازی

خطی

(ویچاپا و همکاران[xxxviii]، 2017)

فضای گسسته

 

ü

 

حل مدل در CPLEX و ارائۀ الگوریتم فراابتکاری

خطی

پژوهش جاری

بیان مسئله و مدل‌سازی

مسئلۀ مکان‌یابی تسهیلات نامطلوب بحث‌شده در این پژوهش باتوجه‌به مقاله‌ای است که محوریت هدف را اصطلاحِ «نه در حیاط خلوت من» قرار داده است. این موضوع اشاره به پدیده‌های اجتماعی دارد که در آن ساکنان با مکان‌یابی تسهیلات نامطلوب اطرافِ خانه‌هایشان مخالف‌اند. مثال‌هایی از این تسهیلات شامل خطوط انتقال برق، مراکز بازیافت، پتروشیمی، سطل زباله و کوره‌اند که به‌طور معمول ساخت این تأسیساتِ نامطلوب با مخالفت مواجه می‌شوند. باتوجه‌به مخالفتی که در ساختن تسهیلات نامطلوب وجود دارد برنامه‌ریزِ تسهیلات باید ماهیت پدیدۀ NIMBY را درک کند و آن را عاملی کلیدی در تعیین محل تسهیلات در نظر بگیرد؛ سپس ویژگی‌های پدیدۀ NIMBY را بررسی و مدل بهینه‌سازی ریاضی را با هدف به حداقل رساندن مجموع درجات پدیده پیشنهاد کند. درجۀ پدیدۀ NIMBY برای ساکنان میزبان تسهیلات به‌خاطر جذب مستقیم اثرات منفی برای هر فرد افزایش می‌یابد. بااین‌حال اگر تسهیلات نامطلوب در هر مکان قرار گیرد و تنها تقاضای منطقۀ خود را پوشش دهند، درجۀ پدیدۀ NIMBY در محل داده‌شده به‌نسبت کمتر می‌شود.

در این پژوهش، مدل ریاضی بهینه‌سازی تک‌معیاره برای مکان‌یابی و تخصیص تسهیلات نامطلوب مطرح شده است. پدیدۀ NIMBY به‌طور مستقیم ازطریق ساختار تابع هدف مطرح شده است. ساختار تابع هدف این اجازه را می‌دهد تا از این حقیقت سخن گفته شود که ساکنان میزبان این تسهیلات کسانی‌اند که هزینه‌های زیست‌محیطی را جذب می‌کنند؛ درحالی‌که سایر مناطق از مزایای این تسهیلات لذت می‌برند. درجۀ پدیدۀ NIMBY برای ساکنان میزبان این تسهیلات، به‌دلیل جذب اثرات منفی به‌طور مستقیم زیاد است. هزینۀ پدیدۀ NIMBY برای یک تسهیل تابعی از تعداد کل گره‌هایی است که به‌وسیلۀ تسهیل نامطلوب پوشش داده شده است. با استفاده از این بینش اولیه، مدل‌های ریاضی به‌صورت توابع خطی، محدب و مقعر برای نشان‌دادن هزینۀ پدیدۀ NIMBY گسترش داده شده است. در این پژوهش از تابع هدف خطی استفاده شده است. باتوجه‌به اینکه میزان درجۀ آلودگی تسهیلات نامطلوب در دنیای واقعی به‌طور قطعی تعیین‌شدنی نیست و در مقالات گذشته و در واقعیت، اطلاعاتی در ارتباط با میزان این درجۀ آلودگی وجود نداشت، تصمیم گرفته شد تا عدم‌قطعیت در میزان درجۀ آلودگی این تسهیلات اعمال شود (سانگ و همکاران، 2013)؛ برای مثال شهری در نظر گرفته شده است و قرار است برای خانه‌های موجود (گره‌های تقاضا) در آن در فواصل مناسبی به‌تعداد بهینه سطل زباله (تسهیلات نامطلوب) قرار داده شوند؛ به‌گونه‌ای‌که میزان درجۀ آلودگی حاصل از این سطل زباله‌ها برای همسایه‌های این تسهیلات در کمترین حالت ممکن باشد. در شکل (1) تصویری برای نمایش این مسئله آورده شده است و مکان‌های تسهیلات نامطلوب (در این نمونه سطل زباله فرض شده است) و پوشش‌دهی نقاط با این سطل زباله‌ها در شکل نشان داده شده است.

 

مفروضات مسئله

در شروع برنامه‌ریزی برای حل مسئله، مفروضات این مسئله به‌شرح زیر است:

1- هیچ‌گونه تسهیلات نامطلوبی وجود ندارد و باید تازه ساخته شوند.

2- گره‌های تقاضا (برای مثال در یک شهر گره‌های تقاضا خانه‌ها هستند) وجود دارند. هر گره تقاضا مقدار تقاضای خود و اطلاعات محلی دوبعدی خود را دارد.

3- تمام گره‌های تقاضا برای مکان تسهیلات نامطلوب کاندید هستند.

4- هرگره تقاضا می‌تواند یک تسهیل نامطلوب باشد.

5- حداکثر تعداد تسهیلات داده‌شده کمتر از تعداد کل گره‌های کاندید است.

6- تسهیلات واقع در یک گره، همۀ تقاضا برای آن گره را پوشش می‌دهند.

7- برای هر گره تقاضا که به‌عنوان مکان برای تسهیل نامطلوب انتخاب می‌شود، یک درجۀ آلودگی اصلی برای پوشش‌دهی تقاضای خودش و یک درجۀ آلودگی حاشیه‌ای برای پوشش‌دهی گره اضافی با این تسهیل نامطلوب در نظر گرفته شده است (سانگ و همکاران، 2013).

نمادگذاری استفاده‌شده در مدل ریاضی به‌صورت جدول (3) است.

 

1

3

4

5

6

7

8

9

11

10

2

شکل 1- نمایش مسئله

 

جدول 3- معرفی نمادها، متغیرها و پارامترهای به‌کاررفته در مسئله

تعریف

نمادها، پارامترها و متغیرها

شاخص گره‌های تقاضا

 

تعداد کل گره‌های تقاضا

 

فاصلۀ اقلیدسی بین گره  و

 

درجۀ آلودگی اصلی از پدیدۀ NIMBY در گره j هنگامی که تسهیل مکان داده‌شده در گرۀ j  تنها تقاضای گره j  را پوشش می‌دهد.

 

درجۀ آلودگی حاشیه‌ای از روند خطی پدیدۀ NIMBY در گره j  هنگامی که گره اضافی با تسهیل نامطلوب واقع در j  پوشش داده شود.

 

محدودیت حداکثر فاصلۀ خدمت تسهیل نامطلوب (یکسان برای تمام تسهیلات)

 

حداکثر تعداد تسهیلات نامطلوب که می‌تواند تأسیس شود.

 

متغیر صفر و یک نشان‌دهندۀ تسهیل نامطلوب است که در گرهj  قرار دارد.

 

متغیر صفر و یک نشان‌دهندۀ گره iتخصیص داده‌شده به تسهیل در گره j  است.

 

عدد غیرمنفی و بزرگ

 

 

مدل ریاضی مسئله در شرایط قطعی

مدلی که برای موضوع مکان‌یابی تسهیلات نامطلوب در این مقاله استفاده شده است براساس مدل زیر است (سانگ و همکاران، 2013).

(1)

 

(2)

 

(3)

 

(4)

 

(5)

 

(6)

 

(7)

 

 

(1): تابع هدف شامل دو بخش است، بخش نخست مربوط به درجۀ آلودگی اصلی حاصل از تأسیس تسهیل نامطلوب است و بخش دوم مربوط به درجۀ آلودگی حاشیه‌ای حاصل از پوشش‌دهی گره اضافی با تسهیل نامطلوب است. درجه‌های آلودگی تابعی از تعداد گره‌های موجود هستند. (2): حداکثر محدودیت شعاع خدمات را اعمال می‌کند. (3): هر گره i تنها می‌تواند به یک تسهیل j تخصیص داده شود. (4): هر گره iدرصورتی می‌تواند به یک تسهیل در گره j  تخصیص داده شود که چنین تسهیلی وجود داشته باشد. (5): این محدودیت مستلزم آن است که اگر یک تسهیل در گره j اختصاص یافته باشد، گره jاز خودش خدمت می‌گیرد. (6): حداکثر تعداد تسهیلات نامطلوب که می‌تواند استقرار یابد. (7): همۀ متغیرهای تصمیم تخصیص و مکان‌یابی به متغیرهای باینری محدود می‌شوند (سانگ و همکاران، 2013).

ماهیت درجۀ آلودگی: بیوگاز تولیدی محل‌های دفن زبالۀ شهری دارای اجزای آلی و درصد بالایی از گاز متان فرّار هستند که باعث آسیب به لایۀ ازن می‌شوند. گازهای محل دفن از انجام مجموعه‌ای از واکنش‌های زیست شیمیایی روی مواد آلی تجزیه‌پذیرِ موجود در زباله در شرایط بی‌هوازی به دست می‌آید. این گازها شامل متان، دی اکسید کربن و گازهای هیدروژن، هیدروژن سولفاید، ترکیبات آلی فرار و غیره است. متان 60-50 درصد کل گاز محل دفن زباله را تشکیل می‌دهد که در اثر تجزیۀ بی‌هوازی پسماند تولید می‌شود. 50-40 درصد بقیه را عمدتاً دی اکسید کربن و جزءِ اندکی را گازهای دیگر ازجمله سولفید هیدروژن تشکیل می‌دهند. ترکیبات آلی فرّار گازهای محل دفن دارای اثرات سوئی بر سلامتی انسان‌ها هستند. این ترکیبات برای سلامتی انسان مضر است و بر مناطقی که در نزدیکی یا در محل‌های دفن ساخته شده‌اند و یا برای مناطق مسکونی با فاصلۀ کمتر از 100 متریِ آن، اهمیت دارند. مدل ریاضی استفاده‌شده در این پژوهش برای یافتن مکان‌های بهینۀ سطل‌های زباله است. درجۀ آلودگی که در تابع هدف این مدل ریاضی در نظر گرفته شده است نشان‌دهندۀ میزان گازهای متصاعدشده از زباله‌ها است که به‌صورت برداری شامل بازه‌ای از اعداد تصادفی تعریف می‌شوند. هر مکانی که به‌عنوان قرارگرفتن تسهیل نامطلوب انتخاب شود به‌ازای گره‌های اضافی که زیر پوشش خود قرار دهد شامل درجۀ آلودگی حاشیه‌ای می‌شود که درنهایت در مکانی که تسهیل نامطلوب قرار گرفته است آلودگی بیشتری ایجاد می‌شود.

 

مدل‌سازی در شرایط عدم‌قطعیت

باتوجه‌به ساختار مسئلۀ مطالعه‌شده در این پژوهش، اگر مدل به مدل قطعی تبدیل شود و مقدار درجۀ آلودگی که در این مسئله پارامتری تصادفی در نظر گرفته شده است، با بهترین مقدار آن جایگزین و مدل ریاضی ارائه‌شده با درجۀ آلودگی کم حل شود، در این صورت مسئله به جواب خوشبینانه‌ای می‌رسد که درواقع دیدگاه مناسبی را برای مکان بهینۀ تسهیلات نامطلوب برای تصمیم‌گیرنده فراهم نمی‌کند (میرحسنی، 1393). همچنین در نظر گرفتن بدترین حالت یا مقدار میانگین نیز تصمیم‌گیرنده را به بدترین حالت یا مقدار تعادلی هدایت می‌کند. دراین‌صورت نیز ممکن است مکان‌های مناسبی برای تسهیلات نامطلوب انتخاب نشود. باتوجه‌به اینکه در مسئلۀ مطالعه‌شده در این پژوهش، تغییرات دو پارامتر به‌طور هم‌زمان باید بررسی شوند و در روش تحلیل حساسیت اثر تغییر یک پارامتر وقتی بررسی می‌شود که سایر پارامترها ثابت فرض شده‌اند، این روش نیز در این مسئله کارا نیست. به‌دلیل برتری روش سناریو بر سایر روش‌های مواجه با عدم‌قطعیت، همچنین ساختار گسسته در مسئلۀ مطالعه‌شده در این پژوهش، برای در نظر گرفتن مسئله در حالت تصادفی، بهتر است از روش سناریو استفاده شود؛ به این دلیل که می‌توان تغییرات دو پارامتر درجۀ آلودگی اصلی و حاشیه‌ای را هم‌زمان بررسی کرد. همچنین از بین تعداد حالات زیادی که می‌توان برای میزان تغییرات این دو پارامتر در این مسئله در نظر گرفت، چند حالت مختلف از این دو پارامتر انتخاب می‌شود که در گذشته بیشتر استفاده شده است یا ازطریق تجربه این نتیجه حاصل شده است که این حالات کاربرد بیشتری در این مسئله دارد. سپس مدل در حالت‌های مختلف پارامترها حل و نتایج حاصل از سناریوها تجزیه و تحلیل می‌شود.

در اینجا عدم‌قطعیت در میزان درجۀ آلودگی و سناریوهای مختلف برای آن در نظر گرفته است و مسئله حل می‌شود. به‌دلیل گسسته‌بودن سناریوها و یک‌مرحله‌ای‌بودن، این مسئلۀ برنامه‌ریزی تصادفی در نظر گرفتن هم‌زمان سناریوها و حل جداگانۀ آنها تفاوتی در شرایط حل مسئله و جواب آن وجود ندارد و حل مدل گسترده در این حالت، تنها باعث افزایش زمان حل مسئله می‌شود. به این منظور از روش صبر و مشاهده برای مدل‌سازی این مسئله در حالت تصادفی استفاده می‌شود. این مسئلهSبار، هر دفعه برای یک سناریو حل شده است. درادامه جواب‌های به‌دست‌آمدۀ حاصل از سناریوها مقایسه شده و درنهایت امید ریاضی جواب سناریوها به دست آمده است. باتوجه‌به توضیحات ارائه‌شده تغییرات زیر در تابع هدف مدلِ ارائه‌شده به وجود آمده است.

(8)

 

 

تابع هدف شامل دو بخش است. بخش نخست مربوط به درجۀ آلودگی اصلی حاصل از تأسیس تسهیل نامطلوب است و بخش دوم مربوط به درجۀ آلودگی حاشیه‌ای حاصل از پوشش‌دهی گره اضافی به تسهیل نامطلوب است. این درجه‌های آلودگی تابعی از تعداد گره‌های موجود و گسسته‌اند و به‌صورت برداری شامل بازه‌ای از اعداد تصادفی تعریف می‌شوند. درحالت تصادفیِ این مسئله، به‌ازای سناریوهایی که برای این دو بردار درجۀ آلودگی تعریف می‌شوند، بازۀ تغییرات این دو بردار متفاوت است. همان طور که در مدل ریاضی تصادفی نشان داده شده است، به‌ازای هر سناریو متغیرهای باینری مکان تسهیلات نامطلوب و تخصیص متفاوت‌اند. درنهایت  برابر مقدار متوسط مقادیر  تعریف می‌شود و رابطۀ 9 به‌صورت زیر برقرار است.

(9)

 

(10)

 

 

دامنۀ تعریف سناریوها

طبق مدل ریاضی ارائه‌شده در حالت تصادفی، مسئله برای هر سناریو به‌صورت جداگانه حل و درنهایت سه سناریو مقایسه شده است و امید ریاضی تابع هدف برای کلیۀ سناریوها به دست می‌آید. باتوجه‌به مطالعات انجام‌شده در مقالات و همچنین مقالۀ اصلی که پایۀ کار این پژوهش بوده است، در ارتباط با میزان درجۀ آلودگی اصلی و حاشیه‌ای و ارتباط عددی این دو پارامتر، اطلاعاتی در دسترس نبوده است. همچنین به‌دلیل اینکه در نظر گرفتن کل حالات ممکن برای تغییرات این دو پارامتر کاری وقت‌گیر و غیرممکن است و در روش سناریو معمولاً چند حالت از بین حالت‌های ممکن در نظر گرفته می‌شود و همۀ حالات بررسی نمی‌شود، در این مسئله نیز سه حالت ممکن برای دامنۀ تغییرات این دو پارامتر در نظر گرفته می‌شود. باتوجه‌به اینکه ارتباط و میزان اختلاف درجۀ آلودگی اصلی و حاشیه‌ای نیز در مقالات گذشته نامشخص بوده است، در این پژوهش سناریوها براساس درجۀ اختلاف این دو پارامتر در نظر گرفته شده است که به‌شرح زیر است:

سناریوی(1): درجۀ آلودگی اصلی (a) 100 برابر درجۀ آلودگی حاشیه‌ای(b

سناریوی(2): هر دو در بازۀ نزدیک به‌هم تغییر می‌کنند؛

سناریوی(3): درجۀ آلودگی اصلی (a) 10 برابر درجۀ آلودگی حاشیه‌ای(b).

 

ساختار الگوریتم پیشنهادی

در این بخش به‌دلیل NP-hard بودن ماهیت مسئلۀ درحال مطالعه، برای حل آن در ابعاد بزرگ الگوریتم فراابتکاری شبیه‌سازی تبرید پیشنهاد شده است.

 

نمایش راه‌حل

نخستین مرحله در طراحی روش فراابتکاری، کدبندی مناسب برای تولید راه‌حل‌های امکان‌پذیر و کارا است. همان طور که گفته شد، در این مسئله nگره وجود دارد و تمام گره‌ها برای قرارگرفتن مکان تسهیل نامطلوب کاندید هستند. برای نمایش راه‌حل در این مسئله، بردار1×n  با اعداد صفر و یک در نظر گرفته شده است. این بردار برای نشان‌دادن گره‌هایی است که به‌عنوان مکان قرارگرفتن تسهیل نامطلوب انتخاب شده‌اند. صفربودن عدد در هر خانه به این معنی است که این گره برای مکان قرارگرفتن تسهیل نامطلوب انتخاب نشده است و اگر عدد یک بگیرد برای مکان قرارگرفتن تسهیل نامطلوب انتخاب شده است. این بردارِ جواب وارد الگوریتم می‌شود و طبق ساختاری که برای تابع هزینه تعریف شده است، برای تخصیص گره‌ها به تسهیلات نامطلوب انتخاب‌شده ماتریس n×n تشکیل می‌شود؛ این ماتریس، ماتریس تخصیص نامیده می‌شود و شامل اعداد 0 و 1 است؛ برای نمونه در شکل (1) نمایش بردار جواب برای n=10 گره آمده است. همان طور که در شکل (1) مشخص است این بردار شامل 10 گره است و گره‌های 1، 2، 6، 7 برای مکان قرارگرفتن تسهیل نامطلوب انتخاب شده‌اند.

 

10

9

8

7

6

5

4

3

2

1

0

0

0

1

1

0

0

0

1

1

شکل 1- نمایش بردار جواب برای n=10

 

تولید راه‌حل اولیه

جمعیت اولیه یکی از ویژگی‌های الگوریتم‌های تکاملی است که بر سرعت هم‌گرایی و کیفیت راه‌حل نهایی تأثیر می‌گذارد؛ بنابراین تولید جمعیت اولیۀ با کیفیت قدم مهمی برای الگوریتم محسوب می‌شود. در این مسئله به‌دلیل تولید جواب‌های نشدنی زیاد اگر راه‌حل اولیه، تصادفی تولید شود الگوریتم از فضای شدنی خارج می‌شود؛ همچنین به‌دلیل بزرگ‌بودن فضای جواب، نشدنی باقی می‌ماند؛ به‌همین دلیل راه‌حلی ابتکاری برای تولید جواب اولیه به‌شرح زیر ارائه شده است:

1-       یک ماتریس n×n  فاصله تشکیل می‌شود. همان طور که ذکر شد n تعداد کل گره‌ها است و تمام گره‌ها برای قرارگرفتن تسهیل نامطلوب کاندید هستند.

2-       برای کل گره‌ها محدودیت شعاع خدمات چک می‌شود تا مشخص شود هر گره می‌تواند کدام‌یک از گره‌های دیگر را پوشش دهد؛ بنابراین در این مرحله یک ماتریس 0 و 1 تشکیل می‌شود. عدد 1 در خانه‌هایی از ماتریس به این معنی است که این گره با تسهیل مذکور پوشش‌دهی می‌شود و عدد 0 به‌معنای عدم پوشش‌دهی این گره با تسهیل مذکور است.

3-       در گام بعدی تعداد یک‌های هر ستون شمارش می‌شود. درنهایت برای هر ستون (هر گره) یک عدد وجود دارد. این عدد نشان‌دهندۀ تعداد گره‌هایی است که این گره می‌تواند به‌عنوان تسهیل نامطلوب پوشش دهد.

4-       از بین این اعداد، حداکثرِ آن انتخاب می‌شود. درنتیجه این گره به‌عنوان مکان قرارگرفتن تسهیل نامطلوب انتخاب می‌شود.

5-       تمام گره‌هایی که در ستون مربوط به این تسهیل نامطلوب عدد یک را گرفته‌اند، زیر پوشش این تسهیل نامطلوب قرار می‌گیرند.

6-       بعد از تخصیص گره‌ها به این تسهیل، سطرها و ستون‌های مربوط به گره‌هایی حذف می‌شوند که پوشش داده شده‌اند.

7-       شرط توقف بررسی می‌شود: اگر تمام گره‌ها پوشش داده شده‌اند (ماتریس اولیه 0 و 1 تهی شود) الگوریتم پایان می‌یابد؛ در غیر این صورت به گام 8 می‌رود.

8-       شمارش یک‌ها در ستون‌هایِ باقی‌مانده به‌روزرسانی می‌شود و به گام 4 می‌رود.

در پایان این الگوریتم، بردار 1×n وارد الگوریتم SA می‌شود و طبق این بردار ماتریس تخصیص شکل می‌گیرد.

 

روش تخصیص

ابتدا بردار جواب با روش ابتکاری به دست می‌آید. همان طور که گفته شد این بردار شامل اعداد 0 و1 است و وارد الگوریتم می‌شود. برای تشکیل ماتریس تخصیص، برای تسهیلات نامطلوب انتخاب‌شده محدودیت شعاع حداکثر خدمات برای کل گره‌های موجود چک می‌شود. هرکدام از گره‌ها که بتوانند زیر پوشش این تسهیلات نامطلوب باشند در این ماتریس مشخص می‌شوند. سپس برای تخصیص گره‌ها به تسهیلات نامطلوب باتوجه‌به محدودیتی که در این مسئله ذکر شده است، هر گره‌ای که برای تسهیل نامطلوب انتخاب شود گره خود را حتماً پوشش می‌دهد؛ بنابراین درایۀ مربوط به این گره در ماتریس 1 می‌شود. سپس برای سایر گره‌ها برای پوشش‌دهی با تسهیلات نامطلوب انتخاب‌شده سه حالت پیش می‌آید:

حالت نخست: این گره در شعاع پوشش‌دهی هیچ‌کدام از تسهیلات نامطلوب انتخاب‌شده نیست؛ در این‌صورت جواب نشدنی تولید می‌کند.

حالت دوم: این گره می‌تواند ازطریق یکی از تسهیلات نامطلوب انتخاب‌شده خدمت بگیرد؛ بنابراین فقط یک انتخاب دارد و درایۀ مربوط به این گره و تسهیل نامطلوب 1 می‌شود.

حالت سوم: این گره می‌تواند ازطریق دو یا تعداد بیشتری از تسهیلات خدمت بگیرد؛ در این صورت باتوجه‌به اینکه پوشش‌دهی این گره ازطریق کدام تسهیل درجۀ آلودگی کمتری داشته باشد، تسهیل مدنظر را برای خدمت‌گرفتن انتخاب می‌کند و درایۀ مربوطه عدد 1 را می‌گیرد.

درنهایت در ماتریس تخصیص، درایه‌های زیر پوشش تسهیلات نامطلوب مقدار 1 را به‌خود اختصاص می‌دهند و سایر درایه‌های ماتریس 0 می‌شوند و یک ماتریس 0 و1 که شامل تخصیص گره‌ها به تسهیلات نامطلوب است به وجود می‌آید. برای نشان‌دادن روش تخصیص، نمونه‌ای با n=6 گره آورده شده است. در شکل (2) بردار نمایش جواب برای این نمونه آورده شده است.

 

6

5

4

3

2

1

0

0

0

1

0

 

شکل 2- بردار نمایش جواب باn=6 گره

 

بردار موجود در شکل (2) از دو روش ساخته می‌شود: (i) به‌صورت تصادفی؛ (ii) ازطریق روش ابتکاری. در این پژوهش بردار جواب اولیه با استفاده از روش ابتکاری ساخته شده است. در این نمونه با 6 گره، گره‌های 1 و 3 به‌عنوان تسهیل نامطلوب انتخاب شده‌اند و مقدار 1 را به‌خود اختصاص داده‌اند. صفربودن سایر درایه‌ها به این معنی است که این گره‌ها برای مکان قرارگرفتن تسهیل نامطلوب انتخاب نشده‌اند. این بردار وارد الگوریتم می‌شود و طبق توضیحات داده‌شده برای تسهیلات نامطلوب 1 و 3 شعاع پوشش‌دهی برای کلیۀ گره‌ها چک می‌شود. شکل (3) نمایش ماتریس فاصله برای مثال ذکرشده است و شعاع حداکثر خدمات R=40 است.

 

6

5

4

3

2

1

 

30

20

50

30

20

0

1

20

100

30

60

0

20

2

100

20

30

0

60

30

3

80

20

0

30

30

50

4

10

0

20

20

100

20

5

0

10

80

100

20

30

6

شکل 3- ماتریس فاصله برای n=6 گره

 

در شکل (3)، برای تسهیلات نامطلوب 1 و 3 باتوجه‌به ماتریس فاصله و R، برای تمامی گره‌ها شعاع پوشش‌دهی خدمات چک می‌شود. مطابق شکل (4) درایه‌های مربوط به گره‌هایی که بتوانند زیر پوشش این تسهیلات باشند مقدار 1- می‌گیرند و سایر درایه‌ها مقدار 0 را می‌گیرند. پس از به وجود آمدن ماتریس در شکل (4) درایه‌های روی قطر اصلیِ مربوط به تسهیلات نامطلوبِ انتخاب‌شده، 1 می‌شود. به این دلیل که تسهیلات نامطلوب موجود در هر گره باید تمام تقاضای گره خود را پوشش دهد، ماتریس موجود در شکل (5) به وجود می‌آید.

در گام بعدی باید مشخص شود سایر گره‌هایی که در شعاع پوشش‌دهی تسهیلات نامطلوب انتخاب‌شده هستند ازطریق کدام تسهیل تقاضای خود را برآورده کنند. طبق مسائلی که در روش تخصیص ذکر شد، نحوۀ پوشش‌دهی این گره‌ها مشخص می‌شود. همان طور که در شکل (5) مشخص شده است گره 2 تنها می‌تواند از تسهیل 1 خدمت بگیرد؛ بنابراین درایۀ سطر 2 و ستون 1، مقدار 1 می‌گیرد. گره 4 تنها می‌تواند از تسهیل 3 خدمت بگیرد؛ بنابراین درایۀ مربوط به آن مقدار 1 را می‌گیرد. گره 5 می‌تواند از هر دو تسهیل انتخاب‌شده خدمت بگیرد؛ بنابراین گره‌ای را برای خدمت‌گرفتن انتخاب می‌کند که میزان درجۀ آلودگی حاشیه‌ای تولیدشده با این تسهیل کمتر باشد. در این نمونه فرض می‌شود ازطریق تسهیل 3 درجۀ آلودگی کمتری دارد؛ بنابراین درایۀ سطر 5 و ستون 3 مقدار 1 می‌گیرد. همچنین گره 6 که تنها در شعاع پوشش‌دهی تسهیل 1 است، درایۀ سطر 6 و ستون 1 مقدار 1 را می‌گیرد و سایر درایه‌ها 0 می‌شوند. درنهایت ماتریس موجود در شکل (6) به وجود می‌آید. در این ماتریس تخصیص همۀ گره‌ها به تسهیلات نامطلوب انتخاب‌شده، مشخص شده است.

 

 

6

5

4

3

2

1

 

0

0

0

1

0

1

 

 

 

 

 

 

 

 

0

0

0

1-

0

1-

1

0

0

0

0

0

1-

2

0

0

0

1-

0

1-

3

0

0

0

1-

0

0

4

0

0

0

1-

0

1-

5

0

0

0

0

0

1-

6

شکل 4- ماتریس برای چک‌کردن شعاع پوشش‌دهی گره‌ها ازطریق تسهیلات نامطلوب

 

6

5

4

3

2

1

 

0

0

0

1

0

1

 

 

 

 

0

0

0

1-

0

1

1

0

0

0

0

0

1-

2

0

0

0

1

0

1-

3

0

0

0

1-

0

0

4

0

0

0

1-

0

1-

5

0

0

0

0

0

1-

6

شکل 5- ماتریس پوشش‌دهی تقاضای هر گره ازطریق تسهیل نامطلوب واقع در همان گره

 

6

 

5

4

3

2

1

 

0

 

0

0

1

0

1

 

 

 

 

 

 

 

 

 

0

 

0

0

0

0

1

1

0

 

0

0

0

0

1

2

0

 

0

0

1

0

0

3

0

 

0

0

1

0

0

4

0

 

0

0

1

0

0

5

0

 

0

0

0

0

1

6

شکل 6- ماتریس 0 و1 تخصیص گره‌ها به تسهیلات نامطلوب

ساختار همسایگی

روش انتقال از یک راه‌حل به راه‌حل همسایۀ آن ازطریق عامل کلیدی شناخته‌شده با ساختار همسایگی مشخص می‌شود. در اینجا از چهار عملگر برای تولید راه‌حل همسایه در الگوریتم شبیه‌سازی تبرید استفاده شده است. ساختارهای همسایگی به‌شرح زیرند:

ساختار همسایگی جابه‌جایی[xxxix] : این ساختار همسایگی با جابه‌جاکردن موقعیت دو عضو در رشتۀ حل کاندیدا، راه‌حل جدیدی تولید می‌کند. به این صورت که دو عضو را به‌تصادف انتخاب می‌کند و موقعیت این دو عضو جابه‌جا می‌شود.

ساختار همسایگی معکوس[xl]: این ساختار همسایگی دو عضو را به‌تصادف انتخاب می‌کند و ترتیب قرارگرفتن موقعیت عناصر را در بین این دو عضو معکوس می‌کند.

ساختار همسایگی جایگذاری[xli]: در این ساختار همسایگی دو عضو به‌تصادف انتخاب می‌شود.

ساختار همسایگی جهش[xlii]: یک عضو به‌تصادف انتخاب می‌شود و اگر مقدار این خانه از بردار 1 باشد، 0 می‌شود و اگر 0 باشد، 1 می‌شود.

 

ساختار کلی الگوریتم پیشنهادی

فلوچارت الگوریتم ابتکاری و الگوریتم پیشنهادی در شکل (7) آورده شده است.

 

تحلیل و نتایج محاسباتی

در این بخش عملکرد و کارایی مدل ریاضی مسئلۀ مکان‌یابی تسهیلات نامطلوب با در نظر گرفتن شرایط عدم‌قطعیت در پارامتر درجۀ آلودگی و الگوریتم پیشنهادی با استفاده از نرم‌افزار بهینه‌سازی سیپلکس (12.6) و MATLAB (R2015b) ارزیابی می‌شوند. با وجود آنکه در مدل ارائه‌شده متغیرها وابسته به سناریو هستند، برای هر سناریو باتوجه‌به آنکه مقدار پارامترهای درجۀ آلودگی سناریو برای آنها تعریف‌شده است، ورودی مسئله‌اند؛ به همین دلیل حالت مجهولی در سناریوها وجود ندارد و درنتیجه با نرم‌افزار IB ILOG حل‌شدنی است. همچنین در اینجا هر سناریو جداگانه در نرم‌افزار حل شده است؛ درنتیجه حالت قطعی دارد. همچنین درحالتی‌که چند سناریو هم‌زمان با هم حل شده‌اند (به‌دلیل ماهیت مسئله که سناریوها برای پارامتر درجۀ آلودگی تعریف شده است) سناریوها دارای مقادیر معلوم هستند.

بدین منظور نحوۀ تولید نمونه‌های تصادفی شرح داده شده است. در این بخش12 نمونه مسئله در ابعاد کوچک و متوسط برای مقایسۀ حل دقیق سیپلکس و الگوریتم فراابتکاری شبیه‌سازی تبرید و 16 نمونه مسئله برای مقایسۀ کارایی الگوریتم فراابتکاری شبیه‌سازی تبرید و ژنتیک در ابعاد بزرگ به‌صورت تصادفی تولید شده است. الگوریتم فراابتکاری ژنتیک که در این مقاله استفاده شده است مربوط به مقالۀ سانگ و همکاران (2013) است.

 

 

بهبود با الگوریتم SA

 

چک‌کردن محدودیت شعاع خدمات برای تمامی گره‌ها و به دست آمدن ماتریس 0و1

تولید یک عدد تصادفی (p) بین

خیر

تشکیل ماتریس تخصیص

بردار جواب اولیه:  

محاسبۀ مقدار تابع هدف

تولید راه‌حل همسایه

خیر

بله

بله

بله

تشکیل ماتریس  فاصله‌ها

شروع

شمارش یک‌های هرستون (هرگره)

انتخاب ماکزیمم عدد در بین ستون‌ها

اختصاص‌دادن همه گره‌های دارای شرایط تخصیص به این تسهیل

حذف سطرها و ستون‌های تخصیص داده شده

بررسی شرط توقف

پایان

خیر

             

خیر

بله

بله

خیر

بررسی شدنی بودن جواب

 

    

 

 

        

 

K = k + 1

 

پایان

خیر

آیا شرط توقف برقرار است؟

بله

کاهش دما

بله

 
 

 

شکل 7- فلوچارت الگوریتم پیشنهادی

 

تولید داده‌های آزمایشی

باتوجه‌به اینکه اطلاعات مربوط به مسائل حل‌شده در مقالات مشابه برای مسئلۀ مدنظر موجود نبوده است؛ همچنین به‌دلیل در دسترس نبودن اطلاعات نمونه‌های واقعی، لازم است داده‌های آزمایشی برای بررسی و اعتبارسنجی مدل ریاضی و کیفیت نتایج الگوریتم‌های فراابتکاری تولید شوند. در این پژوهش باتوجه‌به الگوی موجود در ادبیات موضوع برای ارزیابی و مقایسۀ نتایج مدل ریاضی و الگوریتم‌های فراابتکاری از نمونه‌های تصادفی استفاده شده است. نحوۀ تولید آنها در جدول (4) و (5) آمده است.

جدول 4- مقادیر داده‌های تصادفی

پارامترها

نمادها

مقادیر

تعداد کل گره‌های موجود

N

{40،…،9000}

حداکثر تسهیلات نامطلوب

K

{5،…،800}

حداکثر شعاع پوشش‌دهی

R

{100،…،750}

فاصلۀ بین گره‌ها

d

(1، 1000)

 

سناریوها برای دامنۀ تغییرات درجۀ آلودگی اصلی و حاشیه‌ای براساس درجۀ اختلاف این دو پارامتر در نظر گرفته شده و به‌شرح زیر است.

سناریوی(1) : درجۀ آلودگی اصلی (a) 100برابر درجۀ آلودگی حاشیه‌ای(b)

سناریوی(2): هر دو در بازۀ نزدیک به‌هم تغییر می‌کنند.

سناریوی(3): درجۀ آلودگی اصلی (a) 10برابر درجۀ آلودگی حاشیه‌ای(b)

 

جدول 5- بردار درجۀ آلودگی در سناریوها

دامنۀ تغییرات درجۀ آلودگی حاشیه‌ای

دامنۀ تغییرات درجۀ آلودگی اصلی

سناریوها

b=(10،300)

a=(1000،30000)

سناریوی 1

b=(50،400)

a=(100،500)

سناریوی 2

b=(10،300)

a=(100،3000)

سناریوی 3

 

تنظیم پارامتر الگوریتم شبیه‌سازی تبرید

در این مقاله برای سه مثال در سطح کوچک، متوسط و بزرگ مقادیر مختلف فاکتورهای تأثیرگذار بر عملکرد الگوریتم، آزمایش شده است. عوامل مؤثر بر عملکرد الگوریتم و سطوح آنها در جدول 6 و 7 نشان داده شده است. در جدول 6 برای هر عملگر، احتمالی در نظر گرفته شده است. درواقع این احتمال‌ها و ترکیب‌هایی که برای هر سطح عملگرها در نظر گرفته شده است به دو دلیل است: (1) به‌صورت آزمایش و خطا و نتایج مطلوب به‌دست‌آمده برای نمونه‌های آزمایشی، ترکیب‌های مناسب احتمال‌های چهار عملگر به دست آمده است؛ (2) باتوجه‌به اینکه باید مجموع احتمال عملگرا یک باشد، اگر احتمال هر عملگر به‌تنهایی یک سطح تعیین شود، ممکن است در آزمایش تاگوچی طرحی انتخاب شود که مجموع احتمال عملگرها بیشتر از یک شوند.

 

جدول 6- سطوح مختلف عملگرهای الگوریتم شبیه‌سازی تبرید

عملگرهای الگوریتم

سطوح مختلف ترکیب احتمال عامل‌ها

1

2

3

جابه‌جایی

0/4

0/3

0/2

جایگذاری

0/2

0/2

0/2

معکوس

0/2

0/2

0/2

جهش

0/2

0/3

0/4

جدول 7- سطوح مختلف پارامترهای الگوریتم شبیه‌سازی تبرید

پارامترهای الگوریتم

سطوح مختلف عامل‌ها

 

1

2

3

Max sub IT

50

40

60

T0

10

30

50

Alfa

0/99

0/89

0/79

 

برای تعیین سطوح مطلوب و اقتصادی پارامترهای الگوریتم باتوجه‌به سطوح تعیین‌شده در جداول 6 و 7، از طرح تاگوچی  برای انتخاب سطوح بهینۀ پارامترها استفاده شده است. همچنین برای رسیدن به نتایج قابل اطمینان‌تر، هر ترکیب 10 بار اجرا شده است و میانگین آنها برای نتیجۀ حاصل از این ترکیب ثبت می‌شود. در نمودار میانگین SN Ratios، سطحی از فاکتورها که بیشترین مقدار SN Ratios را دارند، بهترین سطح فاکتور انتخاب می‌شود. این مقادیر در جدول (8) نشان داده شده است.

 

جدول 8- فاکتورها و مقادیر مناسب پارامترهای الگوریتم شبیه‌سازی تبرید

طبقه‌بندی مسائل

پارامترها

بزرگ

 

متوسط

 

کوچک

 

 

40

2

40

2

60

3

Max sub IT

10

1

10

1

30

2

T0

0/79

3

0/79

3

0/99

1

Alfa

ترکیب2

2

ترکیب1

1

ترکیب 1

1

Operators

 

شاخص بررسی کارایی الگوریتم‌ها

برای بررسی عملکرد الگوریتم‌ها از شاخص PRD استفاده می‌شود. این معیار از رابطۀ 11 محاسبه می‌شود.

(11)

 

 

در این رابطه،  تابع هدف حاصل از حل یک نمونه با استفاده از الگوریتم مدنظر و  کمترین مقدار تابع هدف حاصل از حل آن نمونه با استفاده از روش‌های حل مختلف است.

 

نتایج در ابعاد کوچک و متوسط

در این بخش نتایج آزمایش‌های عددی مسئله با در نظر گرفتن 3 سناریو در هر نمونه برای 12 نوع مسئله در ابعاد کوچک و متوسط با نرم‌افزار بهینه‌سازی سیپلکس و الگوریتم فراابتکاری شبیه‌سازی تبرید آمده است. درنهایت نتایج مقایسه شده‌اند. در ابعاد کوچک و متوسط، الگوریتم شبیه‌سازی تبرید به جواب بهینۀ سیپلکس می‌رسد. در جدول (9) نتایج عددی نمونه‌های آزمایشی آمده است.

 

جدول 9- نتایج محاسباتی مسائل نمونه در ابعاد کوچک و متوسط در نرم‌افزار سیپلکس و الگوریتم شبیه‌سازی تبرید

سناریو3

سناریو2

سناریو1

مسئله

T(s)

SA

T(s)

Cplex

T(s)

SA

T(s)

Cplex

T(s)

SA

T(s)

Cplex

R

K

N

18

11919

45/0

11919

43/37

4166

42/0

4166

17/26

41984

67/0

41984

230

5

40

83

24619

62

24619

58

42333

31/0

42333

003/47

326737

218

326737

200

10

70

75

36646

15.8

36646

32

30581

53/0

30581

3/115

70431

45/3

9/70430

100

30

100

70

7943

22

7943

28

11678

9

11678

643/72

29296

532

29296

300

30

200

330

8032

292

8032

250

17305

32/14

17305

230

19899

157

19899

250

40

300

250

7889

14/99

7889

64

82769

86

82769

460

23615

577

23615

350

100

400

490

16104

586

16104

300

102077

144

102077

400

23485

577

23485

400

100

500

450

9716

68

9716

500

121801

221

121801

700

23115

658

23115

400

100

600

400

12131

309

12131

600

143565

175

143565

351

22995

2875

22995

450

100

700

600

10678

562

10678

500

161562

273

161562

400

57669

1201

57669

600

100

800

690

47824

275

47824

800

451202

105.38

451202

547

101419

785

101419

750

110

900

900

11607

481

11607

900

201171

147

201171

774

95267

5460

95267

700

280

1000

 

تحلیل نتایج در ابعاد کوچک و متوسط

همان طور که از جدول نتایج عددی مشخص است در همۀ نمونه‌های آزمایشی، الگوریتم فراابتکاری به جواب بهینۀ نرم‌افزار حل دقیق سیپلکس رسیده است. نتایجِ مقایسۀ مقدار تابع هدف در سه سناریو برای نمونه‌های آزمایشی در شکل (8) آمده است. در سناریوی 1 که مقدار درجۀ آلودگی اصلی 100 برابر درجۀ آلودگی حاشیه‌ای فرض شده است، در ابعاد کوچک، نرم‌افزار سیپلکس در زمان کمتری به جواب بهینه رسیده است و در ابعاد متوسط، الگوریتم فراابتکاری در زمان کمتر به جواب بهینه رسیده است. در سناریوی 2 (درجۀ آلودگی اصلی و حاشیه‌ای هر دو در یک دامنۀ تغییرات) و سناریوی 3 (درجۀ آلودگی اصلی 10 برابر درجۀ آلودگی حاشیه‌ای) است، نرم‌افزار سیپلکس در همۀ نمونه‌ها به‌جز یک مورد در زمان کمتری به جواب بهینه رسیده است.

شکل (4-12): فلوچارت الگوریتم پیشنهادی

3-7: فلوچارت الگوریتم ابتکاری

 

باتوجه‌به اینکه مسئلۀ درحال مطالعه در این مقاله برنامه‌ریزی تصادفی یک‌مرحله‌ای است، از شاخصی با عنوان EVPI[xliii] (متوسط ارزش اطلاعات کامل) استفاده می‌شود که مبین اهمیت پرداختن به عدم‌قطعیت اطلاعات است. این شاخص به‌صورت زیر تعریف می‌شود و نشان می‌دهد تا چه اندازه کمبود و نقصان اطلاعات تأثیرگذار است.

(12)

 

 

در این رابطه،  مقدار تابع هدف اینجا و اکنون است؛ به این معنی است که اگر در مدل هم‌زمان همۀ سناریوها با احتمال مربوطه در نظر گرفته شود، درنهایت مقداری که می‌دهد  نامیده می‌شود.  مقدار تابع هدف صبر و مشاهده است که همچنان به این معنی است که اگر مسئله S بار و هر بار برای یک سناریو حل شود،  برابر با مقدار متوسط مقادیر  است. در مسئلۀ مکان‌یابی تسهیلات نامطلوب درحال مطالعه در این پژوهش به‌دلیل گسسته‌بودن سناریوها مقدار این دو تابع هدف یکسان است (  )؛ بنابراین مقدار شاخص  است. کوچک‌بودن این شاخص نشان می‌دهد که به دست آوردن اطلاعات دربارۀ آینده تأثیر درخور توجهی ندارد.

نتایج در ابعاد بزرگ

در این بخش به‌دلیل اینکه نرم‌افزار سیپلکس قادر به حل نمونه‌های آزمایشی برای ابعاد 1000 گره و بزرگتر از این بُعد از مسئله نیست، نتایج آزمایش‌های عددی مسئله با در نظر گرفتن 3 سناریو در هر نمونه برای 16 نوع مسئله در ابعاد بزرگ با الگوریتم‌های فراابتکاری شبیه‌سازی تبرید و ژنتیک حل شده است. زمان توقف هر دو الگوریتم 1 ساعت است. درنهایت نتایج حاصل مقایسه شده‌اند. الگوریتم ژنتیک براساس مقالۀ سانگ و همکاران (سانگ و همکاران، 2013) نوشته شده است و به دلیل اینکه در ابعاد بزرگ قادر به تولید جواب‌های شدنی نبوده است، از روش ابتکاری استفاده می‌شود که در الگوریتم شبیه‌سازی تبرید برای تولید جواب اولیه استفاده شده است. هر نمونه برای هر سناریو 10 بار اجرا شده و میانگین نتایج برای هر سناریو در جدول نتایج آمده است. همان طور که از جدول نتایج عددی و نمودارهای ترسیم‌شده مشخص است، در تمام نمونه‌های آزمایشی، الگوریتم شبیه‌سازی تبرید در مقایسه با الگوریتم ژنتیک کمترین مقدار تابع هدف را دارد. در ابعاد بزرگ هرچه نمونه بزرگ‌تر می‌شود کارایی الگوریتم ژنتیک به‌شدت پایین‌تر می‌آید و در زمان 1 ساعت که معیار مقایسۀ دو الگوریتم است در ابعاد 4000 – 5000 گره، تنها قادر به تولید یک جواب شدنی است و در ابعاد 5000 – 7800 گره، الگوریتم ژنتیک در زمان یک ساعت قادر به تولید یک جواب شدنی نیست و 2ساعت زمان لازم داشته است. در ابعاد 7800 گره، 3 ساعت و برای 9000 گره، در مدت زمان 3 ساعت موفق به تولید یک جواب شدنی هم نبوده است. درصورتی‌که الگوریتم شبیه‌سازی تبرید قادر به تولید جواب‌های بهتر در زمان کمتری است و سرعت همگرایی و عملکرد بهتری نسبت به الگوریتم ژنتیک در تمام نمونه‌های آزمایشیِ مسئله دارد. همان طور که برای ابعاد کوچک و متوسط، شاخص EVPI توضیح داده شد، برای ابعاد بزرگ نیز مقدار شاخص  است و کوچک‌بودن این شاخص نشان می‌دهد به دست آوردن اطلاعات دربارۀ آینده، تأثیر درخور توجهی ندارد. نمودار متوسط مقادیر PRD برای مسائل با ابعاد بزرگ در شکل (9) ترسیم شده است. همان طور که در شکل نشان داده شده است، مقادیر PRD برای الگوریتم شبیه‌سازی تبرید صفر است؛ به این دلیل که در تمامی نمونه‌ها مقدار تابع هدف حداقل را دارد.

 

 

شکل 8- نمودار مقایسۀ مقدار تابع هدف سناریوها

 

شکل 9- نمودار میانگین مقادیر PRD برای الگوریتم‌های شبیه‌سازی تبرید و ژنتیک

 

جدول 10- نتایج محاسباتی مسائل نمونه در ابعاد بزرگ در الگوریتم شبیه‌سازی تبرید و ژنتیک

سناریو3

سناریو2

سناریو1

مسئله

PRD

GA

SA

PRD

GA

SA

PRD

GA

SA

R

K

N

525/0

88903

58283

0/998

36473

18248

3/05

141034

34803

700

180

1200

0/33

131145

98132

0/073

88253

82208

1/67

993614

371136

250

170

1500

0/087

122338

112487.6

0/017

293615

288594

2/012

477414

158461

700

200

1800

0/0958

116326

106154

0/011

608798

602000

1/714

670144

246855

450

250

2000

0/199

124531

103784

0/041

156564

150331

0/626

296827

182467

750

350

2500

0/142

178501

156227

0/088

164871

151460

2/11

176514

56738

700

400

3000

0/343

66727

49661

0/158

447115

386031

1/953

151955

51457

650

500

3500

0/478

195616

132279

0/072

516602

481855

0/84

299406

162699

550

710

4000

0/516

298207

196583

0/103

500190

453449

0/757

442409

251731

500

760

4500

0/311

405436

309065

0/155

288684

249849

0/655

464997

280960

420

600

5000

2/21

188111

58601

0/144

490289

428386

0/478

502609

340046

500

605

5300

0/22

692633

566073

0/28

697428

542459

0/512

791088

523091

620

615

6000

0/207

613306

507875

0/078

569358

528054

0/614

825242

511186

600

610

6500

0/336

693486

518854

0/497

5324730

3555430

0/449

637137

439638

715

680

7100

0/197

858051

716544

0/662

135310

81406

0/964

680616

346400

690

750

7800

-

-

924869

-

-

451583

-

-

303436

640

800

9000

 

نتیجه‌گیری و پیشنهادات آتی

در این مقاله مسئلۀ مکان‌یابی تسهیلات نامطلوب با محوریت کاهش درجۀ آلودگی حاصل از این تسهیلات درحال مطالعه قرار گرفت. همچنین این مسئله به‌صورت کامل تشریح و مدل ریاضی آن ارائه شد. باتوجه‌به اینکه در مقالات گذشته، همچنین در دنیای واقعی میزان دقیق این درجۀ آلودگی نامشخص است، تصمیم گرفته شد این مسئله در حالت عدم‌قطعیت در میزان درجۀ آلودگی حاصل از این تسهیلات بررسی شود. سپس با بررسی روش‌های مواجهه با عدم‌قطعیت و روش‌های مدل‌سازی مسائل برنامه‌ریزی تصادفی، روش سناریو برای در نظر گرفتن عدم‌قطعیت در این مسئله به کار گرفته شد. از طرف دیگر سناریوهایی برای در نظر گرفتن عدم‌قطعیت در میزان درجۀ آلودگی این تسهیلات برای نقاط اطراف آنها طراحی شد. مسئله برای نمونه‌های آزمایشی مختلف در سناریوهای طراحی‌شده در ابعاد کوچک و متوسط با نرم‌افزار حل دقیق سیپلکس حل شد و جواب‌های بهینه به دست آمد. باتوجه‌به ماهیت پیچیدۀ این مسئله، برای حل آن در ابعاد بزرگ، الگوریتم فراابتکاری شبیه‌سازی تبرید پیشنهاد داده شد. باتوجه‌به اینکه فضای جواب بزرگ است، برای تولید جواب اولیه به‌جای تولید راه‌حل تصادفی از راه‌حلی ابتکاری برای تولید جواب اولیۀ شدنی در این مسئله استفاده شد. نتایج محاسباتی حل بهینۀ سیپلکس و الگوریتم شبیه‌سازی تبرید در ابعاد کوچک و متوسط مقایسه شدند. هر دو روش به جواب بهینه دست یافتند و تفاوت در زمان حل این نمونه‌ها بود. برای ابعاد بزرگ نمونه‌های آزمایشی با استفاده از الگوریتم شبیه‌سازی تبرید و الگوریتم ژنتیک که در ادبیات این مسئله موجود بود، مقایسه شدند و کارایی بهتر الگوریتم شبیه‌سازی تبرید در همگراشدن به جواب بهینه و زمان حل کمتر در نمونه‌ها و سناریوهای مختلف به اثبات رسید. محورهای پیشنهاد برای پژوهش‌های آتی به شرح زیر است:

1- پیاده‌سازی مدل در یک مطالعۀ موردی واقعی برای ایجاد درک بهتر از مسئله؛

2- اضافه‌کردن محدودیت ظرفیت برای نزدیک‌ترشدن به دنیای واقعی؛

3- بررسی مسئلۀ مکان‌یابی- مسیریابی برای تعیین مسیرهای بهینۀ حمل و نقل بین تسهیلات و نقاط زیر پوشش.



[i] Not in my backyard (NIMBY)

[ii] Song et al

[iii] Snyder

[iv] Simulated annealing

[v] Mirchandani & odoni

[vi]Louveaux & Thisse

[vii] cooper

[viii] Sheppard

[ix] Mirchandani & Oudjit

[x] Weaver and church

[xi] Approximation Algorithm

[xii] Ravi & Sinha

[xiii]Berman and Odoni

[xiv] Pavankumar et al

[xv] Rosa et al

[xvi] Gulpmar et al

[xvii] Hu et al

[xviii] N Markovic et al

[xix] Puga & Tancrez

[xx] E. Erkut, S. Neuman

[xxi] Daskin

[xxii] E Melachrinoudis

[xxiii] E Melachrinoudis &  TP Cullinane

[xxiv] F Plastria

[xxv] Farber

[xxvi] J Brimberg & H Juel

[xxvii] F Plastria, E Carrizosa

[xxviii] J Fernández, P Fernández &  B Pelegrın

[xxix] E Melachrinoudis &  Zaharias

[xxx] Rakas, J., Teodorović, D., & Kim

[xxxi] Colebrook, M., Gutiérrez, J., & Sicilia, J

[xxxii] Rodríguez et al

[xxxiii] Colebrook, M., & Sicilia, J

[xxxiv] G Tuzkaya et al

[xxxv] K Yamaguchi

[xxxvi] Tang et al

[xxxvii] F Abastante et al

[xxxviii]Wichapa, N., & Khokhajaikiat, P

[xxxix] Swap

[xl] Reversion

[xli] Insertion

[xlii] Mutation

[xliii] The Expected Value of Perfect Information (EVPI)

Taqavi Fard, M.T. Mousavi, S.E. Heydar, M. Mojtahedi, S.M.H. (2008). "A new fuzzy multi-objective model to undesirable facility location". 5th International Conference on Industrial Engineering . Iran University of Science and Technology. (In Persian).

Mirhassani, S.A. (2014). Stochastic programming. First Edition. Amirkabir University of Technology Press. (In Persian).

Abastante، F. Bottero، M. Greco، S. Lami، I. (2014). "Addressing the Location of Undesirable Facilities through the Dominance-based Rough Set Approach". J. Multi-Crit. Decis. Anal.، 21(1-2): 3–23.

Brimberg ، J. Juel، H. (1998). "On Locating a Semi-desirable Facility on the Continuous Plane". Int. Trans. Opl. Res.، 5(1): 59-66.

Berman، O. Odoni، A. R. (1982). "Locating mobile servers on a network with Markovian properties"، Networks.، 12(1): 73-86.

Cooper، L. (1974). "A random locational equilibrium problem". Journal of Regional Science.، 14(1): 47-54.

Colebrook، M. Gutierrez، J. Sicilia، J. (2005). "A new bound and an O(mn) algorithm for the undesirable1-median problem (maxian) on networks". Computers & Operations Research، 32(2): 309–325.

Daskin، M. (1997). "Network and Discrete Location: Models، Algorithms and Applications". New York، John Wiley & Sons Inc.

Erkut، E. Neuman، S. (1989). "Analytical models for locating undesirable facilities". European Journal of Operational Research، 40(3): 275-291.

Fernandez، J. Fernandez، P. Pelegr، B. (2000). "A continuous location model for siting a nonoxious undesirable facility within a geographical region". European Journal of Operational Research، 121(2): 259-274.

Farber، S. (1998). "Undesirable facilities and property values: a summary of empirical studies". Ecological Economics، 24(1): 1-14.

Gulpınar، N. Pachamanova، D. Canakoglu، E. (2013)."Robust strategies for facility location under uncertainty". European Journal of Operational Research، 225(2): 21–35.

Hu، Ch. Liu، X. Lu، J. (2017). "A bi-objective two-stage robust location model for waste-to energy facilities under uncertainty". Decision Support Systems، 99(1):37-50.

Jamalian، A. Salahi، M. (2014). "Robust solutions to multi-facility Weber location problem under interval and ellipsoidal uncertainty". Applied Mathematics and Computation، 242(1): 179–186.

Lawrence، V. S. (2006). "Facility Location Under Uncertainty: A Review". IIE Transactions، 38(1): 537-554.

Louveaux، F. Thisse، J. F. (1985). "Production and location on a network under demand uncertainty". Operations Research Letters، 4(4): 145-149.

Mirchandani، P. B. Odoni، A. R. (1979). "Locations of medians on stochastic networks"، Transportation Science، 13(2): 85-97.

Mirchandani، P. B. Oudjit، A. (1980). "Localizing 2-medians on probabilistic and deterministic tree networks"، Networks، 10(4): 329-350.

Markovi، N. Ryzho، O. Schonfeld، P. (2017)." Evasive flow capture: A multi-period stochastic facility location problem with independent demand.: European Journal of OperationalResearch.، 257(2): 687-703.

Melachrinoudis، E. (1984). "Determining an optimum location for an undesirable facility in a workroom environment". Appl. Math. Model، 9(5): 365-369.

Melachrinoudis، E. Cullinane، T.P. (1985). "Locating an Undesirable Facility within a Geographical Region Using the Maximin Criterion". Journal of Regional Science، 25(1): 115-127.

Melachrinoudis ، E. Cullinane، T.P. (1986). "Locating an Obnoxious Facility within a Polygonal Region". Annals of Operations Research، 6(5): 137-145.

Melachrinoudis، E. Xanthopulos، Z. (2003). "Semi-obnoxious Single Facility Location in Euclidean Space". Computers & Operations Research، 30(4): 2191-2209.

Marcos، C. Joaquín، S. (2007)." Undesirable facility location problems on multicriteria networks". Computers & Operations Research، 34(5): 1491-1514.

Pavankumar، M. Ordonezb، F. Dessouky، M. M. (2012). "Facility location under demand uncertainty: Response to a large-scale bio-terror attack". Socio-Economic Planning Sciences، 46(1):78-87.

Pugaa، M. Tancreza، J. ( 2016). "A heuristic algorithm for solving large location-inventory problems with demand uncertainty". European Journal of Operational Research، 259(2): 413-423.

Plastria، F. (1996). "Optimal Location of Undesirable Facilities: A Selective Overview". Belgian Journal of Operations Research Statistics and Computer Science.، 36(1): 109-127.

Plastria، F. Carrizosa، E. (1999). "Undesirable facility location with minimal covering objectives". European Journal of Operational Research، 119(1): 158-180.

Ravi، R. Sinha، A. (2006). "Hedging uncertainty: Approximation algorithms for stochastic optimization problems". Mathematical Programming،108(1): 97–114

Rosa،V.D. Hartmann، E.Gebhard،M. Wollenweber، J. (2014). "Robust capacitated facility location model for acquisitions under Uncertainty". Computers & Industrial Engineering، 72(1): 206–216.

Rakas، J. Teodorovi، D. Kim، T. (2004). "Multi-objective modeling for determining location of undesirable facilities". Transportation Research Part D، 9(2): 125-138.

Rodriguez، J.J. S. Garcia، C. G. Perez، J. M. Casermeiro، E. M. (2006). "Ageneral model for the undesirable single facility location Problem". Operations Research Letters، 34(4): 427 – 436.

Song، B. D. Morrison، J. R. Ko، Y. D. (2013). "Efficient location and allocation strategies for undesirable facilities considering their fundamental properties". Comput. Ind. Eng.، 65(3): 475–484.

Sheppard، E. S. (1974). "A conceptual framework for dynamic location-allocation analysis". Environment and Planning A.، 6(1): 547-564.

Tuzkaya، G. Onut، S. Tuzkaya، R. Gulsun، B. (2008). "An analytic network process approach for locating undesirable facilities: An example from Istanbul، Turkey". Journal of Environmental Management، 88(4): 970–983.

Tang، S.H. Boyer، O. Pedram، A. Yusuff، R. Zulkifli، N. ( 2013). "A Review on Multiple Criteria Undesirable Facility Location Problems". J. Basic. Appl. Sci. Res.، 8(3): 708-713.

Weaver، J. R. Church، R. L. (1983). "Computational procedures for location problems on stochastic networks". Transportation Science.، 17(2): 168-180.

Wichapa، N. Khokhajaikiat، P. (2017). "Solving multi-objective facility location problem using the fuzzy analytical hierarchy process and goal programming: a case study on infectious waste disposal centers". Operations Research Perspectives، 4(1): 39–48.

Yamaguchi، K. (2011). "Location of an undesirable facility on a network: A bargaining approach". Mathematical Social Sciences، 62(2): 104–108.