应用于求解协同配送的路径规划的粒子群优化方法和系统

1.本发明涉及物流配送技术领域，尤其是指一种应用于求解协同配送的路径规划的粒子群优化方法和系统。


背景技术：

2.随着我国经济的发展，物流行业迎来巨大腾飞。但根据大数据显示，“最后一公里”的物流配送成本已经占到总成本30％以上。促进物流降本增效，做好最后一公里路径规划是我国物流行业面临的挑战。无人机技术的快速发展为物流和运输领域的众多创新应用打开了大门，在防御、公共安全和保障、医疗保健、林业和农业都有应用。亚马逊在物流配送领域宣布使用无人机进行产品配送计划后，无人机用于产品配送受到了较多关注。传统的化石能源货车越来越受到限制，研究表明城市物流选择在电动化和自动驾驶等有效的干预措施下完成物流配送，可以将最后一公里排放和交通拥堵减少30％，有效助力实现“碳中和”；在经济层面，与例如货车等的传统运输工具相比，无人机运输成本更低。农村市场的消费潜力巨大，发展前景广阔，农村地广人稀、配送不便，但无人机可快速、低成本到达。新冠疫情的发展给交付带来更多挑战，尤其是粮食、杂货、家居用品甚至是医疗用品，都需要减少人与人的直接接触，而无人机运输可完美解决这一问题。所以无论是在城市物流运输还是在偏远农村市场中，如何解决传统货车配送与无人机协同配送的路径规划问题成为各运输行业研究的重点。
3.目前已经有很多研究解决货车路径规划问题的方法，然而很少有方法可以用来解决基于货车与无人机协同配送的路径规划问题。传统用于解决货车路径规划问题的方法有邻域搜索、禁忌搜索、遗传算法、蚁群算法等等。这些方法虽然可以解决传统货车路径规划问题，但是它们并不能解决基于货车与无人机协同配送的路径规划问题。因为在基于货车与无人机协同配送的路径规划问题中，无人机存在最大载货量与最大行程时间约束，以及与货车汇合以及分离同步的约束。此外，不像传统路径规划问题中所有客户点均由货车服务，在货车与无人机协同配送的路径规划问题中，部分满足无人机服务条件的客户点可能由无人机服务，可能由货车服务。不满足无人机服务条件的客户只能由货车服务。
4.粒子群优化算法(particle swarm optimization，pso)是在1995年由 eberhart和kennedy[1]一起提出的(详见文献“kennedy j,eberhart r. particle swarm optimization[c]//icnn95-international conference on neuralnetworks.ieee,1995.”)，它源于对鸟群捕食行为的研究。粒子群优化算法的基本核心是利用群体中的个体对信息的共享从而使整个群体的运动在问题求解空间中产生从无序到有序的演化过程，从而获得问题的最优解。在 2003年被wang[2]应用于求解tsp问题(traveling salesman problem，旅行商问题)(详见文献“k.p.wang,l.huang,c.g.zhou,w.pang,particleswarm optimization for traveling salesman problem,international conference onmachine learning and cybernetics 3(2003)1583
–
1585.”)。在之后的研究工作中，粒子群优化算法被广泛应用于求解带时间窗问题以及容量限制等各种tsp问题的变种。
[0005]
粒子群优化算法主要由以下几项部分组成：
[0006]
表1粒子群优化算法的参数构成表
[0007]
n群体规模c1，c2学习因子(加速常数)ω惯性权重v，v
max
粒子速度，粒子最大速度p
best
个体极值g
best
全局极值r1,r2[0,1]内的均匀随机数
[0008]
粒子群优化算法的流程如图1所示，基本流程包括：
[0009]
(1)初始化所有粒子、初始化它们的速度和位置，并且将粒子的历史最优p
best
设为当前位置，而群体中最优的粒子作为当前的g
best
；
[0010]
(2)在每一次迭代中，计算各个粒子的适应度函数值，对于每一个粒子而言、该位置即为问题的一个潜在解；
[0011]
(3)如果该粒子当前的适应度函数值比历史最优值好，那么历史最优将会被当前位置所替代；
[0012]
(4)如果该粒子的历史最优比全局最优好，全局最优将会被粒子的历史最优所替代；
[0013]
(5)对每个粒子i的第j维的速度和位置分别按照下面公式进行更新：
[0014]vij
(t+1)＝v
ij
(t)+c1r1(t)[p
ij
(t)-x
ij
(t)]+c2r2(t)[p
gj
(t)-x
ij
(t)]， x
ij
(t+1)＝x
ij
(t)+v
ij
(t+1)；
[0015]
其中，v
ij
(t)表示粒子i在t时刻的速度，i＝1,2,3
…
n；r1(t)、r2(t)表示是0 到1之间的均匀随机数，用于增加粒子飞行的随机性；p
ij
(t)表示粒子i在t 时刻的个体最优解，x
ij
(t)表示粒子i在t时刻的例子位置，p
gj
(t)表示t时刻群体最优解，x
ij
(t+1)表示t+1时刻粒子i更新后的位置。
[0016]
但是，现有技术中使用的粒子群优化算法的研究对象均为传统汽车，所有客户点均由货车完成配送服务，不考虑无人机可服务的节点以及无人机在货车服务客户点发射无人机与回收无人机的同步发布计算。传统粒子群优化算法也无法用于求解基于货车与无人机协同配送的路径规划问题。不能适应协同配送的约束，无法确定无人机访问节点、无法确定无人机出发点以及回收点、协调同步完成配送时间(无法求解)；并且传统粒子群优化算法局部搜索能力差，容易陷入局部最优。
[0017]
路径规划问题隶属于运筹学的研究范畴，是np-hard问题。在小规模问题中，建立如图2所示的货车和无人机协同配送的问题模型，包括6个顾客点，1个配送中心。建立该问题的混合整数规划模型，并将模型代码化输入到一般的商业求解软件中，可以很快的得到最优解，也就是精确结果。 cplex和gurobi是两款商用软件，他们内部所基于的核心算法是分支定界法。分支定界是一种精确求解方法，他能够适用于求解小规模的问题，但如果问题的规模变为12个顾客点，经测试商业求解软件在3600s无法求出精确解。如果问题规模扩大到40、50，那么商业求解软件是得不到最优解的，或者说以目前计算机的计算能力需要算上几百年。那么就需要设计一种方法，在较短的可接受的时间内，取得一个接近最优解的结
果，也就是近似解，这种不依赖于传统运筹学中精确求解的方法统称为启发式方法或者经验方法。目前一般货车的路径规划问题的研究已经趋于成熟，出现了一些比较有效的启发式求解方法，例如模拟退火、遗传算法、蚁群算法、粒子群算法、禁忌搜索等，这类方法可以用于求解大规模的路径规划问题，他所求的解是接近最优解的解，并且在绝大情况下可能就是最优解。但是在主体对象切换为货车与无人机协同配送时，上述的传统启发式方法不能有效适应并求解。无人机的出现，使得顾客点可能被无人机服务也可能被货车服务，且无人机需要工作人员在货车点发射并回收，使得出现了无人机发射点与无人机回收点，确定无人机服务节点与无人机路线大大增加的运算的次数。
[0018]
因此，传统的启发式算法除了不能求解基于货车与无人机协同配送的路径规划问题，在更加接近最优解和使得求解时间更短之间也不能达到平衡。如果想要更加接近最优解，那么需要增加迭代数，增加搜索量，这势必会增加计算机的处理时间；如果想要使得求解时间更短，那么需要减少搜索次数，最优解的质量也会受到影响，现有技术中没有有效的搜索机制来以有限的搜索次数寻找到质量更好的解。


