一种兼顾派单效率性与公平性的多目标排程方法与流程

1.本发明属于订单配送技术领域，具体地说，是涉及一种兼顾派单效率性与公平性的多目标排程方法。


背景技术：

2.在企业订单配送的过程中，往往存在企业总成本与员工收益分配之间的矛盾：企业希望让合适的人干合适的事，但这样往往忽略了订单分配给员工时的公平性，极易引发管理性矛盾。
3.现阶段的派单分单仍为人工派单或服务兵相互协调派单的方式，容易出现过多资源匹配不合理，造成资源消耗，且该流程耗费时间过多；而如若在设计“派单+排程”的方案时，只考虑服务的高效性，则很容易造成劳务分配的失衡，较难考虑到服务兵间的工作公平性；
4.服务兵进行配送的排程时，单纯依靠自身经验，有的按照距离的远近决定配送先后顺序，有的按照自身习惯决定配送顺序，这样规划出来的配送路径往往不是最优，且极易因时间消耗大而导致准确率无法确保，从而进一步影响企业的用户口碑及服务兵的服务质量。
5.本背景技术所公开的上述信息仅仅用于增加对本技术背景技术的理解，因此，其可能包括不构成本领域普通技术人员已知的现有技术。


技术实现要素：

6.本发明提出了一种兼顾派单效率性与公平性的多目标排程方法，解决了现有技术只考虑效率因素，造成劳务分配不合理的技术问题。
7.为实现上述发明/设计目的，本发明采用下述技术方案予以实现：
8.与现有技术相比，本发明的优点和积极效果是：一种兼顾派单效率性与公平性的多目标排程方法，考虑网点及服务兵实际需要，在派单时尽量顾及每位服务兵切实感受，以总运输成本为效率目标，以订单满意度的差异最小化作为公平性目标，建立兼顾公平与配送效率的多目标车辆路径规划模型，并利用优化算法获取求解结果，管理者可依据实际需要制定合理的派单排程方案。结合附图阅读本发明的具体实施方式后，本发明的其他特点和优点将变得更加清楚。
附图说明
9.为了更清楚地说明本发明实施例中的技术方案，下面将对实施例中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。
10.图1是本发明所提出的实施例车辆的配送路径规划图；
11.图2是本发明所提出的实施的流程。
12.图3是本发明所提出的实施例pfih算法的流程图；
13.图4是本发明所提出的实施例nsga-ii算法的流程图；图5是本发明所提出的实施例模型求解获得pareto前沿曲线示意图；
14.图6是本发明所提出的实施例pareto曲线中最效率点的车辆路线图与对应的目标函数值；
15.图7是本发明所提出的实施例pareto曲线中最平稳点的车辆路线图与对应的目标函数值；
16.图8是本发明所提出的实施例pareto曲线中最公平点的车辆路线图与对应的目标函数值；
17.图9是现有人工派单机制车辆路线图。
具体实施方式
18.下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。
19.在本发明的描述中，需要理解的是，术语“中心”、“上”、“下”、“前”、“后”、“左”、“右”、“竖直”、“水平”、“顶”、“底”、“内”、“外”等指示的方位或位置关系为基于附图所示的方位或位置关系，仅是为了便于描述本发明和简化描述，而不是指示或暗示所指的装置或元件必须具有特定的方位、以特定的方位构造和操作，因此，不能理解为对本发明的限制。
20.在本发明的描述中，需要说明的是，除非另有明确的规定和限定，术语“安装”、“相连”、“连接”应做广义理解，例如，可以是固定连接，也可以是可拆卸连接，或一体地连接。对于本领域的普通技术人员而言，可以具体情况理解上述术语在本发明中的具体含义。在实施方式的描述中，具体特征、结构、材料或者特点可以在任何的一个或多个实施例或示例中以合适的方式结合。
21.术语“第一”、“第二”仅用于描述目的，而不能理解为指示或暗示相对重要性或者隐含指明所指示的技术特征的数量。由此，限定有“第一”、“第二”的特征可以明示或者隐含地包括一个或者更多个该特征。
22.在本发明的描述中，除非另有说明，“多个”的含义是两个或两个以上。
23.车辆路径规划为一个或多个配送中心，有一定数量的客户，在全部客户和一个或多个配送中心构成的配送网络上，车辆从配送中心出发，根据预先规划好的路线向不同的客户进行服务，最后回到配送中心。
24.在实际配送中，服务兵均倾向于利润高、难度低的订单，但现有派单模式不考虑该因素。为解决上述问题，本发明将服务兵对于每一个订单的满意度量化，并设计考虑公平性的vrptw多目标模型，使服务兵的派单结果在满意度上差别最小。本发明为兼顾订单分配公平性和配送高效性的多目标排程方法。
25.一种兼顾派单效率性与公平性的多目标排程方法：
26.获取订单信息和服务兵数据信息。
27.根据上述信息，提取车辆路径规划模型参数和订单满意度评价参数。
28.计算每个服务兵对每个订单i的订单满意度pi。
29.根据多目标车辆路径规划模型得到优化结果，多目标车辆路径规划模型包括车辆路径规划目标和订单满意度差异目标。
30.根据优化结果制定派单排程方案，根据实际需求进行方案选择。
31.其中，订单信息包括以下六个属性：地理位置、货量需求、最早服务时间、最晚服务时间、完成该订单所需的服务时间以及完成该订单所得的利润。
32.服务兵信息包括服务兵擅长配送或安装的货物种类、服务兵驾驶的车辆信息，包括容量、油耗等。
33.具体流程如图2所示。
34.车辆路径规划模型为带时间窗的车辆路径规划模型。
35.带时间窗的车辆路径规划(vehicle routing problems with time windows,vrptw)问题为：有一定数量的客户，每个客户有不同的货量需求和时间要求。在全部客户和一个或多个配送中心构成的配送网络上，车辆从配送中心出发，根据预先规划好的路线向不同的客户进行服务，最后回到配送中心。
36.车辆需要对所有的客户订单进行服务。每一个客户订单只能被一辆车服务，车辆服务开始时间必须在客户订单时间窗之内。若车辆早于时间窗开始时间到达客户位置，则车辆必须停止等待；若车辆晚于时间窗结束时间到达客户位置，则该客户不能被服务。同时，车辆在服务过程中的货量不能超过车辆最大容量。所有车辆都是从同一配送中心出发，配送中心也有一个时间窗，所有车辆必须在该时间窗内完成所有货物的配送。车辆的配送流程如图1所示。
37.本实施例的关键在于计算每个服务兵对每个订单i的订单满意度pi，建立订单满意度差异模型。
38.订单满意度pi根据服务兵收益和订单服务难度确定。
39.订单满意度pi＝w1*服务兵收益+w2*订单服务难度，其中，w1和w2为事先确定的权重。w1+w2＝1。
40.服务兵收益根据配送收入、配送距离和服务时间确定；订单服务难度根据装卸难度、时间约束和客户点硬件设施确定。
41.服务兵收益＝w11*配送收入+w12*配送距离+w13*服务时间，其中，w11、w12和w13为事先确定的权重。w11+w12+w13＝1
42.配送收入可以根据企业的收入规则进行确定。
43.配送距离可根据订单信息进行计算。
44.服务时间可根据实际产品的若干实际安装时间确定。
45.订单服务难度＝w21*装卸难度+w22*时间约束+w23*客户点硬件设施，其中，w21、w22和w23为事先确定的权重。w21+w22+w23＝1。
46.装卸难度主要与产品的尺寸和重量有关，但是不同的家电有不同的品牌，对应有不同的尺寸和重量。所以为了方便统计和计算，把配送量较大的产品分为轻、中、重三个量级。
47.如下表1所示：
48.表1装卸难度分级表
[0049][0050]
时间约束指的是在服务兵配送订单时，服务兵是否会因为时间有限而加快自己的配送速度。因此这项指标主要与配送距离和允许配送时间之比，也就是最低配送速度有关。利用下面的公式计算出每个订单的最低允许配送速度：
[0051]vi
＝运送距离/(要求送达时间-出库时间)
ꢀꢀ
(1)
[0052]
由于硬件设施的相关数据和资料难以获取，但是其对于订单质量的评价却有很大的关系。例如在实际情况中，配送地的小区是否安装电梯会极大地影响服务兵在中高楼层的服务。
[0053]
针对硬件设施得分的计算，由于硬件设施多数情况都是客户的居住环境，因此，采用随机数来表示硬件设施的得分，具体公式如下：
[0054]b4i
＝random(0,1)
ꢀꢀ
(2)
[0055]
订单满意度pi的确定指标判断是否需要量化，对于需要量化的指标，根据指标特性进行量化后利用优劣距离法计算得分，对于不需要量化的指标利用优劣距离法计算得分。计算总得分即为订单满意度pi。
[0056]
根据对相关工作人员的采访以及问卷数据，得到服务兵对订单满意度的判断依据。在订单数据分析时，本团队一共设立了六个小指标并且六个指标之间没有明显的权重差别，说明这六个指标时都需要考虑在内的。为了更好的分析服务兵的需求，在六个二级指标上的基础上建立了两个一级指标。这样的指标体系一方面能分析利润和服务难度对订单质量的影响，另一方面将小指标归类，更有层次性便于后续的优化和更改。
[0057]
多目标车辆路径规划模型如下：
[0058]
车辆路径规划目标minz1＝σ
i∈n
σ
j∈n
σ
k∈kcij
x
ijk
ꢀꢀ
(3)；
[0059]
订单满意度最小差异目标minz2＝σ
k∈k
σ
g∈k,g＞k
|σ
i∈v
∑
j∈v
x
ijk
p
i-σ
i∈v
σ
j∈v
x
ijg
pi|(4)；
[0060][0061][0062][0063][0064]
[0065][0066][0067][0068][0069]
其中，k为服务兵(车辆)集合，索引为k∈k,g∈k，且g＞k表示两个不同服务兵(车辆)；
[0070]
n为网络节点的集合；
[0071]
e为网络弧的集合；
[0072]
v为客户节点的集合，且n＝v∪{o}；
[0073]
o为配送中心；
[0074]cij
为节点i与节点j之间的距离，
[0075]
si为完成客户点i的任务所需的时间，
[0076]
t
ij
为经过弧(i,j)所需的时间，
[0077]ei
为客户点i的服务窗开始时间，
[0078]
ui为客户点i的服务窗结束时间，
[0079]
x
ij
为0-1变量，若车辆经过弧(i,j)为1，否则为0；
[0080]
x
ijk
为0-1变量，若服务兵(车辆)k由点i经由点j则为1，否则为0；ti为非负变量，表示车辆在客户点i的开始服务时间；
[0081]
其中，目标式(17)表示运输路径总成本最小化目标；式(18)表示订单满意度差异最小化目标。
[0082]
式(19)为流平衡约束，确保每一辆车的路径是连续的；式(20)和式(21)确保每一辆车从配送中心出发，服务完所有的客户后返回配送中心；式(22)表示被服务的相邻节点开始服务时间的大小关系；式(23)表示车辆在每一个客户的开始服务时间必须位于该客户的时间窗内；式(24)保证每一个客户订单被一辆车服务；式(25)表示车的载货量不能超过车的最大允许载货量；式(26)和式(27)为变量约束。
[0083]
本实施例使用启发式算法，来寻找一组质量较高的可行解作为元启发式算法的初始解。同时为了保持种群的多样性，在启发式算法中加入随机因素，即在较优秀的备选客户中随机选择种子客户和未分配客户。本实施例采用的是改进的基于前向插入的启发式(push-forward insertion heuristic，pfih)算法，如图3所示，算法的基本步骤为：
[0084]
s1、新建一条空路径；
[0085]
s2、根据种子客户费用函数(式28)在所有未分配客户中选择一个费用较小的客户作为种子，插入到s1中的路径；
[0086]
s3、未分配客户在当前路径中是否有可行的插入点，若是，进入步骤s4，否则，进入步骤s5；
[0087]
s4、根据插入费用函数(式29)计算插入费用，选择插入费用较小的未分配客户，将
其插入到s1中的路径；进入s3；
[0088]
s5、是否还有未分配客户，若是，进入s1；否则，得到初始解
[0089]
对于待插入空路径的客户i，种子客户费用函数设定为：
[0090][0091]
其中pi是客户i相对于配送中心的极角，pj是上一条车辆路径的最后一个被服务客户相j对于配送中心的极角，t
ij
为车辆k在路径《i,j》的行驶时间，li为客户i的最晚开始服务时间；
[0092]
对于待插入弧《i,j》的客户w，插入费用函数由四部分组成，分别为附加路径成本、服务成本、风险成本；
[0093][0094]
其中，c
ij
为弧《i,j》上的路径成本，st为服务时间，vj为当前路径上j以及j后续客户节点的集合，l
σ
为客户σ的最晚开始服务时间，a
σ
为客户σ的开始服务时间。
[0095]
对多目标车辆路径规划模型采用多目标优化算法nsga-ii进行优化求解得到优化结果。
[0096]
具体算法如图4所示。
[0097]
以某地区8600000295号网点的真实运营数据为依据，对该网点某日的38个订单作为算例进行测试，所获得pareto前沿曲线如图5所示，可以看到最优解所呈现的图像向右下方倾斜，表示解集中的所有解互不支配，说明求解得出的最优解是可靠的。
[0098]
图6、图7、图8分别展示了pareto曲线中最效率点、最平稳点与最公平点的车辆路线图与对应的目标函数值。最效率点对应的解的距离为151.061km，服务兵订单得分之间的差距为0.557；最平稳点对应的解的距离为156.935km，服务兵订单得分之间的差距为0.146；最公平点对应的解的距离为188.552km，服务兵订单得分之间的差距为0.032。
[0099]
图9为现有人工派单机制车辆路线图，造成了运力资源的浪费以及劳务分配的失衡。下表2为真实运行路径展示：
[0100]
表2现有技术网点真实运营路径展示
[0101][0102]
pareto曲线所求得的解在距离和服务兵订单得分之间的差距两方面均优于该网点的真实运营水平。以最稳定解为例，优化后的解的距离为156.935km，服务兵订单得分之间的差距为0.146；对比真实的运营数据，其距离为187.512km，服务兵订单得分之间的差距为2.178；优化后距离降低了16.3％，服务兵得分之间的差距降低了93.3％，证明算法求解得到的最优解是有效的。优化后该网点的服务兵订单分配情况与排程情况，如下表3所示：
[0103]
表3pareto曲线最平稳点对应路径展示
[0104][0105]
以上实施例仅用以说明本发明的技术方案，而非对其进行限制；尽管参照前述实施例对本发明进行了详细的说明，对于本领域的普通技术人员来说，依然可以对前述实施
例所记载的技术方案进行修改，或者对其中部分技术特征进行等同替换；而这些修改或替换，并不使相应技术方案的本质脱离本发明所要求保护的技术方案的精神和范围。

