CN109102122A - 一种基于nsgaii分组处理大规模带容量约束的方法及系统 - Google Patents

Abstract

本发明提供一种基于NSGAII分组处理大规模带容量约束的车辆路径问题的方法，包括步骤：数据预处理；参数初始化，定义初始迭代次数与最大迭代次数，并初始化一个可行解作为参考解；判断迭代次数是否到达所述最大迭代次数；通过多目标算法NSGAII对所述参考解进行优化分组；通过禁忌搜索算法对分组后第一前沿面上的子问题进行优化处理；更新所述参考解，累积迭代次数；将所述参考解作为最优解输出。

Description

一种基于NSGAII分组处理大规模带容量约束的方法及系统

技术领域

本发明涉及智能交通技术领域，具体涉及一种基于NSGAII分组处理大规模带容量约束的方法及系统。

背景技术

在当今的电子商务时代，全球物流产业有了新的发展趋势。现代物流服务的核心目标是在物流全过程中以最小的综合成本来满足顾客的需求。现在电商的快速崛起和行业的需求，对于仓储物流配送这一重要环节的需求和要求也在不断提高，第三方公司在市场行业中也扮演着越来越重要的角色，甚至能够协助商家在终端和渠道端提供广泛的服务。随着物流行业的发展，需要服务的客户越来越多，导致车辆调度规模越来越大。

车辆路由问题(Vehicle Routing Problem，简称VRP)是指对一系列特定位置和需求量的客户点，调用一定数量的车辆，从中心仓库出发，选择最优的行车路线并有序地访问各个客户点，在满足特定的约束条件下，使得货物尽快到达客户点并且运输总费用达到最低要求。

传统的车辆路由解决方法，主要是依据物流经验，有一定的随机性和偶然性，不具备科学性。随着科学技术的发展，目前解决车辆路由问题主要有四种算法：一、基于拉格朗日松弛、列生成和动态规划三种策略的精准算法，这种算法可以求解的算例规模非常小；二、途程构建启发式算法，在问题中一某节点选择原则或是路线安排原则，这种算法需要将需求点一一纳入途程路线解决；三、途程改善启发式算法，先决定一个可行途程，也就是一个起始解，之后对这个起始解一直做改善，直到不能改善为止；四、通用启发式算法，传统区域搜索方法的最佳解常因起始解特性或搜寻方法的限制，而只能获得局部最佳解，通用启发式算法是新一代启发式解法，包含禁忌搜索算法、模拟退火算法、遗传算法和门坎接受法等，可以有效解决陷入局部最优的问题。上述四类方法都不能有效解决规模较大时的车辆路由问题。

发明内容

针对现有技术的不足，本发明提供一种基于NSGAII分组处理大规模带容量约束的方法及系统，以期能够在需要服务的客户节点特别多时，能够有效解决车辆路由问题。

为实现以上目的，本发明通过以下技术方案予以实现：

一种基于NSGAII分组处理大规模带容量约束的方法，包括步骤：

步骤一、参考解预处理；

步骤二、参数初始化，定义初始迭代次数与最大迭代次数，并初始化一个可行解作为参考解；

步骤三、判断迭代次数是否到达所述最大迭代次数；如果是，执行步骤七；否则执行步骤四；

步骤四、通过多目标算法NSGAII对所述参考解进行优化分组；

步骤五、通过禁忌搜索算法对分组后第一前沿面上的子问题进行优化处理；

步骤六、更新所述参考解，累积迭代次数并返回步骤三；

步骤七、将所述参考解作为最优解输出。

进一步地，所述步骤一具体包括参考解编码和参考解解码；所述参考解编码为使用自然数编码对参考解进行编码，编码长度等于客户节点数目加可使用车辆数目加1。

进一步地，所述步骤四具体包括以下步骤：

步骤A、个体编码；

步骤B、个体解码；

步骤C、初始化种群；

步骤D、选择合适个体；

步骤E、种群进化。

进一步地，所述步骤五具体包括以下步骤：

步骤F、随机生成一个子问题中客户的序列，按车辆尽可能满载的原则插入仓库节点，生成初始解，清空禁忌表，设置禁忌长度；

步骤G、将所述初始解，通过搜索算子产生候选解，并计算各个候选解的适应度值；

