تحلیل و ارزیابی روش‌های فراابتکاری، ابتکاری و قطعی در ارایه مسیر بهینه برای شبکه‌های کوچک، متوسط و بزرگ

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

نویسندگان

1 استادیار، دانشکده عمران، آب و محیط‌زیست، دانشگاه شهید بهشتی، تهران، ایران

2 دانش‌آموخته کارشناسی ارشد، دانشگاه آزاد اسلامی، تهران، ایران

10.22034/road.2021.293402.1964

چکیده

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

کلیدواژه‌ها


-Bin, Yu; Zhong-Zhen, Yang; (2010), “An ant colony optimization model: The period vehicle routing problem with time windows”, Transportation Research Part E.
-Bin, Yu; Zhong-Zhen, Yang; Baozhen, Yao; (2009), “An improved ant colony optimization for vehicle routing problem”, European Journal of Operational Research 196, pp.171–176.
-Davies, C., Lingras, P., (2003), “Discrete Optimization, Genetic algorithms for rerouting shortest paths in dynamic and stochastic networks”, European Journal of Operational Research 144, pp. 27–38.
-Dorigo, M., and Blum, C., (2005), “Ant colony optimization theory: A survey”, Theoretical Computer Science 344,  pp. 243 – 278.
-Dorigo, M., Stutzle, T., 2004; Ant Colony Optimization; the MIT Press, Cambridge, Massachusetts, London, England, ISBN 0-262-04219-3.
-Gajpal, Yuvraj; Abad, Prakash; )2009(, “An ant colony system (ACS) for vehicle routing problem with simultaneous delivery and pickup”, Computers &Operations Research 36; pp.3215-3223.
-Gao, S., Wang, Y., Cheng, J., Inazumi, Y. and Tang, Z., (2016), “Ant colony optimization with clustering for solving the dynamic location routing problem”, Applied Mathematics and Computation, 285, pp.149-173.
-Gao, Yu., (2011), “Shortest path problem with uncertain arc lengths”, Computers and Mathematics with Applications 62,
pp.2591–2600.
-Ghezavati, V.R. and Beigi, M., (2016), “Solving a bi-objective mathematical model for location-routing problem with time windows in multi-echelon reverse logistics using metaheuristic procedure”, Journal of Industrial Engineering International, 12(4), pp.469-483.
-Ghoseiri, Keivan; Nadjari, Behnam, (2010), “An ant colony optimization algorithm for the bi-objective shortest path problem”, Applied Soft Computing 10, pp.1237–1246.
-Ginantra, N.L.W.S.R., Taufiqurrahman, T., Bhawika, G.W., Iswara, I.B.A.I. and Wanto, A., (2019), “Determination of the Shortest Route towards the Tourist Destination Area Using the Ant Algorithma”, IOP Publishing, In Journal of Physics: Conference Series, Vol. 1339, No. 1, pp. 012038.
-Ginantra, N.L.W.S.R., Taufiqurrahman, T., Bhawika, G.W., Iswara, I.B.A.I. and Wanto, A., (2019), “Determination of the Shortest Route towards the Tourist Destination Area Using the Ant Algorithma”, IOP Publishing, In Journal of Physics: Conference Series, Vol. 1339, No. 1, pp. 012038.
-Ginantra, N.L.W.S.R., Taufiqurrahman, T., Bhawika, G.W., Iswara, I.B.A.I. and Wanto, A., (2019), “December. Determination of the Shortest Route towards the Tourist Destination Area Using the Ant Algorithma”, IOP Publishing, In Journal of Physics, Conference Series, Vol. 1339, No. 1, pp. 012038.
-Ji, X., (2005), “Models and algorithm for stochastic shortest path problem”, Applied Mathematics and Computation 170, pp.503–514.
-Lee, Chou-Yuan; Lee, Zne-Jung; Lin, Shih-Wei; Ying, Kuo-Ching, (2010), “An enhanced ant colony optimization (EACO) applied to capacitated vehicle routing problem”,
Appl Intell 32, pp.88–95.
-Machuca, E.; Mandow, L.; J.L. Pérez de la Cruz; A. Ruiz-Sepulveda, (2011), “A comparison of heuristic best-first algorithms for bicriterion shortest path problems”, European Journal of Operational Research.
-Mahpour, A., Amiri, A.M., Deldar, M., Saffarzadeh, M. and Nazifi, A., (2018),
“A heuristic method to determine traffic bottlenecks based on ant colony, A case study of Iran, Case Studies on Transport Policy, 6(4),
pp.716-721.
-Mahpour, A., Mamdoohi, A. and Hakimelahi, A., (2020), “A heuristic technique for traffic assignment with variable step size and number of iterations”, Transportation Research Procedia, 48, pp.2569-2579.
-Mahpour, A., Nazifi, A. and Amiri, A.M., 2021. Development of Optimization Model to Reduce Unloading and Loading Time at Berth in Container Ports. Iranian Journal of Science and Technology, Transactions of Civil Engineering, pp.1-10.
-Min, F., Zhang, Z.H. and Dong, J., (2018), “Ant colony optimization with partial-complete searching for attribute reduction”, Journal of Computational Science, 25, pp.170-182.
-Qureshi, A. G., Taniguchi, E., Yamada, T., (2010), “Exact solution for the vehicle routing problem with semi soft time windows and its application, Procedia Social and Behavioral Sciences 2, pp.5931–5943.
-Vidal, T., Crainic, T.G., Gendreau, M. and Prins, C., (2013), “Heuristics for multi-attribute vehicle routing problems, A survey and synthesis”, European Journal of Operational Research, 231(1), pp.1- 21.
-Vidal, T., Crainic, T.G., Gendreau, M. and Prins, C., (2014), “A unified solution framework for multi attribute vehicle routing problems”, European Journal of Operational Research, 234(3), pp.658-673.
-Wanto, A., Zarlis, M. and Hartama, D., (2017), “Analysis of Artificial Neural Network Back propagation Using Conjugate Gradient Fletcher Reeves in the Predicting Process”, IOP Publishing, In Journal of Physics, Conference Series,Vol. 930, No. 1, pp. 012018.
-Wu, J., Chen, B., Zhang, K., Zhou, J. and Miao, L., (2018), “Ant pheromone route guidance strategy in intelligent transportation systems”, Physica A: Statistical Mechanics and its Applications, 503, pp.591-603.
-Yang, X., Dong, H. and Yao, X., (2017), “Passenger distribution modeling at the subway platform based on ant colony optimization algorithm”, Simulation Modeling Practice and Theory, 77, pp.228- 244.