黃　敏,錢小虎*,金東洋,王興偉

(東北大學(xué)信息科學(xué)與工程學(xué)院;流程工業(yè)綜合自動化國家重點實驗室(東北大學(xué)),遼寧沈陽110819)

成本結(jié)構(gòu)離散的兩屬性電子逆向拍賣機制設(shè)計

黃敏,錢小虎*,金東洋,王興偉

(東北大學(xué)信息科學(xué)與工程學(xué)院;流程工業(yè)綜合自動化國家重點實驗室(東北大學(xué)),遼寧沈陽110819)

在由一個采購商和多個供應(yīng)商組成的電子逆向拍賣系統(tǒng)中,針對供應(yīng)商成本結(jié)構(gòu)離散且成本和交貨期是其私有信息的兩屬性機制設(shè)計問題,為采購商提出一個新的基于協(xié)商的多輪逆向拍賣機制.建立基于協(xié)商的兩層分布式?jīng)Q策模型,提出基于交貨期偏差量的交貨期讓步策略、基于總體目標(biāo)值的交貨期讓步策略和基于總體目標(biāo)值的帶有隨機的交貨期讓步策略,并通過數(shù)值算例驗證了所提讓步策略的可行性和有效性.最后通過隨機算例對所提的三種讓步策略進行對比分析,結(jié)果表明基于總體目標(biāo)值的帶有隨機的交貨期讓步策略具有最佳的協(xié)商效果.

電子逆向拍賣;機制設(shè)計;兩層分布式?jīng)Q策模型;協(xié)商;交貨期讓步策略

1　引　言

電子逆向拍賣(electronic reverse auctions,ERA),是一個采購組織和一組預(yù)先審核合格的供應(yīng)商之間的在線實時動態(tài)拍賣系統(tǒng).采購組織明確規(guī)定產(chǎn)品或服務(wù)的設(shè)計、質(zhì)量、數(shù)量、交貨期等相關(guān)條款,供應(yīng)商必須在規(guī)定的時間內(nèi)通過連續(xù)降價投標(biāo)來贏得向采購組織提供產(chǎn)品或服務(wù)的合同[1],通常采購組織根據(jù)投標(biāo)結(jié)果選擇具有競爭力的供應(yīng)商.

隨著信息技術(shù)的飛速發(fā)展和全球化市場競爭的日益激烈,傳統(tǒng)的采購模式已難以快速響應(yīng)市場需求、贏得市場競爭.作為一種新的采購模式,ERA成為政府采購和大型企業(yè)采購降低成本、提高效率和優(yōu)化資源的重要戰(zhàn)略選擇[1-3],其運行和發(fā)展也是學(xué)術(shù)界關(guān)注的熱點.目前,ERA已經(jīng)成功應(yīng)用于通用電氣(General Electric)、通用汽車(General Motors)、柏克德(Bechtel)等制造和服務(wù)公司[1,4],受到企業(yè)界的廣泛關(guān)注.因此,對ERA展開研究可以說既有很高的學(xué)術(shù)價值,更有重要的應(yīng)用意義.

目前,關(guān)于ERA機制設(shè)計的研究依據(jù)采購商和供應(yīng)商的決策地位不同主要包括兩個方面:

一方面研究供應(yīng)商靜態(tài)投標(biāo)拍賣機制.文獻[5]以政府采購為背景,首先研究了考慮價格和質(zhì)量的兩屬性逆向拍賣問題,設(shè)計了打分函數(shù)拍賣機制(scoring rule auction),并證明了二維的收益等價定理.文獻[6]以零售業(yè)為背景,考慮價格和采購量兩個屬性,設(shè)計了帶有入場費的最優(yōu)供應(yīng)合同拍賣機制(supply contract auction),并證明該機制與供應(yīng)商數(shù)目無關(guān),但沒有考慮完成交易的其他成本(如運輸成本、稅費、貨物檢驗成本等).文獻[7]假設(shè)其他成本是采購商的私有信息,設(shè)計了考慮供應(yīng)商的報價和其他成本的兩屬性逆向拍賣機制,并分析了其他成本對采購商收益的影響,但沒有對供應(yīng)商投標(biāo)中的非價格屬性進行審查.文獻[8]設(shè)計了考慮供應(yīng)商審查的逆向拍賣機制,并說明當(dāng)審查費用較低時,預(yù)先審查對采購商來說是有益的,但是當(dāng)審查費用較高時,事后審查是采購商明智的選擇.針對供應(yīng)源有限的情形,文獻[9]設(shè)計了考慮合作激勵的多屬性逆向拍賣機制,并通過仿真分析說明對采購商而言,該機制比現(xiàn)有的不帶激勵的拍賣機制具有更高的效用.針對重復(fù)采購問題,文獻[10]設(shè)計了基于供應(yīng)商歷史績效的馬爾科夫決策機制,數(shù)值分析結(jié)果表明對采購商而言,該機制比基于績效得分(performance score-based)的選擇機制具有更高的效用和更好的質(zhì)量.上述文獻均假設(shè)采購商為主導(dǎo)的決策情形,針對不同的問題為采購商設(shè)計不同的逆向拍賣機制,但現(xiàn)實中采購商與供應(yīng)商常常處于對等決策地位,且雙方具有更多的不對稱信息.

