一种基于启发式分支定价算法的带时间窗车辆路径规划方法

1.本发明涉及车辆路径规划领域，尤其涉及一种基于启发式分支定价算法的带时间窗车辆路径规划方法。


背景技术：

2.车辆路径问题是路径规划与运筹优化领域研究较为广泛的组合优化问题之一。车辆路径问题是由旅行商问题发展而来，在1959年由dantzig和ramser提出，属于np-难问题。随着物流行业的快速发展，车辆路径问题受到越来越多的重视，同时客户对于配送过程也提出了越来越多的要求，其中包括时间窗要求，客户点的时间窗要求分为硬时间窗和软时间窗，硬时间窗要求配送车辆在客户要求的时间窗内进行配送，如果车辆早于时间窗到达客户点需要进行等待，如果车辆晚于时间窗到达客户点则需要提供其他车辆服务该客户；软时间窗则是对未在客户点时间窗内到达的车辆进行时间成本惩罚。因此对于带有时间窗要求的车辆路径问题如何设计有效的求解算法具有重要的实际意义。
3.车辆路径问题的求解算法主要分为精确算法和启发式算法。精确算法能够得到问题的精确解，但时间复杂度较大，对于大规模的车辆路径问题在现有的计算水平下无法在有效时间内得到问题的解，因此精确算法适合求解中小规模的车辆路径问题。启发式算法一般分为进化算法和群智能算法，因为其具有较好的并行求解能力和快速收敛的特点，因此能够适应于大规模的车辆路径问题，但启发式算法无法得到精确解，依赖于算法的收敛性。


技术实现要素：

