黃學(xué)文，孫 榕，艾亞晴

(大連理工大學(xué) 管理與經(jīng)濟(jì)學(xué)部，遼寧 大連 116023)

0 引言

招標(biāo)采購(gòu)(Procurement Auction)也稱逆向拍賣(Reverse Auction)，是招標(biāo)者(采購(gòu)商)提出一組貨物和服務(wù)(統(tǒng)稱為物品)的采購(gòu)要求，邀請(qǐng)指定或非指定的投標(biāo)者(供應(yīng)商)參與投標(biāo)，按照一定程序和規(guī)則選擇中標(biāo)者的一種有效的市場(chǎng)交易行為[1]，招標(biāo)采購(gòu)作為一種價(jià)格發(fā)現(xiàn)機(jī)制在國(guó)內(nèi)外得到廣泛應(yīng)用[2]。

當(dāng)采用采購(gòu)招標(biāo)來購(gòu)買一組物品時(shí)，采購(gòu)商需要在拍賣活動(dòng)開始之前解決如下的問題：哪些物品需要打包成一個(gè)采購(gòu)包？以及在保證充分市場(chǎng)競(jìng)爭(zhēng)性的前提下，需要多少個(gè)采購(gòu)包來完成全部物品的采購(gòu)？其中，打包(bundling或lotting)是指采購(gòu)商將多個(gè)物品捆綁成一個(gè)采購(gòu)包[3]，供多位供應(yīng)商投標(biāo)。另外，Schoenherr等[4]通過對(duì)30家美國(guó)公司的實(shí)證研究發(fā)現(xiàn)：在75.9%的招標(biāo)采購(gòu)活動(dòng)中，要求或鼓勵(lì)供應(yīng)商對(duì)采購(gòu)包中全部物品進(jìn)行投標(biāo)，被多數(shù)采購(gòu)商尤其是大公司采購(gòu)商所推崇。由此便產(chǎn)生一個(gè)問題——采購(gòu)物品打包問題(bundling from buyer’s perspective)，即：在要求候選供應(yīng)商對(duì)采購(gòu)包中的所有物品進(jìn)行投標(biāo)和確保候選供應(yīng)商之間存在充分的市場(chǎng)競(jìng)爭(zhēng)的前提下，如何確定一組互斥的采購(gòu)包(任意兩個(gè)不同的采購(gòu)包中不能包含相同的物品)來滿足采購(gòu)商購(gòu)買一系列物品的要求。目前，在中國(guó)的絕大數(shù)招標(biāo)采購(gòu)中，采購(gòu)商要求供應(yīng)商對(duì)采購(gòu)包中的全部物品做出投標(biāo)響應(yīng)，同時(shí)，《中華人民共和國(guó)招標(biāo)投標(biāo)法》和《評(píng)標(biāo)委員會(huì)和評(píng)標(biāo)方法暫行規(guī)定》等法律文件規(guī)定每個(gè)采購(gòu)包有不少于三家的候選供應(yīng)商[2,5]。

作為逆向拍賣過程的一個(gè)關(guān)鍵參數(shù)和前置過程，采購(gòu)物品打包對(duì)采購(gòu)績(jī)效有顯著影響[2,3,6～11]，如，降低采購(gòu)過程的管理成本[12]、提高采購(gòu)的規(guī)模經(jīng)濟(jì)[13,14]、增加采購(gòu)商的議價(jià)能力[15,16]、縮短招標(biāo)采購(gòu)時(shí)間和減少采購(gòu)約束條件[17]等。但不合理的采購(gòu)物品打包策略會(huì)顯著降低采購(gòu)績(jī)效[3,7,8]，Estache等[8]通過實(shí)證研究表明：在公共基礎(chǔ)設(shè)施建設(shè)項(xiàng)目中，不合理的采購(gòu)物品打包策略嚴(yán)重限制了供應(yīng)商之間的市場(chǎng)競(jìng)爭(zhēng)性。

現(xiàn)實(shí)中存在兩類不同的打包問題：采購(gòu)物品打包和銷售物品打包(bundling from seller’s perspective)，銷售物品打包是指賣方將兩個(gè)或兩個(gè)以上的物品捆綁銷售。目前國(guó)內(nèi)外研究主要集中于銷售物品打包問題，關(guān)于該問題的研究，參見文獻(xiàn)[18～21]。

