کولونی مورچه ها مسئله فروشنده دوره گرد با پنجره زمانی

کولونی مورچه ها مسئله فروشنده دوره گرد با پنجره زمانی – ایران ترجمه – Irantarjomeh

مقالات ترجمه شده آماده گروه مهندسی صنایع

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

مقالات

چگونگی سفارش مقاله

الف – پرداخت وجه بحساب وب سایت ایران ترجمه(شماره حساب)ب- اطلاع جزئیات به ایمیل irantarjomeh@gmail.comشامل: مبلغ پرداختی – شماره فیش / ارجاع و تاریخ پرداخت – مقاله مورد نظر --مقالات آماده سفارش داده شده پس از تایید به ایمیل شما ارسال خواهند شد.

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

چکیده

مسئله فروشنده دوره گرد با پنجره زمانی در مسیریابی و زمان بندی کاربرد مهمی دارد و به طور گسترده در مباحث موجود مورد مطالعه قرار گرفته است. در این مقاله یک فرمول ریاضی از مسئله فروشنده دوره گرد – زمانی  با پنجره زمانی ارائه شده و یک فرمول فرا اکتشافی بر اساس یک سیستم کولونی مورچه ها مطرح و اجرا شده است. یک آزمایش محاسباتی بر حس نوعی معیارسنجی انجام شده و یک مطالعه موردی نیز مورد تحلیل قرار گرفته که منجر به نتایج جالبی گردیده است.

واژگان کلیدی: سیستم کولونی مورچه ها، TSPTW– زمانی

کولونی مورچه ها مسئله فروشنده دوره گرد با پنجره زمانی

 ۱- مقدمه

مسئله فروشنده دوره گرد با پنجره زمانی (TSPTW) عبارت است از یافتن مینیمم طول مسیری که یک وسیله نقلیه طی می کند، به طوریکه از مجموعه ای از گره ها دقیقاً یک بار عبور کند. ارائه خدمت در گره باید در یک پنجره زمانی معین انجام شود به طوریکه اگر وسیله نقلیه زودتر برسد باید منتظر بماند تا پنجره باز شود [۴].

هدف مسئله معمولاً حداقل کردن کل طول مسیر می باشد. در این مقاله فرمول کلاسیک TSPTW مورد بررسی قرار گرفته [۴] و نوع دیگری از مسئله،  به نام TSPTW – زمانی مطرح شده است.  تفاوت بین دو مسئله در تعریف تابع هدف آنها می باشد. در TSPTW– زمانی زمان وزنی کل، زمان طی مسیر و زمان انتظار به حداقل رسیده اند.

TSPTW در ادبیات هم با الگوریتم های دقیق [۷]، [۸]، [۱۱] و هم با روش های اکتشافی [۱۰]، [۱۲] حل شده است.

در این مقاله یک روش فرا اکتشافی بر اساس سیستم کولونی مورچه ها  هم برای مسئله فروشنده دوره گرد با پنجره زمانی (SACS) و هم برای مسئله فروشنده دوره گرد با پنجره زمانی – زمانی (TACS) مطرح و اجرا شده است و یک آزمایش محاسباتی نیز ارائه شده که نمونه هایی از یک معیارسنجی که در مقالات [۱۱] و [۱۳] مطرح شده است را حل میکند. همانطور که در ادامه بحث خواهد شد، نمونه های معیارسنجی هم برای SACS و هم برای TACS آزمایش شده اند.

کولونی مورچه ها مسئله فروشنده دوره گرد با پنجره زمانی

۲- مسئله

یک مسئله توزیع حمل و نقل را در نظر بگیرید که ویژگی های زیر را دارد:

• یک وسیله نقلیه باید در یک دوره زمانی[۰,T] به مجموعه ای از مشتریان دقیقاً یک بار خدمت ارائه می دهد.

• ممکن است هر مشتری در یک پنجره زمانی خاص در دوره [۰,T] نیاز به خدمت داشته باشد.

• حداقل هزینه مسیر باید تعیین شود.

