一种考虑阶梯运价补贴的车辆调度方法

摘要

本发明公开了一种考虑阶梯运价补贴的车辆调度方法，属于物流运输技术领域，包括：S1：将获取的客户订单及地理位置信息和车辆约束信息作为输入信息；S2：基于混合整数规划构建考虑阶梯运价补贴的多车型分配与路径规划的车辆调度模型；S3：将基于混合整数规划的车辆调度模型重构为主问题模型和子问题模型；S4：采用优化的分支定界算法对所述车辆调度模型的主问题模型进行求解得到目标结果，利用所述目标结果获得最低成本的车辆调度方案，以进行多车型分配和行车路径规划。本发明使用改进的分支定价算法求解车辆调度模型的主问题，根据目标结果进行多车型分配和行车路径规划，从而提高车辆调度效率、降低物流成本。

说明书

技术领域

本发明属于物流运输技术领域，更具体地，涉及一种考虑阶梯运价补贴的车辆调度方法。

背景技术

车辆路径规划是物流配送的核心环节，也是物流配送信息系统建立的基础和重要模块。车辆路径规划的好坏，对物流配送的效率有非常大的影响。当前物流配送中一般拥有多种数量有限且容量不同的车型，需要使用这些车型在客户指定的时间窗内完成客户订单的配送和服务，这便形成了经典的多车形路径规划问题。

当前大量企业物流配送采用外包承运商进行，不同客户在对应区域的运输单价因运输地区而不同，在运输结算中普遍存在当订单数量未达到对应运输模式下的保底数量时，需要进行相应的运输补贴的情况。同时，由于在运输配送结算过程中保底数量还会因为车辆运输数量的不同而变化，这样就产生了考虑阶梯运价补贴的运价结算机制。更为特殊的，对于烟草、医药等高价值、强监管的物流，其配送特性要求其单车运输客户数量存在限制。

然而，现有技术中车辆调度算法多为启发式算法，其收敛性有待考证，并且其容易陷入局部最优解，不能保证获得行车路径规划问题的最优解，进而导致车辆调度效率低，物流成本高。

发明内容

针对现有技术的以上缺陷或改进需求，本发明提供了一种考虑阶梯运价补贴的车辆调度方法，其目的在于使用改进的分支定价算法求解车辆调度模型的主问题，从而提高车辆调度效率、降低物流成本，由此解决现有技术中车辆调度效率低，物流成本高的技术问题。

为实现上述目的，按照本发明的一个方面，提供了一种考虑阶梯运价补贴的车辆调度方法，包括：

S1：将获取的客户订单及地理位置信息和车辆约束信息作为输入信息；

S2：基于混合整数规划构建考虑阶梯运价补贴的多车型分配与路径规划的车辆调度模型；

S3：将基于混合整数规划的车辆调度模型重构为主问题模型和子问题模型；

S4：采用优化的分支定界算法对所述车辆调度模型的主问题模型进行求解得到目标结果；利用所述目标结果获得最低成本的车辆调度方案，以进行多车型分配和行车路径规划。

在其中一个实施例中，所述步骤S1中的：

所述客户订单及地理位置信息包括：每个等待配送客户的地理位置、订货量、服务时间窗以及单位运输成本；配送中心与各个客户的位置信息、和路径长度信息；车辆的最大允许客户运输量，以及运输节点相关的运算标准重量；

