考虑单一优化目标的双边匹配方法的优化

（1）考虑稳定性的双边匹配方法

Roth（1982）[39]以婚姻匹配问题为背景研究了匹配问题和匹配过程中的几个博弈问题，研究结果表明不存在一个能够产生稳定匹配并且使双方匹配参与者有动机揭示真实偏好的匹配过程；确实存在一个能够产生稳定匹配结果并且能够保证一方匹配参与者有动机揭示真实偏好的匹配过程。Aldershof和Carducci（1999）[276]针对两个不同的岗位申请者与雇主双边匹配问题，提出了两个获得岗位申请者与雇主稳定匹配的遗传算法。在遗传算法解决的两个双边匹配问题中，岗位申请者和雇主给出的偏好列表都是部分偏好列表，其中第1个双边匹配问题中岗位申请者和雇主的偏好是不关联的，而第2个双边匹配问题允许成对的岗位申请者提交成对雇主的联合偏好序。Yuan和Wang（1996）[277]提出了最大选择神经元和最大中断神经元，并用这两种最大神经元构建了一个神经网络来表示和解决稳定匹配问题，研究表明神经网络方法允许匹配在分布式环境下被动态的实现，并且匹配神经网络具有很高的鲁棒性。Manlove等（2007）[278]通过直接CSP编码将医院与实习生的匹配问题转换为CSP问题，然后采用弧相容算法（AC）进行求解，指出对于可交换稳定匹配问题、禁止对问题及群组稳定匹配问题，采用这个模型很容易进行求解，但是对于具有无差异偏好的HR问题可以对模型进行扩展求解。Gent等（2001）[279]研究了具有广泛实际应用价值的稳定婚姻匹配问题，提出了将稳定婚姻匹配问题转化为约束满足问题的两种编码方式，证明了建立弧一致等同于构建扩展Gale-Shapley算法，可以快速获得男士最优和女士最优稳定匹配，并且通过这两种编码方式可以很容易地枚举所有的稳定匹配。Manlove和O’Malley（2005）[280]研究了具有无差异偏好信息的稳定婚姻匹配问题，提出了两个将稳定婚姻问题转化为约束满足问题的模型，采用第一种编码方式建立弧一致的时间复杂度要劣于扩展Gale-Shapley算法，第二种编码方式的时间复杂度是最优的，并且采用两种编码方式不用搜索就可以获得稳定婚姻匹配问题的所有稳定匹配。Bistarelli等（2008）[281]将婚姻问题中的最优稳定婚姻问题表示为一个软约束满足问题，为了定义新的联盟形成准则和稳定条件，将成对个体扩展到普通代理联盟，并采用基于半环的软约束方式来表达一个能够处理不同最优概念的框架，而无须采用不同的专用算法。Gelain等（2010）[282]提出了一个用于求解一般稳定匹配问题的局部搜索启发式算法，该算法通过随机方式或启发式方式产生一个初始匹配方案，通过不断迭代删除不稳定对，直至找到稳定匹配方案，模拟实验表明对于具有严格偏好序和完全偏好列表的双边匹配问题（SM），局部搜索启发式算法的时间复杂度为O（n log（n）），表明它是产生稳定婚姻匹配的有效方法；对于具有无差异偏好和部分偏好列表的双边匹配问题（SMTI），实验结果表明尽管获得具有最大匹配对数量的稳定匹配是一个NP-hard问题，而局部搜索启发式算法即便对于大规模SMTI问题仍然能够快速地获得稳定匹配对数量比较大并且经常获得最优规模的稳定匹配。Eirinakis等（2007）[283]将大学录取问题转化为约束满足问题，提出了一个基于超弧一致的获取所有稳定对的算法，该算法的时间复杂度为O（n2），通过随机产生的算例计算表明超弧一致能够在合理的时间内大幅度实现论域缩减。Eirinakis等（2012）[284]以工作市场中工人与企业的多对多双边匹配为背景，提出了识别所有的工人和企业稳定对以及所有的稳定匹配方案的时间最优算法，并将多对多的双边匹配问题编码并转化为约束满足问题，通过一系列算例计算表明了约束满足方法的有效性。Unsworth（2008）[285]研究了婚姻匹配问题和医院与实习生匹配问题中将稳定匹配问题建模为专用约束的问题，开发了能够显著提高算法性能的专用约束解，实证研究表明与以往约束解相比，这些专用约束解能够解决大规模的双边匹配问题。Unsworth和Prosser（2013）[286]采用约束规划方法研究了具有不完全偏好列表的稳定婚姻问题，提出了一个时间复杂度为O（n2）的特殊的n-弧约束，虽然在理论上该约束与以往最优约束具有相同的时间复杂度，但是计算实验表明该约束在求解大规模问题方面求解效率更高，也更加实用。

