论文部分内容阅读
应用无人机解决“最后一公里”的配送问题,构建智慧创新的下一代末端配送体系,对满足日益增长的配送需求,缓解地面交通的压力,摆脱老龄化带来的劳动力短缺束缚,推动快递服务业数字化转型,带动全产业链协同发展具有重要作用。在这种情境下,基于地面车辆的配送网络与基于无人机的空中配送网络的动态整合需求尤为迫切,也对快递服务商的运营管理构成新的挑战。一方面,新增的无人机空中配送作业与已有的卡车地面配送作业尚未进行充分整合,二者同步配送的角色定位存在冲突,难以发挥配送系统的潜在效率。另一方面,空中与地面双重不确定因素对卡车与无人机联合作业形成干扰,增大配送系统的协同风险。在不确定条件下如何安排卡车与无人机联合作业,兼顾配送效率与协同风险,成为物流服务商难以回避的问题,这也为物流网络设计理论与方法的研究提出了新主题。本研究通过卡车与无人机两级配送网络的优化,弥补物流网络设计理论在完全动态服务网络设计研究中的不足,为实现既对节点服务又对弧服务的复杂两级物流网络的整合提供支持,进一步满足复杂系统在不确定条件下的自主决策需求,推动数据驱动的鲁棒优化理论的应用与发展。首先通过理论分析,梳理研究现状,从卡车与无人机配送网络动态整合的实际需要出发,根据完全动态的物流网络配置,本文提出了卡车与无人机两级配送网络动态整合的三大核心问题:单卡车-单无人机路径问题鲁棒优化、单卡车-多无人机路径问题鲁棒优化和多卡车-多无人机路径问题鲁棒优化。接着针对不同的问题类型,给出不确定条件下鲁棒解的定义与标准,选择不确定参数的处理方法,构建鲁棒优化模型。然后根据具体问题的结构特征,设计高效的求解算法。最后使用算例仿真的方法,验证鲁棒模型及求解算法的适用性和有效性。本研究的主要工作有三方面:(1)从运输规划角度研究不确定的交通条件下单卡车-单无人机路径问题的鲁棒优化,提出卡车与无人机联合路径的同步规划方法。从运输规划角度,解析了单卡车与单无人机路径规划的三个层次:路径决策、任务分配决策、无人机起降位置选择的中继地选址决策,且中继地选址决策从属于路径决策。进而考虑不确定交通条件,采用简单椭球不确定性集合处理卡车行驶时间的扰动,构建鲁棒的带无人机旅行商问题的二阶锥规划模型。最后,基于卡车与无人机路径问题的结构特征,设计有效前沿启发式算法,并通过数值算例检验了鲁棒模型和算法性能。(2)从车辆调度角度研究不确定导航环境下单卡车-多无人机路径问题的鲁棒优化,提出单卡车与多无人机联合作业的概念,通过鲁棒性分析确定一台卡车所应部署无人机的最佳数量。从车辆调度角度,定义单卡车与多无人机的联合作业,剖析在每一次联合作业中,卡车与无人机之间的任务分配以及派出的无人机数量对配送效率和协同风险的影响。进而考虑不确定导航环境,当两架或以上无人机在一台卡车上起降时,不确定导航环境会增加潜在的作业冲突,导致协同失败。为量化这一影响,将其描述为无人机在被卡车回收前的一段不确定的等待时间。然后在无人机最大续航时间约束下,将卡车与无人机的调度决策包括客户任务分配、无人机派遣、中继地选址整合到一个二阶锥规划模型,以最小化作业总时间的同时降低协同风险。为求解这一复杂问题,设计出三阶段自适应大邻域搜索启发式算法。最后基于长春市主城区的快递包裹配送网络开发算例,检验鲁棒模型和算法性能,进行鲁棒性分析,从而确定一台卡车所应部署无人机的最佳数量。(3)从物流网络设计角度系统地研究不确定条件下多卡车-多无人机路径问题的鲁棒优化,提出适用于一般情形的鲁棒模型,开发高效的混合启发式算法,以求解实际应用中的大规模问题。从物流网络设计角度,分析不确定条件下中继地的选择对卡车和无人机构成的两级配送网络有三种不同程度的影响:正常停止、操作性停止和紧急停止。为满足复杂系统在不确定条件下的自主决策需求,将操作性停止和紧急停止统称为卡车与无人机的协同失败。进而考虑不确定的交通条件、不确定的导航环境,分别构建一台卡车与一架无人机配对、一台卡车与多架无人机配对的带无人机车辆路径问题的鲁棒模型,并推广到一般情形,构建不确定条件下带无人机车辆路径问题的鲁棒模型。为提升求解效率,开发基于禁忌搜索与分支切割的混合启发式算法。最后参考长春市主城区快递包裹配送网络,生成不同规模的算例,检验鲁棒模型和算法性能,模拟分析不同车队规模、风险惩罚系数组合下配送效率与协同风险的变化。本研究得出的主要结论如下:(1)对单卡车-单无人机路径问题的鲁棒优化表明,采用选址决策从属于路径决策的联合路径同步规划方法能够动态插入卡车停靠点,从而适当调整卡车行驶路线、合理确定无人机的起降位置,为不确定的交通条件下动态整合卡车与无人机配送网络、满足“最后一公里”配送需求提供了一条可行的途径。(2)对单卡车-多无人机路径问题的鲁棒优化表明,采用鲁棒优化方法能够调整卡车与无人机的联合作业以及派出的无人机数量,降低协同风险的同时减少配送作业总时间,从而在不确定导航环境下,为确定一台卡车所应部署无人机的最佳数量提供决策依据。(3)对多卡车-多无人机路径问题的鲁棒优化表明,本文提出的带无人机车辆路径问题的鲁棒模型以及混合启发式算法能够稳定、高效地获得鲁棒(近似)最优解,从而满足求解大规模实际问题的需要,进而为不确定条件下卡车与无人机两级配送网络的动态整合提供了适用的数学模型和高效的求解算法。本研究的创新点主要体现在:(1)针对卡车与无人机配送网络动态整合这一新问题,首次在“最后一公里”配送场景中提出选址决策从属于路径决策的同步规划方法,将无人机起降位置选择整合到卡车与无人机的联合路径规划中,弥补了完全动态服务网络设计理论研究的不足。(2)对于一台卡车与一架无人机构成的两级配送网络,考虑不确定交通条件,首次将鲁棒的带无人机旅行商问题构建为二阶锥规划模型,并设计有效前沿启发式算法进行求解,为卡车与无人机之间的任务分配提供鲁棒优化的新方法。(3)对于一台卡车与多架无人机构成的两级配送网络,考虑不确定导航环境,首次将鲁棒的带多架无人机的旅行商问题构建为二阶锥规划模型,并开发三阶段自适应大邻域搜索算法进行求解,为确定卡车所应配备无人机的最佳数量提供新工具。(4)对于多台卡车与多架无人机构成的两级配送网络,考虑交通条件与导航环境的不确定性,首次将鲁棒的带无人机车辆路径问题构建为二阶锥规划模型,并开发混合启发式算法进行求解。本文揭示不同运输车队配置、不同风险惩罚系数下卡车与无人机系统的配送效率变化,以及采用鲁棒(近似)最优解的鲁棒代价与鲁棒收益,为全面实现卡车与无人机两级配送网络的动态整合提供通用的数学模型和更高效的求解算法,同时也丰富了数据驱动的鲁棒优化理论与方法的工具箱。