实时需求下卡车与无人机协同配送的在线与离线问题研究

　　引言

　　卡车与无人机联合配送模式是一种新型的物流配送模式，通过将卡车作为无人机的起降平台，实现更高效、更低成本、更灵活的配送服务。这种模式在近年来受到了工业界和学术界的广泛关注和研究，也有一些企业和机构在不同的场景和地区进行试点运营。例如京东物流在江苏常熟市区和山西太原市区分别投入了数辆无人车和数架无人机，还在山区、岛屿等地区开展无人机的特殊配送服务，解决了传统物流难以到达的问题。UPS在美国北卡罗来纳州进行医疗用品的无人机配送实验，利用卡车作为无人机的起降平台，将医疗样本从医院送到实验室，缩短了运输时间和成本。随着科技的不断进步，卡车与无人机组合的配送模式正逐渐成为物流行业的新选择，这将极大地促进物流效率和便捷性。在实际的配送过程中，各种原因都会影响到消费者的需求和偏好，可能会出现订单更改等难以预测的情形，需求的动态性增强，从而导致配送难度变大，路径优化也更复杂。因此针对产品配送过程中实时产生且无法预知的情形，本文提出了卡车与无人机协同在线配送问题。

　　对于卡车与无人机协同配送问题，MURRAY和CHU[1]将卡车与无人机协同配送问题称为FSTSP（Flying Sidekick Traveling Salesman Problem），并设计启发式算法进行求解。AGATZ等[2]提出了带有无人机的旅行商问题，并设计了局部搜索和动态规划的启发式算法求解该问题。WANG等[3]等描述了VRP-D模型，并证明了几种最坏情况定理，结果显示了使用卡车与无人机配送比单独使用卡车配送更节省时间。熊兴隆等[4]以最小化交付时间为目标，提出了一种新型的优化迭代方法，并通过相应的示例来验证算法的有效性。彭勇和黎元钧[5]考虑无人机的载重、最大飞行时间以及道路条件等因素，将客户按照不同性质分类，并设计了混合邻域搜索算法求解该问题。蒋丽等[6]以最小化综合配送成本为目标建立混合整数规划模型，并提出了一个两阶段混合蚁群算法对卡车路径和无人机路径进行联合优化以实现问题求解。高娇娇和郭秀萍[7]考虑卡车与无人机协同配送模式下两级车辆路径优化问题，设计基于扫描算法和改进的大规模邻域搜索的混合算法求解。蒋丽等[8]针对卡车与无人机协同配送无接触配送问题，构建了一个混合整数规划模型，并提出一个双层模型，设计了一种双层启发式算法求解该问题。现有的研究大多是基于静态的假设，即需求是事先已知的。然而，在实际应用中，需求往往是动态变化的。因此，如何解决卡车与无人机协同配送的动态问题，是一个有待深入探讨的课题。

　　对于动态需求，王新玉和赵志明[9]通过归纳总结相关文献，发现对于动态输入的需求可以采用重优化的策略将动态问题转换为多个离线的静态问题进行求解，也可以采用在线算法分析。AUSIELLO等[10]在2001年最早提出在线TSP问题，针对需要返回起点的情形，在一般网络上给出2竞争比算法，并且在直线上给出1.75-竞争比算法。JAILLET和WAGNER[11]将单服务器情形扩展到多个服务器，并证明了竞争比为2ρ。AUSIELLO等[10]分析了Nomadic的在线TSP问题，并给出了2.5-竞争比算法。LIPMANN[12]在这个基础上进行了相应的改进，将一般网络上的竞争比结果改进到1+，而温新刚等[13]进一步提出了带有预知信息的Nomadic在线TSP问题，并在一般网络上和直线上给出了相应的算法。马军平等[14]研究了具有服务时长的在线TSP问题，证明得到一般网络和直线上的竞争比分别为（2-β/（1+α））和（7/4-3/4（α/（1+α）））。樊相宇等[15]提出了环形路网上带有服务时长的在线TSP问题，并给出了LOOP算法和SD算法，证明得到环形路网上的竞争比（2+（2-2β）/（2+α））。以上学者对车辆的在线调度研究的非常深入，但是对于卡车与无人机协同在线配送问题还有待研究。余海燕等[16]针对应急配送中的实时需求，研究了无人机与车辆并行在线配送问题，在一般网络上给出2.5-竞争比算法。但其只考虑了在配送中心附近的配送场景，没有充分利用车辆与无人机的协同优势，也没有考虑无人机的载重限制对配送效果的影响。因此，对于实时变化的配送需求，本文还可以进一步研究车辆与无人机的协同在线配送问题，以提高配送的灵活性和效率。

　　综上所述，本文针对产品配送过程中需求实时产生且无法预知的情形，研究了卡车与无人机协同在线配送问题。首先给出问题描述和基本定义，采用竞争分析法来证明该问题的下界，其次设计RAR（Return And Replan）在线算法，并运用最坏情形法证明该问题的竞争比；然后建立相应的离线模型，设计TSOA（Two Stage Off-line Algorithm）算法，运用MATLAB将其与CPLEX仿真结果对比，最后通过算例仿真和灵敏度分析，验证RAR算法的有效性。