摘 要

互联网时代的到来带动了电子商务的高速发展，也带来了物流运输与配送的巨大需求，近些年来，物流运输总量不断攀升，传统的人工操作与普通运输已经无法满足日益增大的物流需求。另一方面，在各家电商平台的竞争下，线上用户对于包裹运输速度与质量也提出了更高的要求。为解决这些问题，企业也不断寻求能够降成本、提效率的方法，提供更加科学化、智能化、精细化的服务，民用无人机为物流业带来新的机遇。随着无人机技术的精进，其灵活、快速、低耗的特点为提升物流效率带来了很大空间，在国内外也逐步用于现实配送环节。但同时无人机具有载重能力小，续航时间短等缺点，在实际配送中往往需要与卡车协同配送，发挥二者的优势。运营商也面临着新的问题：采用怎样的协同运输模式、卡车与无人机两种运输方式如何分配以及怎样合理安排配送路径。因此，有效的解决无人机与卡车协同配送的路径优化问题对于无人机实际落地参与配送以降低运营商成本具有非常重要的意义。

本文在以往研究的基础上，考虑了卡车作为无人机的承载工具，且二者同时参与配送环节的协同配送方式，同时分别考虑了需求可拆分、同时取送货、动态环境下同时取送货情形下的三类路径优化问题。本文旨在通过优化无人机与卡车协同配送提供合理服务路径以降低运营成本。首先，本文对无人机与卡车协同路径优化问题的相关研究背景和无人机与卡车协同配送的实际运营情况进行了系统性分析，然后基于运筹学与传统车辆路径问题的理论背景，以最小化运输成本与人力成本为目标建立了符合问题描述的混合整数规划模型。针对问题的NP-Hard性质，提出了有效的启发式算法来解决大规模的优化问题。本文求解算法主要采用改进的变邻域搜索算法，在基本算法的基础上，结合不同问题的特点生成符合约束的初始解、对下降算法中的邻域算子、扰动算子进行改进，且加入了新的改进策略。在数值实验部分采用CPLEX对模型精确求解，将求解结果与变领域搜索算法产生的解进行比较，证明了所提出的启发式方法的有效性，并强调了无人机与卡车协同完成“最后一公里”配送相比传统卡车运输方式的显著优势。

关键词：车辆路径问题；无人机；变邻域搜索算法；协同配送；混合整数规划