市区内卡车与无人机协同配送路径优化研究

陈添博，谢宝玲（沈阳工业大学 化工装备学院，辽宁 辽阳 111000）

0 引言

近年来，随着经济的不断进步与物流业的快速发展，人们的需求也逐渐增加，对物品的配送效率提出了更高的要求。传统的单一卡车配送所带来的问题逐渐暴露在面前，不但耗时长、效率低进而增加了时间成本，而且还会加重环境污染问题，不符合我国低碳环保的发展理念。随着无人机研发技术逐渐成熟，制造成本大幅降低，无人机[1]在各个领域得到了广泛应用，除军事领域外，还包括农业植保、电力巡检、警用执法、地质勘探以及应急救援等民用领域。但单单使用无人机配送的缺点也十分明显，如无人机续航时间不够长、有区域配送限制、有潜在的不安全性等。为了整合两者单一配送的优势、规避存在的劣势，提出“卡车与无人机协同配送”的模式，卡车仅仅作为无人机的移动配送站点，由无人机进行末端配送，保证安全的同时高效地将所需货品送到需求点。

目前看来，国外学者Murray 和Chu[2]提出了两种数学规划模型，分别是PDSTSP 模型和FSTSP 模型，两种模型的区别主要在于PDSTSP 模型是无人机与卡车分别同时进行配送，FSTSP 模型是卡车搭载无人机进行配送。而我国对于卡车与无人机协同配送的模式还在初步研究中，集中在“最后一公里”和农商配送的领域较多，并且主要致力于降低成本这一经济目标。本文综合考虑了现有的研究内容，为了进一步优化卡车与无人机协同配送模型，将围绕以下两点核心问题展开实证研究：（1）本文的研究对象是对市区内的客户点配送，扩展了现有研究对象的范围。（2）本文将时间作为首要目标，对卡车单独配送和卡车与无人机协同配送分别做路径规划，进而对比分析证明卡车与无人机协同配送的高效性。

1 卡车-无人机问题建模

1.1 问题描述

J 公司是一家拥有雄厚的综合服务实力的第三方物流企业，有关加急配送商品的任务承接是J 公司所有项目中的重要组成之一。然而在城市中，经常会遇到交通拥堵、道路限行、车辆限号等一系列不可控问题，即使加急单的金额高、数量多，能够提高公司效益，但为了保证服务的标准性J 公司无法承包更多的加急单任务，损失了一大批潜在客户。

为了解决这类问题，J 公司在无人机方面投入大量的时间、金钱和精力进行研发，目前，J 公司在无人机领域的技术相当成熟，已经获得相关部门许可能够进行试运营。然而仅仅采用无人机配送加急货物，虽然能够在配送过程中不受路面交通的影响，从而一定程度上降低收货延误的风险，但是无人机随处停放和起飞很容易在市区发生危险。因而J 公司将采取卡车与无人机协同的方式对加急单进行配送。

为了方便研究，对问题进行简化，根据J 公司的企业实力以及配送中实际存在的问题，做出如下假设：

（1）客户点坐标需求已知，且卡车物资量满足需求，所有客户点均被访问。

（2）卡车可携带多架同质无人机配送，无人机只能当卡车在停靠站点处于停留状态时被发射和收集。

（3）只要不违反无人机的电量及负载限制，可一次服务多个客户点。

（4）同一架无人机只能返回搭载其的卡车，即回收无人机的站点与发射站点相同。

（5）无人机返回卡车进行更换物资、电池或充电等工作，卡车仅作为无人机的移动配送中心，不参与配送。

（6）每个站点只能被卡车访问一次，客户点也只能被无人机服务一次。

（7）无人机充电、更换电池以及装卸包裹时间不考虑，装卸无人机时间也不考虑，但无人机设置最大飞行时间。

（8）无人机只要返回卡车均进行电池更换或充电，保证每次以满电形式进行配送。根据所提出的研究假设，对模型的符号进行定义，如表1 所示。

表1 模型符号定义

1.2 建立模型

根据问题描述和参数定义，构建以下模型：

目标函数：

式（1）表示完成所有客户的配送任务后，卡车返回到配送中心的总配送时间最小。

卡车路径约束：

