本发明属于车辆路径规划领域，尤其是涉及一种基于拉格朗日松弛算法的双层车辆路径规划方法。
背景技术：
1、城市交通枢纽作为城市交通系统的关键站点，其连接性和服务水平对整个城市交通体系至关重要。促进综合客运枢纽旅客联程运输高质量发展，开发“一次购票、一次支付、一码通行”服务产品，有利于提升交通枢纽的接驳效率和服务质量。为此，本发明提出了一种定制巴士结合网约车拼车的新型接驳模式。
2、定制巴士和网约车拼车各具有独特的优势，协同运营可以充分发挥两者的优点，实现资源的最大化利用和运输成本的优化，减少环境污染和碳排放，推动城市公共交通的可持续发展。定制巴士是一种按需响应的公共交通运营方式，具有精准高效、方便快捷以及环保低碳等优点，符合当前“互联网+大数据+共享”的智慧交通发展趋势，成为满足交通枢纽出行需求的有力手段。然而，交通枢纽乘客需求量大、分布复杂，定制巴士座位利用率不稳定、覆盖面有限等缺点也不可忽视。相比之下，网约车拼车则更具灵活性，能够解决居民出行“最后一公里”难题，满足乘客从交通枢纽到具体目的地“门对门”的个性化需求。定制巴士适合长途、高乘载需求，而网约车拼车适用于短途、个性化的出行需求。通过发展定制巴士与网约车联程服务模型，有助于减少车辆空驶率，提高整体经济效益，实现更灵活、高效的城市交通枢纽接驳服务。
技术实现思路
1、本发明的目的是提供一种基于拉格朗日松弛算法的双层车辆路径规划方法，基于车辆联程运输理念，提出一种面向机场、高铁站等综合客运枢纽接驳的定制巴士结合网约车拼车联程服务模式，以保证服务效率的同时，提供高效、低碳的“门对门”服务。
2、为实现上述目的，本发明提供一种基于拉格朗日松弛算法的双层车辆路径规划方法，包括以下步骤：
3、s1、根据订单预约信息，包括订单始发地、目的地、期望上车时间和期望下车时间，构建订单需求数据集；
4、s2、根据订单需求数据集，通过轮廓系数法确定定制巴士停靠站点数量，对订单目的地进行k-means聚类分析，确定定制巴士停靠站点；对交通枢纽站点、定制巴士停靠站点、网约车服务站点以及虚拟终点设置站点编号，构建定制巴士-网约车服务网络；
5、s3、根据服务网络站点坐标，构建站点距离矩阵、时间矩阵及成本矩阵，确定定制巴士与网约车路径协同优化的目标函数和约束条件，其中，所述目标函数是最大化平台的运营收益，所述约束条件包括：需求分配约束、容量限制约束、车辆流平衡约束、订单流平衡约束以及服务时间窗约束；
6、s4、根据所述目标函数和约束条件，建立混合整数线性规划模型；
7、s5、设计基于拉格朗日松弛的启发式算法对模型进行求解，引入拉格朗日乘子松弛难约束，将原问题拆分为两个不含复杂约束的子问题，包括子问题1和子问题2，采用次梯度算法更新乘子，迭代获取原问题的上下界，直到满足终止条件，输出定制巴士线路、网约车线路以及订单指派方案。
8、优选的，s1具体包括：
9、考虑一组订单集合p，定义订单的索引为p，其目的地的横纵坐标分别为xp和yp，订单的总数为|p|；平台接受订单p的收益为rp，每个订单的始发地和目的地分别为o(p)和d(p)；订单的期望服务时间窗为[0,ltp]，其中，初始化所有订单的出发时间为0，ltp表示订单p期望抵达目的地d(p)的时间；此外，定义定制巴士和网约车集合分别为k1和k2，令车辆集合k＝k1∪k2，将车辆的索引定义为k和l，k,l∈k；将调用车辆k产生的固定成本定义为ck，将车辆的容量上限设置为wk。
10、优选的，s2的具体过程如下：
11、s2.1、通过轮廓系数法确定定制巴士停靠站点数量n，站点i的轮廓系数的计算公式如下：
12、
13、其中ai是站点i在同簇内到其它点的平均距离，bi是站点i到最近不同簇中其它点的平均距离。计算所有点的轮廓系数均值，即获得聚类结果总的轮廓系数。选取总轮廓系数最大的聚类中心数量作为确定的n值；
14、s2.2、根据步骤s2.1，给定定制巴士站点的数量n，任选n个点作为初始质心，寻找质心确定定制巴士停靠的站点；
15、s2.3、将每个订单目的地所在站点指派到最近的质心，形成n个簇；
16、s2.4、以最小化成本函数j为目标，重新计算每个簇的质心，更新定制巴士停靠站点位置，成本函数的计算公式如下：
17、
18、其中，x(i)表示订单目的地所在站点；c(i)表示x(i)当前被分配的簇质心索引；μk为簇质心，定制巴士站点位置；表示x(i)当前被分配的簇质心，|p|为订单的总数；
19、s2.5、重复步骤s2.3和s2.4，直到簇质心不发生变化；
20、s2.6、通过以上步骤s2.1-s2.5的k-means聚类算法确定定制巴士停靠站点后，对交通枢纽站点、定制巴士停靠站点、网约车服务站点以及虚拟终点设置站点编号；考虑一个单起点和多个目的地的定制巴士与网约车双层车辆路径拓扑网络g＝(h,a)，定义h为网络站点的集合，h＝h1∪h2∪{v}，其中，h1＝{0,1,…,n}表示定制巴士站点集合，{0}表示交通枢纽站点，为定制巴士的始发点，h2＝{n+1,n+2,…,n+|p|}表示网约车服务站点集合，{v}表示虚拟终点集合；定义站点的索引为i,i∈h，将拓扑网络上站点i的道路连接索引定义为站点j,j∈h，站点之间连通的道路定义为(i,j),(i,j)∈a，a为网络边的集合。
21、优选的，s3具体包括：
22、s3.1、根据站点坐标构建距离矩阵，各站点之间的距离由欧氏距离表示；设两点坐标分别为(x1,y1)、(x2,y2)，则两点间距离由式计算。将计算结果以数组形式进行储存，记数组为d，数组元素为dij，表示车辆从i行驶到j的距离，其中每个站点到达虚拟终点的距离均设置为0；
23、s3.2、根据所构建的距离矩阵，计算时间矩阵和成本矩阵；由于不同车型单位距离行驶时间和行驶成本存在一定差异，故分别计算不同车辆旅行的时间矩阵和成本矩阵；以车辆k的单位距离行驶时间乘以距离矩阵计算出车辆的行驶时间矩阵，并将计算结果以数组形式进行储存，记为tk，数组元素为表示车辆k从i行驶到j的时间；以车辆k的单位距离行驶成本乘以距离矩阵得到车辆的运营成本矩阵，记为ck，数组元素为表示车辆k从i行驶到j的运营成本；
24、s3.3、确定定制巴士与网约车路径协同优化的目标函数和约束条件；目标函数是最大化平台的运营收益；约束条件包括：需求分配约束，确保每个订单被合理指派到服务车辆；容量限制约束，确保乘客数量不超过车辆的容量限制；车辆流平衡约束和订单流平衡约束，保证乘客准确、不间断地抵达目的地；服务时间窗约束，保证乘客在期望时间范围内到达目的地。
25、优选的，s4中根据所述目标函数和约束条件，建立混合整数线性规划模型的具体表达式如下：
26、
27、s.t.
28、
29、
30、
31、
32、
33、
34、
35、
36、
37、
38、
39、
40、
41、
42、
43、
44、
45、
46、
47、
48、
49、
50、
51、
52、
53、
54、其中，{0}{v}分别为枢纽起点集合和虚拟终点集合；h1为定制巴士站点集合，包括枢纽起点集合{0}；h2为网约车服务站点集合，表示订单目的地站点集合；h为所有站点集合，h＝h1∪h2∪{v}，i,j表示站点索引；k1为定制巴士车辆集合；k2为网约车车辆集合；k为所有车辆集合，k,l表示车辆索引；p为订单集合，p表示订单索引；rp为平台接受订单p的收益；为车辆k在站点i,j之间行驶的成本；为车辆k在站点i,j之间行驶的时间；ck为调用车辆k产生的固定成本；wk为车辆k的最大容量；ltp为订单p期望抵达目的地d(p)的最晚时间；m为一个足够大的正数，决策变量为非负实数变量，表示车辆k访问站点i的时间，fk是二元变量，描述如下：
55、
56、
57、
58、
59、上述式(4.1)为目标函数，优化目标为最大化平台的运营利润，通过收益减去可变运营成本和固定运营成本表示；约束(4.2)-(4.3)是订单-车辆分配约束，保证一个订单至多由一辆定制巴士服务，订单一旦被巴士服务，就必须安排相应网约车服务；约束(4.4)是容量限制约束，限制载客数量不得超过车辆的容量上限；约束(4.5)-(4.9)和(4.10)-(4.15)分别是定制巴士和网约车拼车的路径优化约束，确保定制巴士及网约车服务线路规划连贯、合理；约束(4.16)-(4.17)是订单流约束，保证订单流准确、不间断地到达订单目的地；约束(4.18)-(4.22)是运行时间约束，其中，约束(4.18)-(4.19)计算车辆到达站点的时间，约束(4.20)-(4.21)确保乘客乘坐定制巴士抵达换乘点的时间等于在该点乘坐网约车的时间；约束(4.22)是右时间窗约束，保证乘客在期望下车时间前到达目的地；约束条件(4.23)-(4.27)定义了决策变量的取值范围。
60、优选的，s5中设计拉格朗日松弛算法求解数学规划模型的具体过程如下：
61、s5.1、将原规划问题的目标函数(4.1)转化为求解最小值的标准形式，等价为：
62、
63、引入拉格朗日乘子λp和分别松弛难约束(4.3)和(4.16)，将原问题拆分成两个不含复杂约束的子问题，包括子问题1和子问题2，原问题模型式(4.1)-(4.27)中，同时包含两种车型变量的耦合约束，包括(4.3)、(4.16)、(4.20)-(4.21)；引入拉格朗日乘子λp和分别将难约束(4.3)和(4.16)松弛至目标方程(5.1)中，消除约束(4.20)-(4.21)，实现两种车型变量之间的解耦，将原问题分解为两个不含复杂耦合约束的子问题，包括子问题1和子问题2，对应定制巴士路线规划和网约车拼车路线规划问题；
64、s5.2、基于当前拉格朗日乘子求解子问题，获取原问题下界；基于当前拉格朗日乘子取值，将已知参数带入两个子问题模型，利用cplex求解器求解；初始时，将拉格朗日乘子设定为全零数组；依次求解两个子问题，将子问题1输出的定制巴士抵达站点时刻作为子问题2中网约车服务的初始时刻输入，再求解子问题2；根据对偶松弛理论，对于任意给定的拉格朗日乘子向量，求解松弛模型所得的最优值作为原模型的下界；获取子问题1和子问题2求解结果的目标函数值并求和，如果求和的值大于原问题的下界lb，则更新为原问题的当前下界值；需要注意的是，步骤s5.1分解原问题时剔除了耦合约束(4.20)-(4.21)，而约束(4.20)-(4.21)的作用是准确完成定制巴士-网约车换乘点的时刻运算，确保乘客乘坐定制巴士抵达换乘点的时间等于在该点乘坐网约车的时间；通过优先求解子问题1，将子问题1输出的定制巴士到达站点时刻作为子问题2中网约车服务的初始时刻输入，再求解子问题2，以满足约束(4.20)-(4.21)；
65、s5.3、对步骤s5.2所输出的结果进行可行化操作得到原问题的上界；由于原问题的可行域被扩大，拉格朗日松弛得到的下界解可能违背部分松弛约束，因此，对步骤s5.2输出的结果进行可行化操作得到原问题的上界；
66、s5.4：采用次梯度迭代算法对拉格朗日乘子进行更新；
67、s5.5：判断是否满足迭代终止条件，若满足，终止迭代；否则转至s5.2。
68、优选的，子问题1为定制巴士路线规划问题，对应的目标函数及约束条件如下：
69、
70、
71、
72、
73、
74、
75、
76、
77、
78、
79、
80、
81、
82、
83、
84、
85、
86、上述式(5.2)为子问题1的目标函数，是拉格朗日松弛问题目标函数中只包含定制巴士车型相关变量的部分；约束(5.3)是定制巴士订单分配约束，即一个订单至多由一辆定制巴士服务；约束(5.4)是定制巴士容量限制约束，限制载客数量不超过定制巴士容量；约束(5.5)-(5.9)是定制巴士路径优化约束，确保定制巴士服务线路规划连贯、合理；约束(5.10)是订单起点约束，保证被服务的订单从枢纽起点出发，订单流准确、不间断地到达订单目的地；约束(5.11)-(5.12)是定制巴士到达站点的时间运算；约束(5.13)-(5.17)定义了决策变量的取值范围；
87、子问题2为网约车拼车路线规划问题，对应的目标函数及约束条件如下：
88、
89、s.t.
90、
91、
92、
93、
94、
95、
96、
97、
98、
99、
100、
101、
102、
103、
104、
105、
106、上述式(5.18)为子问题2的目标函数，是拉格朗日松弛问题目标函数中只包含网约车车型相关变量的部分；约束(5.19)是网约车容量限制约束，限制载客数量不超过网约车容量；约束(5.20)-(5.25)是网约车拼车路径优化约束，确保网约车服务线路规划连贯、合理；约束(5.26)是订单流约束，保证网约车服务的订单流准确、不间断地到达订单目的地；约束(5.27)-(5.28)是网约车到达站点的时间运算公式；约束(5.29)是右时间窗约束，保证乘客在期望下车时间前到达目的地；约束条件(5.30)-(5.34)定义了决策变量的取值范围。
107、优选的，s5.3中对步骤s5.2所输出的结果进行可行化操作得到原问题的上界包括：分析s5.2求解结果发现，原问题拆分为定制巴士路线规划子问题和网约车拼车路线规划子问题之后，两个子问题的规划互不干扰，可能造成订单流的断裂，从而导致结果不可行；因此，将子问题1输出的订单到达定制巴士站点结果带入子问题2，作为子问题2中网约车拼车服务的订单起点，即可解决解不可行问题；根据求解结果计算原问题的上界，计算公式为：
108、
109、将当前可行化操作所得上界ub与历史最小上界ubmin比较，若低于历史最小上界，则更新并保存最小上界值ubmin，并存储本轮可行解作为最优规划结果；否则，当前上界为历史最小上界值，对应的当前上界ub＝ubmin。
110、优选的，s5.4中采用次梯度迭代算法对拉格朗日乘子进行更新的具体过程如下：
111、s5.4.1：明确拉格朗日对偶问题fld，理论研究表明拉格朗日松弛问题flr的目标函数为拉格朗日乘子的分段线性凸函数，且其最优目标函数值为原模型最优目标函数值的下界，可通过最大化该函数值以寻找更好的下界。简而言之，为了获得最逼近原问题最优解的下界，需要构造拉格朗日对偶问题fld：
112、
113、s5.4.2：将步骤s5.2中子问题1和子问题2求解的决策变量zpk和的值带入式(5.37)和(5.38)计算次梯度：
114、
115、
116、将第t次迭代的计算结果以数组形式进行储存，记数组为st，获得本轮次梯度，若st＝0，则拉格朗日算法终止；否则，继续s5.4.3；
117、s5.4.3：更新步长θt：
118、
119、其中ubt为当前上界值，lbt为当前下界值，st为当前次梯度，β取值为2；
120、s5.4.4：将本轮λp和以数组形式存储为λt，计算λt+1＝λt+θtst，更新拉格朗日乘子。
121、优选的，迭代终止条件包括：
122、(1)迭代次数不超过最大迭代次数iter_max；
123、(2)上下界gap为0，对应的上界值与下界值相等，ubt＝lbt；
124、(3)λt或目标函数值在规定步数内变化不超过给定值；
125、以上条件满足任意一条则终止算法迭代，输出当前可行上界解，得到定制巴士线路、网约车线路以及订单指派方案。
126、因此，本发明采用上述一种基于拉格朗日松弛算法的双层车辆路径规划方法，具有以下有益效果：
127、(1)本发明提出了定制巴士结合网约车拼车的新型联程服务模式，根据乘客个性化出行需求和出行时间，为乘客提供定制化联程服务，使乘客在机场、高铁站等客运枢纽接驳服务中享受更高的灵活性和便利性；
128、(2)本发明建立了一个以最大化运营收益为目标，综合考虑需求分配约束、容量限制约束、车辆流约束、订单流约束以及时间窗约束的混合整数线性规划模型，对系统进行整体优化，以更精准地规划双层车辆路径优化方案；
129、(3)本发明运用拉格朗日松弛算法求解模型，在保证结果准确性的基础上提升求解效率。首先，引入拉格朗日乘子松弛难约束，将原问题拆分为两个不含复杂约束的子问题求解，以次梯度算法更新乘子，迭代获取原问题上下界直到满足终止条件，最终输出最佳定制巴士线路、网约车线路以及订单指派方案。
130、下面通过附图和实施例，对本发明的技术方案做进一步的详细描述。
1.一种基于拉格朗日松弛算法的双层车辆路径规划方法，其特征在于，包括以下步骤：
2.根据权利要求1所述的一种基于拉格朗日松弛算法的双层车辆路径规划方法，其特征在于，s1具体包括：
3.根据权利要求2所述的一种基于拉格朗日松弛算法的双层车辆路径规划方法，其特征在于，s2的具体过程如下：
4.根据权利要求3所述的一种基于拉格朗日松弛算法的双层车辆路径规划方法，其特征在于，s3具体包括：
5.根据权利要求4所述的一种基于拉格朗日松弛算法的双层车辆路径规划方法，其特征在于，s4中根据所述目标函数和约束条件，建立混合整数线性规划模型的具体表达式如下：
6.根据权利要求5所述的一种基于拉格朗日松弛算法的双层车辆路径规划方法，其特征在于，s5中设计拉格朗日松弛算法求解数学规划模型的具体过程如下：
7.根据权利要求6所述的一种基于拉格朗日松弛算法的双层车辆路径规划方法，其特征在于，子问题1为定制巴士路线规划问题，对应的目标函数及约束条件如下：
8.根据权利要求7所述的一种基于拉格朗日松弛算法的双层车辆路径规划方法，其特征在于，s5.3中对步骤s5.2所输出的结果进行可行化操作得到原问题的上界；具体将子问题1输出的订单到达定制巴士站点结果带入子问题2，作为子问题2中网约车拼车服务的订单起点，重新求解子问题2，解决订单流断裂导致的解不可行问题；根据新的求解结果计算原问题的上界，计算公式为：
9.根据权利要求8所述的一种基于拉格朗日松弛算法的双层车辆路径规划方法，其特征在于，s5.4中采用次梯度迭代算法对拉格朗日乘子进行更新的具体过程如下：
10.根据权利要求9所述的一种基于拉格朗日松弛算法的双层车辆路径规划方法，其特征在于，迭代终止条件包括：
