拍卖是一种竞价的买卖方式。传统的拍卖是将特定物品或财产权利转让给最高应价者。组合拍卖与传统拍卖不同,组合拍卖允许投标人在多个拍卖品中自由组合,给出总价格作为出价进行竞标,而不对其中物品单独给出价格。组合拍卖在电子商务、空间分配、云计算等领域均有应用。而胜者决定问题又是组合拍卖领域的核心问题之一,有着重要的理论意义和实际应用价值。然而,胜者决定问题已经在理论上被证明是NP难问题,目前找不到多项式时间内求解的精确算法。精确算法虽然能证明输出解的最优性,但随着问题规模的扩大,它需要的求解时间将呈指数型增长,难以在可接受的时间里应对复杂的大规模实例。这类NP问题通常都需要依靠启发式算法进行近似求解,以达到可以在实际中应用的目的。局部搜索作为一类重要的启发式算法,具有简洁和高效的特点。局部搜索算法在多种NP问题求解中都有极好的表现。尽管它无法像精确算法一样给出最优解并证明其最优性,但在大规模实例上,局部搜索算法通常可以在更短时间内给出高质量的近似解。胜者决定问题在实际应用中十分重要,受到了很多关注。本文将设计和实现一种求解胜者决定问题的局部搜索算法,用于在短时间内求解较大规模的实例并使解质量尽可能提高。本文中提出的算法名为WDPLS。WDPLS基于一种高效且简明的局部搜索框架,并配有三种技术,分别为格局检测技术、自由出价技术和伪并列技术。格局检测技术是一种十分高效的用于局部搜索算法的防回溯策略。针对胜者决定问题,我们为WDPLS设计了适合该问题的格局定义,阻止算法贪婪搜索时发生回溯。在算法进行搜索时,可能会出现自由出价。这是一种特殊的出价,WDPLS优先选择自由出价以快速提升解质量。此外,在搜索过程中可能会遇到质量(得分)非常相似的落败出价。对于这些出价,伪并列技术阻止了算法过度贪婪地选择最高得分出价,从而为其他高质量出价提供了被选可能,进一步增加了解的多样性。在LG数据集上的大量实验表明,WDPLS在求解质量和求解时间上均领先于已发表的先进算法。特别地,尽管WDPLS在本文实验中被实现为单线程程序,但其在与多线程实现的算法CARA及商业求解器CPLEX相比时仍具有明显优势。同时,实验也展示出,以上三种主要技术都对WDPLS的性能有正面影响,证明了它们的有效性。