關(guān)于采購(gòu)物品打包問題的研究及成果較少，僅提出了幾種概念性的采購(gòu)物品打包策略，如，Jap[2]認(rèn)為采購(gòu)包應(yīng)盡可能包含更多的物品，以降低其采購(gòu)費(fèi)用；但不能導(dǎo)致采購(gòu)包的候選供應(yīng)商數(shù)量減少，進(jìn)而降低供應(yīng)商之間的市場(chǎng)競(jìng)爭(zhēng)性。相關(guān)學(xué)者[22～25]進(jìn)一步提出為增加采購(gòu)包中物品的數(shù)量，可將屬于同一類別(commodity group)的物品打包在一起的策略。Beall等[6]提出兩種打包策略：市場(chǎng)籃子打包(market basket lotting)策略和個(gè)體打包(individual lotting)策略，其中，前者適用于采購(gòu)物品來源于相同或相似的物品類別且候選供應(yīng)商能夠供應(yīng)全部或大部分采購(gòu)物品的情況，經(jīng)過80/20的帕累托(Pareto)分析后，最重要的物品打包在一起；個(gè)體打包策略適用于采購(gòu)物品來源于不同的物品類別的情況，并將單一物品打包在一個(gè)采購(gòu)包中。Linthorst等[26]基于采購(gòu)人員的采訪和總結(jié)，提出了同質(zhì)打包(homogeneous bundling)策略和異質(zhì)打包(heterogeneous bundling)策略，其中，將屬于同一類別的物品打包在一起，稱之為同質(zhì)打包，反之則是異質(zhì)打包。Hu等[27]定義市場(chǎng)競(jìng)爭(zhēng)性(market competitiveness)和物品相似性(item similarity)兩個(gè)變量，來度量?jī)煞N物品打包在同一采購(gòu)包的可能性，并提出了PBBS(Post-Bidding Bundle Strategy)采購(gòu)物品打包策略；汪定偉等[28,29]在采購(gòu)物品的價(jià)格互補(bǔ)性和投標(biāo)一致性的基礎(chǔ)上提出了基于量子算法的打包算法；唐振宇和廖騰芳等[30,31]針對(duì)圖書館期刊采購(gòu)問題設(shè)計(jì)了基于雙聚類算法的打包算法；孟碟和張智慧等[32,33]面向工程建設(shè)類項(xiàng)目提出了基于交易成本經(jīng)濟(jì)學(xué)的打包算法。此外，Schoenherr等[3,7]和Linthorst等[26]，采用實(shí)證分析方法建立了一系列采購(gòu)包屬性用于評(píng)價(jià)采購(gòu)包的價(jià)值和最佳采購(gòu)物品打包程度，如物品定義難度(item specification difficulty)和采購(gòu)包復(fù)雜性(overall bundle complexity)等。

文獻(xiàn)綜述表明：Jap所提出的采購(gòu)物品打包理論已成為該問題的基本原則；但目前的采購(gòu)物品打包策略多屬于概念性方法，尚未形成通用性的采購(gòu)物品打包優(yōu)化模型和定量分析方法；同時(shí)，基于實(shí)證研究所提出的諸多采購(gòu)包屬性既難于度量又對(duì)采購(gòu)績(jī)效有相互依賴性的影響，從而難以通過這些采購(gòu)包屬性對(duì)采購(gòu)物品打包問題進(jìn)行定量分析。

本文將通過對(duì)采購(gòu)包和采購(gòu)打包方案等概念的定義，建立采購(gòu)物品打包問題的0-1整數(shù)規(guī)劃模型；同時(shí)針對(duì)該模型的NP-hard特點(diǎn)，首先將其轉(zhuǎn)化為旅行商問題(Traveling Salesman Problem, TSP)，并基于遺傳算法(Generic Algorithm, GA)設(shè)計(jì)采購(gòu)物品打包問題的求解算法；最后通過一系列的數(shù)據(jù)實(shí)驗(yàn)以驗(yàn)證算法的優(yōu)化性能和計(jì)算效率。

1 問題描述

1.1 基本概念和定義

(1)物品-供應(yīng)商矩陣

設(shè)采購(gòu)物品集合為G={1,2,…,n}，候選供應(yīng)商集合為V={1,2,…,m}，則物品-供應(yīng)商矩陣為G×V=(eij)n×m，eij∈{0,1}，物品i若可以由供應(yīng)商j提供，則eij=1，否則eij=0。

物品-供應(yīng)商矩陣可通過供應(yīng)商管理系統(tǒng)以及RFQ(Request For Quote)、RFI(Request For Information)或RFP (Request For Proposal)等手段獲得，物品-供應(yīng)商矩陣定義了招標(biāo)采購(gòu)的基本信息。

(2)采購(gòu)包

采購(gòu)包是由一種或多種的采購(gòu)物品構(gòu)成，供不少于λ(λ∈Z+)個(gè)且盡可能更多的候選供應(yīng)商投標(biāo)，任意候選供應(yīng)商應(yīng)對(duì)采購(gòu)包中的全部物品進(jìn)行投標(biāo)。采購(gòu)包的候選供應(yīng)商數(shù)量決定了該采購(gòu)包的供應(yīng)商之間的市場(chǎng)競(jìng)爭(zhēng)性[34]，最小市場(chǎng)競(jìng)爭(zhēng)性由市場(chǎng)競(jìng)爭(zhēng)控制參數(shù)λ決定。文獻(xiàn)以及實(shí)際的招標(biāo)采購(gòu)中，一般建議λ=2[6]，或λ=3[7]。

根據(jù)采購(gòu)包的定義，任意采購(gòu)包b可表示為一個(gè)矩陣Gb×Vb=(1)nb×mb，其中，Gb(Gb?G)表示該采購(gòu)包中的物品集合，Vb(Vb?V,|Vb|≥λ)表示該采購(gòu)包的候選供應(yīng)商集合。

給定矩陣G×V和參數(shù)λ，存在滿足采購(gòu)包定義的一個(gè)潛在采購(gòu)包集合Ω={b1,b2,…,bN}。N(N=|Ω|)由矩陣G×V和參數(shù)λ決定的，Ω可通過枚舉法獲得，但當(dāng)G×V=(1)n×m且|V|≥λ時(shí)，有N=2n-1，即：枚舉法計(jì)算潛在采購(gòu)包集合Ω，會(huì)帶來組合爆炸問題。

