【文章链接】
https://doi.org/10.1287/msom.2022.0339
研究背景
随着技术的进步，无人机被越来越多地用于包裹配送，但是这种配送方式受到诸如天气条件等不确定性因素的影响。风、雨雪和雾等天气状况可能会限制无人机的操作能力，增加能量消耗，影响无人机的飞行距离、飞行时长，造成配送的延误。大多数关于无人机配送的研究都假设未来的天气条件或者飞行范围/时间是确定性的，遵循已知的概率分布，或者属于具有已知概率的某些情景。然而，这样的假设并不总是成立，特别是在天气条件变化多端的情况下。因此，如何合理利用天气数据等信息，以便在决策过程中减少服务延迟，是非常重要的。
研究问题
该研究旨在解决无人机配送中因风况的不确定性而导致的服务延迟问题。通俗地说，研究者建立两期无人机调度模型，早上做出调度决策，上午按计划配送并观测、反馈风况信息（风向、风速等），支撑系统更新下午的交付安排，从而降低服务延迟风险。
研究模型
在无人机配送系统中，一队相同的无人机被派往一组 N 个地理上分散的客户。每架无人机可以进行多次往返，每次往返都是从仓库飞往客户，然后返回仓库准备下一次配送。无人机在仓库和指定客户之间的运输时间受风况影响，也就是说，风可能会根据其速度和方向增加或减少其飞行时间。图 1 说明了风况和飞行时间之间的关系。
基本设定
仓库和客户分布在二维空间中，不失一般性，仓库的坐标位于 (0, 0)。风矢量用极坐标 （r,θ）表示，其中r表示风速，θ是风向与x轴的夹角。客户i的位置用极坐标（di,φi）表示，其中 di 是与仓库的距离，φi 是仓库和客户 i 之间连线与 x 轴的夹角。
对于第 i 个客户，无人机前往送货的空速取决于客户货物的重量和大小，用 ri 表示。在没有负重的情况下，无人机返回的空速为 r0，r0 ≥ ri。假设 r < ri，以禁止在大风条件下送货。送货无人机内的自动导航系统会根据风况进行调整，以抵消风对飞行方向的影响，这样无人机就可以径直从仓库飞到客户那里。易得前往用时ui和返回用时vi为
无人机可以降低速度甚至延迟飞行，以避免提前到达客户所在地。例如，如果无人机在τ时从仓库出发，并且约定在τ1为客户提供服务，那么无人机到达客户所在地的时间将是 max{τ+ ui, τ1}。
两期模型
考虑一个两期模型，其中周期 1 和周期 2 分别代表上午和下午。周期 1 从时间 0 开始，到中午时间τ1结束；周期 2 从τ1开始，到τ2结束。在周期 1 开始时，模型会优化调度策略，该策略决定了无人机在上午的配送时间表，而下午的时间表可以灵活地适应上午观测到的风矢量 (r1,θ1) 和中午之前已知的其他天气信息。有 H 个风观测数据样本，在样本 h 下，分别定义 (r1h,θ1h) 和 (r2h,θ2h) 为周期 1 和周期 2 中观测到的风矢量。
由于风况不确定性导致飞行时长不确定，令
分别表示两期的前往、返回时长，并定义矢量符号
聚类模糊集
首先使用聚类模糊集来表征第一阶段的模糊集，将风矢量图划分为K1个不重叠的聚类uK1 ，样本索引集为
如下图所示：
引入随机变量k~1，它在 [K1] 中取离散值。于是构建了与随机变量 (u˜1 ,v˜1 ,κ˜1 ) 相关的聚类模糊集
如下所示：
其中与集群 k 相关的前往飞行时长参数特征如下：
同理可得返回飞行时长的参数。
在中午时，随机变量 (u˜1 ,v˜1 ,κ˜1 ) 将实现。为了将风况数据以外的其它天气信息纳入模型中，把天气信息离散化为 S 个有限场景，引入随机变量s~，并与一阶段类似地得到二阶段飞行时长参数特征，最终模糊集建立为如下形式：
配送时间与延迟风险
目标是优化无人机配送时间表，减轻送货延迟风险。客户指定他们希望在早上还是下午送货。将客户分成三组，C1 和 C2 是期望在第 1 阶段和第 2 阶段送货的客户集，C3允许在任一时期获得服务，并会被告知他们将在第 1 阶段或第 2 阶段收到。
表示随机到达时间，引入ERI来评估服务延迟风险：
最小化以下联合决策：
其中Ktd表示无人机 d 在 t 时期需要服务的客户集合。
事实上，（8）可以转化为更直接的形式：
第1期中无人机d到达最后一位顾客的随机时间是
第2期客户只能在τ1之后，且第1期客户全部送完后得到服务，所以需要考虑第2期无人机d到达的第一位客户的时间ł2-d。第2期无人机d到达最后一位顾客的随机时间是
无人机调度决策
定义决策变量
二元变量
第二阶段同理，分别用y2id、z2id和x2id来刻画第最后一个、非第一或最后、第一个客户。
无人机调度计划决策如下：
DRO模型与转化
对于给定的d，其服务1期和2期最后一个顾客的到达时间分别记作：
最终构建的DRO模型如下所示：
对于（15a），其中的sup问题等同于
利用全概率定理可以转化为
运用对偶变换，我们可以将其转化为如下线性规划问题：
同理可以将（15b）转化为线性规划问题。于是我们可以将（15）的DRO问题转化为经典线性问题：
结论
（1）在无人机送货问题中，必须考虑随机天气条件导致的不确定行程时间。否则，一旦出现不确定性，确定性模型提供的决策将导致性能不佳，从而导致包裹递送严重延迟。
（2）尽管存在多个面向服务的决策标准，但建模者在选择标准时应考虑至少两个方面：（i）标准考虑不良事件概率及其幅度的能力；（ii）候选决策标准下的模型复杂性。基于ERI的联合决策标准为上述两点提供了解决方案。
（3）使用已实现的第一阶段信息灵活调整第二阶段决策可以提高DRO模型在样本外测试中的性能，即使该模型可能未得到最佳解决。
微信公众号后台回复
加群：加入全球华人OR|AI|DS社区硕博微信学术群
资料：免费获得大量运筹学相关学习资料
人才库：加入运筹精英人才库，获得独家职位推荐
电子书：免费获取平台小编独家创作的优化理论、运筹实践和数据科学电子书，持续更新中ing...
加入我们：加入「运筹OR帷幄」，参与内容创作平台运营
知识星球：加入「运筹OR帷幄」数据算法社区，免费参与每周「领读计划」、「行业inTalk」、「OR会客厅」等直播活动，与数百位签约大V进行在线交流
文章须知
文章作者：东南数智港
责任编辑：张琪 马玺渊
微信编辑：疑疑
文章转载自『东南数智港』公众号，原文链接： 成果快照 | 结合天气信息的鲁棒无人机配送
关注我们
FOLLOW US
