考虑匹配均衡性的供需双方多对多双边匹配决策方法

王 娜 ，李引珍 ，柴 获

（1. 兰州交通大学机电工程学院, 兰州730070；2. 兰州交通大学交通运输学院, 兰州730070）

随着我国交通行业和互联网信息技术的快速发展，物流服务信息化水平和专业能力得到了大幅度提高. 物流服务行业的迅速发展，有助于提升产品的运输效率，降低企业物流成本，提升企业自身的核心竞争力. 在激烈的竞争中，物流服务需求方的目标是用最低的成本获得最满意的物流服务，而物流服务供给方要在物流需求方满意的同时追求较高的利润，供需双方的交易是典型的不交叉关系，两者的匹配决策为自主自愿的市场化运作，其合作特征符合双边匹配理论基本要求，适用双边匹配理论和匹配决策方法进行研究分析.

在物流服务供需双边匹配决策问题中，通常物流服务供需匹配的供方或需方需要对对方做出一定的偏好排序，即供给方或需求方需要具备对对方的“敏感性偏好”，在该问题的研究中，根据供需双方各自的评价指标给出完全偏好序信息是常见的研究方法. 因此，基于完全偏好序的双边匹配问题研究备受关注，樊治平等[1]在基于完全偏好序信息的一对一双边匹配问题中,以双边主体的匹配满意度最大构建了多目标优化模型，利用双边主体的最高可接受偏好序算法进行求解获得匹配结果. 孔德财等[2]针对一对一双边匹配问题，考虑匹配的稳定性、公平性和满意性，以匹配主体的满意度最大及匹配主体间的满意度绝对差异最小建立了多目标优化模型. 姜艳萍等[3]针对基于偏好序的双边匹配问题,提出了具有抗操作和抗自亏性的匹配方法.张笛等[4]在考虑匹配特征基础上，提出了多重偏好下的一对一多阶段双边匹配方法. Dalzell等[5]认为当用于匹配的分类变量有误差时，可以同时估计回归模型和匹配记录，提出了一种贝叶斯匹配方法.Li等[6]提出了一种基于双重犹豫模糊偏好信息的一对一双边匹配方法，在稳定匹配约束下，以双方的满意度最大、差异度最小建立多目标优化模型.Yu等[7]针对人事岗位匹配问题提出了新的直觉模糊Choquet积分聚2集算子，构建了一个直观的模糊一对一双边匹配模型. 李铭洋等[8]针对基于序值偏好信息的一对多双边匹配问題构建了以匹配主体序值之和最小为目标的多目标优化模型.Zhang等[9]对多对多双边匹配的匹配因素进行了研究，构建了一种顺序联结反应模型. Chen等[10]研究了弱偏好序的多对多双边匹配问题，提出了一种新的Pareto稳定匹配算法. Klaus等[11]利用两阶段非揭示机制研究了多对多匹配问题. Zhang等[12]提出了一种基于失望理论的不完全模糊偏好序一对一双边匹配决策理论，构建了确定最佳匹配解的双目标优化模型. Jiao等[13]考虑了多对多双边匹配中的激励相容性问题. Fan等[14]考虑心理因素将预期的各代理对相对代理的偏好序数基于不确定偏好序数计算，根据失望理论得到可能的匹配结果.Chen等[15]提出了一种根据参与者的主观偏好修正一些关键目标，有效地提高了双边参与者的满意度.林杨等[16-19]也进行了相应的研究.

既有文献对一对一、多对多双边匹配问题进行了一定的研究，主要从整体满意度角度考虑匹配主体进行匹配，而对匹配主体中个体的满意度及其均衡性较少涉及，个体满意度未得到充分满足，很难保证匹配的公平性. 在保证整体满意度前提下，考虑双边匹配主体中个体在匹配中的满意度，主体中个体的匹配满意度较均衡时才能达到公平的双边匹配.鉴于此，本文充分考虑整体满意度和个体满意度，构建基于完全偏好序物流服务供需多对多双边匹配两阶段优化模型，并基于NSGA-Ⅱ（non-dominated sorting genetic algorithm-Ⅱ）和线性规划方法设计模型求解算法.

1 问题描述

