CN114707693A - 一种车辆配送路径规划方法及系统 - Google Patents

Abstract

本发明涉及一种车辆配送路径规划方法及系统，首先，获取获取配送中心节点位置信息、客户信息和车辆信息，并据此以总配送车辆里程最短为目标建立目标函数；然后通过扫描算法求得一个初始解，以所述目标函数为目标值，利用改进大规模邻域搜索算法结合Metropolis准则选择最优的车辆配送路径。利用改进的大规模邻域搜索算法能够筛选出车辆最优的配送路径，从而制定出更合理的配送路径方案，提高了配送效率，同时也大大降低了车辆总配送里程，减少了人工制订方案的工作强度。

Description

一种车辆配送路径规划方法及系统

技术领域

本发明涉及货物配送领域，特别是涉及一种基于改进自适应大规模邻域搜索算法的大规模车辆配送路径规划方法及系统。

背景技术

车辆路径的研究是近十年来的热点问题，已成为物流配送的一个发展趋势。其与实际生活中资源配送和路径规划息息相关，主要解决当多辆有容量限制的配送车辆服务多个客户节点时，如何合理规划确定最优车辆路径的问题。随着配送问题规模的增大，即配送客户节点数量的增加，配送方案的制订变得更为复杂，现有的方案中一般是依靠人工经验，然而仅仅依靠人工经验难以得到车辆路径较优的配送方案，造成了人工和时间浪费。

因此，本领域亟需一种可用于大规模客户的车辆最优配送路径的规划方案。

发明内容

本发明的目的是提供一种车辆配送路径规划方法及系统，选择车辆最大载重量这一配送限制，以带容量约束的车辆路径问题作为车辆配送的模型，以配送方案中各车辆配送里程最短为目标，并引入了改进的大规模邻域搜索算法进行最优配送路径的选择，从而制定出合理的配送路径方案，减少了人工制订方案的工作强度。

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

一种车辆配送路径规划方法，所述方法包括：

获取配送中心节点位置信息、客户信息和车辆信息；所述客户信息包括：客户数量、各客户货物需求量以及各客户节点的位置；所述车辆信息包括：车辆个数和车辆最大载重信息；

根据所述配送中心节点位置信息、客户信息以及车辆最大载重信息建立以总配送车辆里程最短为目标的目标函数；所述目标函数的约束条件为每个客户由且仅由一辆车服务且每辆车所服务的客户需求总量不超过车辆载重；

确定初始编码序列；所述初始编码序列为初始配送路径的编码化表示，所述初始编码序列包括所述初始配送路径上的各客户节点及所述各客户节点的配送顺序；

根据所述目标函数计算所述初始编码序列的目标值；

根据所述初始编码序列的目标值计算Metropolis准则的初始温度，并开始最优配送路径迭代；

所述最优配送路径迭代，具体包括：

根据各移除算子和各插入算子的权重，利用轮盘赌的方法选取一个移除算子和一个插入算子，并根据选取出的移除算子和插入算子，分别对当前解进行算子移除操作和算子插入操作，得到局部解；所述移除算子包括：随机客户节点移除、随机子路径移除、相似客户节点移除和环区相似度移除；所述插入算子包括：成本贪婪插入和后悔值插入；第一次迭代过程中的当前解为所述初始编码序列；

若局部解的目标值小于当前解的目标值，则以所述局部解为当前解；若局部解的目标值大于当前解的目标值，则根据Metropolis准则，结合此次迭代的温度值，概率接受局部解，并更新温度值；第一次迭代过程中的温度值为初始温度值；

根据各插入算子和各移除算子的使用次数和预设评分，更新对应的算子权重，更新间隔为预设迭代次数；

直至局部解的目标值不小于当前解的迭代次数达到预设次数时，停止迭代，输出车辆最优编码序列。

在一些实施例中，所述以总配送车辆里程最短为目标的目标函数为：

其中，F表示目标函数；m为配送能够使用的最大车辆数；n为客户数量；d_ij表示任意两节点i和j之间的距离；x_ijk为0-1规划，表示车辆k是否经过节点i和j，0表示车辆k不经过节点i和j，1表示车辆k经过节点i和j。

在一些实施例中，所述确定初始编码序列，具体包括：

以配送中心节点位置为极点，以所述配送中心节点和距离所述配送中心节点最近的客户节点所在的射线为极轴建立极坐标系，并将所述配送中心节点和客户节点的位置坐标转换为极坐标；

将客户节点按照极角大小的顺序进行排序；

在满足约束条件的前提下，根据目标函数依次将各客户节点插入到解决方案中；所述解决方案包括若干条配送路径；在插入过程中，若遇到不满足约束条件的客户节点，并且所述不满足约束条件的客户节点不是最后一个客户节点，则跳过所述不满足约束条件的客户节点；

搜索是否具有未插入的客户节点j，若有，则依次计算所述客户节点j插入到每条配送路径中的每两个客户节点之间的插入成本c_ij，并插入成本最低所对应的两个客户节点之间；其中，c_ij＝d_i,j+d_j,i+1-d_i,i+1；式中，d_i,j表示客户节点i到客户节点j之间的距离，d_j,i+1表示客户节点j到客户节点i+1之间的距离，d_i,i+1表示客户节点i到客户节点i+1之间的距离；

