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

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

نویسندگان

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

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

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

چکیده

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

کلیدواژه‌ها


-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.