假设所有物流服务供需双方都要接受决策者的指令，决策者给出多种匹配方案后，物流服务供需方根据各自不同的偏好选择匹配方案. 假设在物流服务供需双方数量充足的情况下，物流服务需求方其集合为A={A1,A2,···,Am}（+m≥2），Ai表示第i个物流服务需求方，i=1,2,···,m；物流服务供给方其集合 为B={B1,B2,···,Bn}（+n≥2) ，Bj表 示 第j个 物 流服 务 供 给 方，j=1,2,···,n. 则I={1,2,···,m} ，J={1,2,···,n} . 设Ri=(ri1,ri2,···,rin) 为需求方Ai给出的关于供应方B的偏好序向量，其中rij为需求方Ai把供应方Bj排在第rij位. 设Tj=(t1j,t2j,···,tmj)为供应方Bj给出的关于需求方A偏好序向量，其中tij为需求方Bj把供给方Ai排在第tij位.

1.1 参数和变量定义

基于完全偏好序的物流服务供需双边匹配模型中的相关参数与变量定义如下：

αij——第i个物流服务需求方Ai对第j个物流服务供应方Bj的满意度；

βij——第j个物流服务供应方Bj对第i个物流服务需求方Ai的满意度；

pi——与第i个物流服务需求方匹配的供应方最大个数；

qj——与第j个物流服务供应方匹配的需求方最大个数；

hi— —与第i个物流服务需求方匹配的供应方个数；

lj— —与第j个物流服务供应方匹配的需求方个数；

xij——第i个物流服务需求方Ai与第j个物流服务供应方Bj匹配，0-1变量，其中xij= 0表示Ai与Bj不匹配，xij= 1表示Ai与Bj匹配.

1.2 物流服务供需方满意度

αij和 βij的表达式如下：

式中：l(•) 和g(•) 均为单调递减函数.

按照完全偏好序的物流服务供需方双边匹配问题的描述，本文规定物流服务供需双方偏好序的倒数即为物流服务供需双方对对方的满意度，则满意度 αij和 βij可分别表示为

基于完全偏好序向量Ri和Tj，分别建立完全偏好序矩阵与. 依据式（1）和式（2），完全偏好序矩阵R与T分别转化为完全满意度值矩阵与

2 模型构建

本文构建多对多物流服务供需双边匹配两阶段优化模型，第1阶段以物流服务需求方的整体满意度最大及物流服务需求方个体满意度的方差最小构建匹配模型（同理建立物流服务供给方匹配模型），利用遗传算法进行模型求解得到物流服务供需方理想点的双边匹配Pareto解集；第2阶段构建以供需双方满意度与理想点满意度差最小的多目标优化模型，利用遗传算法进行模型求解得到双边匹配Pareto解集.

2.1 第1阶段优化模型

1） 针对物流服务需求方A，依据满意度值矩阵以物流需求方整体满意度及个体满意度为优化目标，令为物流服务需求方的个体满意度平均值.

构建第1阶段物流服务需求方优化模型1：

第1阶段物流服务需求方优化模型1，只考虑物流服务需求方主体A总体满意度和物流服务需求方Ai个体满意度方差. 式（3）、（4）为目标函数；式（3）表示在严格双边匹配意义下最大化物流服务需求方主体A关于物流服务供给方主体匹配的总体满意度，式（4）表示在严格双边匹配意义下物流服务需求方个体Ai与供给方个体Bj匹配，Ai的个体满意度方差最小；式（5）表示每个物流服务需求方主体可以与多个物流服务供应方主体匹配；式（6）表示每个物流服务供给方主体可以与多个物流服务需求方主体匹配；式（7）保证物流服务需求方个体Ai匹配的供应方不是最差匹配（例如，与需求方A1匹配的供应方数量是2个，这2个供应方不能是需求方A1在满意度排序中最后两位的供应方），其中；式（8）保证物流服务供给方个体Bj匹配的需求方不是最差匹配，其中

2） 针对物流服务供给方B，依据满意度值矩阵以物流供给方整体满意度及个体满意度为优化目标，令为物流服务供给方的满意度平均值.

构建第1阶段物流服务供给方优化模型2，模型2只考虑物流服务供给方主体B总体满意度和物流服务需求方Bj个体满意度方差，与模型1类似，这里不再赘述.

2.2 第2阶段优化模型

第2阶段模型中，考虑物流服务供需主体的整体满意度与供需双方在匹配时理想值的差值最小.构建第2阶段优化模型3：

3 模型求解

3.1 第1阶段模型求解

模型1为双目标非线性0-1规划问题，优化目标分别为整体满意度Z1和个体满意度Z2，由于Z2为非线性表达式，因此，该问题没有精确算法. 解决此类问题的最好方法是基于NSGA-Ⅱ的多目标优化算法[20]. 本文将从以下3个方面进行算法设计.

1） 个体编码

如图1所示，个体采用多层0-1编码，总长度为m×n，第i行第j列的编码值如果为1表示需求方i和供应方j匹配，否则为两者不匹配. 对于第i行编码，其和必须小于等于pi，表示与物流服务需求方Ai匹配的供给方个数最多不超pi；同理，对于第j列编码，其和必须小于等于qj.

