科技和产业

变量符号	变量含义
N	客户节点集合,$N=\{\mathrm{1,2},\dots,i,\dots,j,\dots,n\};n$为节点总数
O	送货公司仓库
K	车辆集合,$K=\{\mathrm{1,2},\dots,k\},k$即车辆总数
U	无人机集合,$U=\{\mathrm{1,2},\dots,u\},u$为无人机总数
q_i	为客户i配送的货物量
f	配送货物量的单位收益
[e_i,l_i]	客户i的允许配送时间窗, e_i为起始时间窗,l_i为终止时间窗
T_max	无人机可飞行的最长时间
${Q}_{max}^{v}$	车辆装载货物的最大容量
${Q}_{max}^{u}$	无人机的装载货物的最大容量
p	服务客户超出时间窗的单位惩罚
${t}_{ij}^{v}$	运货车辆从节点i前往节点j的行驶时间
${t}_{ij}^{u}$	无人机从节点i前往节点j的行驶时间
${\delta }_{i}^{k}$	运货车辆k访问节点i的车载货物量
${\delta }_{i}^{u}$	无人机u访问节点i的无人机货物量
${w}_{i}^{k}$	客户节点i被运货车辆k访问的时间
${w}_{i}^{u}$	客户节点i被无人机u访问的时间

变量符号	变量含义
N	客户节点集合,$N=\{\mathrm{1,2},\dots,i,\dots,j,\dots,n\};n$为节点总数
O	送货公司仓库
K	车辆集合,$K=\{\mathrm{1,2},\dots,k\},k$即车辆总数
U	无人机集合,$U=\{\mathrm{1,2},\dots,u\},u$为无人机总数
q_i	为客户i配送的货物量
f	配送货物量的单位收益
[e_i,l_i]	客户i的允许配送时间窗, e_i为起始时间窗,l_i为终止时间窗
T_max	无人机可飞行的最长时间
${Q}_{max}^{v}$	车辆装载货物的最大容量
${Q}_{max}^{u}$	无人机的装载货物的最大容量
p	服务客户超出时间窗的单位惩罚
${t}_{ij}^{v}$	运货车辆从节点i前往节点j的行驶时间
${t}_{ij}^{u}$	无人机从节点i前往节点j的行驶时间
${\delta }_{i}^{k}$	运货车辆k访问节点i的车载货物量
${\delta }_{i}^{u}$	无人机u访问节点i的无人机货物量
${w}_{i}^{k}$	客户节点i被运货车辆k访问的时间
${w}_{i}^{u}$	客户节点i被无人机u访问的时间

算例信息	无人机与货运车辆并行配送	无人机单独配送	货运车辆单独配送
算例	算例个数	收益/ 元	惩罚/ 元	求解时间/s	收益/ 元	惩罚/ 元	求解时间/s	收益/ 元	惩罚/ 元	求解时间/s
C101-C109	9	179 000	1 082.89	28.71	68 666.67	2 078.70	1.27	179 000	5 241.85	40.55
C201-C208	8	179 000	110.25	34.35	73 875.00	498.09	1.99	179 000	128.99	58.41
R101-R112	12	144 100	457.56	31.20	59 191.67	311.17	0.96	144 100	2 102.17	52.66
R201-R211	11	144 100	16.24	33.75	79 818.18	55.58	2.77	144 100	75.08	51.64
RC101-RC108	8	172 100	330.24	28.28	49 675.00	200.16	0.85	172 100	1627.43	47.86
RC201-RC208	8	172 100	24.31	33.22	51 000.00	6.08	1.15	172 100	174.41	54.97

算例信息	无人机与货运车辆并行配送	无人机单独配送	货运车辆单独配送
算例	算例个数	收益/ 元	惩罚/ 元	求解时间/s	收益/ 元	惩罚/ 元	求解时间/s	收益/ 元	惩罚/ 元	求解时间/s
C101-C109	9	179 000	1 082.89	28.71	68 666.67	2 078.70	1.27	179 000	5 241.85	40.55
C201-C208	8	179 000	110.25	34.35	73 875.00	498.09	1.99	179 000	128.99	58.41
R101-R112	12	144 100	457.56	31.20	59 191.67	311.17	0.96	144 100	2 102.17	52.66
R201-R211	11	144 100	16.24	33.75	79 818.18	55.58	2.77	144 100	75.08	51.64
RC101-RC108	8	172 100	330.24	28.28	49 675.00	200.16	0.85	172 100	1627.43	47.86
RC201-RC208	8	172 100	24.31	33.22	51 000.00	6.08	1.15	172 100	174.41	54.97

