招标采购中的采购物品打包模型及其优化算法

doi:10.12005/orms.2020.0223

摘要/Abstract

摘要： 招标采购是采购物品(货物或服务)的有效方式, 采购物品打包是招标采购的重要环节并对采购绩效有重要影响。采购物品打包是确定一组互斥的采购包集合, 在充分的市场竞争条件下购买全部采购物品, 且每个采购包的候选供应商应对该采购包中的所有物品进行投标。目前采购物品打包问题的研究文献较少, 本文通过定义采购包和采购打包方案等概念, 建立了采购物品打包问题的0-1整数规划模型。由于该模型具有NP-hard特征, 为此首先将其转化为旅行商问题, 并基于遗传算法设计采购物品打包问题的求解算法。实验表明:与整数规划求解软件和双聚类算法相比, 本文所提出的算法在解决采购物品打包问题时具备更好的优化性能和计算效率。

关键词: 招标采购, 采购物品打包, 旅行商问题, 遗传算法

Abstract: Procurement auction plays an import role for sourcing items (products and/or services), which significantly affects the purchase performance. Literature on bundling from buyer’s perspective is quite scarce. Bundling from buyer’s perspective is the problem of determining a set of mutually exclusive bundles from the buyer perspective, which will induce competitive bidding behavior under the constraint that suppliers are required to bid on all the items in a bundle. In this paper, we present a buy-side perspective on bundling, by clarifying the definitions of the concepts of a bundle and a bundling solution, and introduce a 0-1 integer program optimization model, with the objective of minimizing the number of bundles in the bundling solution. The optimization model is proved to be NP-hard. For the sake of efficiently solving this problem, the model is first transformed into a traveling salesman problem and then solved using a genetic algorithm proposed in this paper. The performance of the proposed approach is compared with those of a traditional integer program solver and an existing bi-clustering approach. The experimental results show that the proposed approach can provide promising results in terms of a bundling solution and computing efficiency.

Key words: procurement auction, bundling from the buyer perspective, traveling salesman problem, genetic algorithm

中图分类号:

F224

黄学文, 孙榕, 艾亚晴. 招标采购中的采购物品打包模型及其优化算法[J]. 运筹与管理, 2020, 29(9): 18-26.

HUANG Xue-wen, SUN Rong, AI Ya-qing. Modelling and Optimization Algorithm for Bundling from Buyer’s Perspective in Procurement Auction[J]. Operations Research and Management Science, 2020, 29(9): 18-26.

参考文献

