摘要: 在物流配送领域，传统单配送车送货存在配送成本高、效率低、延误高、环境污染等问题。随着无人机在物流领域受到越来越多的关注，一种新型交付概念被提出——无人机联合配送车协同配送包裹，从而引发了“无人机——旅行商”问题(TravellingSalesmanProblem... 展开 在物流配送领域，传统单配送车送货存在配送成本高、效率低、延误高、环境污染等问题。随着无人机在物流领域受到越来越多的关注，一种新型交付概念被提出——无人机联合配送车协同配送包裹，从而引发了“无人机——旅行商”问题(TravellingSalesmanProblemwithDrone,TSP-D)的讨论。本文针对该种新型交付方式，以最小化交付时间为问题目标，研究无人机与配送车联合路径规划以及路径优化算法问题。 首先，论文建立了无人机联合配送车配送问题模型。通过对传统旅行商问题模型的研究，在此基础上建立了联合配送问题模型。在考虑无人机与系统约束条件的前提下提出问题假设条件并建立混合整数规划数学模型。其次，针对问题中无人机与配送车之间的协同特性以及约束条件，论文提出了一种新型优化迭代算法对联合路径进行规划。算法思路是将问题分为两步，第一步确定配送车路径及客户节点分配，第二步固定配送车路径及无人机节点，确定二者汇合节点生成无人机配送路径。保留满足约束条件的无人机路径及对应配送车路径，求解联合配送总耗时，以此方式从最少的配送车节点开始迭代，通过更新全局上界对问题求解。然后，采用模拟退火算法对解进行改进优化。最后，本文对10、11节点规模的问题在均匀和聚集两种算例下进行实验，结果表明在约20min合理时间范围内实验能够得到10至11节点规模问题的最优解，本文提出的算法在一定程度上缩小了问题求解时的搜索规模同时降低了程序运行时间。分析实验结果得到，在聚集算例下解的质量更优即当客户节点分布越密集时，算法优势更大；增大无人机速度可以提高问题求解质量和效率；分配给无人机的节点个数与求解质量的优劣这二者之间不存在正比例关系；通过对比相同问题规模下TSP解与TSP-D解，表明将无人机整合入传统单配送车配送模式中能够在一定程度上提高传统物流系统的配送效率并节约整体成本，具有实际的应用价值。 收起