4.发明目的：本发明的目的是提供一种启发式分支定价算法，融合精确算法的准确性以及启发式算法快速收敛的特点，提高了精确算法的适应性以及启发式算法的收敛性，能够在有效的时间内提供较好的近似解。
5.技术方案：一种基于启发式分支定价算法的带时间窗车辆路径规划方法，包括以下步骤：
6.步骤1，根据实际要解决的带时间窗车辆路径规划问题，建立客户点数据模型；所述客户点数据模型包括客户点和配送中心，并对配送中心和客户点分别设定标号；
7.步骤2，根据配送中心以及客户点信息，构建客户点之间的距离矩阵、时间矩阵；
8.步骤3，根据客户点的实际需求建立时间窗违反惩罚规则，将运输成本最小化作为目标函数，构建带时间窗的车辆路径规划模型；
9.步骤4，通过启发式分支定价算法对带时间窗的车辆路径规划模型进行优化，求解最佳配送序列。
10.进一步，所述步骤1建立客户点数据模型，具体如下：
11.设置客户点数量为n；设置配送中心为o、d，其中o表示车辆从配送中心出发，d表示车辆返回配送中心；设置配送中心标号为0，客户点标号为1、2、3
…
、n,设置客户点和配送中
心的横坐标和纵坐标分别为xi,yi；每辆车的容量设置为q，车辆速度设置为u；客户点时间窗为[ei,li],其中ei为客户点的最早服务时间，li为客户点的最晚服务时间，并将配送中心以及客户点信息存储在数据表中。
[0012]
进一步，步骤2中，构建客户点之间的距离矩阵、时间矩阵，具体如下：
[0013]
距离矩阵：计算配送中心以及客户点两两之间的距离，并将计算结果以数组的形式进行存储，记数组为d，数组元素为d
ij
，表示车辆从i行驶到j的距离，其中d
ii
＝0,d
ji
＝d
ij
；
[0014]
时间矩阵：计算配送中心以及客户点两两之间的运输时间，并将计算结果以数组的形式进行存储，记数组为t，数组元素为t
ij
,其中t
ii
＝0。
[0015]
进一步，步骤3中，所述目标函数数学建模如下：
[0016][0017]
s.t.
[0018]
第二约束：
[0019]
第三约束：
[0020]
第四约束：
[0021]
第五约束：
[0022]
第六约束：
[0023]
第七约束：
[0024]
第八约束：
[0025]
第九约束：
[0026]
第十约束：
[0027]
其中o，d表示同一配送中心，o表示车辆从配送中心出发，d表示车辆返回配送中心；c表示客户点集合，v表示车辆集合，n表示配送中心与客户点集合，即n＝c∪o∪d；no表示出发配送中心和客户点集合，即no＝c∪o；nd表示返回配送中心和客户点集合，即nd＝c∪d；k表示车辆标号，i表示出发配送中心和客户点标号，j表示返回配送中心和客户点标号，表示任意；表示车辆k从配送中心出发访问客户，表示车辆k从客户点返回配送中心；fv表示车辆使用成本，fs表示车辆单位运输成本；d
ij
表示车辆从i行驶到j的距离，p表示单位时间惩罚成本；q表示车辆最大容量；at
ki
表示车辆k到达节点i的时间；wt
ki
表示车辆k在节点i的早到等待时间；st
ki
表示车辆k在节点i的服务时间，变量y
ki
是二元变量，当车辆k访问了节点i为1，其他为0，表示如下：
[0028][0029]
变量是二元变量，当车辆k离开节点i并访问节点j为1，其他为0，表示如下：
[0030][0031]
其中，目标函数表示运输成本最小化，包括车辆使用成本、车辆行驶成本、违反时间窗的惩罚成本；第二约束表示每个客户点被一辆车访问，并且只访问一次；第三约束表示从其他节点流入该节点满足流平衡约束；第四约束表示从该节点流出访问其他节点满足流平衡约束；第五约束表示车辆从配送中心出发并返回配送中心；第六约束表示车辆容量约束；第七约束表示车辆到达客户点的时间不能晚于客户点的最晚时间窗；第八约束用于约束客户点之间访问的时间顺序；第九约束表示车辆k访问节点i的二元变量；第十约束表示车辆k离开节点i的二元变量。
[0032]
进一步，步骤4中，调用启发式分支定价算法对带时间窗的车辆路径规划模型进行优化，求解最佳配送序列，包括以下步骤：
[0033]
步骤4-1，通过启发式算法初始化一组路径集ω，此时的路径集为全部路径的一个子集，在该路径集的约束下形成限制主问题，将限制主问题进行线性松弛，通过线性规划方法求解该松弛问题，得到松弛问题的最优解ω’以及对偶变量值πi，具体过程如下：
[0034]
g(x)＝object(ω),ω＝(θ1,θ2,
…
,θ
p
)
[0035]
其中g(x)＝object(ω)为min∑
p∈ωcp
·
θ
p
，表示运输成本最小化；c
p
表示路径p的运输成本；θ
p
表示路径变量；ω表示路径集合，并且满足∑
p∈ωvip
·
θ
p
＝1θ
p
∈{0,1}；当路径p经过客户点i时v
ip
＝1，其他v
ip
＝0；
[0036]
步骤4-2，通过对偶变量值更新子问题，并求解带有资源约束的最短路径问题；
[0037]
f(x)＝object(x),x＝(x1,x2,
…
,xc)
[0038]
其中object(x)表示目标函数，用来表示运输成本最小化；x表示可行域；
[0039]
步骤4-3，计算检验数：
[0040][0041]
其中c
ij
表示最短路径问题的当前路段成本；πi表示限制主问题的线性松弛问题的对偶变量，该对偶变量表示访问节点i为降低路段成本带来的收益，用于修正路段成本；表示通过限制主问题对偶变量修正后的路段成本；
[0042]
若检验数小于0，则将所得最短路径添加到路径集转到步骤4-1，更新限制主问题；若检验数大于等于0，转到步骤4-4；
[0043]
步骤4-4，判断是否达到最大迭代次数，若达到最大迭代次数，转到步骤4-7；否则，转到步骤4-5；
[0044]
步骤4-5，对步骤4-2得到的最短路径通过2-interchange和or-interchange进行扰动，得到最新最短路径；
[0045]
步骤4-6，通过步骤4-3检验数对步骤4-5得到的最新最短路径进行检验，判断检验数是否小于0；若检验数小于0，则将所得最短路径添加到路径集转到步骤4-1，更新限制主问题；若检验数大于等于0，转到步骤4-7；
[0046]
步骤4-7，对步骤4-1限制主问题的线性松弛问题最优解ω’的所有变量值进行检查，若所有的变量值都满足整数约束，则最优解为整数解，算法结束；否则，转到步骤4-8对ω’进行优化；
[0047]
步骤4-8：将最优解通过分支定界法进行求解，若得到最优解，则结束；若不满足整数约束的最优解，则通过分支定界法进行求解，得到最优整数解ω’。
[0048]
进一步，步骤4-5中，对当前路径集中的路径依据路径长度从小到大进行排序，选取当前最短路径与步骤4-2所述最短路径进行2-interchange操作得到一个邻域解，然后对所得领域解进行or-interchange操作得到新的邻域解，最终得到的邻域解为最新最短路径。
[0049]
本发明与现有技术相比，其显著效果如下：
[0050]
1、本发明通过引入启发式分支定价算法来求解带时间窗的车辆路径问题，能够有效的融合精确求解算法和启发式求解算法的特点，因此该算法具有较好的鲁棒性和快速收敛的特点，能够更加有效的求解大规模的车辆路径问题。
[0051]
2、本发明建立的带时间窗车辆路径问题充分考虑了客户点的时间窗要求，更好的贴合了实际服务需求，提高了客户点的服务水平，提升了客户满意度。
附图说明
[0052]
图1为本发明的流程框图；
[0053]
图2为本发明中启发式分支定价算法的流程框图；
[0054]
图3(a)为本发明中路径进行2-interchange前的示意图；图3(b)为本发明中路径进行2-interchange后的示意图；
[0055]
图4(a)为本发明中路径进行or-interchange前的示意图；图4(b)为本发明中路径进行or-interchange后的示意图。
具体实施方式
[0056]
为了更加直观清楚的展示本发明的目的和优点，下面结合本发明实施方式中的附图对本发明进行详细阐述，显然，所描述的实施方式是本发明的一部分实施方式，而不是全部的实施方式。基于本发明中的实施方式，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其它实施方式，都属于本发明保护的范围。
[0057]
本发明提出的一种基于启发式分支定价算法的带时间窗车辆路径规划方法，包含以下步骤：
[0058]
步骤1，根据实际要解决的带时间窗车辆路径规划问题，建立客户点数据模型；所述客户点数据模型包括客户点和配送中心，并对配送中心和客户点分别设定标号；
[0059]
客户数量为n，设置配送中心为o、d，其中o表示车辆从配送中心出发，d表示车辆返回配送中心；配送中心标号为0，客户点标号1、2、3
…
n,设置配送中心和客户点的横坐标和纵坐标分别为xi,yi；每辆车的容量设置为q，车辆速度设置为u；客户点时间窗为[ei,li],其中ei为客户点的最早服务时间，li为客户点的最晚服务时间；将配送中心以及客户点信息存储在数据表中，具体如下：
[0060]
表1
[0061][0062][0063]
步骤2，根据配送中心以及客户点信息，构建客户点之间的距离矩阵、时间矩阵；
[0064]
距离矩阵：计算配送中心以及客户点两两之间的距离，并将计算结果以数组的形式进行存储，记数组为d，数组元素为d
ij
，表示车辆从i行驶到j的距离，其中d
ii
＝0,d
ji
＝d
ij
。
[0065]
时间矩阵：计算配送中心以及客户点两两之间的运输时间，并将计算结果以数组的形式进行存储，记数组为t，数组元素为t
ij
,其中t
ii
＝0。
[0066]
步骤3，构建带时间窗的车辆路径规划模型；
[0067]
依据客户点的实际配送需求建立时间窗违反惩罚规则，对于早于时间窗到达客户点的车辆增加时间成本惩罚，对于晚于时间窗到达客户点的车辆则另派其他车辆进行服务以提高服务水平，目标函数表示为运输成本最小化，其中运输成本包含车辆使用成本，车辆行驶成本以及时间惩罚成本。
[0068]
目标函数：
[0069][0070]
s.t.
[0071]
[0072][0073][0074][0075][0076][0077][0078][0079][0080]
其中o，d表示同一配送中心，o表示车辆从配送中心出发，d表示车辆返回配送中心；c表示客户点集合，v表示车辆集合，n表示配送中心与客户点集合，即n＝c∪o∪d；no表示出发配送中心和客户点集合，即no＝c∪o；nd表示返回配送中心和客户点集合，即nd＝c∪d；k表示车辆标号，i表示出发配送中心和客户点标号，j表示返回配送中心和客户点标号，表示任意；表示车辆k从配送中心出发访问客户，表示车辆k从客户点返回配送中心；fv表示车辆使用成本，fs表示车辆单位运输成本；d
ij
表示车辆从i行驶到j的距离，p表示单位时间惩罚成本；q表示车辆最大容量；at
ki
表示车辆k到达节点i的时间；wt
ki
表示车辆k在节点i的早到等待时间；st
ki
表示车辆k在节点i的服务时间，变量y
ki
是二元变量，当车辆k访问了节点i为1，其他为0，表示如下：
[0081][0082]
变量是二元变量，当车辆k离开节点i并访问节点j为1，其他为0，表示如下：
[0083][0084]
其中，公式(1)为目标函数，表示运输成本最小化，包括车辆使用成本、车辆行驶成本、违反时间窗的惩罚成本；公式(2)为第二约束，表示每个客户点被一辆车访问，并且只访问一次；公式(3)为第三约束，是流平衡约束，表示从其他节点流入该节点满足流平衡约束；公式(4)为第四约束，是流平衡约束，表示从该节点流出访问其他节点满足流平衡约束；公式(5)为第五约束，表示车辆从配送中心出发并返回配送中心；公式(6)为第六约束，表示车辆容量约束；公式(7)为第七约束，表示时间窗约束，表示车辆到达客户点的时间不能晚于客户点的最晚时间窗；公式(8)为第八约束，表示时间窗约束，用于约束客户点之间访问的时间顺序；公式(9)为第九约束，表示二元变量；公式(10)为第十约束，表示二元变量。
[0085]
步骤4，通过启发式分支定价算法对带时间窗的车辆路径规划模型进行优化，求解最佳配送序列。启发式分支定价算法求解最佳配送序列的迭代方法的具体流程如图2所示，具体步骤如下：
[0086]
步骤4-1:通过启发式算法初始化一组路径集ω，此时的路径集为全部路径的一个子集，在该路径集的约束下形成限制主问题，将限制主问题进行线性松弛，通过线性规划方
法求解该松弛问题，得到松弛问题的最优解ω’以及对偶变量值πi，具体公式如下：
[0087]
g(x)＝object(ω),ω＝(θ1,θ2,
…
,θ
p
)
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(13)
[0088]
其中g(x)＝object(ω)为min∑
p∈ωcp
·
θ
p
，表示运输成本最小化；c
p
表示路径p的运输成本；θ
p
表示路径变量；ω表示路径集合，并且满足∑
p∈ωvip
·
θ
p
＝1θ
p
∈{0,1}；当路径p经过客户点i时v
ip
＝1，其他v
ip
＝0。
[0089]
步骤4-2:通过对偶变量值更新子问题，并求解带有资源约束的最短路径问题；
[0090]
f(x)＝object(x),x＝(x1,x2,
…
,xc)
ꢀꢀꢀꢀꢀꢀꢀꢀ
(14)
[0091]
其中object(x)表示目标函数，用来表示运输成本最小化；x表示步骤3中所述第三约束(3)到第十约束(10)组成的可行域。
[0092]
步骤4-3:计算检验数：
[0093][0094]
其中c
ij
表示最短路径问题的当前路段成本；πi表示步骤4-1所述限制主问题的线性松弛问题的对偶变量，该对偶变量表示访问节点i为降低路段成本带来的收益，用于修正路段成本；表示通过限制主问题对偶变量修正后的路段成本。判断检验数是否小于0；若检验数小于0，则将所得最短路径添加到路径集转到步骤4-1，更新限制主问题；若检验数大于等于0，转到步骤4-4。
[0095]
步骤4-4:判断是否达到最大迭代次数，若达到最大迭代次数，转到步骤4-7；否则，转到步骤4-5。
[0096]
步骤4-5:对当前路径集中的路径依据路径长度从小到大进行排序，选取当前最短路径与步骤4-2的最短路径进行2-interchange操作得到一个邻域解，然后对所得路径进行or-interchange操作得到新的邻域解，最终得到的邻域解为最新最短路径。
[0097]
如图3(a)、图3(b)所示为对最短路径进行2-interchange的示意图，2-interchange用于两条路径间的邻域搜索，从两条路径分别选取a和b个节点进行交换来产生邻域解(a,b∈{0,1,2}且a和b不同时为0)。当a＝1,b＝1时，将路径l中的1个节点x与路径k中的1个节点y进行交换产生邻域解。
[0098]
图4(a)、图4(b)为对最短路径进行or-interchange的示意图，or-interchange用于单条线路的邻域搜索，将线路内部两个节点交换位置来产生邻域解。当a＝1，b＝1时，将路径l中x、y两个节点进行交换产生领域解。
[0099]
步骤4-6：通过步骤4-3检验数对步骤4-5得到的领域解进行检验，判断检验数是否小于0；若检验数小于0，则将所得最短路径添加到路径集转到步骤4-1，更新限制主问题；若检验数大于等于0，转到步骤4-7。
[0100]
步骤4-7：对步骤4-1限制主问题的线性松弛问题最优解ω’的所有变量值进行检查，若所有的变量值都满足整数约束，则最优解为整数解，算法结束；否则转到步骤4-8对ω’进行优化。
[0101]
步骤4-8：将最优解通过分支定界法进行求解，若得到最优解，则结束；若不满足整数约束的最优解，则通过分支定界法进行求解，得到最优整数解ω’。
[0102]
综上所述，本发明基于精确算法与启发式算法相结合的方式，对带时间窗的车辆路径问题的解不断进行优化，将原问题分解为主问题和子问题，对于主问题选取一部分路
径作为可行域形成限制主问题，通过求解限制主问题的松弛问题，得到对偶变量值重新定价子问题的路段成本，形成新的子问题，通过求解子问题判断检验数的值，从而决定是否将子问题的解添加到限制主问题的路径集。然后不断迭代主问题与子问题，直至达到最大迭代次数。
[0103]
本发明在主问题与子问题的迭代过程中加入2-interchange和or-interchange的路径扰动，以此来达到避免陷入局部最优的目的，使算法的结果更加的准确。