另一方面則研究供應(yīng)商動態(tài)投標(biāo)拍賣機制.文獻[11]首先考慮帶有數(shù)量折扣的組合逆向拍賣機制設(shè)計問題,假設(shè)供應(yīng)商的成本結(jié)構(gòu)是離散的,建立帶有數(shù)量折扣的組合逆向拍賣勝者確定問題的模型,提出多輪動態(tài)逆向拍賣機制,但僅考慮了單一屬性價格.針對多屬性動態(tài)逆向拍賣機制設(shè)計問題,文獻[12]假設(shè)采購商知道供應(yīng)商的成本結(jié)構(gòu)和投標(biāo)策略,根據(jù)據(jù)供應(yīng)商每一輪的投標(biāo)結(jié)果,采用逆向優(yōu)化(inverse optimization)方法設(shè)計最優(yōu)逆向拍賣機制,從而使采購組織的利潤最大,但假設(shè)供應(yīng)商的成本結(jié)構(gòu)是連續(xù)的.對于供應(yīng)商成本結(jié)構(gòu)離散的多屬性逆向拍賣問題,文獻[13]假設(shè)供應(yīng)商采用近視最優(yōu)反應(yīng)(myopic best-response,MBR)投標(biāo)策略,設(shè)計了考慮供應(yīng)商之間的信息泄露的動態(tài)逆向拍賣機制,并證明該機制是改進的VCG機制,但沒有基于采購商的視角進行研究.文獻[14]針對供應(yīng)商供應(yīng)能力有限的逆向拍賣機制設(shè)計問題,基于采購商的視角設(shè)計了嵌入線性規(guī)劃動態(tài)求解的最優(yōu)拍賣機制,分析了博弈論框架下供應(yīng)商的順序投標(biāo)策略,并給出勝標(biāo)者的上確界.對于考慮制造商生產(chǎn)計劃的逆向拍賣問題,文獻[15]基于采購商的視角建立了雙層分布式?jīng)Q策模型,分別描述采購商和制造商的決策過程,并通過優(yōu)化方法求解雙層模型中的分配量、交貨期、報價和生產(chǎn)計劃.針對競價人數(shù)不足的網(wǎng)上逆向組合拍賣問題,文獻[16]提出一種捆綁與組合相結(jié)合的兩輪拍賣機制,數(shù)值分析結(jié)果表明該機制可以提高拍賣人的經(jīng)濟收益.上述文獻均假設(shè)采購商知道供應(yīng)商的決策偏好,針對不同的問題研究采購商的逆向拍賣機制,但現(xiàn)實中存在供應(yīng)商決策偏好是未知的情況.

綜上,現(xiàn)有文獻沒有同時考慮供應(yīng)商成本結(jié)構(gòu)離散且決策偏好未知的逆向拍賣機制設(shè)計.而現(xiàn)實采購中,由于數(shù)量折扣供貨模式可以提高供應(yīng)商的收益[17],供應(yīng)商在供貨時通常采用數(shù)量折扣模式,如全球最大的食品生產(chǎn)商之一瑪氏公司(Mars)在采購時要求供應(yīng)商提供數(shù)量折扣的供貨模式[11],此時供應(yīng)商的成本結(jié)構(gòu)是離散的.同時,采購商通常不知道供應(yīng)商的決策偏好.并且信息不對稱情況下的動態(tài)逆向拍賣機制能使采購商的采購費用更低[18].因此對供應(yīng)商成本結(jié)構(gòu)離散且供應(yīng)商決策偏好未知的動態(tài)逆向拍賣機制設(shè)計問題展開研究,具有理論和實際意義.

本文基于采購商的視角,就這一類現(xiàn)實中的問題展開研究,提出基于協(xié)商的多輪逆向拍賣機制.與文獻[15]相比,本文有四個重要的不同之處:其一,本文考慮的是采購商和供應(yīng)商(分銷商或零售商)之間的問題,采購商決策分配量和交貨期,供應(yīng)商決策報價;而文獻[15]考慮的是采購商和制造商之間的問題,采購商決策分配量和交貨期,制造商決策報價和生產(chǎn)計劃.其二,本文假設(shè)供應(yīng)商的決策偏好是未知的,即供應(yīng)商的決策模型未知,采購商只知道供應(yīng)商以一定的概率選擇某種策略,但不知道供應(yīng)商具體選擇哪種策略;而文獻[15]假設(shè)供應(yīng)商的決策偏好是已知的,即供應(yīng)商的決策模型已知,采購商知道供應(yīng)商只需優(yōu)化相應(yīng)的決策模型,供應(yīng)商的決策是確定的.其三,對所建立的雙層分布式?jīng)Q策模型,本文通過基于協(xié)商的讓步策略和基于優(yōu)化的方法對上層模型進行求解,即通過優(yōu)化方法確定分配量,通過采購商讓步策略確定交貨期,同時通過供應(yīng)商讓步策略確定下層模型的最優(yōu)報價;而文獻[15]主要是通過優(yōu)化的方式來求解雙層模型的,即通過KKT優(yōu)化條件(Karush-Kuhn-Tucker optimality conditions)和最大最小決策方法(max-min decision concept)將雙層模型轉(zhuǎn)化為單層模型進行求解,對轉(zhuǎn)化后的上層模型進行優(yōu)化可確定分配量和交貨期,對轉(zhuǎn)化后的下層模型進行優(yōu)化可以確定生產(chǎn)計劃和最優(yōu)報價.其四,本文的協(xié)商終止準(zhǔn)則是達到最大協(xié)商次數(shù)或連續(xù)5次協(xié)商結(jié)果不變,由采購商和供應(yīng)商共同決定;而文獻[15]實質(zhì)上是一個雙層優(yōu)化問題,并沒有協(xié)商過程.

