基于SP模型的两阶段路径规划优化方法

基于sp模型的两阶段路径规划优化方法
技术领域
1.本发明属于物流调度优化技术问题领域，尤其涉及一种基于sp模型的两阶段路径规划的优化方法。


背景技术：

2.在城市道路拥堵问题日趋严重这样的背景下，企业员工上班不仅面临着因道路拥堵问题而产生的迟到风险，而且其上班的成本也会显著地增加。针对这种情况，企业通勤班车服务应运而生。通勤服务企业或大型企业自身的通勤服务团队为员工提供统一接送服务，通勤团队首先设定多个乘车点，乘客可就近选择上下车站点，每个站点会有前往多个目的地或厂区的乘客，通勤团队需合理进行车辆、车型和运行路线规划，保证把乘客送往目的地。
3.现在多数通勤服务企业关于多目的地多车型的路线规划普遍存在以下问题：
4.一、人工设计线路，首先会耗时耗力，其次会不可避免地造成成本浪费，多车型多目的地使得人工规划路线的难度加大；
5.二、部分企业在利用现存路径规划算法计算路线的耗时过久，且计算结果与最优解仍存在一定差距。
6.关于多目的地多车型的路线规划属于车辆路径问题(vehicle routing problem，vrp)，是个典型的np-hard问题。目前求解vrp问题的方法主要分为启发式算法和精确算法两大类，其中启发式算法主要包括遗传算法、自适应广义粒子群算法、模拟退火、蚁群算法等，启发式算法常用于求解vrp问题，但由于其具有随机性，无法直接证明其求解结果的最优性，且启发式算法往往伴随着大量可调参数，求解性能对参数的依赖较大，往往需要调试人员对算法具有较深的理解，且对于不同数据，其效果也会不同，求解结果稳定性较差，容易出现收敛速度慢，陷入局部极小值，计算时间过长等问题，并且其优解不可复现，从某种程度上限制了其使用。


技术实现要素：