遍历所有未插入的客户节点，直至所有的客户节点均插入所述解决方案中，得到初始编码序列。

在一些实施例中，所述根据所述初始编码序列中的目标值计算Metropolis准则的初始温度，具体包括：

根据所述初始编码序列中的目标值计算Metropolis准则的初始温度T₀；

所述初始温度T₀表示在劣解接受概率为η的情况下，要接受比当前目标值f(x)差β％的劣解，所对应的温度为T₀。

在一些实施例中，

所述随机客户节点移除具体包括：在当前解中若存在不可行子路径解，则随机移除不可行子路径中的客户节点，直至客户需求量之和不超过车辆最大载重；若移除的客户节点数量不超过移除上限，则选取随机客户节点进行移除，直至移除客户节点的数量达到移除上限；不可行子路径解即子路径的客户需求量之和大于车辆最大载重；所述移除上限由随机函数生成；

所述随机子路径移除具体包括：在当前解中若存在不可行子路径解，则移除不可行子路径；若移除的客户节点数量不超过移除上限，则选取随机子路径进行移除，直至移除客户节点的数量达到移除上限；

所述相似客户节点移除具体包括：随机选取当前解中的一个客户节点i，计算所述客户节点i与其他客户节点j的相似度，依次移除相似度最大的客户节点，直至移除客户节点的数量达到移除上限；

所述环区相似度移除具体包括：基于当前解中各子路径所在环形区域间的三种空间关系，计算相似度；

两子路径间的相似度为：

其中，σ₁>σ₂>σ₃，s_i和s_j表示当前解中两条子路径r_i和r_j对应的环形区域，则单一子路径r_i的相似度系数为：

在

中选出相似度系数最大的子路径r_m镠x，通过轮盘赌的方法选出非最大相似度系数的子路径r_d，之后移除r_m镠x和r_d中的所有客户节点，

表示所有子路径的相似度系数集合，l表示当前解中子路径总数；

所述成本贪婪插入具体包括：将每个移除的客户节点插入到当前解的子路径中，每次插入均选择插入成本最小且满足载重限制的子路径；

所述后悔值插入具体包括：将每个移除的客户节点插入到当前解的子路径中，每次插入时选择后悔值最大的子路径插入；所述后悔值为：Δc＝c_m2-c_m1，其中c_m1表示最小插入成本，c_m2表示次小插入成本。

在一些实施例中，所述算子权重的更新公式为：

其中，τ表示间隔τ次迭代，y表示第y个迭代间隔，q表示第q个算子，

表示算子q在τ次迭代内的使用次数，对应的预设评分为

在第y个迭代间隔内，第q个算子对应的算子权重为

在第y+1个迭代间隔内，第q个算子对应的算子权重为

μ∈[0,1]是控制算子影响的因子，该值越小，则第y个迭代间隔的权重对第y+1个迭代间隔的权重更新影响越大；若μ＝0，则权重完全取决于上一迭代间隔的权重；若μ＝1，则只考虑迭代间隔内评分，若0<μ<1，则同时考虑迭代间隔内的得分与之前的权重值。

在一些实施例中，在所述确定初始编码序列之前，还包括：

对所述配送中心节点和各所述客户节点进行染色体编码。

在一些实施例中，所述温度值的更新公式为：T′＝T*α

其中T′表示更新后的温度，T表示更新前的当前温度，α∈(0,1)为降温速度，α的值为人为预设的常参数。

在一些实施例中，所述根据Metropolis准则，结合此次迭代的温度值，概率接受局部解，具体包括：

根据Metropolis准则，结合此次迭代的温度值，概率接受局部解，接受概率为

其中，P_Δ的值与[0,1]间的随机数r，若P_Δ≥r，则接受劣解作为下一次迭代的当前解，T表示当前温度，f(x)表示当前解x的目标值，f(x′)表示局部解x′的目标值。

本发明还提供了一种车辆配送路径规划系统，所述系统包括：

信息获取模块，用于获取配送中心节点位置信息、客户信息和车辆信息；所述客户信息包括：客户数量、各客户货物需求量以及各客户节点的位置；所述车辆信息包括：车辆个数和车辆最大载重信息；

目标函数确定模块，用于根据所述配送中心节点位置信息、客户信息以及车辆最大载重信息建立以总配送车辆里程最短为目标的目标函数；所述目标函数的约束条件为每个客户由且仅由一辆车服务且每辆车所服务的客户需求总量不超过车辆载重；

初始解构建模块，用于确定初始编码序列；所述初始编码序列为初始配送路径的编码化表示，所述初始编码序列包括所述初始配送路径上的各客户节点及所述各客户节点的配送顺序；

初始解目标值计算模块，用于根据所述目标函数计算所述初始编码序列的目标值；

最优配送路径迭代模块，用于根据所述初始编码序列的目标值计算Metropolis准则的初始温度，并开始最优配送路径迭代；

所述最优配送路径迭代，具体包括：

根据各移除算子和各插入算子的权重，利用轮盘赌的方法选取一个移除算子和一个插入算子，并根据选取出的移除算子和插入算子，分别对当前解进行算子移除操作和算子插入操作，得到局部解；所述移除算子包括：随机客户节点移除、随机子路径移除、相似客户节点移除和环区相似度移除；所述插入算子包括：成本贪婪插入和后悔值插入；第一次迭代过程中的当前解为所述初始编码序列；

