نوع مقاله : مقاله پژوهشی- فارسی
نویسندگان
1 کارشناسی ارشد، دانشکده مهندسی صنایع و سیستم‌ها، دانشگاه صنعتی اصفهان، ایران
2 استادیار، دانشکده مهندسی صنایع و سیستم‌ها، دانشگاه صنعتی اصفهان، ایران
چکیده
کلیدواژه‌ها
موضوعات
عنوان مقاله [English]
نویسندگان [English]
In this paper, modeling and solving an open selective vehicle routing problem with pricing are introduced. We will discuss optimal pricing when using a homogeneous fleet of vehicles. Furthermore, in some real world applications, companies prefer to distribute their products using rented vehicles so returning to the depot is not required. Therefore we face an open routing problem. Despite the applicability of such problem, we did not find any published research that examines it.also an Improved Imperialist Competitive Algorithm (IICA) is proposed to solve proposed model. For validating this method, some small scale problems are solved and results are compared to the results of an exact method and Simulated Annealing (SA) algorithm. The comparison of results shows that the proposed method is suitable for solving the model. For investigating its efficiency in dealing with real world problems, some large scale problems are solved and the results are compared to the results of Simulated Annealing (SA) algorithm. Results show that IICA is more efficient than SA.
کلیدواژه‌ها [English]
- مقدمه
مسأله مسیریابی وسایل نقلیه و قیمت‌گذاری، دو موضوع محوری در توزیع و فروش هستند. بسیاری از مسائل بهینه‌سازی که در این حوزه به وجود می‌آیند، جزء مسائلNP-hard هستند و حل‌کردن آنها در عمل بسیار دشوار است. به همین دلیل، تا به حال این دو حوزۀ تحقیقاتی توأمان کمتر در نظر گرفته شده‌اند و هزینۀ این کار نرسیدن به جواب مطلوب بوده است. درنظرگرفتن هم‌زمان این دو مسئله، منجر به افزایشِ دشواری حل مسئله می‌شود؛ اما از سویی دیگر، امکان به‌دست‌آوردن جواب بهتر در راستای اهداف واحد توزیع و فروش را پدید می‌آورد.
در دنیای واقعی، حالاتی وجود دارد که از ناوگانی برای خدمات‌رسانی به مشتریان استفاده می‌شود. درنظرگرفتن معیارهای هزینه‌ای در بسیاری از موارد سبب می‌شود که خدمت‌دهی به برخی از مشتریان مقرون‌به‌صرفه نباشد؛ بنابراین مشتریانی که سود بیشتری برای مجموعه دارند انتخاب می‌شوند. درنظرگرفتن چنین فرضی در مدل‌سازی مسأله مسیریابی وسیلۀ نقلیه (VRP[1])، منجر به معرفی مسأله مسیریابی انتخابی وسیلۀ نقلیه[2] می‌شود. از یک سو میزان قیمت، تقاضای مشتریان و هزینه‌های مسیریابی بحث مقرون‌به‌صرفه‌بودن خدمت‌دهی به مشتری را مورد توجه قرار می‌دهد و از سوی دیگر قیمت کالا بر میزان تقاضای مشتریان تأثیر می‌گذارد؛ بنابراین قیمت‌گذاری مناسب محصولات هم‌زمان با مسیریابی، می‌تواند بیشترین سود را نصیب شرکت توزیع کند.
از سوی دیگر در برخی از کاربردهای حمل‌ونقل از وسایل نقلیه اجاره‌ای استفاده می‌شود که این مورد منجر به ایجاد مسأله مسیریابی وسیلۀ نقلیۀ باز[3] شده است. مسئله‌ای که در این مقاله برای ترکیب مسائل مسیریابی و قیمت‌گذاری استفاده شده است، مسأله مسیریابی وسیلۀ نقلیۀ انتخابی باز با درنظرگرفتن قیمت‌گذاری است.
نوآوری‌های این مقاله را می‌توان بهصورت زیر عنوان کرد: معرفی مسأله مسیریابی وسیلۀ نقلیۀ انتخابی و قیمت‌گذاری، درنظرگرفتن مسیرهای باز به‌منظور نزدیک‌سازی مدل پیشنهادی به دنیای واقعی، ارائۀ یک مدل ریاضی جدید برای مسأله مطرح‌شده و درنهایت ارائۀ یک الگوریتم فرااِبتکاری مبتنی بر الگوریتم رقابت استعماری به‌منظور حل مدل ارائه‌شده. ساختار ارائۀ مطالب بدین صورت خواهد بود که پس از مقدمۀ ارائه‌شده در این بخش، در بخش دوم، ادبیات موضوع بررسی می‌شود؛ در بخش سوم مدل ریاضی مسئله ارائه خواهد شد، در بخش چهارم ساختار الگوریتم حل پیشنهادی تشریح خواهد شد، بخش پنجم به بیان نتایج محاسباتی اختصاص یافته است و سرانجام در بخش ششم نتیجه‌گیری وپیشنهادهایی برای مطالعات آتی ارائه شده است.
2- ادبیات موضوع
لین و یو (2015) یک الگوریتم شبیه‌سازی تبرید با استراتژی شروع دوباره )[4](SA-RS برای نوع خاصی از مسأله مسیریابی انتخابی وسیلۀ نقلیه پیشنهاد داده‌اند. آنها دو نسخه از SA-RS را ارائه داده‌اند. نسخۀ اول، SA-RSBF، از تابع بولتزمن[5] برای تعیین احتمال پذیرش بدترین جواب استفاده می‌کند؛ در حالی که نسخۀ دوم، SA-RSCF، بدترین جواب را برمبنای احتمال پذیرش تعیین‌شده توسط تابع کائوچی[6] می‌پذیرد. آنها به این نتیجه رسیدند که هر دو نسخه قابلیت حل مسائل معیار را دارند و در برخی موارد جوابی بهتر ارائه می‌دهند. آنها همچنین نشان دادند که SA با استراتژی شروع دوباره بهتر از SA بدون استراتژی شروع دوباره عمل می‌کند.
الاهویرانلو و همکاران (2014) اشاره می‌کنند که مسأله مسیریابی انتخابی وسیلۀ نقلیه نسبت به مسائل مرسوم VRP در مسائل عدم‌قطعیت با منابع محدود بهتر عمل می‌کنند. آنها برای اثبات حرف خود سه فرمول‌بندی از مسائل مسیریابی انتخابی وسیلۀ نقلیه برای سه استراتژی بهینه‌سازی با سطح تقاضای غیرقطعی ارائه می‌دهند که عبارت‌اند از مسائل مسیریابی انتخابی فازی[7] ،رباست[8] و قابل‌اطمینان[9]. همچنین آنها سه الگوریتم ژنتیک موازی)[10](PGAs و یک الگوریتم ژنتیک کلاسیک ارائه دادند و با جواب‌های قطعی مقایسه کردند. نتایج نشان‌داده‌شده صدق گفتار آنها را تأیید می‌کند.
ساهین‌یازانا و همکاران (2015) یک سیستم متحرک جمع‌آوری خون [11] با هدف اولیۀ بیشترین سطح جمع‌آوری خون طراحی کردند. این سیستم همچنین هزینۀ عملیاتی را برای جمع‌آوری خون به‌عنوان هدف بعدی در نظر می‌گیرد. این سیستم تورهایی را برای جمع‌آوری خون در نظر می‌گیرد که در پایان هر روز، مقدار جمع‌آوری‌شده جهت جلوگیری از فاسدشدن به مرکزی طراحی‌شده برای حفاظت که به‌عنوان دپو در نظر گرفته شده است، بازگردانده می‌شوند. با درنظرگرفتن محدودیت زمانی و محدودیت منابع آنها این سیستم را به‌عنوان مثالی کاربردی از مسأله مسیریابی انتخابی در نظر گرفتند. آنها یک مدل ریاضی و یک مسأله عددصحیح 2 مرحله‌ای ابتکاری برای تعیین تورها در نظر گرفتند.
هماهنگی دو مسأله مسیریابی و قیمت‌گذاری سابقۀ طولانی ندارد و به‌تازگی مورد توجه قرار گرفته است. ژیونز و همکاران (2007) در سال 2007 اولین کسانی بودند که اثر قیمت‌گذاری را در مسأله مسیریابی با هدف بیشینه‌کردن سود بررسی کردند؛ به این صورت که تقاضای مشتریان را تابعی از قیمت فرض کردند و قیمت را به‌عنوان متغیر تصمیم وارد مسئله کردند. در این مسئله هزینۀ مسیریابی با تابعی بهصورت تقریبی در نظر گرفته شده و قیمت‌گذاری برمبنای آن صورت گرفت.
یی و همکاران (2007) یک مدل دومرحله‌ای برای قیمت‌گذاری در یک مسأله مسیریابی همراه با کالاهای مرجوعی[12] ارائه کردند. هدف نهایی آنها تعیین یک قیمت پایه (قیمت کف) برای پیشنهاد به مشتری است. در پایان نیز یک مطالعۀ موردی به‌همراه حل آن به‌روش شبیه‌سازی تبرید[13] (SA) ارائه شده است. در این مقاله تمامی مشتریان بایستی بازدید می‌شدند و بنابراین قیمت‌گذاری با این فرض در نظر گرفته شد.
لیو و چن (2011) قیمت‌گذاری را همراه با مسأله مسیریابی موجودی بررسی کردند. یکپارچگی دو مسأله مسیریابی وسایل حمل‌ونقل و مسائل موجودی در یک سیستم زنجیرۀ تأمین، مسأله مسیریابی موجودی[14] (IRP) نامیده می‌شود. در مسأله مسیریابی موجودی دو موضوع مورد بررسی قرار می‌گیرد: موضوع اول پیداکردن مسیر بهینه برای وسایل حمل‌ونقل به‌منظور تحویل کالاها از تأمین‌کنندگان به خرده‌فروش‌ها و موضوع دوم تعیین سیاست بهینه برای موجودی خرده‌فروش. در این مدل، قیمت به‌عنوان یک متغیر وارد شده است و درنتیجه تابع هدف از نوع بیشینه‌کردن سود خواهد بود. آنها اظهار داشتند تصمیمات مربوط به قیمت بر میزان موجودی بهینه و بر مسیر بهینه برای وسایل حمل‌ونقل تأثیر دارد. به‌عنوان مثال قیمت بالاتر باعث تقاضای کمتر و درنتیجه مقدار سفارش کمتر و درنهایت موجودی کمتر خواهد شد. از این رو درنظرگرفتن دو مسأله قیمت‌گذاری و مسأله مسیریابی موجودی بهصورت مجزا باعث دورشدن از جواب بهینه و سود کمتر می‌شود. در پایان نیز یک روش ابتکاری که در آن از الگوریتم جستجوی ممنوع [15](TS) بهره گرفته می‌شود، برای حل این مسئله ارائه شده است. در مدل مطرح‌شده نیز خدمات‌دهی به تمامی مشتریان در نظر گرفته شده است.
نوآوری‌های این مقاله را می‌توان بهصورت زیر عنوان کرد: معرفی مسأله مسیریابی وسیلۀ نقلیۀ انتخابی و قیمت‌گذاری، درنظرگرفتن مسیرهای باز به‌منظور نزدیک‌سازی مدل پیشنهادی به دنیای واقعی، ارائۀ یک مدل ریاضی جدید برای مسأله مطرح‌شده و درنهایت ارائۀ یک الگوریتم فرااِبتکاری مبتنی بر الگوریتم رقابت استعماری به‌منظور حل مدل ارائه‌شده است.
3- تعریف مسئله
قیمت‌گذاری کالا معمولاً با توجه به قیمت محصولات رقیب، کشش بازار و هزینه‌های تولید در نظر گرفته می‌شود. در میان هزینه‌های تولید، هزینۀ توزیع کالا بخشی از هزینه‌ها است که توجه به این هزینه در انتخاب قیمت مناسب نقش مؤثری دارد. از سوی دیگر شرکت‌های توزیع می‌توانند با توجه به قیمت بهینه و هزینه‌های مسیریابی تنها خدمات‌دهی به مشتریانی را در نظر بگیرند که خدمات‌دهی به آنها در سطح قیمت بهینه مقرون‌به‌صرفه باشد و از این طریق سود مناسبی را نصیب خود کنند. همچنین در بسیاری از شرکت‌های توزیع از ناوگان حملی استفاده می‌شود که بهصورت اجاره‌ای در خدمت شرکت توزیع هستند. این ویژگی سبب می‌شود که نیاز به بازگشت به دپو برای ناوگان حمل وجود نداشته باشد. همان‌گونه که اشاره شد درنظرگرفتن رابطۀ خطی بین قیمت و تقاضا یک فرض عمومی و پرکاربرد است. در این تحقیق رابطۀ بین قیمت و تقاضا بهصورت خطی در نظر گرفته شده است و از رابطۀ زیر پیروی می‌کند:
|
(1) |
در این رابطه و مقادیر ثابت مربوط به مشتری iام هستند و p و به‌ترتیب قیمت و تقاضای مشتری iام است. با تغییر قیمت تقاضای مشتریان افزایش و یا کاهش مییابد.
فرضیات مسئله بهصورت زیر در نظر گرفته شده‌اند:
3-1- مدل ریاضی مسأله مطرح‌شده
اندیس‌های استفاده‌شده در مدل عبارت‌اند از:
|
مربوط به مشتریان است. |
i,j=1,2,3,…,N |
|
|
مربوط به وسیله نقلیه است |
k=1,2,3,..,K |
|
N |
تعداد مشتریان است که مشتری آخر بهصورت مجازی در نظر گرفته شده است.
|
پارامترهای استفاده‌شده در مدل عبارت‌اند از:
|
زمان طی سفر بین مشتریiام و مشتریjام |
|
|
حداکثر ممکن زمان سفر برای هر وسیلۀ نقلیه |
|
|
مقدار ثابت از تابع قیمت – تقاضا برای مشتری iام |
|
|
مقدار شیب تابع قیمت-تقاضا برای مشتریiام |
|
|
𝐾 |
تعداد وسایل نقلیۀ دردَسترس |
|
ظرفیت وسیلۀ نقلیۀ kام |
همچنین، متغیرهای استفاده‌شده در مدل‌سازی مسئله بهصورت زیر است:
|
قیمت کالای موردنظر که بهصورت بازه‌ای[ ] در نظر گرفته شده است. |
|
|
متغیری که اگر مسیر بین دو مشتری iام و 𝑗ام با وسیلۀ نقلیۀ kام پیموده شود مقدار یک و در غیر این صورت مقدار صفر می‌گیرد. |
|
|
برابر است با جایگاه رأس i در مسیر مربوط به وسیلۀ نقلیۀ kام |
|
|
متغیری که اگر رأس i بازدید شود مقدار یک و در غیر این صورت مقدار صفر می‌گیرد. |
رابطۀ (2) درصدد بیشینه‌کردن کل سود است که قسمت اول آن مربوط به کل درآمد ناشی از فروش کالا است و قسمت دوم آن مربوط به هزینۀ سفر است. محدودیت (3) تضمین می‌کند که هر مسیری از رأس یک شروع می‌شود. محدودیت (4) تضمین می‌کند که هر رأس حداکثر یک بار بازدید می‌شود. محدودیت (5) تضمین می‌کند که تمامی مسیرها به رأس مجازی N ختم می‌شود. محدودیت (6) نیز تضمین می‌کند که از هیچ گره‌ای جز گره مجازی N حق بازگشت به دپو را نداریم. محدودیت (7) تضمین می‌کند که هیچ مسیری از گره مجازی Nام به گره‌های دیگر به جز دپو وجود ندارد. محدودیت (8) پیوستگی مسیر را تضمین می‌کند. محدودیت (9) محدودیت زمانی را برای هر مسیر یا وسیلۀ نقلیه تضمین می‌کند. محدودیت (10) تضمین می‌کند که مقدار بارگیری‌شده از ظرفیت وسایل نقلیه تجاوز نکند. محدودیت‌های (11) و (12) جهت جلوگیری از تشکیل زیر تور لازم‌اند.
3-2- خطی‌سازی مدل
به‌منظور خطی‌سازی مدل پیشنهادی از رویکردی که گلور و ولسی (1974) و چانگ و چانگ (2000) ارائه کردند، بهره برده شد.
4- روش‌های حل
در این مقاله، یک روش برمبنای الگوریتم رقابت استعماری (ICA[16]) برای حل مدل استفاده شده است و نتایج محاسباتی آن بررسی شده است. به‌منظور صحه‌گذاری بر اعتبار این روش در حل مسئله، نتایج حل آن در ابعاد کوچک با نتایج GAMS و الگوریتم شبیه‌سازی تبرید (SA) مقایسه شد؛ سپس برای بررسی عملکرد روش پیشنهادی در ابعاد بزرگ نیز چندین مسئله حل شده است و نتایج آن با الگوریتم SA مقایسه شده است.
4-1- نمایش جواب
نحوۀ نمایش جواب در شکل (1) نشان داده شده است. جواب بهصورت رشته‌ای به‌طول در نظر گرفته شده است که در آن خانۀ اول مربوط به انتخاب یا عدم‌انتخاب مشتریان (تمام مشتریان به جز مشتری آخر که بهصورت مجازی در نظر گرفته شده است) است که بهصورت صفر و یک نشان داده شد (یک به‌منزلۀ انتخاب مشتری iام و صفر برعکس). خانه بعدی توالی بازدید از مشتریان را مشخص می‌کند، خانۀ بعدی تعداد مشتریان تخصیص‌یافته به هر وسیله را مشخص می‌کند و خانۀ آخر هم مربوط به متغیر است.
|
5 |
1 |
1 |
2 |
6 |
2 |
5 |
4 |
3 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
شکل 1- نحوۀ نمایش جواب
نمونۀ جواب تولیدشده برای یک مسئله با شش مشتری و سه وسیلۀ نقلیه در شکل بالا ارائه شده است. همان‌گونه که از خانۀ اول مشخص است مشتریان 2 و 3 بازدید نمی‌شوند لذا در خانۀ اول این مشتریان به وسایل نقلیه اختصاص داده نمی‌شوند. از خانۀ دوم با حذف مشتریان 2 و 3، 2مشتری اول یعنی مشتریان 1 و 4 به وسیلۀ نقلیۀ اول، مشتری 5 به وسیلۀ نقلیۀ دوم و مشتری 6 به وسیلۀ نقلیۀ آخر اختصاص مییابد که این مطلب در خانۀ بعدی مشهود است. همچنین در خانۀ آخر عدد 5 نمایش داده شده است که مربوط به متغیر قیمت است و نشان‌دهندۀ این است که قیمت اختصاص‌یافته به این خدمت‌رسانی جهت بیشینه‌کردن سود 5 واحد است.
4-2- تولید جواب اولیه
برای تولید جواب اولیه الگوریتم SA می‌تواند بهصورت تصادفی این جواب را به دست آورد که در الگوریتم شبیه‌سازی تبرید از این روش استفاده شده است؛ به‌گونه‌ای که برای پارامترP عددی به‌طور تصادفی از بازه ]10/0[ انتخاب شده است و همچنین تخصیص مشتریان به وسایل نقلیه و انتخاب یا عدم‌انتخاب مشتریان نیز به‌طور تصادفی در نظر گرفته شده است. اما روشی که در این مقاله برای تولید جواب اولیه الگوریتم رقابت استعماری بهبودیافته(IICA[17]) در نظر گرفته شده است استفاده از روشی برمبنای نزدیک‌ترین همسایۀ تصادفی است. گام‌های روش مبتنی بر نزدیک‌ترین همسایۀ تصادفی بهصورت زیر است.
1. ابتدا مشتریان به ترتیب کمترین فاصله از انبار مرکزی مرتب می‌شوند و سپس مشتری اول هر یک، به یک وسیله اختصاص داده می‌شوند.
2. سپس از بین سایر مشتریان باقیمانده، فاصلۀ آنها را از Kمشتری اختصاص‌یافته در گام اول محاسبه می‌کنیم و مشتری که کمترین فاصله به هریک از این Kمشتری را داشته باشد به آن مشتری متصل می‌کنیم و این گام را تا اختصاص تمامی مشتریان به وسایل نقلیه ادامه می‌دهیم.
3. با استفاده از روش2-optکه در ادامه توضیح داده می‌شود مسیرها را بهبود می‌دهیم.
4. در گام بعدی مقدار صرفه‌جویی حاصل‌شده از حذف مشتری را برای تمامی مشتریان محاسبه می‌کنیم:
به‌عنوان مثال در شکل (2) صرفه‌جویی حاصل از حذف گره 3 در مسیر 2 برابر است با مجموع هزینه‌های پیمودن مسیر 3-1 و 5-3 منهای هزینۀ پیمودن مسیر 5-1.
شکل 2- نمونۀ حل‌شدۀ مسئله در پایان گام 3
5. در گام بعدی مقدار سوددهی تمامی مشتریان بهصورت زیر محاسبه می‌شود:
اگر تعداد مشتریان n باشد مقدار درآمد کل را که از تابع هدف مدل استخراج شده، از رابطۀ زیر محاسبه می‌کنیم:
با مشتق‌گیری از این رابطه داریم:
سپس مقدار Pرا با صفرقراردادن رابطۀ بالا محاسبه می‌کنیم و داریم:
با مقدار P به‌دست‌آمده از رابطۀ بالا مقدار درآمد هر مشتری را از رابطۀ زیر محاسبه می‌کنیم:
سپس مقدار درآمد به‌دست‌آمده برای هر مشتری در این مرحله را از مقدار صرفه‌جویی محاسبه‌شده در گام 4 کم می‌کنیم. در صورتی که این مقدار منفی شد مشتری مربوطه از مسیر حذف می‌شود و به گام 4 بازمی‌گردیم و این مراحل را آنقدر تکرار می‌کنیم که این مقدار برای تمامی مشتریان باقیمانده مثبت باشد.
4-3- روش پیشنهای مبتنی بر الگوریتمICA
الگوریتم رقابت استعماری یک الگوریتم جدید در زمینۀ الگوریتم‌های تکاملی است که براساس تکامل سیاسی- اجتماعی انسان‌ها شکل گرفته است (آتشپز و لوکاس 2007). الگوریتم پیشنهادی مانند دیگر الگوریتم‌های تکاملی با یک جمعیت اولیه (npopulation) شروع می‌شود(کشورها). پس از تولید کشورها به تعداد از قبل مشخصی (nimperialist) از بهترین کشورها برمبنای قدرتشان، امپراتورها انتخاب می‌شوند. سپس مابقی جواب‌ها به‌عنوان مستعمره به هر امپراتور با توجه به قدرتی که آن امپراتور دارد تخصیص داده می‌شود. قدرت هر استعمارگر بهصورت عکس با هزینۀ آنها ارتباط دارد. پس از تقسیم تمام مستعمره‌ها میان استعمارگرها، درصدی از مستعمره‌ها (PA) شروع به حرکت به سمت امپراتوری خود می‌کنند. هر مستعمره با یک زاویه و با درصدی مشخص به سمت امپراتوری حرکت می‌کند.
شکل 3- نحوۀ حرکت جواب‌ها
در شکل (3) فاصلۀ بین جواب‌های تولیدشده و بهترین جواب با d نشان داده شده است. x نیز عددی تصادفی با توزیع یک‌نواخت است. برای x داریم:
سپس بر مستعمره‌های هر امپراتوری به تعداد مشخصی جستجوی محلی اعمال می‌شود. نحو/ اعمال جستجوهای محلی بدین صورت است که هر بار بهصورت تصادفی یک مستعمره یا امپراتوری انتخاب می‌شود و یک جستجوی محلی بهصورت تصادفی بر آن اعمال می‌شود. در صورت ایجاد جواب بهتر، جواب جایگزین می‌شود و در غیر این صورت تغییرات اعمال نمی‌شود. قدرت هر امپراتوری بستگی به قدرت استعمارگر آن و مستعمره‌های آن دارد. این قدرت بهصورت جمع قدرت استعمارگر و درصدی
( ) از میانگین قدرت مستعمره‌های آن نشان داده می‌شود. سپس رقابت استعماری میان تمام امپراتوری‌ها شروع خواهد شد. هر امپراتوری که نتواند با دیگر امپراتوری‌ها رقابت کند قادر به افزایش قدرت خود نخواهد بود و یا در مواردی کاهش قدرت خود را در پی خواهد داشت و در آخر از رقابت حذف خواهد شد. رقابت استعماری به‌تدریج سبب افزایش قدرت در استعمارگران قدرتمند و کاهش قدرت استعمارگران ضعیف‌تر خواهد شد. امپراتوری‌های ضعیف‌تر قدرت خود را از دست می‌دهند و سرانجام از هم می‌پاشند. حرکت مستعمرات به سمت امپراتوری‌های مربوطه و رقابت بین امپراتوری‌ها و مکانیسم ازهم‌پاشیدگی امپراتوری‌ها سبب می‌شود که کشورها در یک وضعیت قرار بگیرند که در آن یک امپراتوری باقی می‌ماند و تمام کشورها مستعمرۀ آن می‌شوند. در این حالت ایدئال مستعمرات هم قدرت استعمارگران قرار می‌گیرند.
4-3-1- جستجوی محلی
در مسائلی که فضای جواب گسترده‌ای را شامل می‌شوند، از جستجوهای محلی برای بهبود عملکرد روش‌های حل مختلف، استفاده می‌شود. با توجه به گستردگی و پیچیدگی مسأله موردنظر، انتظار می‌رود وجود چهار جستجوی محلی در قسمت مسیریابی الگوریتم ارائه‌شده، بتواند کارایی آن را بهبود دهد. از این رو، از بین این عملگرهای جستجوی محلی روی هر جواب جدیدی که تولید می‌شود، یکی بهصورت تصادفی عمل خواهد کرد. عملگرهایی که در این جستجوی محلی استفاده شده‌اند عملگرهای متغیر ، تعویض دونقطه[18]، چیدمان مجدد[19](2-opt و or-opt) و عملگر انتخاب مشتری هستند.
الف- عملگر متغیر P:به‌منظور تغییر در قیمت هر بار که جستجوی محلی مربوط به متغیر قیمت اجرا می‌شود، بهصورت تصادفی عددی در بازۀ انتخاب می‌شود و به مقدار قیمت اضافه می‌شود.
ب- عملگرهای تعویض دونقطه: این عملگرها برای ایجاد جواب‌های جدید و افزایش تنوع جواب‌های ایجادشده هستند و رویۀ آن به این صورت است که از دو عملگر با احتمال یکسان استفاده می‌شود. عملگر اول بهصورت تصادفی یک وسیلۀ نقلیه را انتخاب می‌کند و جای دو مشتری را در آن تغییر می‌دهد. عملگر دوم نیز جای دو مشتری را در دو وسیلۀ نقلیۀ متفاوت تغییر می‌دهد. این عملگر که از نوع swap در تبادل مشتری است (واترز، 1987)، در شکل (4) مشاهده می‌شود.
شکل 4- عملگر swap
ج- عملگرهای چیدمان مجدد: در این روش پیشنهادی برای ایجاد جواب‌های جدید و افزایش تنوع جواب‌های ایجادشده، از دو عملگر با احتمال به‌کارگیری یکسان استفاده شده است. عملگر اول تغییری از روش 2-opt (کروس، 1958) و (لین، 1965) است که نحوۀ عملکرد برای دو مشتری یک وسیلۀ نقلیه و همچنین دو مشتری از دو وسیلۀ نقلیه متفاوت در شکل (5) دیده می‌شود.
شکل 5- عملگر 2-opt
همان‌گونه که در این شکل مشاهده می‌شود، عملگر گفته‌شده در صورت انتخاب دو مشتری از یک مسیر (سمت چپ)، توالی بین آن دو را برعکس می‌کند و در صورتی که از دو مشتری از دو مسیر متفاوت انتخاب کند (سمت راست)، توالی از آن دو مشتری و به بعد عیناً با یکدیگر عوض می‌شود.
عملگر دوم نیز تغیری از روش or-opt (واترز، 1987) است. این عملگر مکان یک مشتری را تغییر می‌دهد که نحوۀ عملکرد آن در یک مسیر و دو مسیر متفاوت در شکل (6) دیده می‌شود.
شکل 6- عملگر or-opt
د- عملگر انتخاب مشتری: این عملگر نیز برای ایجاد جواب‌های جدید و افزایش تنوع جواب‌های ایجادشده به این صورت عمل می‌کند که از بین تمامی مشتریان یکی را بهصورت تصادفی انتخاب می‌کند. در صورتی که این مشتری قبلاً انتخاب شده باشد، آن را از مسیر حذف می‌کند و در صورتی که انتخاب نشده باشد، آن را انتخاب می‌کند. سپس اقدام به حل مجدد این مسئله می‌کند.
فرایند کلی الگوریتم رقابت استعماری بهبودیافته که در این مقاله به کار گرفته شده است، به‌ترتیب در شکل (7) نمایش داده شده است.
شکل 7- فرایند کلی الگوریتم ICA بهبودیافته
4-4- ارائۀ روش حل برمبنای الگوریتم شبیه‌سازی تبرید
ایده اولیۀ استفاده از الگوریتم شبیه‌سازی را نخستین بار کریک پاتریک (1984) و کرنی و همکارانش (1985) مطرح کردند.
برای حل این مسأله بهینه‌سازی، الگوریتمSA ابتدا از یک جواب اولیه شروع می‌کند و سپس در یک حلقۀ تکرار به جواب‌های همسایه حرکت می‌کند. در این پژوهش از عملگر متغیر ، عملگر تعویض دونقطه و عملگر انتخاب مشتری در الگوریتم شبیه‌سازی تبرید جهت جستجوی محلی استفاده شده است. اگر جواب همسایه بهتر از جواب فعلی باشد، الگوریتم آن را به‌عنوان جواب فعلی قرار می‌دهد (به آن حرکت می‌کند)، در غیر این صورت، الگوریتم آن جواب را با احتمال exp(-ΔE/T) به‌عنوان جواب فعلی می‌پذیرد. در این رابطه ΔE تفاوت بین تابع هدف جواب فعلی و جواب همسایه است و T یک پارامتر به نام دما است. در هر دما، چندین تکرار انجام می‌شود و سپس دما به‌آرامی کاهش داده می‌شود. در گام‌های اولیه، دما خیلی بالا قرار داده می‌شود تا احتمال بیشتری برای پذیرش جواب‌های بدتر وجود داشته باشد. با کاهش تدریجی دما، در گام‌های پایانی احتمال کمتری برای پذیرش جواب‌های بدتر وجود خواهد داشت و بنابراین الگوریتم به سمت یک جواب خوب همگرا می‌شود. گام‌های الگوریتم SA در شکل (8) مشاهده می‌شود.
شکل 8- گام‌های الگوریتم SA
5- نتایج محاسباتی
الگوریتم پیشنهادی به‌همراه الگوریتم شبیه‌سازی، با استفاده از زبان برنامه‌نویسی متلب[20] کدنویسی شد و بر یک رایانۀ 2.5 GHz با حافظۀ 6 گیگابایت اجرا شد.
5-1- مسائل نمونه
از آنجا که مسأله موردبررسی، برای اولین بار معرفی شده است، مسأله نمونه برای آن وجود نداشت و ساختن چنین مسائلی امری ضروری به نظر می‌رسید. برای این مسئله، 14 نمونه با تعداد مشتریان 5 تا 45 و تعداد وسایل نقلیۀ 2 تا 10ساخته شد. مختصات مشتریان و تقاضای آنها برگرفته از نمونه‌های کلاس 1 استفاده‌شده درVRPLIB است[21].
همچنین برای تقاضای هر خرده‌فروش از تابع تقاضای خطی[22] با شیب غیرصعودی استفاده شده است. برای این منظور مقدار متغیر ثابت بهصورت تصادفی در بازۀ [15-45] و مقدار شیب بهصورت تصادفی در بازه
[2-5] برای هر خرده‌فروش در نظر گرفته شده است. همچنین برای قیمت خدمات ارائه‌شده یک بازه از 1 تا 10 در نظر گرفته‌ایم که سعی در یافتن بهترین قیمت برای ارائۀ خدمات به مشتریان داریم که از طرفی در بازار رقابتی بتوانیم مشتریان را به سوی خود جلب کنیم و از سوی دیگر سود خود را بیشینه کنیم. تعداد مشتریان و وسایل نقلیه برای مسائل نمونه در جدول (1) مشاهده می‌شود.
جدول 1- مشخصات مسائل نمونه
|
نمونه |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
|
تعداد مشتریان |
5 |
7 |
8 |
10 |
10 |
12 |
15 |
18 |
20 |
25 |
30 |
35 |
40 |
45 |
|
تعداد وسایل |
2 |
2 |
3 |
2 |
3 |
3 |
5 |
5 |
6 |
7 |
8 |
9 |
10 |
10 |
5-2- تنظیم پارامتر
پارامترهای تأثیرگذار در الگوریتم ICA پیشنهادی عبارت‌اند از: اندازه جمعیت هر دوره(npopulation)، تعداد قدرتمندترین امپراتوری‌ها (nimperialist)، نرخ جواب‌هایی که به امپراتور نزدیک می‌شوند (PA)، ضریبی که هزینۀ امپراتوری را به هزینۀ استعمارگر وابسته می‌کند
( ) و ضریب مربوط به حرکت مستعمره‌ها به سمت استعمارگر خود ( ). همچنین پارامترهای تأثیرگذار در الگوریتم SA عبارت‌اند از: دمای اولیه ( )، ضریب تبرید الگوریتم( (، تعداد دفعات تکرار الگوریتم (IT) و تعداد دفعات تکرار در هر دما (innerIT). مقدار تمامی این پارامترها با استفاده از روش طراحی آزمایش‌های تاگوچی به دست آمده است. روش طراحی آزمایش‌های تاگوچی را در سال 1960 پروفسور تاگوچی معرفی کرد. این روش می‌تواند با کمترین تعداد آزمایش‌ها، شرایط بهینه را تعیین کند (روی، 2010). استفاده از این روش منجر به صرفه‌جویی بسیار در زمان و هزینۀ انجام آزمایش‌های موردنیاز برای تنظیم پارامتر نسبت به روش کلاسیک فاکتوریل کامل می‌شود.
مقادیر هریک از پارامترهای مربوط به IICA و الگوریتم SA به‌کاررفته در این الگوریتم بهصورت جدول (2) تنظیم شده است.
جدول 2- پارامترهای تنظیم‌شدۀ الگوریتم‌ها
|
IICA |
SA |
||
|
عامل |
مقدار بهینه |
عامل |
مقدار بهینه |
|
50 |
100 |
||
|
6 |
99/0 |
||
|
0.64 |
800 |
||
|
0.195 |
70 |
||
|
1.8 |
|||
5-3- بررسی الگوریتم پیشنهادی برای مسائلی در مقیاس کوچک
برای سنجش اعتبار الگوریتم‌های پیشنهادی، عملکرد آن با عملکرد الگوریتم شبیه‌سازی تبرید پایه و حل‌کنندۀ CPLEX بستۀ تجاری گمز[23](نسخه 24.1.3) در حل مسائلی در مقیاس کوچک مقایسه شده است. بدین منظور، برای هریک از این نمونه‌ها، ابتدا جواب بهینه با استفاده از بستۀ گفته‌شده به دست آمد و سپس با نتایج الگوریتم‌ها مقایسه شد. در این پژوهش، شاخص دسته‌بندی یک مسئله در مقیاس کوچک، زمان حل توسط بستۀ تجاری گمز در نظر گرفته شد و مسائلی که زمان حلی کمتر از 3600 ثانیه داشتند، در این دسته قرار گرفتند. نتایج محاسباتی مربوط به بستۀ تجاری گمز، الگوریتم ICA بهبودیافته و الگوریتم SA به‌ترتیب در ستون‌هایی تحت‌عنوان GAMS، IICA و SA آمده است. برای هر مسئله، هریک از الگوریتم‌ها سه بار اجرا شد.
بهترین مقدار تابع هدف به دست آمده است و میانگین زمان اجرای الگوریتم برحسب ثانیه در این تعداد از دفعات اجرا، به‌ترتیب در ستون «تابع هدف» و ستون «زمان» گزارش شده است. ستونی که تحت‌عنوان %dev در این جدول مشخص است، برای نشان‌دادن درصد انحراف از جواب بهینه برای هریک از الگوریتم‌های فرااِبتکاری است. همان‌گونه که مشاهده می‌شود، الگوریتم‌های IICA و SA توانایی دستیابی به جواب بهینه را برای مسائلی در مقیاس کوچک دارند که این نکته، اعتبارآنها را در حل مدل تأیید می‌کند.
براساس اطلاعات جدول (3) با وجود انحراف قابل‌قبول از جواب بهینه در دو الگوریتم، عملکرد الگوریتم IICA براساس شاخص درصد انحراف از جواب بهینه، بسیار بهتر از الگوریتم شبیه‌سازی تبرید پایه (SA) است. درصد انحراف از جواب بهینه برحسب نمونه در شکل (9) نیز دیده می‌شود.
شکل 9- نمودار درصد انحراف از جواب بهینه برای مسائل در مقیاس کوچک
نمودار زمان محاسباتی برحسب نمونه برای بستۀ تجاری و هر دو الگوریتم فراابتکاری در شکل (10) دیده می‌شود. براساس این شکل،IICA نسبت به SA عملکرد بهتری دارد، البته در نمونۀ گفته‌شده،IICA جوابی نزدیک به جواب بهینه ارائه داده است.
شکل 10- نمودار زمان محاسباتی برحسب نمونه برای مسائل در مقیاس کوچک
جدول 3- نتایج محاسباتی برای مسائلی در مقیاس کوچک
|
SA |
|
IICA |
|
GAMS |
|
نمونه |
|||||
|
% dev |
زمان (s) |
تابع هدف |
|
% dev |
زمان (s) |
تابع هدف |
|
زمان (s) |
تابع هدف |
|
|
|
00/0 |
00/0 |
2/168 |
|
00/0 |
00/0 |
2/168 |
|
31/2 |
20/168 |
|
1 |
|
00/0 |
15/23 |
187/57 |
|
00/0 |
59/6 |
57/187 |
|
47/2 |
57/187 |
|
2 |
|
71/6 |
13/49 |
94/164 |
|
00/2 |
13/8 |
32/173 |
|
3/4 |
86/176 |
|
3 |
|
60/8 |
02/79 |
39/138 |
|
76/2 |
35/19 |
23/147 |
|
7/5 |
41/151 |
|
4 |
|
86/8 |
29/140 |
37/209 |
|
33/1 |
24/20 |
67/226 |
|
2/18 |
72/229 |
|
5 |
|
51/10 |
39/169 |
49/384 |
|
81/3 |
85/80 |
27/413 |
|
6/617 |
65/429 |
|
6 |
|
46/21 |
28/271 |
99/661 |
|
38/1 |
27/210 |
27/831 |
|
9/1220 |
88/842 |
|
7 |
|
02/8 |
61/104 |
56/273 |
|
61/1 |
31/49 |
79/306 |
|
35/276 |
33/312 |
|
میانگین |
براساس جدول و نمودارهای ارائه‌شده، می‌توان به این نتیجه رسید که برای مسائل در مقیاس کوچک، IICA نسبت به الگوریتم SA بسیار بهتر عمل می‌کند؛ این برتری شامل تمامی شاخص‌های بررسی (درصد انحراف از جواب بهینه و زمان محاسباتی) است.
5-4- بررسی الگوریتم‌های پیشنهادی برای مسائلی در مقیاس بزرگ
در این قسمت نیز همانند قسمت قبل، برای هر مسئله، هریک از الگوریتم‌های شبیه‌سازی تبرید پایه و شبیه‌سازی تبرید بهبودیافته سه بار اجرا شد، بهترین مقدار تابع هدف به دست آمد و میانگین زمان اجرای الگوریتم برحسب ثانیه در این تعداد از دفعات اجرا، به‌ترتیب در ستون «تابع هدف»، ستون «زمان» و ستون «قیمت» جدول (4) گزارش شده است.
برای بررسی‌های بهتر، نمودار تابع هدف برحسب نمونه برای هر دو الگوریتم در شکل (11) نمایش داده شده است. براساس این نمودار می‌توان به این نتیجه رسید که در حالت کلی، عملکرد IICA از الگوریتم SA بهتر است.
جدول 4- نتایج محاسباتی برای مسائلی در مقیاس بزرگ
|
ICA |
SA |
||||
|
زمان(s) |
تابع هدف |
% dev |
زمان(s) |
تابع هدف |
نمونه |
|
8/248 |
23/947 |
68/11 |
92/328 |
59/836 |
8 |
|
1/317 |
3/1182 |
79/21 |
85/371 |
76/924 |
9 |
|
9/381 |
1/1537 |
66/19 |
48/591 |
92/1234 |
10 |
|
2/430 |
2/1841 |
92/12 |
82/639 |
44/1603 |
11 |
|
3/812 |
6/2634 |
01/16 |
1/1128 |
69/2212 |
12 |
|
2/1012 |
4/3137 |
22/14 |
9/1429 |
39/2691 |
13 |
|
4/1423 |
8/3879 |
88/17 |
3/1884 |
13/3186 |
14 |
|
1/660 |
7/2165 |
31/16 |
66/910 |
85/1812 |
Ave |
شکل 11- نمودار مقدار تابع هدف برحسب نمونه برای مسائل در مقیاس بزرگ
همچنین برای بررسی عملکرد دو الگوریتم، درصد انحرافات الگوریتم SA از IICA برحسب نمونه در شکل (12) نشان داده شده است. براساس این نمودار مشاهده می‌شود که در تمامی نمونه‌ها الگوریتم پیشنهادی نسبت به الگوریتم پایه عملکرد بهتری را از خود نشان می‌دهد.
شکل 12- نمودار درصد انحرافات الگوریتمSA نسبت به الگوریتم IICA
برای بررسی عملکرد دو الگوریتم براساس زمان محاسباتی، در شکل (13) این شاخص برحسب نمونه آورده شده است. همان‌گونه مشاهده می‌شود IICA عملکرد قابل‌قبولی را از خود نشان می‌دهد.
شکل 13- نمودار زمان محاسباتی برحسب نمونه برای مسائل در مقیاس بزرگ
همان‌طور که از نمودار شکل (11) مشخص است IICA در تمامی نمونه‌های با سایز بزرگ از نظر مقدار تابع هدف، عملکرد بهتری نسبت به الگوریتم SA داشته است. در شکل (12) نیز نمایان است که مقدار انحرافات الگوریتم SA نسبت به الگوریتمIICA در تمامی نمونه‌ها مقداری زیاد است و به‌طور میانگین الگوریتم SA 31/16درصد نسبت به الگوریتم پیشنهادی از نظر مقدار تابع هدف اختلاف دارد که این مقدار، عملکرد بهتر الگوریتم پیشنهادی را نشان می‌دهد. همچنین در شکل (13) مشخص می‌شود که عملکرد IICA نسبت به الگوریتم SA از نظر زمانی، در تمامی 7 نمونه با سایز بزرگ بهتر است؛ طوری که میانگین زمانی حل این مسائل برای IICA ،660.16 ثانیه است؛ در حالی که این مقدار برای الگوریتم SA، 66/910 ثانیه است که نشان‌دهندۀ عملکرد بهتر الگوریتم پیشنهادی است.
6- نتیجه‌گیری و پیشنهادهایی برای مطالعات آتی
قیمت‌گذاری کالا معمولاً با توجه به قیمت محصولات رقیب، کشش بازار و هزینه‌های تولید در نظر گرفته می‌شود. در میان هزینه‌های تولید، هزینۀ توزیع کالا بخشی از هزینه‌ها است که توجه به این هزینه در انتخاب قیمت مناسب نقش مؤثری دارد. از سوی دیگر شرکت‌های توزیع می‌توانند با توجه به قیمت بهینه و هزینه‌های مسیریابی تنها خدمت‌دهی به مشتریانی را در نظر بگیرند که خدمات‌دهی به آنها در سطح قیمت بهینه مقرون‌به‌صرفه باشد و از این طریق سود مناسبی را نصیب خود کنند. در این مقاله مسأله مسیریابی وسیلۀ نقلیۀ انتخابی باز با درنظرگرفتن قیمت‌گذاری بررسی شد. برای این منظور فرض شد که قیمت با تقاضای مشتریان یک رابطۀ خطی دارد و شرکت‌های توزیع از ناوگان حملی که بهصورت اجاره‌ای در خدمت شرکت توزیع هستند استفاده می‌کنند و همچنین هر مشتری حداکثر یک بار بازدید می‌شود و قیمت یکسانی برای تمامی مشتریان در نظر گرفته شد. همان‌گونه که قبلاً نیز اشاره شد، چنین مسئله‌ای باوجودِ کاربردی‌بودن در ادبیات مسأله مسیریابی مشاهده نمی‌شود. پس از معرفی مسأله ذکرشده، مدل ریاضی برای آن ارائه شد و سپس روش حلی برمبنای الگوریتم رقابت استعماری برای حل آن توسعه یافت و نتایج آن با نتایج حاصل از الگوریتم SA بررسی و تحلیل شد.
مطالعۀ حاضر را می‌توان با درنظرگرفتن تابع تقاضای درجۀ دو برای هر مشتری توسعه داد. همچنین می‌توان از هزینه‌های دیگر برای این مسئله استفاده کرد. درنهایت، می‌توان الگوریتم‌های دقیق، ابتکاری یا فرااِبتکاری دیگر برای حل مسأله ذکرشده استفاده کرد.
[1]- Vehicle routing problem
[2]- Selective vehicle routing problem
[3]- Open vehicle routing problem
[4]- Simulated Annealing with Restart Strategy
[5]- Boltzmann Function
[6]- Cauchy Function
[7]- Fuzzy
[8]- Robust
[9]- Reliable
[10]- Parallel Genetic Algorithm
[11]- Mobile blood collection system
[12]- VRP with Backhauls
[13]- Simulated annealing
[14]- Inventory Routing Problem
[15]- Tabu search
[16]- Imperialist competitive algorithm
[17]- Improved Imperialist Competitive Algorithm
[18]- Swap
[19]- Reversion
[20]- MATLAB
[21]-برای دستیابی به مسائل ذکرشده می‌توان به http://www.or.deis.unibo.it/research_pages/ORinstances/VRPLIB/VRPLIB.html مراجعه کرد.
[22]- Linear demand function
[23]- GAMS
)