优化农村物流:一种用于解决包含多个无人机站的卡车-无人机定位与路径规划问题的双层启发式算法

【字体: 时间:2026年03月13日 来源:Case Studies on Transport Policy 3.3

编辑推荐:

  农村物流中卡车与无人机协同配送问题,提出多无人机中转站选址路径规划模型,通过混合整数线性规划分层建模,上层优化无人机中转站选址,下层规划卡车路径与无人机配送,设计融合遗传算法与蚁群优化的双层启发式算法GACS,实验表明该算法在解决大规模问题时具有更优的解质量和计算效率,敏感性分析揭示无人机单位运输成本补贴比中转站建设补贴更有效。

  
吴丽荣|张航|王泽浩|张元凯|王素丽
山西大学经济与管理学院,中国太原

摘要

电子商务的快速发展给农村物流配送带来了重大挑战。农村地区通常人口稀少,道路基础设施不足,缺乏先进的物流信息系统。卡车与无人机结合的运输方式具有灵活性,并且相对不受地面地理障碍(如河流、山脉、道路网络不发达)的影响,因此在农村物流应用中引起了广泛的研究兴趣。为了提高农村物流配送的效率,本文研究了具有多个无人机站点的卡车与无人机定位-路径问题(LRP-DS)。该问题旨在优化卡车和无人机的运行,同时确保满足所有客户需求并最小化运营成本。假设卡车停放在中央仓库,且有多个潜在的无人机站点可用。我们将问题构建为一个混合整数线性规划模型,该模型分为上层位置模型和下层车辆路径模型。为了解决这个问题,我们提出了一种双层启发式算法,该算法结合了改进的遗传算法和扩展的蚁群系统算法。在小型和大型数据集上的计算实验表明,所提出的算法在解决方案质量和计算效率方面优于CPLEX求解器。此外,敏感性分析显示,与卡车搭载无人机的方式相比,我们的模型在时间成本上更具优势。随着网络节点间距离的增加,当无人机的单位运输成本降低时,我们模型的成本逐渐变得更加有利。敏感性分析还表明,对无人机单位运输成本的补贴比对无人机站点启动成本的补贴更有效。

引言

随着全球电子商务的快速发展以及农村地区消费水平的提高,农村地区已成为在线消费的新前沿。最新统计数据显示(SCIO,2023年),2023年中国农村地区的在线零售销售额达到了惊人的2.5万亿元,凸显了农村物流在将偏远地区融入更广泛经济框架中的关键作用。然而,与相对成熟和高效的都市物流相比,农村物流面临诸如地理分布广泛、道路基础设施不均衡和人口密度低等重大挑战。这些障碍阻碍了商品和服务的有效及时交付,阻碍了农村物流的发展。为了满足超过2亿农村互联网用户的物流需求,开发更高效的农村终端配送物流网络至关重要(Yang等人,2020年)。
低空经济是将无人机(UAV)整合到物流中的新兴愿景(Sun等人,2025年)。无人机技术的出现为农村物流提供了有前景的解决方案(Wang等人,2024年),通过快速且灵活的解决方案改变了偏远地区的配送格局(Otto等人,2018年)。与传统使用卡车直接服务客户的方式相比,无人机提供了显著的优势,如降低成本、加快交付时间以及提高客户满意度(Rejeb等人,2023年)。大型企业正在积极探索无人机在包裹配送中的应用,例如DHL利用无人机向德国北海岛屿Juist进行紧急包裹配送(Boysen等人,2018年)。无人机技术具有独特优势;它们能够在三维空间中机动,从而避免交通拥堵和事故,确保一致且快速的运输。此外,无人机具有操作灵活性和易用性,为偏远地区的配送带来了显著的成本节约,而它们依赖电池供电的特点也体现了其能源效率和环境可持续性。
尽管无人机运输具有诸多优势,但与传统卡车运输相比并不实用(Tamke和Buscher,2023年)。由于无人机的某些限制——如载重能力限制、需要签名的包裹或飞行范围有限——某些客户只能通过卡车服务(Otto等人,2018年;Pachayappan和Sundarakani,2023年)。在农村物流中,由于道路条件差,卡车无法到达某些偏远地区,使得无人机配送成为某些客户的唯一可行选择。因此,在农村物流中,客户明显分为两类:一类由卡车服务,另一类由无人机服务。为了支持无人机运营,建立了多个无人机站点,作为无人机存储和充电的中心。这些站点通常建立在现有的基础设施上,尤其是分布在农村地区的杂货店。卡车不仅直接服务无人机无法到达的客户,还将包裹送到无人机站点,然后由无人机完成最终的客户配送。卡车与无人机的无缝集成已成为高效安全运输的关键技术,吸引了大量学术关注(Dang等人,2024年)。
与卡车搭载无人机的方式相比,无人机站点模式特别适合人口稀少的农村地区,原因有二。首先,农村客户通常分布较远,直接使用卡车配送在运输成本上较高。卡车搭载无人机的方式往往导致卡车等待时间过长,而无人机站点模式可以有效降低运输成本和卡车等待时间。其次,虽然卡车搭载无人机的方式注重配送时效性——需要多架无人机同时运行以满足客户的时间要求——但农村客户通常不需要时间敏感的配送。在这种情况下,每个站点只需一两架无人机即可运行。每架无人机可以进行多次配送任务,使卡车可以无需等待即可继续行驶。无人机数量的减少显著降低了固定成本。此外,无人机站点的布局对农村物流至关重要,因为它增强了无人机服务覆盖的灵活性。因此,本文介绍了一个针对农村物流的具有多个无人机站点的定位-路径问题(LRP-DS)框架。
需要注意的是,LRP-DS建立在定位-路径问题和枢纽定位-路径问题的基础之上(详见Tadaros和Migdalas,2022年;Wandelt等人,2025年)。LRP-DS框架涉及多种复杂性。首先,这一问题的新颖性要求根据农村物流的特点开发定制模型。其次,该问题本质上扩展了经典的车辆路径问题,这是一个众所周知的NP难问题。即使对于小规模问题,LRP-DS也涉及大量的决策变量和大M约束,使得数学模型无法使用CPLEX求解器在多项式时间内得到解决。因此,能够为大规模场景提供可行解决方案的高效启发式方法至关重要。此外,对于实际应用而言,为农村物流的利益相关者提供可操作的管理洞察以有效指导决策制定也非常重要。
本研究的主要贡献有三方面。首先,我们开发了一个新颖的混合整数线性规划(MILP)模型,该模型将多个无人机站点的位置与车辆路径结合,用于农村物流中的卡车-无人机配送。其次,我们提出了一种高效的双层启发式算法(GACS),该算法结合了改进的遗传算法和蚁群优化算法,在解决方案质量和计算效率方面均优于CPLEX,特别是在大规模实例中。第三,通过全面的敏感性分析,我们提供了关键的管理洞察,揭示了增加无人机站点的收益递减现象,并建议补贴无人机单位运输成本比补贴站点启动成本更有利于提高农村无人机物流的经济可行性。
本文的其余部分结构如下:第2节总结了相关文献。第3节我们为LRP-DS问题开发了一个MILP模型,并将其分解为双层编程结构。第4节介绍了我们的双层启发式解决方案GACS。第5节我们分别使用CPLEX求解器和提出的算法对各种实例进行了计算性能比较,并对关键参数进行了敏感性分析,提供了管理洞察。第6节对全文进行了总结。