技术特征：
1.一种基于启发式分支定价算法的带时间窗车辆路径规划方法，其特征在于，包括以下步骤：步骤1，根据实际要解决的带时间窗车辆路径规划问题，建立客户点数据模型；所述客户点数据模型包括客户点和配送中心，并对配送中心和客户点分别设定标号；步骤2，根据配送中心以及客户点信息，构建客户点之间的距离矩阵、时间矩阵；步骤3，根据客户点的实际需求建立时间窗违反惩罚规则，将运输成本最小化作为目标函数，构建带时间窗的车辆路径规划模型；步骤4，通过启发式分支定价算法对带时间窗的车辆路径规划模型进行优化，求解最佳配送序列。2.如权利要求1所述的基于启发式分支定价算法的带时间窗车辆路径规划方法，其特征在于，步骤1中，所述客户点数据模型如下：设置客户点数量为n；设置配送中心为o、d，其中o表示车辆从配送中心出发，d表示车辆返回配送中心；设置配送中心标号为0，客户点标号为1、2、3
…
、n,设置客户点和配送中心的横坐标和纵坐标分别为x
i
,y
i
；每辆车的容量设置为q，车辆速度设置为u；客户点时间窗为[e
i
,l
i
],其中e
i
为客户点的最早服务时间，l
i
为客户点的最晚服务时间，并将配送中心以及客户点信息存储在数据表中。3.如权利要求1所述的基于启发式分支定价算法的带时间窗车辆路径规划方法，其特征在于，步骤2中，构建客户点之间的距离矩阵、时间矩阵，具体如下：距离矩阵：计算配送中心以及客户点两两之间的距离，并将计算结果以数组的形式进行存储，记数组为d，数组元素为d
ij
，表示车辆从i行驶到j的距离，其中d
ii
＝0,d
ji
＝d
ij
；时间矩阵：计算配送中心以及客户点两两之间的运输时间，并将计算结果以数组的形式进行存储，记数组为t，数组元素为t
ij
,其中t
ii
＝0。4.如权利要求1所述的基于启发式分支定价算法的带时间窗车辆路径规划方法，其特征在于，步骤3中，所述目标函数数学建模如下：s.t.第二约束：第三约束：第四约束：第五约束：第六约束：第七约束：第八约束：
第九约束：第十约束：其中，o、d表示同一配送中心，o表示车辆从配送中心出发，d表示车辆返回配送中心；c表示客户点集合，v表示车辆集合，n表示配送中心与客户点集合，即n＝c∪o∪d；n
o
表示出发配送中心和客户点集合，即n
o
＝c∪o；n
d
表示返回配送中心和客户点集合，即n
d
＝c∪d；k表示车辆标号，i表示出发配送中心和客户点标号，j表示返回配送中心和客户点标号，表示任意；表示车辆k从配送中心出发访问客户，表示车辆k从客户点返回配送中心；f
v
表示车辆使用成本，f
s
表示车辆单位运输成本；d
ij
表示车辆从i行驶到j的距离，p表示单位时间惩罚成本；q表示车辆最大容量；at
ki
表示车辆k到达节点i的时间；wt
ki
表示车辆k在节点i的早到等待时间；st
ki
表示车辆k在节点i的服务时间，变量y
ki
是二元变量，当车辆k访问了节点i为1，其他为0，表示如下：变量是二元变量，当车辆k离开节点i并访问节点j为1，其他为0，表示如下：其中，目标函数表示运输成本最小化，包括车辆使用成本、车辆行驶成本、违反时间窗的惩罚成本；第二约束表示每个客户点被一辆车访问，并且只访问一次；第三约束表示从其他节点流入该节点满足流平衡约束；第四约束表示从该节点流出访问其他节点满足流平衡约束；第五约束表示车辆从配送中心出发并返回配送中心；第六约束表示车辆容量约束；第七约束表示车辆到达客户点的时间不能晚于客户点的最晚时间窗；第八约束用于约束客户点之间访问的时间顺序；第九约束表示车辆k访问节点i的二元变量；第十约束表示车辆k离开节点i的二元变量。5.如权利要求1所述的基于启发式分支定价算法的带时间窗车辆路径规划方法，其特征在于，步骤4中，调用启发式分支定价算法对带时间窗的车辆路径规划模型进行优化，求解最佳配送序列，包括以下步骤：步骤4-1，通过启发式算法初始化一组路径集ω，此时的路径集为全部路径的一个子集，在该路径集的约束下形成限制主问题，将限制主问题进行线性松弛，通过线性规划方法求解该松弛问题，得到松弛问题的最优解ω’以及对偶变量值π
i
，具体过程如下：g(x)＝object(ω),ω＝(θ1,θ2,
…
,θ
p
)其中g(x)＝object(ω)为min∑
p∈ω
c
p
·
θ
p
，表示运输成本最小化；c
p
表示路径p的运输成本；θ
p
表示路径变量；ω表示路径集合，并且满足∑
p∈ωvip
·
θ
p
＝1θ
p
∈{0,1}；当路径p经过客户点i时v
ip
＝1，其他v
ip
＝0；步骤4-2，通过对偶变量值更新子问题，并求解带有资源约束的最短路径问题；f(x)＝object(x),x＝(x1,x2,
…
,x
c
)其中object(x)表示目标函数，用来表示运输成本最小化；x表示可行域；
步骤4-3，计算检验数：其中c
ij
表示最短路径问题的当前路段成本；π
i
表示限制主问题的线性松弛问题的对偶变量，表示访问节点i为降低路段成本带来的收益，用于修正路段成本；表示通过限制主问题对偶变量修正后的路段成本；若检验数小于0，则将所得最短路径添加到路径集转到步骤4-1，更新限制主问题；若检验数大于等于0，转到步骤4-4；步骤4-4，判断是否达到最大迭代次数，若达到最大迭代次数，转到步骤4-7；否则，转到步骤4-5；步骤4-5，对步骤4-2得到的最短路径通过2-interchange和or-interchange进行扰动，得到最新最短路径；步骤4-6，通过步骤4-3检验数对步骤4-5得到的最新最短路径进行检验，判断检验数是否小于0；若检验数小于0，则将所得最短路径添加到路径集转到步骤4-1，更新限制主问题；若检验数大于等于0，转到步骤4-7；步骤4-7，对步骤4-1限制主问题的线性松弛问题最优解ω’的所有变量值进行检查，若所有的变量值都满足整数约束，则最优解为整数解，算法结束；否则，转到步骤4-8对ω’进行优化；步骤4-8，将最优解通过分支定界法进行求解，若得到最优解，则结束；若不满足整数约束的最优解，则通过分支定界法进行求解，得到最优整数解ω’。6.根据权利要求5所述的基于启发式分支定价算法的带时间窗车辆路径规划方法，其特征在于：步骤4-5中，对当前路径集中的路径依据路径长度从小到大进行排序，选取当前最短路径与步骤4-2所述最短路径进行2-interchange操作得到一个邻域解，然后对所得领域解进行or-interchange操作得到新的邻域解，最终得到的邻域解为最新最短路径。

技术总结
本发明公开了一种基于启发式分支定价算法的带时间窗车辆路径规划方法，包括以下步骤：步骤1，根据实际要解决的带时间窗车辆路径规划问题，建立客户点数据模型；步骤2，根据配送中心以及客户点信息，构建客户点之间的距离矩阵、时间矩阵；步骤3，根据客户点的实际需求建立时间窗违反惩罚规则，构建带时间窗的车辆路径规划模型；步骤4，通过启发式分支定价算法对带时间窗的车辆路径规划模型进行优化，求解最佳配送序列。本发明采用全局搜索能力强、收敛速度快、鲁棒性好的启发式分支定价算法进行最优配送路径的选择，有利于降低企业物流配送成本、提高服务质量。提高服务质量。提高服务质量。


技术研发人员：程琳 王世伟 张晨皓 李哲航 赵汗青 刘玥 任姿蓉
受保护的技术使用者：东南大学
技术研发日：2023.04.24
技术公布日：2023/8/21