一种基于大规模领域搜索的多场站校车路径求解方法

1.本发明属于校车路径规划技术领域，尤其涉及一种基于大规模领域搜索的多场站校车路径求解方法。


背景技术：

2.为中小学学生提供安全、高效的校车服务是教育主管部门的一项重要职能，也是教育发展面临的新要求。校车路径问题是在满足既定约束的条件下，合理地规划校车线路，将学生从乘车站点送到学校(或从学校送回乘车站点)，并达到特定目标的组合优化问题。校车路径规划是一项极其复杂的工作，涉及到学区道路状况、学生、学校以及校车等多种因素。受校车运营公司的资金配置、学生分布状况、道路等级等条件的影响，对校车场站的调度，能够减少校车数量，减少成本，更加符合实际应用的需求。
3.依据校车场站的数量，可以将校车分为单场站校车路径问题(single depot school bus routing problem,sdsbrp)和多场站校车路径问题(multiple depot school bus routing problem,mdsbrp)。在sdsbrp中，场站只有一个，要求校车在服务完学生之后，返回场站。在mdsbrp中，场站数量有多个，分为开放性mdsbrp和闭合mdsbrp两类。前者指校车在服务完学生之后，可以返回其他场站，后者则必须返回原场站。对校车路径问题进行定义时通常会做一些限定和抽象。假设某个学区内已有若干校车场站、若干所学校、若干个乘车站点、学生和道路网络等数据。某校车服务公司有一组容量和成本相同的校车车队停放在校车场站，每个乘车站点均有一定数量的乘车学生，这些学生可以由到达不同学校的学生组成。场站、学校、乘车站点等任意两个站点之间的运行距离和运行时间已知。基于以上假设，要求：校车从场站出发经过乘车站点并在学校开学时间内将学生送到学校，每个学生在乘车站点上车有最早时间和最晚时间的限制。目标是找到总成本最小的路径安排。
4.目前，主要有精确算法和启发式算法两类优化算法用于求解校车路径问题。但由于校车路径问题属于np难题，最优化算法在实际应用中有限，因此大多数研究致力于构造更高质量的启发式算法。校车路径问题自1969年提出后，学者便进行了大量的研究，其中以单场站sdsbrp的研究居多。mdsbrp要比sdsbrp更为复杂，求解程度也更加困难。虽然近年来对多场站的研究逐渐增多，但mdsbrp对于算法求解质量和求解效率仍然拥有较高的提升空间。本发明为构造更高质量的针对mdsbrp的启发式算法，考虑校车容量和学生最大乘车时间等多种问题特征，提出多场站运营模式下总成本最小的校车路径安排方案。


技术实现要素：

5.本发明针对上述mdsbrp存在的求解质量差的问题，提出一种基于大规模领域搜索的多场站校车路径求解方法，能够寻找多场站运营模式下总成本最小的校车路径安排方案，优化校车数量和运营里程。
6.为了实现上述目的，本发明采用以下技术方案：
7.一种基于大规模领域搜索的多场站校车路径求解方法，包括：
8.步骤1：构建mdsbrp模型的初始解：首先，针对每个学校，基于场站、目标学校为该学校的乘车站点、可用车型信息和最大乘车时间约束条件,使用广义插入法构造多条到达该学校的路径；然后，将针对每个学校构造的路径进行合并，即得到mdsbrp模型的初始解；
9.步骤2：使用lns算法，通过站点操作算子对站点完成局部搜索，在局部搜索过程中，采用多点移动的方式对局部优解完成扰动，得到局部最优解；
10.步骤3：针对得到的局部最优解，采用场站操作算子对其进行扰动操作，得到全局最优解；
11.步骤4：判断是否达到最大迭代次数，若否则重复步骤2和步骤3，若是则输出全局最优解、即最佳校车路径。
12.进一步地，所述步骤1包括：
13.步骤101：读取案例文件，获得包括场站集合d、乘车站点集合p

