一种基于多约束修正C-W算法优化解决智能无人车路径规划问题的方法

摘要

本发明公开了一种基于多约束修正C‑W算法优化解决智能无人车路径规划问题的方法。本发明是通过对简单的C‑W算法进行修改，在已有的路径优化上添加限重、时间窗、车辆种类不同约束条件，对智能无人车派送路线进行规划形成的一种方法。本发明先是对实际问题进行建模，再使用修正的C‑W算法解决派送路线规划中限重、时间窗的约束问题，然后根据运输任务优化类型的不同对规划的路线进行不同处理，从而找到一种最佳的无人车派送方案。

说明书

技术领域

本发明涉及物流派送领域，具体为一种基于多约束修正C-W算法优化解决智能无人车路径规划问题的方法。

背景技术

车辆调度问题是物流管理中非常重要的一个问题,通常指的是，在特定的约束条件下,企业通过调配一定的车辆,并且组织适当的行车线路为客户进行配送货物,力争实现一定的目标,例如运输距离、费用最小化。配送中仅考虑空间而不考虑时间的问题称为车辆路径问题(Vehicle routing Problem,简称VRP)。当配送时具有时间窗约束时,这样的问题为车辆调度问题(Vehicle Scheduling Problem,简称 VSP)。VSP广泛应用于大型制造装配、钢铁、物流运输以及大型连锁零售等行业具有很强的现实应用背景。随着科技的快速发展，无人车送货技术即将出现在人们的生活中。未修正的C-W算法是解决TSP问题的一种算法，但将它运用到无人车派送路径优化调度上只能找到最短路径，而不能解决多无人车分配、无人车限重和时间窗问题。

为了解决多无人车分配、无人车限重和时间窗问题，出现了很多修正的算法。虽然它们能够地解决配送车辆调度问题,但是当存在多个约束条件时,这些算法就会存在计算量大、收敛速度慢等问题。尤其当存在硬约束的时间窗和车辆种类不同时,上述算法的缺点就更加突出。

发明内容

本发明的目的是为了解决无人车派送中限重、时间窗和车辆种类不同所产生的问题，提出了一种基于多约束修正C-W算法优化解决智能无人车路径规划问题的方法。

为实现上述目的，本发明提供如下技术方案：

步骤一：根据实际问题模型，对实际问题描述并建立模型。

步骤二：在C-W节约算法的基础上，添加限重、时间窗的约束对 C-W算法修正优化，并在两个约束下的优化算法试解决实际路径优化。

步骤三：再添加车辆类型的约束再次实现路径优化，构成多约束下多无人车的路径优化系统，并测试算法性能。

步骤四：根据实际问题模型，确定运输任务优化类型。

步骤五：根据运输任务优化类型，做不同的处理，最后得到最佳路线。

优选的，所述步骤一：根据实际问题进行描述。

在由一个x个客户和m辆配送车辆数量组成的系统中,其中x个客户之间有有限的货物需要m辆配送车辆进行配送，而每种派送车辆载重不同。在满足配送车辆载重量、客户对货物运输的时间窗等约束条件下选择最适合的车辆,通过优化得到最小成本下的车辆调度方案。

优选的，所述步骤一：根据实际问题建立模型。