(3)采購(gòu)打包方案

采購(gòu)商為采購(gòu)全部物品G，需要設(shè)計(jì)由若干采購(gòu)包構(gòu)成的某種采購(gòu)打包方案，采購(gòu)打包方案S定義為：S={b1,…,bSk}，且滿足如下三個(gè)條件：

1)bi∈Ω，1≤i≤Sk；

2)?i≠j，有Gbi∩Gbj=?；

3)∪bi∈SGbi=G。

其中，Sk為S中的采購(gòu)包數(shù)量(|S|=Sk)，條件2)表示S中任意兩個(gè)不同的采購(gòu)包在物品集合上互斥；條件3)表示采購(gòu)打包方案S覆蓋全部的采購(gòu)物品。

表1為五個(gè)物品和五個(gè)供應(yīng)商的采購(gòu)問題實(shí)例，若參數(shù)λ=3，采用枚舉法可知共有11個(gè)潛在采購(gòu)包；針對(duì)該問題，可設(shè)計(jì)多種采購(gòu)打包方案，如S1={b1,b2,b3,b4,b5}、S2={b1,b3,b11}等。

表1 采購(gòu)物品打包問題的示例

值得注意的是：b2={2}×{1,2,3,4}是僅包含物品2的唯一滿足采購(gòu)包定義的采購(gòu)包，盡管{2}×{1,2,3}、{2}×{1,2,4}、{2}×{1,3,4}和{2}×{2,3,4}都有3個(gè)供應(yīng)商，滿足λ=3的要求，但不滿足“盡可能最多的供應(yīng)商”的要求，因此這些采購(gòu)包是不合法的。事實(shí)上，僅包含物品2的采購(gòu)包最多有4個(gè)供應(yīng)商，即供應(yīng)商1、2、3和4。

1.2 問題模型

關(guān)于采購(gòu)物品打包問題，Grimm等[24]提出了貼合招標(biāo)采購(gòu)整體目標(biāo)的兩個(gè)子優(yōu)化目標(biāo)，即：最小化采購(gòu)成本和將采購(gòu)包分配給成本最低的供應(yīng)商；但度量這兩個(gè)目標(biāo)依賴于供應(yīng)商的投標(biāo)數(shù)據(jù)(如價(jià)格、質(zhì)量、交貨等)，而供應(yīng)商的投標(biāo)對(duì)象則是采購(gòu)物品打包的結(jié)果——采購(gòu)包，即：供應(yīng)商的投標(biāo)活動(dòng)發(fā)生在采購(gòu)物品打包活動(dòng)之后，因此，上述優(yōu)化目標(biāo)無法在采購(gòu)物品打包過程使用。

本文將最優(yōu)采購(gòu)物品打包方案定義為“在保證充分市場(chǎng)競(jìng)爭(zhēng)性的前提下，包含最小采購(gòu)包數(shù)量的采購(gòu)打包方案即為最優(yōu)采購(gòu)打包方案”。由于采購(gòu)包的定義已經(jīng)保證了每一個(gè)采購(gòu)包有不少于λ個(gè)的候選供應(yīng)商，即每一個(gè)采購(gòu)包都有充分的市場(chǎng)競(jìng)爭(zhēng)性，因此，采購(gòu)物品打包問題的優(yōu)化目標(biāo)為最小化采購(gòu)打包方案中的采購(gòu)包數(shù)量。

上述觀點(diǎn)與Jap的采購(gòu)物品打包理論是一致的：其一，采購(gòu)包的定義確保了候選供應(yīng)商之間有充分的市場(chǎng)競(jìng)爭(zhēng)性；其二，最小化采購(gòu)打包方案中的采購(gòu)包數(shù)量，則意味著最大化采購(gòu)打包方案中的采購(gòu)包的平均物品數(shù)量(|G|/|S| )和平均采購(gòu)費(fèi)用C/|S| (設(shè)C為采購(gòu)全部物品的期望費(fèi)用)，顯然，這樣的采購(gòu)打包方案會(huì)增加候選供應(yīng)商的投標(biāo)積極性，并給采購(gòu)商帶來更強(qiáng)的議價(jià)能力[16,26]；其三，由于包含更少的采購(gòu)包，可以加速招標(biāo)采購(gòu)的執(zhí)行過程，減少招標(biāo)采購(gòu)的管理成本。

因此，采購(gòu)物品打包問題可定義為：給定物品-供應(yīng)商矩陣G×V和市場(chǎng)競(jìng)爭(zhēng)控制參數(shù)λ，尋找某種采購(gòu)打包方案，且該方案包含最小數(shù)量的采購(gòu)包。在給出問題的數(shù)學(xué)模型之前，先給出如下假設(shè)條件：

1)?g∈G，有|V(g)|≥λ；

2)?g∈G，其采購(gòu)數(shù)量可由V(g)中任意一家候選供應(yīng)商的供貨能力所覆蓋；

3)?供應(yīng)商v∈V，均是采購(gòu)商的合格供應(yīng)商(如產(chǎn)能、供貨，商譽(yù)等)；

4)?供應(yīng)商v∈V，在其能力范圍內(nèi)，不會(huì)放棄可能的投標(biāo)機(jī)會(huì)。

基于以上假設(shè)，采購(gòu)物品打包問題可表示為如下的0-1整數(shù)規(guī)劃模型：

(3)