、车辆集合m和学校集合p-信息；
14.步骤102：将一个乘车站点和其所属学校组合成为一条路径；
15.步骤103:针对所有未插入到封闭环路上的站点，找到封闭环路内距离其最近的若干个站点，若环路内的所有站点的个数不足7个，则包含环路内所有的站点；
16.步骤104:随机选择一个不在环路中的站点，评估该站点顺时针插入和逆时针插入的成本，寻找能够以最小成本插入的位置并采用广义插入法进行站点插入；
17.步骤105：完成站点的插入后，更新所有站点的邻域，跳转到步骤103继续执行，直到所有的站点均已经加入到环路中；
18.步骤106：根据得到的包含场站、所有学生乘车站点和学校的封闭环路，应用以上拆分过程划分为单个路径；
19.步骤107：从场站集合d出发，顺序的访问环路中的站点，将站点加入到一条包含场站和学校的初始路径中；根据车辆容量，不断的将站点加入到路径中，同时移除环路中对应的站点；若违反车型容量约束或最大乘车时间约束，重新构造一条新的初始路径，跳转到步骤106继续执行，直到环路中不存在站点为止；
20.步骤108:将针对每个学校构造的路径进行合并，即得到mdsbrp模型的初始解。
21.进一步地，所述步骤1需要满足如下约束条件：
22.对场站的约束条件为：
23.l
ik
＝0，k∈m，确保从场站i出发或者回到场站i时车辆k上学生数量l
ik
为0；
24.对车辆的约束条件为：
25.s.t.∑
j∈v
x
ijk-∑
j∈v
x
jik
＝0,k∈m，其中v表示所有站点；x
ijk
表示车辆k是否经过站点i和站点j连接的弧，1表示经过，0表示不经过；x
jik
表示车辆k是否经过站点j和站点i连接的弧，1表示经过，0表示不经过；p＝p

∪p-；确保一辆车驶入站点后离开站点；
26.对学生所在站点和学校之间关系的约束条件：
27.t
ik
sti t
is(i)
≤t
s(i)k
，其中t
ik
表示车辆k经过站点i后累计的时间；sti表示站点i的服务时间，即上、下车时间间隔，i∈p；t
ij
表示站点i和站点j之间的行驶时间，i、j∈v，v＝p∪d表示所有站点；t
ik
表示车辆k经过站点i后累计的时间；限定校车必须先访问学生所在站点再访问对应的学校；
28.对车辆上学生数量的约束条件：
29.qi≤l
ik
≤qk,k∈m，保证车辆k经过站点i后的学生人数l
ik
大于等于站点i上车的学生人数qi，并且小于等于校车容量qk；
30.对车辆到达站点的时间约束条件：
31.ei≤ti≤li,k∈m，其中ei表示站点i的最早发车时间，i∈p；ti表示车辆到达站点i的最大行车时间；li表示站点i的最晚发车时间，i∈p；限制车辆到达任何站点的时间都必须满足时间窗要求。
32.进一步地，所述步骤2包括：
33.步骤201：使用swap(1，1)，shift(1，0)，swap(2，1)三种站点操作算子对站点进行局部搜索；swap(1，1)表示随机选择两条路径上的两个站点进行交换得到可行解；shift(1，0)表示随机选择某条路径上的一个站点，综合考虑所有其他路径看能否将此站点插入到可行位置构成可行解；swap(2，1)表示随机选择某条路径上连续的站点，然后与另外一条路径上一个站点进行交换，反复尝试执行直到得到一个可行解；
34.步骤202：记录局部搜索解sl，得到局部优解sb^，并进行更新；
35.步骤203：采用多点移动的方式对局部优解sb^进行扰动，输出局部最优解sb。
36.进一步地，所述步骤201包括：
37.步骤2011：使用创建领域节点列表方法创建节点j、即站点j的大小为size的领域节点列表；
38.步骤2012：获取领域节点列表中的节点k，创建记录此次移动的对象m，使用evaluate评估方法评估将节点j插入到节点k的移动是否满足约束，使用checkmove方法评估此次移动产生的新解是否能够接受，按照启发规则确定此次移动对象m是否比目前的最好的移动对象bestm更优，如果是则将当前移动对象m作为最好移动对象bestm；
39.步骤2013：依次搜索邻域节点列表中的每个节点，对每个节点进行步骤2012操作，确定j的最佳插入位置；
40.步骤2014：搜索结束，根据当前记录的最好移动对象bestm对点执行移动操作，操作成功，则节点j就会被永久移动，如果没有找到可行的移动位置或者移动失败，则结束。
41.进一步地，所述步骤3包括：
42.步骤301：输入局部最优解；
43.步骤302：对场站附近的站点采用destroy场站操作算子进行一定程度的破坏，然后采用对应的repair场站操作算子进行修复，闭合场站不破坏返回路线，开放场站破坏返回路线，重新生成新路线，并检测是否满足约束条件，确定是否接受解；
44.步骤303：记录局部搜索解，检测当前解是否优于当前局部最优解，若是，则通过当前解更新全局最优解。
45.进一步地，所述步骤302包括：
46.采用random destroy算子随机从当前解中移除一定比例的站点，采用worst destroy算子从当前解中移除引起目标函数增幅较大的站点；目标函数为：
[0047][0048]
其中p