若局部解的目标值小于当前解的目标值，则以所述局部解为当前解；若局部解的目标值大于当前解的目标值，则根据Metropolis准则，结合此次迭代的温度值，概率接受局部解，并更新温度值；第一次迭代过程中的温度值为初始温度值；

根据各插入算子和各移除算子的使用次数和预设评分，更新对应的算子权重，更新间隔为预设迭代次数；

直至局部解的目标值不小于当前解的迭代次数达到预设次数时，停止迭代，输出车辆最优编码序列。

根据本发明提供的具体实施例，本发明公开了以下技术效果：

本发明提供了一种车辆配送路径规划方法及系统，首先，获取获取配送中心节点位置信息、客户信息和车辆信息，并据此以总配送车辆里程最短为目标建立目标函数；然后通过扫描算法求得一个初始解，以目标函数确定初始编码序列的目标值，利用改进的大规模邻域搜索算法结合Metropolis准则选择最优的车辆配送路径。本发明利用改进的大规模邻域搜索算法能够筛选出车辆最优的配送路径，从而制定出更合理的配送路径方案，提高了配送效率，同时也大大降低了车辆总配送里程，减少了人工制订方案的工作强度。

附图说明

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

图1为本发明实施例一提供的车辆配送路径规划方法流程图。

图2为本发明实施例一提供的配送中心和各节点位置示意图。

图3为本发明实施例一提供的两条子路径对应环形区域的空间关系示意图。

图4为本发明实施例一提供的4辆车完成全部配送任务的过程以及各车辆所需要服务的客户节点示意图。

图5为本发明实施例二提供的车辆配送路径规划系统的框图。

具体实施方式

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

本发明的目的是提供一种车辆配送路径规划方法及系统，选择车辆最大载重量这一配送限制，以带容量约束的车辆路径问题作为车辆配送的模型，以配送方案中各车辆配送里程最短为目标，并引入了改进的大规模邻域搜索算法进行最优配送路径的选择，从而制定出合理的配送路径方案，减少了人工制订方案的工作强度。首先，获取确定车辆路径的基本信息；所述基本信息包括配送中心节点和各客户节点的地理位置、客户数量、客户货物需求量以及车辆的最大载重；然后建立以车辆配送路径里程最短为目标的目标函数；再通过扫描算法确定模型的初始解；最后以所述目标函数为目标值，利用改进的大规模邻域搜索算法确定最优的车辆配送路径。

为使本发明的上述目的、特征和优点能够更加明显易懂，下面结合附图和具体实施方式对本发明作进一步详细的说明。

实施例一：

如图1所示，本实施例提供了一种车辆配送路径规划方法，所述方法包括：

S1、获取配送中心节点位置信息、客户信息和车辆信息；所述客户信息包括：客户数量、各客户货物需求量以及各客户节点的位置；所述车辆信息包括：车辆个数和车辆最大载重信息。配送中心与各客户节点的位置如图2所示。

S2、根据所述配送中心节点位置信息、客户信息以及车辆最大载重信息建立以总配送车辆里程最短为目标的目标函数；所述目标函数的约束条件为每个客户由且仅由一辆车服务且每辆车所服务的客户需求总量不超过车辆载重。

所述以总配送车辆里程最短为目标的目标函数为：

其中，F表示目标函数；m为配送能够使用的最大车辆数；n为客户数量；d_ij表示任意两节点i和j之间的距离；x_ijk为0-1规划，表示车辆k是否经过节点i和j，1表示车辆k经过节点i和j，0表示车辆k不经过节点i和j，0表示节点i和节点j点间不连通，即车辆k不经过节点i和节点j之间的路径，也就不经过该路段的两个端点，即节点i和节点j。

考虑到车辆与客户之间配送的分配，以及配送车辆自身的载重量均会影响到车辆配送路径的选择，所以为了得到更优的配送路径，需要对目标函数设置一定的约束条件。即目标函数的约束条件为每个客户由且仅由一辆车服务且每辆车所服务的客户需求总量不超过车辆载重。

然后，对所述配送中心节点和各所述客户节点进行染色体编码，为了便于对配送中心和客户节点做区分，用0表示配送中心，即配送车辆出发处，用自然数来表示各客户节点。

S3、确定初始编码序列；所述初始编码序列为初始配送路径的编码化表示，所述初始编码序列包括所述初始配送路径上的各客户节点及所述各客户节点的配送顺序。配送顺序即配送的子路径和顺序。举例说明，初始编码序列内包含配送中心(此处用0表示)，以及有序客户点(用1，2，3等自然数表示)。例如对于有一个配送中心，6个配送点的车辆路径问题，其一个初始编码序列可以表示为{0，3，4，2，0，5，1，6，0}，{}内为一个解的编码，表示车辆从配送中心(0)出发，依次经过客户点3，4，2后返回配送中心，再从配送中心(0)出发依次经过客户5，1，6后返回配送中心。对于配送中心0，客户点1，2，3，4，5，6，经过步骤S3，即可形成{0，3，4，2，0，5，1，6，0}。