式中，xb是決策變量，用來判斷最終的采購(gòu)打包方案是否選中了采購(gòu)包b(b∈Ω)，xb=1表示采購(gòu)包b被選中，否則xb=0；參數(shù)δgb∈{0,1}，若物品g打包在采購(gòu)包b中則δgb=1，否則δgb=0。式(1)表示采購(gòu)物品打包問題的優(yōu)化目標(biāo)為最小化采購(gòu)打包方案中的采購(gòu)包數(shù)量，式(2)表示采購(gòu)物品集合中的任意一種物品必須包含于采購(gòu)打包方案中，且只能被打包到唯一采購(gòu)包中。

從式(1)～(3)可以看出：上述模型延續(xù)了Jap等人所提出的概念化采購(gòu)物品打包理論或策略，并將這些概念化的理論或策略轉(zhuǎn)化成精確的0-1整數(shù)規(guī)劃模型，為求解優(yōu)化的的采購(gòu)物品打包方案提供了一種數(shù)學(xué)分析方法。

如，對(duì)于表1中的問題，共有11個(gè)潛在的采購(gòu)包，因此有11個(gè)決策變量向量x1,x2,…,x11，參數(shù)δgb可以由如下的矩陣δ=(δgb)5×11表示：

矩陣δ中第i行表示物品i，第j列表示第j個(gè)采購(gòu)包，如δ37=1表示了在采購(gòu)包b7中包含了物品3(見表1)，則該問題的整數(shù)規(guī)劃模型如下:

minz=x1+x2+…+x11

s.t.x1+x6=1

x2+x6+x7+x8+x9+x11=1

x3+x7=1

x4+x8+x10+x11=1

x5+x9+x10+x11=1

xi∈{0,1},?i=1,2,…,11

1.3 問題復(fù)雜性分析

命題1采購(gòu)物品打包問題是NP-hard問題。

證明該命題的證明是通過說明采購(gòu)物品打包問題分別是集合分區(qū)問題(Set Partitioning Problem, SPP)和雙聚類問題(Bi-clustering Problem)的實(shí)例。由于這個(gè)兩個(gè)問題均是NP-hard問題[35,36]，因此，采購(gòu)物品打包問題是NP-hard問題。

(1)集合分區(qū)問題

集合分區(qū)問題的定義如下[37]：給定一個(gè)行集合M={1,…,m}和列集合N={1,…,n}，如果第j列(其權(quán)重為cj，cj>0)包含行集合中的元素i∈M則aij=1，否則aij=0，集合分區(qū)問題的目的是尋找一個(gè)最小權(quán)重的集合M的分區(qū)(partition)，其數(shù)學(xué)描述如下:

xj∈{0,1},?j∈N

其中，決策變量為xj，當(dāng)?shù)趈列選中到最后的分區(qū)中則xj=1，否則xj=0。

如果將潛在采購(gòu)包集合Ω中的每個(gè)采購(gòu)包b∈Ω中的物品集合Gb看成是集合分區(qū)問題中權(quán)重恒為1的一列，并將采購(gòu)物品集合G看成是集合分區(qū)問題中的行集合，則采購(gòu)物品打包問題是集合分區(qū)問題的一個(gè)實(shí)例。

(2)雙聚類問題

雙聚類問題定義如下[36]：給定一個(gè)矩陣A(I,J)，其中，I={1,…,n}為行集合(或基因集合)，J={1,…,m}為列集合(或條件集合)，矩陣中的元素aij∈R表示第i行基因在第j列條件下的表達(dá)值。一個(gè)雙聚類A(I0,J0)是矩陣A(I,J)的一個(gè)子矩陣，其中，I0?I且J0?J。雙聚類問題的目的是尋找滿足某種同質(zhì)性標(biāo)準(zhǔn)的一組雙聚類。

按照定義，任何一個(gè)采購(gòu)包是矩陣G×V的一個(gè)子矩陣，且其元素均等于1，因此，一個(gè)采購(gòu)包是矩陣G×V的一個(gè)常聚類(constant bi-cluster)；同時(shí)，任何采購(gòu)打包方案S={b1,…,bSk}，按照定義，滿足Gbi∩Gbj=?(i≠j)和Ubi∈SGbi=G，即：采購(gòu)打包方案S={b1,…,bSk}是矩陣G×V的行獨(dú)占型雙聚類。因此，采購(gòu)物品打包問題可以看成是一個(gè)矩陣G×V的雙聚類問題的實(shí)例。

由此，命題1得證。命題1說明：采購(gòu)物品打包問題具有很高的計(jì)算復(fù)雜性，單純依靠概念性的打包理論(如Jap的采購(gòu)打包理論[1])或打包策略(如Beall等的打包策略[6])以及實(shí)際經(jīng)驗(yàn)來指導(dǎo)采購(gòu)物品打包是很難獲得優(yōu)化的采購(gòu)打包方案，特別是對(duì)于中、大規(guī)模的招標(biāo)采購(gòu)問題。

命題2采購(gòu)物品打包問題是一類比集合分區(qū)問題更為復(fù)雜的問題。

證明命題1證明了采購(gòu)物品打包問題是集合分區(qū)問題的一個(gè)實(shí)例。

但是，采購(gòu)物品打包問題和集合分區(qū)問題有著很大的差異，其差異體現(xiàn)在如下兩個(gè)方面：

