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

قنبری, وجیهه; رضائیان, جواد; مهدوی, ایرج

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

نوع مقاله : علمی - پژوهشی

نویسندگان

¹ کارشناس ارشد، دانشکده مهندسی صنایع، دانشگاه علوم و فنون مازندران، بابل، ایران

² استادیار، دانشکده مهندسی صنایع، دانشگاه علوم و فنون مازندران، بابل، ایران

³ دانشکده مهندسی صنایع، دانشگاه علوم و فنون مازندران، بابل، ایران

چکیده

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

کلیدواژه‌ها

20.1001.1.20086598.1395.8.1.2.1

عنوان مقاله [English]

An ant colony meta-heuristic algorithm for school bus routing problem

نویسندگان [English]

Vahije Ghanbari ¹
Javad Rezaeian ²
Iraj Mahdavi ³

¹ MSc. Grad., Department of Industrial Engineering, Mazandaran University of Science and Technology, Babol, Iran

² Assistant Professor, Department of Industrial Engineering, Mazandaran University of Science and Technology , Babol, Iran

چکیده [English]

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 meta-heuristic for combinatorial optimization problems. In this paper, artificial ant colony is developed. its successful application to the SBRP and finds optimal or close-to- optimal solutions of large instances of the SBRP in very limited computing times is shown.

کلیدواژه‌ها [English]

vehicle routing problem
School bus routing problem
ant colony optimization
Location

مراجع

-Arias-Rojas, J., Jiménez, J. and Torres, J. (2012) "Solving of school bus routing problem by ant colony optimization", Revista EIA, Vol.17, pp. 193-208.

-Bodin, L. D. and Berman, L. (1979) "Routing scheduling of school buses by computer", Transportation Science, Vol. 13, No. 2, pp. 113–129.

-Bowerman, R., Hall, B. and Calamai, P. (1995) "A multi-objective optimization approach to urban school bus routing: formulation and solution method", Transportation Research, An International Journal, Part A: Vol. 29, No. 2, pp. 107-123.

-Chapleau, L., Ferland, J. A. and Rousseau, J. M. (1985) "Clustering for routing in densely populated areas", European Journal of Operational Rearearch, 20. pp. 48-57

- Batta, Rajan, He, Qing (2015) "School bus routing with stochastic demand and duration constraints", Transportation Science, Vol. 36, No. 2, pp.199–217.

-Cortes, C. E., Matamala, M. and Contardo, C. (2011) "The pickup and delivery problem with transfers:
formulation and a branch-and-cut solution method", Operational Research, An European Journal, vol. 20, No. 3, pp. 711-724.

-Desrosiers, J., Ferland, J. A., Rousseau, J. M., Lapalme, G. and Chapleau, L. (1981) "An overview of school busing system", In Jaiswal, N.K. (Ed.), Scientific Management of Transport Systems. North- Holland, Amsterdam, pp. 235–243.

-Desrosiers, J., Soumis, F., Desrochers, M. and Sauve, M. (1986b) "Methods for routing with time windows", Operational Research, An European Journal, Vol. 23, No. 2, pp. 236-245.

-Dulac, G., Ferland, J. A. and Forgues, P. A. (1980) " School bus routes generator in urban surroundings" Computers and Operational Research, Vol. 7, No. 3, pp. 199-213.

-Houda, D., Bassem, J. H. and Habib, C. (2012) "Genetic algorithm with iterated local search for solving a location-routing problem", Journal of Expert Systems with Applications, Vol. 39, pp. 2865–2871.

-Jalel, E. and Rafaa, M. (2012) "Urban bus routing problem in the Tunisian case by the hybrid artificial ant colony algorithm", Swarm and Evolutionary Computation Journal. Vol. 2, PP. 25-24.

-Kumar, N., Kumar, M., Denis, D. M, Srivastava, S. K., Srivastva, O. S. (2014) "Geospatial school bus routing", The International Journal Of Engineering and Science (IJES), Vol.3, No.11, pp. 80-84.

-Laporte, G. and Semet, F. (2002) "Classical heuristics for the capacitated VRP", In Toth P and Vigo D, editors, The Vehicle Routing Problem., pp. 109-128.

-Laporte, G. (1992) "The vehicle routing problem: an overview of exact and approximate algorithms", Operations Research, An European Journal, Vol. 59, No. 3, pp. 345-358.

-Newton, R.aM. and Thomas, W.aH. (1969) "Design of school bus routes by computer", In Socio Economic Planning Sciences, Vol. 3, No. 1, pp. 75-85.

-Park, J. and Kim, B. I. (2010) "The school bus routing problem: a review" Operational Research, An European Journal, Vol. 202, No. 2, pp. 311–319.

-Pereira, F. B., Tavares, J., Machado, P. and Costa, E. (2002) GVR: a new genetic representation for the vehicle routing problem. Proc. 13th Irish conf. on Artificial Intelligence and cognitive Science, Limerick, Ireland, pp. 95-102.

-Perugia, A., Cordeau, J. F., Laporte, G. and Moccia, L. (2011)" Designing a home-to-work bus service in a metropolitan area", Transportation Research, Part B: Methodological, Vol. 10, pp. 1710–1726.

-Seung-Min, S. and Taeho, K., (2013) "Customeroriented school bus operations for childcare centers in Korea", Computers & Industrial Engineering, Vol. 66, No. 1, pp.116–124.

-Schittekat, P., Sevaux, M., Sörensen, K. and Springael, J. (2007)" A meta-heuristic for solving large instances of the School Bus Routing Problem.", The Seventh Meta-heuristics International Conference.

-Schittekat, P., Kinable, J., Sorensen, K. Sevaux, M. Spieksma, F. and Springael, J. (2013)" A metaheuristic for the school bus routing problem with bus stop selection." , European Journal of Operational Research, vol. 229, pp. 518–528.

-Spada, M., Bierlaire, M. and Lieblin, Th. (2005) "Decision-aiding methodology for the school bus routing and scheduling problem", In Transportation Science. Vol. 39, No. 4, pp. 477–490.

-Tavares, J., Pereira, F. B., Machado, P. and Costa, E. (2002) "GVR delivers it on time", Proceeding., 4th Asia- Pacific Conf. on Simulated - Evolution and Learning, Singapore. 2002, pp. 745-749

-Tavares, J., Pereira, F. B., Machado, P. and Costa, E. (2003) "On the influence of GVR in vehicle routing", Proceedings. ACM symposium on Applied Computing

– Evolutionary computation and optimization track, Florida, USA. pp. 753- 758.