步骤H、将所有所述候选解中选出适应度值最好的候选解。

本发明还提供一种基于NSGAII分组处理大规模带容量约束的系统，包括：

预处理模块，用于参考解预处理；

参数初始化模块，用于参数初始化，定义初始迭代次数与最大迭代次数，并初始化一个可行解作为参考解；

判断模块，用于判断迭代次数是否到达所述最大迭代次数；如果是，进入输出模块；否则进入分组模块；

分组模块，用于通过多目标算法NSGAII对所述参考解进行优化分组；

处理模块，用于通过禁忌搜索算法对分组后第一前沿面上的子问题进行优化处理；

参数更新模块，用于更新所述参考解，累积迭代次数并进入判断模块；

输出模块，用于将所述参考解作为最优解输出。

进一步地，所述预处理模块包括参考解编码子模块和参考解解码子模块。

进一步地，所述分组模块包括：

个体编码子模块，用于个体编码；

个体解码子模块，用于个体解码；

种群初始化子模块，用于初始化种群；

个体筛选子模块，用于选择合适个体；

种群进化子模块，用于种群进化。

进一步地，所述处理模块包括：

初始化子模块，用于随机生成一个子问题中客户的序列，按车辆尽可能满载的原则插入仓库节点，生成初始解，清空禁忌表，设置禁忌长度；

候选解处理子模块，用于将所述初始解，通过搜索算子产生候选解，并计算各个候选解的适应度值；

候选解筛选子模块，用于将所有所述候选解中选出适应度值最好的候选解。

与现有技术相比，本发明具有以下有益效果：

目前的大多数解决带容量限制的车辆路由问题的算法在小规模问题上或许能提供比较好的解，但是当问题规模变大时就无法提供较优解。本发明通过采用分组的方式，将大问题转换成小问题求解，将难点转移到如何分组上，并利用多目标优化算法解决了这个难点。

附图说明

为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。

图1为本发明算法流程图；

图2为本发明系统结构图；

图3为本发明中分组模块结构图；

图4为本发明中处理模块结构图。

具体实施方式

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

本发明实施例提供一种基于NSGAII分组处理大规模带容量约束的方法及系统。

定义所述网络表征为G(V,E)，V＝{v₁,v₂,…,v_i,…,v_n}表示所述网络中所有节点的集合，v_i表示第i个节点；n为节点的总数；v₁表示仓库节点，其余节点均为客户节点。E＝{e_ij|i＝1,2,…,n；j＝1,2,…,n}表示任意两个节点之间的路径距离的集合；e_ij表示第i个节点v_i与第j个节点v_j之间的距离；约束为车容量约束。

步骤1、参考解编码及解码：

步骤1.1：参考解编码

使用自然数编码对参考解进行编码，其编码长度等于客户节点数目加上可使用车辆数目再加一；个体编码为X＝{g₁,g₂,...,g_i,...,g_m},g_i＝0表示第i个节点为仓库节点，g_i＝{1,2,3,4…}表示客户节点；

步骤1.2：参考解解码

步骤1.2.1：初始化遍历个体参数i为1，记录下标参数k为1；

步骤1.2.2：找到下一个基因位值为0的节点的下标i，k到i之间的节点为一辆车服务的所有客户节点；

步骤1.2.3：将i赋给k，执行步骤1.2.2，直到i的值大于个体编码长度。从而得到n条路径c＝{c₁,c₂,...,c_r,...,c_n}，其中c_r表示第r条路径；

步骤2、初始化

步骤2.1：定义最大迭代次数为T，初始迭代次数为t＝1；

步骤2.2：使用贪心思想初始化一个可行解X_g作为参考解；

步骤3、进化过程中更新参考解

在进化过程中利用多目标算法(NSGAII)优化分组，再通过禁忌搜索算法(Tabu)对第一前沿面上的子问题进行优化，再去更新参考解，通过嵌套优化解决大规模带容量约束的车辆路由问题；

步骤3.1：NSGAII优化分组

步骤3.1.1:个体编码及解码

分组编码使用0～1之间的小数和不大于路径数与分组数的商来编码，编码长度为参考解中的路径数加上分组数减一；个体编码为X＝{g₁,g₂,...,g_i,...,g_m}；

步骤3.1.2：个体解码

