روش جدید برای حل مسئله مسیریابی وسایل نقلیه با استفاده از الگوریتم تکاملی بهبودیافته

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

نویسندگان

1 استاد دانشگاه شهید باهنر کرمان، دکتری علوم کامپیوتر/هوش مصنوعی و نویسنده مسئول

2 دانشیار دانشگاه شهید باهنر کرمان، دکتری علوم کامپیوتر

3 دانشگاه و پژوهشگاه عالی دفاع ملی و تحقیقات راهبردی، پژوهشکده آماد، فناوری‌های دفاعی و پدافند غیرعامل، تهران، ایران

چکیده

امروزه مسئله مسیریابی وسایل نقلیه، یکی از موضوعات پرکاربرد در موضوعات صنعتی، نظامی و حتی امنیتی است که با هدف افزایش کارایی سیستم‌های حمل‌ونقل تعریف شده است. مسئله مسیریابی وسیله نقلیه با شرایط برداشت و تحویل هم‌زمان محموله ازجمله این مسائل می‌باشد. این مسئله ازنظر پیچیدگی محاسباتی در مجموعه مسائل سخت (NP-hard) قرار می‌گیرد؛ بنابراین یافتن بهترین پاسخ برای این مسائل در زمان اجرایی قابل‌قبول، امکان‌پذیر نیست. استفاده از الگوریتم‌های فرا ابتکاری ازجمله الگوریتم جست‌وجوی گرانشی یکی از روش‌هایی است که به‌وسیله آن‌ها می‌توان جواب‌هایی مناسب و در زمان محاسباتی قابل‌قبول به دست آورد. در این مقاله، با استفاده از این الگوریتم، روشی برای حل مسئله مسیریابی وسایل نقلیه با شرایط برداشت و تحویل هم‌زمان ارائه‌ شده است. با استفاده از این روش، علاوه بر محاسبه مسیرهای مناسب برای انجام خدمات، تعداد بهینه وسایل نقلیه برای فرایند خدماتی نیز تعیین می‌شود. برای ارزیابی کارایی روش پیشنهادی در این مقاله، روش پیشنهادی شبیه‌سازی شده و روی مجموعه داده‌ای استانداردی که برای این دسته از مسائل تعریف شده، اجرا شده است. نتایج تجربی و شبیه‌سازی نشان می‌دهد که این روش، با وجود سادگی در روش پیاده‌سازی و اجرا، دارای اثربخشی بهتری نسبت به الگوریتم‌ها و روش‌های موجود است.

کلیدواژه‌ها


Ai, T. J., & Kachitvichyanukul, V. (2009). A particle swarm optimization for the vehicle routing problem with simultaneous pickup and delivery. Computers & Operations Research, 36(5), 1693-1702.
Bianchessi, N., & Righini, G. (2007). Heuristic algorithms for the vehicle routing problem with simultaneous pick-up and delivery. Computers & Operations Research, 34(2), 578-594.
Christofides, N. (1976). The vehicle routing problem. Revue française d'automatique d'informatique et de recherche opérationnelle. Recherche opérationnelle, 10(1), 55-70.
Das, P., Behera, H., Jena, P., & Panigrahi, B. (2016). Multi-robot path planning in a dynamic environment using improved gravitational search algorithm. Journal of Electrical Systems and Information Technology, 3(2), 295-313.
Dell’Amico, M., Righini, G., & Salani, M. (2006). A branch-and-price approach to the vehicle routing problem with simultaneous distribution and collection. Transportation science, 40(2), 235-247.
Dethloff, J. (2001). Vehicle routing and reverse logistics: the vehicle routing problem with simultaneous delivery and pick-up. OR-Spektrum, 23(1), 79-96.
EBRAHIMI, M. S., RASHEDI, E., & JAVIDI, M. M. (2015). New functions for mass calculation in gravitational search algorithm.
González, B., Melin, P., Valdez, F., & Prado-Arechiga, G. (2018). Ensemble neural network optimization using a gravitational search algorithm with interval type-1 and type-2 fuzzy parameter adaptation in pattern recognition applications. In Fuzzy Logic Augmentation of Neural and Optimization Algorithms: Theoretical Aspects and Real Applications (pp. 17-27): Springer.
Gupta, A., & Saini, S. (2017). On solutions to vehicle routing problems using swarm optimization techniques: a review. In Advances in Computer and Computational Sciences (pp. 345-354): Springer.
Hatamlou, A. (2013). Black hole: A new heuristic optimization approach for data clustering. Information sciences, 222, 175-184.
Kato, A., Nakamoto, Y., Ishimori, T., & Togashi, K. (2016). Predictability of Posthepatectomy Liver Failure (PHLF) using 99mTc-GSA scintigraphy. Journal of Nuclear Medicine, 57(supplement 2), 644-644.
Kherabadi, H. A., Mood, S. E., & Javidi, M. M. (2017). Mutation: a new operator in gravitational search algorithm using fuzzy controller. Cybernetics and Information Technologies, 17(1), 72-86.
Mohanty, D. K. (2016). Gravitational search algorithm for economic optimization design of a shell and tube heat exchanger. Applied Thermal Engineering, 107, 184-193.
Montané, F. A. T., & Galvao, R. D. (2006). A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service. Computers & Operations Research, 33(3), 595-619.
Noel, M. M. (2012). A new gradient based particle swarm optimization algorithm for accurate computation of global minimum. Applied Soft Computing, 12(1), 353-359.
Rafsanjani, M. K., & Dowlatshahi, M. B. (2012). Using gravitational search algorithm for finding near-optimal base station location in two-tiered WSNs. International Journal of Machine Learning and Computing, 2(4), 377.
Rashedi, E., Nezamabadi-Pour, H., & Saryazdi, S. (2009). GSA: a gravitational search algorithm. Information sciences, 179(13), 2232-2248.
Rashedi, E., Nezamabadi-Pour, H., & Saryazdi, S. (2010). BGSA: binary gravitational search algorithm. Natural Computing, 9(3), 727-745.
Sabri, N. M., Puteh, M., & Mahmood, M. R. (2013). A review of gravitational search algorithm. Int. J. Advance. Soft Comput. Appl, 5(3), 1-39.
Shams, M., Rashedi, E., & Hakimi, A. (2015). Clustered-gravitational search algorithm and its application in parameter optimization of a low noise amplifier. Applied Mathematics and Computation, 258, 436-453.
Soleimanpour-Moghadam, M., Nezamabadi-Pour, H., & Farsangi, M. M. (2014). A quantum inspired gravitational search algorithm for numerical function optimization. Information sciences, 267, 83-100.
Tang, K., Yáo, X., Suganthan, P. N., MacNish, C., Chen, Y.-P., Chen, C.-M., & Yang, Z. (2007). Benchmark functions for the CEC’2008 special session and competition on large scale global optimization. Nature Inspired Computation and Applications Laboratory, USTC, China, 24.
Toth, P., & Vigo, D. (2002). The vehicle routing problem: SIAM.
Yao, B., Yu, B., Hu, P., Gao, J., & Zhang, M. (2016). An improved particle swarm optimization for carton heterogeneous vehicle routing problem with a collection depot. Annals of Operations Research, 242(2), 303-320.
Zhang, J., & Sanderson, A. C. (2009). JADE: adaptive differential evolution with optional external archive. IEEE Transactions on evolutionary computation, 13(5), 945-958.
Zhang, J. T., & Qiao, L. X. (2013). Optimization Mechanism Control Strategy of Vehicle Routing Problem Based on Improved PSO. Paper presented at the Advanced Materials Research.