(1)集合分區(qū)問題的列集合是事先給定和已知的，但若將采購(gòu)物品打包問題視為集合分區(qū)問題，其列集合，即潛在采購(gòu)包集合Ω，不是事先給定的；

(2)枚舉法是獲得潛在采購(gòu)包集合Ω的唯一方法，對(duì)于中、大規(guī)模招標(biāo)采購(gòu)問題，會(huì)導(dǎo)致組合爆炸問題。正如前文所述，當(dāng)G×V=(1)n×m且|V|≥λ時(shí)，潛在采購(gòu)包的數(shù)量高達(dá)2n-1。

由此，命題2得證。命題1意味著采購(gòu)物品打包問題可用集合分區(qū)問題和雙聚類問題的現(xiàn)有算法來求解。目前，集合分區(qū)問題和雙聚類問題均有成熟的求解算法。對(duì)于集合分區(qū)問題，已有一些精確算法(如列生成算法、商用數(shù)學(xué)規(guī)劃軟件等)和啟發(fā)式算法(如并行遺傳算法)[38,39]；對(duì)于雙聚類問題[40]，有MSB算法(Maximum Similarity Bi-cluster algorithm)、FLOC算法(Flexible Overlapped Bi-clustering)、SA-B算法(Simulated Annealing Bi-clustering)和CTWC算法 (Coupled Two-way Clustering)等算法。然而，由于采購(gòu)物品打包問題屬于NP-hard問題，因此，若將這些現(xiàn)成的算法直接用于求解一定規(guī)模的采購(gòu)物品打包問題，只能得到近似最優(yōu)解。另一方面，命題2說明：用于求解集合分區(qū)問題的現(xiàn)成算法或只適用于求解小規(guī)模的采購(gòu)物品打包問題。與此同時(shí)，現(xiàn)成的雙聚類算法不能保證“雙聚類中的列數(shù)量不小于λ”的要求(采購(gòu)包有不能小于λ個(gè)候選供應(yīng)商)，即原始的雙聚類算法并不完全適用于采購(gòu)物品打包問題，它需要一定的改造并滿足雙聚類中的列數(shù)量不小于λ的要求后才可以用于求解采購(gòu)物品打包問題。

在求解采購(gòu)物品打包問題時(shí)，將選用商用數(shù)學(xué)規(guī)劃軟件——CPLEX(Version 12.2)和一種雙聚類算法——MSB算法，作為對(duì)比算法來比較本文所提算法的優(yōu)化性能。

2 基于TSP和GA的優(yōu)化算法

2.1 采購(gòu)物品打包問題的TSP模型

旅行商問題(TSP)是研究歷史最為悠久的經(jīng)典組合優(yōu)化問題并有更為廣泛和成熟的求解算法，其定義如下[41]：設(shè)圖Graph=(V,E)，V是N個(gè)頂點(diǎn)的集合，E為邊集，設(shè)C=(cij)是一個(gè)與E有關(guān)的非負(fù)距離矩陣。TSP的目標(biāo)是尋找一個(gè)具有最短長(zhǎng)度的巡回路徑，且該巡回路徑有且只有一次經(jīng)過每一個(gè)頂點(diǎn)。

某種意義上講，一個(gè)采購(gòu)打包方案類似于采購(gòu)物品集合G意義上的一個(gè)巡回路徑，這是因?yàn)椋喝魏我粋€(gè)物品只能打包在采購(gòu)打包方案中唯一的采購(gòu)包中，即任意一個(gè)采購(gòu)打包方案有且只有一次地“訪問”了每一個(gè)物品。

因此，若將采購(gòu)物品集合G看成是TSP問題的頂點(diǎn)集合，采購(gòu)物品集合G意義上的一個(gè)巡回路徑長(zhǎng)度看成是該路徑所對(duì)應(yīng)的采購(gòu)打包方案中的采購(gòu)包數(shù)量(后文給出相應(yīng)的解碼算法)。則采購(gòu)物品打包問題可以看成是如下的一個(gè)TSP問題。

min|{xij=1│i,j∈G}|

(4)

其中，若有向邊(i,j)包含在巡回路徑中則xij=1，否則xij=0 ；集合{xij=1│i,j∈G}表示由n個(gè)xij=1所構(gòu)成的巡回路徑，|{xij=1│i,j∈G}|表示該路徑的距離，即：該路徑所對(duì)應(yīng)的采購(gòu)打包方案中的采購(gòu)包數(shù)量。式(4)表示問題的優(yōu)化目標(biāo)，即最小化巡回路徑所對(duì)應(yīng)的采購(gòu)打包方案中的采購(gòu)包數(shù)量，式(5)、(6)和(7)表示每一頂點(diǎn)(物品)在巡回路徑中只出現(xiàn)一次。

巡回路徑R={xij=1│i,j∈G}為集合G的一個(gè)全排列，即R={g1,g2,…,…,gn}，巡回路徑采用如下的BUNDLING算法解碼為采購(gòu)打包方案，該算法中用到如下的數(shù)學(xué)符號(hào)：

(1)運(yùn)算符?：對(duì)于矩陣G×V的任意兩個(gè)行向量：i=(ei1,ei2,…,eim)和j=(ej1,ej2,…,ejm)，有：i?j=(e1,…,ek,…,em)，ek=eik·ejk，k=1,2,…,m；