步骤3.1.2.1：假设路径数为n,分组数为G,将个体X的前n位进行升序排序，得到路径编号的一个序列；

步骤3.1.2.2：然后按照后G-1位的基因值，对路径编号的序列进行切割，从而得到路径的一个分组c＝{c₁,c₂,...,c_r,...,c_n}，其中c_r表示第r个分组；

步骤3.1.3:初始化种群

步骤3.1.3.1：定义最大迭代次数为maxgen，初始迭代次数为g＝1，种群个体的数目为pop,路径数为n,分组数为G；

步骤3.1.3.2：设种群中有pop个个体{X₁,X₂，…,X_g,…,X_pop}；X_g表示第g个个体；

步骤3.1.3.3：随机生成n个0～1之间的数，再随机生成G-1个不大于n/G的整数，合并在一起得到第g个个体X_g；

步骤3.1.3.4：执行pop次步骤3.1.1.3得到初始种群的编码

步骤3.1.4：选择合适个体P'

如果随机的从种群中选取个体或者选取种群中所有个体进行判断分组好坏，得到的结果往往不是很理想，所以从分组之间的距离和分组内部距离以及分组中客户节点数目来判断是否是合适个体。首先，个体解码之后的分组之间的距离要大且分组内部距离要小，因为分组之间的距离越大且分组内部距离要小，表示该个体解码后的分组效果越好。其次考虑到若个体客户点的分组不均匀，得到的子问题的规模还是较大，求解子问题的难度太大，达不到想要的效果；

步骤3.1.4.1：按照步骤3.1.2对第t代种群中的每个个体进行解码，得到若干个路径分组，其中第g个个体的内部距离看成一个目标函数；第g个个体的外部距离的倒数看成一个目标函数；第g个个体解码得到的分组中客户点数目差值的和看成一个目标函数。

步骤3.1.4.2：执行pop次步骤3.1.4.1，得到第i代种群的三个目标值，把第i代种群中个体按照对应三个目标值值进行非支配最小化排序，选取第一前沿面中的个体作为合适个体P'＝{P'₁,P'₂,...,P'_g,...,P'_num}，P'_g表示P'中第g个个体；

步骤3.1.5、种群进化：

步骤3.1.5.1：初始化初始迭代次数变量g＝1；

步骤3.1.5.2：采用二元联赛选择父代，采用多点交叉方式生成新的子代child；

步骤3.1.5.3：根据步骤3.1.4.1计算新产生的个体child；

再计算子代child的三个目标函数值，合并子代和父代，通过非支配排序选择下一代种群的个体；

步骤3.1.5.3：将g+1赋给g，重复执行步骤3.1.5.2，直到达到最大迭代次数为止；

步骤3.2：禁忌搜索优化子问题的车辆路由

步骤3.2.1：初始化

随机生成一个子问题中客户的序列，按车辆尽可能满载的原则插入仓库节点，生成初始解，清空禁忌表，设置禁忌长度；

步骤3.2.2：邻域搜索产生候选解

根据步骤3.2.1产生初始解，通过搜索算子relocation、exchange、2-opt等产生候选解，并计算各个候选解的适应度值(这里目标函数为路由总距离)；

步骤3.2.3：选择最好的候选解

从步骤3.2.2产生的所有候选解中选出适应度值最好的候选解，将其与当前最好解(即搜索算法开始到现在找到的最好解)进行比较，如果优于当前最好解，就不考虑其是否被禁忌，用这个最好的候选解来更新当前最好解，并且作为下一个迭代的当前解，然后将对应操作加入禁忌表，如果不优于当前最好解，就从所有候选解中选出不在禁忌状态下的最好解作为新的当前解，然后将对应操作加入禁忌表。

步骤3.2.4：判断终止条件

若满足终止条件，则立即停止并输出当前最好解；否则继续搜索，终止条件为最大迭代次数；

步骤3.3：对每个子组件得到的解合并，并计算其适应度，与当前参考解适应度值比较，如果优于当前参考解，则更新当前参考解，否则，不更新；

步骤3.4：将t+1赋给t，重复执行步骤3.1，直到t＞maxgen为止，输出最优的路由结果。

