چکیده
در این مقاله الگوریتم ممتیک موازی برای مسئله مسیریابی وسایل نقلیه NP-hard با پنجره های زمانی (VRPTW) پیشنهاد شده است. این الگوریتم از اجزایی تشکیل می شود که به صورت فرایندهای موازی اجرا می شوند. فرایندیک الگوریتم هیوریستیک یا ابتکاری یا ترکیبی از الگوریتم ژنتیکی و تعدادی رویه اصلاح محلی اجرا می کند. برای بهبود نتایج، فرایندها با استفاده از طرح تصادفی جدیدی به صورت دوره ای باهم همکاری می کنند. در طول هر فاز از فرایندهای همکاری از بهترین راه حل های تاکنون یافت شده استفاده می گردد. هدف این کار، توصیه الگوریتم ممتیک موازی است که راه حل های VRPTW با بالاترین کیفیت ممکن را تعیین می کند. آزمایشات انجام شده روی تست های محک زنی Gehring و Homberger (GH) نشان می دهد که الگوریتم به نتایج بسیار خوبی دست می یابد. با استفاده از بهترین و شناخته شده ترین راه حل ها برای 171 GH از میان 300 GH، نتایج بدست آمده بهبود یافت.
1-مقدمه
مسئله مسیریابی وسایل نقلیه با پنجره های زمانی (VRPTW)، یک مسئله بهینه سازی NP-hard مهم می باشد. در این مسئله طرح مسیریابی حداقل یا مینیموم هزینه برای تحویل کالاها از یک انبار به مجموعه مشتریان، تعیین می گردد. هدف اصلی، به حداقل رساندن تعداد وسایل نقلیه بکاررفته و هدف دوم، به حداقل رساندن فاصله کل پیموده شده توسط وسایل نقلیه می باشد...