31836

ارائه‌ي مدل مسيريابي وسيله‌ي نقليه بازگشتي در توزيع واكسن كوويد-19

كارشناسي ارشد

مهندسي صنايع گرايش لجستيك و زنجيره تأمين

1399

1402/7/5

جناب دكتر سعيد يعقوبي

نداشتم

مهندسي صنايع

بيماري كوويد-19 يكي از مهمترين چالش‌هاي جهاني بود كه سلامتي انسان را در قرن بيست و يكم مورد خطر قرار داد و جهان را محتمل بحران‌هاي سنگيني كرد. بنابراين در پاسخ به نياز مبرم براي مهار شيوع ويروس كوويد-19، تسريع بخشي به تحويل نهايي واكسن كوويد-19 از موضوعات حائز اهميت به شمار مي‌رفت. يكي از عوامل موثر بر تحويل به موقع، انتخاب مسير بهينه مي‌باشد كه تحت عنوان مسأله مسيريابي وسايل نقليه مطرح مي‌شود. ازاينرو، با توجه به آنكه استفاده از پهپاد براي تحويل بسته به دليل پتانسيل آن در تسريع و بهبود كارايي تحويل نهايي كالا اخيراً توجه زيادي را به خود جلب كرده، تلاش‌هايي ضمن تركيب پهپاد و كاميون انجام شده تا بتوان با استقرار چندين پهپاد به همراه كاميون به عمليات تحويل واكسن تسريع بخشيد. بر اين اساس با نگاهي بر نحوه‌ي توزيع واكسن كوويد- 19 طي دوره‌هاي مختلف و اهميت توزيع به موقع آن، چارچوبي از دو مدل مسيريابي وسيله‌‌ي نقليه را ارائه كرده‌ايم كه با عنوان‌هاي «مسأله مسيريابي پهپاد كاميون با پهپادهاي مشترك بين كاميون‌ها (VRP-ImD)» و «مسأله‌‌ي مسيريابي بازگشتيِ وسيله‌ي نقليه با چندين پهپاد‌‌ (R-VRPmD) » مطرح شده است. در مدل اول (VRP-ImD)چندين پهپاد به همراه چندين كاميون عمليات تحويل واكسن را انجام مي‌دهند. در اين سيستم هر پهپاد قادر است در هر پرواز خود و با توجه به محدوديت برد پروازش، به يك يا چند مركز واكسيناسيون واكسن تحويل دهد و سپس به هر كدام از كاميون‌ها بازگردد. در مدل دوم(R-VRPmD) چند پهپاد همراه با يك كاميون براي توزيع انواع مختلفي از واكسن‌هاي كوويد-19 طي چندين دوره بكار گرفته مي‌شوند. در اين مدل پس از تحويل واكسن‌ها در هر دوره، با توجه به نوع واكسني كه در هر دوره تحويل داده شده، هر يك از وسايل نقليه (پهپاد يا كاميون) ممكن است در دوره‌هاي بعدي پس از گذشت فاصله زماني لازم بين دو دوز متوالي، به صورت بازگشتي از مراكز واكسيناسيون كه قبلا به آن واكسن تحويل داده‌اند بازديد كنند. لازم به ذكر است مسأله‌ (R-VRPmD) كه با توجه به سيستم توزيع واكسن كوويد-19 و ملاحظاتي كه در آن ديده شد ارائه شده است، به عنوان شاخه جديدي از مسائل (VRP) طبقه‌بندي مي‌شود. بعلاوه، مدل‌هاي ارائه شده به عنوان مدل‌هاي برنامه‌ريزي خطي عدد صحيح مختلط (MILP) فرموله شده‌اند. هدف هر دو مدل به حداقل رساندن مجموع هزينه‌هاي حمل و نقل به مراكز واكسيناسيون مي‌باشد. علاوه بر اين با توجه به اينكه مسائل مطرح شده NP-hard مي‌باشند و براي ابعاد بزرگ آن نمي‌توانيم در زمان كوتاه با روش‌هاي دقيق پاسخي باكيفيت پيدا كنيم، لذا براي حل هركدام از آن‌ها رو‌ش‌هاي فراابتكاري در قالب الگوريتم سازگار شبيه سازي تبريد مبتني بر جمعيت ارائه كرده‌ايم و در اين پژوهش با عنوان الگوريتم TURA به آن اشاره مي‌كنيم. براي ارزيابي كيفيت جواب‌هاي بدست آمده براي حل مدل (R-VRPmD) به ازاي تعداد گره‌هاي مختلف كران پايين محاسبه شده است و با توجه به آن كيفيت عملكرد الگوريتم TURA توسعه داده شده را ارزيابي مي‌كنيم.

1403/10/16

Proposing a Recursive Vehicle Routing model for COVID-19 vaccine distribution

1/1/1900 12:00:00 AM

COVID-19 was one of the remarkable health threats facing the world in the 21st century that caused severe humanitarian crises worldwide. In spite of efforts to curtail the spread of the disease, the pandemic continued to pose a significant strain on healthcare systems worldwide. Hence, in response to a pressing need to limit viral transmission, the virus responsible for coronavirus disease sparked a race toward accelerating the Covid-19 vaccine's last-mile delivery. Taking this into account, the Covid-19 vaccine delivery was made within a given time frame consisting of distinct periods to distribute varied types of single-dose vaccines as well as the double-dose ones. On that account, with the goal of deploying drones in conjunction with a truck to capture the propounded scenario, once the vaccines are delivered in each period, either of the vehicles may visit the serviced nodes recursively in subsequent periods. Not only to satisfy the existing primary demand of each vaccination center but also to fulfill the demand for succeeding doses. In addition, with respect to the double-dose vaccine type previously delivered to each node and the required interval between every dose in succession, the recursive visits can be scheduled at each node. Accordingly, in light of the illumination perceived from the Covid-19 pandemic vaccine delivery, this paper presents two frameworks of novel Vehicle Routing Problem (VRP) called "Vehicle Routing Problem with Interchangeable multivisit drones" (VRP-ImD) and the "Recursive delivery Vehicle Routing Problem with multiple Drones" (R-VRPmD) that can be classified as a new branch of VRP. (VRP-ImD) presents an approach to optimize last-mile delivery. In this scenario, multiple trucks are equipped with a fleet of drones capable of launching from a truck, delivering parcels to one or more customers per flight, and returning to either their originating truck or any available alternative regarding its flightrange. In addition, the presented novel R-VRPmD is an application captured from the enlightenments of Covid-19 vaccine delivery that can be applied to many other scenarios such as home healthcare, equipment maintenance and repair, in which, with a glance at the kind of services supplied in previous periods and their required time interval, the same service must recursively be provided in following periods after its specific time interval passes. We formulate the R-VRPmD as a mixed integer linear programming (MILP) model. The objective of the presented optimization models are to minimize the total transportation costs to service nodes. In addition, due to the limitations of the solver's performance when applied to large-scale instances, we have developed a heuristic approach based on several algorithms to solve real-world problems. Furthermore, we have incorporated a lower bound to compare the proposed heuristic's performance to the results of the solver.

تحويل بازگشتي، مسأله‌ي مسيريابي وسيله نقليه، برنامه ريزي پهپاد، كوويد-19؛ تحويل نهايي كالا، برنامه ريزي خطي عدد صحيح مختلط.

Recursive delivery; Vehicle Routing Problem; Drone Scheduling; Covid-19; Last-mile delivery; Mixed integer linear programming.

fatemeh jamshidian

dr saeed yaghoubi