مسئله را می توان به صورت یک مسئله فروشنده دوره گرد کلاسیک TSPTW فرمول بندی کرد.

کولونی مورچه ها مسئله فروشنده دوره گرد با پنجره زمانی

۳- سیستم کولونی مورچه ها

سیستم کولونی مورچه ها یک مجموعه از مورچه های مصنوعی که برای حل یک مسئله بهینه سازی از طریق تبادل اطلاعات توسط فرمون (ماده شیمیایی بودار که به وسیله حیوانات تولید شده و وسیله ای برای ایجاد ارتباط بین گروهی است[۱]) که در لبه های گراف بر جا گذاشته شده است  با هم همکاری می کنند را مطالعه می کند.

مورچه های واقعی قادرند با استفاده از فرمونی که توسط مورچه های قبلی به جا می ماند  کوتاهترین مسیر از یک منبع غذا به لانه خود را پیدا کنند، این کار موجب توسعه چیزی می شود که به عنوان یادگیری گروهی تفسیر می شود. ردپای فرمون در کوتاهترین مسیر سریعتر انباشته می شود، به طوری که به زودی تمام مورچه ها به آنجا خواهند رفت.

اولین مسئله ای که این روش در آن اعمال شده مسئله فروشنده دوره گرد (TSP) ([5]،[۶]،[۱۴]) است و اخیراً یک الگوریتم برای VRP([1]،[۲]) و TRPTW( [9])  نیز مطرح شده است. این روش هرگز برای حل TSPTW به کار نرفته است.

[۱] یادداشت مترجم

کولونی مورچه ها مسئله فروشنده دوره گرد با پنجره زمانی

۴- توصیف روش فرا اکتشافی

الگوریتم هایی که برای حل مسئله فرموله شده در بخش ۲ مطرح شده اند مشابه الگوریتم های مطرح شده برای حل TSP در [۶] بوده و با الگوریتم دیگری که تنها برای ارزیابی تابع هدف مطرح شده است تفاوت دارند. این الگوریتم ها به ترتیب  SACS( سیستم مکانی کولونی مورچه ها) و TACS ( سیستم زمانی کولونی مورچه ها) نامیده می شوند.

در ادامه الگوریتم TACS توصیف می شود.

مرحله اول روند کار توسط یک الگوریتم که بر اساس نزدیکترین مجاور می باشد یک حل امکان پذیر را پیدا می کند [۱۳]. این الگوریتم به خاطر پیچیدگی اندکش انتخاب شده است، حتی اگر تضمین نکند تمام گره ها در مسیر وارد شده اند:  این امر ممکن است به خاطر یک پنجره زمانی خاص اتفاق بیفتد؛ که ممکن است بعضی گره ها را در بر نگیرد. از آنجا که هدف این مرحله فقط ارائه یک معیار دقیق از هزینه مسیر که برای تثبیت سطح اولیه فرمون لبه ها لازم است می باشد، در این مسئله طول میانگین لبه ای که در حل جزئی مورد استفاده قرار گرفته بود محاسبه شد و به هزینه طول کل تمام گره هایی که هنوز مشاهده نشده بودند اضافه شد.

اجازه دهید  را بهترین حل جاری ( در کل بهترین حل) در نظر بگیریم.

مرحله دوم مستلزم این است که یک کولونی از مورچه ها فعال باشند تا کوتاهترین مسیر را پیدا کنند.

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

۴-۱- مجموعه مشتریان سازگار و محدودیت پنجره زمانی

اجازه دهید N_i را مجموعه مشتریان سازگار در نظر بگیریم به طوریکه آخرین گره ای که مشاهده می شود گره i باشد. N_i مجموعه تمام  مشتریانی خواهد بود  که j را مشاهده نمی کنند، به طوریکه

۴-۲- ارزیابی

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

۴-۳- قوانین به روز رسانی فرمون

قوانین به روز رسانی فرمون عبارتند از:

کولونی مورچه ها مسئله فروشنده دوره گرد با پنجره زمانی

۵- نتایج محاسباتی

