هیچ محصولی در سبد خرید نیست.
روش مسئله احتمالاتی تخصیص – مکان یابی ماکزیمم پوشش با روشی ترکیبی
دانلود ترجمه مقاله متد ترکیبی برای مسئله احتمالاتی تخصیص – مکان یابی حداکثر پوشش
21,000 تومانشناسه فایل: 7311
- حجم فایل ورد: 871.5KB حجم پی‌دی‌اف: 441.4KB
- فرمت: فایل Word قابل ویرایش و پرینت (DOCx)
- تعداد صفحات فارسی: 30 انگلیسی: 19
- دانشگاه:
- São Paulo State University, Av. Dr. Ariberto Pereira da Cunha, 333, Guaratinguetá 12516-410, Brazil
- CIRRELT - Interuniversity Research Centre on Enterprise Networks, Logistics and Transportation, Canada
- Faculté des sciences de l׳administration, Université Laval, 2325 de la Terrasse, Quebec City, Canada G1K 0A6
- Instituto Nacional de Pesquisas Espaciais, Av. dos Astronautas, 1758, São José dos Campos 12221-010, Brazil
- ژورنال: Computers and Operations Research (2)
نشانگر دیجیتالی شیء:
DOI: 10.1016/j.cor.2014.12.001
« متن زیر تنها بخش هایی از محتوای این پروژه است »
چکیده
این مقاله الگوریتمی ترکیبی را شرح می‌دهد که روشی فوق‌ابتکاری و دقیق، جهت حل مسئله احتمالاتی تخصیص – مکان یابی حداکثر پوشش را با یکدیگر ترکیب می‌کند. یک رابطه برنامه نویسی خطی برای مسئله متغیرهایی را ارائه می‌دهد که می‌توان آنها را به تصمیمات مکان یابی و تخصیص تقسیم نمود. این مدل برای بدست آوردن نمونه‌های کوچک و متوسط بهینه حل می‌شود. جهت حل نمونه‌های بزرگتر، تکنیک ابتکاری جستجوی همسایگی وسیع تطبیقی انعطاف پذیر برای حصول راه حل‌های مکان یابی ابداع شد، در حالی که مسائل فرعی تخصیص برای راه حل بهینه حل می‌شوند. یک شیوه ارتقا دهی بر پایه روش برنامه نویسی عدد صحیح نیز بکار گرفته می‌شود. آزمایش‌های محاسباتی گسترده روی نمونه‌های معیار حاصل از منابع علمی کارآمدی روش پیشنهادی را تأیید می‌کنند. این روش دقیق بهترین راه حل‌های جدید را برای 19 نمونه یافت که بهینگی را برای 18 نمونه از آنها تأیید می‌کند. روش ترکیبی عملکرد سازگاری داشت و بهترین راه حل معلوم را برای 94.5 درصد نمونه‌ها و 17 راه حل جدید را برای مجموعه داده بزرگی در یک سوم زمان حل کننده پیشرفته پیدا کرد.
مقدمه مقاله
مکان یابی تاسیسات نقش مهمی در تصمیمات لجستیک ایفا می‌کند. هر روز، شرکت‌های بسیاری برای تخمین بهترین روش یا روش اقتصادی‌تر جهت تامین نیاز مشتریانشان به کالا یا خدمات به روش‌های کمّی متوسل می‌شوند. در برخی موارد، قابلیت دسترسی به سرویس ممکن است با زمان یا مسافت تا تأسیسات موجود ارتباط داشته باشد. در این مورد، تصمیم گیرنده باید بهترین مکان را برای گشایش تاسیسات بیابد تا عمده نیاز مشتریان را تامین کند.
مسئله مکان‌یابی حداکثر پوشش (MCLP) یک مسئله مکان یابی تجهیزات است که هدف اش انتخاب تعداد محدودی مکان کاندید جهت راه اندازی تاسیسات است تا نیاز کل مشتریانی که در مسافت پوششی از تأسیسات موجود ساکن‌اند به حداکثر رسد (6). بطور مثال، نمونه‌هایی از این مسئله در بخش عمومی جهت تعیین مکان سرویس‌های اضطراری مانند ایستگاه‌های آتش نشانی، آمبولانس‌ها و غیره دیده می‌شود. شرکت‌های خصوصی این مسئله را جهت مکان یابی ATM ها یا دستگاه‌های فروشنده، شعب بانک‌ها، فروشگاه‌های زنجیره‌ای غذای آماده، آنتن‌های تلفن سلولی و غیره حل می‌کنند. در مراجع 13، 15 و 27 فهرست کامل‌تری از کاربردهای این مسئله آمده است. انواع این مسئله از جمله وزن‌های منفی و عدم قطعیت زمان سفر در مراجع 4 و 5 آمده‌اند. از روش‌های حل مسئله MCLP می‌توان به تکنیک‌های ابتکاری حریصانه (6.12)، آزادسازی برنامه نویسی خطی (6)، آزادسازی لاگرانژی (14)، الگوریتم ژنتیک (1)، تکنیک ابتکاری لاگرانژی/جایگزین (19) و ستون سازی (23) اشاره کرد.
در برخی موارد کاربرد این مسئله، شمار مشتریان و نیازشان که به یک تأسیسات تخصیص یافته است ممکن است بر رفتار سیستم مؤثر باشد. بسته نوع سرویس، ممکن است مشتریان برای بهره گیری از سرویس مجبور به منتظر ماندن شوند. در چنین سیستم‌های مزدحمی، کیفیت سرویس نه تنها بر حسب نزدیکی به یک تاسیسات گشایش یافته، بلکه بر اساس سطح سرویس مانند تعداد مشتریان در صف و زمان انتظار نیز اندازه گیری می‌شود. براساس این فرض که درخواست‌های سرویس با گذشت زمان ثابت باشند، می‌توان این جنبه را به سادگی با افزودن قیدهای ظرفیت به مدل MCLP مدل کرد. با این حال، این روش قطعی می‌تواند سبب بیکاری یا اضافه کاری سرویس دهندگان شود.
جهت پرداختن به سناریوهای واقعی‌تر، مارینوف و سرا (21) مدلی را پیشنهاد کردند که دستیابی مشتریان به یک تاسیسات را بسته به نیازهای مشتریان فرآیندی تصادفی فرض می‌کرد. مولفین حد کمینه‌ای برای کیفیت سرویس بر اساس تعداد مشتریان در صف یا حداکثر زمان انتظار تعریف می‌کنند. بدین صورت صورت تعمیم یافت مسئله MCLP بنام مدل تخصیص – مکان یابی حداکثر پوشش (QM-CLAM) یا مسئله احتمالاتی تخصیص – مکان یابی حداکثر پوشش (PMCLAP) حاصل می‌شود. به سبب پیچیدگی این مسئله و وسعت نمونه‌های واقعی، اغلب تحقیقات به ابداع روش‌های ابتکاری اختصاص یافته‌اند (10.11).
مدل‌های مکان یابی – تخصیص دستکم شامل دو نوع متغیر تصمیم‌اند: محل راه اندازی تاسیسات (تصمیم مکان یابی) و مشتریانی که از تأسیسات گشایش یافته سرویس می‌گیرند (تصمیم تخصیص). روش‌های حل سنتی مانند الگوریتم‌های شاخه و قید، همزمان به تصمیمات مکان یابی و تخصیص می‌پردازند: مشتریان به مکان کاندیدی تخصیص می‌یابد که همچنان برای راه اندازی تاسیسات در نظر گرفته می‌شود. با این حال، روش سلسله مراتبی همانند یک الگوریتم ابتکاری طبیعی بنظر می‌رسد: ابتدا مکان یابی تاسیسات و درگام دوم تخصیص مشتریان به آنها.
جهت بررسی این مشخصه مسئله، روش ترکیبی تکرارشونده جدیدی ابداع می‌شود. الگوریتم فراابتکاری جستجوی همسایگی وسیع تطبیقی (ALNS) به بخش مکان یابی این مسئله می‌پردازد و راه حل نظیر تخصیص با حل یک مسئله فرعی عدد صحیح برای بدست آوردن راه حل بهینه بدست می‌آید. ALNS توسط روپکی و پیسینگر (25) برای دسته مسائل مسیریابی وسیله نقلیه پیشنهاد شده است و از آن پس به بعد برای هزاران مسئله دیگر از جمله مسئله زمانبندی وسیله (3.22)، مسئله روند شبکه پرشده ثابت (17)، مسئله مسیریابی قوس تصادفی (18)، چند دسته از مسائل مسیریابی وسیله نقلیه (26)، مسئله مسیریابی موجودی کالاها (7.8) و جدول زمانی قطار (2) بکار گرفته شد. ما تنها از یک مورد کاربرد ALNS برای مسئله دارای مولفه مکان یابی تاسیسات (16) اگاهیم که با مسئله مورد بحث بسیار متفاوت است.
ترتیب بخش‌های باقیمانده این مقاله بدین صورت است: بخش 2 شرحی رسمی و رابطه ریاضی برای PBCLAP ارائه می‌دهد. شیوه فراابتکاری ترکیبی ALNS در بخش 3 شرح داده می‌شود. نتایج محاسبات گسترده در نمونه‌های معیار در بخش 4 ارائه می‌شوند. در بخش 5 هم نتیجه گیری‌ها ارائه می‌شوند.
مطالب پیشنهادی:
- مکان یابی تسهیلات چند دوره ای با ظرفیت محدود تحت تامین با تعویق تقاضا
- چارچوب تصمیمگیری چند معیاره (MCDM) فازی جهت مکان یابی نیروگاه اتمی در ترکیه
- مدیریت ریزشبکه با پیکربندی مجدد احتمالاتی و تعهد واحد
- بکارگیری الگوریتم ژنتیک GA برای ماکزیمم کردن کارایی فنی در تحلیل پوششی داده ها DEA
- فقه زنان و مسئله برابری
- اعتیاد، مسئله اجتماعی مهم در میان دانشجویان
ABSTRACT A hybrid method for the Probabilistic Maximal Covering Location–Allocation Problem
This paper presents a hybrid algorithm that combines a metaheuristic and an exact method to solve the Probabilistic Maximal Covering Location–Allocation Problem. A linear programming formulation for the problem presents variables that can be partitioned into location and allocation decisions. This model is solved to optimality for small- and medium-size instances. To tackle larger instances, a flexible adaptive large neighborhood search heuristic was developed to obtain location solutions, whereas the allocation subproblems are solved to optimality. An improvement procedure based on an integer programming method is also applied. Extensive computational experiments on benchmark instances from the literature confirm the efficiency of the proposed method. The exact approach found new best solutions for 19 instances, proving the optimality for 18 of them. The hybrid method performed consistently, finding the best known solutions for 94.5% of the instances and 17 new best solutions (15 of them optimal) for a larger dataset in one-third of the time of a state-of-the-art solver.
Introduction
Facility location plays an important role in logistic decisions. Each day, many enterprises resort to quantitative methods to estimate the best or the more economical way to meet clients’ demand for goods or services. In some cases, the availability of the service can be associated with a time or distance to an existing facility. In this case, the decision maker has to find the best location to open the facilities in order to satisfy most of the demand.
The Maximal Covering Location Problem (MCLP) is a facility location problem which aims to select some location candidates to install facilities, in order to maximize the total demand of clients that are located within a covering distance from an existing facility [6]. Examples of this problem appear, for instance, in the public sector to determine the location of emergency services such as fire stations, ambulances, etc. Private companies solve this problem to locate ATMs or vending machines, branches of a bank, stores of fast food chains, cellular telephony antennae, etc. A more extensive list of applications can be found in [13], [15] and [27]. Variations of this problem, including negative weights and travel time uncertainty, can be found in [4] and [5]. Solution approaches to the MCLP include greedy heuristics [6, 12], linear programming relaxation [6], lagrangean relaxation [14], genetic algorithm [1], lagrangean/surrogate heuristic [19] and column generation [23].
In some applications, the number of clients and their associated demand allocated to a facility may have an impact on the behavior of the system. Depending on the nature of the service, clients may have to wait to be served. In such congested systems, the service quality is measured not only by the proximity to an open facility, but also by a service level, such as the number of clients in a queue or the waiting times. Under the assumption that the service requests are constant over time, this aspect can be modeled by simply adding capacity constraints to the MCLP model. However, this deterministic approach may yield idle or overloaded servers.
To deal with more realistic scenarios, Marianov and Serra [21] proposed a model considering the arrival of clients to a facility as a stochastic process depending on the clients’ demands. The authors define a minimum limit on the quality of service based on the number of clients in the queue or on the maximum waiting time. This yields an extension of the MCLP called Queueing Maximal Covering Location-Allocation Model (QM-CLAM) or Probabilistic Maximal Covering Location-Allocation Problem (PMCLAP). Due to the complexity of the problem and to the size of real world instances, most research is devoted to the development of heuristic methods [10, 11].
Location-allocation models contain, at least, two types of decision variables: where to install a facility (location decision) and which clients to serve by the opened facility (allocation decision). Traditional solution approaches, such as branch-and-bound algorithms, deal with location and allocation decisions simultaneously: clients are allocated to a candidate location that is still being considered for the installation of a facility. However, a hierarchical approach appears as a natural heuristic algorithm: locate facilities first and, in a second step, allocate clients to them.
To explore this characteristic of the problem, a new iterative hybrid method is developed. The location part of the problem is dealt with by an Adaptive Large Neighborhood Search (ALNS) metaheuristic, and the corresponding allocation solution is obtained by solving an integer subproblem to optimality. The ALNS was proposed by Ropke and Pisinger [25] for a class of the vehicle routing problem, and has since then been employed for a myriad of other problems, including the vehicle scheduling problem [3, 22], the fixed charged network flow problem [17], the stochastic arc routing problem [18], several classes of vehicle routing problems [26], the inventory-routing problem [7, 8], and train timetabling [2]. We are aware of only one application of the ALNS to a problem with a facility location component [16], which is significantly different from the problem at hand.
The remainder of this paper is organized as follows. Section 2 provides a formal description and a mathematical formulation for the PMCLAP. The hybrid ALNS metaheuristic is described in Section 3. The results of extensive computational results on benchmark instances are presented in Section 4. Conclusions follow in Section 5.
این فقط قسمتی از متن مقاله است . جهت دریافت کل متن مقاله ، آن را خریداری نمایید.
دسته: مهندسی صنایع, مهندسی کامپیوتر
6کلمات کلیدی:
- مقاله درمورد روش مسئله احتمالاتی تخصیص – مکان یابی ماکزیمم پوشش با روشی ترکیبی
- پروژه دانشجویی روش مسئله احتمالاتی تخصیص – مکان یابی ماکزیمم پوشش با روشی ترکیبی
- متد مسئله احتمالاتی تخصیص – مکان یابی ماکزیمم پوشش
- پایان نامه در مورد روش مسئله احتمالاتی تخصیص – مکان یابی ماکزیمم پوشش با روشی ترکیبی
- تحقیق درباره روش مسئله احتمالاتی تخصیص – مکان یابی ماکزیمم پوشش با روشی ترکیبی
- مقاله دانشجویی روش مسئله احتمالاتی تخصیص – مکان یابی ماکزیمم پوشش با روشی ترکیبی
- روش مسئله احتمالاتی تخصیص – مکان یابی ماکزیمم پوشش با روشی ترکیبی در قالب پايان‌نامه
- پروپوزال در مورد روش مسئله احتمالاتی تخصیص – مکان یابی ماکزیمم پوشش با روشی ترکیبی
- گزارش سمینار در مورد روش مسئله احتمالاتی تخصیص – مکان یابی ماکزیمم پوشش با روشی ترکیبی
- گزارش کارورزی درباره روش مسئله احتمالاتی تخصیص – مکان یابی ماکزیمم پوشش با روشی ترکیبی