一种多车多目标无人车路径优化方法

1.本发明属于信息数据处理及传输技术领域，具体涉及一种多车多目标无人车路径优化方法。


背景技术：

2.当前的无人配送内涵主要是作为“最后一公里配送”的新型解决方案。配送的“最后一公里”并不是实际上的一公里，而是指从物流分拣中心到客户手中这段较短距离，通过运输工具，将货物送至客户手中的过程。这一短距离配送，是物流的末端环节，也是唯一直接和客户面对面接触的环节。在无人配送投入使用前，国家出台的更多是宏观鼓励和发展规划，目的是推动互联网及人工智能相关产业的发展；在无人配送逐渐进入试用阶段后，主要是地方政府针对无人配送车的推广提倡和具体管理方案。
3.现阶段行业内对于无人配送车的归类存在较大分歧：作为机动车，在享受路权、质量控制的同时，要面临严格的管理条例，影响发展创新；作为非机动车，其重量和速度与国家标准可能存在出入；作为机器人管理，目前的法律尚不禁止机器人上路，但又缺乏相应管理方案。由于单个目的地的订单量很大所以快递员的主要工作是在末端场景的分发派送，而即时配送员讲究的是时效性，这会使得单趟配送的订单量不多，且外卖这种模式属于多个商家对多个消费者，规模效应没有快递那么强，所以配送员承担的更多是路上运输的工作。


技术实现要素：

