نوع مقاله : مقاله پژوهشی- فارسی
نویسندگان
1 دانشیار، دانشکده فنی مهندسی، دانشگاه الزهرا، تهران، ایران
2 دانشیار، دانشکده فنی مهندسی، دانشگاه شاهد، تهران، ایران
3 کارشناسی ارشد مهندسی صنایع، دانشگاه الزهرا، تهران، ایران
چکیده
کلیدواژهها
عنوان مقاله [English]
نویسندگان [English]
Purpose: Hub location problems are getting more and more attention today due to their widespread application in designing product transportation systems and communication networks. In these systems, products (including data transmission, passenger transportation, freight forwarding and logistics, postal services, etc.) are shipped from multiple sources to multiple destinations. The performance of these systems can be improved by using hub points. In fact, instead of just deciding on a single period, a planning horizon with multiple time periods is considered. The necessity of doing this research is that decisions are made in each period according to the costs and flows of the same period. In the real world, facilities are usually depreciated after a certain period of time and must be closed or rebuilt if possible.
Design/methodology/approach: In this research, hubs reconstruction is allowed, meaning it can be reconstructed to reduce costs rather than startups, to operate for a specified lifetime and to cover network demands. It is also selected to operate hubs from different contractors. In this study, there are also several levels of capacity to set up that can be selected with respect to the demand of the period, which is both sufficient and cheaper to meet the demands. Genetic algorithm has been used to solve and evaluate the model performance.
In general, this study has attempted to provide comprehensive modeling for the multi-period hub location problem with multiple capacities. The investigated problem considered the hubs lifetime as well as the possibility of reconstruction at the end of lifetime. It has also been attempted to design the model to suit real-world conditions.
Findings: Investigations in this study showed that the proposed model is more efficient than the previous models in terms of coordination and compliance with real-world conditions. Further,the validity of the proposed model was also evaluated by performing a variety of sensitivity analyzes. Solving the various numerical examples by the genetic algorithm and comparing them with the exact method demonstrates the acceptable performance of the meta heuristic method.
Research limitations/implications: For future research and improvement of proposed model the following recommendations are suggested:
Consider different capacity levels for nodes so that the capacity of each node can be changed at different times depending on the problems conditions.
Assume that the hubs can be closed before the expiration date depending on the problems conditions.
Consider case studies in various industries and model development with conditions much closer to real situations, for example in the field of urban transport, perishable products, emergency services, and so on.
Using uncertain programming such as probabilistic and fuzzy programming to predict and plan the model and its parameters in successive periods.
Providing solution methods with better performance and solving larger problems in rational times. For example, heuristic methods can reduce the complexity of the problem and thus solve larger samples in shorter times, so they will be useful.
Practical implications: The main advantage of a multi-period problem over a single period problem is making the best decision in the time frame. In the single-period model, once the decision is made for all time periods, it is obvious that this decision will not be optimal because the parameters and conditions governing the problem are not the same over successive periods, so the result will not be global optimal. Another advantage is that the single-period model optimizes the cost of each period separately and it does not consider the relationship between the network structure of the nodes in different periods. Therefore, in this study, a multi-period model was proposed to obtain the global optimal solutions.
Originality/value: The main difference between this study and previous work is the following:
Providing a hub location model in which it is possible to select a contractor for each hub set up.
In this research, the hubs have a known lifespan and this lifespan is determined after the contractor selection.
Providing a new model that enables the choice between reconstructing and closing at the end of each hub's life by considering network costs.
کلیدواژهها [English]
مقدمه
یک راهکار اساسی برای کاهش هزینه در ترابری کالا و مسافر، طراحی صحیح شبکههای حمل و نقل و ترابری است. مسئلۀ مکانیابی هاب[i] یکی از مسائل مهم در ادبیات موضوع مکانیابی به شمار میآید. در این مسئله عموماً بهدنبال پیداکردن مکان هاب در شبکه و به دست آوردن حجم نقل و انتقالات بین نقاط تقاضا بهگونهای هستیم که مجموع هزینهها به کمترین مقدار خود برسد.
مدل ارائهشده در این مقاله یک مدل چنددورهای[ii] و دربرگیرندۀ کاربردهای زمان واقعی مسئلۀ مکانیابی هاب است. در واقعیت، فقط برای یک دورۀ واحد تصمیمگیری نمیشود و برنامهریزی برای یک افق زمانی با چندین دوره است؛ بنابراین ممکن است باتوجهبه عوامل مختلف مانند تغییر در جریانها و هزینههای هر دوره، پیکربندی اولیۀ شبکه تغییر یابد. در هر دوره از افق برنامهریزی، پیکربندی دورۀ قبلی بهروزرسانی میشود و این روند تا پایان افق زمانی ادامه مییابد.
ضرورت اجرای این پژوهش این است که تصمیمگیری در هر دوره باتوجهبه هزینهها و جریانات همان دوره انجام میشود. در دنیای واقعی معمولاً تسهیلات بعد از زمان مشخصی مستهلک میشوند و باید بعد از اتمام طول عمرشان[iii] بسته یا در صورت امکان بازسازی شوند. در این پژوهش اجازۀ بازسازی[iv] به هاب داده شده است؛ یعنی میتوان برای کاهش هزینهها بهجای راهاندازی، هاب را بازسازی کرد تا در یک طول عمر مشخص کار کند و تقاضاهای شبکه را پوشش دهد. همچنین برای راهاندازی هابها میتوان از میان پیمانکاران[v] مختلف انتخاب کرد. در این پژوهش چندین سطح ظرفیت[vi] برای راهاندازی وجود دارد تا باتوجهبه تقاضای دورۀ مدنظر، ظرفیتی انتخاب شود که هم برای پاسخدهی تقاضاها کافی باشد وهم هزینه کمتری داشته باشد.
بهطور کلی در رویکرد برنامهریزی چنددورهای، شبکه دربرگیرندۀ کل افق برنامهریزی خواهد بود و با بینشی کامل و باتوجهبه شرایط تصمیمات اخذ میشود. این تغییرات در ساختار شبکهها معمولاً تابعی از الگوهای تغییر حجم توزیع جریانها، ظهور تکنولوژیها، موضوعات اقتصادی و غیره هستند؛ بنابراین باتوجهبه تغییرات در محیطهای داخلی و خارجی، شرکتها و صنایع در تصمیمات استراتژیک خود بازنگری میکنند.
برای نخستین کار درزمینۀ مکانیابی هاب چنددورهای میتوان به مدل کمبپل[vii] (1990) اشاره کرده که مدل تقریب پیوستۀ یک کشتی حامل عمومی که یک منطقۀ ثابت را با تراکم افزایشی تقاضا تحت پوشش قرار میداد. پس از آن، گلاره[viii] (2008) مسئلۀ مکانیابی هاب چنددورهای برای حمل و نقل عمومی را در نظر گرفت که در آن وضعیتهای مکانهای هاب میتواند در مدت افق برنامهریزی تغییر کند. تیموریان و همکاران (2011) و تقی پوریان و همکاران (2012) مسائل مکانیابی هاب پویا را درزمینۀ برنامهریزی اورژانسی برای صنعت هوایی بررسی کردند. برخی یا همۀ ظرفیت یک فرودگاه میتواند بهدلیل شرایط هوایی غیرقابل دسترس شود. پروازها ممکن است به هابهای مجازی مسیردهی شوند که در مواقع اضطراری فعال میشوند. مدلهای برنامهریزی عدد صحیح مختلط[ix] و برنامهریزی عدد صحیح فازی[x] برای تعیین مکان هابهای مجازی و مسیر بین جفت مبدا- مقصد در مدت افق برنامهریزی توسعه داده شده است. کنترراس و همکاران[xi] (2011) مسئلۀ مکانیابی هاب داینامیک بدون محدودیت ظرفیت را در نظر گرفتند. آنها مورد تخصیص چندگانه[xii] را با استفاده از رویکرد شاخه و کران[xiii] بررسی کردند که از آزادسازی لاگرانژ[xiv] برای حل مسائل بالای 100 گره استفاده میکند. در هورهامر[xv] (2014) مسئلۀ مکانیابی هاب چنددورهای با تخصیص تکی[xvi] و ظرفیت چندگانه بررسی شده است. در این مقاله چندین فرمول برنامهریزی عدد صحیح مختلط پیشنهاد شد و درنهایت این مدلها با هم مقایسه شدند. گلاره و همکاران (2015) مدل ریاضی مسئلۀ مکانیابی هاب چنددورهای را با تخصیص چندگانه و با ظرفیت نامحدود ولی ظرفیت بودجه ارائه دادند. مدل پیشنهادی ویژگیهای زیادی از آنچه در عمل در حمل و نقل دریایی و زمینی وجود دارد را شامل میشد. در این مقاله همچنین الگوریتم فرا ابتکاری پیشنهاد شد که حلهای با کیفیت بالا در مدت زمان منطقی و معمول ارائه میداد.
مسائلی و همکاران (2018) تصمیمات مربوط به برنامه ریزی حمل و نقل را در مکان یابی هاب وارد کردند. آنها سه مدل برنامهریزی عدد صحیح مختلط را برای حالتهای مختلف این مسئله، بسته به اینکه هزینه نگهداری وجود داشته باشد یا اینکه وسائل نقلیههای مختلفی داشته باشیم، پیشنهاد دادند. آنها تأثیر برنامهریزی حمل و نقل و هزینۀ نگهداری را در شبکۀ هاب، تصمیمات مسیریابی و هزینۀ کل شبکۀ هاب بررسی کردهاند. کوریا و همکاران (2018) مدل مکانیابی هاب چنددورهای تصادفی را با تخصیص چندگانه و محدودیت ظرفیت بررسی کردند. در این مقاله برای تقاضا عدم قطعیت در نظر گرفته شده است. عدم قطعیت را میتوانند بهوسیلۀ مجموعه ی محدودی از سناریوها که هرکدام با احتمالات برآوردشدهای رخ می دهند به دست آورند و شکل گستردۀ معادله قطعی را استخراج کنند.
درادامه، مدلِ ارائهشده در این مقاله بررسی میشود. در مدل پیشنهادی این مسئله، برای هابها باتوجهبه پیمانکار انتخابی طول عمر در نظر گرفته شده است و درانتهای طول عمر دربارۀ بازسازی یا بستهشدن هاب تصمیمگیری میشود؛ بنابراین تفاوت مدل هورهامر و مدل پیشنهادی، اضافهشدن محدودیتهای مربوط به طول عمر، بازسازی و انتخاب بین پیمانکاران و سطوح مختلف بازسازی است. در مدل هورهامر امکان تغییر سطح ظرفیت برای هابها وجود دارد. درصورتیکه در این پژوهش از این مورد صرفنظر شده است. پس از تشریح مدل، پارامترها و متغیرهای تصمیم مدل با استفاده از مجموعه اطلاعات پست استرالیا ( AP) بررسی میشود و مسائل با استفاده از نرمافزار GAMS بهروش دقیق و بار دیگر بهوسیلۀ الگوریتم فراابتکاری ژنتیک حل شدهاند. درنهایت نتیجهگیری و پیشنهادات برای پژوهشهای آتی ارائه شده است.
مدلسازی مسئله
مدل بهکاررفته در این مسئله، مکانیابی هاب پویا با تخصیص تکی و همراه با محدودیت ظرفیت است و شامل تغییرات پویای جریان و هزینهها در دورههای گوناگون زمانی است. هابها طول عمر مشخص دارند و طول عمرشان بستگی به انتخاب پیمانکار دارد، هابها در پایان این طول عمر میتوانند بازسازی یا بسته شوند و همچنین سطوح ظرفیت هر هاب و بازسازی، چندگانه در نظر گرفته شدهاند. فرض بر این است که G=(N,E) یک گراف کامل است.
پارامترها و متغیرهای تصمیم مسئله در ادامه آورده شده است:
پارامترها:
|
N |
مجموعه گرهها i= {1, 2, …, n} |
|
T |
مجموعه دورههای زمانی در افق زمانی در نظر گرفته شده t= {1, 2, ..., e} |
|
طول عمر هر هاب بعد از استفاده از پیمانکار p برای راهاندازی |
|
|
p |
مجموعۀ پیمانکار p = {1, 2, ..., pn} |
|
T2 |
مجموعه دورههای زمانی تداوم عملکرد در طول عمر هاب = {1, 2, ..., vp-1} |
|
S |
مجموعه سطوح بازسازی s= {1, 2, ..., d} |
|
Ls |
طول عمر هاب پس از بازسازی در بازسازی سطح s |
|
T3 |
مجموعه دورههای زمانی تداوم بازسازی پس از بازسازی = {1, 2, ..., Ls -1} |
|
Ck |
مجموعه سطوح ظرفیت برای هاب k |
|
Gkc |
ظرفیت هاب k در ظرفیت سطح c |
|
هزینۀ بازکردن هاب k در ظرفیت سطح c توسط پیمانکار p در دورۀ t |
|
|
هزینۀ بازسازی هاب k در ظرفیت سطح c و بازسازی سطح s در دورۀ t |
|
|
هزینۀ عملیات برای هاب k و ظرفیت سطح c در دورۀ t |
|
|
هزینۀ بستن هاب k در ظرفیت سطح c در دوره t |
|
|
dij |
فاصلۀ بین گره i و گره j |
|
جریان از گره iبه گره j در دورۀ t |
|
|
کل جریان صادرشده از گره i در دورۀ زمانی t، |
|
|
کل جریان واردشده به گره i در دوره t، |
|
|
χ |
ضریب تخفیف اقتصادی ناشی از جمع آوری محصول (غیرهاب به هاب) |
|
α |
ضریب تخفیف اقتصادی ناشی از انتقال محصول (هاب به هاب) |
|
Δ |
ضریب تخفیف اقتصادی ناشی ازتوزیع محصول (هاب به غیر هاب) |
قبل از بیان مدل مسئله ما متغیرهای تصمیم را معرفی میکنیم:
|
برابر یک است اگر گره i به هاب k در دوره t تخصیص یابد، در غیر این صورت صفر است |
||
|
برابر یک است اگر هاب k در ظرفیت سطح cدر دورۀ t بهوسیلۀ پیمانکارpباز شود، در غیر این صورت صفر است. |
||
|
مقدار جریان از گره i که از هاب k و l در دوره t استفاده میکند. |
||
|
برابر یک است اگر هاب k با ظرفیت سطح c در دوره t در سطح s بازسازی شود، در غیر این صورت برابر با صفر است. |
||
|
برابر یک است اگر هاب k در ظرفیت سطح c در دوره t تداوم عملکرد داشته باشد، در غیر این صورت صفر است. |
||
|
برابر یک است اگر هاب kبا ظرفیت سطح c در دوره t در سطح s تداوم بازسازی داشته باشد، در غیر این صورت برابر با صفر است. |
||
|
(1) |
||
|
|
s.t.
|
|
|
(2) |
|
|
|
(3) |
|
|
|
(4) |
|
|
|
(5) |
|
|
|
(6) |
|
|
|
(7) |
|
|
|
(8) |
|
|
|
(9) |
|
|
|
(10) |
|
|
|
(11) |
|
|
|
(12) |
|
|
|
(13) |
|
|
|
(14) |
|
|
|
(15) |
|
|
|
(16) |
|
|
|
(17) |
|
|
|
(18) |
|
|
|
(19) |
|
|
|
(20) |
|
|
|
(21) |
|
|
تابع هدف، هزینۀ کل را در افق زمانی کمینه میکند. هزینهها شامل هزینههای جمعآوری، انتقال، توزیع، بازکردن، عملیات، بستن و بازسازی است. نخستین عبارت هزینههای جمعآوری و توزیع را نشان میدهد. در دومین عبارت هزینۀ انتقالِ بینِ هابی نشان شده است. فرض میشود که فاکتور تخفیف α برای منعکسکردن اقتصادیبودن مقیاس است. سومین عبارت هزینههای راهاندازی را زمانی که یک هاب در ابتدای دورۀ t نصب میشود، نشان میدهد. در قسمت چهارم و پنجم، ششم و هفتم هزینّۀ عمیات، عبارت هشتم هزینۀ بازسازی و دو عبارت آخر هزینۀ بستن را نشان میدهد. زمانی یک هاب میتواند بسته شود که در دورههای پیشین بازشده باشد و در دورۀ حاضر تصمیم به بازسازی آن گرفته نشود.
محدودیتهای مسئله مکانیابی هاب مشابه با مسئلۀ ایستا است. همۀ محدودیتها باید در هر دوره t برقرار شود. محدودیت (2) این موضوع را که هر هاب باید در هر دوره فقط به یک هاب تخصیص یابد را نشان میدهد. محدودیت (3) فقط به گرههای غیر هاب اجازه تخصیص به گرههای هاب را میدهد و اینکه هر گره هاب به خودش تخصیص پیدا میکند. محدودیت (4) تصمیم تخصیص با مکانیابی هاب را با هم ترکیب میکند. یک گره به خودش تخصیص مییابد اگر آن هاب باشد، یک گره هاب است اگر برخی از ظرفیتهای هاب در آن نصب شود یا بازسازی داشته باشد و یا اینکه در دورهی تداوم عملکرد یا بازسازی خود باشد. محدودیت (5) اطمینان میدهد که ظرفیت نصب شده در گره هاب k کافی برای به انجام رساندن جریانات ورودی از گرههای تخصیص داده شده را دارد. محدودیت (6) بیان کننده این امر است که در یک دوره و برای هر هاب فقط یکی از موارد باز کردن، تداوم عملکرد، بازسازی و یا تداوم بازسازی را خواهیم داشت. این موضوع که بعد از طول عمر یک هاب تصمیم بر بازسازی گرفته میشود یا خیر در محدودیت (7) عنوان میشود. محدودیت (8) نشان دهندهی این موضوع است که بعد از پایان طول عمر هاب به فاصله یک دورۀ زمانی ما اجازه راهاندازی مجدد آن هاب را نخواهیم داشت. در محدودیت (9) و (10) نشان داده میشود که بلافاصله بعد از بازسازی و تداوم بازسازی یک هاب نمیتوانیم آن را راهاندازی مجدد کنیم. محدودیت (11) و (12) عملکرد هاب را در طی طول عمر و یا بازسازی آن بیان میکند، s و p به ترتیب مجموعه سطوح بازسازی و مجموعه پیمانکاران برای هابها هستند. به عبارت دیگر برای راه اندازی یک هاب، چندین پیمانکار وجود دارد که باتوجهبه نیاز مسئله و مدل، از پیمانکار بهینه برای راهاندازی هاب استفاده میشود. برای بازسازی هاب نیز چندین سطح وجود دارد که سطوح مختلف برای بازسازی، طول عمر متفاوت برای هابها را در بر خواهد داشت. در محدودیت (13) ظرفیتهای تجمیع شده عنوان میشود. این برای اطمینان مسئله مورد استفاده قرار میگیرد و اغلب در مسائل مکانیابی تسهیلات یافت میشود. این محدودیت اطمینان میدهد که همۀ ظرفیتهای نصبشده برای همۀ جریانات ورودی کفایت میکند. محدودیت (14) حفاظت جریان از آغاز جریان در گره i تا هاب k را نشان میدهد. محدودیت (15) اطمینان میدهد که جریان از مقصد i تا هاب های k و l زمانی نامنفی است که گره i به هاب k تخصیص یافته باشد. محدودیتهای (16)، (17)، (18)، (19)، (20) و (21) وضعیت متغیرها را مشخص میکند. در بخشهای بعدی بهروش حل فراابتکاری ژنتیک پرداخته میشود و برای اعتبارسنجی و نشاندادن کارایی مدل تحلیل حساسیت انجام میشود. همچنین برای نمایش کارایی روش فرابتکاری پیشنهادشده از مثال عددی موجود در ادبیات استفاده میشود.
مثال عددی
یکی از مجموعه اطلاعاتی که بهطور معمول استفاده میشود، مجموعه اطلاعات پست استرالیا ( AP) است. مجموعه اطلاعات AP بر پایۀ یک تحویل پستی در سیدنی و شامل 200 گره نشاندهندۀ نواحی پستی است. این دادهها شامل فاصلۀ اقلیدسی بین 200 شهر استرالیا و مقادیر جریانهای پستی بین جفت شهرهاست. در ادبیات این مجموعه دادهها برای تعداد نواحی 10، 20، 25، 40 و 50 تایی بهطور وسیعی استفاده میشود.
دادههای موجود در مجموعه اطلاعات AP قابل استفاده در مدل تک دورهای میباشند. بنابراین نمونه ثابت از مجموعه داده AP گرفته میشود و بهصورت ذیل به نمونه پویا (چند دورهای) تبدیل میشود.
در این تحقیق برای هر جفت گره مبدأ و مقصد مقدار جریان در هر دوره با احتمال 90%، 30% افزایش مییابد در غیر این صورت 25% کاهش مییابد. هزینه بازکردن مقدار 90%-120% هزینۀ راهاندازی مربوط به نمونه ثابت را به خود میگیرد. هزینههای عملیاتی در دورههای مختلف بین 10%-15%، هزینههای بستن هاب بین 40%-60% و هزینههای بازسازی بین 30-60% هزینههای بازکردن هاب متغیر خواهند بود. در ذیل نحوۀ محاسبه هزینهها نشان داده شده است:
|
(22) |
|
|
(23) |
|
|
(24) |
|
|
(25) |
|
|
(26) |
|
دربارۀ سطوح ظرفیت نیز باید گفت بیشترین سطح ظرفیت از داده عددی AP گرفته میشود و سطوح دیگر بهصورت زیر محاسبه میشود:
|
(27) |
Gkc =𝜆 Gk(c+1) 𝜆 = 0.7 |
همچنین مقادیر هزینه (بازکردن، بستن و ...) برای سطوح دیگر ظرفیت بهصورت زیر محاسبه خواهد شد:
|
(28) |
هزینۀ بازسازی برای سطوح مختلف بهصورت زیر به دست میآید:
|
(29) |
شایان ذکر است که این روش تولید داده برای دورههای چندگانه برگرفته از روشی است که کنتراس و همکاران (2011) در پژوهش خود برای تولید دادههای دورههای متوالی انجام دادند. درادامه نتایج محاسبات عددی ارائه خواهد شد. در این بخش مدل مکانیابی هاب تکدورهای با تخصیص تکی و سطوح ظرفیت چندگانه با مدل پیشنهادی در این پژوهش مقایسه و دو مدل ازلحاظ تعداد هابهای بازشده و سطوح ظرفیتشان بررسی میشود. نتایج دو مدل برای 10 گره و 8 دوره زمانی در جدول 1 آمده است.
جدول (1): مقایسۀ مدل چنددورهای و تکدورهای
|
هابهای بازشده و سطح ظرفیتشان |
دورۀ زمانی |
|||||||||
|
4 |
|
1 |
k |
1 |
||||||
|
2 |
|
1 |
c |
|||||||
|
9 |
4 |
|
k |
استاتیک |
||||||
|
1 |
1 |
|
c |
|||||||
|
10 |
8 |
4 |
|
2 |
1 |
k |
2 |
|||
|
1 |
1 |
2 |
|
1 |
1 |
c |
||||
|
9 |
4 |
|
k |
استاتیک |
||||||
|
2 |
1 |
|
c |
|||||||
|
10 |
8 |
7 |
5 |
4 |
|
2 |
1 |
k |
3 |
|
|
1 |
1 |
1 |
1 |
2 |
|
1 |
1 |
c |
||
ادامه جدول (1): مقایسۀ مدل چنددورهای و تکدورهای
|
هابهای بازشده و سطح ظرفیتشان |
دورۀ زمانی |
|||||||||
|
9 |
3 |
k |
استاتیک |
|||||||
|
1 |
2 |
c |
||||||||
|
10 |
8 |
7 |
5 |
4 |
|
2 |
1 |
k |
4 |
|
|
1 |
1 |
1 |
1 |
2 |
|
1 |
1 |
c |
||
|
7 |
|
3 |
k |
استاتیک |
||||||
|
2 |
|
2 |
c |
|||||||
|
10 |
8 |
7 |
5 |
|
3 |
2 |
1 |
k |
5 |
|
|
1 |
1 |
1 |
1 |
|
1 |
1 |
1 |
c |
||
|
9 |
|
3 |
k |
استاتیک |
||||||
|
2 |
|
1 |
c |
|||||||
در مقایسه مدلها میتوان گفت که در حالت چند دورهای هاب های بیشتری نسبت به تک دورهای بازشده است و دلیل این موضوع این است که مدل پویا نسبت به مدل تک دورهای بهترین تصمیم در بازهی زمانی مدنظر را اتخاذ میکند. در صورتی که در مدل تک دورهای یک بار تصمیمگیری برای کل دورهها اجرا میگردد، واضح است که این تصمیم بهینه نخواهد بود، زیرا پارامترها و شرایط حاکم بر مسئله طی دورههای متوالی یکسان نیست، بنابراین جواب حاصل جواب بهینه کلی نخواهد بود. مزیت دیگر آن این موضوع است که مدل تک دورهای هزینه مربوط به دورهها را بهطور جداگانه بهینه مینماید و ارتباط بین ساختار شبکه گرهها در دورههای مختلف را در نظر نمیگیرد؛ بنابراین مدل چنددورهای مطابقت بیشتری با دنیای واقعی دارد. در مقایسه با مدل هورهامر (2014) میتوان گفت که چون در این پژوهش امکان بازسازی و همچنین انتخاب پبمانکار برای هابها وجود دارد می توان با هزینۀ کمتری به تقاضا ها پاسخ داد به این دلیل که با توجه به مدل میتوان طول عمر هاب را به گو نه ای در طول دورههای زمانی انتخاب کرد که هم پاسخگوی تقاضاها باشد و هم هزینۀ کمتری داشته باشد. مورد دیگر این است که بهجای بازکردن هاب که هزینۀ بهمراتب بیشتری برای ما دارد می توان هابها را بازسازی کرد. در این پژوهش بستن هاب به این دلیل که میتوان از تسهیلات هابهای بستهشده برای بازکردن هاب دیگر استفاده نمود، برای ما منفعت خواهد داشت.
الگوریتم ژنتیک
الگوریتم ژنتیک الگوریتم تکاملی است که در سال 1975 توسط جان هلند در دهه 1980 بسیار شایان توجه قرار گرفت. الگوریتم ژنتیک روش فراابتکاری است که با استفاده از روشهای الهام گرفتهشده از طبیعت به جوابهای مطلوب میرسد. این الگوریتم با راهحلهایی تصادفی بهنام «جمعیت» متشکل از کروموزومها شروع شده و این عمل براساس عملگر تابع تناسب انجام می شود؛ به اینصورت که احتمال انتخاب برای فرزندان دارای تابع تناسب بالاتر، بیشتر است.
نحوه نمایش جواب
نخستین گام در الگوریتم پیشنهادی، کدکردن متغیرهای مسأله در غالب بردارها یا کروموزومهای حامل جواب و به عبارت بهتر «نحوه نمایش جوابها» است. به طور نمونه کروموزوم بهینه مسأله چهار دوره ای با ده گره در شکل زیر نشان داده شده است.
|
ظرفیت سطح 2 |
ظرفیت سطح 2 |
ظرفیت سطح 3 |
ظرفیت سطح 2 |
ظرفیت سطح 1 |
|
پیمانکار 2 |
پیمانکار 2 |
پیمانکار 3 |
پیمانکار 3 |
پیمانکار 1 |
ردیفهای یک تا چهار نحوۀ تخصیص گرهها را بهترتیب در چهار دورۀ زمانی نشان میدهد، ردیف پنج تا هشت مشخص می نماید که هاب بازسازی میشود و یا خیر و در صورت بازسازی، در کدام دوره بازسازی میشود. دو ردیف آخر مشخص می کند که از چه ظرفیت و یا پیمانکاری برای راهاندازی یا بازسازی هابها استفاده شده است. ترتیب در هر ردیف بهترتیب افزایش شمارۀ هاب و در صورت مساویبودن شماره هاب به ترتیب افزایش دوره مرتب شده اند.
|
10 |
10 |
10 |
10 |
10 |
5 |
2 |
5 |
2 |
2 |
|
10 |
10 |
10 |
10 |
10 |
4 |
4 |
4 |
2 |
2 |
|
5 |
5 |
5 |
5 |
5 |
5 |
2 |
5 |
2 |
2 |
|
5 |
5 |
5 |
5 |
5 |
5 |
2 |
5 |
2 |
2 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
شکل 1- کروموزوم بهینه مسئله چهار دوره ای با ده گره
عملگر تقاطع
این عملگر بر روی یک جفت از کروموزومها عمل میکند و میتواند بهصورت تک نقطهای، چندنقطهای و یکنواخت باشد. در این پژوهش از ترکیب یک نقطه ای استفاده شده است. عملگر تقاطعی تک نقطهای، دو کروموزوم را بهطور تصادفی از یک نقطه شکسته و بخشهای شکسته دو کروموزوم را جابجا میکند.
|
10 |
10 |
10 |
10 |
10 |
10 |
3 |
3 |
1 |
1 |
|
10 |
10 |
10 |
10 |
10 |
10 |
3 |
3 |
1 |
1 |
|
10 |
10 |
10 |
10 |
10 |
10 |
3 |
3 |
3 |
3 |
|
10 |
10 |
10 |
10 |
10 |
10 |
3 |
3 |
3 |
3 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
والد1:
|
ظرفیت سطح 3 |
ظرفیت سطح 2 |
ظرفیت سطح 1 |
|
پیمانکار 1 |
پیمانکار 1 |
پیمانکار 2 |
|
10 |
10 |
10 |
10 |
10 |
10 |
1 |
1 |
2 |
1 |
|
10 |
10 |
10 |
10 |
10 |
10 |
1 |
1 |
2 |
1 |
|
10 |
10 |
10 |
10 |
10 |
10 |
2 |
2 |
2 |
2 |
|
10 |
10 |
10 |
10 |
10 |
10 |
1 |
1 |
2 |
1 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
والد2:
|
ظرفیت سطح 1 |
ظرفیت سطح 3 |
ظرفیت سطح 2 |
ظرفیت سطح 1 |
|
پیمانکار 1 |
پیمانکار 1 |
پیمانکار 3 |
پیمانکار 2 |
|
10 |
10 |
10 |
10 |
10 |
10 |
3 |
1 |
2 |
1 |
|
10 |
10 |
10 |
10 |
10 |
10 |
3 |
1 |
2 |
1 |
|
10 |
10 |
10 |
10 |
10 |
10 |
3 |
2 |
2 |
2 |
|
10 |
10 |
10 |
10 |
10 |
10 |
3 |
1 |
2 |
1 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
فرزند1:
|
ظرفیت سطح 3 |
ظرفیت سطح 2 |
ظرفیت سطح 1 |
|
پیمانکار 1 |
پیمانکار 1 |
پیمانکار 2 |
|
10 |
10 |
10 |
10 |
10 |
10 |
1 |
3 |
1 |
1 |
|
10 |
10 |
10 |
10 |
10 |
10 |
1 |
3 |
1 |
1 |
|
10 |
10 |
10 |
10 |
10 |
10 |
2 |
3 |
3 |
3 |
|
10 |
10 |
10 |
10 |
10 |
10 |
1 |
3 |
3 |
3 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
فرزند2:
|
ظرفیت سطح 1 |
ظرفیت سطح 3 |
ظرفیت سطح 2 |
ظرفیت سطح 1 |
|
پیمانکار 1 |
پیمانکار 1 |
پیمانکار 1 |
پیمانکار 2 |
شکل 2- نمونه عملکرد تقاطع
عملگر جهشی
این عملگر به این صورت ایت که که به ازای هر بیت از کروموزوم، یک عدد تصادفی تولید میکند. اگر مقدار این عدد تصادفی از مقدار Pm (احتمال انجام جهش) کمتر باشد، در آن بیت عمل جهش انجام میشود و در غیر این صورت، در آن بیت عمل جهش انجام نمیگیرد. عمل جهش در هر بیت با تولید تصادفی عدد ٠ یا ١ و جایگزینی آن بجای بیت مورد جهش انجام میگیرد. اگر عملیات جهش صورت نگیرد، فرزندان بدون تغییر دیگری وارد نسل جدید میشوند. اما اگر عملیات جهش صورت بگیرد قسمتهایی از کروموزوم تغییر میکند.
|
10 |
10 |
10 |
10 |
10 |
10 |
3 |
3 |
1 |
1 |
|
10 |
10 |
10 |
10 |
10 |
10 |
3 |
3 |
1 |
1 |
|
10 |
10 |
10 |
10 |
10 |
10 |
3 |
3 |
3 |
3 |
|
10 |
10 |
10 |
10 |
10 |
10 |
3 |
3 |
3 |
3 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
والد:
|
ظرفیت سطح 3 |
ظرفیت سطح 2 |
ظرفیت سطح 1 |
|
پیمانکار 1 |
پیمانکار 1 |
پیمانکار 2 |
|
10 |
10 |
6 |
6 |
6 |
10 |
3 |
4 |
1 |
1 |
|
10 |
10 |
10 |
10 |
10 |
10 |
3 |
4 |
1 |
1 |
|
10 |
10 |
10 |
10 |
10 |
10 |
3 |
4 |
3 |
3 |
|
10 |
10 |
10 |
10 |
10 |
10 |
3 |
4 |
3 |
3 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
فرزند:
|
ظرفیت سطح 3 |
ظرفیت سطح 1 |
ظرفیت سطح 1 |
|
پیمانکار 1 |
پیمانکار 1 |
پیمانکار 2 |
شکل 3- نمونه عملکرد جهش
اجرای الگوریتم ژنتیک
ابتدا با توجه به صورت مسئله، متغیرهایی که باید تعیین شوند، مشخص میشوند. سپس این متغیرها به نحو مناسبی کدگذاری شده و به شکل کروموزوم نمایش داده میشوند. بر اساس تابع هدف، یک تابع برازندگی برای کروموزومها تعریف میگردد و یک جمعیت اولیه دلخواه نیز بهطور تصادفی انتخاب میشود. به دنبال آن، میزان تابع برازندگی برای هر کروموزوم جمعیت اولیه حساب میشود. کروموزوم های جدید به مجموعه جمعیت قبلی اضافه شده و در ادامه از مجموعه کنونی بر اساس مقادیر تابع برازش، بهترین ها به اندازه تعداد جمعیت اولیه انتخاب می گردد و یک نسل جدید تولید می شود.
جدول 2 ، نشان دهندهی نتایج به دست آمده از حل این مسئله در اندازههای 10-20-25-40 و 50 توسط مدل ارائه شده است. هرکدام از مسائل یکبار به روش دقیق و توسط نرمافزار بهینهسازی GAMS و بار دیگر بهوسیله الگوریتم فرا ابتکاری ژنتیک حل شدهاند و علاوه بر تابع هدف، زمانهای حل کامپیوتری آنها نیز در جدول گزارش شده است.
تمامی نتایج این پژوهش با استفاده از رایانهای با سیستم عامل ویندوز 64 بیتی با قدرت پردازش 60/2 گیگا هرتز، و حافظه 4 گیگا بایت با استفاده از نرمافزار GAMS 24.1.2 و MATLAB R2014a به دست آمده است. حداکثر زمان مجاز برای اجرای برنامه ها 30 ساعت در نظر گرفته شده است.
جدول (2): مقایسۀ نتایج روش دقیق و فراابتکاری
|
تعداد گره |
تعداد دوره زمانی |
تابع هدف روش دقیق |
زمان روش دقیق |
تابع هدف روش فراابتکاری |
زمان روش فرا ابتکاری |
درصد فاصله از تابع هدف |
|
10 |
4 |
648/167019 |
381/4 |
648/167019 |
450/4 |
0 |
|
5 |
732/179731 |
350/29 |
732/179731 |
231/20 |
0 |
|
|
6 |
508/208283 |
206/204 |
013/214532 |
340/60 |
03/0 |
|
|
20 |
4 |
852/345409 |
344/62 |
640/373042 |
50 |
08/0 |
|
5 |
980/366817 |
056/739 |
778/403499 |
121/120 |
1/0 |
|
|
6 |
520/431105 |
904/1005 |
182/482838 |
008/145 |
12/0 |
|
|
25 |
4 |
- |
- |
329/523691 |
120/200 |
|
|
5 |
- |
- |
230/540097 |
59/320 |
|
|
|
6 |
- |
- |
436/582611 |
203/589 |
|
|
|
40 |
4 |
- |
- |
120/655980 |
350/669 |
|
|
5 |
- |
- |
201/678922 |
3/700 |
|
|
|
6 |
- |
|
256/705987 |
267/769 |
|
|
|
50 |
4 |
- |
- |
009/761236 |
340/890 |
|
|
5 |
- |
- |
345/786901 |
568/990 |
|
|
|
6 |
- |
- |
785/809711 |
645/1232 |
|
همانطورکه از جدول 2 مشخص است مدل بهدلیل داشتن متغیرها و محدودیتهای زیاد فقط قابلحل بهوسیله نرمافزار گمز تا اندازه 20 میباشد. از طرف دیگر روش فرا ابتکاری ارائه شده نشان میدهد که قابلیت حل مسائل و رسیدن به پاسخهای بهینه را در اندازه های بزرگتر دارد. با در نظر گرفتن مسائل با بیش از 20 گره روش حل دقیق کارایی خود را از دست داده است و روش فرا ابتکاری قادر است پاسخهای خوبی را در زمان حل منطقی تولید کند.
تحلیل حساسیت
ازآنجاییکه تغییر در ارزش پارامترها سبب تغییر نتایج به دست آمده از حل مسئله میشود، بنابراین تحلیل حساسیت میتواند به فرایند تصمیمگیری بهتر در مسائل دنیای واقعی کمک کند. بهعبارتدیگر در این بخش نشان داده خواهد شد که چطور نتایج بهدستآمده از حل مسئله بهوسیلۀ تغییر در یک پارامتر خاص تغییر مییابد و این در حالی است که سایر پارامترها ثابت در نظر گرفته شدهاند. تحلیل حساسیتهای انجامشده در این پژوهش بیشتر برای نشاندادن نحوۀ عملکرد مدلسازی و همچنین کارایی آن در هنگام تغییر ارزش پارامترهایی از قبیل تعداد سطوح بازسازی، تعداد پیمانکاران و هزینه بازسازی است.
تحلیل حساسیت روی سطوح بازسازی
برای انجام این امر از یک مثال شبیهسازیشده با در نظر گرفتن 10 گره، 8 دورۀ زمانی، 2 سطح ظرفیت و 2 پیمانکار استفاده شده است. نتایج حاصل از این تحلیل در جدول 3 نشان داده شده است. طبق این جدول با افزایش سطوح بازسازی، مقدار تابع هدف ابتدا روند کاهشی دارد و سپس ثابت میشود. همچنین زمان حل افزایش مییابد. کمتربودن هزینۀ بازسازی نسبت به هزینۀ بازکردن هاب دلیل کاهش در تابع هدف است. با افزایش سطوح بازسازی تعداد دورههای زمانی تحت پوشش توسط هاب بازسازیشده بیشتر و نیاز به راهاندازی هاب جدید کمتر میشود. دلیل متوقفشدن روند کاهشی تابع هزینه نیز این است که سطوح بالاتر بازسازی هزینه بیشتری داشته و انتخاب آنها برای مسئله بهینه نخواهد بود. این در حالی است که سایر پارامترهای استفاده شده در مدلسازی در طول انجام این آزمایش ثابت در نظر گرفته شدهاند.
جدول (3): تحلیل حساسیت روی سطوح بازسازی
|
تعداد سطوح بازسازی |
تابع هدف |
زمان حل |
|
1 |
620/214549 |
797/69 |
|
2 |
292/211193 |
459/580 |
|
3 |
360/198950 |
540/700 |
|
4 |
908/192190 |
300/1000 |
|
5 |
908/192190 |
78/1010 |
|
6 |
908/192190 |
50/1102 |
تحلیل حساسیت روی تعداد پیمانکاران
در این قسمت به بررسی نحوهی تغییر در پاسخها با تغییر در تعداد پیمانکاران میپردازیم. همانطور که در جدول 4 مشخص است با افزایش تعداد پیمانکاران، تابع هدف کاهش و زمان حل افزایش مییابد. دلیل کاهش تابع هدف این است که با افزایش پیمانکاران، برای بازکردن هابها گزینههای بیشتری وجود دارد که میتوان در بازکردن هاب علاوه بر پوششدهی تقاضاها، کمینهکردن هزینهها را در نیز نظر گرفت. دلیل افزایش زمان حل نیز پیچیدهترشدن مدل است.
جدول (4): تحلیل حساسیت روی تعداد پیمانکاران
|
تعداد پیمانکاران |
تابع هدف |
زمان |
|
1 |
292/231193 |
410/349 |
|
2 |
292/211193 |
978/507 |
|
3 |
32/201236 |
369/1056 |
|
4 |
69/189683 |
320/1179 |
|
5 |
69/189683 |
786/1280 |
تحلیل حساسیت روی هزینۀ بازسازی
در جدول 5 مقدار تابع هدف و تعداد هابهای راهاندازیشده برای مقادیر مختلف هزینه بازسازی نشان داده شده است. از جدول 5 مشخص است که با افزایش هزینۀ بازسازی تعداد هابهای راهاندازی شده و تابع هدف افزایش مییابد و کاهش هزینه بازسازی نیز باعث کاهش تابع هدف و تعداد هاب های راهاندازیشده میشود.
جدول (5): تحلیل حساسیت روی هزینۀ بازسازی
|
هزینه بازسازی |
تعداد هاب های راهاندازی شده |
تعداد هاب های بازسازیشده |
تابع هدف |
|
2/0 |
5 |
3 |
676/195384 |
|
5/0 |
7 |
2 |
292/201193 |
|
1 |
8 |
1 |
129/208819 |
|
3/1 |
8 |
1 |
435/213206 |
|
5/1 |
8 |
0 |
836/215623 |
|
6/1 |
8 |
0 |
836/215623 |
نتیجه گیری و پیشنهادات آتی
مدل مدنظر این مقاله بر اساس بسط مدل DCSAHLP میباشد که در آن اجازهی انتخاب پیمانکار و بازسازی هاب ها داده شده است. بررسی ادبیات موضوع در این حوزه نشان میدهد در هیچیک از مطالعات انجامشده طول عمر برای هابها در نظر گرفته نشده و امکان بازسازی در هابها لحاظ نشده است. این در حالی است که هر تسهیل بعد از زمان مشخصی مستهلک شده و باید بعد از اتمام طول عمرشان بسته یا در صورت امکان بازسازی شوند. در این تحقیق اجازه بازسازی به هاب داده شده است یعنی میتوان برای کاهش هزینهها بهجای راهاندازی، هاب را بازسازی کرد تا در یک طول عمر مشخص کار کند و تقاضاهای شبکه را پوشش دهد. پس از ارائهی مدلسازی مسئله، بهمنظور حل و ارزیابی عملکرد مدل از روش فرا ابتکاری ژنتیک استفاده شده است. بررسیها نشان داده است، مدل ارائهشده در این پژوهش نسبت به مدلهای پیشین ارائهشده برای این مسئله از نقطهنظر هماهنگی و منطبقبودن با شرایط دنیای واقعی کارایی زیادی دارد. همچنین حل مثالهای عددی متنوع بهوسیلۀ روش فرا ابتکاری ژنتیک و مقایسهی آنها با روش دقیق حاکی از عملکرد قابلقبول روش فرا ابتکاری میباشد.
پیشنهادهایی برای پژوهشهای آتی
برای پژوهشهای آتی و بهبود مدل ارائهشده موارد ذیل پیشنهاد میشود:
[i]- Hub
[ii]- Dynamic
[iii]- Life Cycle
[iv]- Reconstruct
[v]- Conractor
[vi]- Capacity
[vii]- Campbell
[viii]- Gelareh
[ix]- Mixed Integer
[x]- Fuzzy Integer Programing
[xi]- Contreras
[xii]- Multiple Allocation
[xiii]- Branch & Bound
[xiv]- Lagrangean Relaxation
[xv]- Hörhammer
[xvi]- Single Allocation
)