需求可拆分的无人机与卡车协同路径优化问题

    Split-delivery Vehicle Routing Problem with Drone

    • 摘要: 基于无人机配送优势,提出一类无人机与卡车分区域协同配送问题。考虑需求稀疏地区由无人机配送,需求密集地区由卡车与无人机协同配送的情形。由于无人机的载重能力较小,无人机访问的顾客需求允许被拆分。结合无人机与卡车的访问路径关系,以最小化运输成本和使用卡车的人力成本为目标建立混合整数规划模型,并设计一种改进变邻域搜索算法对问题进行求解。小规模算例的特性分析表明,运输成本对无人机的载重能力及单位运输成本敏感性较高。多个不同规模的算例测试表明,改进变邻域搜索算法能在较短时间内有效求解各规模算例,且算法稳定性较好。

       

      Abstract: Based on the advantages of drone distribution, a regional collaborative distribution problem between drone and truck is proposed. Considering the situation that drone is used to distribute in sparse area and truck and drone cooperate in demand intensive area, due to the small load capacity of drone, the customer demand of drone access is allowed to be split. Combined with the access path relationship between drone and truck, a mixed integer programming model is established to minimize the transportation cost and the labor cost of using truck, and an improved variable neighborhood search algorithm is designed to solve the problem. The characteristic analysis of small-scale calculation shows that the transportation cost is sensitive to the load capacity and unit transportation cost of drone. The test results of several different scale examples show that the improved variable neighborhood search algorithm can effectively solve the cases of various scales in a short time, and the algorithm has a good stability.

       

    /

    返回文章
    返回