本文首先建立了基于協(xié)商的兩層分布式?jīng)Q策模型,用于刻畫采購商和供應(yīng)商的決策與信息交互過程.進而提出基于交貨期偏差量的交貨期讓步策略、基于總目標(biāo)值的交貨期讓步策略和基于總目標(biāo)值的帶有隨機的交貨期讓步策略,并通過數(shù)值算例驗證了所提讓步策略的可行性和有效性.最后通過50組隨機算例對這三種讓步策略進行對比,結(jié)果表明基于總目標(biāo)值的帶有隨機的交貨期讓步策略好于其他兩種讓步策略.

2　問題描述及模型

2.1問題描述

在考慮價格和交貨期兩屬性的ERA中,采用基于協(xié)商的多輪密封投標(biāo)方式進行采購:采購商首先公布采購量和供應(yīng)商的初始分配量及初始交貨期;然后供應(yīng)商間接競標(biāo),即根據(jù)自己的成本結(jié)構(gòu)以及分配量和交貨期進行密封投標(biāo),其投標(biāo)結(jié)果將影響采購商的分配決策;最后采購商調(diào)整每個供應(yīng)商的分配量和交貨期,同時判斷是否滿足協(xié)商終止準(zhǔn)則,如果不滿足,則進入下一輪協(xié)商.

模型基本假設(shè)如下:

假設(shè)1采購商向供應(yīng)商購買Q個同類商品,供應(yīng)市場貨源充足,但供應(yīng)商i(i=1,2,...,n,n＞2)的供應(yīng)能力有限,其最大供應(yīng)量為

假設(shè)2供應(yīng)商的成本結(jié)構(gòu)具有批量折扣和交貨期折扣的特征,為簡單起見,設(shè)單位成本隨著批量和交貨期的增加而降低.

假設(shè)3采購商的費用和交貨期的預(yù)算分別為c0和d0,即實際費用和交貨期與預(yù)算的偏差越小越好.

假設(shè)4供應(yīng)商的報價策略帶有隨機性,獲得分配量的供應(yīng)商以較小的概率降價,未獲得分配量的供應(yīng)商以較大的概率降價.

假設(shè)5采供雙方都是風(fēng)險中性的理性決策者,其中采購商的目標(biāo)是最小化實際費用與期望費用的偏差率和實際交貨期與期望交貨期的偏差率,供應(yīng)商的目標(biāo)是在最低報價的約束下獲得更多的分配量.

圖1　采購商與供應(yīng)商的信息交換過程Fig.1　The information exchange process between buyer and suppliers

2.2兩層分布式?jīng)Q策模型

針對上述問題,采購商首先根據(jù)上一輪的交貨期和報價決策本輪的最優(yōu)分配量,然后根據(jù)上一輪的分配量和本輪的分配量來決策本輪的交貨期;而供應(yīng)商根據(jù)上一輪的分配量、本輪的分配量和交貨期決策報價.為此,構(gòu)建確定最優(yōu)分配量和最優(yōu)報價的兩層分布式?jīng)Q策模型如下.

上層決策,即采購商決策模型(TM)為

下層決策,即供應(yīng)商決策模型(BM)為

上述各式中符號、參數(shù)及變量含義如下:

t為拍賣輪數(shù),t=1,2,...,T;

Ti為采購商與供應(yīng)商i進行交易的費用,即交易費用;

wc為費用偏差率權(quán)重,0＜wc＜1;

wd為交貨期偏差率權(quán)重,0＜wd＜1,且wc+wd=1;

α為供應(yīng)商報價的降價幅度,0＜α≤1;

λ1為供應(yīng)商本輪的分配量大于上一輪的分配量時降價的概率;

λ2為供應(yīng)商本輪的分配量小于上一輪的分配量時降價的概率.

上層采購商根據(jù)上一輪報價決策本輪分配量,目標(biāo)函數(shù)如式(1)所示,包括兩部分:采購費用的偏差率和交貨期的偏差率;式(2)表示采購需求;式(3)是供應(yīng)商的能力約束;式(4)是實際采購費用與目標(biāo)費用的偏差量約束;式(5)表示實際交貨期與期望交貨期的偏差量約束;式(6)表示是否選擇供應(yīng)商;式(7)是分配量和交貨期偏差量約束,本文假設(shè)分配量和交貨期均為整數(shù);式(8)是采購費用偏差量約束.

下層供應(yīng)商根據(jù)上層采購商傳遞的分配量和交貨期進行報價,其報價讓步策略如式(9)所示:當(dāng)本輪的報價大于上一輪報價時,按本輪報價;當(dāng)本輪報價小于上一輪報價且本輪的分配量大于上一輪的分配量或等于最大供應(yīng)量時,以較小的概率按本輪報價(即降價),以較大的概率按上一輪報價(即不降價);當(dāng)本輪報價小于上一輪報價且本輪的分配量小于上一輪的分配量時,以較大的概率按本輪報價(即降價),以較小的概率按上一輪報價(即不降價).式(10)是供應(yīng)商的降價策略,為了獲得更多的分配量,供應(yīng)商會以降價系數(shù)α按照上一輪的報價進行降價,但如果降價后的報價低于成本價,則按成本價報價.

3　基于協(xié)商的多輪逆向拍賣機制設(shè)計

