本发明属于物流路径规划领域，具体涉及一种配送路径规划方法。
背景技术：
1、vrp(vehicle routing problem)是优化物流配送的关键问题，但随着科技与商业的快速发展，多种多样的物流配送模式层出不穷。基于传统配送模式下的vrp模型已不再适用于建模和求解当前复杂的物流配送模式。目前针对客户可被车辆重复服务的配送模式，尚未有有效的建模求解方法。
2、传统的vrp考虑的问题模型较为理想，其主要研究客户需求均由中心仓库满足，客户的货物需求量及货物来源地确定，且仓库中不同种类的货物均不会出现短缺的配送问题。而现实中的生产环境较为复杂，其不同种类的货物存放于各车场中，每个客户均由多个车场的库存来满足，客户与车场的具体供需匹配关系及相应匹配数量未知，在具体配送过程中客户需要不同的车辆重复访问以满足该客户的所有需求。因此传统的vrp在处理“多车场与客户匹配问题”与“客户可被重复问题”时存在盲区。
3、vrp是一类np难问题，传统的精确式算法无法在合理时间内对此进行求解。所以，使用启发式算法求解问题的优秀可行解，是研究该类问题的一个重要方法。当前，研究人员多使用蚁群算法处理该类问题，蚁群算法是模拟蚁群觅食的一种仿生算法，该算法在处理中等规模的组合问题时性能优异，但是对复杂问题时，存在迭代时间长和易陷入局部最优的缺陷，对于复杂的配送路径规划问题，容易出现路线匹配偏差及规划匹配路线时间长的问题。
技术实现思路
1、为了克服规划配送路线不准确及规划匹配路线时间长的问题，本发明提供了一种配送路径规划方法，包括如下步骤：
2、根据所有的货物种类与客户需求节点要求的货物种类，建立客户需求节点与货物种类的对应关系矩阵；
3、根据各仓库保有的货物种类与所有的货物种类，建立车场与货物种类的对应关系矩阵；
4、根据客户需求节点与货物种类的对应关系矩阵及车场与货物种类的对应关系矩阵建立车场与客户之间的供求匹配关系的vrp混合整数模型；
5、通过混合变邻域搜索算法对所述vrp混合整数模型进行求解，以获得最优配送路径，具体包括以下步骤：
6、使用蚁群算法确定客户需求节点和车场节点的匹配方案；
7、使用节约算法为客户需求节点和车场节点匹配方案进行路径分组得到初始可行解；
8、使用贪婪算法对所述初始可行解进行优化，得到优化后的路径序列；
9、使用两元素优化算法2-opt对所述路径序列进行局部优化得到优化后的可行解；
10、使用变邻域搜索对所述优化后的可行解进行深度优化，获得最终的可行解，以获得最优路径规划。
11、优选的，所述vrp混合整数模型的目标函数为：
12、
13、式中，cij为节点i与节点j之间的运输成本，k为车辆的编号，k为所有车辆组成的集合，d为所有车场组成的集合，v为所有客户需求节点组成的集合，xijk为车辆k是否从i到j的决策变量，是则置1，否则置0。
14、优选的，所述vrp混合整数模型的约束包括：
15、约束条件1：规定每一辆车的行程都必须是圈：
16、
17、约束条件2：规定每辆车最多使用一次：
18、
19、约束条件3：规定每辆车携带的货物种类不能超过其所出发的车场所储存的货物种类范围：
20、
21、式中，kd代表k车的服务范围；c(i)代表i车场能够服务的客户需求节点集合；
22、规定车辆不会服务到其所属车场服务范围以外的客户需求节点：
23、
24、
25、约束条件4：规定每个客户需求顶点都必须被服务到：
26、
27、约束条件5：车辆不可以从任一个车场直接前往任一个车场：
28、
29、约束条件6：消除子环约束：
30、
31、式中，m∈n*，m≥|v|，n*为正整数集，|v|为客户需求节点集合的大小，
32、m为正整数，u为变量，当节点i与节点j在一个边的两端时，即xijk＝1时，变量ujk小于uik，一个车辆所遍历的所有节点将按照顺序，使节点相应的变量u逐渐增大；
33、约束条件7：车辆容量限制约束，对任意的车辆而言，其服务的客户需求节点的总需求量不能超过其自身的容量：
34、
35、式中，di为i客户需求节点的需求量；q为车辆的容量；
36、约束条件8：车流量平衡，为避免车辆行程中边出现断裂的状况，保证车辆的行程是一个完整的圈：
37、∑i∈v∑j∈v∪dxijk＝∑i∈v∑j∈v∪dxjik。
38、优选的，使用蚁群算法确定客户需求节点和车场节点的匹配方案，包括如下步骤：
39、在每个客户需求节点与每个可服务节点的车场之间设置浓度相等的起始信息素；
40、设置变量：信息素浓度τij(0)＝c，i∈v，j∈d；
41、设置变量：信息素浓度增加值δτij(0)＝0，i∈v，j∈d；
42、τij(0)代表在第一次迭代开始时，i客户需求节点与车场j之间的信息素浓度；δτij(0)代表在第一次迭代开始时，i客户需求节点与车场j之间增加的信息素浓度；
43、设置所有客户需求节点列表，逐个为每个客户需求节点选择车场，遍历整个客户需求节点列表；
44、在蚁群中取出一只蚂蚁，所述蚂蚁为所有的客户需求节点寻找车场，生成一个客户需求节点和车场节点匹配方案，且每只蚂蚁都采用轮盘赌方法为客户需求节点选择车场，并在轮盘赌过程中，使用信息素浓度与能见度作为计算转移概率的参数；
45、计算客户需求节点i和对应的所有可服务该节点的车场之间的转移概率pija；
46、使用轮盘赌方法在所有的pija组成的轮盘中，选出与i匹配的车场j，生成客户需求节点和车场节点匹配方案，每个车场得到应服务列表ld。
47、优选的，使用节约算法为客户需求节点和车场节点匹配方案进行路径分组，得到初始可行解，包括如下步骤：
48、以某一车场节点作为起始点d，将所述车场应服务列表中的每个点与起始点相连接，得到n条线路的d→j→d，j∈ld，n为所述车场应服务列表中的客户需求节点数量；
49、计算不违背限制条件的所有可连接点对(i，j)的节约值s(i，j)，i，j∈ld，计算公式如下：
50、s(i，j)＝c(i，d)+c(j，d)-c(i，j)；
51、式中，节约值s(i，j)代表使用边(i，j)代替原来两条边(i，d)和(j，d)后节省下的距离，c(i，d)代表i点与d点之间的距离，c(j，d)代表j点与d点之间的距离，c(i，j)代表i点与j点之间的距离；
52、将节约值按照从大到小的顺序排列；
53、按照所得的顺序，逐个进行如下操作：若满足以下所有条件即将边(i，j)接入路径；
54、条件1：i节点与j节点不在同一条路线上；
55、条件2：i节点与j节点均与起始点相邻；
56、条件3：新增j节点后不超过车辆的总容量限制；
57、若可插入边(i，j)未遍历结束，返回上一步，直至遍历完所有可插入边；
58、对每个ld进行以上操作，得到一个完整的可行解变量ra，ra代表在蚂蚁a生成的匹配方案下得到的可行解；
59、按照上述步骤对所有的车场进行路径分组，得到由k个路径列表rk组成的ra。
60、优选的，使用贪婪算法对所述初始可行解进行优化，得到优化后的路径序列，包括如下步骤：
61、step1：设定一个空的路径序列，将路径列表所在的车场节点填入空的路由序列中；
62、step2：选中路径序列中的最后一个节点，视作x节点，找到路径列表中离x节点最近的非x节点y，y＝near(x)；
63、step3：将节点y紧接着x节点填入路径序列中，并将y节点从路径列表中移除；
64、step4：若路径列表不为空则返回step2，若路径列表为空则贪婪搜索结束，得到优化后的路径序列；
65、step5：对所有车辆的路径列表做以上操作得到优化后的行程规划。
66、优选的，使用两元素优化算法2-opt对所述路径序列进行局部优化得到优化后的可行解，包括如下步骤：
67、设置变量count，该变量用于计数；
68、设置变量max_count，该变量为最大循环值；
69、设置变量opt_rk，该变量储存k车辆的最优路径序列；
70、设置变量opt_vk，该变量储存当前车辆的最优路径序列总长度；
71、设置变量cur_bk，该变量储存当前车辆的路径序列总长度；
72、设置变量cur_rk，该变量储存当前车辆的路径序列；
73、设置标量len，该标量确定进行2-opt操作时的两个元素之间的距离；
74、设置变量cut_r，该变量储存当前切下的片段；
75、设置变量rev_r，该变量储存反转后的切下的片段；
76、step1：设置最大循环值max_count，置count＝0；
77、step2：设定k车辆的路径序列为opt_rk；
78、step3：若count≤max_count，则随机在路径序列中选取相隔步长为len的一段序列，储存入cut_r，否则输出opt_rk；
79、step4：将cut_r翻转后得到rev_r；
80、step5：将rev_r代替opt_rk中cut_r位置得到cur_rk；
81、step6：计算cur_rk的距离cur_vk，如果cur_vk＜opt_vk，则opt_rk＝cur_rk并置count＝0返回step3，否则置count+＝1返回step3；
82、step7：对所有车辆的路径序列进行以上操作，得到进一步优化的可行解ra。
83、优选的，使用变邻域搜索对所述优化后的可行解进行深度优化，获得最终的可行解，以获得最优路径规划，包括如下步骤：
84、构造贪婪破坏重组邻域；
85、构造遗憾破坏重组邻域；
86、利用贪婪破坏重组邻域和遗憾破坏重组邻域对优化后的可行解深度优化，包含以下步骤：
87、步骤1：设置循环终止条件；
88、步骤2：搜索贪婪破坏重组邻域；
89、步骤3：当搜索到更好的解时，重复步骤2操作；
90、步骤4：当搜索不到更好的解时，继续步骤5操作；
91、步骤5：搜索遗憾破坏重组邻域；
92、步骤6：当搜索到更好的解时，重复步骤5操作；
93、步骤7：当搜索不到更好的解时，继续步骤2操作；
94、步骤8：当到达循环终止条件时，停止邻域操作，得到本次迭代的最优行程规划。
95、优选的，构造贪婪破坏重组邻域，包括如下步骤：
96、step1：破坏动作，根据贪婪准则，将一个使得对总路径成本变化最大的客户需求节点移除，得到一个不完整的路径；
97、step2：重组动作，根据贪婪准则，选择一个使总路径成本变化最小的插入位置，将该被移除的客户需求节点插入到不完整的路径中。
98、优选的，构造遗憾破坏重组邻域，包含以下步骤：
99、step1：破坏动作，根据贪婪准则，将一个使得对总路径成本变化最大的客户需求节点移除，得到一个不完整的路径；
100、step2：重组动作，根据遗憾值重新选择一个使得遗憾值最大的插入位置；将所述被移除的客户需求节点插入到不完整的路径中。
101、本发明提供的一种配送路径规划方法具有以下有益效果：
102、本发明提出一种利用蚁群信息素来引导初始解的变异方法，以提高解的质量，它可以在保留解的优良特征的同时，在小范围内改变解的结构，从而帮助算法跳出局部最优，使得规划的配送路径更精确；通过节约算法将客户分配到各车辆路径中，从而降低了车辆路径中各个客户之间的距离差异，提高了初始解的目标函数值，从而能够减少规划配送路径的时间；通过贪婪搜索算法能够确定客户与车场之间的最佳匹配关系，从而能够匹配最优的配送路径；通过采用变邻域搜索算法进行局部优化，利用不同的邻域结构进行交替搜索，平衡了集中性和疏散性，缩短了算法的迭代时间；因此，由于本发明生成的初始解质量较高，所以局部搜索时能够避免遍历质量较差的解，从而加快了算法收敛的速度，减少了计算的迭代时间，从而在保证路径规划准确性的同时节约了路径规划的时间。
1.一种配送路径规划方法，其特征在于，包括如下步骤：
2.根据权利要求1所述的配送路径规划方法，其特征在于，所述vrp混合整数模型的目标函数为：
3.根据权利要求2所述的配送路径规划方法，其特征在于，所述vrp混合整数模型的约束包括：
4.根据权利要求1所述的配送路径规划方法，其特征在于，使用蚁群算法确定客户需求节点和车场节点的匹配方案，包括如下步骤：
5.根据权利要求4所述的配送路径规划方法，其特征在于，使用节约算法为客户需求节点和车场节点匹配方案进行路径分组，得到初始可行解，包括如下步骤：
6.根据权利要求5所述的配送路径规划方法，其特征在于，使用贪婪算法对所述初始可行解进行优化，得到优化后的路径序列，包括如下步骤：
7.根据权利要求6所述的配送路径规划方法，其特征在于，使用两元素优化算法2-opt对所述路径序列进行局部优化得到优化后的可行解，包括如下步骤：
8.根据权利要求7所述的配送路径规划方法，其特征在于，使用变邻域搜索对所述优化后的可行解进行深度优化，获得最终的可行解，以获得最优路径规划，包括如下步骤：
9.根据权利要求8所述的配送路径规划方法，其特征在于，构造贪婪破坏重组邻域，包括如下步骤：
10.根据权利要求8所述的配送路径规划方法，其特征在于，构造遗憾破坏重组邻域，包含以下步骤：