7.本发明旨在解决现有技术在路径规划问题上分别使用启发式算法和精确算法在参数选择上调试容易导致的求解结果稳定性较差、收敛速度慢、陷入局部极小值、计算时间过长的技术问题。
8.为解决上述技术问题，第一方面，本发明实施例提供一种基于sp模型的两阶段路径规划的优化方法，所述方法包括以下步骤：
9.s1、构建关于运营成本的路径规划数学模型；
10.s2、基于dantzig-wolfe分解方式，将所述路径规划数学模型分解为路径优化主问题和资源优化子问题；
11.s3、根据预设初始解求解算法，计算所述路径规划数学模型的初始解，并根据所述初始解初始化分支定价问题树，使所述初始解作为所述分支定价问题树的根节点；
12.s4、从所述分支定价问题树取出头节点，进行列生成，对所述资源优化子问题进行求解，其中，判断对应的所述路径优化主问题的解是否为整数解，若是，则更新所述分支定价问题树的上界，并将对应的所述路径优化主问题的解进行剪枝；若否，则基于对应的所述路径优化主问题的解的弧值构建所述分支定价问题树的分支节点；
13.s5、判断所述分支定价问题树是否为空，若否，迭代至步骤s4；若是，则输出所述路径优化主问题的解作为路径规划优化结果。
14.更进一步地，所述路径规划数学模型满足以下关系式：
[0015][0016][0017][0018][0019][0020][0021]ckij
＝d
ij
δk；
[0022]yij
≥0，i≠j＝(0，...，n)；
[0023]
x
kij
∈{0，1}，i≠j＝(0，...，n)，k＝(1，...，t)；
[0024]
其中，t表示车型数目，qk表示车型k的最大载客量，pj表示第j个站点的乘客数量，c
kij
表示第k个车型从站点i行驶至站点j的能耗，为零一变量，取值1表示第k种车型从站点i行驶至站点j，0表示车辆统一放置中心，y
ij
表示从站点i到站点j的乘客装载量。
[0025]
更进一步地，所述路径优化主问题满足以下关系式：
[0026][0027][0028]
p
ij
∈{0，1}；
[0029]
θi≥0；
[0030]
其中，θi表示模型选择可行路径i的系数；p
ij
为表示在可行路径i中含有站点j的零一变量，若含有则p
ij
取1，否则取0；ci表示第i条可行路径的能耗；
[0031]
所述资源优化子问题满足以下关系式：
[0032][0033][0034][0035][0036][0037][0038]
更进一步地，步骤s3中的所述预设初始解求解算法，包括并行蚁群算法和变邻域搜索算法。
[0039]
更进一步地，步骤s3中，所述根据预设初始解求解算法，计算所述路径规划数学模型的初始解的步骤，还包括步骤：
[0040]
根据预设初始解改进方法，对所述初始解进行处理，所述预设初始解改进方法包括状态压缩动态规划法和混合整数规划法。
[0041]
更进一步地，步骤s3包括以下子步骤：
[0042]
s31、初始化剩余站点集合s和初始路径集合t，其中s为所有到指定目的地的乘客数非零的站点集合，t为空集，利用所述并行蚁群算法对所述剩余站点集合s进行计算，得到最佳路径，并将所述最佳路径放入所述初始路径集合t，同时将所述最佳路径中的站点从所述剩余站点集合s移出，重复上述步骤直到所述剩余站点集合s为空集；
[0043]
s32、基于所述预设初始解改进方法，对所述初始路径集合t进行优化，得到第二路径集合t2；
[0044]
s33、利用所述变邻域搜索算法对所述第二路径集合t2进行优化计算，得到第三路径集合t3；
[0045]
s34、基于所述预设初始解改进方法，对所述第三路径集合t3进行优化，输出得到所述初始解。
[0046]
更进一步地，步骤s4中，从所述分支定价问题树取出头节点，进行列生成，对所述资源优化子问题进行求解的方法包括启发式spfa算法和pulse算法。
[0047]
更进一步地，步骤s4中，更新所述分支定价问题树的上界，并将对应的所述路径优化主问题的解进行剪枝的策略，包括不可行剪枝策略、边界剪枝策略和回滚剪枝策略。
[0048]
本发明所达到的有益技术效果，在于提出了一种基于sp模型的启发式精确式两阶段路径规划优化方法，该方法把含有大量变量和约束的混合整数模型分解成一个基于路径的主问题和一个带有资源约束的最短路径子问题，以达到分而治之的效果，并且在求解定价子问题时算法采取并行计算，大幅节省不同车型的求解时间，相比传统人工计算的方法，不依赖调试人员对算法参数的调整，求解速度更快，计算结果更可靠，求解的稳定性也更
高。
附图说明
[0049]
图1是本发明实施例提供的基于sp模型的两阶段路径规划的优化方法的步骤流程图；
[0050]
图2是本发明实施例提供的解码评价规则的示意图；
[0051]
图3是本发明实施例提供的无环图构造过程的节点示意图；
[0052]
图4是本发明实施例提供的bin-shuffle算子示意图；
[0053]
图5是本发明实施例提供的bin-shake算子示意图；
[0054]
图6是本发明实施例提供的bin-shuffle-shake算子示意图；
[0055]
图7是本发明实施例提供的初始解路径示意图；
[0056]
图8是本发明实施例提供的不含有子回路的路径示意图；
[0057]
图9是本发明实施例提供的分支定价问题的求解流程；
[0058]
图10是本发明实施例提供的回滚剪枝示意图。
具体实施方式
[0059]
为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅仅用以解释本发明，并不用于限定本发明。
[0060]
请参照图1，图1是本发明实施例提供的基于sp模型的两阶段路径规划的优化方法的步骤流程图，所述方法包括以下步骤：
[0061]
s1、构建关于运营成本的路径规划数学模型。
[0062]
具体的，本发明实施例所解决的技术问题背景为：针对多车型多目的地路径规划问题，通勤团队首先设定多个乘车点，乘客可就近选择上下车站点，每个站点会有前往多个目的地或厂区的乘客，通勤团队需合理进行车辆、车型和运行路线规划，保证把乘客送往目的地，运营最终目的就是尽可能降低车型车辆路径运营方案的成本，用于求解该问题建立的模型即sp模型。
[0063]
运营服务企业的成本与车辆数、车型、行驶路径有关，已知所有站点位置，包含车辆统一停靠区域、目的地、上下车站点、每个上下车站点对应的不同目的地的乘客数量、不同类型车辆的最大乘客承运量作为算法输入，通过计算获取不同车型车辆数和不同车辆的运行路线，使车辆数尽可能少、总里程尽可能短，保障运营工作的同时实现运营企业全年运营成本最优。
[0064]
定义t表示车型数目，qk表示车型k的最大载客量，pj表示第j个站点的乘客数量，c
kij
表示第k个车型从站点i行驶至站点j的能耗，为零一变量，取值1表示第k种车型从站点i行驶至站点j，0表示车辆统一放置中心，y
ij
表示从站点i到站点j的乘客装载量，和y
ij
的决策变量取值规则如下：
[0065]
[0066]yij
＝从站点i到站点j的乘客装载量
ꢀꢀꢀꢀ
(2)；
[0067]
更进一步地，所述路径规划数学模型满足以下关系式：
[0068][0069][0070][0071][0072][0073][0074]ckij
＝d
ij
δkꢀꢀꢀꢀ
(9)；
[0075]yij
≥0，i≠j＝(0，...，n)
ꢀꢀꢀꢀ
(10)；
[0076]
x
kij
∈{0，1}，i≠j＝(0，...，n)，k＝(1，...，t)
ꢀꢀꢀꢀ
(11)；
[0077]
其中，目标函数(3)表示最小化总能耗；约束(4)和(5)保证车辆到达目的地后乘客的下车；约束(6)表示乘客的移动，确保每个乘客都能被送往目的地；约束(7)确保车辆在行驶过程中搭载的乘客数量不超过其最大载客量；约束(8)表示如果没有车辆从站点i行驶至站点j，则从站点i到站点j就没有人员流动。
[0078]
s2、基于dantzig-wolfe分解方式，将所述路径规划数学模型分解为路径优化主问题和资源优化子问题。
[0079]
由于所述路径规划数学模型中描述的混合整数规划模型含有大量的变量和约束，即使转化为sp模型后，模型的规模也很大，为高效求得sp模型的最优解或近似最优解，本发明实施例根据dantzig-wolfe分解原理，把含有大量变量和约束的混合整数模型分解成一个基于路径的主问题和一个带有资源约束的最短路径子问题，以达到分而治之的效果。
[0080]
假设能得到满足(4)-(11)所有约束条件的可行路径集为r，其中(i，k)∈r，表示第i条可行路径使用第k种类型的车车辆。则问题可以转化为从该可行路径集中选择若干个(i，k)组合组成一个可行解且使模型的目标函数值最小。
[0081]
更进一步地，所述路径优化主问题满足以下关系式：
[0082][0083]
[0084]
p
ij
∈{0，1}
ꢀꢀꢀꢀ
(14)；
[0085]
θi≥0
ꢀꢀꢀꢀ
(15)；
[0086]
其中，θi表示模型选择可行路径i的系数；p
ij
为表示在可行路径i中含有站点j的零一变量，若含有则p
ij
取1，否则取0；ci表示第i条可行路径的能耗；
[0087]
目标函数(12)表示选择合适的可行路径组合以最小化总能耗；约束(13)表示每个站点j都至少被经过一次，需要注意的是，这里的站点j已经排除了那些没有乘客的站点，所以任意一个站点j的乘客数量都是大于0的。由于可行路径集组合数量较大，因此本发明实施例采用列生成法迭代地求解定价子问题，以加入有效列(i，k)，从而对主问题进行优化。
[0088]
从上述模型可以看出，子问题是k个带有资源约束的初等最短路径问题(elementary shortest path problem with resource constraints，espprc)，每一个问题所求的最短路径都必须满足容量约束，且每个站点只能经过一次，只有使得其目标函数值小于0的可行路径才能作为新的列加入主问题中进行迭代，以改善主问题的目标函数值。
[0089]
设πj对应主问题中约束(13)的对偶变量值；d
ij
为站点i到站点j的能耗；x
ij
表示车辆是否从站点i行驶至站点j，如果是则x
ij
取1，否则取0；其中定价操作是根据πj子问题中每条弧的能耗成本，修正公式如下：
[0090][0091]
所述资源优化子问题满足以下关系式：
[0092][0093][0094][0095][0096][0097][0098]
其中，目标函数(17)表示最小化行驶总成本；约束(18)表示可行路径不得超过第k种车型的最大载客量；约束(19)-(21)是为了保证有向图内流平衡，所有路径都会以车辆统一放置点0为起点，并以指定目的地n+1为终点，且该路径内不会出现子回路。那么可以得到检验数(reduced cost)为：
[0099][0100]
根据改进单纯形法原理，将检验数小于0的这一列加入到主问题模型，能改进当前主问题的目标值。
[0101]
s3、根据预设初始解求解算法，计算所述路径规划数学模型的初始解，并根据所述初始解初始化分支定价问题树，使所述初始解作为所述分支定价问题树的根节点。
[0102]
步骤s3的目的是构造输出一个足够优秀的初始解供精确式阶段进行进一步求解。
[0103]
更进一步地，步骤s3中的所述预设初始解求解算法，包括并行蚁群算法和变邻域搜索算法。
[0104]
更进一步地，步骤s3中，所述根据预设初始解求解算法，计算所述路径规划数学模型的初始解的步骤，还包括步骤：
[0105]
根据预设初始解改进方法，对所述初始解进行处理，所述预设初始解改进方法包括状态压缩动态规划法和混合整数规划法。
[0106]
更进一步地，步骤s3包括以下子步骤：
[0107]
s31、初始化剩余站点集合s和初始路径集合t，其中s为所有到指定目的地的乘客数非零的站点集合，t为空集，利用所述并行蚁群算法对所述剩余站点集合s进行计算，得到最佳路径，并将所述最佳路径放入所述初始路径集合t，同时将所述最佳路径中的站点从所述剩余站点集合s移出，重复上述步骤直到所述剩余站点集合s为空集。
[0108]
具体的，所述并行蚁群算法的步骤如下：
[0109]
s311、初始化剩余站点集合s和初始路径集合t，其中s为所有到指定目的地的乘客数非零的站点集合，t为空集；
[0110]
s312、判断s是否为空集，如果是则输出初始路径集合t，程序结束，否则转步骤s313；
[0111]
s313、初始化蚁群算法参数；
[0112]
s314、随机选取s中的站点放置蚂蚁；
[0113]
s315、根据信息素浓度，对每只蚂蚁进行轮盘赌，选择下一个站点；
[0114]
s316、判断是否还有站点可选，如果还有则转步骤s315，否则转步骤s317；
[0115]
s317、更新各站点间的信息素浓度；
[0116]
s318、评价每只蚂蚁，更新最佳路径；
[0117]
s319、判断是否到达最大迭代次数，如果到达最大迭代次数，则转步骤s3110，否则转步骤s314；
[0118]
s3110、将最佳路径加入集合t，并将最佳路径中的站点从s中移除，然后转步骤312。
[0119]
所述并行蚁群算法需要设定的参数包括信息素、路径编码和解码评价规则，并且，本发明实施例中使用多线程技术对算法进行了加速，对于信息素参数：
[0120]
设τ
ij
(t+1)为第t+1次循环后站点i到站点j的信息素含量；ρ为信息素挥发因子；为新增信息素含量，即m只蚂蚁在站点i到站点j的路径上留下的信息素总和。则信息素的更新公式可以表达如下：
[0121][0122]
在构建路径编码时，蚂蚁通过当前信息素浓度，按照一定概率选择下一个要到达的城市，设i和j分别为起点和终点，τ
ij
(t)为时间t时，从站点i到站点j的信息素浓度，ak为
第k只蚂蚁的尚未访问的邻接节点的集合，p
kij
代表第k只蚂蚁从站点i行驶到站点j的概率，η
ij
表示i和j两点间距离的倒数，综上，概率的计算规则可以表达如下：
[0123][0124]
而对于解码评价规则，设当前使用的汽车的最大载客量为c，pi为编码中第i个位置所代表的站点的乘客数，则解码流程可如下表示：
[0125]
步骤1：初始化指针i＝1，人数p＝0，解码集合为l；
[0126]
步骤2：如果p+pi≤c，则转步骤3，否则转步骤4；
[0127]
步骤3：将i指针指向的编号对应的站点id加入解码集合l，i＝i+1，p＝p+pi，转步骤5；
[0128]
步骤4：i＝i+1，转步骤5；
[0129]
步骤5：判断i是否超出编码长度，如果超出则解码结束，否则转步骤2。
[0130]
图2给出了一个解码的示例，其中假设车的最大载客量为15，由编码{3、2、7、4、1、8、5、6}解码得到解码集合l＝{3、2、7、8、5}，然后在解码集合两端分别接上统一放置点s和指定目的地e即可获得一条可行路径{s、3、2、7、8、5、e}。
[0131]
通过解码得到可行路径之后，需要对其进行评价，由于该可行路径只是构成初始解的一部分，不能只拿它的总能耗作为评价准则，否则会造成求出来的可行路径都只经过一个站点。
[0132]
为此，本发明实施例综合考虑了可行路径的能耗和装载率两个因素，设可行路径长度为l，选用车型的百公里能耗为h，最大载客量为c，路径中搭载的人数为p，n为可控参数，n越大越偏向于选择装载率较高、载客数量较多的路径，本发明实施例取n＝2，建立如下的评价函数：
[0133][0134]
由于本问题中有多种车型，所以在评价解码时需要对每个车型都进行一次解码和评价，然后从中选出z最小的可行路径方案作为最后的解码和评价结果。
[0135]
s32、基于所述预设初始解改进方法，对所述初始路径集合t进行优化，得到第二路径集合t2。
[0136]
s33、利用所述变邻域搜索算法对所述第二路径集合t2进行优化计算，得到第三路径集合t3。
[0137]
变邻域搜索算法的基本流程如下：
[0138]
设mk为第k个邻域动作的最大迭代次数，n为邻域动作数，在vns框架下，采用最短路径解码器将序列转换为一个可行路径集合。
[0139]
最短路径解码器的工作流程如下：给定序列i＝{i1，i2，...，in}，可以构造出一个有向无环图g(v，e)，其中顶点集v＝{1，2，3，...，n，n+1}，顶点n+1是虚构的顶点。设为序列i的第k个元素对应站点的乘客数，c表示当前考虑车型的最大载客量。于是，边集e的构造规则如下，如果满足下述条件，则边(i，j)可以被构造：
[0140][0141]
而边(i，j)的成本做如下定义：
[0142][0143]
其中表示在关于序列i的有向无环图g中，从顶点i到顶点j所需要花费的成本；表示从起点s到序列i中的第i个元素对应站点的成本；表示从序列i中的第j-1个元素对应站点到指定目的地e的成本；表示从序列i的第i个元素对应的站点到序列i的第j个元素对应的站点的成本。
[0144]
于是，关于序列i的有向无环图g(v，e)构造完毕，该无环图称g为i的成本图，以上构造过程的节点图如图3所示。从g的构造可以看出，g中从顶点1到n+1的任何路径都对应着一个可行路径，其中每个边(i，j)代表将从i到j-1项的站点放在同一条可行路径中，故本问题的解决方案的总能耗成本就是从1到n-1的路径中所有边的成本之和。所以求解最小总能耗问题就转换成了求解从顶点1到顶点n-1的经典最短路径问题，这被证明可以在o(e+v)的时间内解决。本发明实施例采用spfa算法对该经典最短路径问题进行求解，在得到最短路之后，利用最短路的每一条弧还原出可行路径，例如弧9
→
5，不包括右端点，对应g中的9
→3→
4，再考虑统一放置中心和指定目的地，最终可行路径为s
→9→3→4→
e。而整条序列的评价值就是g中最短路问题的解值。
[0145]
而对于邻域动作算子，在使用邻域动作算子生成新序列时，本发明实施例规定只有当新序列对应的解优于原序列解时，才接受新序列。本发明实施例使用的邻域动作算子包括以下三种：
[0146]
bin-shuffle：更改两个随机选择的容器的相对位置，同时保留每个容器中元素的相对位置，如图4所示；
[0147]
bin-shake：更改随机选择的容器中元素的相对位置。更准确地说，所选容器中所有元素的顺序被随机改变为另一个顺序，如图5所示；
[0148]
bin-shuffle-shake：更改两个随机选择的容器的相对位置和每个容器中元素的相对位置。它结合了前两个邻域动作算子，如图6所示。
[0149]
s34、基于所述预设初始解改进方法，对所述第三路径集合t3进行优化，输出得到所述初始解。
[0150]
具体的，对于所述预设初始解改进方法，由于初始解中的可行路径是通过启发式算法求解得到的，对于每一条可行路径来说，其不一定是最优的，可能存在进一步优化的空间。例如，以s代表车辆统一停靠区域，e代表目的地，阿拉伯数字代表车辆中间经过的乘客上车点，通过变邻域搜索算法可能得到的一条可行路径为[s，1，3，2，e]，其路径如图7左所示，路线存在交叉，明显还可以优化；在经过状压dp或混合整数规划优化后的路径如图7右所示，优化后的路径为[s，1，2，3，e]。
[0151]
对于可行路径的优化，可以看作特殊的tsp问题，即从起点出发到达终点，且必须经过所有节点的问题。不难发现，该问题和tsp问题的差别仅仅在于最后一个中间节点是返
回起点还是必须到达指定终点，因此，对该问题，只需要将tsp问题中的最后一个中间节点到起点的距离看作最后一个中间节点到终点的距离，即可对其进行求解。
[0152]
本发明实施例对初始解进行处理的方法包括状态压缩动态规划法和混合整数规划法，其中，为了提高计算速度，在对一个可行路径进行改进时，会以节点数19为分界点，选用计算速度更快的算法进行求解，并且分情况采用状态压缩动态规划法和混合整数规划法的操作不仅使得初始解路径得到优化，并且在优化速度上也有所提升，并不同现有算法单一地采取一种方法进行优化甚至不优化。
[0153]
状态压缩动态规划法：由于可行路径的优化问题是特殊的tsp问题，因此它同样具有最优子结构。假设从起点i出发；v表示起点与所有中间节点的集合；d(i，v
′
)表示从节点i出发，经过v
′
中各个节点一次且仅一次，最后到达指定终点e的最短路径长度；c
ik
为节点i到节点k的路程长度；开始时，v
′
＝v-{i}；于是，动态规划的状态转移方程可定义为：
[0154]
d(i，v
′
)＝min{c
ik
+d(k，v
′‑
{k})}，k∈v
′ꢀꢀꢀꢀ
(29)；
[0155]
d(k，{})＝c
ke
(k≠i)
ꢀꢀꢀꢀ
(30)；
[0156]
可以看出，在状态转移的过程中，需要保存集合v
′
，如果用数组来存储集合中的节点，会有占用空间大，集合变更效率低的问题。又由于只需要存储集合v
′
中含有哪些点，不含有哪些点，而对于是否含有某个节点，只需要状态码0-1即可表示，所以这里可以使用二进制串来存储集合v
′
的信息，只需要一个整数即可完成状态转移，将集合状态压缩为一个整数，大大节省了内存占用。
[0157]
混合整数规划法：设节点总数为n，起点为s，终点为e，节点i到节点j的距离为d
ij
，01变量x
ij
表示是否选用节点i到节点j这条弧。于是，混合整数规划法模型可以表示如下：
[0158][0159][0160][0161][0162]ui-uj+nx
ij
≤n-1，1＜i≠j≤n
ꢀꢀꢀꢀ
(35)；
[0163]
x
ij
∈{0，1}，ui为实数
ꢀꢀꢀꢀ
(36)；
[0164]
目标函数(31)表示最小化路径总长度；约束(32)表示变量矩阵对角线上的元素必须等于0；约束(33)表示变量矩阵每一行之和为1；约束(34)表示变量矩阵每一列之和为1；约束(35)是为了消除子回路。
[0165]
根据上面的约束，如果节点i到节点j的弧被选用了，那么就会有x
ij
＝1，此时约束(35)就变为u
i-uj≤-1，即ui≥ui+1，也就意味着沿着路线往下走u值是单调递增的，假设存在子回路[2，4，6，2]，那么就有u2≥u6+1≥u4+2≥u2+3，显然u2≥u2+3是矛盾的，故在约束(35)的作用下子回路不可能存在。图8展示了含有与不含有子回路的路径示意图。
[0166]
s4、从所述分支定价问题树取出头节点，进行列生成，对所述资源优化子问题进行
求解，其中，判断对应的所述路径优化主问题的解是否为整数解，若是，则更新所述分支定价问题树的上界，并将对应的所述路径优化主问题的解进行剪枝；若否，则基于对应的所述路径优化主问题的解的弧值构建所述分支定价问题树的分支节点。
[0167]
步骤s4的目的是将上一阶段输出的初始解进行进一步求解，最终输出结果即为完整的车型选择车辆路径方案。
[0168]
更进一步地，步骤s4中，从所述分支定价问题树取出头节点，进行列生成，对所述资源优化子问题进行求解的方法包括启发式spfa算法和pulse算法。
[0169]
更进一步地，步骤s4中，更新所述分支定价问题树的上界，并将对应的所述路径优化主问题的解进行剪枝的策略，包括不可行剪枝策略、边界剪枝策略和回滚剪枝策略。
[0170]
具体的，分支定价问题的求解流程如图9所示，其描述如下：
[0171]
第0步：初始化。求解原问题对应的定义在初始列集合并且不含整数约束的子问题，将该子问题的解作为b&p树的根节点，放入当前需要分支的节点列表。当前迭代次数初始化为如果求得该子问题的整数可行解，则选择其中最优的解作为原问题当前最优解对应目标函数值作为原问题当前最优目标函数值否则，令
[0172]
第1步：算法停止。如果当前需要分支的节点列表还包含节点元素，则按照一定策略选择一个节点，记作进入第2步。如果当前需要分支的节点列表为空，则算法停止。若存在一个当前最优解则它就是最优解；否则，该模型不可行；
[0173]
第2步：线性松弛。求解对应节点子问题的线性规划松弛问题；
[0174]
第3步：更新当前最优解。如果线性松弛问题最优解满足0-1整数约束，并且对应目标函数值比原问题当前最优解得到的更优，则更新原问题当前最优解和当前最优目标函数值，令
[0175]
第4步：列生成。将第2步中受限主问题得到的最优对偶变量代入到定价子问题中进行求解，其中，对每种车型求一次espprc，将所有检验数为负数的列加入主问题方案集合，如果存在满足条件的新列，则令返回第2步；否则，当前线性松弛问题的解就是该节点子问题的最优解；
[0176]
第5步：基于最优解可行性的分支终止条件判断。如果当前节点子问题的线性松弛问题最优解不可能满足该分支下的整数约束，则不可能根据继续分支得到原问题整数解。因此，终止这个分支，令返回到第1步；
[0177]
第6步：基于目标值上下界的分支终止条件判断。对于目标函数最小化问题，如果该线性松弛问题的当前最优目标函数值的下届为则不可能根据继续分支改进原问题当前最优解。因此，终止这个分支，令返回到第1步；
[0178]
第7步：基于线性松弛问题整数解的分支终止条件判断。如果该线性松弛问题的最优解满足原问题中的所有0-1整数约束，则解是该分支下的最优整数解。所以，终止
这个分支，令返回到第1步；
[0179]
第8步：分支。在最后的线性松弛问题的最优解中，采取基于弧的分支策略进行分支，得到两个规划问题，将他们添加到需要分支的节点列表中。然后，令返回到第1步。
[0180]
在求解定价子问题时，如果每次都要用精确算法将子问题求到最优解，会导致求解时间比较长，收敛较慢。为了加快收敛速度，本发明实施例在求解子问题时，首先采取启发式spfa算法进行求解，该算法平均求解时间在1ms以内，并且可以得到较好解；如果启发式方法没有得到reducedcost为负数的可行解，则再调用pulse精确算法进行求解。
[0181]
其中，本发明实施例在实施时在spfa算法的基础上做了一点改动，即加入人数记录数组对每一节点的出队入队造成的人数变动进行记录，如果发现节点i入队会造成人数超载，则i不可入队，从而达到处理载客量约束的作用。对于子回路约束，只需要每个节点入队次数，并限制每个节点的入队次数必须小于等于1即可。
[0182]
另外，pulse算法在搜索过程中不一定要搜索完所有可行路径找出最优解，为了加快收敛，本发明实施例设置了一个参数n，pulse算法在搜索过程中会将reducedcost为负数且在mp模型中不存在的列加入最短路径集t，当t的长度大于等于n时，pulse算法即可结束，否则需要找出最优解为止。
[0183]
本发明实施例使用的三种剪枝策略如下：
[0184]
不可行剪枝策略(infeasibility pruning)：在pulse过程到达任一点时，不可行剪枝策略会判断加入该点是否会构成环、是否会超出容量约束，若有任意一条违背，就会停止当前pulse过程；
[0185]
边界剪枝策略(bounds pruning)：设当前pulse过程到达站点i，当前成本消耗为c，当前载客量为p，当前考虑车型的最大载客量为q，则剩余载客量为以剩余载客量从站点i到达终点的最低花费为当前最优解成本为lu，如果满足不等式c+lc≥lu，则说明该路径继续扩展下去也不会产生比当前最优解更好的解，故路径可以被剪枝；
[0186]
回滚剪枝策略(rollback pruning)：假设pulse过程当前点为点i，接下来到达点n，回滚剪枝策略会先回退到点i的前驱节点j，评估从点j直接到点n是否是更好的选择，如果是，那么当前路径可以被剪枝。设c
ij
为点i到点j所需要花费的成本，则回滚剪枝条件的数学表达式如下：
[0187]cji
+...+c
qn
≥c
jn
，q为n的前驱节点
ꢀꢀꢀꢀ
(37)。
[0188]
本发明实施例的步骤s4中回滚剪枝示意图如图10所示。
[0189]
步骤s4中同样进行了多线程设计，在定界过程需要在不同资源约束情况进行pulse，其中，不同资源约束之间的脉冲过程是相对独立的，故可以利用多线程技术对不同资源约束情况同时进行pulse过程，这样可以大幅提高定界过程的速度。
[0190]
s5、判断所述分支定价问题树是否为空，若否，迭代至步骤s4；若是，则输出所述路径优化主问题的解作为路径规划优化结果。
[0191]
分支定价算法的一个关键部分即为制定合适的分支策略以求得整数解。常规的分支策略是基于变量的，即在分支树的左侧令最优解中不能出现可行路径r，在分支树的右侧令最优解中必须包含可行路径r。这样就需要将可行路径r从左侧分支树的主问题中删除，而在接下来的左侧分支树的子问题的计算中，就需要防止被删除的可行路径r再次由于reduced cost小于0作为基列加入主问题，这样会使得子问题求解变得更加复杂，左子树的定价子问题的复杂度大幅度提高，就会造成分支树的极不平衡，降低分支搜索效率，故这种常规的基于变量的分支策略并不适用于分支定价算法。
[0192]
为此，本发明十四合理采用分支定价算法用于求解车辆路径规划路径时的标准分支策略，即基于弧的分支策略。
[0193]
在基于弧的分支策略中，首先把基于变量的分数解转化为与其对应弧的分数值zh，其计算公式如下，其中θi表示第i条可行路径的分数解值，y
ih
表示第i条可行路径中是否含有弧h，如果有则为1，否则为0，h为弧的全集。
[0194][0195]
优先选择弧值最接近0.5的弧进行分支，直至找到最优整数解。分支后需要对左右子树的已有路径集合进行一些处理，假设根据弧值选择了弧h，那么就存在左右两个分支，设弧h为节点i到节点j的弧，则左分支约束：如果可行路中存在节点i，则节点i的后继节点必须为节点j，右分支约束：如果可行路中存在节点i，则节点i的后继节点不能为节点j。在已有的路径集中删除与约束相悖的路径后，再继续分支定价的迭代。
[0196]
采用基于弧的分支策略可以提高定界效率，加快寻优速度。下面是主要分支步骤：
[0197]
步骤1：初始化搜索树s，加入根节点；
[0198]
步骤2：在搜索树s中选取一个节点n，用节点n的信息初始化分支定价问题模型；
[0199]
步骤3：求解分支定价问题模型，得到解x；
[0200]
步骤4：如果解x为整数解则转步骤5，否则转步骤6；
[0201]
步骤5：将整数解x与当前上界进行比较，如果小于上界，则更新上界值，并且根据新的上界值对搜索树进行剪枝，转步骤7；
[0202]
步骤6：如果小数解小于当前的上界，则根据上述基于弧的分支策略选择一条弧进行分支，并删除当前节点，将分支节点加入搜索树，否则无需进行分支操作；
[0203]
步骤7：如果搜索树s不为空，则转步骤2，否则转步骤8；
[0204]
步骤8：当前的上界值即为最优整数解。
[0205]
在本发明实施例中，由于问题中存在多种车型，不同车型的载客量和单位能耗均不同，故定价子问题需要对不同车型都求一次espprc，显然，不同车型之间的求解是完全独立的，因此可以采用并行计算的方式，来大大缩短定价子问题的计算时间。
[0206]
本发明所达到的有益技术效果，在于提出了一种基于sp模型的启发式精确式两阶段路径规划优化方法，该方法把含有大量变量和约束的混合整数模型分解成一个基于路径的主问题和一个带有资源约束的最短路径子问题，以达到分而治之的效果，并且在求解定价子问题时算法采取并行计算，大幅节省不同车型的求解时间，相比传统人工计算的方法，不依赖调试人员对算法参数的调整，求解速度更快，计算结果更可靠，求解的稳定性也更高。
[0207]
本领域普通技术人员可以理解实现上述实施例方法中的全部或部分流程，是可以通过计算机程序来指令相关的硬件来完成，所述的程序可存储于一计算机可读取存储介质中，该程序在执行时，可包括如上述各方法的实施例的流程。其中，所述的存储介质可为磁碟、光盘、只读存储记忆体(read-only memory，rom)或随机存取存储器(random access memory，简称ram)等。
[0208]
需要说明的是，在本文中，术语“包括”、“包含”或者其任何其他变体意在涵盖非排他性的包含，从而使得包括一系列要素的过程、方法、物品或者装置不仅包括那些要素，而且还包括没有明确列出的其他要素，或者是还包括为这种过程、方法、物品或者装置所固有的要素。在没有更多限制的情况下，由语句“包括一个
……”
限定的要素，并不排除在包括该要素的过程、方法、物品或者装置中还存在另外的相同要素。
[0209]
通过以上的实施方式的描述，本领域的技术人员可以清楚地了解到上述实施例方法可借助软件加必需的通用硬件平台的方式来实现，当然也可以通过硬件，但很多情况下前者是更佳的实施方式。基于这样的理解，本发明的技术方案本质上或者说对现有技术做出贡献的部分可以以软件产品的形式体现出来，该计算机软件产品存储在一个存储介质(如rom/ram、磁碟、光盘)中，包括若干指令用以使得一台终端(可以是手机，计算机，服务器，空调器，或者网络设备等)执行本发明各个实施例所述的方法。
[0210]
上面结合附图对本发明的实施例进行了描述，所揭露的仅为本发明较佳实施例而已，但是本发明并不局限于上述的具体实施方式，上述的具体实施方式仅仅是示意性的，而不是限制性的，本领域的普通技术人员在本发明的启示下，在不脱离本发明宗旨和权利要求所保护的范围情况下，还可做出很多形式用等同变化，均属于本发明的保护之内。

