مساله مسیریابی وسایل نقلیه با هواپیماهای بدون سرنشین

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

Highlights•Vehicle routing problem with drones is presented.•An arc-based model is constructed.•A branch-and-price algorithm is developed.•Experiments and sensitivity analysis are conducted for managerial insights.AbstractThe vehicle routing problem with drones (VRPD) is an extension of the classic capacitated vehicle routing problem, where not only trucks but drones are used to deliver parcels to customers. One distinctive feature of the VRPD is that a drone may travel with a truck, take off from its stop to serve customers, and land at a service hub to travel with another truck as long as the flying range and loading capacity limitations are satisfied. Routing trucks and drones in an integrated manner makes the problem much more challenging and different from classical vehicle routing literature. We propose a mixed integer programming model, and develop a branch-and-price algorithm. Extensive experiments are conducted on the instances randomly generated in a practical setting, and th