确定初始编码序列的步骤，具体包括：

S31、以配送中心节点位置为极点，以所述配送中心节点和距离所述配送中心节点最近的客户节点所在的射线为极轴建立极坐标系，并将所述配送中心节点和客户节点的位置坐标转换为极坐标。

S32、将客户节点按照极角大小的顺序进行排序。排序规则为从小到大或者从大到小。

S33、在满足约束条件的前提下，根据目标函数依次将各客户节点插入到解决方案中；所述解决方案包括若干条配送路径。即解决完一个客户节点的配送，便把该解决的客户节点及路径放入解决方案中。

在插入过程中，若遇到不满足约束条件的客户节点，并且所述不满足约束条件的客户节点不是最后一个客户节点，则跳过所述不满足约束条件的客户节点。

S34、搜索是否具有未插入的客户节点j，若有，则依次计算所述客户节点j插入到每条配送路径中的每两个客户节点之间的插入成本c_ij，并插入成本最低所对应的两个客户节点之间；其中，c_ij＝d_i,j+d_j,i+1-d_i,i+1；式中，d_i,j表示客户节点i到客户节点j之间的距离，d_j,i+1表示客户节点j到客户节点i+1之间的距离，d_i,i+1表示客户节点i到客户节点i+1之间的距离。

例如，{0，3，4，2，0，5，1，6，0}，开始时这个解只是{0}，然后考虑1，2，3，4，5，6这几个点的插入成本，基于插入成本的比较确定哪个点放到0后，如将3插入，变为{0，3}，以此类推，直至{0，3，4，2，}，再插入5时发现点3、4、2、5的客户需求之和超过载重了，所以5不能插入，因此先插入0，变成{0，3，4，2，0}，再插入5，形成{0，3，4，2，0，5}，直至所有点插入完成，形成{0，3，4，2，0，5，1，6，0}。

S35、遍历所有未插入的客户节点，直至所有的客户节点均插入所述解决方案中，得到初始编码序列。

S4、根据所述目标函数计算所述初始编码序列的目标值。

目标值指的是总车辆路径长度。以解{0，3，4，2，0，5，1，6，0}为例，其目标值f(x)＝d₀₃+d₃₄+d₄₂+d₂₀+d₀₅+d₅₁+d₁₆+d₆₀，其中d_ij为点i与点j之间的距离。此处的目标值也可以理解为遗传算法中一个染色体的适应度，其本质是为了评价一个解的好坏。

S5、根据所述初始编码序列的目标值计算Metropolis准则的初始温度，并开始最优配送路径迭代，迭代结束后输出车辆最优编码序列。

Metropolis准则的初始温度T₀的计算公式为：

所述初始温度T₀表示在劣解接受概率为η的情况下，要接受比当前目标值f(x)差β％的劣解，所对应的温度为T₀，其中η和β一般是人为规定，无固定范围，本实施例中令η＝50和β＝20。

所述最优配送路径迭代，具体包括：

A1、根据各移除算子和各插入算子的权重，利用轮盘赌的方法选取一个移除算子和一个插入算子，并根据选取出的移除算子和插入算子，分别对当前解进行算子移除操作和算子插入操作，得到局部解；所述移除算子包括：随机客户节点移除、随机子路径移除、相似客户节点移除和环区相似度移除；所述插入算子包括：成本贪婪插入和后悔值插入；第一次迭代过程中当前解为所述初始编码序列。开始时：每个算子(本实施例中的4种移除算子和2种插入算子)权重在算法开始值均为1，此权重初始时为人为预定。

步骤S3已经构建车辆路径问题的一个初始解，这个初始解实际上已经可以作为该问题的最终答案，但初始解的质量一般较差，因此后面的步骤主要是对初始解的优化，这个优化过程属于自适应大规模邻域搜索算法(简称ALNS)的主体。ALNS算法本身不包括对初始解产生方法的描述，因此需要通过其他方法构建初始解，此处选择的是扫描算法，方法也可以是节约算法、邻近插入算法等。ALNS算法的优化思想可以理解为对解不断进行破坏再重组，在这个过程中解会向更优的方向变换。

就像在模拟退火算法中会在每次迭代中计算当前温度一样，移除和插入是ALNS算法的固有操作和核心特点。ALNS算法的优化过程可以简单描述为：完整解(形如初始解，包含完整的路径信息)→执行移除算子(将完整解中的一些点或者一些子路径移除，移除后的解可以称为非完整解)→执行插入算子(将上面移除的点按移除算子描述的过程重新插入到非完整解中，再次形成完整解)→完整解，如此形成了闭环，不断迭代优化。其中的一次移除算子和插入算子形成一次迭代，每次迭代仅选择一种移除算子和插入算子。

移除算子的选取(多个移除算子中选出一个)和插入算子的选取(多个插入算子中选出一个)所用方法均为轮盘赌，二者的选取互不干扰。

轮盘赌选择法是算法中常见的一种通用方法，常见于遗传算法中染色体的选择，此处算子的选取与之相似。

以在h个移除算子中选出1个移除算子为例，设h个移除算子对应权重分别为w₁，w₂，…，w_h，则第u个算子对应个体概率