章节摘录

文献综述

近年来,各大公司率先在配送服务中使用了无人机,从而推动了无人机路线研究的显著增加(Tan等人,2025年)。然而,大多数这些研究集中在城市最后一公里配送上(Bektur,2024年;Lemardelé等人,2021年;Gentili等人,2022年)。这种关注点与电子商务的发展趋势不符,因为农村地区的需求正在显著增长。因此,学术界越来越关注探索无人机在农村物流中的应用

问题描述

在本节中,我们定义了LRP-DS并描述了其基本假设。该模型包括无人机站点的位置、卡车路线以及选择由无人机服务的客户。假设卡车位于一个仓库,提供了一组客户和多个潜在的无人机站点位置。目标是确定卡车和无人机操作的可行路线,以最小化服务所有客户的总成本。

双层启发式算法

鉴于LRP-DS的NP难性质,解决大规模实例需要高效的启发式方法。我们提出了一种双层启发式算法(GACS),该算法结合了用于上层无人机站点位置分配的遗传算法(GA)和用于下层卡车路径分配的蚁群系统(ACS)算法。算法的总体框架如图3所示。

计算实验

本节介绍了两种实验,用于评估所提出模型的有效性和算法的性能。此外,还进行了敏感性分析,以获得实用的农村物流管理方法。GACS算法使用Python实现,数学模型使用CPLEX 12.9求解。实验在配备1.8 GHz Intel Core i5-8250 CPU和8 GB RAM的个人计算机上进行。

结论与未来工作

本文研究了农村地区具有多个无人机站点的卡车和无人机定位-路径问题,这是随着无人机配送技术的发展和应用而出现的新挑战。为此问题制定了一个MILP模型,然后将其分解为上层无人机站点位置模型和下层卡车配送路径优化模型。根据问题的特点,开发了一种双层启发式算法(GACS)。

CRediT作者贡献声明

吴丽荣:写作——审稿与编辑、方法论、概念化。张航:写作——初稿、软件、方法论。王泽浩:验证、方法论。张元凯:监督、项目管理、资金获取。王素丽:可视化、软件。

资金支持

本研究得到了中国国家重点研发计划(2023YFE0115600);国家自然科学基金一般项目(72542014;72571013;72501162;72101230);国家自然科学基金重大项目(72394374);国家自然科学基金创新研究群体(72288101)的支持。

利益冲突声明

作者声明他们没有已知的竞争性财务利益或个人关系可能影响本文所述的工作。
相关新闻
生物通微信公众号
微信
新浪微博
  • 搜索
  • 国际
  • 国内
  • 人物
  • 产业
  • 热点
  • 科普

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号