حل مسئله چندین فروشنده دوره‌گرد با الگوریتم‌های رقابت استعماری و جریان آب در حالت عدم قطعیت تقاضا (مطالعه موردی: شرکت بازار گستر پگاه منطقه یک)

  • حمزه امين طهماسبي استاديار، گروه مهندسي صنايع، دانشکده فنی و مهندسی شرق، دانشگاه گيلان
  • امیر خلیلی کرباسدهی دانشجوی کارشناسی ارشد مهندسی صنایع، مؤسسه آموزش عالی غیردولتی کوشیار، رشت

چکیده

مسئله چندین فروشنده دوره‌گرد (MTSP) تعمیم‌یافته مسئله معروف فروشنده دوره‌گرد 4(TSP) است که هدف این مسئله تعیین حداقل هزینه سفر به n شهر می‌باشد، به‌گونه‌ای که فروشندگان سفر خود را از یک نقطه به‌عنوان مبدأ آغاز کرده و با عبور از تمام شهرها دوباره به نقطه مبدأ بازگردند. همچنین در مسیر خود باید هر شهر را دقیقاً یک‌مرتبه ملاقات کنند. در این مقاله که در شرکت پخش محصولات لبنی پگاه (بازار گستر) منطقه یک و برای حل مسئله واقعی ایشان انجام‌شده است، مدل فازی برای حل مسئله چندین فروشنده دوره‌گرد در شرایط وجود تقاضای غیرقطعی مشتریان، ارائه خواهد شد. تقسیم‌بندی شهر به مناطق کوچک‌تر و تخصیص هر یک از آنها به عاملین توزیع نیازمند صرف زمان زیادی است که نتیجه‌ای غیرقطعی نیز به دنبال خواهد داشت. در این پژوهش با استفاده از الگوریتم‌های فرا ابتکاری رقابت استعماری و جریان آب مسیرهای بهینه تعیین‌شد. درنتیجه محاسبات، جواب‌های به‌دست‌آمده از الگوریتم رقابت استعماری از کیفیت بهتر و جواب‌های به‌دست‌آمده از الگوریتم جریان آب از مدت‌زمان محاسباتی کمتر برخوردار بودند. بر این مبنا نحوه تخصیص و ترتیب خدمت‌دهی به مشتریان اصلاح و متعادل‌سازی گردید.

مراجع

Bektas Tolga., “The multiple traveling salesman problem: an overview of formulations and solution procedures”. Omega 34, 209 – 219, 2006.

