چکیده

مسألۀ مسیریابی وسیلۀ نقلیه با پنجره­ های زمانی (VRPTW)شامل تعیین مسیرهای خودرو مفروض با ظرفیت برابر و مستقر در یک انبار مرکزی است که برای پاسخ گویی به تقاضاهای مجموعۀ مشتریان با پنجره ­های زمانی مشخص استفاده می شود. این مورد، یک مسألۀ پیچیده با چندمحدودیت با پیامدهای صنعتی، اقتصادی و محیطی است که به صورت گسترده ­ای در گذشته تحلیل شده است. این مقاله، با انواع چندهدفه VRPTW سروکار دارد به طوری که به صورت هم زمان مسافت پیموده شده و عدم تعادل­ مسیرها را حداقل می­کند. این عدم تعادل، از دو منظر تحلیل می­ شود: عدم تعادل در مسافت­های طی شده با وسایل نقلیه، و عدم تعادل در بارهای تحویل داده شده به وسیلۀ آن­ها. رویکرد چندهدفه برمبنای نوردیدن شبیه سازی شده، نوردیدن شبیه ­سازی شده پارتو تحت دماهای مختلف (MT-PSA) در این مقاله جهت مواجهه با فرمول­ بندی ­های چندهدفه VRPTW پیشنهاد می­ شود، رویکرد MT-PSA و نسخه موازی جزیره-مبنای MT-PSA ارزیابی شده و به ترتیب با اجراهای جزیره-مبنای موازی و توالی SPEA2 مقایسه می ­شوند. نتایج محاسباتی به دست آمده در مسائل معیار Solomon نشان می ­دهد که روندهای موازی سازی جزیره-مبنا، نسبت به آنهایی که به وسیلۀ نسخه ­های متوالی بدست می ­آیند بدون افزایش هزینۀ محاسباتی مرزهای پاراتو با کیفیت بالاتر حاصل می­ کند، در حالی که کاهش قابل توجهی در زمان اجرا با حفظ کیفیت جواب نیز دارند. به طور خاص­ تر، در بیشتر قسمت­ ها در اینجا، روش MT-PSA با توجه به کیفیت جواب و زمان اجرای بهتر از SPEA2 به عنوان معیار در نظر گرفته می­ شود.

1-مقدمه

مسألۀ مسیریابی وسیلۀ نقلیه، نوعی مسألۀ بهینه­ سازی ترکیبی است که به وفور در زندگی واقعی اتفاق می ­افتد مانند حمل و نقل، لجستیک و برنامه­ ریزی.  از این رو، خانوادۀ مسائل مربوط به وسیلۀ نقلیه در دستۀ مسائل دشوار NP قرار می ­گیرند (Lenstra & Rinnooy Kan, 1981,). به ویژه زمانی که تعداد مشتریان زیاد می­ شود حل آنها نیز دشوارتر می ­شود (Lee, Lee, Lin, & Ying, 2010). آن­ها با تکنیک­ های مختلفی بررسی شده ­اند که هم  روش های دقیق و هم روش ­های ابتکاری را شامل می­شود (Eksioglu, Vural, & Reisman, 2009)، اما هزینۀ محاسباتی روش­های دقیق و عملکرد ضعیفشان در مسائل بزرگ، باعث شده است که پژوهش فعلی بر الگوریتم ­های تصادفی تمرکز داشته باشد که قادر به تولید جواب ممکن اما نه لزوماً بهینه در زمان محدود هستند. مسائل بهینه ­سازی در دنیای واقعی، در اقتصاد، مهندسی یا صنعت نیاز به طراحی الگوریتم­ های کارا دارند...