图1 个体编码Fig. 1 Individual encoding

2） 适应度函数

针对物流服务需求方，Z1为整体满意度，优化目标为整体满意度最大，可采用 1 /Z1作为该目标的适应度函数，Z2为个体满意度，优化目标为个体满意度差异最小，可采用Z2直接作为该目标的适应度函数.

3） 种群进化策略

一般情况下，通过交叉获得新个体的方法来保证在进化过程中群体多样性. 由于本模型中个体的行和列均有约束，个体的合法性采用惯常的交叉方法无法得到保证，基于上述考虑，设计一种能够满足模型中约束条件的行（列）交叉算子，计算步骤如下：

步骤1随机选中两个父个体，交换其奇数行（列）生成两个子个体；

步骤2针对每一个子个体，从0到n（m）循环检查其第j列（第i行）是否满足条件

如果全部满足，则所有子个体均为合法个体；

步骤3对于非法个体，选择不满足步骤2中条件的列（行），定位其奇数行中第1 次出现元素1的行列值，尝试与本行（列）第1个元素0交换位置，交换后分别检查交换列（行）是否满足步骤2中条件，如果满足，则修正后的子个体合法，如果不满足，重新尝试与本行（列）其他元素0交换位置，再次检查，直到条件满足.

以某物流供需服务为例，共有4个物流服务需求方和6个物流服务供给方，4个物流服务方可匹配的供给方个数分别不超过2、3、2、2，6个物流服务供给方可匹配的需求方个数分别不超过2、2、2、2、2、1. 以如图2所示两个父个体的行交叉为例，首先将父个体1和父个体2的第1、3行交换，生成子个体1和子个体2，下一步分别检查子个体1和子个体2的合法性.

图2 行交叉示例Fig. 2 Example of row-cross operator

对于子个体1，第6列的元素和为2，不满足可匹配的需求方个数约束，需要进行修正，第6列第1个元素1出现在第1行，首先与第1行第2列的元素0交换，交换后分别检查第2列和第6列，第6列元素和为1，满足要求，但第2列元素和为3，不满足可匹配的需求方个数约束，再次尝试第1行第3列的元素0交换，交换后分别检查第3列和第6列，均满足可匹配的需求方个数约束，子个体1合法. 同理，对于子个体2，行交叉后也不满足可匹配的需求方个数约束，将第3列第3行的元素1和第1列第3行的元素0交换后，个体合法.

为防止早熟收敛，在交叉的基础上引入适度的变异. 变异操作采用行（列）交换变异法得到新个体，核心思想是随机选择个体，同时基于随机方法选择两行（列），将被选个体的选中行进行交换，生成一个新个体，并检查个体的合法性. 如果个体非法，从导致个体非法的行中找到第1个元素1，与被交换行中的相同位置元素交换位置，交换后分别检查交换列（行）是否满足步骤2中条件，如果满足，则修正后的子个体合法，如果不满足，继续在导致个体非法的行中查找元素1，与被交换行中的相同位置元素交换位置，再次检查，直到条件满足.

以图3所示个体为例，选中个体的2、3行，进行交换，交换后第2行满足可匹配的需求方个数约束，但第3行元素之和为3，不满足可匹配的需求方个数约束，在第3行中查找第1个元素1，其位于第3行第1列，与第2行第1列元素进行交换，交换后2、3行同时满足可匹配的需求方个数约束，个体合法.

3.2 第2阶段模型求解

针对第1阶段优化得到的Pareto最优解中，根据对整体满意度和个体满意度的偏好，供需双方决策者分别选择合理的整体满意度作为第2阶段模型的理想点和，多目标函数的最优值与理想点的距离越接近越好，利用线性规划方法求解.

加权将多目标优化模型转化为单目标优化模型4：

在现实的物流服务双边匹配问题中,ε 和1−ε可被分别视为物流供需双方主体的重要程度，通常由中介依据物流供需双边主体的地位来考虑如何确定权重. 若认为物流供需双边主体在匹配过程中处于平等地位，则有 ε= 0.5. 若认为物流供需双边主体在匹配过程中的地位不同，即一方主体与另一方主体相比在匹配过程中显得更重要，则有 0 ≤ε≤1，ε 取值从0.0001～1.0000，以步长0.0001循环，通过线性规划方法进行求解，可获得多对多物流服务供需双边匹配的Pareto解集.

4 算例分析