基于協(xié)商的多輪逆向拍賣機制設(shè)計主要包括拍賣啟動階段初始量設(shè)置、采購商決策過程設(shè)計、供應(yīng)商決策過程設(shè)計及協(xié)商終止準(zhǔn)則設(shè)計.拍賣啟動時,上層采購商首先向下層供應(yīng)商傳遞初始分配量和初始交貨期,供應(yīng)商根據(jù)采購商傳遞的分配量和交貨期確定初始報價,并計算此時的交易目標(biāo)值.此后,采購商首先根據(jù)供應(yīng)商的報價求解上層模型(TM),確定最優(yōu)分配量,并根據(jù)交貨期讓步策略確定交貨期;然后供應(yīng)商根據(jù)采購商傳遞的分配量和交貨期求解下層模型(BM),并進行報價,直到協(xié)商終止.

基于協(xié)商的多輪拍賣機制流程具體如下:

步驟1拍賣啟動階段初始量設(shè)置

步驟1.1拍賣啟動,t=1;

步驟1.2上層采購商分配給下層每位供應(yīng)商相同的分配量q和相同的交貨期d(若超出供應(yīng)商的最大供應(yīng)能力,則自動按最大供應(yīng)能力分配);

步驟1.3下層每位供應(yīng)商根據(jù)上層采購商傳遞的分配量和交貨期,確定自己的最低報價并按最低報價的w倍進行報價;

步驟1.4采購商確定初始投標(biāo)目標(biāo)值G0和初始交易目標(biāo)值

步驟2上層采購商決策過程

步驟2.1上層采購商在獲得下層每位供應(yīng)商遞交的報價后,通過求解上層模型(TM)對采購量進行重新分配;

步驟2.2上層采購商根據(jù)下層供應(yīng)商本輪和上一輪的分配量設(shè)計相應(yīng)的交貨期讓步策略,同時根據(jù)交貨期讓步策略確定新的交貨期;

步驟3下層供應(yīng)商決策過程

步驟3.1下層供應(yīng)商根據(jù)獲得的分配量和上層采購商對交貨期的決策,確定自己的最低報價

步驟3.2下層供應(yīng)商通過求解下層模型(BM)確定本輪的投標(biāo)價格;

步驟4協(xié)商終止準(zhǔn)則

步驟4.1本輪競標(biāo)結(jié)束后,上層采購商計算本輪的投標(biāo)目標(biāo)值Gt;

步驟4.2上層采購商將本輪的投標(biāo)目標(biāo)值與上一輪的交易目標(biāo)值進行比較,若對本輪投標(biāo)結(jié)果滿

步驟4.3判斷是否滿足協(xié)商終止條件,如果滿足,則協(xié)商終止,進行交易;否則,進行下一輪協(xié)商, 即t=t+1,并跳轉(zhuǎn)到步驟2.

3.1拍賣啟動設(shè)置

拍賣開始時,由上層采購商首先向下層每家供應(yīng)商傳遞兩個啟動量:采購數(shù)量和交貨期.為使得分配具有公平性,對每家供應(yīng)傳遞的兩個啟動量分別保持相同,設(shè)為下層每家供應(yīng)商則根據(jù)這兩個量向上層采購商遞交自己的報價.首先,每家供應(yīng)商根據(jù)上層采購商分配的采購量和指定的交貨期,找出對應(yīng)的最低報價,然后以最低報價的w(w＞1)倍進行投標(biāo),即

3.2采購商采購量決策方法

采購商通過下層供應(yīng)商上一輪的報價決策本輪的采購量分配方案,通過分配采購量影響供應(yīng)商的報價決策,使想要獲得更多分配量的供應(yīng)商降低報價.由于考慮供應(yīng)商供應(yīng)能力的上層模型(TM)是NP難問題,對于小規(guī)模的問題通常采用枚舉算法進行求解,對于大規(guī)模的問題則可以通過啟發(fā)式算法或遺傳算法等智能優(yōu)化算法進行求解.

3.3采購商交貨期讓步策略

由于交貨期對拍賣結(jié)果具有較大的影響,因此本文提出三種交貨期的讓步策略:基于交貨期偏差量的交貨期讓步策略、基于總目標(biāo)值的交貨期讓步策略和基于總目標(biāo)值的帶有隨機的交貨期讓步策略,分別記為策略1、策略2和策略3.下面重點介紹這三種讓步策略.

3.3.1基于交貨期偏差的交貨期讓步策略

由于上層模型(TM)通過分配量的多少間接控制供應(yīng)商的報價,使實際費用與期望費用的偏差最小,而采購商的目標(biāo)是實際費用和交貨期與期望費用和交貨期的偏差率最小化,因此采購商需要制定相應(yīng)的交貨期讓步策略,使實際交貨期與期望交貨期的偏差最小.本文首先考慮基于交貨期偏差量的交貨期讓步策略,記為策略1.策略1的基本思想是,當(dāng)實際交貨期大于期望交貨期時,采購商通過降低交貨期可以減小交貨期偏差;同時,當(dāng)實際交貨期小于或等于期望交貨期時,采購商通過增加交貨期可以降低費用偏差.定義

為第t輪供應(yīng)商i交貨期的變化趨勢.

設(shè)Di為供應(yīng)商i的交貨期集合,則采購商對供應(yīng)商交貨期dti的決策為

式(11)表示若上一輪的交貨期大于期望交貨期,則減小本輪的交貨期;否則增加本輪的交貨期;式(12)表明如果本輪所求得的交貨期屬于交貨期集合Di且不小于期望交貨期,則按本輪算得的交貨期成交;否則按上一輪的交貨期成交.

3.3.2基于總目標(biāo)值的交貨期讓步策略

