بررسی مسیله مسیریابی چندهدفه با در نظر گرفتن پنجره زمانی

یکی از مسایل مهم که در چند دهه اخیر کاربرد بسیار بالایی در عمل داشته و برای افزایش کارایی و بهره وری سیستم های حمل ونقل مطرح شده است بحث مسیله مسیریابی وسایل نقلیه(VRP)1 است. مسیله مسیریابی وسایل نقلیه به مجموعه ای از مسایل اطلاق میگردد که در آن تعدادی خودرو متمرکز در یک یا چند قرارگاه بایستی به مجموعه ای از مشتریان مراجعه نموده و خدمتی را ارایه دهند که هریک دارای تقاضای معینی میباشند. این مسیله درصدد است تا با مدل ریاضی و بهینه سازی به گونه ای عمل کند که مسافت طی شده، زمان کل سفر، تعداد وسایل حمل ونقل، جریمه های دیرکرد و در نهایت تابع هزینه حمل ونقل حداقل گردد و رضایت مشتریان به حداکثر برسد. وجود محدودیت های مختلف در اینگونه مسایل انواع مختلفی از مسایل کلاسیکی تشکیل میدهد که یکی از آنها بحث وجود پنجره های زمانی در سرویس مشتریان است. در این نوع مسایل خدمت دهندگان موظفند در بازه زمانی تعیین شده خدمت رسانی کنند. اینگونه مسایل جز مسایل NP-Hard بوده و حل آن از طریق برنامه ریزی خطی و نرم افزارهای موجود مدت زمان بالایی را به خود اختصاص میدهد. لذا برای حل از الگوریتمهای فراابتکاری استفاده میشود.اگرچه بیشتر مقالات پژوهشی در زمینه VRP روی بهینه سازی یک هدفه تمرکز دارند اما استفاده از بهینه سازی چند هدفه توجه بیشتر محققان را جذب میکند، چون فرصتهای جدید برای تعریف مسیله را به وجود میآورد. بنابراین در سالهای اخیر مسیله مسیریابی با چند هدف گسترش بسیاری یافته است. برخی مسایل چند هدفه با استفاده از رویکردهای متراکم فرموله و حل می شوند، که در آن با استفاده از ترکیب عملیات ریاضی تمام اهداف بهینه میشود. نقطه ضعف این رویکرد این است که تعیین دقیق وزن دشوار است، به ویژه زمانی که اطلاعات ناکافی یا دانش مربوط به مسیله دنیای واقعی مقیاس بزرگ مسیله مسیریابی وجود دارد. استراتژی مبتنی بر پارتو برای این منظور بسیار مناسب است.

Keywords:

مساله مسیریابی , پنجره زمانی , بهینه سازی چند هدفه