张振华等（2008）[287]针对电子中介中的买卖交易匹配问题，考虑商品的多属性，给出了交易者按综合满意成对对满足自己约束对方的排序计算法方法，将Gale-Shapley和H-R算法从理论上扩展到“p-k”情况，用来解决电子处理稳定的多对多双边匹配问题，并证明了扩展算法所得结果的稳定性。刘永强等（2011）[288]针对多属性双边匹配问题，给出了多属性匹配度的定义和排序方法，建立了针对稳定匹配结果的评价函数和评价准则，在此基础上提出了蚁群算法求解此问题的思路及适合此类问题求解的蚂蚁状态转移策略和信息素更新策略，仿真结果表明，改进的蚁群算法能够有效求解传统稳定匹配问题以及多属性双边稳定匹配问题。边红等（2011）[289]研究了一对多的大学招生问题，依据Gale-Shapley算法，利用稳定广义匹配的概念，给出了大学招生问题的一个O（m2n3）算法，并且这个算法可以看出是匈牙利算法的一种推广。梁海明和姜艳萍（2015）[290]针对二手房组合交易匹配决策问题，给出了二手房组合交易匹配、个体理性、不浪费、公平、帕累托占优和帕累托有效匹配方案的定义，在考虑匹配方案稳定性的基础上，设计了确定最优匹配方案的扩展H-R算法。李建荣（2015）[291]用数据工具格分析劳动力市场的资源配置，采用博弈论的分析与证明方法研究多对一双方匹配市场中的优化路径，在替代偏好和LAD偏好下，证明了稳定匹配集合是一个满足分配律的完备格。熊化峰等（2019）[292]针对共享经济背景下的双边匹配问题的特点，对双边匹配类问题进行抽象建模，改进属性匹配度计算模型，求出匹配双方的偏好序，引入机器学习的思想改进蚁群算法对之求解，提出非线性梯度启发信息和基于历史搜索信息的状态转移策略；针对蚁群算法初始参数设置难、调参工作量大的问题，提出基于梯度下降思想的自动调参方法；并制定稳定匹配和当前最优匹配的评价规则，引导蚁群算法的信息素更新。仿真结果表明改进的蚁群算法与传统蚁群算法相比评价值提升约20%，与传统蚁群和基于RNA计算改进的蚁群算法相比求解稳定性更优。张登兵（2017）[293]将匹配要素分为匹配主体、匹配物、匹配算法、匹配集，从而规范了匹配决策的研究体系。在对Gale-Shapley算法进行分析的基础上，设计了一种GS算法的表上作业方法，并提出了匹配的一种矩阵表示。但是，GS算法也存在明显的局限性。GS算法显著依赖于群体容量，结果可能会偏离一般统计偏好，而且GS匹配的效率评价缺乏客观标准。陈晔等（2018）[294]分析供需匹配之间存在的冲突，提出一种基于图模型冲突分析法来求解供需匹配问题的思路，在图模型视角下给出供需匹配问题的研究框架，分析不同类型的供需匹配问题，设定决策主体和决策策略；然后讨论不同匹配类型下的状态约简、偏好表达，进行稳定性分析；最后通过应用案例，将图模型法与群决策匹配算法进行对比分析，验证图模型求解供需匹配问题的有效性。

（2）考虑公平性的双边匹配方法

