CN119863182B 基于自适应大邻域搜索算法的客货共运公交路径规划方法 （浙江大学）

(19)国家知识产权局(12)发明专利地址310058浙江省杭州市西湖区余杭塘(56)对比文件(72)发明人李德纮郑文曹朋生李珂豫杨业顺司33212GO6Q10/0835(2023.01)权利要求书3页说明书13页附图2页基于自适应大邻域搜索算法的客货共运公(57)摘要本发明涉及适用于物流管理目的的信息和搜索算法的客货共运公交路径规划方法。包括：时间窗口限制的因素，寻求成本最低的路径方先满足乘客需求为核心，同时兼顾货物运输服是否达到停止条件输出最优解21.一种基于自适应大邻域搜索算法的客货共运公交路径规划方法，其特征在于，以下步骤：(2)根据客货共运策略建立路径优化模型，在优先满足乘客需求的同时兼顾货物运输式(1)用于保障能够满足经筛选后的所有不同客货的运输需求；式(2)-(4)是流平衡约所述服务时间窗约束具体包括：xk=1→sik+serv,+t;≤Sjk式(6)保证车辆k在结束需求点i的服务后，通过路径x;5到达下一服务点j的时间不得3策略一：将同一地点的客运和货运视为一种需求，并设定每辆车只访问每个需求点一策略二：将同一地点的客运和货运需求分开处理，不同的货物需求量；q为车辆额定容量，即车辆限定的最大能装载的乘客人数和货物标准件数j,其离开j点时的客/货装载量需要等于车辆在离开点i后的客/货装载量与在j点上下客/步骤ii:定义破坏操作与修复操作对应的破坏算子集合和修复算子集合；步骤v:构建初始解；4(vi-5)计算新解的成本，并通过模拟退火方法计算接受概率；(vi-6)根据接受准则接受新解作为当前解；(vi-7)更新最优解；(vi-8)更新操作权重；(vi-9)降温，使得算法从探索阶段过渡到收敛阶段；步骤vii:当达到最大迭代次数时，输出当前的最优解作为最终的路径方案。5.根据权利要求1所述的方法，其特征在于，所述自适应大邻域搜索算法中，包括下述九种破坏算子：随机请求移除、随机路线移除、最差距离移除、最差时间移除、最差邻域移除、Shaw移除、基于邻近性的移除、基于时间的移除、基于请求的移除。6.根据权利要求1所述的方法，其特征在于，所述自适应大邻域搜索算法中，包括下述三种修复算子：随机插入、贪婪插入、遗憾插入。5基于自适应大邻域搜索算法的客货共运公交路径规划方法技术领域[0001]本发明涉及适用于物流管理目的的信息和通信技术领域，尤其是涉及一种基于自适应大邻域搜索算法的预约式客货共运公交路径规划方法。背景技术[0002]在城市交通的高峰时段，由于出行需求增加，交通量大幅提升，而货运车辆因行驶速度较慢且体积庞大，往往成为道路的瓶颈，进一步加剧了拥堵并导致碳排放的急剧增加。反之，在非高峰期，城市公交系统的运力往往存在过剩，这为解决高峰与非高峰客货运输需求失衡的问题提供了思路——即在非高峰时段，充分利用公交系统的富余运力协同承载部分货运需求，实现客货共运的有效融合。[0003]因此，如何有效分析与整合客货需求，并根据实际情况合理规划预约式公交的运行路径，使得其能够以最小的成本满足客户的需求，是当前亟待解决的关键问题。为应对上述挑战，优先满足乘客出行需求，同时运用剩余运力来运输货物，通过构建客货共运场景下车辆路径问题的混合整数规划模型，并建立合适的算法完成求解。[0004]中国发明专利CN111798067A提出基于自适应大邻域搜索算法的自动驾驶汽车配送路径规划方法，包括：计算任意两点间的距离；生成单独采用轿运车配送自动驾驶汽车的车辆路径作为初始解；采用自适应大邻域搜索算法选择邻域算子对可行解进行操作形成新的可行解；对新可行解的质量进行评估进而对邻域算子进行评估；采用模拟退火算法控制自适应大邻域搜索算法的可行解是否被接受、直到算法达到终止条件后将自动驾驶汽车与轿运车协同配送的路径规划方案输出。该方法对自动驾驶汽车这种可以自行移动位置的特殊货物配送进行配送路径规划，提炼出数学模型在Removal算子、Insertion算子的基础上加入拆分算子、融合算子来对该问题进行求解。但该技术方案只适用于单一配送目的的自动驾驶汽车路径规划(特别是远距离之间的长途运输),不能用于实现城市交通条件下的不同配送目的的货运车辆与城市公共交通之间的客货共运。[0005]为了有效求解客货共运场景下的车辆路径优化模型，优化算法的选择至关重要。精确算法如分支定界法和割平面法，可以确保获得最优解，其通过系统性的搜索和剪枝策法往往需要耗费大量时间，尤其在问题规模较大的情况下，求解效率受到显著影响。因此，本发明旨在提出更适于城市复杂交通条件的算法机制以提升计算效率，更好地应对复杂动态环境中的客货需求变化，并实际应用中表现出优越的灵活性和效率。发明内容[0006]本发明要解决的技术问题是，克服现有技术中的不足，提供一种基于自适应大邻域搜索算法的客货共运公交路径规划方法。[0008]提供一种基于自适应大邻域搜索算法的客货共运公交路径规划方法，包括以下步6[0018]其中，各式中的符号分别指：k为车辆序号；K为车辆集合；i、j为提供需求或服务的节点或地点；A为不同节点之间的路径集合，(i,合；D为下客点/送货点集合；n为上客/取货点的数量；V是指对于任意的参数取值；Xijk为0-1变量，若车辆k通过路径(i,j)则为1,否则为0;[0019]式(1)用于保障能够满足经筛选后的所有不同客货的运输需求；式(2)-(4)是流客户点的要求；式(5)是联结约束，用于保证同一需求的起点和终点必须是被同一辆车服7作为本发明的优选方案，所述服务时间窗约束具体包括：xk=1→sik+serv;+t,≤SjkV(i,[0022]其中，各式中的符号分别指：Xijk为车辆在需求点i和j之间的行驶路径；为车辆k在需求点i的开始服务时间；serv,为服务时间；t为车辆在需求点i和j之间的行驶时间；V为所有提供需求或服务的节点或地点的集合；a;为需求点i设定最早开始服务的时间；b:为需求点i设定最晚开始服务的时间；[0023]式(6)保证车辆k在结束需求点i的服务后，通过路径x₁n到达下一服务点j的时间不得大于该点的服务开始时间；式(7)为车辆运输优先级约束，即针对每一客货运需求，其上客/取货需求的服务顺序一定要早于下客/配送需求；式(8)为需求点服务时间窗约束，即车辆k到达需求点i开始服务的时间sik,不得早于a,也不能晚于b。[0024]作为本发明的优选方案，所述车辆容量约束具体包括：[0026]其中，各式中的符号分别指：Q¹ik为车辆k在离开需求点i时的乘客总装载量；Q²k为车辆k在离开需求点i时的货物总装载量；为需求点i、j的乘客需求量；为需求点i、j的货物需求量；q为车辆额定容量，即车辆限定的最大能装载的乘客人数和货物标准件数量；[0027]式(9)和式(10)分别保证车辆k在结束需求点j的服务后，通过路径xijk到达下一服务点j,其离开j点时的客/货装载量需要等于车辆在离开点i后的客/货装载量与在j点上下客/装卸货量之和；式(11)保证车辆k在i点的总装载量不得大于车辆额定容量。[0028]作为本发明的优选方案，所述目标函数具体如下为车辆在需求点i和j之间的行驶路径；SjkSi为车辆k到达需求点j、i开始服务的时间；8间的权重系数；β为平均乘客在途时间的权重系数。[0031]作为本发明的优选方案，所述进行自适应大邻域搜索算法的求解，具体包括以下步骤：[0032]步骤i:输入一个可行的初始路径方案，以及算法的相关参数；[0033]步骤ii:定义破坏操作与修复操作对应的破坏算子集合和修复算子集合；[0034]步骤iii:定义邻域大小集合；[0035]步骤iv:初始化温度和操作的权重；[0036]步骤v:构建初始解；[0037]步骤vi:在未达到最大迭代次数之前，进行如下操作：[0038](vi-1)检查解池，如为空则添加新解及对应的成本；[0039](vi-2)从解池中选择新解，保障每次迭代从不同的初始解开始；[0040](vi-3)轮盘赌选择操作；[0041](vi-4)选择邻域大小并执行破坏修复操作；[0042](vi-5)计算新解的成本，并通过模拟退火方法计算接受概率；[0043](vi-6)根据接受准则接受新解作为当前解；[0044](vi-7)更新最优解；[0045](vi-8)更新操作权重；[0046](vi-9)降温，使得算法从探索阶段过渡到收敛阶段；[0047]步骤vii:当达到最大迭代次数时，输出当前的最优解作为最终的路径方案。[0048]作为本发明的优选方案，所述自适应大邻域搜索算法中，包括下述九种破坏算子：随机请求移除(RRE)、随机路线移除(RRO)、最差距离移除(WDR)、最差时间移除(WTR)、最差邻域移除(WNR)、Shaw移除(SR)、基于邻近性的移除(PR)、基于时间的移除(TR)、基于请求的[0049]作为本发明的优选方案，所述自适应大邻域搜索算法中，包括下述三种修复算子：随机插入(RAI)、贪婪插入(GI)、遗憾插入(REI)。[0050]本发明进一步提供了一种计算机设备，包括：至少一个处理器，以及与至少一个处理器通信连接的存储器，其中，存储器存储有被至少一个处理器执行的指令，指令被至少一个处理器执行，以使所述至少一个处理器执行任一项前述的基于自适应大邻域搜索算法的客货共运公交路径规划方法。[0051]本发明还提供了一种计算机可读存储介质，所述计算机可读存储介质存储有计算机指令，所述的计算机指令用于使所述计算机执行任一项前述的基于自适应大邻域搜索算法的客货共运公交路径规划方法。[0052]与现有技术相比，本发明的技术效果是：[0053]1、针对现有城市交通运输系统中所存在客货流不平衡导致的交通资源利用不均衡问题，本发明提出了一种基于自适应大邻域搜索算法的预约式客货共运公交路径规划方法，根据乘客与货物不同的运输需求(包含客/货运量，运输起终点以及运输时间窗等),为预约式公交系统中的客货运输问题提供了高效的车辆路径规划方案。该方案在综合考虑乘客优先原则的基础上，能够实现客货共运模式下的供需平衡，为预约式公交系统的高效运营提供了新的视角和解决方案。9[0054]2、由于公共交通服务的特殊性，传统的车辆路径规划模型中常用的节点访问次数约束条件未能优先考虑乘客因素，不能适用于公交客货共运模式。本发明创新地提出两种客货共运策略，可用于不同规模以及不同类型客货需求站点的公交路径规划，包括上客上货、上客下货、下客上货以及下客下货的站点。因此体现了公共交通中乘客-货物共运模式在提升运输效率方面的潜力，同时也强调了在这种模式下优先满足乘客需求的重要性。在需要时，策略二相较于策略一往往能取得更好的效果。[0055]3、基于全新的客货共运策略，本发明提出了综合考虑乘客和货物共运需求的车辆路径优化模型。该模型以优先满足乘客需求为核心，同时兼顾货物运输服务。在模型的目标函数中，特别引入了乘客在途时间这一关键指标，具体由公式(12)的计算予以实现，以确保乘客体验的优化。此外，模型还综合考虑了时间窗口和车辆容量等关键约束条件，这些约束对于确保模型解决方案的实用性和可行性至关重要。[0056]4、本发明构建了改进的自适应大邻域搜索算法，通过动态选择和调整破坏与修复操作有效应对客货共运公交路径规划中的复杂性问题。测试实验的结果表明，与商业求解器Gurobi相比该算法在求解性能上具有明显优势，主要体现在求解时间上。并且，随着模型中约束条件与决策变量的规模增加，这种优势会更加显著。附图说明[0057]图1为本发明不同策略下客货共运模式示意图。[0058]图2为本发明求解算法执行过程示意图。[0059]图3为本发明算法的不同算子在求解过程中权重变化图。具体实施方式[0061]首先，本发明所述基于自适应大邻域搜索算法的客货共运公交路径规划方法，是基于计算机设备和计算机可读存储介质的硬件设备而实现的。[0062]其中，计算机设备包括：至少一个处理器，以及与至少一个处理器通信连接的存储器，其中，存储器存储有被至少一个处理器执行的指令，指令被至少一个处理器执行，以使所述至少一个处理器执行所述的基于自适应大邻域搜索算法的客货共运公交路径规划方法。计算机可读存储介质存储有计算机指令，所述的计算机指令用于使计算机执行所述的基于自适应大邻域搜索算法的客货共运公交路径规划方法。[0063]本发明所述基于自适应大邻域搜索算法的客货共运公交路径规划方法，主要包括确定客货共运策略、建立路径优化模型以及进行搜索算法求解三个关键部分。其中，客货共运策略的制定是根据不同客/货需求的特征来划分不同的运输策略；路径优化模型的建立旨在满足需求的各种条件的前提下，寻求成本最低的路径方案；进行搜索算法求解则是为了应对大规模混合整数规划问题的计算复杂性，提出适合模型结构的计算方法，以实现模型求解的精确性和快速性。[0064]1、通过公共交通服务系统的预约系统，以预约方式接收乘客与货物的基本运输信息，至少应包括客货数量、起讫点和时间要求；通过获取不同客货需求的特征，确定客货共运策略。[0065]本发明所述的客货共运公交的路径规划问题有两种可行的方案。第一种方案：将同一地点的客运和货运视为一种需求，并设定每辆车只访问每个需求点一次。这表明，当客运和货运同时存在时，该地点的客运和货运需求必须由同一辆车提供服务；第二种方案：将同一地点的客运和货运需求分开处理，不同的车辆最多可以访问该地点两次，即当同时有乘客上车，又有货物装车时，可以分别由不同的车辆提供服务。这两种情况分别对应图1中的策略一和策略二。通常情况下，传统的车辆路径问题受限于同一节点只能访问一次，以确保资源的合理利用和成本最小化。然而，在客货共运场景中，这种定义可能会导致运输成本的增加。从图1中可以看出，策略一与策略二的不同之处在于，它允许不同的车辆访问同一节点两次。[0066]本发明所述的规划方法可用于不同的优化目标，如最小时间成本、最小费用成本以及最大利润等。所述的路径规划方法为不同需求的用户提供合适的运输方案，满足客户的客/货需求，实现交通运输资源的合理分配，实现交通运输系统的降本增效，为预约式公交的客货共运模式提出范式。[0067]在表1、表2中，分别针对两种策略进行了目标函数值的比对，其中表1中是基于十个需求点算例的紧凑时间窗限制条件，表2中是基于十个需求点算例的宽松时间窗限制条件。时间车时间时间在车时间一二;时间车时间时间在车时间一二;[0072]从表1、表2中可以看出，策略一在紧迫时间窗口下表现优异：当时间窗口紧迫时，策略一在减少车辆行驶时间和总成本方面表现更好。这主要是由于时间窗口约束较为严格，导致乘客需求的优先考虑会增加成本，特别是在需要增派车辆的情况下。[0073]此外，策略二在宽松时间窗口下更具优势：在宽松的时间窗口条件下，策略二能更好地平衡车辆和乘客时间，减少乘客车内等待时间。这表明，在时间灵活性较大的情况下，策略二更能有效地调度资源和优化整体运营。[0074]2、根据客货共运策略建立路径优化模型；在满足所有需求的前提下，侧重考虑车11辆容量以及时间窗口限制的因素，寻求成本最低的路径方案。[0075]本发明的路径优化模型，包含约束条件与目标函数两部分，其中约束条件主要包括需求服务约束、服务时间窗约束以及车辆容量约束。而目标函数主要是以时间成本为优化目标。[0077]由于运输任务是满足经过平台处理后同意预约请求的需求，因此须保障预约式公交能够服务筛选后的所有需求，而式(1)的设置满足了该约束。式(2)-(4)是经典的流平衡约束，其保障了车辆须从始发运输场站点出发并且回到该点，且满足到达并离开每个客户点的要求。此外，式(5)是一种联结约束，其保证了同一需求的起点和终点必须是被同一辆车服务。[0079](2)服务时间窗约束：[0080]为了保障车辆在期望的时段内满足需求，需要给预约式公交添加适当的时间约束。其中，式(6)表达了车辆k在结束需求点i的服务后，通过路径xijk到达下一服务点j的时间不得大于该点的服务开始时间。式(7)为车辆运输优先级约束，即针对每一客货运需求，其上客(取货)需求的服务顺序一定要早于下客(配送)需求。式(8)为需求点服务时间窗约束，即车辆k到达需求点i开始服务的时间sik,不得早于a,也不能晚于b。[0082](3)车辆容量约束：[0083]预约式公交作为一种预约出行工具，需要保证其车厢有足够个人空间(即不能超过车辆的额定容量q,即最大能装载的乘客人数和货物标准件数量不能超过车辆限定容量)。因此，在模型中需要限定车辆中客货的数量，而式(9)和式(10)分别表示了车辆k在结束需求点i的服务后，通过路径xijk到达下一服务点j,其离开j点时的客/货装载量需要等于车辆在离开点i后的客/货装载量与在j点上下客(装卸货)量之和。而式(11)则[0089]本发明所述公式(1)-(12)中的参数及变量含义具体见表3。页模型nPTDVACV上客点/取货点集合，P={1,2,3,…,n}下客点/配送点集合，D={n₁+1,n₁+2,,n₁+n₂}所有节点集合，V=PUDU{0}客户点i的客运需求量(即上/下客数量),如果i是上客d>0;如果i是下客点，d¹<0;若没有乘客上下车，则为0;客户点i的货运需求量(即取/送货数量),如果i是取货点，;如果i是配送点，;若没有装卸货物，则为0车辆额定容量(设定为50,即可以分别单独容纳50个乘客或者50个标准化包裹，或者二者总量为50)从i点到点的行驶时间，t,=c,/v车辆在客户点i的服务时间一个足够大的正数qM决策若路径i→j被选择，则×=1,否则为0Sik车辆k开始服务客户点i的时刻[0101]设定邻域大小集合Q={qmin,Q₁,Q₂,Q₃,…,4max³,用于控制每步操作中处理任[0103]设定初始温度T和冷却速率φ,用于控制模拟退火的接受准则。初始化每个破[0105]生成初始解x0,并将其设为当前最优解x*。初始解可通过随机分配或启发式新解x以及对应的成本Cost,并将其添加到解池中。[0122]生成一个0~1范围内的随机数，如果该随机数小于接受概率Paccept,则xn作为当前解x。[0125]根据操作的表现(即生成的解是否被接受或改进了当前最优解),更新破坏和修复[0128]步骤7:输出最优解x*;[0130]本发明使用的自适应大邻域算法与常规算法相比，在操作步骤上进行了显著改[0131]本发明使用的自适应大邻域算法中，主要针对破坏算子的构造进行了适应性改[0134](2)随机路线移除(RRO):这个破坏操作用于随机选择包含请求的路线，通过随机筛选无效路线来确保所选路线至少包含足够的请求以供操作。[0135](3)最差距离移除(WDR):这个操作的核心思想是从当前解决方案中移除那些对整体解决方案质量贡献最差的距离因素，这些因素通常会显著增加解决方案的成本或影响解决方案的效率。[0136](4)最差时间移除(WTR):这是一种考虑最差时间的破坏操作，用于识别时间窗口约束问题，通过找到服务开始时间与时间窗口开始时间之间差异最大的请求，可以帮助优化路线调度问题中的时间约束。[0137](5)最差邻域移除(WNR):该操作基于邻近请求的相对贡献来有效识别对路径成本影响最大的请求。通过计算每个请求相对于其前一个和后一个位置的距离贡献，识别出对整体路径距离贡献百分比最高的请求。随后可以通过移除或重新优化该请求来优化整个路[0138](6)Shaw移除(SR):该操作通过模型中考虑的因素(在本发明中考虑距离、时间窗口和需求)选择与当前位置最相关的下一个服务请求。[0139](7)基于邻近性的移除(PR):这种方法基于邻近性来识别下一个请求，选择最接近的位置来破坏当前解决方案，以实现进一步的优化。[0140](8)基于时间的移除(TR):这是为了根据时间窗口差异选择下一个最合适的请求。其目标是最小化请求之间的时间窗口差异，以满足时间窗口约束并优化调度问题中的服务顺序。[0141](9)基于请求的移除(RR):这是一种基于需求差异的启发式破坏操作操作，能够通