A branch-and-price algorithm for robust truck-drone collaborative routing problem with road restoration uncertainty in disaster relief

With the frequent occurrence of natural disasters and extreme weather, the issue of relief transportation in humanitarian logistics has become increasingly critical. In disaster-affected areas, roads are often blocked by debris, requiring trucks to clear obstacles and restore the accessibility of roads before they can pass. Moreover, the uncertainty of road damage further complicates rescue efforts. Drones, unaffected by road conditions, serve as excellent auxiliary tools for trucks. This study addresses a robust truck-drone collaborative routing problem integrating road restoration and relief delivery. A truck and a drone are deployed to deliver supplies, aiming to maximize the fulfillment of prioritized demands within the limited rescue time. We have constructed a model for this problem and proposed a Branch-and-Price algorithm with customized labeling algorithm for task allocation in road restoration and rescue material delivery. The computational results demonstrate its superior performance, making the method well-suited for route planning in emergency rescue scenarios.