需要说明的是，在本文中，诸如第一和第二等之类的关系术语仅仅用来将一个实体或者操作与另一个实体或操作区分开来，而不一定要求或者暗示这些实体或操作之间存在任何这种实际的关系或者顺序。而且，术语“包括”、“包含”或者其任何其他变体意在涵盖非排他性的包含，从而使得包括一系列要素的过程、方法、物品或者设备不仅包括那些要素，而且还包括没有明确列出的其他要素，或者是还包括为这种过程、方法、物品或者设备所固有的要素。在没有更多限制的情况下，由语句“包括一个……”限定的要素，并不排除在包括所述要素的过程、方法、物品或者设备中还存在另外的相同要素。

以上实施例仅用以说明本发明的技术方案，而非对其限制；尽管参照前述实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本发明各实施例技术方案的精神和范围。

Claims (8)

1.一种基于NSGAII分组处理大规模带容量约束的方法，其特征在于，所述方法包括步骤：

步骤一、参考解预处理；

步骤二、参数初始化，定义初始迭代次数与最大迭代次数，并初始化一个可行解作为参考解；

步骤三、判断迭代次数是否到达所述最大迭代次数；如果是，执行步骤七；否则执行步骤四；

步骤四、通过多目标算法NSGAII对所述参考解进行优化分组；

步骤五、通过禁忌搜索算法对分组后第一前沿面上的子问题进行优化处理；

步骤六、更新所述参考解，累积迭代次数并返回步骤三；

步骤七、将所述参考解作为最优解输出。

2.根据权利要求1所述的一种基于NSGAII分组处理大规模带容量约束的方法，其特征在于：所述步骤一具体包括参考解编码和参考解解码；所述参考解编码为使用自然数编码对参考解进行编码，编码长度等于客户节点数目加可使用车辆数目加1。

3.根据权利要求1所述的一种基于NSGAII分组处理大规模带容量约束的方法，其特征在于，所述步骤四具体包括以下步骤：

步骤A、个体编码；

步骤B、个体解码；

步骤C、初始化种群；

步骤D、选择合适个体；

步骤E、种群进化。

4.根据权利要求1所述的一种基于NSGAII分组处理大规模带容量约束的方法，其特征在于：所述步骤五具体包括以下步骤：

步骤F、随机生成一个子问题中客户的序列，按车辆尽可能满载的原则插入仓库节点，生成初始解，清空禁忌表，设置禁忌长度；

步骤G、将所述初始解，通过搜索算子产生候选解，并计算各个候选解的适应度值；

步骤H、将所有所述候选解中选出适应度值最好的候选解。

5.一种基于NSGAII分组处理大规模带容量约束的系统，其特征在于，所述系统包括：

预处理模块，用于参考解预处理；

参数初始化模块，用于参数初始化，定义初始迭代次数与最大迭代次数，并初始化一个可行解作为参考解；

判断模块，用于判断迭代次数是否到达所述最大迭代次数；如果是，进入输出模块；否则进入分组模块；

分组模块，用于通过多目标算法NSGAII对所述参考解进行优化分组；

处理模块，用于通过禁忌搜索算法对分组后第一前沿面上的子问题进行优化处理；

参数更新模块，用于更新所述参考解，累积迭代次数并进入判断模块；

输出模块，用于将所述参考解作为最优解输出。

6.根据权利要求5所述的一种基于NSGAII分组处理大规模带容量约束的系统，其特征在于：所述预处理模块包括参考解编码子模块和参考解解码子模块。

7.根据权利要求5所述的一种基于NSGAII分组处理大规模带容量约束的系统，其特征在于，所述分组模块包括：

个体编码子模块，用于个体编码；

个体解码子模块，用于个体解码；

种群初始化子模块，用于初始化种群；

个体筛选子模块，用于选择合适个体；

种群进化子模块，用于种群进化。

8.根据权利要求5所述的一种基于NSGAII分组处理大规模带容量约束的系统，其特征在于，所述处理模块包括：

初始化子模块，用于随机生成一个子问题中客户的序列，按车辆尽可能满载的原则插入仓库节点，生成初始解，清空禁忌表，设置禁忌长度；

候选解处理子模块，用于将所述初始解，通过搜索算子产生候选解，并计算各个候选解的适应度值；

候选解筛选子模块，用于将所有所述候选解中选出适应度值最好的候选解。