技术特征：
1.一种兼顾派单效率性与公平性的多目标排程方法，其特征在于，所述方法为：1)获取订单信息和服务兵数据信息；2)根据所述信息，提取车辆路径规划模型参数和订单满意度评价参数；3)计算每个服务兵对每个订单i的订单满意度pi；4)根据多目标车辆路径规划模型得到优化结果，所述多目标车辆路径规划模型包括车辆路径规划目标和订单满意度最小差异目标；5)根据所述优化结果制定派单排程方案，根据实际需求进行方案选择。2.根据权利要求1所述的兼顾派单效率性与公平性的多目标排程方法，其特征在于，所述订单满意度最小差异目标其中，v为客户节点的集合，且n＝v∪{o}；为网络节点集合k为服务兵(车辆)集合，索引为k∈k,g∈k，且g＞k表示两个不同服务兵(车辆)；p
i
为订单i的服务兵满意度；x
ijk
为0-1变量，若服务兵(车辆)k由点i经由点j则为1，否则为0。3.根据权利要求1所述的兼顾派单效率性与公平性的多目标排程方法，其特征在于，所述订单满意度pi根据服务兵收益和订单服务难度确定。4.根据权利要求3所述的兼顾派单效率性与公平性的多目标排程方法，其特征在于，所述订单满意度pi＝w1*服务兵收益+w2*订单服务难度，其中，w1和w2为事先确定的权重。5.根据权利要求3所述的兼顾派单效率性与公平性的多目标排程方法，其特征在于，所述服务兵收益根据配送收入、配送距离和服务时间确定；所述订单服务难度根据装卸难度、时间约束和客户点硬件设施确定。6.根据权利要求5所述的兼顾派单效率性与公平性的多目标排程方法，其特征在于，所述服务兵收益＝w11*配送收入+w12*配送距离+w13*服务时间，其中，w11、w12和w13为事先确定的权重；所述订单服务难度＝w21*装卸难度+w22*时间约束+w23*客户点硬件设施，其中，w21、w22和w23为事先确定的权重。7.根据权利要求1所述的兼顾派单效率性与公平性的多目标排程方法，其特征在于，所述车辆路径规划目标为带时间窗的车辆路径规划目标。8.根据权利要求7所述的兼顾派单效率性与公平性的多目标排程方法，其特征在于，所述多目标车辆路径规划模型：述多目标车辆路径规划模型：述多目标车辆路径规划模型：
其中，n为网络节点的集合；e为网络弧的集合；v为客户节点的集合，且n＝v∪{o}；o为配送中心；c
ij
为节点i与节点j之间的距离，s
i
为完成客户点i的任务所需的时间，t
ij
为经过弧(i,j)所需的时间，e
i
为客户点i的服务窗开始时间，u
i
为客户点i的服务窗结束时间，x
ijk
为0-1变量，若服务兵(车辆)k经过弧(i,j)为1，否则为0；t
i
为非负变量，表示车辆在客户点i的开始服务时间；式(4)为流平衡约束，确保每一辆车的路径是连续的；式(5)和式(6)确保每一辆车从配送中心出发，服务完所有的客户后返回配送中心；式(7)表示被服务的相邻节点开始服务时间的大小关系；式(8)表示车辆在每一个客户的开始服务时间必须位于该客户的时间窗内；式(9)保证每一个客户订单被一辆车服务；式(10)表示车的载货量不能超过车的最大允许载货量；式(11)和式(12)为变量约束。9.根据权利要求1所述的兼顾派单效率性与公平性的多目标排程方法，其特征在于，所述多目标车辆路径规划模型使用pfih算法产生初始解：s1、新建一条空路径；s2、根据种子客户费用函数(式15)在所有未分配客户中选择一个费用较小的客户作为种子，插入到s1中的路径；s3、未分配客户在当前路径中是否有可行的插入点，若是，进入步骤s4，否则，进入步骤s5；s4、根据插入费用函数(式16)计算插入费用，选择插入费用较小的未分配客户，将其插
入到s1中的路径；进入s3；s5、是否还有未分配客户，若是，进入s1；否则，得到初始解对于待插入空路径的客户i，种子客户费用函数设定为：其中p
i
是客户i相对于配送中心的极角，p
j
是上一条车辆路径的最后一个被服务客户相j对于配送中心的极角，t
ij
为车辆k在路径<i,j>的行驶时间，l
i
客户i的最晚开始服务时间；对于待插入弧<i,j>的客户w，插入费用函数由四部分组成，分别为附加路径成本、服务成本、风险成本；其中c
ij
为弧<i,j>上的路径成本，st为服务时间，v
j
为当前路径上j以及j后续客户节点的集合，l
σ
为客户σ的最晚开始服务时间，a
σ
为客户σ的开始服务时间。10.根据权利要求1所述的兼顾派单效率性与公平性的多目标排程方法，其特征在于，对所述多目标车辆路径规划模型采用多目标优化算法nsga-ii进行优化求解得到优化结果。

技术总结
本发明公开了一种兼顾派单效率性与公平性的多目标排程方法，考虑网点及服务兵实际需要，在派单时尽量顾及每位服务兵切实感受，以总运输成本为效率目标，以订单满意度的差异最小化作为公平性目标，建立兼顾公平与配送效率的多目标车辆路径规划模型，并利用优化算法获取求解结果，管理者可依据实际需要制定合理的派单排程方案。派单排程方案。派单排程方案。


技术研发人员：于永斌 范宣勇 员丽芬 黄世鸿 王卫清 郭志伟 马筠斐 崔林 汪思妤 朱泓屹 余润峰 刘妍希
受保护的技术使用者：日日顺供应链科技股份有限公司
技术研发日：2023.03.31
技术公布日：2023/8/5