ارائه مدل مسیریابی وسایل نقلیه امدادی در شبکه‌های کوچک و متوسط

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

نویسندگان

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

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

3 دانشکده مهندسی صنایع، واحد تهران جنوب، عضو هیئت علمی دانشگاه آزاد اسلامی

10.22119/jte.2020.92670

چکیده

در پژوهش حاضر، هدف، طراحی یک مسئله مسیریابی خودروهای امدادی بر روی شبکه‌های کوچک و متوسط و حل این مسئله با استفاده از الگوریتم پیشنهادی است. تفاوت اساسی مسیریابی خودروهای امدادی با سایر مسائل مسیریابی مطرح شده در مرور ادبیات، استفاده از فاصله برروی شبکه به جای فاصله هوایی، محدودیت زمان لازم برای حل مسئله، تک‌ظرفیتی بودن وسایل نقلیه و عدم اجبار بازگشت وسیله نقلیه به مبداء اولیه است. وروردی‌های مسئله شبکه حمل و نقل، تعداد و محل وسایل نقلیه، بیمارستان‌‌ها و درخواست‌‌های امدارسانی، تابع هدف مسئله، کمینه کردن مجموع زمان سفر کل وسایل نقلیه به علاوه زمانی است که آخرین درخواست پاسخ داده می‌شود و خروجی مسئله ترتیب پاسخ‌گویی به درخواست‌ها و تخصیص وسایل نقلیه و بیمارستان به هر درخواست است. 138مثال تصادفی بر روی شبکه کوچک با 7گره و 75 مثال بر روی شبکه متوسط سوفالز با 24 گره و 76 کمان تولید شد. برای کاهش زمان حل مسئله، ابتدا با ثابت نگه داشتن ترتیب پاسخ‌گویی به درخواست‌ها، تعداد پاسخ‌های امکان‌پذیر مسئله کاهش یافت. برای این منظور، سه سناریوی متفاوت ترتیب پاسخ‌گویی به درخواست‌ها بر روی مثال‌های تولید شده بررسی شد. بر اساس نتایج، مرتب کردن درخواست‌ها بر اساس فاصله از نزدیک‌ترین وسیله نقلیه پاسخ‌های بهتری داشت. در گام بعدی، یک الگوریتم پیشنهادی ارائه شد. نتایج نشان داد که الگوریتم پیشنهادی قادر است در کمتر از 5ثانیه به پاسخ نهایی دست یابد که برای برنامه‌ریزی درخواست‌های امدادی، مناسب است. حل دقیق مسئله بسته به ابعاد آن تا 1770 ثانیه زمان نیاز دارد.  اختلاف میان پاسخ تولید شده توسط الگوریتم پیشنهادی و پاسخ دقیق مسئله در بیش از 80درصد مثال‌های شبکه کوچک و بیش از 50درصد مثال‌های شبکه متوسط، کمتر از 10درصد و در بیش از 94درصد مثال‌های شبکه کوچک و بیش از 89درصد مثال‌های شبکه متوسط، کمتر از 30درصد است. در مجموع، نتایج نشان می‌دهد که الگوریتم ابتکاری ارائه شده از نظر زمان حل و کیفیت پاسخ دارای عملکرد مناسبی در شبکه‌های کوچک است

کلیدواژه‌ها


- اعتباری، ف. و دشتیان، ز. (1397) “مدلسازی مسئله مسیریابی-موجودی سبز با در نظر گرفتن وسائل نقلیه هیبریدی و حل آن توسط الگوریتم جستجوی همسایگی بزرگ”، فصلنامه مهندسی حمل و نقل، انتشار آنلاین
- معماری، پ.، پرتویی، م.، جولای، ف. و توکلی مقدم، ر. (1396) «توسعه مدل مکان‌یابی- مسیریابی با در نظر گرفتن رضایت مشتری و دریافت و تحویل همزمان»، فصلنامه مهندسی حمل و نقل، انتشار آنلاین
- صبوحی، ف. و بزرگی امیری، الف. (1396) «مسیریابی و زمان‌بندی وسایل حمل و نقل برای توزیع کمک‌های امدادی با در نظر گرفتن تحویل جزئی و انبار چندگانه»، فصلنامه مهندسی حمل و نقل، دوره 9، شماره 1
- Caric, T. and Gold, H. (2008) “Vehicle routing problem”, Vienna: I-Tech Education and Publishing KG
- Cordeau, J. F. and Laporte, G. (2003) “A tabu search heuristic for the static multi-vehicle dial-a-ride problem”, Transportation Research Part B, *Vol. 37, No. 6, pp. 579-594
- Cordeau, J. F. and Laporte, G. (2007) “The dial-a-ride problem: models and algorithms”, Annals of Operations Research, Vol. 153, No. 1, pp. 29-46
- Cimen, M. and Soysal, M. (2017) “Time-dependent green vehicle routing problem with stochastic vehicle speeds: An approximate dynamic programming algorithm”, Transportation Research Part D, Vol. 54, pp. 82-98
- Dantzig, G. B. and Ramser, J. H. (1959) “The truck dispatching problem”, Management science, Vol. 6, No. 1, pp. 80-91
- El-Sherbeny, N. A. (2010) “Vehicle routing with time windows: An overviewof exact, heuristic and metaheuristic methods”, Journal of King Saud University (Science), No.  22, pp. 123–131
- Jlassi, J., Euchi, J. and Chabchoub H. (2012) “Dial-a-Ride and Emergency Transportation Problems in Ambulance Services”, Computer Science and Engineering, Vol. 2, No. 3, pp. 17-23
- Kirchler, D. and Wolfer Calvo, R. (2013) “A granular tabu search algorithm for the dial-a-rideProblem”, Transportation Research Part B, Vol. 56, pp. 120-135
- Kirci, P. (2016) “An optimization algorithm for a capacitated vehicle routing problem with time windows”, Sadhana Academy proceedings in Engineering Sciense, Vol. 41, No. 5, pp. 519-52
- Liu, M., Luo Z. and Lim, A. (2015) “A branch-and-cut algorithm for a realistic dial-a-ride problem”, Transportation Research Part B, No. 81, pp. 267-288
- Muelas, S., LaTorre, A. and Peña, J. (2015) “A distributed VNS algorithm for optimizing dial-a-rideproblems in large-scale scenarios”, Transportation Research Part C, No. 54, pp. 110–130
- Parragh, S. N. (2011) “Introducing heterogeneous users and vehicles into models and algorithms for the dial-a-ride problem”, Transportation Research Part C, Vol. 19, No.5, pp. 912-930
- Ritzinger, U., Puchinger, J. and Hartl R. F. (2016) “A survey on dynamic and stochastic vehicle routing problems”, International Journal of Production Research (online), Vol. 54, No. 1, pp. 215-231
- Talarico, L., Meisel, F. and Sörensena K. (2015) “Ambulance routing for disaster response with patient groups”, Computers & Operations Research, No. 56, pp. 120-133
- Zhang, Z., Liu, M. and Lim, A. (2015) “A Memetic Algorithm for the Patient Transportation Problem”, Omega-the International Journal of Management Science, No. 54, pp. 60-71