技术特征：
1.一种基于sp模型的两阶段路径规划的优化方法，其特征在于，所述方法包括以下步骤：s1、构建关于运营成本的路径规划数学模型；s2、基于dantzig-wolfe分解方式，将所述路径规划数学模型分解为路径优化主问题和资源优化子问题；s3、根据预设初始解求解算法，计算所述路径规划数学模型的初始解，并根据所述初始解初始化分支定价问题树，使所述初始解作为所述分支定价问题树的根节点；s4、从所述分支定价问题树取出头节点，进行列生成，对所述资源优化子问题进行求解，其中，判断对应的所述路径优化主问题的解是否为整数解，若是，则更新所述分支定价问题树的上界，并将对应的所述路径优化主问题的解进行剪枝；若否，则基于对应的所述路径优化主问题的解的弧值构建所述分支定价问题树的分支节点；s5、判断所述分支定价问题树是否为空，若否，迭代至步骤s4；若是，则输出所述路径优化主问题的解作为路径规划优化结果。2.如权利要求1所述的基于sp模型的两阶段路径规划的优化方法，其特征在于，所述路径规划数学模型满足以下关系式：径规划数学模型满足以下关系式：径规划数学模型满足以下关系式：径规划数学模型满足以下关系式：径规划数学模型满足以下关系式：径规划数学模型满足以下关系式：c
kij
＝d
ij
δ
k
；y
ij
≥0，i≠j＝(0，...，n)；x
kij
∈{0，1}，i≠j＝(0，...，n)，k＝(1，...，t)；其中，t表示车型数目，q
k
表示车型k的最大载客量，p
j
表示第j个站点的乘客数量，c
kij
表示第k个车型从站点i行驶至站点j的能耗，为零一变量，取值1表示第k种车型从站点i行驶至站点j，0表示车辆统一放置中心，y
ij
表示从站点i到站点j的乘客装载量。3.如权利要求2所述的基于sp模型的两阶段路径规划的优化方法，其特征在于，所述路径优化主问题满足以下关系式：
p
ij
∈{0，1}；θ
i
≥0；其中，θ
i
表示模型选择可行路径i的系数；p
ij
为表示在可行路径i中含有站点j的零一变量，若含有则p
ij
取1，否则取0；c
i
表示第i条可行路径的能耗；所述资源优化子问题满足以下关系式：所述资源优化子问题满足以下关系式：所述资源优化子问题满足以下关系式：所述资源优化子问题满足以下关系式：所述资源优化子问题满足以下关系式：所述资源优化子问题满足以下关系式：4.如权利要求3所述的基于sp模型的两阶段路径规划的优化方法，其特征在于，步骤s3中的所述预设初始解求解算法，包括并行蚁群算法和变邻域搜索算法。5.如权利要求4所述的基于sp模型的两阶段路径规划的优化方法，其特征在于，步骤s3中，所述根据预设初始解求解算法，计算所述路径规划数学模型的初始解的步骤，还包括步骤：根据预设初始解改进方法，对所述初始解进行处理，所述预设初始解改进方法包括状态压缩动态规划法和混合整数规划法。6.如权利要求5所述的基于sp模型的两阶段路径规划的优化方法，其特征在于，步骤s3包括以下子步骤：s31、初始化剩余站点集合s和初始路径集合t，其中s为所有到指定目的地的乘客数非零的站点集合，t为空集，利用所述并行蚁群算法对所述剩余站点集合s进行计算，得到最佳路径，并将所述最佳路径放入所述初始路径集合t，同时将所述最佳路径中的站点从所述剩余站点集合s移出，重复上述步骤直到所述剩余站点集合s为空集；s32、基于所述预设初始解改进方法，对所述初始路径集合t进行优化，得到第二路径集合t2；s33、利用所述变邻域搜索算法对所述第二路径集合t2进行优化计算，得到第三路径集合t3；
s34、基于所述预设初始解改进方法，对所述第三路径集合t3进行优化，输出得到所述初始解。7.如权利要求6所述的基于sp模型的两阶段路径规划的优化方法，其特征在于，步骤s4中，从所述分支定价问题树取出头节点，进行列生成，对所述资源优化子问题进行求解的方法包括启发式spfa算法和pulse算法。8.如权利要求7所述的基于sp模型的两阶段路径规划的优化方法，其特征在于，步骤s4中，更新所述分支定价问题树的上界，并将对应的所述路径优化主问题的解进行剪枝的策略，包括不可行剪枝策略、边界剪枝策略和回滚剪枝策略。

技术总结
本发明属于物流调度优化技术问题领域，尤其涉及一种基于SP模型的两阶段路径规划的优化方法。本发明提出的方法把含有大量变量和约束的混合整数模型分解成一个基于路径的主问题和一个带有资源约束的最短路径子问题，以达到分而治之的效果，并且在求解定价子问题时算法采取并行计算，大幅节省不同车型的求解时间，相比传统人工计算的方法，不依赖调试人员对算法参数的调整，求解速度更快，计算结果更可靠，求解的稳定性也更高。求解的稳定性也更高。求解的稳定性也更高。


技术研发人员：陈壮耿 王孙康弘 姚绍文 魏丽军 刘强
受保护的技术使用者：广东工业大学
技术研发日：2023.03.20
技术公布日：2023/8/14