[1] Mishra D, Veeramani D. Vickrey-dutch procurement auction for multiple items[J]. European Journal of Operational Research, 2007, 180(2): 617-629.
[2] Jap S D. Online reverse auctions: Issues, themes, and prospects for the future[J]. Journal of the Academy of Marketing Science, 2002, 30(4): 506-525.
[3] Schoenherr T, Mabert V A. The use of bundling in B2B online reverse auctions[J]. Journal of Operations Management, 2008, 26(1): 81-95.
[4] Schoenherr T, Mabert V A. The effect of buyer-imposed bidding requirements and bundle structure on purchase performance[J]. Journal of Supply Chain Management, 2007, 43(1): 27-39.
[5] 全国人民代表大会常务委员会.中华人民共和国招标投标法[Z].2000-01-01.
[6] Beall S, Carter C, Carter P L. The role of reverse auctions in strategic sourcing[J]. CAPS Research, 2003.7-13.
[7] Schoenherr T, Mabert V A. An Exploratory study of procurement strategies for multi-item RFQs in B2B markets: antecedents and impact on performance[J]. Production & Operations Management, 2015, 20(2): 214-234.
[8] Estache A, Iimi A. (Un)bundling infrastructure procurement: evidence from water supply and sewage projects[J]. Utilities Policy, 2011, 19(2): 104-114.
[9] Schmitz P W. Public procurement in times of crisis: the bundling decision reconsidered[J]. Economics Letters, 2013, 121(3): 533-536.
[10] Muylle S, Standaert W. The use of procedural fairness in electronic reverse auctions to enhance relationship quality[J]. Psychology & Marketing, 2016, 33(4): 283-296.
[11] Pawar P V, Behl A, Aital P. Systematic literature review on electronic reverse auction: Issues and research discussion[J]. International Journal of Procurement Management, 2017, 10(3): 290-310.
[12] Looman A, Ruffini F A J, Boer L D. Designing ordering and inventory management methodologies for purchased parts[J]. Journal of Supply Chain Management, 2002, 38(1): 22-29.
[13] Birou L, Fawcett S E, Magnan G M. Integrating product life cycle and purchasing strategies[J]. Journal of Supply Chain Management, 2010, 33(1): 23-31.
[14] Kaufmann L, Carter C R. International supply management systems— the impact of price vs. non-price driven motives in the united states and germany[J]. Journal of Supply Chain Management, 2002, 38(3): 4-17.
[15] Ramsay J. Purchasing’s strategic irrelevance[J]. European Journal of Purchasing & Supply Management, 2001, 7(4): 257-263.
[16] Schoenherr T 1. Bundling for B2B procurement auctions: current state and best practices[J]. International Journal of Integrated Supply Management, 2006, 2(3): 189-213.
[17] Mabert V A, Schoenherr T. An online RFQ system: a case study[J]. Practix, 2001.
[18] Venkatesh R, Mahajan V, Katz J M. The design of bundles: a review of normative guidelines and practical approaches[M]. Handbook of Pricing Research in Marketing, 2009. 232-257.
[19] 杨光勇, 计国君.捆绑策略对于低性能产品引入的价值[J].管理科学学报, 2017, 20(4):84-100.
[20] 高尚, 滕春贤, 孙嘉轶.不同主导力量下基于捆绑销售的旅游供应链决策分析[J].中国软科学, 2016(7):155-161.
[21] 潘林, 周水银.考虑捆绑销售的多产品供应链定价策略[J].运筹与管理, 2016, 25(6):11-17.
[22] Carter C R, Kaufmann L, Beall S, et al. Reverse auctions——grounded theory from the buyer and supplier perspective[J]. Transportation Research Part E Logistics & Transportation Review, 2004, 40(3): 229-254.
[23] Arnold U, Krner H, Schnabel M. Target-oriented use of strategic sourcing tools: a critical analysis creating process awareness for electronic reverse auctions[J]. Journal of Purchasing & Supply Management, 2005, 11(2-3): 116-128.
[24] Grimm V, Pacini R, Spagnolo G, et al. Division in lots and competition in procurement, handbook of procurement[M]. Cambridge University Press, 2006. 168-192.
[25] Hur D, Hartley J L, Mabert V A. Implementing reverse e-auctions: a learning process[J]. Business Horizons, 2006, 49(1): 21-29.
[26] Linthorst M M, Telgen J, Schotanus F. Buying bundles: the effects of bundle attributes on the value of bundling[C]. International Euroma Conference, 2008.
[27] Hu D Y, Feng Y Q. Research on post-bidding bundle strategy for online reverse auction[C]//International Conference on Management Science and Engineering. IEEE, 2011. 51-57.
[28] 汪定伟.网上集中采购的捆绑-组合拍卖机制设计[J].系统工程学报, 2011, (6):809-816.
[29] 汪定伟, 王娜.多项目采购中基于量子进化算法的打包优化方法[J].工业工程, 2013, 16(1):45-49.
[30] 唐振宇, 万晶, 冯玉强等.基于资源优化配置的外文期刊采购标段划分研究[J].情报科学, 2009, (10):1555-1558.
[31] 廖腾芳, 周月明.图书招标的基本原则及标段划分的数学模型研究——以湖南城市学院图书馆图书招标为例[J].图书馆理论与实践, 2009, (3):104-106.
[32] 孟碟, 冯平.滚朋羊二级水电站工程标段的优化划分[J].天津大学学报:自然科学与工程技术版, 2011, 44(12):1088-1092.
[33] 张智慧, 何倩儒.高速公路标段划分对工程造价的影响[J].清华大学学报:自然科学版, 2010, (6):830-833.
[34] Li C. Sourcing for supplier effort and competition: design of the supply base and pricing mechanism[J]. Management Science, 2013, 59(6): 1389-1406.
[35] Karp R M. Reducibility among combinatorial problems in complexity of computer computations[J]. Plenum Press, 1972. 85-103.
[36] Cheng Y, Church G M. Bi-clustering of expression data[C]. Eighth International Conference on Intelligent Systems for Molecular Biology. AAAI Press, 2000, 8(5): 93-103.
[37] Balas E, Padberg M W. Set partitioning: a survey[J]. Siam Review, 1976, 18(4): 710-760.
[38] Lin C A. Generational model genetic algorithm for real world set partitioning problems[J]. International Journal of Electronic Commerce Studies, 2013, 4(1): 33-46.
[39] Nguyen T D. A fast approximation algorithm for solving the complete set packing problem[J]. European Journal of Operational Research, 2014, 237(1): 62-70.
[40] Pontes B, Giráldez R, Aguilarruiz J S. Biclustering on expression data: a review[J]. Journal of Biomedical Informatics, 2015, 57 (C): 163-180.
[41] Laporte G. The traveling salesman problem: an overview of exact and approximate algorithms[J]. European Journal of Operational Research, 1992, 59(2): 231-247.
[42] Lee H, Kim S S. Integration of process planning and scheduling using simulation based genetic algorithms[J]. International Journal of Advanced Manufacturing Technology, 2001, 18(8): 586-590.
[43] Liu X, Wang L. Computing the maximum similarity bi-clusters of gene expression data[J]. Bioinformatics, 2007, 23(26): 50-56.