策略1是從局部進行考慮的,僅通過交貨期偏差決策交貨期,帶有一定的局限性,因此提出改進的基于總目標(biāo)值的交貨期讓步策略,記為策略2.策略2的基本思想是,當(dāng)目標(biāo)值減小時則按照上一輪交貨期的變化方向確定交貨期,否則按照上一輪交貨期變化的反方向確定交貨期.具體描述如下.

第一輪,與策略1相同,根據(jù)實際交貨期與期望交貨期的偏差量確定交貨期,如式(11)–式(12)所示.此后(t≥2),定義

為第t輪供應(yīng)商i交貨期的變化趨勢,其中Gt-1是第t-1輪投標(biāo)后的目標(biāo)值.此時,則采購商對供應(yīng)商交貨期dti的決策為式(12).

3.3.3基于總目標(biāo)值的帶有隨機的交貨期讓步策略

策略2根據(jù)整體目標(biāo)值決策交貨期,而不是根據(jù)不同供應(yīng)商不同目標(biāo)值的偏差決策交貨期,因此提出策略2的改進策略,即基于總目標(biāo)值的帶有隨機的交貨期讓步策略,記為策略3.策略3的基本思想是,當(dāng)本輪的分配量大于上一輪的分配量時,以較大的概率保持交貨期不變,以較小的概率使交貨期變化;否則以較小的概率保持交貨期不變,以較大的概率使交貨期變化.具體描述如下.

第一輪的交貨期由式(11)—式(12)確定,此后(t≥2)交貨期的變化趨勢由式(13)確定,同時采購商根據(jù)供應(yīng)商的不同情況確定交貨期dti的讓步策略為

其中γ1,γ2,υ1,υ2為參數(shù),且γ1,υ1,υ2＞0.5,γ2＜0.5.式(14)表明若本輪的分配量大于上一輪的分配量或等于最大供應(yīng)量,則以較大的概率γ1保持交貨期不變,以較小的概率1-γ1變化交貨期,具體為以較大的概率υ1按照目標(biāo)值減小的方向定交貨期,以較小的概率1-υ1按照目標(biāo)值增加的方向定交貨期;否則以較小的概率γ2保持交貨期不變,以較大的概率1-γ2變化交貨期,具體為以較大的概率υ2按照目標(biāo)值增加的方向定交貨期,以較小的概率1-υ2按照目標(biāo)值減小的方向定交貨期.對于所求的交貨期,若dti/∈Di或dti＜d0,則保持上一輪的交貨期.

3.4終止準(zhǔn)則

設(shè)定到達最大拍賣輪次(T=50)或連續(xù)5次協(xié)商結(jié)果一致為協(xié)商終止準(zhǔn)則.本文上層模型(TM)是采購商的分配策略,用于決策最優(yōu)分配量,并不是每一輪最終成交情況,而實際成交的目標(biāo)值是在本輪協(xié)商完成以后確定的.定義[x]+=max{x,0},則第t輪投標(biāo)后的目標(biāo)值為

4　集中式?jīng)Q策模型

為了分析所提方法的有效性,下面考慮集中式?jīng)Q策模型,即采購商和供應(yīng)商之間信息是對稱的.此時,采購商只需建立如下的集中式?jīng)Q策模型(CM).

上述各式中符號含義如下:

xi為0–1決策變量,若選擇供應(yīng)商i則為1,否則為0;

qi為整數(shù)決策變量,分配給供應(yīng)商i的分配量;

di為決策變量,供應(yīng)商i的交貨期;

c+0為實際采購費用與目標(biāo)費用的偏差,c+0≥0;

pi(qi,di)為供應(yīng)商i對應(yīng)于批量和交貨期的最低報價,不失一般性,設(shè)pi(qi,di)為供應(yīng)商的成本.

集中式?jīng)Q策模型(CM)與上層決策模型(TM)的區(qū)別在于:(TM)模型中采購商需要根據(jù)供應(yīng)商上一輪的報價決策下一輪的最優(yōu)分配量,同時需要通過不同的讓步策略確定最終的交貨期,而(CM)模型中所有成本和交貨期的信息均已知,采購商只需要求解(CM)模型就可以確定最優(yōu)分配量和最優(yōu)交貨期.

5　數(shù)值算例

為說明基于協(xié)商的多輪逆向拍賣機制和所提三種交貨期讓步策略的可行性和有效性,下面通過數(shù)值算例進行對比分析.首先通過比較三種策略的投標(biāo)值和交易值說明所提三種讓步策略的收斂過程,進而說明所提策略的有效性;其次通過隨機產(chǎn)生的50組數(shù)值算例將三種策略與集中決策結(jié)果進行對比分析,說明基于總目標(biāo)值的帶有隨機的交貨期讓步策略好于另外兩種策略,但由于信息不對稱,仍無法達到集中式?jīng)Q策的效果;最后通過參數(shù)分析說明所提策略具有魯棒性.

5.1交貨期讓步策略分析

例1假設(shè)采購方的需求總量Q=1 500,采購預(yù)算為c0=7 500元,期望交貨時間為d0=2天,兩個權(quán)重系數(shù)分別設(shè)置為wc=0.7和wd=0.3,初始量設(shè)置為q=200,d=2.有N=10個供應(yīng)商參與競標(biāo),供應(yīng)商的成本是私有信息.每家供應(yīng)商為獲得更多利潤,開始都不以最低價格進行報價,此后通過競爭均以α=0.9的倍數(shù)進行降價,降價概率為λ1=0.3,λ2=0.7.

采用C++語言對策略1進行仿真,得每一輪的投標(biāo)結(jié)果和實際交易結(jié)果曲線,如圖2所示.

圖2　策略1投標(biāo)值與交易值對比Fig.2　The comparison of bid value and deal value based on strategy 1