Ergin（2002）[309]研究了学生对位置（房屋、大学位置或企业岗位）有偏好、位置对学生有优先权的学生安置问题，指出不违背指定优先权的安置机制是公平的，研究表明当且仅当优先权结构是非循环时，一个公平安置机制是有效的。Abdulkadiroglu和Sönmez（2003）[310]研究了波士顿和纽约城市公共学校的学校选择机制，指出学校当前采用的选择机制存在无效率、策略操作脆弱性和缺少公平性，而Agent最优稳定匹配机制（AOSM）是防操纵且公平的，但不是帕累托有效的；TTC机制是防操纵且帕累托有效的，但不是公平的。Klaus和Klijn（2007）[311]研究了具有成对夫妻的医院与实习生匹配问题，指出当不存在成对夫妻时，非循环性是公平和有效匹配机制的必要和充分条件；当存在成对夫妻时，非循环性是必要不充分条件，给出了采用所谓顺序匹配机制能够获得公平和有效匹配的充分条件。Liu和Ma（2015）[312]研究了具有不确定偏好序的双边匹配问题，设计了确定偏好序值的数据处理方法，给出了计算每个匹配对偏好距离的方法，构建了以匹配对数量最大和所有匹配对之间的偏好距离最小为目标的优化模型，通过与已有方法相比，提出的方法能保证每个匹配对都不会太差。Brams和Kilgour（2013）[313]针对延迟接受算法获得的匹配结果对一方是最优的，而对另外一方是最差的不公平情况，提出了最小最大公平匹配，研究表明帕累托最优的最小最大匹配能够提供比延迟接受算法更均衡的匹配对，此外，对帕累托最优的最小最大匹配进行策略操作是困难的。Wu和Zhong（2014）[314]比较了不同偏好提交时间（考前估分提交、考后估分提交、考后知分提交）以及不同录取过程情形下的中国大学录取机制的公平性和效率，理论研究表明考后知分提交偏好或序列独裁机制是事后而非事前公平和有效的；考前估分提交偏好和波士顿机制是事前更公平和有效的，通过对来自中国顶级大学数据的实证测试支持了上述假设。Lien等（2015）[315]研究了学生在不同时间提交学校偏好时波士顿机制与序列独裁机制的优缺点，研究假定学生在考后知分前提交学校偏好时，波士顿机制在公平性和效率方面优于序列独裁机制，通过一系列实验室试验证实了这一假设。(www.xing528.com)

聂海峰（2007）[11]分析了高考招生中考后知分报考录取机制下的志愿填报博弈，研究表明完全信息时这个显示偏好博弈只有唯一的纳什均衡结果，均衡是帕累托有效和公平的。但是真实的偏好并不一定是每个考生的均衡策略，达到均衡结果需要参与人之间的协调。冯科和聂海峰（2007）[132]研究了中国高考的录取程序，分析了分数录取机制下的公平和效率问题，指出由于目前的招生录取机制并不是分数公平的机制，使得录取结果可能是没有效率的；如果使用分数公平的录取机制，考生真实申报对学校的偏好就是他的优势策略，录取结果可以同时达到帕累托最优和分数公平。魏立佳（2010）[316]研究了目前高考录取平行志愿制度的优点和缺陷，提出降低投档比例、打通不同院校之间的专业志愿和增加志愿个数可以改进学生的效用损失；针对博士生录取设计了一种偏好顺序机制，并证明了这种机制是满足公平、无浪费、个人理性、抗策略且帕累托最优的。马明明（2012）[317]利用河北省一所高中高考志愿填报和录取结果的实际数据首次实证地描述和检验了中国高考机制的公平性和考生填报策略的问题，实证发现了“志愿优先”的高考机制不公平性的证据和高分底就的现象，通过对“平行志愿”和“志愿优先”的志愿填报和录取结果的比较，发现“平行志愿”并未显示出更好的公平性。吴斌珍和钟笑寒（2012）[10]研究了高考志愿填报机制对优质大学学生质量的影响，论证了考前报改为考后报并引入平行志愿的改革模式可以带来事后的效率与公平，但未必增加事前的效率与公平，基于某顶级学院的学生数据，从实证上验证了这一假说：相对于考前无平行志愿的制度，该学院在考后填报制度下招收的学生高考成绩更高，但以大学学业衡量的学习能力或兴趣并没有更高。

（3）考虑满意性的双边匹配方法

Zhang和Guo（2011）[295]研究了具有不同类型属性信息的多属性双边匹配决策问题，提出了一种解决具有不完全权重信息的双边匹配决策问题，通过解决二次规划模型来计算属性的权重，构建了双目标的0-1型整数规划模型，并将双目标规划模型采用线性加权和方法转换为单目标模型，通过求解单目标模型来获得最优的匹配结果。Yang等（2015）[296]研究了考虑手术医生对手术时间段偏好的手术调度方法，将手术室一天的工作时间视为资源，依据申请手术室的手术医生数量，将时间划分为时间段，时间段分配给手术医生视为双边匹配问题，构建了双方满意度最大的优化模型，通过求解模型获得双边最优匹配。Yue（2012）[297]研究了具有得分值信息的双边匹配问题，给出了满意度的概念，构建了以双边主体满意度最大为目标的优化模型，采用线性加权法将多目标优化模型转换为单目标进行求解。