为乘车站点集合，m为车辆集合，v表示所有站点，fk表示车辆k的固定成本，
vk表示车辆k的可变成本，d
ij
表示站点i和站点j之间的行驶距离；x
ijk
表示车辆k是否经过站点i和站点j连接的弧，1表示经过，0表示不经过；
[0049]
以最小化目标函数为优化目标，其中校车数量为第一优化目标，运营里程为第二目标。
[0050]
与现有技术相比，本发明具有的有益效果：
[0051]
本发明针对站点和场站分别采用了不同的算子进行搜索：针对站点采用了swap(1，1)，shift(1，0)，swap(2，1)三种站点操作算子完成邻域搜索；针对场站引入了扰动机制进行优化。本发明通过站点操作算子在路径间和路径内调整站点，扩展了邻域解的启发策略，通过在一组基准测试实例上测试了该算法的性能。lns对求解mdsbrp实例具备有效性和稳定性。通过在mdsbrp和sdsbrp中的测试，结果表明本发明提出的方法是有效的，无论在mdsbrp还是sdsbrp均取得不错的效果，能够提高解决方案的质量。通过mdsbrp和sdsbrp的比较，mdsbrp能够进一步减少所需校车数量和缩短行驶距离，进而节约校车服务成本。本发明方法计算效率高，稳定性好。
附图说明
[0052]
图1为本发明实施例一种基于大规模领域搜索的多场站校车路径求解方法的基本流程图；
[0053]
图2为本发明实施例swap(1，1)、shift(1，0)、swap(2，1)站点操作算子操作示意图；
[0054]
图3为本发明实施例场站操作算子操作示意图。
具体实施方式
[0055]
下面结合附图和具体的实施例对本发明做进一步的解释说明：
[0056]
如图1所示，本发明提出一种基于大规模领域搜索的多场站校车路径求解方法，将lns算法引入到多目标sbrp、即mdsbrp的求解，针对该问题设计了站点操作算子和场站操作算子。首先构造问题的初始解，而后分别执行站点操作和场站操作两个阶段。在不同的执行阶段，通过优化目标和启发策略确定领域搜索和解的接受规则。该算法包括初始解生成、扰动、局部搜索和接受规则四个基本步骤。该方法具体包括：
[0057]
步骤1：构建mdsbrp模型的初始解：根据场站、乘车站点、学校和车型等信息，采用插入算法，得到问题的初始解。初始解的构造包含单个学校的路径构造和路径合并两个阶段。首先，针对每个学校，基于场站、目标学校为该学校的乘车站点、可用车型信息和最大乘车时间约束条件,使用广义插入法(geni)构造多条到达该学校的路径；然后，将针对每个学校构造的路径进行合并，即得到mdsbrp模型的初始解；
[0058]
步骤2：使用lns算法，通过站点操作算子对站点完成局部搜索，在局部搜索过程中，采用多点移动的方式对局部优解完成扰动，得到局部最优解；
[0059]
步骤3：针对得到的局部最优解，采用场站操作算子对其进行扰动操作，得到全局最优解；
[0060]
步骤4：判断是否达到最大迭代次数，若否则重复步骤2和步骤3，若是则输出全局最优解、即最佳校车路径。
[0061]
进一步地，所述步骤1包括：
[0062]
步骤101：读取案例文件，获得包括场站集合d、(学生)乘车站点集合p