(2)aBundle表示一個(gè)采購(gòu)包，它由兩個(gè)元素構(gòu)成：Items和Suppliers，其中，Items表示采購(gòu)包中的物品集合；Suppliers表示候選供應(yīng)商集合；若aBundle=?，則有aBundle.Items=?和aBundle.Suppliers=?；

(3)BunSolution表示采購(gòu)打包方案。

算法BUNDLING的具體步驟如下：

Step1輸入巡回路徑R={g1,g2,…,gn}和參數(shù)λ；

Step2初始化：BunSolution=?；aBundle=?，向量R*=(1,…,1)∈R|V|，循環(huán)變量j=1；

Step3Repeat

Step3.1R=R*?gj，其中g(shù)j為路徑R={g1,g2,…,gn}中第j個(gè)物品gj所對(duì)應(yīng)的行向量；

Step3.2如果Sum(R)≥λ且j

Step3.3如果Sum(R)<λ或j=n，則：R*中分量為1所對(duì)應(yīng)的供應(yīng)商集合記為tempSup,aBundle.Suppliers+=tempSup,BunSolution+={aBundle}；重置aBundle=?和R*=(1,…,1)∈R|V|；

Step3.4循環(huán)變量j=j+1；

Step4Untilj=n；

Step5輸出采購(gòu)打包方案，即BunSolution。

如對(duì)表1中的問題，若巡回路徑為R=(2,4,5,3,1)(即：x24=1,x45=1,x53=1,x31=1,x12=1)和λ=3，則該路徑將解碼為采購(gòu)打包方案{b11,b3,b1}，即{{2,4,5}×{1,3,4},{3}×{1,3,4},{1}×{2,3,4} }。這是因?yàn)椋篟*?i2?i4?i5=i2?i4?i5=(1,0,1,1,0)、Sum(i2?i4?i5)=λ、i2?i4?i5?i3=(1,0,1,0,0)且Sum(i2?i4?i5?i3)=2≤λ，故第一個(gè)采購(gòu)包將包含3個(gè)物品，即{2,4,5}；并有候選三個(gè)潛在供應(yīng)商，即{1,3,4}(i2?i4?i5的第1、第3和第4個(gè)分量為1)；同時(shí)，第二個(gè)采購(gòu)包從該路徑的第4個(gè)元素開始，又因?yàn)閕3?i1=(0,1,1,0,0)和|i3?i1|<λ，故：第二個(gè)采購(gòu)包為b3={3}×{1,3,4}，第三個(gè)采購(gòu)包為b1={1}×{2,3,4}。

從式(4)～(9)來看，正是由于BUNDLING算法的提出，從而使得采購(gòu)物品集合G意義上的一個(gè)巡回路徑可以解釋成一個(gè)采購(gòu)打包方案，進(jìn)而使得采購(gòu)物品打包問題可以表達(dá)為TSP問題。

2.2 基于GA的優(yōu)化算法

旅行商問題有著廣泛而且成熟的求解算法，其中，元啟發(fā)式算法(metaheuristic algorithms)是一類重要的求解算法[41]。本文選用遺傳算法(GA)來求解采購(gòu)物品打包問題的TSP模型，該算法采用GA的標(biāo)準(zhǔn)流程，此處不再贅述，以下介紹其主要組成部分，如：種群初始化、染色體編碼和解碼、適應(yīng)度評(píng)價(jià)、交叉與變異算子和個(gè)體選擇機(jī)制等。

2.2.1 染色體編碼和解碼

染色體編碼直接采用采購(gòu)物品集合G的全排列，如前文所述，采購(gòu)物品集合G的任意一個(gè)全排列，表示了集合G意義上的一個(gè)巡回路徑。以表1中的問題為例，其染色體編碼如圖1所示：

25134

染色體的解碼直接采用BUNDLING算法，該算法將染色體解碼成合法的采購(gòu)打包方案。

2.2.2 種群初始化、適應(yīng)度評(píng)價(jià)和個(gè)體選擇機(jī)制

按照染色體編碼策略，隨機(jī)構(gòu)造遺傳算法的初始種群。

由于采購(gòu)物品打包問題的優(yōu)化目標(biāo)為最小化采購(gòu)包數(shù)量，故染色體i的適應(yīng)度定義為：

Fit(i)=n+1-|BunSolution(i)|

(10)

其中，BunSolution(i)表示染色體i所對(duì)應(yīng)的采購(gòu)打包方案，|BunSolution(i)|表示該采購(gòu)打包方案中的采購(gòu)包數(shù)量，由適應(yīng)度的定義可知：Fit(i)≥1，這是因?yàn)椋鹤類毫拥牟少?gòu)打包方案是一個(gè)采購(gòu)包有且只包含一個(gè)物品，要采購(gòu)全部物品，則最多有n個(gè)采購(gòu)包。

選用帶有精英保留策略的輪盤賭選擇機(jī)制，即染色體i的生存概率定義為：

(11)

其中，Popsize為遺傳算法的種群數(shù)量。

2.2.3 交叉和變異算子

為避免產(chǎn)生不合法的染色體，選用POX交叉算子(Precedence Preserving Order-based Crossover)[42]。其過程如下：隨機(jī)選擇兩條染色體P1和P2，初始化兩條空的子代染色體O1和O2，將采購(gòu)物品集合G隨機(jī)劃分為兩個(gè)非空子集G1和G2；將P1中屬于集合G1中的元素所對(duì)應(yīng)的基因復(fù)制到O1的相同位置上，再將P2中屬于集合G2中的元素所對(duì)應(yīng)的基因從左到右依次填充到O1的空位上；互換P1和P2的角色得到O2。O1和O2為P1和P2的交叉結(jié)果。

