توسعه الگوریتم غذایابی کندوی زنبور عسل برای حل مسئله مسیریابی خودرو

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

چکیده

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

کلیدواژه‌ها


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

Bee Hive`s Foraging Algorithm for Vehicle Routing Problem

چکیده [English]

Finding the shortest path that a vehicle can go through its all points with static coordinate, and finally back to the initial point is one kind of vehicle routing problem. This problem is called Traveling Salesman Problem, which has many applications in transportation engineering and other science. Deterministic methods (mathematical) have been shown unsuitable for such complicated problems. Therefore, in this paper it has been tried to solve this problem by modifying Bee Colony Algorithm, one of the recent optimization algorithms.  Results demonstrate the proposed Bee Colony Algorithm has suitable ability to solve the problem, compared to other optimization methods.

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

  • Transportation engineering
  • vehicle routing problem
  • Bee colony algorithm
- Baykasoùlu, A., Özbakır, . L. and Tapkan, P.  (2007) “Artificial bee colony algorithm and its application to generalized assignment problem”, Vienna, Austria: Itech Education and Publishing,
- Chatterjee, S., Carrera, C. and Lynch, L. A. (1996) “Genetic algorithms and traveling salesman problems”, European Journal of Operational Research, Issue 93, pp. 490-510.
- Abu Zitar, R. E. and  Shehabat, E. (2007) “Genetic algorithm with solution approach for traveling salesman problem”, Neural Network World, 07(5), pp. 497-504.
- Araque, G., J., Kudva, G., Morin, T. and Pekny, J. (1994) “A branch-and-cut algorithm for vehicle routing problems”, Annals of Operations Research, Issue 50, pp. 37-59.
- Ascheuer, N., Junger, M. and Reinelt, G. (2000) “A branch and cut algorithm for the asymmetric traveling salesman problem with precedence constraints”,  Computational optimization and applications, Issue 17, pp. 61–84.
- Barbarosoglu, G. and Ozgur, D. (1999) “A tabu search algorithm for the vehicle routing problem”. Computers and Operations Research, Issue 26, pp. 255-270.
- Bel, J. E. and McMullen, P. R. (2004) “Ant colony optimization techniques for the vehicle routing problem”, Advanced Engineering Informatics, Issue 18, pp. 41-48.
- Bhagade, A. S. and Puranik, P. V. (2012) “Artificial bee colony (ABC) algorithm for vehicle routing optimization problem”, International Journal of Soft Computing and Engineering (IJSCE), 2(2).
- Chiang, W.-C. and Russell, R. A. (1996) “Simulated annealing metaheuristics for the vehicle routing problem with time windows”, Annals of Operations Research, Issue 63, pp. 3-27.
- Fiechter, C. (1994) “A parallel tabu search algorithm for large traveling salesman problems”, Discrete Applied Mathematics, Issue 51, pp. 243-267.
- Fischetti, M., Salazar Gonzalez, J. J. and Toth, P. (1997) “A branch-and-cut algorithm for the symmetric generalized traveling salesman problem”, Operations Research, 3(45), pp. 378-394.
- Geng, X. (2011) “Solving the traveling salesman problem based on an adaptive simulated annealing algorithm with greedy search”, Applied Soft Computing, Issue 11, pp. 3680–3689.
- Hasegawa, M., Ikeguchi, T. and Aihara, K. (2002) “Solving large scale traveling salesman problems by chaotic neurodynamics”, Neural Networks, Issue 15, pp. 271-283.
- Jemai, J. and Mellouli, K. (2008) “A neural-tabu search heuristic for the real time vehicle routing problem”. J Math Model Algor , Issue 7, pp. 161-176.
- Ji, P. and Wu, Y. (2011) “An improved artificial bee colony algorithm for the capacitated vehicle routing problem with time-dependent travel times”, The Tenth International Symposium on Operations Research and Its Applications (ISORA 2011), pp. 75-82.
- Li, M., Yi, Z. and Zhu, M. (2009) “Solving TSP by using Lotka–Volterra neural networks”, Neurocomputing, Issue 72, pp. 3873–3880.
- Ling, C., Hai-Ying, S. and Shu, W. (2012) “A parallel ant colony algorithm on massively parallel processors and its convergence analysis for the travelling salesman problem”, Information Sciences, Issue 199, pp. 31-42.
- Lucic, P. and Teodorovic, D. (2003) “Computing with bees: Attacking complex transportation engineering problems”, International Journal on Artificial Intelligence Tools, 3(12), pp. 375-394.
- Ma, J. , Yang, Tao, Hou, Zeng-Gunag, Tan, Min and Liu, Derong (2008) “Neurodynamic programming: a case study of the traveling salesman problem”, Neural Comput & Applic, Issue 17, pp. 347-355.
- Malek, M., Guruswamy, M., Pandya, M. and Owens, H. (1989) “Serial and parallel simulated annealing and tabu search algorithms for the traveling salesman problem”. Annals of Operations Research, Issue 21, pp. 59-84.
- Manfrin, M., Mauro, B., Stutzle, T. and Dorigo, M. (2006) “Parallel ant colony optimization for the traveling salesman problem”. ANTS 2006,LNCS, Volume 4150, pp. 224-234.
- Masutti, T. A. and Castro, L. N. D. (2009) “A self-organizing neural network using ideas from the immune system to solve the traveling salesman problem”, Information Sciences, Issue 179, pp. 1454–1468.
- Moon, C., Kim, J., Choi, G. and Seo, Y. (2002) “An efficient genetic algorithm for the traveling salesman problem with precedence constraints”. European Journal of Operational Research, Issue 140, pp. 606-617.
- Padberg, M. and Rinaldi, G. (1991) “A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman”. S.LA.M. Review, Issue 33, pp. 60-100.
- Potvin, J.-Y. (1996) “Genetic algorithms for the traveling salesman problem”, Annals of Operations Research, Issue 63, pp. 339-370.
- Wong, L.-P. and Chong, C. S. (2009) ”An efficient bee colony optimization algorithm for traveling salesman problem using frequency-based pruning”, IEEE, pp. 775-783.
- Yonezawa, Y. and Kikuchi, T. (1996) “Ecological algorithm for optimal ordering used by collective honey bee behavior”, 7th International Symposium on Micro Machine and Human, pp. 249-256.