基于两阶段鲁棒优化的无人机载机平台调度问题

      1 引言

      近年来，物流末端配送领域掀起了“无人机配送”的变革热潮.相较于人力配送，无人机配送不受地面道路状况的影响，可以快捷、经济地完成对农村、山区和城市拥堵区的配送任务.城区配送方面，订餐平台饿了么在2018年获得政府批准，开设了无人机送餐航线.迅蚁无人机公司也与星巴克、肯德基等餐饮企业合作，在杭州未来科技城提供无人机送餐服务.农村物流方面，京东早在2017年便获得了陕西省无人机送货的空域批文，开设了一系列航空物流试点项目.顺丰于2018年取得无人机航空运营许可证，开始在江西赣州开展无人机配送业务.相较于城区配送，农村无人机配送目前已经初步形成较为完善的末端配送模式.亚马逊是最早涉足农村无人机配送的公司，发展了“空中仓库+无人机”配送模式，即将仓库建在空中，以大型飞艇作为空中仓库和无人机搭载平台，对末端客户进行配送服务.京东仿照亚马逊的配送模式，发展了“货运通航飞机+无人机”“车载无人机”等类似的配送模式.无人机，载机平台，区域调度中心等节点形成了完善的无人机末端配送系统，对于这样一个系统，管理人员需要综合考虑顾客需求点的地理分布、系统的服务能力以及建设成本等因素进行载机平台的调度决策.

      无人机载机平台的服务模式可以看作传统固定设施和普通车辆服务模式的结合.固定设施的服务模式如图1(a)所示，决策者首先根据顾客需求的地理分布确定设施位置，其后每个固定设施与周边的顾客根据距离远近等规则建立服务关系，这类问题统称为设施选址问题.普通车辆的服务模式如图1(b)所示，多辆车从仓库出发，对顾客进行“单对单”的上门服务，顾客点必须在某条车辆路径上才可以被服务，决策者需要合理设计车辆路径来满足顾客需求，即车辆路径问题.载机平台的服务模式如图1(c)所示，决策者首先根据顾客需求的地理分布确定载机平台的备选停靠点，其后根据顾客需求的变化趋势规划载机平台的调度路径，当载机平台在某备选停靠点静止时，可以像物流仓库一样辐射周边顾客.

      

      图1 三种服务模式对比

      Fig.1 Comparison of three service modes

      目前，很多偏远的乡村地区物流末端基础设施落后，利用载机平台搭载无人机进行送货，不仅配送高效节省人力，还可以克服交通不便等地理因素的影响.此外，相较于固定设施和普通车辆，载机平台能够更好地适应顾客需求分散、需求随时间波动频繁的物流情境.与传统的固定仓库相比，载机平台可以灵活调整设施位置动态满足不同区域的配送需求.与普通车辆相比，载机平台区域覆盖能力较强，可以辐射周边，同时满足多个顾客的需求.然而，载机平台的调度问题在建模求解方面也比前两者复杂很多，既要在不确定需求下确定载机平台的调度路径和服务关系，又要考虑载机平台容量、无人机续航里程等限制因素.目前，国内外与无人机载机平台调度相关的理论研究涉及固定设施动态选址问题、需求不确定的车辆路径问题和移动设施调度问题.

      动态选址问题要求决策者考虑未来需求变化，制定设施选址的长期决策方案，包括确定初始选址位置，设施服务能力调整和重新选址等决策.Antunes等[1]研究了固定设施的动态选址问题，假设设施选址后可以关闭并搬迁到新地址，旧设施关闭后不能重新使用，而新建立的设施不能再关闭.在此基础上，Jena等[2]提出的动态设施选址模型允许固定设施在计划期内发生多次变动.动态设施选址的最新研究，还考虑了仓库容量、供应链网络的可靠性等因素对选址的影响[3-6].不确定环境下的车辆路径问题假设客户需求在车辆到达前是未知的，此时可能会出现顾客需求超出配送车辆服务能力限制的情况.该类不确定问题通常需要进行两阶段建模[7-10]，即在第一阶段在客户需求未知时提前进行车辆路径决策，若车辆到达顾客点时无法满足顾客需求，要根据采取补偿策略.若已知顾客需求的概率分布，通常采用随机规划建模，若需求的概率分布未知，则多采用两阶段鲁棒优化模型求解[11，12].关于鲁棒优化的建模细节，可参考文献[13，14].基于动态选址问题和不确定需求下的车辆路径问题的相关研究，Halper等[15]在2011年首次提出了移动设施路径规划问题，利用最大覆盖模型对移动设施调度进行建模，给出了问题的边界和一些基本假设.其后，Raghavan等[16]考虑了移动设施的容量限制问题，Güden等[17]将传统的P-中值固定设施选址模型拓展到了移动设施调度领域.Lei等[18，19]结合移动设施调度问题的两阶段特点，提出了求解该问题的双层割平面算法.值得关注的是，移动设施调度并不局限与物流配送领域，医疗领域的移动救援车、通信领域的移动基站、旅游景区的移动餐车等，都可以作为移动设施调度的应用场景.

      目前，国内外与无人机载机平台调度直接相关的研究还比较少，而现有的末端配送理论又难以适应无人机送货的调度场景，故研究载机平台的调度决策具有极强的理论价值和现实意义.本文基于动态选址问题、不确定需求下的车辆路径问题、移动设施调度问题的相关研究，在顾客需求分散、需求随时间波动频繁的配送情境下，采用两阶段鲁棒优化的方法对载机平台调度问题进行建模.文章内容包括：1)构建了确定需求下的无人机载机平台调度模型；2)利用多面体集刻画顾客需求的不确定性，根据Bertsimas等[20，21]提出的鲁棒优化思想，建立了载机平台调度问题的两阶段鲁棒优化模型，并通过对偶变换将原模型转化为易求解的鲁棒对等模型；3)基于京东物流数据构造鲁棒优化和随机规划模型的测试算例，采用L型算法，利用CPLEX软件求解两种模型并对比求解性能.