الگوريتم فراابتكاري كلوني مورچگان براي مساله مسيريابي اتوبوس مدرسه

An ant colony metaheuristic algorithm for school bus routing problem

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

This paper deals with the school bus routing problem (SBRP). This problem is a variant of the vehicle routing problem where three simultaneous decisions that have to be made: determining the set of stops to visit, for each student which stop he should walk to and the latter case occurs when determining the routes visited with the chosen stops, so that the total traveled distance is minimized. In the standard VRP all stops to visit are given, but in school bus routing problem, is assumed that a set of potential stops is given, as well as a set of students that can walk to one or more of these potential stops. The school buses used to pick up the students and transport them to school have a finite capacity. Ant Colony Optimization (ACO) is a metaheuristic for combinatorial optimization problems. In this paper, artificial ant colony is developed. its successful application to the SBRP and finds optimal or closeto optimal solutions of large instances of the SBRP in very limited computing times is shown.