XOR标集的逆向组合拍卖的获胜者确定问题  

Winner determination problem in reverse combinatorial auction with XOR bids

作　　者：祁宁[1] 汪定伟[1] 

机构地区：[1]东北大学信息科学与工程学院,辽宁沈阳110819

出　　处：《系统工程学报》2013年第6期748-755,共8页Journal of Systems Engineering

基　　金：国家自然科学基金重点资助项目(70931001);国家自然科学基金创新群体资助项目(60821063);国家自然科学基金资助项目(70771021);国家教育部博士点基金资助项目(200801450008)

摘　　要：基于XOR标集的逆向组合拍卖使得竞标者可以更准确地表达对多种不同资源组合的偏好,建立了适于基于XOR标集的逆向组合拍卖获胜者确定问题的一般模型,设计了三个预处理规则,在此基础之上设计了基于预处理规则的改进最大-最小蚁群算法(MMAS)——PRIM(preprocessing rules-based improved MMAS),解决基于XOR标集的逆向组合拍卖获胜者确定问题.仿真结果表明,提出的预处理规则能够缩小搜索空间,并有效地尽早停止不可能产生最优解的搜索.与CPLEX的计算对比表明,提出的PRIM算法能够有效的求解基于XOR标集的逆向组合拍卖获胜者确定问题,改进效果明显.Reverse combinatorial auction with XOR -bids allows bidders expressing their preference for differ- ent mix of resources more exactly. In this paper, a common model is formulated for the winner determination problem of reverse combinatorial auction with XOR -bids. Three preprocessing rules are proposed and a PRIM （preprocessing rules-based improved MMAS ） algorithm is developed for solving this problem. Simulation results show that the search space is reduced by avoiding unnecessary trials using the proposed preprocessing rules as early as possible. Compared to other algorithms, the developed PRIM is feasible and efficient for solv- ing the winner determination problem of reverse combinatorial auction with XOR-bids and performs better performance.

关 键 词：逆向组合拍卖 XOR标集 获胜者确定问题 最大-最小蚁群算法 预处理规则 

分 类 号：F224[经济管理—国民经济]