式（2）表示卡车从配送中心出发并返回，且全程只有一次；式（3）表示车辆路径的连续性；式（2）和式（3）共同表示卡车在行驶过程中流量平衡。式（4）和式（5）表示卡车到达站点j 的时间等于卡车离开上一个站点i 的时间与i,j 间的旅行时间之和。

无人机路径约束：

式（6）确保每个客户点由一架无人机服务；式（7）保证无人机的连续性；式（8）表示无人机的行驶路径流量平衡；式（9）和式（10）表示无人机到客户点k 的时间等于无人机离开上一客户点i 的时间与i,k 间的旅行时间之和；式（11）确保无人机离开客户点k 前需要为客户点服务。

卡车与无人机协同约束：

式（12）和式（13）表示无人机在对客户点进行配送时，只能从车上发射；式（14）表示从站点j 发射的无人机在完成配送后返回卡车的时刻；式（15）保证无人机无法直接飞回配送中心；式（16）保证无人机无法从配送中心发射到客户点。

卡车去子回路约束：

式（17）和式（18）是为了消除子回路，确保卡车行驶路线正确。

决策变量：

表示变量的取值范围、二进制和非负性。

1.3 数据处理

J 公司使用一辆卡车搭载三架同质无人机的方式向某区域内的17 个客户点进行配送。已知客户点、停靠站点、配送中心的实际坐标，以及每个客户点所需的货物重量，数据如表2 所示。其中序号1 表示配送中心坐标，序号2-18 表示客户点坐标，序号19-27 表示停靠站点坐标。

表2 客户配送数据

1.4 实验结果分析

本文所研究的卡车与无人机协同配送问题属于NP 难问题，为此，将用智能优化算法求解此类约束条件较多的组合优化模型问题。由于遗传算法的鲁棒性强、适用的范围较广并且较容易实现，然而其易早熟并且搜索能力较差的缺点也同样是不可忽略的。因此，针对本文所涉及的范围以及模型的难易度，将采取单亲遗传算法进行求解，遗传算子仅包括选择和变异，由基因个体内部完成进化，不存在交叉算子，提高了计算效率。

以时间最短为目标，分别采取两种配送方式规划路径，即仅由卡车单独配送的路径，如图1 所示，以及由卡车与无人机协同配送的路径，如图2 所示，并获得卡车和无人机协同配送路径的结果，如表3 所示。

图1 卡车单独配送路径

图2 卡车与无人机协同配送路径

表3 卡车与无人机系统配送路径结果图

当卡车单独配送时，在城市内卡车的运行速度为45km/h，在每个客户点进行配送的时间为4min，遇到红灯进行等待或其他突发事故的灵活时间可视为15min，计算可得仅由卡车配送所有客户点至结束的时间为3.38h。

当卡车与无人机协同配送时，由卡车行走至全部的停靠站点，其运行速度仍视为45km/h，由无人机对客户点进行配送，实验中所选取的三架同质无人机的运行速度均为60km/h，携带包裹重量均不超过5kg，发射和回收无人机的时间均为1min，在客户点的服务时间均为1min，遇到红灯进行等待或其他突发事故的灵活时间可视为10min，经过计算可以得出卡车在经过每一站点的时间约为1.37h，无人机对客户点进行配送的时间约为0.8h，总体配送完成回至仓库的总时间为2.17h。

经过对比可知，首先，卡车和无人机协同配送后，由于卡车只需要行驶至停靠站点，那么行驶路程变短后的行驶时间降低的同时灵活处理时间也会降低；其次，由无人机派送包裹后，在保证配送准确率的同时提高了配送包裹的效率；最后，在完成配送任务的总时间上共节省了1.21h，符合预期。

2 结束语

本文基于卡车与无人机协同配送的模式，在市区内以J 公司加急物品配送业务为研究对象进行案例分析，目标是尽可能的缩短时间，提高配送效率及降低延误的可能性。通过单亲遗传算法的求解，研究表明：（1）采取卡车与无人机协同配送的模式比单卡车配送更为省时，并且安全性和可靠性也有一定的保障，一定程度上可以增加企业效益与信任度。（2）以时间最短为主要研究目标的卡车与无人机协同配送路径得以实现，可以类比与其他情境再做研究。