、车辆集合m和学校(站点)集合p-等信息；
[0063]
步骤102：将一个乘车站点和其所属学校组合成为一条路径；
[0064]
步骤103:针对所有未插入到封闭环路上的站点，找到封闭环路内距离其最近的若干个站点(站点数量介于2-7之间)，若环路内的所有站点的个数不足7个，则包含环路内所有的站点；
[0065]
步骤104:随机选择一个不在环路中的站点，评估该站点顺时针插入和逆时针插入的成本，寻找能够以最小成本插入的位置并采用广义插入法进行站点插入；
[0066]
步骤105：完成站点的插入后，更新所有站点的邻域，跳转到步骤103继续执行，直到所有的站点均已经加入到环路中；
[0067]
步骤106：根据得到的包含场站、所有学生乘车站点和学校的封闭环路，应用以上拆分过程划分为单个路径；
[0068]
步骤107：从场站集合d出发，顺序的访问环路中的站点，将站点加入到一条包含场站和学校的初始路径中；根据车辆容量，不断的将站点加入到路径中，同时移除环路中对应的站点；若违反车型容量约束或最大乘车时间约束，重新构造一条新的初始路径，跳转到步骤106继续执行，直到环路中不存在站点为止；
[0069]
步骤108:将针对每个学校构造的路径进行合并，即得到mdsbrp模型的初始解。
[0070]
进一步地，所述步骤1需要满足如下约束条件：
[0071]
满足对场站的约束条件l
ik
＝0,k∈m，确保从场站i出发或者回到场站i时车辆k上学生数量l
ik
为0；
[0072]
满足对车辆的约束条件s.t.∑
j∈v
x
ijk-∑
j∈v
x
jik
＝0,k∈m，其中v表示所有站点；x
ijk
表示车辆k是否经过站点i和站点j连接的弧，1表示经过，0表示不经过；x
jik
表示车辆k是否经过站点j和站点i连接的弧，1表示经过，0表示不经过；p＝p

∪p-；确保一辆车驶入站点后离开站点；
[0073]
满足学生站点和学校站点之间的关系t
ik
sti t
is(i)
≤t
s(i)k
，其中t
ik
表示车辆k经过站点i后累计的时间；sti表示站点i的服务时间，即上、下车时间间隔，i∈p；t
ij
表示站点i和站点j之间的行驶时间，i、j∈v，v＝p∪d表示所有站点；t
ik
表示车辆k经过站点i后累计的时间；限定校车必须先访问学生站点再访问对应的学校；
[0074]
满足车辆上学生数量的约束条件qi≤l
ik
≤qk,k∈m，保证校车上的学生数量不能超过校车容量。车辆经过站点i后的累积学生人数l
ik
大于等于站点i的学生人数qi，并且小于等于校车容量qk；
[0075]
满足对车辆到达站点的时间约束条件ei≤ti≤li,k∈m，其中ei表示站点i的最早发车时间，i∈p；ti表示车辆到达站点i的最大行车时间；li表示站点i的最晚发车时间，i∈p；限制车辆到达任何站点的时间都必须满足时间窗要求。
[0076]
进一步地，所述步骤2包括：
[0077]
步骤201：使用swap(1，1)，shift(1，0)，swap(2，1)三种站点操作算子对站点进行局部搜索；mdsbrp中移动的不是某个乘车站点，而是一个乘车站点及其对应学校组成的点
对。swap(1，1):随机选择两条路径上的两个节点进行交换得到可行解。此过程中路径和路径上的节点都是随机选择的，在交换过程中仅考虑第一个能够找到的可行解。如图2所示，两条路径上的点进行交换之后，得到两条新的路径。shift(1，0):随机选择某条路径上的一个节点，综合考虑所有其他路径看能否将此节点插入到可行位置构成可行解。其操作示意如图2所示，将路线1上的点p移动到路线2上的点之后，得到两条新的路线。swap(2，1)：随机选择某条路径上连续的节点，然后与另外一条路径上一个节点进行交换，反复尝试执行直到得到一个可行解。其操作示意如图2所示，路线1上两个连续的节点与路线2上的节点进行交换，得到两条新的路径。
[0078]
步骤202：记录局部搜索解sl，得到局部优解sb^，并进行更新；
[0079]
步骤203：采用多点移动的方式对局部优解sb^进行扰动，输出局部最优解sb。
[0080]
进一步地，所述步骤201包括：
[0081]
步骤2011：使用创建领域节点列表方法(createneighborlist)创建节点j、即站点j的大小为size的领域节点列表；
[0082]
步骤2012：获取领域节点列表中的节点k，创建记录此次移动(sbrpmove)的对象m，使用evaluate评估方法评估将节点j插入到节点k的移动是否满足约束，使用checkmove方法评估此次移动产生的新解是否能够接受，按照启发规则确定此次移动对象m是否比目前的最好的移动对象bestm更优，如果是则将当前移动对象m作为最好移动对象bestm；
[0083]
步骤2013：依次搜索邻域节点列表中的每个节点，对每个节点进行步骤2012操作，确定j的最佳插入位置；
[0084]
步骤2014：搜索结束，根据当前记录的最好移动对象bestm对点执行移动操作，操作成功，则节点j就会被永久移动，如果没有找到可行的移动位置或者移动失败，则结束。
[0085]
具体地，所述步骤3中，场站操作算子如图3所示，扰动机制实现时首先选择一定数目的节点，将其从当前解中移除得到问题的部分解；然后再将移除的节点重新插入到部分解中得到一个可行解。随机选择某个节点i邻域内一定数目的节点，将其从当前解中移除得到问题的部分解；然后再将移除的节点重新插入到部分解中得到一个可行解。
[0086]
进一步地，所述步骤3包括：
[0087]
步骤301：输入站点操作后的当前解，即局部最优解sb；
[0088]
步骤302：对场站附近的站点采用destroy场站操作算子进行一定程度的破坏，然后采用对应的repair场站操作算子进行修复，闭合场站不破坏返回路线，开放场站破坏返回路线，重新生成新路线，并检测是否满足约束条件，确定是否接受解；
[0089]
步骤303：记录局部搜索解，检测当前解是否优于当前局部最优解sb，若是，则通过当前解更新全局最优解。
[0090]
具体地，所述步骤302包括：
[0091]
使用两种destroy算子对解进行破坏，采用random destroy算子随机从当前解中移除一定比例的站点，采用worst destroy算子从当前解中移除引起目标函数增幅较大的站点；目标函数为：
[0092][0093]
以最小化校车数量和最小化运营里程为优化目标，其中校车数量为第一优化目
标，运营里程为第二目标，p