技术实现要素：

[0019]
为此，本发明所要解决的技术问题在于克服现有技术中的不足，提供一种应用于求解协同配送的路径规划的粒子群优化方法和系统，可以实现对包括无人机和货车的协同配送的路径规划，并提高最优路径的质量、缩短求解时间。
[0020]
为解决上述技术问题，本发明提供了一种应用于求解协同配送的路径规划的粒子群优化方法，包括：
[0021]
建立包括货车和无人机协同配送的问题模型，初始化需要被服务的客户点的排列序列，初始化的排列序列中所有客户点均由货车进行配送；
[0022]
根据排列序列中的可以被无人机服务的客户点切分子例，使用无人机和货车对每个子例进行协同配送得到带无人机节点的排列序列；
[0023]
使用带有权重的粒子群优化算法和模拟退火法更新带无人机节点的排列序列得到最优路径。
[0024]
作为优选的，所述包括货车和无人机协同配送的问题模型，具体为：
[0025]
在一个区域内一辆货车搭载至少一架无人机为客户送货，每个客户点有自己的需求，货车与无人机均可以服务客户，模型目标为最短完成配送时间和最小化成本；
[0026]
满足的条件有：
[0027]
条件一：无人机每次出动只能访问一个客户，但在无人机飞行时货车可以访问多个客户；
[0028]
条件二：无人机在飞行时保持恒定飞行；
[0029]
条件三：无人机可以在某个客户节点由货车收集并再次出发；
[0030]
条件四：无人机无法在预设节点之间与货车汇合；
[0031]
条件五：任何货车都不得再次拜访任何客户；
[0032]
条件六：无人机路径在基地结束，结束后无人机将停止使用；
[0033]
条件七：无人机和货车在汇合状态行驶时，无人机由货车运输；
[0034]
条件八：不考虑无人机交付货物时间，发射与回收无人机时间恒定，无人机续航时
间恒定。
[0035]
作为优选的，所述根据排列序列中的可以被无人机服务的客户点切分子例，具体为：
[0036]
若客户点的配送需求小于无人机最大载货量，则将该节点定义为可由无人机服务节点；
[0037]
根据客户点中的可由无人机服务节点对仅由货车配送的初始化路径进行子例的切分，得到至少一个含有可由无人机服务节点的子例。
[0038]
作为优选的，所述子例包括一个所述可由无人机服务节点且所述子例包含的节点数大于等于3。
[0039]
作为优选的，所述使用无人机和货车对每个子例进行协同配送得到带无人机节点的排列序列，具体为：
[0040]
排列序列中的每个客户点包括配送到达时间和配送离开时间，对每个子例插入无人机节点，根据不同的无人机发射点与无人机回收点确定子例的货车路径以及无人机路径，计算在不同路径下子例完成配送的时间；
[0041]
若无人机回收点存在货车等待无人机到达或者无人机到达等待货车的情况，以该无人机回收点无人机到达时间和货车到达时间两者中的较大值作为该点的到达时间，并比较不同路径的完成配送总时间，以完成配送总时间最短为目标值确定单个子例的最佳无人机路径以及货车路径。
[0042]
作为优选的，所述使用带有权重的粒子群优化算法和模拟退火法更新带无人机节点的排列序列得到最优路径，具体为：
[0043]
在每一轮迭代更新带无人机节点的排列序列得到最优路径的过程中，使用带有权重的粒子群优化算法计算得到新的带无人机节点的排列序列，并在切分子例插入无人机操作后得到对应的货车路径与无人机路径，使用模拟退火法选择是否使用新的带无人机节点的排列序列及其对应的货车路径与无人机路径更新最优解；
[0044]
根据此时的排列序列进行下一轮迭代更新带无人机节点的排列序列并最终得到最优路径，直到达到预设的最大迭代次数停止更新，将此时的最优解作为最优路径。
[0045]
作为优选的，所述使用带有权重的粒子群优化算法计算得到新的带无人机节点的排列序列x
ij
(t+1)，具体为：
[0046]
x
ij
(t+1)＝x
ij
(t)+v
ij
(t+1)，
[0047]vij
(t+1)＝ω
·vij
(t)+c1r1(t)[p
ij
(t)-x
ij
(t)]+c2r2(t)[p
gj
(t)-x
ij
(t)]，
[0048][0049]
其中，ω是惯性权重，x
ij
(t)是当前带无人机节点的排列序列，x
ij
(t+1)表示新的客户节点序列；r1(t)、r2(t)表示是0到1之间的均匀随机数，用于增加粒子飞行的随机性；p
ij
(t)表示个体粒子所有位置中完成配送时间最短的客户节点序列，p
gj
(t)表示所有粒子中截止时间t完成配送时间最短的配送路径；v
ij
(t) 表示该粒子i在t时刻的粒子运动速度，v
ij
(t+1)表示该粒子i在t+1时刻的粒子运动速度；c1、c2是学习因子，t表示表示当前迭代次数，ω
max
表示最大惯性权重，ω
min
表示最小惯性权重，t
max
表示最大迭代次数。
[0050]
作为优选的，所述使用模拟退火法选择是否使用新的带无人机节点的排列序列及其对应的货车路径与无人机路径更新最优解，具体为：
[0051]
将当前带无人机节点的排列序列记为xc，将使用带有权重的粒子群优化算法计算得到的新的带无人机节点的排列序列记为xn；
[0052]
如果xn的最终完成配送的时间小于xc的最终完成配送的时间，则将xn作为此轮的最优解；
[0053]
如果xn的最终完成配送的时间大于等于xc的最终完成配送的时间，则以的概率将xn作为此轮的最优解；其中f(xn)代表xn的最终完成配送的时间，f(xc)代表xc的最终完成配送的时间，t是模拟退火算法的初始温度。
[0054]
本发明还提供了一种应用于求解协同配送的路径规划的粒子群优化系统，包括初始化模块、切分子例模块和最优路径模块，
[0055]
所述初始化模块建立包括货车和无人机协同配送的问题模型，获取用户配送数据并初始化需要被服务的客户点的排列序列，初始化的排列序列中所有客户点均由货车进行配送；
[0056]
所述切分子例模块根据排列序列中的可以被无人机服务的客户点切分子例，使用无人机和货车对每个子例进行协同配送得到带无人机节点的排列序列；
[0057]
所述最优路径模块使用带有权重的粒子群优化算法和模拟退火法更新带无人机节点的排列序列得到最优路径。
[0058]
作为优选的，所述最优路径模块包括插入无人机模块、更新速度与位置模块和模拟退火模块，
[0059]
所述插入无人机模块对每个子例插入无人机节点，根据不同的无人机发射点与无人机回收点确定子例的货车路径以及无人机路径，计算在不同路径下子例完成配送的时间；若无人机回收点存在货车等待无人机到达或者无人机到达等待货车的情况，以该无人机回收点无人机到达时间和货车到达时间两者中的较大值作为该点的到达时间，并比较不同路径的完成配送总时间，以完成配送总时间最短为目标值确定单个子例的最佳无人机路径以及货车路径；
[0060]
所述更新速度与位置模块使用带有权重的粒子群优化算法计算新的需要被服务的客户点的排列序列；
[0061]
所述模拟退火模块使用模拟退火法选择是否使用新的需要被服务的客户点的排列序列更新最优解；
[0062]
所述最优路径模块将所述更新速度与位置模块和模拟退火模块更新得到的最优解作为最优路径。
[0063]
本发明的上述技术方案相比现有技术具有以下优点：
[0064]
本发明通过向需要被服务的客户点的排列序列插入无人机模块并切分子例进行无人机和货车进行协同配送，在此基础上使用带有权重的粒子群优化算法和模拟退火法得到了协同配送的最优路径，带有权重的粒子群优化算法提高了搜索能力、有效避免陷入局部最优解，从而提高了最优路径的质量、缩短了求解时间。无人机在执行飞行运输过程中受到道路拥挤影响小，运输速度远远大于普通货车运输的速度，使用无人机和货车协同配送的方式，可以在较短的时间内配合物流工作人员完成配送任务，减少碳排放量。
附图说明
[0065]
为了使本发明的内容更容易被清楚的理解，下面根据本发明的具体实施例并结合附图，对本发明作进一步详细的说明，其中：
[0066]
图1是粒子群优化算法的流程图，
[0067]
图2是本发明中建立的包括货车和无人机协同配送的问题模型示意图，
[0068]
图3是本发明的流程图，
[0069]
图4是本发明实施例中切分子例的示意图，
[0070]
图5是本发明实施例中使用无人机和货车进行协同配送的示意图，
[0071]
图6是本发明实施例中仿真实验设置的客户点示意图。
具体实施方式
[0072]
下面结合附图和具体实施例对本发明作进一步说明，以使本领域的技术人员可以更好地理解本发明并能予以实施，但所举实施例不作为对本发明的限定。
[0073]
参照图3流程图所示，本发明公开了一种应用于求解协同配送的路径规划的粒子群优化方法，包括：
[0074]
s1：建立包括货车和无人机协同配送的问题模型，初始化需要被服务的客户点的排列序列，初始化的排列序列中所有客户点均由货车进行配送，即货车路径为所有客户点序列，没有无人机路径。
[0075]
包括货车和无人机协同配送的问题模型，具体为：
[0076]
在一个区域内一辆货车搭载至少一架无人机为若干客户送货，每个客户点有自己的需求，货车与无人机均可以服务客户，目标为最短完成配送时间和最小化成本。同时，设置的条件有：
[0077]
条件一：无人机每次出动只能访问一个客户，但在无人机飞行时货车可以访问多个客户；
[0078]
条件二：无人机在飞行时保持恒定飞行；
[0079]
条件三：无人机可以在某个客户节点由货车收集并再次出发；
[0080]
条件四：无人机无法在某些预设节点之间与货车汇合；
[0081]
条件五：任何货车都不得再次拜访任何客户；
[0082]
条件六：无人机路径在基地结束，结束后无人机将停止使用；
[0083]
条件七：无人机和货车在汇合状态行驶时，无人机由货车运输；
[0084]
条件八：不考虑无人机交付货物时间，发射与回收无人机时间恒定，无人机续航时间恒定。
[0085]
s2：根据排列序列中的可以被无人机服务的客户点切分子例，使用无人机和货车对每个子例进行协同配送得到带无人机节点的排列序列，减少每个子例的最终完成时间以求得最终的最小完成配送时间。
[0086]
s2-1：如图4所示，所述根据排列序列中的可以被无人机服务的客户点切分子例，具体为：
[0087]
若客户点的配送需求小于无人机最大载货量，则将该节点定义为可由无人机服务节点；根据客户点中的可由无人机服务节点对仅由货车配送的初始化路径进行子例的切
分，得到至少一个含有可由无人机服务节点的子例。每个所述子例只含有一个可由无人机服务节点且每个子例包含的节点数大于等于3，每个子例包含的节点数大于等于3用于满足无人机在服务客户点时需要的无人机发射节点与无人机回收节点。如果为满足节点数大于等于三的条件切分出的子例中有两个或以上节点可以被无人机访问，则设置其中一个点为无人机节点，其余节点为卡车节点，在后续进行确定无人机出发点及回收点时，只考虑该点为无人机点。
[0088]
s2-2：所述使用无人机和货车对每个子例进行协同配送得到带无人机节点的排列序列，具体为：
[0089]
排列序列中的每个客户点包括配送到达时间和配送离开时间，对每个子例插入无人机节点，在确定好无人机节点后，根据不同的无人机发射点与无人机回收点确定子例的货车路径以及无人机路径，计算在不同路径(包括纯货车路径)下子例完成配送的时间(即子例路径最后一个节点的到达时间)；
[0090]
若无人机回收点存在货车等待无人机到达或者无人机到达等待货车的情况，所以需要确定同步无人机发射点的离开时间与无人机回收点的到达时间过程中进行时间的同步。以该无人机回收点无人机到达时间和货车到达时间两者中的较大值作为该点的到达时间，并比较不同路径的完成配送总时间，以完成配送总时间最短为目标值确定单个子例的最佳无人机路径以及货车路径。
[0091]
本实施例中以子例(6，3，1，5)为例(数字表示货车点或无人机点的编号)，不计算无人机发射与回收时间，使用无人机和货车进行协同配送的基本步骤如图5所示。图5中比较三种不同的无人机路径情况下子例最终的完成时间(图5中括号前一位数字为到达时间，括号后一位数字为离开时间)，最终确定该子例的最佳货车路径为(6-3-1)，最佳无人机路径为(6-5
‑ꢀ
1)。
[0092]
在完成子例集合中所有子例的插入无人机并确定子例的最佳货车路径与无人机路径操作后，得到最终问题的完整货车路径(从场站出发开始，到返回场站结束)、无人机路径、每个客户点的到达时间和离开时间以及完成配送返回场站时间。
[0093]
s3：使用带有权重的粒子群优化算法和模拟退火法(simulate annealarithmetic，saa)更新带无人机节点的排列序列得到最优路径。
[0094]
在每一轮迭代更新带无人机节点的排列序列得到最优路径的过程中，使用带有权重的粒子群优化算法计算得到新的带无人机节点的排列序列，并在切分子例插入无人机操作后得到对应的货车路径与无人机路径，使用模拟退火法选择是否使用新的带无人机节点的排列序列及其对应的货车路径与无人机路径更新最优解；根据此时的排列序列进行下一轮迭代更新带无人机节点的排列序列并最终得到最优路径，直到达到预设的最大迭代次数停止更新，将此时的最优解作为最优路径。
[0095]
s3-1：在每一轮迭代更新带无人机节点的排列序列得到最优路径的过程中，使用带有权重的粒子群优化算法计算新的带无人机节点的排列序列 x
ij
(t+1)，具体为：
[0096]
x
ij
＝(t+1)＝x
ij
(t)+v
ij
(t+1)，
[0097]vij
(t+1)＝ω
·vij
(t)+c1r1(t)[p
ij
(t)-x
ij
(t)]+c2r2(t)[p
gj
(t)-x
ij
(t)]，
[0098][0099]
其中，t表示时间，ω是惯性权重，x
ij
(t)是当前带无人机节点的排列序列，x
ij
(t+1)表示粒子i在t+1时刻新的粒子位置，在该问题中表示新的客户节点序列；r1(t)、r2(t)表示是0到1之间的均匀随机数，用于增加粒子飞行的随机性；p
ij
(t)表示粒子i在t时刻的个体最优解，在该问题中为个体粒子所有位置中完成配送时间最短的客户节点序列，即配送路径；p
gj
(t)表示全局最优解，即所有粒子中截止时间t完成配送时间最短的配送路径；v
ij
(t)表示该粒子i 在t时刻的粒子运动速度，v
ij
(t+1)表示该粒子i在t+1时刻的粒子运动速度； c1、c2是学习因子，t表示表示当前迭代次数，ω
max
表示最大惯性权重，ω
min
表示最小惯性权重，t
max
表示最大迭代次数。本发明针对性得加入惯性权重ω以及对ω的调整，以达到提升求解质量的目标。计算得到的新的需要被服务的客户点的排列序列中客户点出行序列的起点与终点保持不变，均为场站。
[0100]
s3-2：使用模拟退火法选择是否使用新的带无人机节点的排列序列更新最优解：
[0101]
将当前带无人机节点的排列序列记为xc，将使用带有权重的粒子群优化算法计算得到的新的带无人机节点的排列序列记为xn；模拟退火法用来判别接受新生成的解xn，还是拒绝新生成的解xn。
[0102]
如果xn的最终完成配送的时间小于xc的最终完成配送的时间，则将xn作为此轮的最优解(不考虑货车数,货车数量为1)；
[0103]
如果xn的最终完成配送的时间大于等于xc的最终完成配送的时间，则以的概率将xn作为此轮的最优解；其中f(xn)代表xn的目标值、即最终完成配送的时间，f(xc)代表xc的最终完成配送的时间，t是模拟退火算法中设定的初始温度。
[0104]
s3-3：执行步骤s2～s3-2，直到达到预设的最大迭代次数停止更新，将此时的最优解作为最优路径。最优路径对应的货车路径与无人机路径为最优货车路径与最优无人机路径。在每次更新得到新的序列后会重新再一次切分子例，并确定无人机点，两次的无人机点可能不相同，因此需要再对每一个子例进行插入无人机路径操作得到新的卡车路径与无人机路径。每次粒子群算法与模拟退火更新的只是排列序列，对每个序列还需要重新计算得到序列对应的货车路径与无人机路径，最终得到的结果是协同配送时货车与无人机的路径。
[0105]
本发明还公开了一种应用于求解协同配送的路径规划的粒子群优化系统，包括初始化模块、切分子例模块和最优路径模块。
[0106]
所述初始化模块建立包括货车和无人机协同配送的问题模型，获取用户配送数据并初始化需要被服务的客户点的排列序列，初始化的排列序列中所有客户点均由货车进行配送。所述切分子例模块根据排列序列中的可以被无人机服务的客户点切分子例，使用无人机和货车对每个子例进行协同配送得到带无人机节点的排列序列。所述最优路径模块使用带有权重的粒子群优化算法和模拟退火法更新带无人机节点的排列序列得到最优路径。
[0107]
所述最优路径模块包括插入无人机模块、更新速度与位置模块和模拟退火模块。所述插入无人机模块对每个子例插入无人机节点，根据不同的无人机发射点与无人机回收点确定子例的货车路径以及无人机路径，计算在不同路径下子例完成配送的时间；若无人
机回收点存在货车等待无人机到达或者无人机到达等待货车的情况，以该无人机回收点无人机到达时间和货车到达时间两者中的较大值作为该点的到达时间，并比较不同路径的完成配送总时间，以完成配送总时间最短为目标值确定单个子例的最佳无人机路径以及货车路径。所述更新速度与位置模块使用带有权重的粒子群优化算法计算新的需要被服务的客户点的排列序列。所述模拟退火模块使用模拟退火法选择是否使用新的需要被服务的客户点的排列序列更新最优解。所述最优路径模块将所述更新速度与位置模块和模拟退火模块更新得到的最优解作为最优路径。
[0108]
系统的整体流程如下：
[0109]
步骤1：输入种群数量n、最大迭代次数t
max
，最大惯性权重ω
max
、最小惯性权重ω
min
，当前迭代次数t＝0，c1、c2，粒子最大速度v
max
等基本参数。
[0110]
步骤2：初始化种群，初始化种群中每个粒子的初始解x以及当前速度v，每个粒子的位置代表一种所有客户点的排列，起点以及终点位置均为场站；初始解x均由货车完成配送任务，记录当前最优解p
best
、全局最优解g
best
；初始解x的适应值记为无限大；记录对应的货车路径集合、无人机路径集合(此时无人机路径集合为空集)。
[0111]
步骤3：遍历所有粒子当前位置x，当序列中某一客户点需求小于无人机的最大荷载时，将该点定义为可被无人机访问节点，以包含可被无人机访问节点且子例元素数量大于等于3为目标切分得到一个子例，序列中剩下的节点按照相同的方式进行切分直至结束。最后得到子例集合。子例集合中可能有(1)包含可被无人机访问节点的子例(2)直至终点但无可被无人机访问节点的子例。
[0112]
步骤4：对于子例集合中未完成插入无人机计算的子例，计算该子例完全由货车服务时的子例配送时间，得到该子例的货车路径与子例中每个点的当前到达时间与离开时间，无无人机路径，子例中最后一个点的到达时间为子例当前配送时间。
[0113]
步骤5：如果该子例中含有可被无人机访问节点，转入步骤6，否则转入步骤10，该子例标记为完成插入无人机计算。
[0114]
步骤6：确定该子例中的某一可被无人机访问节点为无人机访问节点，剩下子例客户点序列构成新的货车路径。
[0115]
步骤7：确定货车路径上任意一客户点为无人机发射点，货车路径上在该点后被货车访问的一客户点为无人机回收点(无人机往返总路程满足无人机的续航里程)，三点构成无人机路径方案，记录使用过的无人机路径方案。计算新的该子例中每个点的当前到达时间与离开时间，得到新的子例配送时间以及无人机路径。
[0116]
步骤8：对比当前配送时间与新配送时间。如果当前配送时间小于新的配送时间，保持当前货车与无人机路径方案以及相关数据。如果当前配送时间大于新的配送时间，更新当前货车与无人机路径方案以及相关数据。
[0117]
步骤9：判断是否还有不同于步骤7中记录过的无人机路径方案，如果有，返回步骤7，否则，转到步骤10。
[0118]
步骤10：分别在货车路径集合中添加货车路径与无人机路径，记录子例中各点的相关时间。
[0119]
步骤11：判断是否子例集合中所有子例均完成插入无人机操作，如果是，转入步骤12，否则返回步骤4。
[0120]
步骤12：在完成所有子例的插入无人机操作后，得到货车以及无人机返回场站的时间，即新的完成配送时间以及所有的货车路径与无人机路径。
[0121]
步骤13：将新的完成配送时间与当前最优解进化对比，使用模拟退火算法接受新的解，更新当前最优解p
best
。
[0122]
步骤14：更新全局最优解g
best
。
[0123]
步骤15：如果当前迭代次数t≥t
max
，退出算法流程，输出x，以及对应的货车路径、无人机路径、完成配送时间等相关数据。否则转到步骤 16。
[0124]
步骤16：根据迭代次数t、最大迭代次数t
max
，最大惯性权重ω
max
、最小惯性权重ω
min
，粒子当前速度v等数据对粒子的速度、位置进行更新，得到新的客户点序列x，t＝t+1，转入步骤3。
[0125]
本发明通过向需要被服务的客户点的排列序列插入无人机模块并切分子例进行无人机和货车进行协同配送，在此基础上使用带有权重的粒子群优化算法和模拟退火法得到了协同配送的最优路径，带有权重的粒子群优化算法提高了搜索能力、有效避免陷入局部最优解，从而提高了最优路径的质量、缩短了求解时间。无人机在执行飞行运输过程中受到道路拥挤影响小，运输速度远远大于普通货车运输的速度，使用无人机和货车协同配送的方式，可以在较短的时间内配合物流工作人员完成配送任务，减少碳排放量。
[0126]
为了进一步说明本发明的有益效果，本实施例中以图6所示的8个客户点为例进行仿真实验。单货车执行配送任务时，完成配送时间为60个单位时间，而货车与无人机协同配送情况下完成配送时间为33个单位时间，减少了45％的配送时间。
[0127]
接着，本实施例中设置由11个顾客和1个场站组成的场景，10个顾客
[0128]
(客户点)的编号为1-11，1个场站的编号为0。货车的单位行驶速度为1，无人机单位行驶速度为3，因为无人机无在发射点的发射时间与在回收点的回收时间较小故本实施例中忽略不计。设置客户点和场站的数据如表2 所示：
[0129]
表2客户点数据设置表
[0130][0131]
计算所有编号的od距离矩阵d
ij
，od指的是任意两个点之间的距离矩阵；并分别根据货车速度与无人机速度得到货车时间od矩阵tt
ij
与无人机时间od矩阵td
ij
(小数点后保留1位有效数字)。设置最大迭代次数 t
max
为100，实验参数取值如表3所示：
[0132]
表3实验参数设置表
[0133]
名称值最大惯性权重ω
max
0.9学习因子c13粒子最大速度v
max
2无人机最大行驶里程e14最小惯性权重ω
min
0.4学习因子c25种群数量n50无人机最大荷载c8
[0134]
(1)初始解生成
[0135]
利用随机数初始化所有粒子的初始解，以粒子1为例，初始解x＝[0,9, 10,2,3,6,4,8,5,1,11,7,0]，货车路径truckroutess＝[0,9,10,2,3,6,4,8,5, 1,11,7,0]，无无人机
路径，初始解x作为当前解x。其他粒子进行同样操作。
[0136]
(2)切分子例
[0137]
对当前解进行子例的切分，得到子例的集合为[[0,9,10],[9,2,3,6],[3, 4,8],[8,5,1,11,7,0]]，其他粒子进行同样操作。
[0138]
(3)插入无人机
[0139]
对子例[0,9,10]执行插入无人机操作，客户点10的需求7小于无人机最大荷载8，客户点10为可被无人机访问节点。子例[0,9,10]单货车执行任务的配送完成时间点为38，插入无人机后货车路径为[0,9],无人机路径只有一种方案为[0,10,9]且满足无人机续航条件,完成配送时间点为33，33《38, 故该子例经过插入无人机操作后的货车路径为[0,9],无人机路径为[0,10,9]。对[9,2,3,6]进行同样的插入无人机操作，客户点6为可被无人机访问节点。在前一子例完成操作后的情况下，子例[9,2,3,6]单货车执行任务的配送完成时间点为97。插入无人机后货车路径为[9,2,3]，无人机路径可以为[9,6,2]、 [9,6,3]、[2,6,3]；在经过删除不满足无人机续航条件的无人机路径并对比所有可行无人机路径的完成配送时间点后；得到该子例完成配送时间点为87，货车路径为[9,2,3]，无人机路径为[2,6,3]。对余下子例进行同样的插入无人机操作后，得到货车返回场站后的所有货车路径、无人机路径与完成配送时间：货车路径集合truckroutes＝[[0,9],[9,2,3],[3,8],[8,5,1,11,7,0]]；无人机路径集合droneroutes＝[[0,10,9],[2,6,3],[3,4,8]]，完成配送时间为231。其他粒子进行同样操作。
[0140]
(3)更新p
best
与g
best
[0141]
当前解x的货车路径集合[[0,9],[9,2,3],[3,8],[8,5,1,11,7,0]]；无人机路径集合[[0,10,9],[2,6,3],[3,4,8]]，完成配送时间即适应值为231。小于原种群最优解p
best
的适应值，则更新p
best
＝当前解x；如果当前解x的适应值大于原种群最优解p
best
的适应值，则根据模拟退火算法决定是否更新种群最优解p
best
。如果当前解x的适应值小于原全局最优解g
best
的适应值，更新g
best
＝当前解x，计算完所有的粒子的适应值后，得到每个种群 (此处为50)种群最优解p
best
和全局最优解g
best
以及相对应的货车路径和无人机路径。
[0142]
(3)第1次迭代
[0143]
根据速度与位置更新模块对当x＝[0，9,10,2,3,6,4,8,5,1,11,7，0]更新得到当前解x＝[0,1,11,3,5,8,4,7,2,6,9,10,0]。经过同样的切分子例与插入无人机操作后，得到当前解x的货车路径集合truckroutes＝[[0,1,11, 3,5,8],[8,7,2],[2,9],[9,0]]，无人机路径droneroutes＝[[5,4,8],[7,6,2], [2,10,9]]，最终完成配送时间为222。222《231,当前解x的适应值小于原种群最优解p
best
的适应值，更新种群最优解p
best
＝＝[0,1,11,3,5,8,4,7,2,6, 9,10,0]，以及对应的货车路径集合truckroutes＝[[0,1,11,3,5,8],[8,7,2], [2,9],[9,0]]和无人机路径droneroutes，其他粒子进行同样操作。完成所有粒子的第一次迭代后，得到全局最优解g
best
以及相对应的货车路径和无人机路径。迭代次数加1。
[0144]
(4)第10次迭代
[0145]
得到全局最优解g
best
＝[0,8,3,5,4,1,2,6,7,9,11,10,0]，货车路径truckroutes＝[[0,8,3,5],[5,1,2],[2,7,9,11],[11,0]]，无人机路径 droneroutes＝[[8,4,5],[1,6,2],[9,10,11]]，完成配送时间为151。
[0146]
(5)第20次迭代
[0147]
得到全局最优解g
best
＝[0,7,8,4,5,3,1,2,6,9,11,10,0]，货车路径 truckroutes＝[[0,7,8],[8,5,3,1,2],[2,9,11],[11,0]]，无人机路径droneroutes＝[[7,4,8],[1,6,2],[9,10,11]]，完成配送时间为144。
[0148]
(5)第50次迭代
[0149]
得到全局最优解g
best
＝[6,2,4,1,3,5,8,7,9,11,10]，货车路径 truckroutes＝[[0,2],[2,1],[1,3,5,8,7,9,11],[11,0]]，无人机路径 droneroutes＝[[0,6,2],[2,4,1],[9,10,11]]，完成配送时间为138。
[0150]
(6)第100次迭代
[0151]
得到全局最优解g
best
＝[0,2,1,4,3,5,6,8,7,9,11,10,0]，货车路径 truckroutes＝[[0,2,1],[1,3,5],[5,8,7,9,11],[11,0]]，完整的卡车路径为 [0,2,1,3,5,8,7,9,11,0]无人机路径droneroutes＝[[2,4,1],[1,6,5],[9,10,11]]，完成配送时间为138。至此得到了最优路径，此时卡车路径为 [0,2,1,3,5,8,7,9,11,0]，无人机路径为：[[2,4,1],[1,6,5],[9,10,11]]。
[0152]
本领域内的技术人员应明白，本技术的实施例可提供为方法、系统、或计算机程序产品。因此，本技术可采用完全硬件实施例、完全软件实施例、或结合软件和硬件方面的实施例的形式。而且，本技术可采用在一个或多个其中包含有计算机可用程序代码的计算机可用存储介质(包括但不限于磁盘存储器、cd-rom、光学存储器等)上实施的计算机程序产品的形式。
[0153]
本技术是参照根据本技术实施例的方法、设备(系统)、和计算机程序产品的流程图和/或方框图来描述的。应理解可由计算机程序指令实现流程图和/或方框图中的每一流程和/或方框、以及流程图和/或方框图中的流程和/或方框的结合。可提供这些计算机程序指令到通用计算机、专用计算机、嵌入式处理机或其他可编程数据处理设备的处理器以产生一个机器，使得通过计算机或其他可编程数据处理设备的处理器执行的指令产生用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的装置。
[0154]
这些计算机程序指令也可存储在能引导计算机或其他可编程数据处理设备以特定方式工作的计算机可读存储器中，使得存储在该计算机可读存储器中的指令产生包括指令装置的制造品，该指令装置实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能。
[0155]
这些计算机程序指令也可装载到计算机或其他可编程数据处理设备上，使得在计算机或其他可编程设备上执行一系列操作步骤以产生计算机实现的处理，从而在计算机或其他可编程设备上执行的指令提供用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的步骤。
[0156]
显然，上述实施例仅仅是为清楚地说明所作的举例，并非对实施方式的限定。对于所属领域的普通技术人员来说，在上述说明的基础上还可以做出其它不同形式变化或变动。这里无需也无法对所有的实施方式予以穷举。而由此所引申出的显而易见的变化或变动仍处于本发明创造的保护范围之中。