由圖2可知,對于策略1而言,前4輪拍賣的目標(biāo)值連續(xù)下降,這是由于供應(yīng)商降價對目標(biāo)值的影響抵消了交貨期變化帶來的影響.當(dāng)拍賣進行到第22輪時具有最佳的協(xié)商效果,目標(biāo)達到最小值0.755 627,交易值不再變化,而投標(biāo)值由于交貨期的變化而往復(fù)交替波動.仿真結(jié)果表明所提讓步策略的可行性和有效性,但在信息已知的情況下采購商的最優(yōu)目標(biāo)值為0.528 313,遠遠小于策略1的目標(biāo)值.

對于例1,用C++對策略2進行仿真,得每一輪的投標(biāo)結(jié)果和實際交易結(jié)果曲線,如圖3所示.

圖3　策略2投標(biāo)值與交易值對比Fig.3　The comparison of bid value and deal value based on strategy 2

由圖3可知策略2前14輪拍賣目標(biāo)值連續(xù)下降,并在第14輪時達到最小0.750 84,目標(biāo)值略小于策略1.這是由于策略2搜索交貨期的范圍比策略1大,可以沿著目標(biāo)值下降的方向?qū)ふ医回浧?此外,策略1的投標(biāo)值曲線由于交貨期的變化而往復(fù)交替變化,而策略2的投標(biāo)值曲線則會保持1輪再變化,這是由于當(dāng)交貨期沿著交貨期減小的方向變化且實際交貨期小于期望交貨期時,本輪的交貨期與上一輪保持一致,且報價已經(jīng)降到最低.仿真結(jié)果表明策略2的可行性和有效性,但此時目標(biāo)值仍比信息已知的情況大.

令γ1=0.7,γ2=0.3,υ1=0.7,υ2=0.7.對于例1,用C++對策略3進行仿真,得每一輪的投標(biāo)結(jié)果和實際交易結(jié)果曲線,如圖4所示.

由圖4可知策略3前5輪的目標(biāo)值持續(xù)下降,且在第22輪目標(biāo)達到最小值0.592 393,其目標(biāo)值遠好于策略2.這是由于策略3對交貨期的尋找范圍比策略2大,且在第26輪時達到協(xié)商終止條件,整個逆向拍賣過程結(jié)束.仿真結(jié)果表明所提讓步策略的可行性和有效性,但是此時的目標(biāo)值與信息已知情況下的目標(biāo)值0.528 313仍有一定的差距.存在這種差距的主要原因是信息不對稱造成的.

圖4　策略3投標(biāo)值與交易值對比Fig.4　The comparison of bid value and deal value based on strategy 3

5.2交貨期讓步策略對比分析

為了進一步比較策略1、策略2和策略3,隨機產(chǎn)生50組10個供應(yīng)商的成本信息的數(shù)值算例,對其進行仿真.令πjk表示第j個策略第k組算例的最終結(jié)果,πk表示完全信息下第k組算例的最優(yōu)值,其中j= 1,2,3且k=1,2,...,50,則三種讓步策略的評價準(zhǔn)則定義為

式(25)表示對于每個策略而言50組算例的平均偏差率,偏差率越小說明所提讓步策略的最終結(jié)果與完全信息下的最優(yōu)值越接近.

為了獲得每個策略的最優(yōu)參數(shù)組合,需要對初始啟動量和讓步策略中的參數(shù)進行測試.參數(shù)測試的具體步驟為:首先,固定交貨期初始值,測試初始分配量;其次,固定測得的較好的初始分配量,測試初始交貨期;最后,固定初始交貨期和初始分配量,測試策略3中的隨機概率.按照以上三個步驟可以獲得每個策略的最優(yōu)參數(shù)組合如下:策略1的最優(yōu)參數(shù)組合為q0=400,d0=4;策略2的最優(yōu)參數(shù)組合為q0=400, d0=5;策略3的最優(yōu)參數(shù)組合為q0=500,d0=4,γ1=0.8,γ2=0.4,υ1=0.7,υ2=0.7.

在上述參數(shù)組合下,用C++對50組算例進行仿真,結(jié)果如圖5所示.

圖5　三種讓步策略及集中式?jīng)Q策結(jié)果對比分析Fig.5　The comparison of three concession strategies and the results of centralized decision-making

由圖5可知策略3好于策略1和策略2且策略2略好于策略1,說明在不完全信息下采用擴大交貨期尋找范圍的讓步策略能找到更接近最優(yōu)值的解.此外,由策略1、策略2和策略3所求得的50組算例的平均偏差率分別為0.298 305,0.297 281和0.143 776,且從50組算例的個數(shù)對比也可以看出,策略3的目標(biāo)值小于等于策略1的有47個,小于等于策略2的有47個,策略2的目標(biāo)值小于等于策略1的有36個,進一步說明策略3具有最佳的協(xié)商效果.

5.3供應(yīng)商決策參數(shù)對交貨期讓步策略的影響

為說明供應(yīng)商決策參數(shù)α,λ1,λ2對不同交貨期策略的影響,采用隨機產(chǎn)生的50組算例進行仿真,分別計算α=0.9,0.8,0.7,λ1=0.5,0.3,0.7和λ1=0.5,0.7,0.3時的平均偏差率,其中λ1=λ2=0.5表示下層決策完全隨機的情況,λ1=0.7,λ2=0.3表示下層決策出現(xiàn)反常的情況.仿真結(jié)果如表1所示.