其中，w_u与该公式等号前的P_u对应，指的是第u个算子的权重(此处是为了说明个体概率的计算方式，因而以第u个算子为例)，w_g与公式中的

对应，指w_g中g从1开始至h为止的w_g之和，其中的g作用域仅在求和符号之内，指代求和范围符号，而其中h是该段落中的h，即移除算子的总数。算子的累计概率为

其中，P_g为个体概率，

为累计概率；个体概率与累计概率均为轮盘赌这一通用方法中的原有值。与上一个问题中的g同理，Pg在公式

中，P为个体概率，g为其下标，表示求和符号中的序列符号，即Pg为第g个算子的个体概率(由前面的个体概率公式求出)，其理论含义为第g个算子在所有算子(从第1至第h个算子)中，被选取的概率。

表示前n个算子的个体概率之和，如

表示算子1与算子2的概率和。生成一个随机数r∈[0,1]，从n＝1开始，依次比较r与

当第一次出现

时，选择过程结束，第u个算子即为选出的算子。

对当前解先执行移除算子，后执行插入算子。移除算子用于将一些客户点从当前解中移除，直至移除的客户点达到预定的移除上限，从而得到非完整解；插入算子则用于将移除出的客户点按照插入算子所描述的规则重新插入到非完整解中，从而得到新的局部解，以达到搜索出更优解的目的。

所述随机客户节点移除具体包括：在当前解中若存在不可行子路径解，则随机移除不可行子路径中的客户节点，直至客户需求量之和不超过车辆最大载重；若移除的客户节点数量不超过移除上限，则选取随机客户节点进行移除，直至移除客户节点的数量达到移除上限；不可行子路径解即子路径的客户需求量之和大于车辆最大载重；所述移除上限由随机函数生成。移除上限一般是客户节点数量的20％～30％之间的随机数。该随机数一般由程序中的随机函数生成。

所述随机子路径移除具体包括：在当前解中若存在不可行子路径解，则移除不可行子路径；若移除的客户节点数量不超过移除上限，则选取随机子路径进行移除，直至移除客户节点的数量达到移除上限；

所述相似客户节点移除具体包括：随机选取当前解中的一个客户节点i(若当前解中存在不可行子路径解，则优先在不可行子路径解中选取)，计算所述客户节点i与其他客户节点j的相似度，依次移除相似度最大的客户节点，直至移除客户节点的数量达到移除上限。两客户点i和j间距离d_ij作为相似点的移除依据，d_ij值越小则客户点i和j的相似度越高。

所述环区相似度移除具体包括：考虑当前解中子路径间的空间关系，基于各子路径所在环形区域间的三种空间关系，计算其相似度。三种空间关系分别为重叠、相交、相离，如图3所示为解中两条子路径对应环形区域s₁和S₂的空间关系示意图。其中每个环形区域为以配送中心为圆心能够覆盖完整子路径的最小环形，阴影区域为两子路径对应环区重叠的部分。

基于图3中的三种空间关系，计算相似度；

两子路径间的相似度为：

其中，σ₁>σ₂>σ₃(在算法执行过程中其值为固定常数，是人为预定的固定值。其值的选取仅需遵循该不等式，主要表示一种相互关系，无固定范围标准，本实施例中可以使σ₁＝20，σ₂＝5，σ₃＝1)，s_i和s_j表示当前解中两条子路径r_i和r_j对应的环形区域，则单一子路径r_i的相似度系数为：

采用精英策略移除子路径，在

中选出相似度系数最大的子路径r_m镠x，通过轮盘赌的方法选出非最大相似度系数的子路径r_d，之后移除r_m镠x和r_d中的所有客户节点，

表示所有子路径的相似度系数集合，l表示当前解中子路径总数。

所述成本贪婪插入具体包括：将每个移除的客户节点插入到当前解的子路径中的最佳位置。将待插入客户节点i插入到子路径中客户节点j后，则其插入成本c_ij＝d_i,j+d_j,i+1-d_i,i+1，每次插入均选择插入成本最小且满足载重限制的子路径。若经过上述步骤后存在未插入点，则只考虑插入成本进行插入，直至无剩余点。

所述后悔值插入具体包括：将每个移除的客户节点插入到当前解的子路径中，每次插入时选择后悔值最大的子路径插入；所述后悔值为：Δc＝c_m2-c_m1，其中c_m1表示最小插入成本，c_m2表示次小插入成本。其意义在于后悔值Δc越大，则该客户节点若不能插入最佳位置，选择次优位置插入造成的插入成本涨幅越大。

A2、若局部解的目标值小于当前解的目标值，则以所述局部解为当前解；若局部解的目标值大于当前解的目标值，则根据Metropolis准则，结合此次迭代的温度值，概率接受局部解，并更新温度值；第一次迭代过程中的温度值为初始温度值。

概率接受局部解的接受概率为

其中，P_Δ的值与[0,1]间的随机数r，若P_Δ≥r，则接受劣解作为下一次迭代的当前解，T表示当前温度，f(x)表示当前解x的目标值，f(x′)表示局部解x′的目标值。随机数r由程序随机函数生成。

温度值的更新公式为：T′＝T*α