所述车辆约束信息包括：所有客户的订单必须被满足客户的时间窗[a

其中，车辆类型按照容量进行排序并编码，容量越小则排序越靠前编码ID越小，容量越大则排序越靠后编码ID越大。

在其中一个实施例中，所述步骤S3中基于混合整数规划的所述车辆调度模型如下：

其中，公式(1.1)表示目标函数为最小化总成本；公式(1.2)与公式(1.3)共同计算考虑阶梯运价补贴的配送成本；公式(1.4)表示车辆容量约束，保证每个车辆分配的量小于其车辆容量Q

在其中一个实施例中，所述主问题模型如下：

公式(1.15)表示最小化总成本；公式(1.16)表示保证每个订单均被送达；公式(1.17)表示具体车辆数目约束，保证对应车型数量小于已有车辆数量；公式(1.18)为变量范围约束；

其中，Ω

所述子问题模型如下：

公式(1.19)中u

在其中一个实施例中，所述步骤S4包括：

S4-1：初始化节点信息，令全局上界为正无穷大，活跃节点集合Δ

S4-2：启发式方法HVARP获得主问题的初始解Bset；

S4-3：使用所述初始解Bset初始化受限主问题RMP节点树的根节点

S4-4：使用列生成流程CG，计算问题的下界

S4-5：判断Δ

S4-6：选择活跃节点集合Δ

S4-7：判断节点δ的下届δ

S4-8：判断节点δ是否是整数解，如果是则将当前节点的解δ设置为Bset，转步骤S4-5，否则执行下一步；

S4-9：通过分支流程BB生成两个新的节点δ

S4-10：获得最优解，输出所述目标结果，算法结束。

在其中一个实施例中，所述步骤S4-2包括：

HVARP-1：初始化返回集合Δ

HVARP-2：按照客户的时间窗[a

HVARP-3：将折算质量q

HVARP-4：判断Θ是否为空，若为空则转步骤HVARP-8，否则执行下一步；

HVARP-5：依次计算Θ中任意两个客户i，j的节约值Save

HVARP-6：判断临时路径r

HVARP-7：k←k+1，遍历集合Θ，寻找与r

HVARP-8：将路径集合Ω中的路径按照路径容量升序排列，车辆也按照车辆容量升序排列；

HVARP-9：判断路径集合Ω是否为空，若为空则转步骤HVARP-11，否则执行下一步；

HVARP-10：依次为Ω的路径r分配第一个可行的车辆m，分配完成后，添加

HVARP-11：判断Θ′是否为空，若为空，则转步骤HVARP-13，否则执行下一步；

HVARP-12：依次计算Θ′中任意两个客户i，j，选择时间窗可行，且路径容量最大的生成临时路径r

HVARP-13：将路径集合Ω中的路径按照路径容量降序排列，车辆也按照车辆容量降序排列；

HVARP-14：判断路径集合Ω是否为空，若为空则转步骤HVARP-16，否则执行下一步；

HVARP-15：依次为Ω的路径r分配第一个可行的车辆m，分配完成后，添加

HVARP-16：算法结束，返回结果集合Δ

在其中一个实施例中，所述步骤S4-4包括：

CG-1：构造受限主问题模型RMP；

CG-2：使用预设求解器直接求解松弛的受限主问题LP-RMP；

CG-3：使用启发式方法HA获得子问题的解s

CG-4：判断rc

CG-5：判断集合

CG-6：执行精确求解算法EA获得子问题的解s

CG-7：判断rc

CG-8：主问题已到达最优解，返回求解器求解结果，结束算法。

在其中一个实施例中，所述步骤CG-3包括：

HA-1：初始化返回集合Δ

HA-2：分别计算客户i在标准重量θ

HA-3：将虚拟成本

HA-4：判断k＝0，若满足则转步骤HA-10；否则，从集合

HA-5：若

HA-6：判断路径r

HA-7：如果m≤|M|，计算

HA-8：若

HA-9：若|Δ

HA-10：结束算法，返回Δ

在其中一个实施例中，所述步骤CG-6包括：

EA-1：初始化返回集合Δ

EA-2：分别计算客户i在标准重量θ

EA-3：将虚拟成本

EA-4：判断k＝0，若满足则转步骤EA-12，否则从集合

EA-5：若

EA-6：判断路径r

EA-7：遍历

EA-8：计算最小的可用车型

EA-9：如果m≤|M|，计算

EA-10：若

EA-11：若|Δ

EA-12：若

EA-13：结束算法，返回Δ

在其中一个实施例中，所述步骤S4-9中分支流程BB包括：

BB-1：统计当前节点δ的解中包含的弧(i，j)，并将其添加到集和Δ

BB-2：对Δ

BB-3：选择流量最接近0.5的弧(i，j)作为分支项f′

BB-4：生成节点δ

BB-5：算法结束，返回节点δ

总体而言，通过本发明所构思的以上技术方案与现有技术相比，能够取得下列有益效果：

1.本发明通过获取客户数据、地理位置等输入信息，将实际混合路网转换为抽象的节点路段网络；再基于混合整数规划构建考虑阶梯运价补贴的多车型分配与路径规划的车辆调度模型；并将混合整数规划的车辆调度模型重构为主问题模型和子问题模型；针对该车辆调度模型设计了精确分支定价算法，实现针对不同阶梯运价场景的使用，能够提升车辆调度效率，合理安排车型并规划最优路线，从而降低物流成本。

2.本发明采用流量分支和启发式与精确求解方法结合的方式，在保证最优解的同时，有效提升了求解效率，进而提升车辆调度效率。本发明能够为采用阶梯运价补贴的大规模混合车队配送企业或系统提供最佳的调度方案，在保证客户满意度的同时，降低物流成本，实现最优调度。

附图说明

图1是本发明提供的考虑阶梯运价补贴的车辆调度方法的流程图；

图2是本发明实施例的成本随着需求量的变化曲线图；

图3是本发明实施例中步骤S4中求解主问题模型的具体流程图；

图4是本发明实施例中启发式方法HVARP的具体流程图；

图5是本发明实施例中列生成流程CG的具体流程图；

图6是本发明实施例中分支流程BB的具体流程图；

图7是本发明实施例中启发式方法HA的具体流程图；

图8是本发明实施例中确求解算法EA的具体流程图；

图9是本发明实施例中调度方案的示意图。

具体实施方式

为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅仅用以解释本发明，并不用于限定本发明。此外，下面所描述的本发明各个实施方式中所涉及到的技术特征只要彼此之间未构成冲突就可以相互组合。

如图1所示，本实施例提供了考虑阶梯运价补贴的车辆调度方法，主要包含4个步骤：

S1：将获取的客户订单及地理位置信息和车辆约束信息作为输入信息；

S2：基于混合整数规划构建考虑阶梯运价补贴的多车型分配与路径规划的车辆调度模型；

S3：将基于混合整数规划的车辆调度模型重构为主问题模型和子问题模型；

S4：采用优化的分支定界算法对所述车辆调度模型的主问题模型进行求解得到目标结果；利用所述目标结果获得最低成本的车辆调度方案，以进行多车型分配和行车路径规划。

在其中一个实施例中，所述客户订单及地理位置信息包括：每个等待配送客户的地理位置、订货量、服务时间窗以及单位运输成本；配送中心与各个客户的位置信息、和路径长度信息；车辆的最大允许客户运输量，以及运输节点相关的运算标准重量；

所述车辆约束信息包括：所有客户的订单必须被满足客户的时间窗[a

其中，车辆类型按照容量进行排序并编码，容量越小则排序越靠前编码ID越小，容量越大则排序越靠后编码ID越大。

举例来说，假设企业A有n个已知位置和需求地客户需要从发出仓库depot进行发出，且各个客户均具有服务时间窗(早到需要等待，不允许晚到)，企业为了满足客户需求，先将物流配送任务外包给物流企业B，该物流企业拥有一支多种车辆地混合车队，各种车型数量有限，已知此物流企业对各个地域运费单价不同，即客户的运输单价不同，且此物流企业有最低重量阶段保证制度，当客户运送物品折算重量没有达到既定标准重量则按照标准重量计费。同时，由于A企业行业特殊，货品价值及大且要求强监管，要求单个车辆不得运输超过3个客户。物流企业B也依据此设定出三个不同的折算标准重量12、10、5。现在需要A企业联合决策车型分配和车辆的路径规划，配送系统在能够满足客户需求的同时，最小化物流成本。

在其中一个实施例中，混合整数规划模型中，若使用m类型车辆的第v

在其中一个实施例中，所述混合整数规划模型如下，其参数与符号定义如表1所示：

其中，公式(1.1)表示目标函数为最小化总成本；公式(1.2)与公式(1.3)共同计算考虑阶梯运价补贴的配送成本；公式(1.4)表示车辆容量约束，保证每个车辆分配的量小于其车辆容量Q

表1

在其中一个实施例中，所述主问题模型MP，包括以下公式：

公式(1.15)表示最小化总成本；公式(1.16)表示保证每个订单均被送达；公式(1.17)表示具体车辆数目约束，保证对应车型数量小于已有车辆数量；公式(1.18)为变量范围约束；其中，Ω

进一步地，所述子问题模型包括以下公式：

其中，参数与符号定义如表1所示，公式中u

进一步地，所述对主问题模型进行求解，其流程如图3所示，主要包括以下步骤：

S4-1初始化节点信息，令全局上界为正无穷大，活跃节点集合Δ

S4-2启发式方法HVARP获得问题的初始解Bset；

S4-3使用初始解Best初始化受限主问题RMP节点树的根节点

S4-4使用列生成流程CG，计算问题的下界

S4-5判断Δ

S4-6选择活跃节点集合Δ

S4-7判断节点δ的下届δ

S4-8判断节点δ是否是整数解，如果是则将当前节点的解δ设置为Best，转步骤S4-5，否则执行下一步；

S4-9通过分支流程BB生成两个新的节点δ

S4-10获得最优解，输出结果，算法结束。

进一步地，所述S4-2步骤中的启发式方法HVARP，其流程如图5示包括以下步骤：

HVARP-1初始化返回集合Δ

HVARP-2按照客户的时间窗[a

HVARP-3将折算质量q

HVARP-4判断Θ是否为空，若为空则转步骤HVARP-8，否则执行下一步；

HVARP-5依次计算Θ中任意两个客户i，j的节约值Save

HVARP-6判断临时路径r

HVARP-7 k←k+1，遍历集合Θ，寻找与r

HVARP-8将路径集合Ω中的路径按照路径容量升序排列，车辆也按照车辆容量升序排列；

HVARP-9判断路径集合Ω是否为空，若为空则转步骤HVARP-11，否则执行下一步；

HVARP-10依次为Ω的路径r分配第一个可行的车辆m，分配完成后，添加

HVARP-11判断Θ′是否为空，若为空，则转步骤HVARP-13，否则执行下一步；

HVARP-12依次计算Θ′中任意两个客户i，j，选择时间窗可行，且路径容量最大的生成临时路径r

HVARP-13将路径集合Ω中的路径按照路径容量降序排列，车辆也按照车辆容量降序排列；

HVARP-14判断路径集合Ω是否为空，若为空则转步骤HVARP-16，否则执行下一步；

HVARP-15依次为Ω的路径r分配第一个可行的车辆m，分配完成后，添加

HVARP-16算法结束，返回结果集合Δ

在其中一个实施例中，HVARP-7中所述

CG-1构造受限主问题模型(RMP)；

CG-2使用商业求解器直接求解松弛的受限主问题(LP-RMP)；

CG-3使用启发式方法HA获得子问题的解s

CG-4判断rc

CG-5判断集合Δ

CG-6执行精确求解算法EA获得子问题的解s

CG-7判断rc

CG-8主问题已到达最优解，返回求解器求解结果，结束算法。

在其中一个实施例中，所述受限主问题模型即由初始可行解按照主问题模型形式构建地模型，所述松弛的受限主问题即在RMP模型中将公式替换为0≤ψ

进一步地，所述主问题模型进行求解中的分支流程BB，其流程如图6示，包括以下步骤：

BB-1统计当前节点δ的解中包含的弧(i，j)，并将其添加到集和Δ

BB-2对Δ

BB-3选择流量最接近0.5的弧(i，j)作为分支项f′

BB-4生成节点δ

BB-5算法结束，返回节点δ

进一步地，所述列生成流程CG中的启发式方法HA，其流程如图7示，包括以下步骤：

HA-1初始化返回集合Δ

HA-2分别计算客户i在标准重量θ

HA-3将虚拟成本

HA-4判断k＝0，若满足则转步骤HA-10，否则从集合

HA-5若

HA-6判断路径r

HA-7如果m≤|M|，计算

HA-8若

HA-9若|Δ

HA-10结束算法，返回Δ

在其中一个实施例中，size表示启发式方法HA返回的结果集的大小，实际使用时可依据问题不同进行正交实验选择合适的数值。在其中一个实施例中，遍历选取k个客户得到集合

进一步地，所述列生成流程CG中的确求解算法EA，其流程如图8示，包括以下步骤：

EA-1初始化返回集合Δ

EA-2分别计算客户i在标准重量θ

EA-3将虚拟成本

EA-4判断k＝0，若满足则转步骤EA-12，否则从集合

EA-5若

EA-6判断路径r

EA-7遍历

EA-8计算最小的可用车型

EA-9如果m≤|M|，计算

EA-10若

EA-11若|Δ

EA-12若

EA-13结束算法，返回Δ

为使本算法的流程、技术方案和优点更加清楚，下面将结合算例对本算法的技术方案进行清楚、完整地描述。

假设企业A有10个已知位置和需求地客户需要从发出仓库(编号为0)发出，且各个客户均具有服务时间窗(早到需要等待，不允许晚到)，企业为了满足客户需求，现将物流配送任务外包给物流企业B，该物流企业拥有一支多种车辆地混合车队，此车队拥有2种车辆，数量分别为10，6，容量分别为30、20。已知此物流企业对各个地域运费单价不同，即客户的运输单价不同，详细信息见表2，距离情况详见表3。

同时，由于A企业行业特殊，货品价值及大且要求强监管，要求单个车辆不得运输超过3个客户。此物流企业B有最低重量阶段保证制度，当客户运送物品折算重量没有达到既定标准重量则按照标准重量计费，物流企业B也依据此设定出三个不同的折算标准重量12、10、5。现在需要A企业联合决策车型分配和车辆的路径规划，是的配送系统在能够满足客户需求的同时，最小化物流成本。

表2

表3

对节点1使用进行分支得到的25个方案作为初始解，使用列生成求解此节点的松弛受限主问题L-RMP，求解过程中进行了一次列添加，共添加了8个方案。

r

r

r

r

r

r

r

r

最终求得松弛受限主问题L-RMP最优目标值为：2497.8262；求解得最优解为：ψ

r

r

r

r

r

r

此时解对应的调度方案如图9所示。

本领域的技术人员容易理解，以上所述仅为本发明的较佳实施例而已，并不用以限制本发明，凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等，均应包含在本发明的保护范围之内。