以表1中的問題為例，圖2為POX交叉算子的運(yùn)算實(shí)例。

圖2 交叉算子實(shí)例

變異算子則采用簡(jiǎn)單的兩點(diǎn)倒位變異算子，即隨機(jī)選擇兩點(diǎn)并且兩點(diǎn)之間元素倒序排列。

3 數(shù)據(jù)實(shí)驗(yàn)

采用C-Sharp(C#)語言實(shí)現(xiàn)了上述采購(gòu)物品打包算法(以下簡(jiǎn)稱TSP-GA算法)，并進(jìn)行了若干數(shù)據(jù)實(shí)驗(yàn)，測(cè)試環(huán)境為：Windows 7操作系統(tǒng)，CPU i7 2.9G，內(nèi)存4G。

3.1 測(cè)試算法

選擇了兩種測(cè)試算法來對(duì)比分析TSP-GA算法的性能，即：(1)將采購(gòu)物品打包問題視為集合分區(qū)問題的實(shí)例，采用商業(yè)線性規(guī)劃工具軟件CPLEX(Version 12.2)來求解；(2)將采購(gòu)物品打包問題視為雙聚類問題的實(shí)例，采用MSB算法來求解(關(guān)于MSB雙聚類算法，參見文獻(xiàn)[43])。

如前文所述，將采購(gòu)物品打包問題視為集合分區(qū)問題的實(shí)例，需要預(yù)先采用枚舉法生成全部的潛在采購(gòu)包，而這會(huì)產(chǎn)生組合爆炸問題，因此，集合分區(qū)問題的算法只能解決小規(guī)模的采購(gòu)物品打包問題。

MSB算法是一個(gè)優(yōu)秀的雙聚類算法，能夠發(fā)現(xiàn)包含更多行和列的具有最大相似性的雙聚類；但正如前文所述，MSB算法所發(fā)現(xiàn)的雙聚類并不能保證“列數(shù)量不小于λ”的要求(采購(gòu)包有不能小于λ個(gè)候選供應(yīng)商)。為此，本文對(duì)MSB算法做適當(dāng)改進(jìn)，以確保改進(jìn)后的MSB算法(Improved MSB approach，IMSB)所發(fā)現(xiàn)的雙聚類的列數(shù)量不小于λ的要求。

IMSB算法的具體步驟如下：

Step1輸入矩陣G×V和參數(shù)λ；

Step2初始化如下變量：BunSolution=?，aBundle=?；

Step3Repeat

Step3.1置參考基因R*=(1,…,1)∈R|V|；

Step3.2計(jì)算矩陣G×V當(dāng)前的在參考基因R*下的最大相似性雙聚類(Maximum Similarity Bi-cluster)，記為A(I*,J*)；

Step3.3如果|I*|≥2且|J*|≥λ，則:aBundle.Items+=I*、aBundle.Suppliers+=J*、BunSolution+=aBundle；G=G-I*，aBundle=?；

Step4Until|I*|=1或|J*|<λ；

Step5若|G|≠0，則對(duì)于任意物品g∈G，做aBundle=?，aBundle.Items+={g},aBundle.Suppliers+=V(g)和BunSolution+={aBundle}；

Step6輸出采購(gòu)打包方案，即BunSolution。

其中，參考基因設(shè)為R*=(1,…,1)∈R|V|，以確保尋找到的雙聚類中的元素永遠(yuǎn)為1，從而滿足采購(gòu)包的定義；Step 3.3將每一個(gè)列數(shù)量不小于λ的雙聚類輸出成一個(gè)采購(gòu)包；Step 5則將G中雙聚類后剩余的每一個(gè)物品均打包成單一的采購(gòu)包。

3.2 測(cè)試問題

現(xiàn)有文獻(xiàn)中尚未有采購(gòu)物品打包問題的標(biāo)準(zhǔn)算例。為此，采用隨機(jī)的方式建立了七個(gè)不同規(guī)模的采購(gòu)物品打包問題，即：30/15/8、50/50/14、80/80/15、100/100/15、500/100/25、1000/200/35和1500/250/40。問題均表示成|G|/|V|/r的形式，其中，|G|表示采購(gòu)物品的數(shù)量，|V|表示供應(yīng)商的數(shù)量，r(λ≤r≤|V|)是一個(gè)非負(fù)整數(shù)。對(duì)于每個(gè)采購(gòu)物品打包問題，矢量g(即任意采購(gòu)物品)在滿足條件λ≤Sum(g)≤r的前提下隨機(jī)生成。

七個(gè)不同規(guī)模的采購(gòu)物品打包問題，市場(chǎng)競(jìng)爭(zhēng)控制參數(shù)均設(shè)為λ=3。對(duì)于其中的30/15/8問題，采用枚舉法求其全部的潛在采購(gòu)包。

若干實(shí)驗(yàn)后，TSP-GA和IMSB算法中參數(shù)設(shè)置如下：IMSB算法的α=0.4,β=0.5(α，β為MSB算法的內(nèi)置參數(shù))；TSP-GA算法的交叉概率為PC=0.4，變異概率為PM=0.1；對(duì)于第1個(gè)測(cè)試問題：Popsize=50，IteNo=50(遺傳算法的迭代次數(shù))；對(duì)于第2、3個(gè)測(cè)試問題：Popsize=50，IteNo=100；對(duì)于第4個(gè)測(cè)試問題：Popsize=80，IteNo=100；對(duì)于第5、6個(gè)測(cè)試問題：Popsize=100，IteNo=100；對(duì)于第7個(gè)測(cè)試問題：Popsize=100，IteNo=120。

3.3 小規(guī)模問題的優(yōu)化結(jié)果分析

表1給出了小規(guī)模問題30/15/8的優(yōu)化結(jié)果，其物品-供應(yīng)商矩陣G×V采用點(diǎn)陣圖表示(實(shí)心點(diǎn)表示數(shù)1，空心點(diǎn)表示數(shù)0)，通過枚舉法求得潛在的采購(gòu)包共174個(gè)，枚舉耗時(shí)13,199毫秒(ms)。其中，CPLEX求得該問題的最優(yōu)解——15個(gè)采購(gòu)包，CPLEX純粹用于計(jì)算時(shí)間為1,000ms，加上CPLEX所必須的枚舉潛在的采購(gòu)包的時(shí)間(13,199ms)，則CPLEX所需要的全部時(shí)間遠(yuǎn)高于TSP-GA和IMSB算法的計(jì)算時(shí)間；TSP-GA算法的優(yōu)化性能非常接近最優(yōu)解，而IMSB算法優(yōu)化性能稍差，但I(xiàn)MSB算法具有最快的計(jì)算速度。

造成這一現(xiàn)象的原因是：IMSB算法屬于貪心搜索算法，故而收斂速度很快，但易陷入局部最優(yōu)[50]，即容量更大的雙聚類很難被發(fā)現(xiàn)；TSP-GA算法屬于全局搜索進(jìn)化算法，有效地克服了貪心算法的缺點(diǎn)。同時(shí)，TSP-GA算法和IMSB算法均無需事先枚舉潛在的采購(gòu)包，故這兩種算法相對(duì)于CPLEX具有明顯的計(jì)算速度優(yōu)勢(shì)。

表2 30/15/8問題的優(yōu)化結(jié)果

3.4 不同規(guī)模問題的優(yōu)化結(jié)果分析

七個(gè)不同規(guī)模問題的優(yōu)化結(jié)果如表3所示，結(jié)果表明：TSP-GA和IMSB算法均能較好地實(shí)現(xiàn)采購(gòu)物品打包，其中，TSP-GA算法具有更好的優(yōu)化性能，能獲得包含更少采購(gòu)包的采購(gòu)打包方案；IMSB算法的計(jì)算時(shí)間小于TSP-GA算法的計(jì)算時(shí)間的1%，具有明顯的計(jì)算速度優(yōu)勢(shì)；同時(shí)，隨著問題規(guī)模的增大，兩種算法所求得的采購(gòu)打包方案的采購(gòu)包數(shù)量上的差值呈增長(zhǎng)趨勢(shì)。

表3 不同規(guī)模問題的優(yōu)化結(jié)果

TSP-GA算法的計(jì)算時(shí)間明顯高于IMSB算法，且計(jì)算時(shí)間隨著問題規(guī)模的增加而增加。但相對(duì)于問題的規(guī)模而言，其運(yùn)行速度尚在可以接受的時(shí)間范圍內(nèi)，如：對(duì)于七個(gè)問題中的最大規(guī)模的問題1500/250/40，計(jì)算時(shí)間僅為1476秒。這表明TSP-GA算法可以應(yīng)用于實(shí)際的大規(guī)模招標(biāo)采購(gòu)問題。如，國(guó)內(nèi)的藥品集中招標(biāo)采購(gòu)屬于典型的大規(guī)模招標(biāo)采購(gòu)問題(為了規(guī)范醫(yī)療機(jī)構(gòu)藥品購(gòu)銷工作和減輕社會(huì)醫(yī)藥費(fèi)用負(fù)擔(dān)，我國(guó)自2000年起開始實(shí)施藥品集中招標(biāo)采購(gòu))。文獻(xiàn)[27]描述了發(fā)生在2010年的第7界黑龍江省藥品集中采購(gòu)招標(biāo)的情況，在本次招標(biāo)采購(gòu)中涉及到1147種不同藥品。

4 結(jié)論

采購(gòu)商視角下的采購(gòu)物品打包問題對(duì)招標(biāo)采購(gòu)的績(jī)效有顯著影響，本文從采購(gòu)商的角度出發(fā)，通過對(duì)采購(gòu)包、采購(gòu)打包方案以及最優(yōu)采購(gòu)打包方案等概念的定義，首次建立了采購(gòu)物品打包問題的通用型數(shù)學(xué)模型，該模型延續(xù)了Jap等人所提出的概念化的采購(gòu)物品打包理論或策略；同時(shí)，指出該問題是集合分區(qū)問題和雙聚類問題的實(shí)例，證明了采購(gòu)物品打包問題屬于NP-hard問題；隨后，將采購(gòu)物品打包問題轉(zhuǎn)化成一類特殊的旅行商問題(TSP)，并基于遺傳算法設(shè)計(jì)了該問題的求解算法。實(shí)驗(yàn)結(jié)果表明：本文所設(shè)計(jì)的優(yōu)化算法具有很好的優(yōu)化性能和很高的計(jì)算效率。