为(学生)乘车站点集合，m为车辆集合；v表示所有站点，v＝p∪d，p＝p

∪p-；fk表示车辆k的固定成本，vk表示车辆k的可变成本，d
ij
表示站点i和站点j之间的行驶距离；x
ijk
表示车辆k是否经过站点i和站点j连接的弧，1表示经过，0表示不经过。
[0094]
为验证本发明效果，进行如下实验：
[0095]
测试案例基于sbrp领域首个公开的基准测试案例集，包括rsrb和cscb两类案例集。每个案例集中包含若干所学校及对应的站点。rsrb案例中学校和乘车站点的分布是随机的，cscb案例中学校和乘车站点则分别相对集中的分布在若干个聚集区。测试案例的基本情况如表1所列，平均每个案例集有一定数量的学校，车容量限制为66，最大乘车时间分别设置为2700s(45min)。车辆的平均行驶速度为32.2km/h。
[0096]
表1测试案例基本情况
[0097]
案例学校个数站点个数学生人数cscb0162503409cscb02122503670cscb03125006794cscb04255006805rsrb0162503907rsrb02122503204rsrb03125006813rsrb0425500754
[0098]
作为一种可实施方式，在mdsbrp模型中，在校车规划的范围内增加4个场站，分别是最大外接矩形的4个顶点，场站的容量为最大节点数。在sdsbrp中，在校车规划的范围内的中心点增加1个场站。算法主要采用shift(1,0)、swap(1,0)和swap(2,0)等搜索算子对站点进行操作，采用destroy算子和repair算子对场站进行优化。
[0099]
(1)cscb实验结果
[0100]
使用lns算法求解cscb类测试案例，分别对mdsbrp和sdsbrp进行了求解，分析lns在两种模式下的表现。每个案例随机运行10次，并统计其最好解“best”和解的标准差系数“std”，用“mrt”表示最大行车时间、“gap”代表案例10次运行的最好解和平均解与单场站的情形相比最好解的提升程度。
[0101]
表2两种模式下案例的测试结果比较
[0102]
[0103][0104]
其中nbest表示最佳校车数量，dbest表示最佳运营里程，ngap表示案例10次运行的校车数量最好解和平均解与单场站的情形相比最好解的提升程度，dgap表示案例10次运行的运营里程最好解和平均解与单场站的情形相比最好解的提升程度。
[0105]
从表2可以看出，针对具有乘车时间约束和校车容量约束的cscb01-cscb04案例集中，多场站模式下平均需要校车85.8辆，单场站模式下需要90.72辆，平均节约5.16％的校车；多场站模式下校车的平均运营里程为20641252.21m，单场站模式下校车的平均运营里程为22013214.16m，平均节约了6.70％的校车运营里程。
[0106]
(2)rsrb实验结果
[0107]
使用lns算法求解rsrb类测试案例，对lns在mdsbrp和sdsbrp表现效果进行分析，得到两种模式下车辆数的比较。
[0108]
表3两种模式下车辆数比较
[0109][0110][0111]
实验表明lns算法在求解mdsbrp是有效的。多场站模式运营校车路径问题，能够优化得到需要车辆数更少的路径方案,降低校车的运营成本。lns算法的稳定性较好，lns在多场站和单场站两种模式下的解的平均标准差在2.59-3.64之间，解的均值和标准差的变化
很小，表明算法具有良好的稳定性和收敛性。最大乘车时间mrt为5400时，lns算法的求解结果整体较好，原因在于mrt的值变大相当于问题约束更加宽松，算法能够在较短的时间内找到更好的解。
[0112]
(3)cscb和rsrb实验结果比较
[0113]
通过cscb和rsrb对比分析lns算法在cscb和rsrb数据集中的表现，δ表示标准差系数的差值。
[0114]
表4两种模式下cscb和rsrb的结果比较
[0115][0116]
从表4可以看出，在mdsbrp中，cscb案例比rsrb案例节约了3.03％的校车，运营里程节约11.27％；在sdsbrp中，cscb案例比rsrb案例节约了2.71％的校车，平均运营里程节约10.66％；结果说明算法在cscb案例中比rsrb案例效果更好。
[0117]
表5两种模式下cscb和rsrb的稳定性比
[0118]
[0119][0120]
其中，δn表示车辆数平均标准差系数差值，δd表示运营里程标准差系数差值。
[0121]
从表5可以看出，无论在单场站模式还是多场站模式，cscb的稳定性都大于rsrb，说明算法在cscb中具有更好的稳定性。
[0122]
通过以上实验结果，可以得知lns算法在两种案例中具有以下特点:
[0123]
lns算法在mdsbrp中，cscb案例中需要车辆数比rsrb提升了3.03％，cscb的运营里程比rsrb提升了11.27％。在sdsbrp中，cscb案例中需要车辆数比rsrb提升了2.71％，cscb的运营里程比rsrb提升了10.66％。说明lns算法在集中案例中效果更好。
[0124]
lns算法在mdsbrp中，cscb和rsrb车辆数标准差系数相近，但车辆数平均标准差系数差值为0.16。cscb和rsrb运营里程准差系数相近，运营里程标准差系数差值为0.16。在sdsbrp中，cscb车辆数标准差系数大部分小于rsrb，车辆数平均标准差系数差值为0.43。cscb运营里程标准差系数大部分小于rsrb，车辆数平均标准差系数差值为1.31。说明lns稳定性在集中案例中效果更好。
[0125]
综上，本发明针对站点和场站分别采用了不同的算子进行搜索：针对站点采用了swap(1，1)，shift(1，0)，swap(2，1)三种站点操作算子完成邻域搜索；针对场站引入了扰动机制进行优化。本发明通过站点操作算子在路径间和路径内调整站点，扩展了邻域解的启发策略，通过在一组基准测试实例上测试了该算法的性能。lns对求解mdsbrp实例具备有效性和稳定性。通过在mdsbrp和sdsbrp中的测试，结果表明本发明提出的方法是有效的，无论在mdsbrp还是sdsbrp均取得不错的效果，能够提高解决方案的质量。通过mdsbrp和sdsbrp的比较，mdsbrp能够进一步减少所需校车数量和缩短行驶距离，进而节约校车服务成本。本发明方法计算效率高，稳定性好。
[0126]
以上所示仅是本发明的优选实施方式，应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明原理的前提下，还可以做出若干改进和润饰，这些改进和润饰也应视为本发明的保护范围。