A Quantum Evolutionary Algorithm-Based Bundling Optimization for Multi-item Procurements

Abstract

Abstract: The object bundling optimization problem in reverse combinatorial auctions for online procurements and large project tenders is addressed. A mathematical model with multi-objectives is proposed to solve the problem. Because of its nonlinear and non-analytic properties with variable sets, it is very difficult to solve. Thus, a Quantum Evolutionary Algorithm (QEA) is developed for its solution. It adopts the 0-1 encoding scheme with nonzero elements in the cost complementarity matrix, and the β-based rotation gate to enlarge the probability of selecting the better Q-bits. Numerical results from a number of examples show that the β-based rotation gate is evidently better than the α-based one. Compared with a contrastive genetic algorithm, QEA can achieve better computational performances for small- and middle-sized problems.

Key words: online procurement, combinatorial auction, object bundling, optimal auction design, quantum evolutionary computation, rotation gate

Wang Ding-wei1, Wang Na2. A Quantum Evolutionary Algorithm-Based Bundling Optimization for Multi-item Procurements[J]. Industrial Engineering Journal , 2013, 16(1): 45-49.

References

［1］武刚, 冯玉强, 傅丽芳.面向政府采购的多属性电子拍卖机制设计［J］.系统管理学报, 2007, 16(3): 291-297. Wu Gang, Feng Yu-qiang, Fu Li-fang. Government procurement oriented multi-attribute E-auction mechanism design［J］. Journal of Systems & Management, 2007, 16(3): 291-297.  ［2］Vries S de， Vohra R V.Combinatorial auctions: a survey ［J］. INFORMS Journal on Computing, 2003, 15(3): 284-309. ［3］Wagner S M， Schwab A P. Setting the stage for successful electronic reverse auctions ［J］.Journal of Purchasing & Supply Management, 2004, 10(1): 11-26. ［4］Sandholm T. Approaches to winner determination in combinatorial auctions ［J］.Decision Support Systems, 2000, 28(1/2): 165-176.  ［5］Sandholm T. Algorithm for optimal winner determination in combinatorial auctions ［J］. Artificial Intelligence, 2002, 135(1/2):1-54. ［6］陈培友, 汪定伟. 组合拍卖竞胜标确定问题的混沌搜索方法［J］. 管理科学学报, 2003, 6(5): 24-28. Chen Pei-you,Wang Ding-wei. Chaotic search algorithm for winner determination in combinatorial auctions ［J］. Journal of Management Sciences in China, 2003, 6(5): 24-28. ［7］陈培友, 汪定伟. 多物品最优组合供应模式确定问题的模型研究［J］, 中国管理科学, 2006, 14(4): 35-39. Chen Pei-you,Wang Ding-wei. Research on the model of determination of multiple products optimal combinatorial supply patterns［J］. Chinese Journal of Management Science, 2006, 14(4): 35-39. ［8］Avery C, Hendershott T. Bundling and optimal auctions of multiple products［J］. Review of Economic Studies, 2000,67(3): 483-497. ［9］Schoenherr T,Mabert V A. The use of bundling in B2B online reverse auctions［J］.Journal of Operations Management,2008, 26(1): 81-95.〖ZK)〗 ［10］汪定伟. 网上集中采购的捆绑-组合拍卖机制设计［J］. 系统工程学报, 2011, 26(6): 809-815. Wang Ding-wei. Mechanism design of hybrid bundling and combination auction for centralized e-procurement［J］. Journal of Systems Engineering, to appear, 2011, 26(6): 809-815. ［11］Han K H，Kim J H. Quantum-inspired evolutionary algorithm for a class of combinatorial optimization［J］. IEEE Transactions on Evolutionary Computation, 2002, 6(6): 580-593.  ［12］Han K H，Kim J H. Quantum-inspired evolutionary algorithms with a new termination criterion, He Gate, and two-phase scheme［J］. IEEE Transactions on Evolutionary Computation, 2004, 8(2): 156-169. ［13］Vlachogiannis J G，Ostergaard J. Reactive power and voltage control based on general quantum genetic algorithms［J］. Expert Systems with Applications, 2009,36(3): 6118-6126. ［14］Chen J C. Application of quantum-inspired evolutionary algorithm to reduce PAPR of an OFDM signal using partial transmit sequences technique［J］. IEEE Transactions on Broadcasting, 2010, 56(1): 110-113. ［15］王凌. 量子进化算法研究进展［J］.控制与决策, 2008, 23(12): 1321-1326. Wang Ling. Advances in quantum-inspired evolutionary algorithms［J］. Control and Decision, 2008, 23(12): 1321-1326. ［16］任子武, 熊蓉, 储健. 混合量子差分进化算法及应用［J］. 控制理论与应用, 2011, 28(10): 1349-1355. Ren Zi-wu, Xiong Rong, Chu Jian. Hybrid quantum differential evolutionary algorithm and its applications［J］. Control Theory & Applications, 2011, 28(10):1349-1355. ［17］Gen M，Cheng R W. Genetic algorithms and engineering design［M］. New York：John Wiley and Sons, 1997.