其中T′表示更新后的温度，T表示更新前的当前温度，α∈(0,1)为降温速度，α的值为人为预设的常参数，取值一般接近于1(如0.95，0.99，0.999等，此处可令其为0.99)，越接近于1表示温度下降的越慢。

A3、根据各插入算子和各移除算子的使用次数和预设评分，更新对应的算子权重，更新间隔为预设迭代次数。预设迭代次数一般是人为规定，没有硬性要求，本实施例中定为20，表示每迭代20次，基于各个算子在这20次迭代的表现调整各算子的权重。调整后的权重用于下一个20次迭代算子的选择依据。

算子权重的更新公式为：

其中，τ表示间隔τ次迭代，y表示第y个迭代间隔，q表示第q个算子，

表示算子q在τ次迭代内的使用次数，对应的预设评分为

在第y个迭代间隔内，第q个算子对应的算子权重为

在第y+1个迭代间隔内，第q个算子对应的算子权重为

μ∈[0,1]是控制算子影响的因子，该值越小，则第y个迭代间隔的权重对第y+1个迭代间隔的权重更新影响越大；若μ＝0，则权重完全取决于上一迭代间隔的权重；若μ＝1，则只考虑迭代间隔内评分，若0<μ<1，则同时考虑迭代间隔内的得分与之前的权重值，μ的值是人为预设的。

算子的预设评分的规则为：若找到新的全局最优解，则算子分数增加θ₁；若新解仅优于当前解，劣于全局最优解，则算子分数增加θ₂；若新解劣于当前解，但被Metropolis准则接受作为下一迭代初始解，则算子分数增加θ₃；若新解劣于当前解，且未被Metropolis准则接受，则算子分数增加θ₄。一般θ₁>θ₂>θ₃>θ₄，且为人为预设，无固定标准，本实施例中θ₁＝5，θ₂＝3，θ₃＝1.5，θ₄＝1.8。

A4、直至局部解的目标值不小于当前解的迭代次数达到预设次数时，停止迭代，输出车辆最优编码序列。将车辆最优编码序列解码即为车辆最优配送路径。

上述的预设次数可以选择2000代，也可以根据需求对无改进解迭代次数进行调整。另外，选出所记录的最优解进行解码，即可得到完成全部配送任务所需的车辆以及各车辆所服务的客户。如图4所示，图4中给出了4辆车完成全部配送任务的过程以及各车辆所需要服务的客户节点。

本实施例提供了一种车辆配送路径规划方法，包括：获取车辆路径的基本信息；所述基本信息包括配送中心节点和各客户节点的地理位置、客户数量、客户货物需求量以及车辆的最大载重；基于配送模型建立目标函数；通过扫描算法求得模型的一个初始解；以所述目标函数为目标值，利用改进大规模邻域搜索算法选择最优的车辆配送路径。利用改进的大规模邻域搜索算法能够筛选出车辆最优的配送路径，从而制定出更合理的配送路径方案，提高了配送效率，同时也大大降低了车辆总配送里程。本实施例中的改进大规模邻域搜索算法考虑了配送方案中的单次配送的地理位置相关性，提高了算法的局部搜索能力，对于大规模的车辆配送方案的制订有更好的适用性，能够为一般带容量约束的车辆配送路径问题提供解决方案，为管理者决策提供了参考。

实施例二：

如图5所示，本实施例提供了一种车辆配送路径规划系统，所述系统包括：

信息获取模块M1，用于获取配送中心节点位置信息、客户信息和车辆信息；所述客户信息包括：客户数量、各客户货物需求量以及各客户节点的位置；所述车辆信息包括：车辆个数和车辆最大载重信息；

目标函数确定模块M2，用于根据所述配送中心节点位置信息、客户信息以及车辆最大载重信息建立以总配送车辆里程最短为目标的目标函数；所述目标函数的约束条件为每个客户由且仅由一辆车服务且每辆车所服务的客户需求总量不超过车辆载重；

初始解构建模块M3，用于确定初始编码序列；所述初始编码序列为初始配送路径的编码化表示，所述初始编码序列包括所述初始配送路径上的各客户节点及所述各客户节点的配送顺序；

初始解目标值计算模块M4，用于根据所述目标函数计算所述初始编码序列的目标值；

最优配送路径迭代模块M5，用于根据所述初始编码序列的目标值计算Metropolis准则的初始温度，并开始最优配送路径迭代；

所述最优配送路径迭代，具体包括：

根据各移除算子和各插入算子的权重，利用轮盘赌的方法选取一个移除算子和一个插入算子，并根据选取出的移除算子和插入算子，分别对当前解进行算子移除操作和算子插入操作，得到局部解；所述移除算子包括：随机客户节点移除、随机子路径移除、相似客户节点移除和环区相似度移除；所述插入算子包括：成本贪婪插入和后悔值插入；第一次迭代过程中当前解为所述初始编码序列；

若局部解的目标值小于当前解的目标值，则以所述局部解为当前解；若局部解的目标值大于当前解的目标值，则根据Metropolis准则，结合此次迭代的温度值，概率接受局部解，并更新温度值；第一次迭代过程中的温度值为初始温度值；

根据各插入算子和各移除算子的使用次数和预设评分，更新对应的算子权重，更新间隔为预设迭代次数；