技术特征：
1.一种应用于求解协同配送的路径规划的粒子群优化方法，其特征在于，包括：建立包括货车和无人机协同配送的问题模型，初始化需要被服务的客户点的排列序列，初始化的排列序列中所有客户点均由货车进行配送；根据排列序列中的可以被无人机服务的客户点切分子例，使用无人机和货车对每个子例进行协同配送得到带无人机节点的排列序列；使用带有权重的粒子群优化算法和模拟退火法更新带无人机节点的排列序列得到最优路径。2.根据权利要求1所述的应用于求解协同配送的路径规划的粒子群优化方法，其特征在于：所述包括货车和无人机协同配送的问题模型，具体为：在一个区域内一辆货车搭载至少一架无人机为客户送货，每个客户点有自己的需求，货车与无人机均可以服务客户，模型目标为最短完成配送时间和最小化成本；满足的条件有：条件一：无人机每次出动只能访问一个客户，但在无人机飞行时货车可以访问多个客户；条件二：无人机在飞行时保持恒定飞行；条件三：无人机可以在某个客户节点由货车收集并再次出发；条件四：无人机无法在预设节点之间与货车汇合；条件五：任何货车都不得再次拜访任何客户；条件六：无人机路径在基地结束，结束后无人机将停止使用；条件七：无人机和货车在汇合状态行驶时，无人机由货车运输；条件八：不考虑无人机交付货物时间，发射与回收无人机时间恒定，无人机续航时间恒定。3.根据权利要求1所述的应用于求解协同配送的路径规划的粒子群优化方法，其特征在于：所述根据排列序列中的可以被无人机服务的客户点切分子例，具体为：若客户点的配送需求小于无人机最大载货量，则将该节点定义为可由无人机服务节点；根据客户点中的可由无人机服务节点对仅由货车配送的初始化路径进行子例的切分，得到至少一个含有可由无人机服务节点的子例。4.根据权利要求3所述的应用于求解协同配送的路径规划的粒子群优化方法，其特征在于：所述子例包括一个所述可由无人机服务节点且所述子例包含的节点数大于等于3。5.根据权利要求1所述的应用于求解协同配送的路径规划的粒子群优化方法，其特征在于：所述使用无人机和货车对每个子例进行协同配送得到带无人机节点的排列序列，具体为：排列序列中的每个客户点包括配送到达时间和配送离开时间，对每个子例插入无人机节点，根据不同的无人机发射点与无人机回收点确定子例的货车路径以及无人机路径，计算在不同路径下子例完成配送的时间；若无人机回收点存在货车等待无人机到达或者无人机到达等待货车的情况，以该无人机回收点无人机到达时间和货车到达时间两者中的较大值作为该点的到达时间，并比较不同路径的完成配送总时间，以完成配送总时间最短为目标值确定单个子例的最佳无人机路
径以及货车路径。6.根据权利要求1-5任一项所述的应用于求解协同配送的路径规划的粒子群优化方法，其特征在于：所述使用带有权重的粒子群优化算法和模拟退火法更新带无人机节点的排列序列得到最优路径，具体为：在每一轮迭代更新带无人机节点的排列序列得到最优路径的过程中，使用带有权重的粒子群优化算法计算得到新的带无人机节点的排列序列，并在切分子例插入无人机操作后得到对应的货车路径与无人机路径，使用模拟退火法选择是否使用新的带无人机节点的排列序列及其对应的货车路径与无人机路径更新最优解；根据此时的排列序列进行下一轮迭代更新带无人机节点的排列序列并最终得到最优路径，直到达到预设的最大迭代次数停止更新，将此时的最优解作为最优路径。7.根据权利要求6所述的应用于求解协同配送的路径规划的粒子群优化方法，其特征在于：所述使用带有权重的粒子群优化算法计算得到新的带无人机节点的排列序列x
ij
(t+1)，具体为：x
ij
(t+1)＝x
ij
(t)+v
ij
(t+1)，v
ij
(t+1)＝ω
·
v
ij
(t)+c1r1(t)[p
ij
(t)-x
ij
(t)]+c2r2(t)[p
gj
(t)-x
ij
(t)]，其中，ω是惯性权重，x
ij
(t)是当前带无人机节点的排列序列，x
ij
(t+1)表示新的客户节点序列；r1(t)、r2(t)表示是0到1之间的均匀随机数，用于增加粒子飞行的随机性；p
ij
(t)表示个体粒子所有位置中完成配送时间最短的客户节点序列，p
gj
(t)表示所有粒子中截止时间t完成配送时间最短的配送路径；v
ij
(t)表示该粒子i在t时刻的粒子运动速度，v
ij
(t+1)表示该粒子i在t+1时刻的粒子运动速度；c1、c2是学习因子，t表示表示当前迭代次数，ω
max
表示最大惯性权重，ω
min
表示最小惯性权重，t
max
表示最大迭代次数。8.根据权利要求6所述的应用于求解协同配送的路径规划的粒子群优化方法，其特征在于：所述使用模拟退火法选择是否使用新的带无人机节点的排列序列及其对应的货车路径与无人机路径更新最优解，具体为：将当前带无人机节点的排列序列记为x
c
，将使用带有权重的粒子群优化算法计算得到的新的带无人机节点的排列序列记为x
n
；如果x
n
的最终完成配送的时间小于x
c
的最终完成配送的时间，则将x
n
作为此轮的最优解；如果x
n
的最终完成配送的时间大于等于x
c
的最终完成配送的时间，则以的概率将x
n
作为此轮的最优解；其中f(x
n
)代表x
n
的最终完成配送的时间，f(x
c
)代表x
c
的最终完成配送的时间，t是模拟退火算法的初始温度。9.一种应用于求解协同配送的路径规划的粒子群优化系统，其特征在于：包括初始化模块、切分子例模块和最优路径模块，所述初始化模块建立包括货车和无人机协同配送的问题模型，获取用户配送数据并初始化需要被服务的客户点的排列序列，初始化的排列序列中所有客户点均由货车进行配送；
所述切分子例模块根据排列序列中的可以被无人机服务的客户点切分子例，使用无人机和货车对每个子例进行协同配送得到带无人机节点的排列序列；所述最优路径模块使用带有权重的粒子群优化算法和模拟退火法更新带无人机节点的排列序列得到最优路径。10.根据权利要求9所述的应用于求解协同配送的路径规划的粒子群优化系统，其特征在于：所述最优路径模块包括插入无人机模块、更新速度与位置模块和模拟退火模块，所述插入无人机模块对每个子例插入无人机节点，根据不同的无人机发射点与无人机回收点确定子例的货车路径以及无人机路径，计算在不同路径下子例完成配送的时间；若无人机回收点存在货车等待无人机到达或者无人机到达等待货车的情况，以该无人机回收点无人机到达时间和货车到达时间两者中的较大值作为该点的到达时间，并比较不同路径的完成配送总时间，以完成配送总时间最短为目标值确定单个子例的最佳无人机路径以及货车路径；所述更新速度与位置模块使用带有权重的粒子群优化算法计算新的需要被服务的客户点的排列序列；所述模拟退火模块使用模拟退火法选择是否使用新的需要被服务的客户点的排列序列更新最优解；所述最优路径模块将所述更新速度与位置模块和模拟退火模块更新得到的最优解作为最优路径。

技术总结
本发明涉及物流配送领域，公开一种应用于求解协同配送的路径规划的粒子群优化方法和系统，方法包括建立货车和无人机协同配送的问题模型，初始化需要被服务的客户点的排列序列；根据排列序列中的可以被无人机服务的客户点切分子例，对每个子例使用无人机和货车进行协同配送得到子例配送中的货车路径与无人机路径，在完成所有子例配送后得到完整的货车路径与所有的无人机路径；使用带有权重的粒子群优化算法和模拟退火法更新带无人机节点的排列序列并重新切分子例确定无人机路径得到最优路径；系统包括初始化模块、切分子例模块和最优路径模块。本发明可以实现对包括无人机和货车的协同配送的路径规划，提高最优路径的质量、缩短求解时间。缩短求解时间。缩短求解时间。


技术研发人员：谢刚 成明 张成浩 黎怡彤 王静妍
受保护的技术使用者：苏州大学
技术研发日：2022.09.26
技术公布日：2023/1/6