基于农村快递需求分布特征的货运车辆与无人机并行配送优化研究

PDF下载

王超峰 , 公维鑫

科技和产业 | 科技创新 2025,25(7): 82-87

收起

科技和产业 | 科技创新 2025, 25(7): 82-87

基于农村快递需求分布特征的货运车辆与无人机并行配送优化研究

全屏

王超峰, 公维鑫

作者信息

中国民用航空飞行学院机场学院, 四川广汉 618307

王超峰(1981—),男,四川成都人,博士,副教授,研究方向为交通运输规划与管理。

通讯作者:

公维鑫(1999—),男,山东临沂人,硕士研究生,研究方向为交通运输规划与管理。

Research on the Optimization of Parallel Delivery by Cargo Vehicles and Drones Based on the Distribution Characteristics of Rural Demand

Chaofeng WANG, Weixin GONG

Affiliations

Airport College, Civil Aviation Flight University of China, Guanghan 618307, Sichuan, China

出版时间: 2025-04-10

文章导航

摘要

收起

面对农村日益增长的物流配送需求,优化农村物流末端配送模式、降低配送成本、提升配送服务质量成为亟待解决的问题。基于送货车辆与无人机并行配送模式,考虑农村地区物流配送特点,以总配送利润最大化为目标,构建考虑农村地区特征的车辆与无人机并行配送模型。采用改进的蚁群算法进行求解,通过Solomon算例验证算法的可行性。研究结果表明,货运车辆与无人机并行配送与传统货车无人机单独配送相比具有明显优势。

关键词

农村电商物流 / 路径规划 / 并行配送 / 蚁群算法

Abstract

收起

In response to the increasingly growing logistics delivery demands in rural areas, optimizing the last-mile delivery model, reducing delivery costs, and improving service quality have become urgent issues. Based on a parallel delivery model using delivery vehicles and drones, and considering the characteristics of logistics distribution in rural areas, aims to maximize total delivery profit by constructing a parallel delivery model that incorporates the specific features of rural areas. An improved ant colony algorithm was employed to solve the model, and the feasibility of the algorithm was validated using Solomon benchmark instances. The research results demonstrate that the parallel delivery of vehicles and drones has significant advantages over the traditional single-mode delivery of vehicles or drones.

Key words

rural E-commerce logistics / route planning / parallel delivery / ant colony algorithm

引用本文

王超峰, 公维鑫. 基于农村快递需求分布特征的货运车辆与无人机并行配送优化研究. 科技和产业, 2025 , 25 (7) : 82 -87 .

Chaofeng WANG, Weixin GONG. Research on the Optimization of Parallel Delivery by Cargo Vehicles and Drones Based on the Distribution Characteristics of Rural Demand[J]. Science Technology and Industry, 2025 , 25 (7) : 82 -87 .

正文

收起

现今中国农村地区经济发展迅速,公路等基础设施逐渐完善,农村电商经济也随之发展起来,随之而来的是日益增长的物流货物运输需求的快速增长。然而农村地区由于偏远或需求分布不均匀,容易带来更高的运输成本。因此,如何改进农村物流末端配送模式,使其适应飞速发展的农村互联网经济成为亟须解决的问题。近年无人机技术的兴起为解决上述问题提供了新的思路。无人机和货运运货车辆相对单独使用无人机或单独使用货运运货车辆有着明显的优势,联合配送既能保证使用大容量可行驶范围广的运货车辆被有效使用,还能借用无人机完成近距离零散的配送需求,减少配送运货车辆的往返次数和行程,从而保证配送完成度和节约配送时间和成本。