表1　供應(yīng)商決策參數(shù)對三種讓步策略的影響Table 1　The impact of suppliers’decision-making parameters on three concession strategies

由表1可知供應(yīng)商的降價系數(shù)對每種策略有顯著的影響,即對于相同的降價概率,降價系數(shù)越小,每種策略的偏差率越小,說明競爭越激烈,供應(yīng)商的降價系數(shù)越小,則其降價幅度越大,從而對采購商越有利;供應(yīng)商的降價概率對每種策略的影響不顯著,且在相同的參數(shù)組合下策略3好于策略2進而好于策略1,說明所提的交貨期讓步策略對供應(yīng)商決策參數(shù)的變化具有魯棒性.

5.4采購商權(quán)重參數(shù)對交貨期讓步策略的影響

為說明采購商所設(shè)置價格權(quán)重wc和交貨期權(quán)重wd對交貨期讓步策略的影響,令α=0.9,λ1=0.3, λ2=0.7,采用50組隨機算例進行仿真,在采購商更看重價格(wc=0.7,wd=0.3)、同等看重價格和交貨期(wc=0.5,wd=0.5)和更看重交貨期(wc=0.3,wd=0.7)的情況下,分析采購商權(quán)重參數(shù)對交貨期讓步策略的影響.

1)不同權(quán)重參數(shù)下三種讓步策略目標(biāo)值對比分析

在三種權(quán)重參數(shù)分配情況下,針對50組隨機算例,分別計算三種讓步策略的最終交易目標(biāo)值,結(jié)果如圖6所示.

由圖6可知當(dāng)價格權(quán)重較大時,策略3明顯好于策略1和策略2;當(dāng)交貨期權(quán)與價格權(quán)重相當(dāng)或較大時,策略1、策略2和策略3的差異不顯著.這是由于采購商的目標(biāo)僅與價格偏差率和交貨期平均偏差率有關(guān),當(dāng)采購商交貨期權(quán)重與價格權(quán)重相當(dāng)或較大時,價格的偏差率占目標(biāo)值的比重較小,而交貨期平均偏差率占目標(biāo)值的比重較大,交貨期平均偏差率的大小與目標(biāo)值的大小無明顯差異.此時,對交貨期和目標(biāo)的調(diào)整機制達到相似的效果,因此三種讓步策略的差異不顯著.

2)不同權(quán)重參數(shù)下三種讓步策略與最優(yōu)值平均偏差率對比分析

為進一步說明采購商權(quán)重參數(shù)對交貨期讓步策略的影響,針對50組隨機算例,分別計算不同權(quán)重參數(shù)下三種讓步策略與最優(yōu)值的平均偏差率,結(jié)果如表2所示.

表2　不同權(quán)重下三種讓步策略與最優(yōu)值的平均偏差率對比Table 2　The comparison of three concession strategies’average deviations with the optimal value under different weights

由表2可知當(dāng)價格權(quán)重較大時,策略3明顯好于策略1和策略2;當(dāng)交貨期權(quán)重與價格權(quán)重相當(dāng)或較大時,三種讓步策略的差異不顯著.總體而言,策略3具有最佳的協(xié)商效果.

圖6　三種讓步策略不同權(quán)重下的目標(biāo)值對比Fig.6　The comparison of three concession strategies’results under different weights

綜上,通過對不同權(quán)重下三種讓步策略目標(biāo)值的對比分析和三種讓步策略與最優(yōu)值平均偏差率的對比分析可知,策略3對采購商權(quán)重參數(shù)的變化有較好的魯棒性.

6　結(jié)束語

本文考慮由一個采購商和多個供應(yīng)商組成的電子逆向拍賣系統(tǒng).針對供應(yīng)商成本信息未知且供應(yīng)能力有限的考慮價格和交貨期的兩屬性逆向拍賣機制設(shè)計問題,建立了基于協(xié)商的多輪拍賣兩層分布式?jīng)Q策模型,提出確定交貨期的三種讓步策略,即基于交貨期偏差的交貨期讓步策略、基于總目標(biāo)值的交貨期讓步策略和基于總目標(biāo)值的帶有隨機的交貨期讓步策略,并通過隨機產(chǎn)生的50組數(shù)值算例對三種讓步策略進行對比分析,結(jié)果表明:1)三種讓步策略均具有可行性和有效性;2)基于總目標(biāo)值的帶有隨機的交貨期讓步策略具有最佳的協(xié)商效果;3)基于總目標(biāo)值的帶有隨機的交貨期讓步策略對供應(yīng)商決策參數(shù)和采購商權(quán)重參數(shù)的變化均具有魯棒性;4)供應(yīng)商之間的競爭越激烈,則其降價幅度越大,對采購商越有利.

本文的研究為信息不對稱環(huán)境下的考慮供應(yīng)商能力的多屬性電子逆向拍賣機制提供理論支持,對管理實踐中不對稱信息環(huán)境下的逆向拍賣機制設(shè)計與供應(yīng)商選擇具有一定的指導(dǎo)意義.本文僅考慮了價格和交貨期兩個屬性,進一步研究可以考慮更多屬性的情形,分析不完全信息下確定多個屬性值時供應(yīng)商決策參數(shù)對逆向拍賣機制設(shè)計的影響.

[1]Beall S,Carter C,Carter P L,et al.The Role of Reverse Auctions in Strategic Sourcing.Tempe:CAPS Rearch,2003.

[2]TeichJE,WalleniusH,WalleniusJ,etal.Amulti-attributee-auctionmechanismforprocurement:Theoreticalfoundations.European Journal of Operational Research,2006,175(1):90–100.

