الگوریتم فراابتکاری کلونی مورچگان برای مساله مسیریابی اتوبوس مدرسه

Abstract

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