无人机配送业务流程与传统物流业务流程相比更具可行性^[1-3]。许菱等^[4]针对无人机与车辆协同配送模式构建了一个混合整数规划模型并设计一种两阶段算法对无人机与车辆协同配送路径优化问题进行求解。现有运货车辆与无人机并行配送问题的研究中,最早由Murray和Chu^[5]优化了无人机和送货卡车在这一包裹递送新模式中的路由和调度的理论问题(PDSTSP),并建立了两个混合整数线性规划模型以及两种简单而有效的启发式求解方法,以解决实际规模的问题。Ham^[6]针对无人机并行配送问题,提出了变量排序启发式方法求解该问题。Kim和Moon^[7]提出了考虑存放无人机和充电设备的无人机站的卡车-无人机系统(TSP-DS),以克服无人机飞行距离的限制,并基于混合整数编程提出一种分解方法有效处理 TSP-DS问题。Schermer等^[8]在Kim和Moon^[7]研究基础上,建立了一个针对旅行推销员无人机站定位问题(TSDSLP),建立了一个混合整数规划模型。Mbiadou等^[9]针对并行无人机调度旅行推销员问题的启发式解决方案。提出了一种写先将解决方案转换为客户序列的编码再将解决方案转换为客户序列的解码两步迭代启发式。Raïssa等^[10]针对并行无人机调度多重旅行推销员问题提出了混合整数线性规划公式和简单的分支切割方法以及一种混合元启发式求解该问题。综上所述,现有的无人机与车辆联合配送优化研究主要集中于通过混合整数规划模型及精确和启发式算法进行求解,算法以构造式启发和邻域搜索为主,较少涉及人工智能方法。且总体而言,对农村快递需求特征的深入分析及其路径优化的研究仍显不足。

因此,本文针对农村地区运货车辆与无人机并行配送优化问题,提出一个混合整数规划模型,对蚁群算法进行改进设计,并通过Solomon算例来验证模型的合理性和算法的可行性。

1 问题描述与提出

收起

1.1 问题描述

农村地区与城镇地区相比,最明显的特点就是农村地区的人口非常松散,偏远地区的人口更甚,并且居民会以村落呈聚居状态。由于农村的消费结构限制,农村地区的快递需求量相对不稳定,并且某些农村地区位于偏远山区,导致农村网点对顾客进行配送时,单次派件的路程非常远,若地区交通不便需要绕较多的路才能到达,一旦配送时顾客无法立即收货还需要进行二次配送,会导致农村物流配送成本较高。而农村物流较高的配送成本会影响农村末端网点提供物流服务的积极性,这样一来,顾客对物流配送服务满意度会大大降低,不利于促进农村网点的发展。实际配送过程中,农村地区货车配送存在资源浪费、效率低下等问题,并且顾客点越分散,车辆消耗的能源越多,碳排放量越高,在相同情况下,无人机的消耗会小很多。但如果无人机配送距离过长,也会造成能源消耗过高的情况,无人机与货车联合配送可以取长补短,提高效率,更加适合农村居民聚居的场景。

无人机与运货车辆的联合配送模式有很多,分别是运货车辆与无人机协同配送、运货车辆与无人机并行配送、运货车辆支持无人机配送、无人机支持运货车辆配送以及混合配送模式。本文主要研究运货车辆与无人机并行配送模式,如图1所示。运货车辆与无人机并行配送是指货运运货车辆和无人机均参与配送, 货运运货车辆和无人机都作为配送运货车辆,从运货送货服务公司出发,去配送客户并返回运货送货服务公司。在这种模式下,往往由无人机完成近距离形成的松散需求,由货运运货车辆完成长距离的集中配送,并且该模式下相比协同配送车辆路径规划问题,可以大幅缩短完工时间,非常适合郊区仓库、农村园区的配送,无人机服务农村周边客户, 运货车辆服务往返城乡之间的客户。

1.2 问题提出

基于车辆路径问题, 对考虑配送成本与农村区域限制的货车和无人机联合配送问题进行研究。以总配送利润最大化为优化目标, 考虑服务客户的收益和违反时间窗的惩罚成本,建立无人机和货运运货车辆并行配送路径优化模型。无人机和货运运货车辆并行配送意味着所有无人机和运货车辆都可以同时运送包裹。无人机或货运车辆需要装载一定货物,从运货送货服务公司出发,决定服务客户的路线,为客户配送货物,并最终返回运货送货服务公司。其中无人机的载量和行驶时间有限,只能装载较少的货物,并行驶较短的距离。而货运运货车辆的载量和行驶时间则相对无人机更大。已知无人机和运货车辆的容量,无人机的最大行驶时间,无人机或运货车辆配送单位货物量的收益,无人机或运货车辆在各节点之间的行驶时间。部分客户因为居住在农村地区交通不完善的区域只能由无人机为其提供配送服务。由于天气与空域环境无人机无法飞过的区域只能由货车为其提供配送服务。

2 模型构建

收起

2.1 模型假设

针对上述问题,为便于研究、简化模型,设置如下条件假设:①每个客户节点只能由一辆货车或一架无人机提供配送服务;②配送中心有多辆同一型号的货车,每个联合配送中转站内有多架同一型号的无人机;③无人机的最大承重能力和最大飞行距离是已知的;④一架无人机每次从联合配送中转站出发时都可以装载多个包裹,且可以服务多个客户点;⑤无人机续航时间不受任何因素影响;⑥无人机和货车均匀速运动。