直至局部解的目标值不小于当前解的迭代次数达到预设次数时，停止迭代，输出车辆最优编码序列。

本说明书中各个实施例采用递进的方式描述，每个实施例重点说明的都是与其他实施例的不同之处，各个实施例之间相同相似部分互相参见即可。对于实施例公开的系统而言，由于其与实施例公开的方法相对应，所以描述的比较简单，相关之处参见方法部分说明即可。

本文中应用了具体个例对本发明的原理及实施方式进行了阐述，以上实施例的说明只是用于帮助理解本发明的方法及其核心思想；同时，对于本领域的一般技术人员，依据本发明的思想，在具体实施方式及应用范围上均会有改变之处。综上所述，本说明书内容不应理解为对本发明的限制。

Claims (10)

1.一种车辆配送路径规划方法，其特征在于，所述方法包括：

获取配送中心节点位置信息、客户信息和车辆信息；所述客户信息包括：客户数量、各客户货物需求量以及各客户节点的位置；所述车辆信息包括：车辆个数和车辆最大载重信息；

根据所述配送中心节点位置信息、客户信息以及车辆最大载重信息建立以总配送车辆里程最短为目标的目标函数；所述目标函数的约束条件为每个客户由且仅由一辆车服务且每辆车所服务的客户需求总量不超过车辆载重；

确定初始编码序列；所述初始编码序列为初始配送路径的编码化表示，所述初始编码序列包括所述初始配送路径上的各客户节点及所述各客户节点的配送顺序；

根据所述目标函数计算所述初始编码序列的目标值；

根据所述初始编码序列的目标值计算Metropolis准则的初始温度，并开始最优配送路径迭代；

所述最优配送路径迭代，具体包括：

根据各移除算子和各插入算子的权重，利用轮盘赌的方法选取一个移除算子和一个插入算子，并根据选取出的移除算子和插入算子，分别对当前解进行算子移除操作和算子插入操作，得到局部解；所述移除算子包括：随机客户节点移除、随机子路径移除、相似客户节点移除和环区相似度移除；所述插入算子包括：成本贪婪插入和后悔值插入；第一次迭代过程中的当前解为所述初始编码序列；

若局部解的目标值小于当前解的目标值，则以所述局部解为当前解；若局部解的目标值大于当前解的目标值，则根据Metropolis准则，结合此次迭代的温度值，概率接受局部解，并更新温度值；第一次迭代过程中的温度值为初始温度值；

根据各插入算子和各移除算子的使用次数和预设评分，更新对应的算子权重，更新间隔为预设迭代次数；

直至局部解的目标值不小于当前解的迭代次数达到预设次数时，停止迭代，输出车辆最优编码序列。

2.根据权利要求1所述的车辆配送路径规划方法，其特征在于，所述以总配送车辆里程最短为目标的目标函数为：

其中，F表示目标函数；m为配送能够使用的最大车辆数；n为客户数量；d_ij表示任意两节点i和j之间的距离；x_ijk为0-1规划，表示车辆k是否经过节点i和j，0表示车辆k不经过节点i和j，1表示车辆k经过节点i和j。

3.根据权利要求1所述的车辆配送路径规划方法，其特征在于，所述确定初始编码序列，具体包括：

以配送中心节点位置为极点，以所述配送中心节点和距离所述配送中心节点最近的客户节点所在的射线为极轴建立极坐标系，并将所述配送中心节点和客户节点的位置坐标转换为极坐标；

将客户节点按照极角大小的顺序进行排序；

在满足约束条件的前提下，根据目标函数依次将各客户节点插入到解决方案中；所述解决方案包括若干条配送路径；在插入过程中，若遇到不满足约束条件的客户节点，并且所述不满足约束条件的客户节点不是最后一个客户节点，则跳过所述不满足约束条件的客户节点；

搜索是否具有未插入的客户节点j，若有，则依次计算所述客户节点j插入到每条配送路径中的每两个客户节点之间的插入成本c_ij，并插入成本最低所对应的两个客户节点之间；其中，c_ij＝d_i,j+d_j,i+1-d_i,i+1；式中，d_i,j表示客户节点i到客户节点j之间的距离，d_j,i+1表示客户节点j到客户节点i+1之间的距离，d_i,i+1表示客户节点i到客户节点i+1之间的距离；

遍历所有未插入的客户节点，直至所有的客户节点均插入所述解决方案中，得到初始编码序列。

4.根据权利要求1所述的车辆配送路径规划方法，其特征在于，所述根据所述初始编码序列中的目标值计算Metropolis准则的初始温度，具体包括：

根据所述初始编码序列中的目标值计算Metropolis准则的初始温度T₀；

所述初始温度T₀表示在劣解接受概率为η的情况下，要接受比当前目标值f(x)差β％的劣解，所对应的温度为T₀。

5.根据权利要求1所述的车辆配送路径规划方法，其特征在于，

所述随机客户节点移除具体包括：在当前解中若存在不可行子路径解，则随机移除不可行子路径中的客户节点，直至客户需求量之和不超过车辆最大载重；若移除的客户节点数量不超过移除上限，则选取随机客户节点进行移除，直至移除客户节点的数量达到移除上限；不可行子路径解即子路径的客户需求量之和大于车辆最大载重；所述移除上限由随机函数生成；