4.本发明的目的在于提供一种适用于多车多目标无人车路径优化、快速完成优化计算的多车多目标无人车路径优化方法。
5.为了实现上述发明目的，本发明采用以下技术方案：
6.一种多车多目标无人车路径优化方法，包括如下步骤：
7.1)配送中心选址：将现有各个供应点或需求点看成是分布在某一平面内的物流运输系统的节点，从而确定物流系统的重心；
8.2)构建单行程下的多车多目标无人车路径优化模型：对于路径优化问题，通常假设距离、速度等参数已知，在一定约束下，建立以行驶距离、行驶时间为目标的数学模型；
9.3)开发单行程下的多车多目标无人车路径优化算法：选择以并行计算能力突出的遗传算法为框架，采用排列的编码方式；
10.4)构建多行程下的多车多目标无人车路径优化模型；
11.5)开发多行程下的多车多目标无人车路径优化算法：构造多行程下的多车多目标无人车路径优化算法，实现多行程下的多车多目标无人车路径优化模型的算法求解。
12.进一步地，所述步骤3)中在遗传算法的变异算子中引入模拟退火算法，对个体进行局部操作，增强算法的局部搜索能力，以促使算法跳出局部最优，进而通过多种算法优点的结合来设计混合智能优化算法。
13.进一步地，所述步骤5)中编码过程包括如下步骤：
14.1)利用总行程符(2n-1)～2n+(m-2)确定每个配送车辆总的行程的编码；
15.2)利用单个配送车辆行程分割符确定每个配送车辆的具体行程。
16.进一步地，所述步骤1)中采用实证研究与数据挖掘相结合的方法，利用粗糙集理论进行属性约简，去除冗余因素，降低模型的维度。
17.进一步地，所述步骤1)中利用广义成本最小化来处理该问题，构建广义成本最小化目标函数，从系统的角度构建考虑订单需求变化不确定因素构建路径优化模型。
18.进一步地，所述采用精确算法求取小规模、中规模问题的精确解和启发式算法的求解结果进行对比，并利用拉格朗日松弛法求取大规模问题解的界限。
19.与现有技术相比，本发明的有益效果是：
20.1)本发明的模型及算法适用于多车多目标无人车路径优化，支持多方案的快速比选。
21.2)本发明的算法以最小化车辆数、无人车行驶总时间、配送总用时、订单配送用时等为目标，实现在给定订单总量、站点数量、行驶速度等环境下，快速完成优化计算。
22.3)本发明采用智能化的算法自动计算生成无人车路径方案，不需要人工预先输入线路走向等信息。
附图说明
23.图1为本发明一种混合智能优化算法示意图。
24.图2为本发明多行程算法编码及解码示意图。
25.图3为本发明智能优化示意图。
26.图4为本发明sa-ga求解优化过程示意图。
27.图5为本发明sa-ga求得最优配送方案路线示意图。
28.图6为本发明ga求解优化过程示意图。
29.图7为本发明ga求得最优配送方案路线示意图。
具体实施方式
30.下面将参照附图更详细地描述本发明的实施例。虽然附图中显示了本发明的实施例，然而应该理解，可以以各种形式实现本发明而不应被这里阐述的实施例所限制。相反，提供这些实施例是为了使本发明更加透彻和完整，并且能够将本发明的范围完整地传达给本领域的技术人员。本领域的技术人员可以在不偏离本发明精神和保护范围的基础上从下述描述得到替代技术方案。
31.实施例
32.一种多车多目标无人车路径优化方法，包括如下步骤：
33.1)配送中心选址：将现有各个供应点或需求点看成是分布在某一平面内的物流运输系统的节点，从而确定物流系统的重心；
34.采用实证研究与数据挖掘相结合的方法，利用粗糙集理论进行属性约简，去除冗余因素，降低模型的维度。利用广义成本最小化来处理该问题，构建广义成本最小化目标函数，从系统的角度构建考虑订单需求变化不确定因素构建路径优化模型。所述采用精确算
法求取小规模、中规模问题的精确解和启发式算法的求解结果进行对比，并利用拉格朗日松弛法求取大规模问题解的界限。
35.在货运节点的选址实践过程中，人们使用了许多定性和定量的方法，并建立了一些决策模型。本项目的选址方法采用重心法来实现单一选址。重心法是一种模拟方法，其基本原理是：将现有各个供应点(资源点)或需求点(用户点)看成是分布在某一平面内的物流运输系统的节点，他们的资源数量可以看成是这些节点的重量，这样就可以利用求几何重心的方法来找到距现有节点的距离、供应量、运输费率之积的总和为最小的节点，从而确定物流系统的重心，即新的运输节点的最佳位置。
36.如果用pi(xi,yi)表示现有节点(或各供应点)的位置，wi表示第i个节点的运量，ci表示各节点的运输费率，令p0(x0,y0)表示新节点的位置。
37.根据重心法有：
38.解得：
39.各供应点的运输费用均相等，则有：
[0040][0041]
50个站点pi(xi,yi)(i,j＝50)的坐标和订单数如表1所示：
[0042]
[0043]
[0044][0045]
2)构建单行程下的多车多目标无人车路径优化模型：对于路径优化问题，通常假设距离、速度等参数已知，在一定约束下，建立以行驶距离、行驶时间为目标的数学模型；模型范式可表达为：
[0046]mx
inf(x)s.t.g(x)≤c
[0047]
其中，x为变量，f(x)为目标函数，可以是时间等，g(x)为约束条件。针对特定问题，学者根据范式进行实例化建模。
[0048]
定义在有向图g＝(v，a)，其中v＝{0，1，2，
…
n，n+1}表示所有节点的集合，0和n+1表示配送中心，1，2，
…
n表示顾客，a表示弧的集合。规定在有向图g上，一条合理的配送路线必须始于节点0，终于节点n+1。cvrp模型中涉及的参数如表2所示，决策变量如表3所示。此外，δ
+
(i)表示从节点i出发的弧的集合，δ-(j)表示回到节点j的弧的集合，n＝v\{0，n+1}表示顾客集合，k表示配送车辆集合。
[0049]
[0050][0051]
3)开发单行程下的多车多目标无人车路径优化算法：选择以并行计算能力突出的遗传算法为框架，采用排列的编码方式；
[0052]
在遗传算法的变异算子中引入模拟退火算法，对个体进行局部操作，增强算法的局部搜索能力，以促使算法跳出局部最优，进而通过多种算法优点的结合来设计混合智能优化算法。混合智能优化算法流程如图1所示。
[0053]
4)构建多行程下的多车多目标无人车路径优化模型；
[0054]
5)开发多行程下的多车多目标无人车路径优化算法：构造多行程下的多车多目标无人车路径优化算法，实现多行程下的多车多目标无人车路径优化模型的算法求解。
[0055]
编码过程：编码长度维度[n+(n-1)+(m-1)]的整数排列，各维度取值范围为[0,1]。解码过程：首先，1～n为客户编号，(n+1)～(2n-1)为单个配送车辆行程分割符，(2n-1)～2n+(m-2)为配送车辆总行程分割符；编码过程包括如下步骤：
[0056]
1)利用总行程符(2n-1)～2n+(m-2)确定每个配送车辆总的行程的编码；
[0057]
2)利用单个配送车辆行程分割符确定每个配送车辆的具体行程。
[0058]
为了有效地说明上述编码及解码操作，给出如下算例：配送车辆总数m＝3，客户总数n＝9。据此可知，编码长度为19。其编解码过程如图2所示。给出初始的1-19的排列，其中，1-9位客户点，10～17为单个配送车辆行程分割符，18和19为配送车辆总行程分割符。解码过程如下：
[0059]
1)利用总行程分割操作得到三辆配送车的总行程编码分别为：配送车1-(10,6,3,11)、配送车2-(12,7,8,14,13,5,1,2,15)、配送车3-(17,16,4,9)；
[0060]
2)利用单个配送车行程分割操作确定各个配送车的所有行程线：配送车1包含1个行程，线路为：配送中心-客户、6-客户、3-配送中心；配送车2包含2个行程，线路1为：配送中心-客户、7-客户、8-配送中心；线路2为：配送中心-客户、5-客户、1-客户、2-配送中心；配送车3包含1个行程，线路为：配送中心-客户、4-客户、9-配送中心。
[0061]
针对模型的np难特点，采用精确算法求取小规模、中规模问题的精确解和启发式算法的求解结果进行对比，并利用拉格朗日松弛法求取大规模问题解的界限，以此来设计智能优化方法，具体如图3：
[0062]
本发明的创新点如下：
[0063]
创新点1、本发明同时考虑订单服务时间、多车、多目标、运量约束等构建的多车多
目标无人车路径优化模型。本发明多车多目标无人车路径优化问题，构建路径优化模型，将充实相关理论，弥补既有研究的不足。
[0064]
创新点2、基于启发式算法的多车多目标无人车路径优化模型求解方法，本发明针对遗传算法容易陷入局部搜索的问题，综合利用模拟退火算法等设计的混合智能优化算法具有一定的创新。
[0065]
实验仿真与分析
[0066]
实例验证的输入数据共有1个配送中心和随机生成的50个站点，每个点的数据如表4所示，1000个客户订单随机分布在站点中，无人车的行驶速度为10km/h，每辆车的最大载重为100单，用户取订单时间为1分钟。
[0067][0068][0069]
退火遗传算法参数设置
[0070]
在运行退火遗传算法(sa-ga)之前，需要对相应的参数进行设置，各个参数如表5所示。
[0071][0072]
实验结果展示：
[0073]
运用sa-ga求解模型，优化过程如图4所示，最优配送方案路线如图5所示，同样的当算法迭代到99代时，达到了最优解，最短行驶总距离1786.5147m。
[0074]
最终优化结果为11辆无人车，车辆行驶总时间为1786.5147m,每条配送路线详细信息如表6所示。
[0075][0076]
两种算法对比分析
[0077]
传统遗传算法(ga)求解模型，优化过程如图6所示，最优配送方案路线如图7所示，可以看到当算法迭代到11代时，最优行驶总距离为1844.6335m。
[0078]
最终优化结果为11辆无人车，车辆行驶总时间为1844.6335m,每条配送路线详细信息如表7所示，行驶配送总时间，达到最优解时的迭代次数，以及平均每单配送用时如表8,9,10所示。
[0079]
最终配送方案路线
[0080]
[0081][0082]
ga算法
[0083]
ga算法行驶总距离(m)最优解时迭代次数车辆行驶总时间(min)11914.416720661.486521901.8053961.410831880.03813561.280241844.63351161.067851900.274740361.4016平均1888.2337132.861.3293
[0084]
sa-ga算法
[0085][0086][0087]
ga算法与sa-ga算法的对比
[0088][0089]
由从表10中可以看到，遗传算法和退火遗传算法最少使用车辆数都为11辆，在平均行驶总距离上，改进后的遗传算法比传统遗传算法节约77.6822m，平均配送总用时上减少0.466min,在寻优迭代中，基于模拟退火的遗传算法在133代达到了最优解，而传统遗传算法则是80代，仿真实例结果表明，改进遗传算法比传统遗传算法求解效率更高、求解结果更加稳定，算法的鲁棒性也更强。
[0090]
以上所述，仅为本公开的具体实施方式，但本公开实施例的保护范围并不局限于此，任何熟悉本技术领域的技术人员在本公开实施例揭露的技术范围内或者在本公开实施例揭露的思想下，可轻易想到变化、替换或组合，都应涵盖在本公开实施例的保护范围之内。