张振华和汪定伟（2005）[298]研究了电子中介处理多个买家和多个卖家、各交易一件同类商品、卖方定价销售的多属性匹配问题，建立了以每一属性买方总满意度最大为目标的多指标优化模型，并采用理想点法求解。王中兴和黄帅（2014）[299]针对电子商务中买卖双方交易匹配问题，将主体给出的多粒度语言评价信息转化成三角模糊数，运用逼近理想解法计算主体综合评价与理性评价的相对贴近度，并以其表示匹配主体的满意度，构建综合考虑匹配主体满意度一致性和最大化的优化模型，求解该模型获得匹配结果。张振华和汪定伟（2006）[55]研究了电子中介在二手住房市场中的应用问题，给出了一个买卖交易模型；以最大化双方总满意度及总成交额为目标建立的多目标指派模型优化了双边匹配，并用模糊加效率矩阵方法化为单目标问题求解。陈希等（2012）[57]针对现实生活中双边匹配时每一方内部不同个体存在个性化评价指标情况，分析了每一方内部个性化指标的差异度，设计了总体指标集及权重的协同优化模型，定义了双边匹配竞争度，构建了基于总体匹配满意度最优化模型来求解匹配结果。乐琦和樊治平（2012）[300]针对具有序值信息的双边匹配决策问题，构建了以匹配主体对之间的序值总和最小和中介收益最大为目标的多目标优化模型，使用线性加权和方法将多目标优化模型转换为单目标线性规划模型进行求解来获得匹配方案。樊治平和乐琦（2014）[301]研究了考虑双边主体具有最高可接受偏好序的双边匹配问题，给出了严格双边匹配的概念及其存在性理论，考虑到双边主体的满意度和最低可接受满意度，构建了多目标优化模型，使用线性加权法将多目标优化模型转化为单目标优化模型，通过求解该单目标优化模型获得匹配结果。李铭洋等（2012）[302]针对双边主体给出匹配偏好信息的双边匹配问题，构建了将偏好序信息转化为匹配满意度的满意度函数，通过集结双方主体相互间的匹配满意度得到综合匹配满意度，将综合匹配满意度视为双边主体之间匹配的权，并将基于偏好序信息的双边匹配问题转化为完全二分图中的权匹配问题，通过求解最大权匹配问题确定最优匹配结果。乐琦和樊治平（2015）[303]针对基于不完全序值信息的双边匹配问题，引入了完全双边匹配的概念，探讨了完全双边匹配的存在性，提出了求解基于不完全序值新的双边匹配问题的算法，使用该算法可获得完全双边匹配结果。陈圣群等（2014）[304]针对具有不确定偏好序信息的动态匹配决策问题，给出了序数偏差的相关描述，把在同一时刻的不同方案间或同一方案在不同时刻间的序数偏差关系作为证据，并通过证据组合求出双边序数偏差融合度，通过构建优化模型获得双边匹配方案。王中兴等（2014）[305]针对具有语言评价信息的双边匹配决策问题，从匹配主体相互满意的视角，综合考虑匹配主体满意度的互补性和一致性定义匹配主体的组合满意度，以匹配的总组合满意度最大为目标建立求解匹配结果的优化模型。吴凤平等（2016）[306]针对互联网金融背景下风险投资双边匹配选择问题，考虑到风险投资者与风险企业在双向选择时的心理期望，提出一种基于前景理论的风险投资双边匹配决策模型。陈睿等（2017）[307]针对双边匹配问题特点，以匹配双方的需求条件、第三方利益和匹配对个数为主要目标，建立双边匹配问题的多目标优化模型。提出一种基于改进的粒子群蚁群优化算法，对蚁群做自适应信息素更新机制改进，对粒子群做高斯替换改进，避免算法陷入局部最优，提高算法寻优速度。仿真结果表明，该算法可行有效，能较好地解决多目标双边匹配问题。刘绘珍和廖丽平（2015）[308]在订单交货期模糊和加工时间随机分布的条件下，权衡订单成本和客户满意度，提出基于遗传算法的双边匹配调度模型，并利用算例对该模型进行检验。仿真结果显示：该模型对订单调度是有效的；与单目标优化相比，多目标优化是对多个目标的折中，从整个系统来看，多目标优化具有全局性的特点。