一个车场派出载重量为q(k)的货车为L个客户进行货物配送,每个客户i的货运量为g(i),i＝1,2,,,n.其中,g(i)≤q(k),并且配送中心用0表示。每个客户i接受服务的时间窗为[ET

根据费用最小化原则,建立路径规划问题的目标函数Z。

对于无人车的路径规划，最后要找到的是路径的最小值，即最小的Z,具体函数为：

其中相关的符号定义为：

i:第i个客户,i＝0,1,2,,,其中0表示配送中心；

q(k):车辆载重量,j＝(1,2....,n),用k区分不同的车辆种类；

g(i):客户i的货运量；

C

T

ET

LT

RT

t

k:配送车辆类型,k＝1,2...,m；

x

y

优选的，所述步骤二：在C-W节约算法的基础上，添加限重、时间窗的约束对C-W算法修正优化，并在两个约束下的优化算法试解决实际路径优化。

考虑到车辆限重和客户时间窗约束，则需满足以下条件；(1) 所有用户的要求；(2)不使任何一辆车超载；(3)每辆车每天的总运行时间或行驶里程不超过规定的上限；(4)用户到货时间要求。

具体算法步骤：

步骤1：计算所有可能配送车辆可能涉及到的线路s(i,j),并收入到M集合中。

步骤2：将M中的元素进行排序。

步骤3：如果N＝b,则计算终止。否则,由于集合M中的元素已经按照大小进行排列,因此对集合M第一项s(i,j),即集合M中的最大项考察,并且选出由此相对应的(i,j)。

若满足下述情形之一,则算法继续进行：

①点i和j均处在初始化线路中；

②点i和点j一个在初始化线路中,一个在已构点成线路中,且直接与车场相连；

③点i和点j均在已构成线路中,且都直接与车场相连；

步骤4：对经过点和点j线路上的总货运量进行计算,如果总货运量小于单个车辆装载量q,则转入步骤5；如果大于等于车辆装载量 q,则转入步骤7。

步骤5：计算EF,并考虑三种情形，

①若EF

②若EF

③若,则对进行计算

步骤6：再次连接点i和点j,计算出配送车辆所需的新时间或费用,并且转步骤7。

步骤7：令M＝M-(i,j),转步骤3。

其中相关符号定义为：

s(i,j)：点i和点j连接的节约值。计算公式：s(i,j)＝C

EF

R：点j后面的各点；

计算公式：

优选的，所述步骤三：再添加车辆类型的约束再次实现路径优化，构成多约束下多无人车的路径优化系统，并测试算法性能。

现实的车辆分配并不是统一类型的载重的车辆，所以就存在不同载重的车辆参与其中。对于该部分的问题解决，利用遗传算法改变遗传因子使分配方案中有多种解，找出本次派送中最便利的方案。

将构成多约束下多无人车的路径优化系统进行参数调整，使用数据分析工具测试算法性能。通过对最终形成系统的仿真，不断调整和修改方案，将其可视化达到最佳效果。

优选的，所述步骤四：根据实际问题模型，确定运输任务优化类型。

本步骤首先确定任务是属于何种运输优化类型，然后根据系统所确定运输优化类型，来选择不同的优化算法。运输优化类型区分为非规划型和规划型两大类型。非规划型优化这类任务的任务量比较少，大部分的车辆都处于停车场，这种类型结构比较简单。规划型优化主要是车辆都处于动态状态，货物数量非常多，而且车辆要少于货物数量的情况。

若采用非规划型的任务优化方式，这种任务因为车辆数要多于货物数，其优化方案是直接采用遗传算法决策出最佳的派送方案。

若采用规划型的任务优化方式，这种任务因为货物数要多于车辆数，其优化方案是采用限重、时间窗约束下修正的C-W算法进行路径规划，即权利要求1中所述步骤二所使用的修正算法，然后再通过遗传算法解决车辆类型不同约束下路径规划问题，最后选出最佳的派送方案。

优选的，所述步骤五：根据运输任务优化类型，做不同的处理，最后得到最佳路线。

根据步骤四可确定运输任务优化类型，采用不同的处理，分为非规划型的任务优化方式和规划型的任务优化方式。当车辆数要多于货物数时，选择非规划型的任务优化方式，只需要遗传算法来得到最佳路线。当车辆数要远少于货物数时，选择规划型的任务优化方式，就需要先使用限重、时间窗约束下修正的C-W算法找到最佳路线，然后再通过遗传算法解决车辆类型不同约束下路径规划问题，最后选出最佳的派送方案。

与现有技术相比，本发明的有益效果是：

1.与未修正的C-W算法相比，修正后的C-W算法更加适合于车辆在多约束条件下的路径优化，主要体现在：①未修正的算法只能寻找到一条最短的路线，且只有一条路线，而对于车辆的调度肯定需要的是多无人车多条路线，并且无人车辆是限重的；②未修正的C-W算法中未体现时间窗问题，这不利于物流车辆中派送。所以经过对C-W算法的改进，使这种分配方法表现出较大的优势。

2.因为派送中心所分配的无人车种类是不同的，这导致每种车辆的限重不同。因此，采用遗传算法与修正后的C-W算法相结合后，使得多次迭代后能寻找到最优的路径规划。

3.针对任务的优化类型不同采取了不同的优化方式，即非规划型优化和规划性优化，分类处理可大大节约时间。

附图说明

图1为本发明的具体技术线路示意图。

图2为本发明根据实际问题建立模型的交通路线图。

图3为本发明限重、时间窗约束下修正C-W算法产生的具体派送路线图。

图4为本发明确定运输任务的优化类型及解决方案示意图。

具体实施方式

下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

请参阅图1-4，本发明提供一种技术方案：

步骤一：根据实际问题模型，对实际问题描述并建立模型。

步骤二：在C-W节约算法的基础上，添加限重、时间窗的约束对 C-W算法修正优化，并在两个约束下的优化算法试解决实际路径优化。

步骤三：再添加车辆类型等的约束再次实现路径优化，构成多约束下多无人车的路径优化系统，并测试算法性能。

步骤四：根据实际问题模型，确定运输任务优化类型。

步骤五：运行测试后的路径优化系统，从而解决任务。

如图1为本发明的具体技术线路示意图。

步骤一中，根据实际问题进行描述。

在由一个x个客户和m辆配送车辆数量组成的系统中,其中x个客户之间有有限的货物需要m辆配送车辆进行配送，而每种派送车辆载重不同。在满足配送车辆载重量、客户对货物运输的时间窗等约束条件下选择最适合的车辆,通过优化得到最小成本下的车辆调度方案。

步骤一中，根据实际问题建立模型。

如图2为本发明根据实际问题建立模型的交通路线图。一个车场派出载重量为q(k)的货车为L个客户进行货物配送,每个客户i的货运量为g(i),i＝1,2,,,n.其中,g(i)≤q(k),并且配送中心用0表示。每个客户i接受服务的时间窗为[ET

根据费用最小化原则,建立路径规划问题的目标函数Z。

对于无人车的路径规划，最后要找到的是路径的最小值，即最小的Z,具体函数为：

其中相关的符号定义为：

i:第i个客户,i＝0,1,2,,,其中0表示配送中心；

q(k):车辆载重量,j＝(1,2....,n),用k区分不同的车辆种类；

g(i):客户i的货运量；

C

T

ET

LT

RT

t

k:配送车辆类型,k＝1,2...,m；

x

y

步骤二中，在C-W节约算法的基础上，添加限重、时间窗的约束对C-W算法修正优化，并在两个约束下的优化算法试解决实际路径优化。

考虑到车辆限重和客户时间窗约束，则需满足以下条件；(1) 所有用户的要求；(2)不使任何一辆车超载；(3)每辆车每天的总运行时间或行驶里程不超过规定的上限；(4)用户到货时间要求。

具体算法步骤：

步骤1：计算所有可能配送车辆可能涉及到的线路s(i,j),并收入到M集合中。

步骤2：将M中的元素进行排序。

步骤3：如果N＝b,则计算终止。否则,由于集合M中的元素已经按照大小进行排列,因此对集合M第一项s(i,j),即集合M中的最大项考察,并且选出由此相对应的(i,j)。

若满足下述情形之一,则算法继续进行：

①点i和j均处在初始化线路中；

②点i和点j一个在初始化线路中,一个在已构点成线路中,且直接与车场相连；

③点i和点j均在已构成线路中,且都直接与车场相连；

步骤4：对经过点和点j线路上的总货运量进行计算,如果总货运量小于单个车辆装载量q,则转入步骤5；如果大于等于车辆装载量 q,则转入步骤7。

步骤5：计算EF,并考虑三种情形，

①若EF

②若EF

③若,则对进行计算

步骤6：再次连接点i和点j,计算出配送车辆所需的新时间或费用,并且转步骤7。

步骤7：令M＝M-(i,j),转步骤3。

根据以上的步骤可以得到如图3为本发明限重、时间窗约束下修正C-W算法产生的具体派送路线图。

其中相关符号定义为：

s(i,j)：点i和点j连接的节约值。计算公式：s(i,j)＝C

EF

R：点j后面的各点；

计算公式：

步骤三中，再添加车辆类型的约束再次实现路径优化，构成多约束下多无人车的路径优化系统，并测试算法性能。

现实的车辆分配并不是统一类型的载重的车辆，所以就存在不同载重的车辆参与其中。对于该部分的问题解决，利用遗传算法改变遗传因子使分配方案中有多种解，找出本次派送中最便利的方案。

将构成多约束下多无人车的路径优化系统进行参数调整，使用数据分析工具测试算法性能。通过对最终形成系统的仿真，不断调整和修改方案，将其可视化达到最佳效果。

步骤四中，根据实际问题模型，确定运输任务优化类型。

本步骤首先确定任务是属于何种运输优化类型，然后根据系统所确定运输优化类型，来选择不同的优化算法。运输优化类型区分为非规划型和规划型两大类型。非规划型优化这类任务的任务量比较少，大部分的车辆都处于停车场，这种类型结构比较简单。规划型优化主要是车辆都处于动态状态，货物数量非常多，而且车辆要少于货物数量的情况。

若采用非规划型的任务优化方式，这种任务因为车辆数要多于货物数，其优化方案是直接采用遗传算法决策出最佳的派送方案。

若采用规划型的任务优化方式，这种任务因为货物数要多于车辆数，其优化方案是采用限重、时间窗约束下修正的C-W算法进行路径规划，即权利要求1中所述步骤二所使用的修正算法，然后再通过遗传算法解决车辆类型不同约束下路径规划问题，最后选出最佳的派送方案。如图4为本发明确定运输任务的优化类型及解决方案示意图。

步骤五中，根据运输任务优化类型，做不同的处理，最后得到最佳路线。

根据步骤四可确定运输任务优化类型，采用不同的处理，分为非规划型的任务优化方式和规划型的任务优化方式。当车辆数要多于货物数时，选择非规划型的任务优化方式，只需要遗传算法来得到最佳路线。当车辆数要远少于货物数时，选择规划型的任务优化方式，就需要先使用限重、时间窗约束下修正的C-W算法找到最佳路线，然后再通过遗传算法解决车辆类型不同约束下路径规划问题，最后选出最佳的派送方案。

本发明的工作原理为：根据实际问题模型，对实际问题描述并建立模型，在C-W节约算法的基础上，添加限重、时间窗以及车辆类型的约束对C-W算法修正优化，共同构成多约束下多无人车的路径优化系统，智能无人车在接收到传过来的相关信息进行分析，确定任务优化类型，并运行此路径优化系统，然后能找到最佳派送路线，最后无人车完成派送任务。

对于本领域技术人员而言，显然本发明不限于上述示范性实施例的细节，而且在不背离本发明的精神或基本特征的情况下，能够以其他的具体形式实现本发明。因此，无论从哪一点来看，均应将实施例看作是示范性的，而且是非限制性的，本发明的范围由所附权利要求而不是上述说明限定，因此旨在将落在权利要求的等同要件的含义和范围内的所有变化囊括在本发明内。不应将权利要求中的任何附图标记视为限制所涉及的权利要求。