技术特征：
1.一种多车多目标无人车路径优化方法，其特征在于包括如下步骤：1)配送中心选址：将现有各个供应点或需求点看成是分布在某一平面内的物流运输系统的节点，从而确定物流系统的重心；2)构建单行程下的多车多目标无人车路径优化模型：对于路径优化问题，通常假设距离、速度等参数已知，在一定约束下，建立以行驶距离、行驶时间为目标的数学模型；3)开发单行程下的多车多目标无人车路径优化算法：选择以并行计算能力突出的遗传算法为框架，采用排列的编码方式；4)构建多行程下的多车多目标无人车路径优化模型；5)开发多行程下的多车多目标无人车路径优化算法：构造多行程下的多车多目标无人车路径优化算法，实现多行程下的多车多目标无人车路径优化模型的算法求解。2.根据权利要求1所述的一种多车多目标无人车路径优化方法，其特征在于所述步骤3)中在遗传算法的变异算子中引入模拟退火算法，对个体进行局部操作，增强算法的局部搜索能力，以促使算法跳出局部最优，进而通过多种算法优点的结合来设计混合智能优化算法。3.根据权利要求1所述的一种多车多目标无人车路径优化方法，其特征在于所述步骤5)中编码过程包括如下步骤：1)利用总行程符(2n-1)～2n+(m-2)确定每个配送车辆总的行程的编码；2)利用单个配送车辆行程分割符确定每个配送车辆的具体行程。4.根据权利要求1所述的一种多车多目标无人车路径优化方法，其特征在于所述步骤1)中采用实证研究与数据挖掘相结合的方法，利用粗糙集理论进行属性约简，去除冗余因素，降低模型的维度。5.根据权利要求1所述的一种多车多目标无人车路径优化方法，其特征在于所述步骤1)中利用广义成本最小化来处理该问题，构建广义成本最小化目标函数，从系统的角度构建考虑订单需求变化不确定因素构建路径优化模型。6.根据权利要求1所述的一种多车多目标无人车路径优化方法，其特征在于所述采用精确算法求取小规模、中规模问题的精确解和启发式算法的求解结果进行对比，并利用拉格朗日松弛法求取大规模问题解的界限。

技术总结
本发明公开了一种多车多目标无人车路径优化方法，属于信息数据处理及传输技术领域。本发明通过配送中心选址、构建单行程下的多车多目标无人车路径优化模型、开发单行程下的多车多目标无人车路径优化算法、构建多行程下的多车多目标无人车路径优化模型、开发多行程下的多车多目标无人车路径优化算法这五个步骤予以实现。本发明的模型及算法适用于多车多目标无人车路径优化，支持多方案的快速比选。本发明的算法以最小化车辆数、无人车行驶总时间、配送总用时、订单配送用时等为目标，实现在给定订单总量、站点数量、行驶速度等环境下，快速完成优化计算。本发明采用智能化的算法自动计算生成无人车路径方案，不需要人工预先输入线路走向等信息。线路走向等信息。线路走向等信息。


技术研发人员：刘松 周思徽 林文婷 刘狄 高新华 冯诗媛 蔺雅芝 李晶晶 屈杰庆 彭勇
受保护的技术使用者：重庆交通大学
技术研发日：2023.04.20
技术公布日：2023/7/25