2.2 变量定义

2.2.1 基础变量

基础变量见表1。

2.2.2 决策变量

$\begin{array}{l}{x}_{ij}^{k}=\left\{\begin{array}{l}1,　\mathrm{运}\mathrm{货}\mathrm{车}\mathrm{辆}k\mathrm{从}\mathrm{节}\mathrm{点}i\mathrm{到}\mathrm{节}\mathrm{点}j\\ 0,　\mathrm{否}\mathrm{则}\end{array}\right.\\ {y}_{ij}^{u}=\left\{\begin{array}{l}1,　\mathrm{无}\mathrm{人}\mathrm{机}u\mathrm{从}\mathrm{节}\mathrm{点}i\mathrm{到}\mathrm{节}\mathrm{点}j\\ 0,　\mathrm{否}\mathrm{则}\end{array}\right.\end{array}$

2.3 目标函数和约束条件

(1)

${C}_{1}={\sum }_{i\in N}^{}{\sum }_{k\in K}^{}{\sum }_{j\in N\bigcup O}^{}{x}_{ij}^{k}\{f{q}_{i}-p[max(0,{e}_{i}-{w}_{i}^{k})+max(0,{w}_{i}^{k}-{l}_{i})\left]\right\}$

(2)

${C}_{2}={\sum }_{i\in N}^{}{\sum }_{u\in U}^{}{\sum }_{j\in N\bigcup O}^{}{y}_{ij}^{u}\{f{q}_{i}-p[max(0,{e}_{i}-{w}_{i}^{u})+max(0,{w}_{i}^{u}-{l}_{i})\left]\right\}$

(3)C=max(C₁+C₂)

(4)

${\sum }_{k\in K}^{}{\sum }_{j\in N\bigcup O}^{}{x}_{ij}^{k}+{\sum }_{u\in U}^{}{\sum }_{j\in N\bigcup O}^{}{y}_{ij}^{u}\le 1,\forall i\in N$

(5)

${\sum }_{j\in N\bigcup O}^{}{x}_{ij}^{k}={\sum }_{j\in N\bigcup O}^{}{x}_{ji}^{k},\forall i\in N\bigcup O,\forall k\in K$

(6)

${\sum }_{j\in N\bigcup O}^{}{y}_{ij}^{u}={\sum }_{j\in N\bigcup O}^{}{y}_{ji}^{u},\forall i\in N\bigcup O,\forall u\in U$

(7)

${\delta }_{j}^{k}\ge {\delta }_{i}^{k}-{q}_{i}+M({x}_{ij}^{k}-1),\forall i\in N,\forall j\in N\bigcup O,\forall k\in K$

(8)

${\delta }_{j}^{u}\ge {\delta }_{i}^{u}-{q}_{i}+M({y}_{ij}^{u}-1),\forall i\in N,\forall j\in N\bigcup O,\forall u\in U$

(9)

${w}_{j}^{k}\ge {w}_{i}^{k}+{t}_{ij}^{v}+M({x}_{ij}^{k}-1),\forall i\in N\bigcup O,\forall j\in N\bigcup O,\forall k\in K$

(10)

${w}_{j}^{u}\ge {w}_{i}^{u}+{t}_{ij}^{u}+M({y}_{ij}^{u}-1),\forall i\in N\bigcup O,\forall j\in N\bigcup O,\forall u\in U$

(11)

$0\le {\delta }_{i}^{k}\le {Q}_{max}^{v},\forall i\in N\bigcup O,\forall k\in K$

(12)

$0\le {\delta }_{i}^{u}\le {Q}_{max}^{u},\forall i\in N\bigcup O,\forall u\in U$

(13)

$\sum_{i \in N \cup O j \in N \cup O} \sum_{i j}^{u} t_{i j}^{u}＜T_{\max }, \forall u \in U$

式中:C₁为货车的总配送收益;C₂为无人机的总配送收益;C为目标函数,表示货车与无人机并行配送的总收益;式(4)表示每个客户最多被无人机或运货车辆访问一次;式(5)和式(6)表示货车或无人机配送结束后即离开;式(7)和式(8)表示货车和无人机的货物载运量约束;式(9)和式(10)表示货车和无人机配送货物的时间约束;式(11)和式(12)表示货车和无人机的运载容量限制约束;式(13)表示无人机飞行时间限制约束。

3 求解算法设计

收起

3.1 可行路径的构建

无人机或车辆从送货服务公司出发,并不断决策下一阶段选择的节点,即当前节点为i使用式(14)改进的状态转移规则选择下一节点j。其中${\tau }_{ij}$为信息素浓度;η_ij=1/t_ij为能见度,t_ij为客户点i和j之间的行驶时间,无人机或车辆到达的时间为a_j。若a_je_j,车辆需等待一段时间才能开始服务,等待时间过长会影响配送效率、增加配送成本;若a_jl_j,则客户需求不能及时得到满足,配送服务质量受到影响^[11],通过改进遗传算法在状态转移概率中引入等待时间因素和时间窗跨度,使用式(15)计算等待时间wait_j。

(14)

$\text { wait }_{j}=\left\{\begin{array}{ll}e_{j}-a_{j}, & a_{j}＜e_{j} \\0, & e_{j}＜a_{j}＜l_{j} \\a_{j}-l_{j}, & l_{j}＜a_{j}\end{array}\right.$

(15)

$j=\left\{\begin{array}{l}\underset{j\in {N}_{i}^{k}}{max}\left\{\right[{\tau }_{ij}{]}^{\alpha }\left[{\eta }_{ij}{]}^{\beta }\right[1/({l}_{j}-{e}_{j}{\left)\right]}^{\gamma }[1/wai{t}_{j}{]}^{\eta }\},\\ 　　　　　　r\le {r}_{0}\\ {P}_{ij}^{k}=\frac{\left[{\tau }_{ij}{]}^{\alpha }\right[{\eta }_{ij}{]}^{\beta }[1/({l}_{j}-{e}_{j}{\left)\right]}^{\gamma }[1/wai{t}_{j}{]}^{\eta }}{{\sum }_{l\in {N}_{i}^{k}}^{}\{\left[{\tau }_{il}{]}^{\alpha }\right[{\eta }_{il}{]}^{\beta }\frac{1}{({l}_{j}-{e}_{j}{)}^{\gamma }{\left[\frac{1}{wai{t}_{l}}\right]}^{\delta }}\}},\\ 　　　　　　r＞{r}_{0}\end{array}\right.$

式中:状态转移概率${p}_{ij}^{k}$为人工蚂蚁k从i点移动到j点的概率;r为在[0,1]区间内的随机参数;${N}_{i}^{k}$为车辆或无人机k从i点出发可以访问的所有客户j的集合。令一只蚂蚁从送货服务公司出发,按照式(15)依次选择下一待访问节点j。若找不到这样的节点j,则返回送货服务公司,蚂蚁再依次进行上述步骤。当所有顾客点都被访问过时,一条可行路径构造完毕^[11]。

3.2 信息素调整策略与解的局部优化

当蚂蚁构造完一条可行路径R时,将它与全局最优路径R^*进行比较。

(1)若R的用车数V_R大于R^*的用车数V_R^*,则将R中所有边上的信息素进行大量蒸发,令${\tau }_{ij}^{new}={(1-\rho )}^{3}{\tau }_{ij}^{old},\forall (i,j)\in R,$其中,ρ为信息素蒸发率,0＜ρ≤1。

(2)若R的用车数V_R等于R^*的用车数V_R^*,但R的距离/时间费用L_R大于等于R^*相应的费用L_R^*,则将R中所有边上的信息素进行少量蒸发,令${\tau }_{ij}^{new}=(1-\rho ){\tau }_{ij}^{old},\forall (i,j)\in R。$

(3)若R的用车数V_R等于R^*的用车数V_R^*,且R的距离/时间费用L_R小于R^*相应的L_R^*,或R的用车数V_R小于R^*的用车数V_R^*时,则R优于R^*,更新全局最优解,令R^*=R。

对当前全局最优解用2-opt及2-opt^*进行局部优化,其中2-opt和2-opt^*分别对车辆和无人机不同和相同路径之间的两两弧的交换算子,如图2所示,若全局最优解有改进,则更新全局最优解。对于R^*中所有边上的信息素进行更新,有${\tau }_{ij}^{new}={\tau }_{ij}^{old}+\Delta {\tau }_{ij},\forall (i,j)\in {R}^{*}。$其中$\Delta {\tau }_{ij}=S/{L}_{{R}^{*}},S$为一常数。

3.3 算法具体步骤

步骤1:迭代步数t=0,初始化控制参数,将所有蚂蚁放置在起点。

步骤2:令一蚂蚁从送货服务公司出发,按照式(15)选择下一待访问节点j,记录访问过的点,构造可行路径R,将R与全局最优路径R^*进行比较。

步骤3:若R的用车数V_R大于R^*的用车数V_R^*,令${\tau }_{ij}^{new}={(1-\rho )}^{3}{\tau }_{ij}^{old},\forall (i,j)\in R,$转步骤6。

步骤4:若${V}_{R}={V}_{{R}^{*}},{L}_{R}\ge {L}_{{R}^{*}}$,令${\tau }_{ij}^{new}=(1-\rho ){\tau }_{ij}^{old},\forall (i,j)\in R,$转步骤6。

步骤5:若V_R=V_R^*,L_R＜L_R^*,或V_R＜V_R^*,令R^*=R。

步骤6:用2-opt及2-opt^*优化R^*,更新全局最优路径为R'^*。

步骤7:更新全局最优路径R^*的信息素,令${\tau }_{ij}^{new}={\tau }_{ij}^{old}+\Delta {\tau }_{ij},\forall (i,j)\in {R}^{*}。$

步骤8:若${\tau }_{ij}^{new}＞{\tau }_{max},$令${\tau }_{ij}^{new}={\tau }_{max}$; 若${\tau }_{ij}^{new}＞{\tau }_{min},$令${\tau }_{ij}^{new}={\tau }_{min}。$

步骤9:若t≤T,则t=t+1,清空记录表,转步骤2;否则终止算法,输出最终结果。

4 算例验证

收起

4.1 实验参数设置

应用MATLAB软件,以Solomon的集中分布算例C101-C109、C201-C208,随机分布算例R101-R112、 R201-R211,集中与随机分布算例RC101-RC108、 RC201-RC208作为实验算例。在Solomon算例中设定无人机的数量为总车辆的一半,设定无人机的容量是车辆容量的20%,无人机行驶时间限制为60,其他算例和算法参数设定如下:f为服务单位需求的收益取值100,p为等待时间的惩罚系数取值为1,最大迭代步数T设定为5,蚂蚁数量N为10,制转移规则的参数r₀为0.5,信息素启发式因子α设定为2,行驶时间启发因子β取值为3,时间窗跨度启发式因子γ取值为3,等待时间启发式因子$\delta $设定为1,O为用于更新最优解信息素的常数,设定为5,初始节点间信息素浓度${\tau }_{ij}$取值为1,蒸发率ρ取值0.85,c为最大最小蚁群算法中的常数,设定为200,n₀为每代2-opt或2-opt^*的使用次数设定为5,并根据算例选取客户节点个数n进行运算。

4.2 联合配送模式与单独配送模式的成本对比

为了验证和分析无人机与运货车辆的联合配送模式的优势,使用改进蚁群算法分别对不同车辆的使用情况下的优化结果做对比,结果见表2。根据表2可知,无人机与货运车辆并行配送模式能相对无人机单独配送获取更多的收益,同时能相对任何单独配送模式减少因为到达时间不在时间窗之内的惩罚。此外从求解时间上,尽管改进蚁群算法在无人机与货运车辆并行配送模式下的求解时间多于单独无人机配送求解时间,但是却优于货运车辆单独配送的求解时间。结果表明,货车无人机联合配送模式在收益、惩罚和求解时间方面表现最佳。

无人机单独配送的惩罚较高,尤其是在C101-C109和 C201-C208算例中,分别达到2 078.70、498.09元货运车辆单独配送在某些算例中也表现出高惩罚,如C101-C109 的惩罚为5 241.85元。相较之下,联合配送模式在所有算例中的惩罚均较低,显示出其在处理复杂任务时的优势。

在求解时间方面,联合配送模式整体上具有较短的求解时间。无人机单独配送的求解时间较短,但相较于货车无人机并行配送存在惩罚较高的情况,说明单一无人机配送在稳定性方面不足。货运车辆单独配送的求解时间较长,特别是在 C101-C109和R101-R112算例中,求解时间分别为40.55、52.66 s,显示出其在调度复杂性上的劣势。

综上,联合配送模式在收益、惩罚和求解时间等综合指标上均表现优越,联合配送模式利用了无人机和货运车辆的优势互补,在提升收益的同时降低了惩罚和求解时间,而农村电商产业的发展要求末端配送环节产生更多的优化。近年成熟的无人机技术可以应用到农村电商物流末端的配送中,通过并行配送的模式,降低配送成本的同时降低配送等待时长,提升服务质量。

5 结论

收起

基于农村电商物流末端无人机与货运车辆的并行配送模式,考虑最大化送货服务公司的总利润,优化服务收益与等待时间惩罚。考虑无人机和货运车辆的容量与行驶时间限制,构建了无人机与货运车辆并行配送的混合整数规划模型,并设计了一个改进蚁群算法。使用改进的状态转移规则、信息素调整策略与解的局部优化策略改进传统蚁群算法。最后,通过算例和对比实验分析,验证了无人机与货运车辆的并行配送模式的可行性、模型和算法的有效性、相对单一配送模式在服务收益和质量上的优越性。

基金

收起

国家自然科学基金(71403225)
中央高校基本科研业务费(24CAFUC04013)

参考文献

收起

文献

收起

参考文献引证文献

排序方式：

[1]

贺井然, 何广军, 于学生. 基于改进蜂群算法的无人机路径规划[J]. 火力与指挥控制, 2021, 46(10): 103-106.

[2]

冯文静, 卢福强, 王素欣, 等. 考虑充电设施的无人机配送路径规划研究[J]. 控制工程, 2022, 11(6): 1-10.

[3]

林驿, 吕靖, 蒋永雷. 考虑交通时变特性的城乡快递无人机配送优化研究[J]. 计算机应用研究, 2022, 37(10): 2984-2989, 3013.

[4]

许菱, 杨林超, 朱文兴, 等. 农村电商物流下无人机与车辆协同配送路径优化研究[J]. 计算机工程与应用, 2024, 60(1): 310-318.

[5]

MURRAY

C C

, CHU

A G

. The flying sidekick traveling salesman problem: optimization of drone-assisted parcel delivery[J]. Transportation Research Part C: Emerging Technologies, 2015, 54: 86-109.

[6]

HAM

A M

. Integrated scheduling of m-truck, m-drone, and m-depot constrained by time-window, drop-pickup, and m-visit using constraint programming[J]. Transportation Research Part C: Emerging Technologies, 2018, 91: 1-14.

[7]

KIM

, MOON

. Traveling salesman problem with a drone station[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2019, 49(1): 42-52.

[8]

SCHERMER

, MOEINI

, WENDT

. The traveling salesman drone station location problem[C]// Advances in Intelligent Systems and Computing. Cham: Springer International Publishing, 2020: 1129-1138.

[9]

MBIADOU

S R G

, DEROUSSI

, FEILLET

, et al. An iterative two-step heuristic for the parallel drone scheduling traveling salesman problem[J]. Networks, 2018, 72(4): 459-474.

[10]

RAÏSSA

, MBIADOU

S R G

, DEROUSSI

, et al. The parallel drone scheduling problem with multiple drones and vehicles[J]. European Journal of Operational Research, 2022, 300(2): 571-589.

[11]

SAJID

, MITTAL

, PARE

, et al. Routing and scheduling optimization for UAV assisted delivery system: a hybrid approach[J]. Applied Soft Computing, 2022, 126: 109225.

2025年第25卷第7期

PDF下载

334

175

引用本文

BibTeX

文章信息

接收时间：2024-10-18
首发时间：2025-07-21
出版时间：2025-04-10

补充材料

相关文章

文章信息

作者

出版历史

收稿日期：2024-10-18

基金

国家自然科学基金(71403225)

中央高校基本科研业务费(24CAFUC04013)

作者信息

中国民用航空飞行学院机场学院, 四川广汉 618307

通讯作者:

公维鑫(1999—),男,山东临沂人,硕士研究生,研究方向为交通运输规划与管理。

参考文献

分享链接

https://castjournals.cast.org.cn/joweb/kjhcy/CN/1153992995247477083

分享至

全文二维码

扫描看全文

引用本文

BibTeX

本文的引用情况

2种不同金属材料的力学参数

科 Family	属数 Number of genus	种数 Number of species	占总种数比例 Percentage of total species (%)	属 Genus	种数 Number of species	占总种数比例 Percentage of total species (%)
鹅膏菌科Amanitaceae	2	11	5.26	鹅膏菌属 Amanita	10	4.78
小菇科 Mycenaceae	2	12	5.74	丝盖伞属 Inocybe	5	2.39
多孔菌科 Polyporaceae	8	14	6.70	蜡蘑属 Laccaria	5	2.39
红菇科 Russulaceae	3	23	11.00	小皮伞属 Marasmius	6	2.87
				小菇属 Mycena	11	5.26
				光柄菇属 Pluteus	5	2.39
				红菇属 Russula	17	8.13
				栓菌属 Trametes	5	2.39

关闭全屏

BibTeX
EndNote
RefWorks
TxT

变量符号	变量含义
N	客户节点集合,$N=\{\mathrm{1,2},\dots,i,\dots,j,\dots,n\};n$为节点总数
O	送货公司仓库
K	车辆集合,$K=\{\mathrm{1,2},\dots,k\},k$即车辆总数
U	无人机集合,$U=\{\mathrm{1,2},\dots,u\},u$为无人机总数
q_i	为客户i配送的货物量
f	配送货物量的单位收益
[e_i,l_i]	客户i的允许配送时间窗, e_i为起始时间窗,l_i为终止时间窗
T_max	无人机可飞行的最长时间
${Q}_{max}^{v}$	车辆装载货物的最大容量
${Q}_{max}^{u}$	无人机的装载货物的最大容量
p	服务客户超出时间窗的单位惩罚
${t}_{ij}^{v}$	运货车辆从节点i前往节点j的行驶时间
${t}_{ij}^{u}$	无人机从节点i前往节点j的行驶时间
${\delta }_{i}^{k}$	运货车辆k访问节点i的车载货物量
${\delta }_{i}^{u}$	无人机u访问节点i的无人机货物量
${w}_{i}^{k}$	客户节点i被运货车辆k访问的时间
${w}_{i}^{u}$	客户节点i被无人机u访问的时间

变量符号

变量含义

客户节点集合,$N=\{\mathrm{1,2},\dots,i,\dots,j,\dots,n\};n$为节点总数

送货公司仓库

车辆集合,$K=\{\mathrm{1,2},\dots,k\},k$即车辆总数

无人机集合,$U=\{\mathrm{1,2},\dots,u\},u$为无人机总数

q_i

为客户i配送的货物量

配送货物量的单位收益

[e_i,l_i]

客户i的允许配送时间窗, e_i为起始时间窗,l_i为终止时间窗

T_max

无人机可飞行的最长时间

${Q}_{max}^{v}$

车辆装载货物的最大容量

${Q}_{max}^{u}$

无人机的装载货物的最大容量

服务客户超出时间窗的单位惩罚

${t}_{ij}^{v}$

运货车辆从节点i前往节点j的行驶时间

${t}_{ij}^{u}$

无人机从节点i前往节点j的行驶时间

${\delta }_{i}^{k}$

运货车辆k访问节点i的车载货物量

${\delta }_{i}^{u}$

无人机u访问节点i的无人机货物量

${w}_{i}^{k}$

客户节点i被运货车辆k访问的时间

${w}_{i}^{u}$

客户节点i被无人机u访问的时间

算例信息	无人机与货运车辆并行配送	无人机单独配送	货运车辆单独配送
算例	算例个数	收益/ 元	惩罚/ 元	求解时间/s	收益/ 元	惩罚/ 元	求解时间/s	收益/ 元	惩罚/ 元	求解时间/s
C101-C109	9	179 000	1 082.89	28.71	68 666.67	2 078.70	1.27	179 000	5 241.85	40.55
C201-C208	8	179 000	110.25	34.35	73 875.00	498.09	1.99	179 000	128.99	58.41
R101-R112	12	144 100	457.56	31.20	59 191.67	311.17	0.96	144 100	2 102.17	52.66
R201-R211	11	144 100	16.24	33.75	79 818.18	55.58	2.77	144 100	75.08	51.64
RC101-RC108	8	172 100	330.24	28.28	49 675.00	200.16	0.85	172 100	1627.43	47.86
RC201-RC208	8	172 100	24.31	33.22	51 000.00	6.08	1.15	172 100	174.41	54.97

算例信息

无人机与货运车辆并行配送

无人机单独配送

货运车辆单独配送

算例

算例个数

收益/
元

惩罚/
元

求解时
间/s

收益/
元

惩罚/
元

求解时
间/s

收益/
元

惩罚/
元

求解时
间/s

C101-C109

179 000

1 082.89

28.71

68 666.67

2 078.70

1.27

179 000

5 241.85

40.55

C201-C208

179 000

110.25

34.35

73 875.00

498.09

1.99

179 000

128.99

58.41

R101-R112

144 100

457.56

31.20

59 191.67

311.17

0.96

144 100

2 102.17

52.66

R201-R211

144 100

16.24

33.75

79 818.18

55.58

2.77

144 100

75.08

51.64

RC101-RC108

172 100

330.24

28.28

49 675.00

200.16

0.85

172 100

1627.43

47.86

RC201-RC208

172 100

24.31

33.22

51 000.00

6.08

1.15

172 100

174.41

54.97