所述随机子路径移除具体包括：在当前解中若存在不可行子路径解，则移除不可行子路径；若移除的客户节点数量不超过移除上限，则选取随机子路径进行移除，直至移除客户节点的数量达到移除上限；

所述相似客户节点移除具体包括：随机选取当前解中的一个客户节点i，计算所述客户节点i与其他客户节点j的相似度，依次移除相似度最大的客户节点，直至移除客户节点的数量达到移除上限；

所述环区相似度移除具体包括：基于当前解中各子路径所在环形区域间的三种空间关系，计算相似度；

两子路径间的相似度为：

其中，σ₁>σ₂>σ₃，s_i和s_j表示当前解中两条子路径r_i和r_j对应的环形区域，则单一子路径r_i的相似度系数为：

在

中选出相似度系数最大的子路径r_max，通过轮盘赌的方法选出非最大相似度系数的子路径r_d，之后移除r_m镠x和r_d中的所有客户节点，

表示所有子路径的相似度系数集合，l表示当前解中子路径总数；

所述成本贪婪插入具体包括：将每个移除的客户节点插入到当前解的子路径中，每次插入均选择插入成本最小且满足载重限制的子路径；

所述后悔值插入具体包括：将每个移除的客户节点插入到当前解的子路径中，每次插入时选择后悔值最大的子路径插入；所述后悔值为：Δc＝c_m2-c_m1，其中c_m1表示最小插入成本，c_m2表示次小插入成本。

6.根据权利要求1所述的车辆配送路径规划方法，其特征在于，所述算子权重的更新公式为：

其中，τ表示间隔τ次迭代，y表示第y个迭代间隔，q表示第q个算子，

表示算子q在τ次迭代内的使用次数，对应的预设评分为

在第y个迭代间隔内，第q个算子对应的算子权重为

在第y+1个迭代间隔内，第q个算子对应的算子权重为

μ∈[0,1]是控制算子影响的因子，该值越小，则第y个迭代间隔的权重对第y+1个迭代间隔的权重更新影响越大；若μ＝0，则权重完全取决于上一迭代间隔的权重；若μ＝1，则只考虑迭代间隔内评分，若0<μ<1，则同时考虑迭代间隔内的得分与之前的权重值。

7.根据权利要求1所述的车辆配送路径规划方法，其特征在于，在所述确定初始编码序列之前，还包括：

对所述配送中心节点和各所述客户节点进行染色体编码。

8.根据权利要求1所述的车辆配送路径规划方法，其特征在于，所述温度值的更新公式为：T′＝T*α

其中T′表示更新后的温度，T表示更新前的当前温度，α∈(0,1)为降温速度，α的值为人为预设的常参数。

9.根据权利要求1所述的车辆配送路径规划方法，其特征在于，所述根据Metropolis准则，结合此次迭代的温度值，概率接受局部解，具体包括：

根据Metropolis准则，结合此次迭代的温度值，概率接受局部解，接受概率为

其中，P_Δ的值与[0,1]间的随机数r，若P_Δ≥r，则接受劣解作为下一次迭代的当前解，T表示当前温度，f(x)表示当前解x的目标值，f(x′)表示局部解x′的目标值。

10.一种车辆配送路径规划系统，其特征在于，所述系统包括：

信息获取模块，用于获取配送中心节点位置信息、客户信息和车辆信息；所述客户信息包括：客户数量、各客户货物需求量以及各客户节点的位置；所述车辆信息包括：车辆个数和车辆最大载重信息；

目标函数确定模块，用于根据所述配送中心节点位置信息、客户信息以及车辆最大载重信息建立以总配送车辆里程最短为目标的目标函数；所述目标函数的约束条件为每个客户由且仅由一辆车服务且每辆车所服务的客户需求总量不超过车辆载重；

初始解构建模块，用于确定初始编码序列；所述初始编码序列为初始配送路径的编码化表示，所述初始编码序列包括所述初始配送路径上的各客户节点及所述各客户节点的配送顺序；

初始解目标值计算模块，用于根据所述目标函数计算所述初始编码序列的目标值；

最优配送路径迭代模块，用于根据所述初始编码序列的目标值计算Metropolis准则的初始温度，并开始最优配送路径迭代；

所述最优配送路径迭代，具体包括：

根据各移除算子和各插入算子的权重，利用轮盘赌的方法选取一个移除算子和一个插入算子，并根据选取出的移除算子和插入算子，分别对当前解进行算子移除操作和算子插入操作，得到局部解；所述移除算子包括：随机客户节点移除、随机子路径移除、相似客户节点移除和环区相似度移除；所述插入算子包括：成本贪婪插入和后悔值插入；第一次迭代过程中的当前解为所述初始编码序列；

若局部解的目标值小于当前解的目标值，则以所述局部解为当前解；若局部解的目标值大于当前解的目标值，则根据Metropolis准则，结合此次迭代的温度值，概率接受局部解，并更新温度值；第一次迭代过程中的温度值为初始温度值；

根据各插入算子和各移除算子的使用次数和预设评分，更新对应的算子权重，更新间隔为预设迭代次数；

直至局部解的目标值不小于当前解的迭代次数达到预设次数时，停止迭代，输出车辆最优编码序列。

Images