某 地 区 的 中 介 公 司 收 到(A1,A2,A3,A4,A5,A6)6个物流服务外包公司的相关需求信息，而中介公司里有(B1,B2,B3,B4,B5) 5个物流企业的信息. 相关供需双方的满意度排序见表1和2.

针对表1和表2的排序信息，假设每个物流服务需求方A可选择服务供应方最大数量分别为2、3、2、4、2、1，而物流服务供应方B可向需求方提供匹配的最大数量为3、2、2、2、1. 根据求解方法，在第1阶段考虑个体满意度，分别针对需求方A和供给方B进行优化，可分别获得供需双方的整体满意度和个体满意度Pareto前沿（如图4、5所示）.

表2 供给方B对需求方A的排序Tab. 2 Preference list of supplyB versus demandA

图4 需求方A的整体满意度与个体满意度Pareto最优前沿Fig. 4 Pareto optimal front of overall satisfaction and individual satisfaction of demandA

假设需求方A和供给方B可接受的个体满意度阈值均为0.22，则供需双方可选择的方案如图4、5所示，供需双方整体满意度的理想点为5.98和5.23，在此理想点下，根据基于理想点的模型求解方法，可获得如图6所示的整体满意度Pareto最优前沿.

对于图6中整体满意度Pareto最优解，可获得需求方A对供给方B间的匹配关系，假设供需双方可接受的整体满意度值为(5.93,5.20)，则匹配关系如图7所示.

图5 供应方B的整体满意度与个体满意度Pareto最优前沿Fig. 5 Pareto optimal front of overall satisfaction and individual satisfaction of supplyB

图6 供需双方个体满意度限制下的整体满意度Pareto前沿Fig. 6 Pareto optimal front of overall satisfaction constrained by individual satisfactions of supply and demand sides

图7 供需双方整体满意度为(5.93,5.20)下的匹配关系Fig. 7 Matching results of supply and demand sides with overall satisfaction (5.93,5.20)

当不考虑个体满意度时，可以构建多对多物流服务供需双边匹配整体满意度优化模型，以供需双方匹配满意度最大为目标函数的多目标优化模型，求解中先求出物流服务供需双方不考虑对方满意度的情况下自身的理想点满意度，再通过物流服务供需双方实际最大满意度与理想点满意度的差距最小建立多目标优化模型，利用线性规划方法进行模型求解得到双边匹配Pareto解集. 基于NSGA-Ⅱ的多目标优化算法获得整体满意度和个体满意度的Pareto解，为决策者提供了体现整体和个体满意度不同偏好的决策方案，指导决策者获得供需双方满意的匹配关系.

根据基于理想点法对算例求解，其理想点为(7.33,6.75)，可获得如图8所示的整体满意度Pareto最优前沿.

图8 供需双方整体满意度Pareto前沿Fig. 8 Pareto optimal front of overall satisfaction of supply and demand sides

从图8中可以看出：需求方A对供给方B的整体满意度和B对需求方A的整体满意度是此消彼长的关系，即需求方A对供给方B取最大整体满意度时，供给方B对需求方A的整体满意度最低，因此，在决策过程中，需要供需双方谈判以获得彼此可接受的满意度.

对于图8中任意解，可获得需求方A对供给方B间的匹配关系，如供需双方可接受的满意度值为(5.10,6.75)，则匹配关系如图9所示. 在此匹配关系下，需求方A和供给方B的个体满意度方差分别0.57和0.22，个体满意度越小，表示个体之间的差异越小，对于本方案，需求方A的个体满意度差异较大，选择此方案导致需求方之间满意度不公平，容易导致矛盾产生.

图9 供需双方整体满意度为(5.10,6.75)下的匹配关系Fig. 9 Matching results of supply and demand sides with overall satisfaction (5.10, 6.75)

由图6与图8的Pareto前沿对比可以看出：考虑个体满意度差异的情况下得到的整体满意度明显劣于未考虑个体满意度的情况，相对未考虑个体满意度情况，引入个体满意度时会导致双方整体满意度下降，即为使每个个体能够得到满意、公平的匹配结果，需要牺牲双方的整体的满意度. 表明考虑个体满意度最优时，整体满意度会受到一定的影响，但其结果更贴近现实情况，并能得到公平的匹配结果，因为个体满意度离理想点越近，匹配结果越接近个体对匹配结果的期望.

5 结 论

本文中同时考虑整体满意度和个体满意度均衡性的供需双方多对多双边匹配两阶段优化模型，能够刻画物流服务中供需双方的利益关系，既能考虑物流服务供需方整体满意度，又兼顾供需方匹配个体满意度的均衡性. 后续研究将考虑物流服务供需方个体差异化和优先级的稳定匹配问题，以提高实用性和适应性.