[3]Gattiker T F,Huang X,Schwarz J L.Negotiation,Email,and Internet reverse auctions:How sourcing mechanaisms deployed by buyers affect suppliers’trust.Journal of Operations Management,2007,25(1):184–202.

[4]Chandrashekar T S,Narahari Y,Rosa C H,et al.Auction-based mechanisms for electronic procurement.IEEE Transactions on Automation Science and Engineering,2007,4(3):297–321.

[5]Che Y K.Design competition through multidimensional auctions.RAND Journal of Economics,1993,24(4):668–680.

[6]Chen F.Auctioning supply contracts.Management Science,2007,53(10):1562–1576.

[7]Kostamis D,Beil D R,Duenyas I.Total-cost procurement auctions:Impact of suppliers’cost adjustments on auction format choice. Management Science,2009,55(12):1986–1999.

[8]Wan Z,Beil D R.RFQ auctions with supplier qualification screening.Operations Research,2009,57(4):934–949.

[9]Ray A K,Jenamani M,Mohapatra P K J.An efficient reverse auction mechanism for limited supplier base.Electronic Commerce Research and Applications,2011,10(2):170–182.

[10]Ray A K,Jenamani M,Mohapatra P K J.Supplier behavior modeling and winner determination using parallel MDP.Expert Systems with Applications,2011,38(5):4689–4697.

[11]Hohner G,Rich J,Ng E,et al.Combinatorial and quantity-discount procurement auctions benefit mars,incorporated and its suppliers. Interfaces,2003,33(1):23–35.

[12]Beil D R,Wein L M.An inverse-optimization-based auction mechanism to support a multiattribute RFQ process.Management Science,2003,49(11):1529–1545.

[13]Parkes D C,Kalagnanam J.Models for iterative multiattribute procurement auctions.Management Science,2005,51(3):435–451.

[14]Gallien J,Wein L M.A smart market for industrial procurement with capacity constraints.Management Science,2005,51(1):76–91.

[15]ChengCB.Reverseauctionwithbuyer-suppliernegotiationusingbi-leveldistributedprogramming.EuropeanJournalofOperational Research,2011,211(3):601–611.

[16]汪定偉.網(wǎng)上集中采購的捆綁—組合拍賣機制設(shè)計[J].系統(tǒng)工程學(xué)報,2011,26(6):809–816. Wang D W.Mechanism design of hybrid bundling and combination auction for centralized E-procurement.Journal of Systems Engineering,2011,26(6):809–816.(in Chinese)

[17]Kameshwaran S,Narahari Y,Rosa C H,et al.Multiattribute electronic procurement using goal programming.European Journal of Operational Research,2007,179(2):518–536.

[18]Elmaghraby W J,Katok E,Santamaría N.A laboratory investigation of rank feedback in procurement auctions.Manufacturing& Service Operations Management,2012,14(1):128–144.

Mechanism design of bi-attribute electronic reverse auction with discrete cost structure

Huang Min,Qian Xiaohu*,Jin Dongyang,Wang Xingwei
(College of Information Science and Engineering,Northeastern University;State Key Laboratory of Synthetical Automation for Process Industries(Northeastern University),Shenyang 110819,China)

In an electronic reverse auction system that consists of a single buyer and multiple potential suppliers,based on the bi-attribute mechanism design problem of discrete cost structure where cost and delivery time are suppliers’private information,a new iterative reverse auction mechanism based on negotiation theory is proposed for the buyer.A bi-level distributed decision-making model based on negotiation is constructed, and then we propose a concession strategy of delivery time based on deviation of delivery time,a concession strategy of delivery time based on overall target value and a concession strategy of delivery time with randomness based on overall target value.A numerical example is given to show the feasibility and effectiveness of the proposed strategies.Finally,the comparison between the three concession strategies is presented by randomly generated numerical examples,and the result shows that the concession strategy of delivery time with randomness based on overall target value is the best in comparison with the other two.

electronic reverse auction;mechanism design;bi-level distributed decision making model;negotiation;concession strategy of delivery time

F713.36;F224

A

1000-5781(2016)01-0088-13

10.13383/j.cnki.jse.2016.01.009

2013-07-10;

2014-06-26.

國家杰出青年科學(xué)基金資助項目(71325002;61225012);國家自然科學(xué)基金資助項目(71071028;70931001; 71021061);高等學(xué)校博士學(xué)科點專項科研基金優(yōu)先發(fā)展領(lǐng)域資助項目(20120042130003);高等學(xué)校博士學(xué)科點專項科研基金資助項目(20110042110024);中央高校基本科研業(yè)務(wù)費資助項目(N110204003;N120104001);流程工業(yè)綜合自動化國家重點實驗室基礎(chǔ)科研業(yè)務(wù)費資助項目(2013ZCX11);東北大學(xué)基本科研業(yè)務(wù)費資助項目(N130604004).

黃 敏(1968—),女,福建長樂人,博士,教授,博士生導(dǎo)師,研究方向:物流與供應(yīng)鏈管理等,Email:mhuang@mail.neu.edu.cn;

錢小虎(1986—),男,江蘇泰興人,博士生,研究方向:機制設(shè)計與逆向拍賣等,Email:qian_xiaohu@126.com;

金東洋(1987—),男,河北阜城人,碩士生,研究方向:多屬性電子逆向拍賣等,Email:328443742@qq.com;

王興偉(1968—),男,遼寧蓋州人,博士,教授,博士生導(dǎo)師,研究方向:新一代互聯(lián)網(wǎng)等,Email:wangxw@mail.neu.edu.cn.