无人机任务规划及路径规划

城市物流服务商一直在追寻更快、更经济、更高效的最后一公里交付方式，而无人机作为一项新兴的技术为此提供了一个新的解决方案。与普通的卡车相比，无人机具有十分显著的优势，例如避免了道路网络的拥挤，运输速度更快，每公里的运输成本更低，并且无需付出昂贵的人工驾驶成本等。尽管监管障碍如禁飞区等阻碍了无人机交付的广泛采用，但各国放松对商业公司飞行器的监管已经成为了一种趋势。目前有六个国家允许在指定区域内交货，因此无人机的应用被认为是物流行业很有前景的一项选择。

另一方面，由于市场上大多数无人机都是由电池供电的，因此其载重量和飞行距离是无法与卡车相比的，卡车可以将更重、更远的包裹送达。因此卡车和无人机同时交付(VRPD)成为一种有效利用它们优势的方式。实际上，亚马逊、阿里巴巴、DHL等多家公司已经进行了实际试验甚至是试运行。在他们的实践中，可以看到几种新颖的尝试，例如建立无人机交付服务的专职枢纽，在宽敞的区域中使用特殊设备进行受控着陆，降落伞空投包裹，从固定的卡车上发射无人机等。

本文主要介绍了一种如下的解决方案，图中的例子使用了两辆卡车和两架无人机进行交付。无人机2首先由卡车2从仓库中取出的，当卡车服务第一个客户时，在卡车上发射，为另外两个客户服务，随后降落在对接枢纽上重新装载货物，随后进行后续服务，最终飞回仓库。与经典的车辆路径问题（VRP）不同，VRPD中有两种类型的车辆：无人机可能有多次飞行和着陆，每一次可能与另一辆卡车相关；卡车可能会在不同的时间和地点发射并收集多架无人机。如何确定两种车辆完成的客户服务顺序，即卡车收集或下放无人机的位置以及车辆行驶的路线，是应用这种模式的关键所在。

本文主要有如下贡献：（1）构建了现实场景的VRPD问题，据研究，这是首次在城市物流领域对该问题的建模；（2）对VRPD建立了基于弧的模型（arc-based）；（3）依据该问题的特殊结构，将其重构为基于路径的模型（path-based）并设计了分支定价算法找到了高质量的解；（4）进行了广泛的数值实验以及灵敏度分析。

基于路径的模型如下所示：其中目标（24）是使总物流成本最小化。约束（25）确保为每个客户提供一次服务。约束（26）-（27）迫使卡车与无人驾驶飞机关联的数量不能超过在节点处或沿弧线的限制。约束（28）限制了卡车的使用数量。约束（29）规定了变量的取值。

通过设定无人机和卡车的相关参数，对20个算例进行了实验，结果如下图所示。首先，VRPD解决方案最多使用2架无人机进行交付。这些无人机平均行驶47.4公里，可为大约5位客户提供服务。VRPD无人机和VRP卡车为客户服务的平均运输成本分别为0.316和1.933，表明卡车成本是为客户服务的无人机成本的六倍以上，这很好地证明了使用无人机进行交付的有效性。

从获得的解决方案中，我们发现了卡车和无人机之间的各种协作模式。图中绘制了一些路线，提供了对这些协作的直观图像。图中的路由方案变更为：一些客户仍由卡车服务，而另一些则留给无人机服务，这样可以节省21.73％的成本。

从上图中可以看出，卡车必须沿着可能拥挤的地面道路行驶，但是无人机可以在道路上空飞行，因此大大减少了的运输时间。两种类型的载具实现了良好的协作。在该解决方案中，卡车依次穿过节点6、5、10、8、1和2，以便它可以在节点6发射无人机并与无人机相遇在两个对接枢纽上。作为卡车的助手，无人机在其飞行范围和载荷限制内为四个客户提供了服务，其中包括最偏远的客户3和客户7、9和2。如果没有卡车的参与，无人机将无法为这些客户服务；而没有无人机，卡车必须花费更多的成本来服务这四个客户。与只使用卡车相比，这种协作的配送模式节省了28.95％的成本。

本文主要讲述了卡车无人机协作模式下的车辆路径问题（VRPD），其中卡车和无人驾驶飞机都用于运输。只要满足飞行范围和载重量限制，无人机可以跟着卡车行驶，从合理的节点起飞为客户服务，然后降落在对接枢纽以与另一辆卡车一起为客户服务。从不同实例的计算结果我们发现，VRPD的模式下可以有效地降低包裹配送的成本，从而改善快递最后一公里的难题。