الگوریتمی که توصیف شد در برنامه Visaul Basic کدگذاری شده و بر روی XP 1600, 1.39 GHz اجرا گردید.

آزمایشات اولیه برای انتخاب مقدار پارامترها انجام شد. نتایج نشان داد که با تنظیمات زیر می توان نتایج رضایت بخشی بدست آورد:

کولونی مورچه ها مسئله فروشنده دوره گرد با پنجره زمانی

۶- مطالعه موردی

شرکتی تعداد زیادی محصولات غذایی را در تقریباً تمام مناطق ایتالیا خانه به خانه توزیع می کند.

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

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

هدف به کار گیری الگوریتم برای این مورد یافتن یک راه مؤثر برای ملاقات با یک مجموعه مشتری از پیش تعیین شده نسبت به پنجره زمانی آنها در کوتاهترین زمان می باشد.

کولونی مورچه ها مسئله فروشنده دوره گرد با پنجره زمانی

۶-۱- نمونه

نمونه حل شده ۶۴ مشتری را بررسی کرد، داده های مربوطه در جدول۴ ارائه شده است ( پیوست ۱ را ببینید)، مختصات دکارتی مربوط به یک سیستم متریک مناسب و پنجره زمانی هر مشتری می باشد.  گره- مبدأ گره ای است که ۰ نامیده می شود. ماتریس فاصله اقلیدسی با ضریب ۲ وزن دهی شده است تا تقریب بهتری از فاصله واقعی داشته باشد که این واقعیت که جاده ها به صورت خطوط مستقیم وجود ندارند را نیز در نظر بگیرد.  در هر مورد مقدار ۲ برای ضریب اصلاح به نظر بسیار محافظه کارانه می آید.

هر نماینده خودش زمان شروع مسیر خود را انتخاب می کند، به طوریکه گره – مبدأ از ۶:۳۰ تا ۲۲:۳۰ در نظر گرفته می شود؛ برای تمام مشتریانی که یک پنجره زمانی درخواست نکرده اند شرکت فاصله زمانی را بین ۸:۳۰ تا ۲۰:۳۰ مشخص می کند.

کولونی مورچه ها مسئله فروشنده دوره گرد با پنجره زمانی

۷- نتیجه گیری

لازم به ذکر است که در تمام موارد آزمایش محاسباتی که انجام شد تعداد مورچه هایی که به کار رفت ۳۰ مورچه بود، که نسبت به تعداد گره ها زیاد است. در واقع، هرچه تعداد مورچه بزرگتر باشد تأثیر قانون به روز رسانی موضعی فرمون بیشتر است و لذا تعداد حل های استخراج شده بیشتر خواهد بود. به این طریق ممکن است جهش از یک مینیمم موضعی راحت تر باشد، حتی اگر ممکن باشد افتادن در یک مینیمم موضعی یک مسئله خاص از روش های فرا اکتشافی باشد.

از آنجا که تعداد مورچه ها نیز یکی از پارامترهای انتخاب شده است انجام یک آنالیز حساسیت  برای بررسی اینکه مقدار پارامتری که مناسب است کدام است جالب خواهد بود، مشابه کاری که در [۱۳] انجام شد.  به عنوان مثال درک اینکه معیار توقف چگونه باید انتخاب شود که یک حل رضایت بخش را تضمین کند بسیار جالب خواهد بود.

یک تصمیم بسیار مهم دیگر مربوط به ایجاد داده های نمونه می باشد که مخصوصاً در موارد واقعی ممکن است آسان نباشد. در واقع ممکن است تعریف فاصله مکانی بین دو گره با استفاده از جاده های واقعی دشوار باشد و همچنین تعریف فاصله زمانی بین دو گره با در نظر گرفتن مسائلی مانند ترافیک و غیره نیز دشوار خواهد بود.

همانطور که می توان دید زمان محاسبات همیشه بسیار کم است؛ حتی اگر اندازه نمونه مورد بررسی بسیار کوچک باشد، با این وجود انجام محاسبات را می توان بسیار رضایت بخش در نظر گرفت.