دوره 18، شماره 4 - ( 12-1400 )                   جلد 18 شماره 4 صفحات 36-23 | برگشت به فهرست نسخه ها

‎ 10.52547/jsdp.18.4.23

XML English Abstract Print

ارائه الگوریتم جست‌وجوی گرانشی مقید و حل مسأله مسیریابی وسایل نقلیه
سپهر ابراهیمی مود ، محمد مسعود جاویدی* ، محمدرضا خسروی
دانشگاه شهیدباهنر کرمان
چکیده:   (1701 مشاهده)
امروزه مسأله مسیریابی وسایل نقلیه، یکی از موضوعات پرکاربرد در موضوعات صنعتی، نظامی و حتی امنیتی است و برای افزایش کارایی و بهره‌وری سامانه‌های حمل و نقل تعریف شده است. مسأله مسیریابی وسیله نقیله با شرایط برداشت و تحویل هم‌زمان محموله از جمله این مسائل است. این مسأله از نظر پیچیدگی محاسباتی در مجموعه مسائل سخت (NP-hard) قرار می‌گیرد؛ بنابراین محاسبه بهترین پاسخ برای این مسأله، در زمان محاسباتی نمایی انجام خواهد شد و در مسائل اجرایی قابل استفاده نخواهد بود. استفاده از الگوریتم‌های فراابتکاری یکی از روش‌هایی است که به‌وسیله آنها می‌توان جواب‌هایی مناسب و در زمان محاسباتی قابل قبول به‌دست آورد. در روش‌های موجود، قیود موجود در مسأله، با استفاده از روش جریمه به تابع هدف مسأله اضافه شده و مسأله بهینه‌سازی تک‌هدفه تعریف می‌شود. ضمن این‌که تعداد بهینه وسایل نقلیه مورد نیاز برای حل مسأله در نظر گرفته نمی‌شود. در این مقاله، الگوریتم جست‌وجوی گرانشی بهبود‌یافته برای حل مسائل مقید معرفی شده است. همچنین به‌منظور کنترل قابلیت‌های الگوریتم نظیر کاوش و بهره‌وری از یک کنترلر فازی برای تعیین پارامترهای موجود در الگوریتم استفاده شده، سپس، با استفاده از این الگوریتم، روشی برای حل مسأله مسیریابی وسایل نقلیه با شرایط برداشت و تحویل هم‌زمان ارائه‌ شده است. با استفاده از این روش، علاوه‌بر محاسبه مسیرهای مناسب برای انجام خدمات، تعداد بهینه وسایل نقلیه برای فرآیند خدماتی نیز تعیین می‌شود. برای ارزیابی کارایی روش پیشنهادی در این مقاله، روش پیشنهادی شبیه‌سازی شده و روی مجموعه‌داده استانداردی که برای این دسته از مسائل تعریف شده، اجرا شده است. نتایج تجربی و شبیه‌سازی نشان می‌دهد که این روش، با وجود سادگی در روش پیاده‌سازی و اجرا، دارای کارایی بهتری نسبت به الگوریتم‌ها و روش‌های بررسی شده است.
شماره‌ی مقاله: 2
واژه‌های کلیدی: مسیریابی وسایل نقلیه، برداشت و تحویل هم‌زمان، الگوریتم‌های فراابتکاری، الگوریتم جست‌وجوی گرانشی مقید
متن کامل [PDF 712 kb]   (600 دریافت)    
نوع مطالعه: پژوهشي | موضوع مقاله: مقالات گروه امنیت اطلاعات
دریافت: 1398/2/14 | پذیرش: 1399/5/28 | انتشار: 1401/1/1 | انتشار الکترونیک: 1401/1/1
فهرست منابع
1. [1] N. Christofides, ''The vehicle routing problem'', Revue française d'automatique, informatique, recherche opérationnelle,vol. 10(V1), pp. 55-70, 1976. [DOI:10.1051/ro/197610V100551]
2. [2] P. Toth, D. Vigo, The vehicle routing problem, SIAM, 2002. [DOI:10.1137/1.9780898718515]
3. [3] T.J. Ai, V. Kachitvichyanukul, ''A particle swarm optimization for the vehicle routing problem with simultaneous pickup and delivery'', Computers & Operations Research, vol. 36(5), pp. 1693-1702, 2009. [DOI:10.1016/j.cor.2008.04.003]
4. [4] E. Rashedi, H. Nezamabadi-Pour, S. Saryazdi, ''GSA: a gravitational search algorithm'', Information sciences, vol.179(13), pp. 2232-2248, 2009. [DOI:10.1016/j.ins.2009.03.004]
5. [5] E. Rashedi, H. Nezamabadi-Pour, S. Saryazdi, ''BGSA: binary gravitational search algorithm'', Natural Computing, vol.9(3), pp. 727-74, 2010. [DOI:10.1007/s11047-009-9175-3]
6. [6] S.E. Mood, M.M. Javidi, ''Energy-efficient clustering method for wireless sensor networks using modified gravitational search algorithm,'' Evolving Systems, pp. 1-13, 2019.
7. [7] B. González, P. Melin, F. Valdez, G. Prado-Arechiga, ''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, Springer, 2018, pp. 17-27. [DOI:10.1007/978-3-319-71008-2_2]
8. [8] کریمی عباس، حسینی لیلا سادات. الگوریتم بهینه تقسیم‌بندی تصاویر میکروسکوپی خون برای تشخیص سلول‌های لوسمی حاد لنفوبلاست با استفاده از الگوریتم FCM و بهینه‌سازی ژنتیک. پردازش علائم و داده‌ها. ۱۳۹۷; ۱۵ (۲) :۵۴-۴۵
9. [8] A. Karimi , L.S. Hoseini , ''An Optimal Algorithm for Dividing Microscopic Images of Blood for the Diagnosis of Acute Pulmonary Lymphoblastic Cell Using the FCM Algorithm and Genetic Optimization'', JSDP, vol.15 (2),pp. 45-54, 2018. URL: http://jsdp.rcisp.ac.ir/article-1-567-fa.html [DOI:10.29252/jsdp.15.2.45]
10. [9] واقفی مهسا، جمشیدی فاطمه. انتخاب ویژگی برای تشخیص آریتمی های قلبی با استفاده از بهینه‌سازی ازدحام ذرات باینری چند هدفه. پردازش علائم و داده‌ها. ۱۴۰۰; ۱۸ (۲) :۱۷۶-۱۶۳
11. [9] M. Vaghefi, F. Jamshidi , ''Features selection for cardiac arrhythmia diagnosis using multiple objective binary particle swarm optimization'', JSDP, vol. 18 (2), pp.163-176, 2021. URL: http://jsdp.rcisp.ac.ir/article-1-972-fa.html
12. [10] کریمی عباس، حسینی لیلا سادات. الگوریتم بهینه تقسیم‌بندی تصاویر میکروسکوپی خون برای تشخیص سلول‌های لوسمی حاد لنفوبلاست با استفاده از الگوریتم FCM و بهینه‌سازی ژنتیک. پردازش علائم و داده‌ها. ۱۳۹۷; ۱۵ (۲) :۵۴-۴۵
13. [10] A. Karimi, L.S. Hoseini , ''An Optimal Algorithm for Dividing Microscopic Images of Blood for the Diagnosis of Acute Pulmonary Lymphoblastic Cell Using the FCM Algorithm and Genetic Optimization'', JSDP, vol. 15 (2), pp. 45-54, 2018. URL: http://jsdp.rcisp.ac.ir/article-1-567-fa.html [DOI:10.29252/jsdp.15.2.45]
14. [11] S. Mood, E. Rasshedi, M. Javidi, ''New functions for mass caculation in gravitational search algorithm,'' Journal of Computing and Security, 2(3), 2016.
15. [12] H.A. Kherabadi, S.E. Mood, M.M. Javidi, ''Mutation: a new operator in gravitational search algorithm using fuzzy controller'', Cybernetics and Information Technologies, vol. 17(1), pp. 72-86, 2017. [DOI:10.1515/cait-2017-0006]
16. [13] M. Soleimanpour-Moghadam, H. Nezamabadi-Pour, M.M. Farsangi, ''A quantum inspired gravitational search algorithm for numerical function optimization,'' Information Sciences, pp. 83-100, 2014. [DOI:10.1016/j.ins.2013.09.006]
17. [14] A. Hatamlou, ''Black hole: A new heuristic optimization approach for data clustering'', Information sciences, vol. 222, pp. 175-184, 2013. [DOI:10.1016/j.ins.2012.08.023]
18. [15] M. Shams, E. Rashedi, A. Hakimi, ''Clustered-gravitational search algorithm and its application in parameter optimization of a low noise amplifier,'' Applied Mathematics and Computation, vol.258, pp. 436-453, 2015. [DOI:10.1016/j.amc.2015.02.020]
19. [16] E. Rashedi, E. Rashedi, H. Nezamabadi-pour, ''A comprehensive survey on gravitational search algorithm'', Swarm and evolutionary computation, vol. 41, pp.141-158, 2018. [DOI:10.1016/j.swevo.2018.02.018]
20. [17] J.T. Zhang, L.X. Qiao, ''Optimization Mechanism Control Strategy of Vehicle Routing Problem Based on Improved PSO'', Advanced Materials Research, Trans Tech Publ, pp. 130-136, 2013. [DOI:10.4028/www.scientific.net/AMR.681.130]
21. [18] B. Yao, B. Yu, P. Hu, J. Gao, M. Zhang, ''An improved particle swarm optimization for carton heterogeneous vehicle routing problem with a collection depot'', Annals of Operations Research, vol.242(2), pp.303-320, 2016. [DOI:10.1007/s10479-015-1792-x]
22. [19] M. Avci, S. Topaloglu, ''A hybrid metaheuristic algorithm for heterogeneous vehicle routing problem with simultaneous pickup and delivery'', Expert Systems with Applications, vol.53, pp. 160-17,12016. [DOI:10.1016/j.eswa.2016.01.038]
23. [20] A. Gupta, S. Saini, ''On Solutions to Vehicle Routing Problems Using Swarm Optimization Techniques: A Review, '' in: Advances in Computer and Computational Sciences, Springer, pp. 345-354, 2017. [DOI:10.1007/978-981-10-3770-2_32]
24. [21] E. Mezura-Montes, ''C.A.C. Coello, Constraint-handling in nature-inspired numerical optimization: past, present and future,'' Swarm and Evolutionary Computation, vol.1(4), pp. 173-194, 2011. [DOI:10.1016/j.swevo.2011.10.001]
25. [22] D. Orvosh, L. Davis, ''Using a genetic algorithm to optimize problems with feasibility constraints,'' in: Proceedings of the First IEEE Conference on Evolutionary Computation. IEEE World Congress on Computational Intelligence, IEEE, pp. 548-553, 1994.
26. [23] R. de Paula Garcia, B.S.L.P. de Lima, A.C. de Castro Lemonge, B.P. Jacob, ''A rank-based constraint handling technique for engineering design optimization problems solved by genetic algorithms,'' Computers & Structures, vol. 187, pp. 77-87, 2017. [DOI:10.1016/j.compstruc.2017.03.023]
27. [24] M. Dell'Amico, G. Righini, M. Salani, ''A branch-and-price approach to the vehicle routing problem with simultaneous distribution and collection,'' Transportation science, vol. 40(2), pp. 235-247, 2006. [DOI:10.1287/trsc.1050.0118]
28. [25] J. Dethloff, ''Vehicle routing and reverse logistics: the vehicle routing problem with simultaneous delivery and pick-up,'' OR-Spektrum, vol.23(1), pp. 79-96, 2001. [DOI:10.1007/PL00013346]
29. [26] F.A.T. Montané, R.D. Galvao, ''A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service'', Computers & Operations Research, vol.33(3), pp.595-619, 2006. [DOI:10.1016/j.cor.2004.07.009]
30. [27] N. Bianchessi, G. Righini, ''Heuristic algorithms for the vehicle routing problem with simultaneous pick-up and delivery'', Computers & Operations Research, vol.34(2) pp.578-594, 2007. [DOI:10.1016/j.cor.2005.03.014]
بازنشر اطلاعات
Creative Commons License این مقاله تحت شرایط Creative Commons Attribution-NonCommercial 4.0 International License قابل بازنشر است.