Singh Amarbir., “a Review on Algorithms Used to Solve Multiple Travelling Salesman Problem”. International Research Journal of Engineering and Technology (IRJET) 3)4(, 598-603, 2016.

Bolaños Rubén Iván, Toro O Eliana M. and Granada E Mauricio., “A population-based algorithm for the multi travelling salesman problem”. International Journal of Industrial Engineering Computations 7, 245–256, 2016.

Soylu,Banu., “A general variable neighborhood search heuristic for multiple traveling salesmen problem”. Computers & Industrial Engineering 90, 390–401, 2015.

Wang Peng, CesarSanin, Edward Szczerbicki., “Evolutionary algorithm and decisional DNA for multiple travelling salesman problem”. Neurocomputing150, 50–57, 2015.

Kara Imdat, Deryaa Tusan., “Formulations for minimizing tour duration of the traveling salesman problem with time windows”. Procedia Economics and Finance 26, 1026 – 1034, 2015.

Ponraj Ranjana, Amalanathan George., “Optimizing multiple travelling salesman problem considering the road capacity”. Journal of Computer Science 10 (4), 680-688, 2014.

Larki Hossein, Yousefikhoshbakht Majid., “Solving the Multiple Traveling Salesman Problem by a Novel Metaheuristic Algorithm”. Journal of Optimization in Industrial Engineering 16, 55-6, 2014.

Yuan Shuai, Skinner Bradley, Huang Shoudong, Liu Dikai., “A new crossover approach for solving the multiple travelling salesmen problem using genetic algorithms”. European Journal of Operational Research 228, 72–82, 2013.

Jinhui Yang a, Xiaohu Shi a, Maurizio Marchese b, Yanchun Liang,v., “An ant colony optimization method for generalized TSP problem”. Progress in Natural Science 18, 1417–1422, 2008.

Carter, A. E., & Ragsdale, C. T., “A new approach to solving the multiple traveling salesperson problem using genetic algorithms”. European Journal of Operational Research, 175, 246-257, 2006.

Song C., Lee K., Lee W.D., “Extended simulated annealing for augmented TSP and multi-salesmen TSP”. Proceedings of the international joint conference on neural networks, vol. 3, 2340–43, 2003.

Tang L, Liu J, Rong A, Yang Z., “A multiple traveling salesman problem model for hot rolling scheduling in Shangai Baoshan Iron & Steel Complex”. European Journal of Operational Research; 124, 267–82, 2000.

Zhang T, Gruver WA, Smith MH., “Team scheduling by genetic search”. Proceedings of the second international conference on intelligent processing and manufacturing of materials, vol. 2, 839–44, 1999.

Fogel DB., “A parallel processing approach to a multiple traveling salesman problem using evolutionary programming”. In: Proceedings of the fourth annual symposium on parallel processing. Fullerton, CA, 318–26, 1990.

Potvin J, Lapalme G, Rousseau J., “A generalized k-opt exchange procedure for the MTSP”. INFOR; 27(4), 474–81, 1989.

Russell RA., “An effective heuristic for the m-tour traveling salesman problem with some side conditions”. Operations Research; 25(3), 517–24, 1977.

]18[ خیرمند، مهدی. راحتی، امین. "حل مسئله فروشنده دوره‌گرد با استفاده از الگوریتم کلونی زنبورعسل مصنوعی گسسته". اولین کنفرانس ملی ریاضیات صنعتی تبریز، 7 خرداد 1393.

]19[ یوسفی خوشبخت، مجید. هاشمی، سید ناصر. "حل مسئله چندین فروشنده دوره‌گرد به‌وسیله الگوریتم ICA". مهندسی صنایع و مدیریت شریف، دوره 1-30، شماره 1/1، صفحه 121-130، 1393.

]20[ توکلی پور، محمدمهدی. جعفری نسب، سید احسان. "حل مسئله مسیریابی وسایل حمل‌ونقل با ظرفیت محدود به‌وسیله الگوریتم کلونی زنبورهای مصنوعی". دوازدهمین کنفرانس سیستم‌های هوشمند ایران، صفحه 15-17، بهمن‌ماه 1392.

]21[ رجبی، محمدرضا. منصوریان، علی. طالعی، محمد. علی‌محمدی سراب، عباس. "ارائه روشی ابتکاری برای حل مسئله مسیریابی فروشنده دوره‌گرد؛ سنجش ‌از دور و GIS ایران". سال چهارم، شماره چهارم، زمستان 1391.

]22[ یوسفی خوشبخت، مجید. صدیق¬پور، محمد. "الگوریتم نمونه اصلاحی مورچگان برای حل مسئله چندین فروشنده دوره‌گرد". مجله تحقیق در عملیات و کاربردهای آن، سال هشتم، (پیاپی 30)، صفحه 83-96، پاییز 1390.

]23[ زارعی، باقر. میبدی، محمدرضا. "یک روش ترکیبی برای حل مسئله فروشنده دوره‌گرد". سومین کنفرانس فناوری اطلاعات و دانش؛ صفحه 6-8، آذرماه 1386.

]24[ صباغ، محمد سعید. امیری، علیرضا. "روش ابتکاری ساخت و بهبود تور مسئله فروشنده دوره‌گرد نامتقارن". نشریه دانشکده فنی، جلد 40، شماره 4، صفحه 539-551، مهرماه 1385.

]25[ سعادتمند طرزجان، مهدی. اکبرزاده توتونچی، محمدرضا. خادمی، مرتضی. "یک شبکه عصبی جدید با ساختارهای سازنده - ترکیبی برای حل مسئله‌های فروشنده دوره‌گرد و کوتاه‌ترین مسیر با تعداد شهر مشخص". نشریه دانشکده فنی، جلد 39، شماره 4، صفحه 469-487، آبان ماه 1384.

]26[ حجازی، سید رضا. سلطانی، رضا. "ارائه الگوریتم ترکیبی مورچگان و ژنتیک برای حل مسئله فروشنده دوره‌گرد". چهارمین کنفرانس ملی مهندسی صنایع، تهران، انجمن مهندسی صنایع ایران، دانشگاه تربیت مدرس، 1384.

]27[ سعادتمند طرزجان، مهدی. "یک شبکه عصبی فازی ژنتیکی جدید برای حل مسئله فروشنده دوره‌گرد". دوازدهمین کنفرانس مهندسی برق ایران؛ صفحه 22-24، اردیبهشت 1383.

]28[ سعادتمند، مهدی. اکبزاده توتونچی، محمد. خادمی، مرتضی. "ارائه یک شبکه عصبی ترکیبی برای حل مسئله فروشنده دوره‌گرد". نهمین کنفرانس مهندسی برق ایران، اردیبهشت 1380.

]29[ مؤمنی، منصور. "مباحث نوین تحقیق در عملیات". 352 صفحه، 1391.

Laporte G, Nobert Y., “A cutting planes algorithm for the m-salesmen problem”. Journal of the Operational Research Society; 31, 1017–23, 1980.

Gavish B, Graves SC., “The traveling salesman problem and related problems”. working paper GR-078-78, Operations Research Center, Massachusetts Institute of Technology, 1978.

Kara I, Bektas T., “Integer programming formulations of multiple salesman problems and its variations”. 2004, submitted for publication.

Yousefi khoshbakht, Majid, Sedighpour, Mohammad., “New Imperialist Competitive Algorithm to solve the travelling salesman problem”. International Journal of Computer Mathematics, Volume 90, Issue 7, 1495-1505, 2013.

Srour, Ayman, Othman, Zulaiha Ali, and Hamdan Abdul Razak., “A Water Flow-Like Algorithm for the Travelling Salesman Problem”. Advances in Computer Engineering, Volume 2014, Article ID 436312, 14, 2014.

]35[ جلالی مهر، میلاد. طاهری، مهیار. مؤمنی، حسین. "استفاده از تکنیک جریان آب در تست تصادفی سیستم‌های پایگاه داده‌ای". اولین کنفرانس ملی دانش‌پژوهان کامپیوتر و فناوری اطلاعات، تبریز، دانشگاه تبریز، صفحه 207-214، ۱۳۹۰.

چاپ شده
2018-06-18