一種運(yùn)輸作業(yè)指派的迭代下降組合拍賣機(jī)制設(shè)計(jì)

李莉英

（重慶交通大學(xué)理學(xué)院，重慶 400074）

一種運(yùn)輸作業(yè)指派的迭代下降組合拍賣機(jī)制設(shè)計(jì)

李莉英

（重慶交通大學(xué)理學(xué)院，重慶 400074）

針對(duì)4PL公司的卡車運(yùn)輸作業(yè)指派問題提出了一種基于內(nèi)生投標(biāo)的迭代下降組合拍賣機(jī)制設(shè)計(jì)。根據(jù)獲勝者確定問題，構(gòu)造出一個(gè)限制對(duì)偶規(guī)劃，其最優(yōu)解提供近似單條線路運(yùn)輸作業(yè)的價(jià)格信息。投標(biāo)者（3PL企業(yè)）根據(jù)這些價(jià)格信息，在近視最佳反應(yīng)投標(biāo)策略下能夠確定新的有利可圖的線路組合，并以此進(jìn)行下一輪的投標(biāo)。數(shù)值試驗(yàn)顯示，基于內(nèi)生投標(biāo)的迭代拍賣機(jī)制與基于外生投標(biāo)的迭代拍賣機(jī)制相比具有更高的指派效率。

運(yùn)輸作業(yè)指派;迭代組合拍賣;近視最佳反應(yīng)投標(biāo)策略;內(nèi)生投標(biāo)

0 引言

隨著市場(chǎng)競(jìng)爭(zhēng)的日益加劇和企業(yè)對(duì)物流服務(wù)深層次性和全面性要求的提高，傳統(tǒng)的第3方物流（3PL）企業(yè)由于缺乏運(yùn)作整個(gè)供應(yīng)鏈的能力而逐漸不能滿足企業(yè)的物流需求，因而第4方物流（4PL）作為供應(yīng)鏈集成商應(yīng)運(yùn)而生。4PL公司通過其物流信息平臺(tái)，一方面可以接受多個(gè)運(yùn)輸作業(yè)，另一方面能夠找到多個(gè)3PL企業(yè)。于是，探討4PL公司如何將接受來的運(yùn)輸作業(yè)有效地指派給合適的3PL企業(yè)，使得整個(gè)服務(wù)成本最小化，這在管理實(shí)踐中有著重要意義。

在國(guó)外，許多大公司購(gòu)買運(yùn)輸服務(wù)〔特別是卡車運(yùn)輸服務(wù)（TL）〕基本上都是通過參加投標(biāo)過程來進(jìn)行的，產(chǎn)生的合同價(jià)格在1～2a內(nèi)有效?？ㄜ囘\(yùn)輸服務(wù)的特點(diǎn)是3PL企業(yè)在一些不規(guī)則的路線上運(yùn)作，即從某個(gè)發(fā)點(diǎn)到某個(gè)收點(diǎn)做整車直達(dá)運(yùn)送，中間無任何停留。運(yùn)輸服務(wù)的采購(gòu)?fù)稑?biāo)過程與一般商品的采購(gòu)?fù)稑?biāo)過程有許多相同的特征。然而，在某些方面有些不同。其中，最不同的就是運(yùn)輸成本受范圍經(jīng)濟(jì)影響的程度大于受規(guī)模經(jīng)濟(jì)影響的程度。3PL企業(yè)的收益不僅僅依賴于單個(gè)運(yùn)輸作業(yè)的價(jià)格，更重要的是中標(biāo)的各個(gè)作業(yè)能否與3PL企業(yè)整個(gè)運(yùn)輸網(wǎng)絡(luò)中正在運(yùn)作的其它運(yùn)輸作業(yè)聯(lián)系起來，從而最大化裝備（卡車）和司機(jī)的利用率，使得整個(gè)運(yùn)輸成本盡可能地減少。正因?yàn)檫@個(gè)原因，運(yùn)輸服務(wù)拍賣主要采用組合拍賣的方式［1-5］。也就是，3PL企業(yè)可以將一些相關(guān)性較強(qiáng)的線路運(yùn)輸作業(yè)進(jìn)行組合投標(biāo)，以便充分平衡其運(yùn)輸網(wǎng)絡(luò)需求，發(fā)揮網(wǎng)絡(luò)的協(xié)同效應(yīng)，達(dá)到降低總服務(wù)成本的目的。而且，采購(gòu)商（4PL公司）也會(huì)提高討價(jià)還價(jià)能力，從而降低總的采購(gòu)成本。因此，通過組合拍賣來采購(gòu)運(yùn)輸服務(wù)，可以同時(shí)降低采購(gòu)商和3PL企業(yè)雙方的服務(wù)交易成本，達(dá)到物流系統(tǒng)整體優(yōu)化的目的。

自從Caplice首次將組合拍賣引入運(yùn)輸服務(wù)采購(gòu)領(lǐng)域，提出各種承運(yùn)人指派模型以來，運(yùn)輸服務(wù)組合拍賣問題越來越受到人們的關(guān)注［1］。Ledyard，等［2］驗(yàn)證了組合拍賣給托運(yùn)人帶來的收益，西爾斯物流公司在1993年所做的卡車運(yùn)輸服務(wù)采購(gòu)，由于組合拍賣的使用，為西爾斯物流公司每年帶來近1.65億美元的成本節(jié)省。Song，等［3］根據(jù)一組模擬數(shù)據(jù)主要從承運(yùn)人角度檢查了組合拍賣帶來的成本節(jié)省。Y.Sheffi［4］對(duì)組合拍賣在運(yùn)輸服務(wù)采購(gòu)中的適用情況作了調(diào)研，特別是如何將服務(wù)水平和其他非價(jià)格因素融合到組合拍賣的框架中去進(jìn)行了說明，為使用采購(gòu)運(yùn)輸服務(wù)的公司提供了較全面的決策支持。A.Lim，等［5］研究了一個(gè)運(yùn)輸需求量隨季節(jié)變化的運(yùn)輸采購(gòu)模型，其中托運(yùn)人為承運(yùn)人在非高峰時(shí)期的運(yùn)送提供運(yùn)量保證，該文作者采用分解啟發(fā)式方法對(duì)拍賣模型進(jìn)行了求解。楊華龍，等［6］以運(yùn)價(jià)、服務(wù)質(zhì)量、信譽(yù)和網(wǎng)絡(luò)覆蓋等因素為衡量標(biāo)準(zhǔn)，構(gòu)建了一個(gè)集裝箱航運(yùn)服務(wù)的多屬性組合拍賣模型。

以上學(xué)者雖然成功地將組合拍賣引入到運(yùn)輸服務(wù)采購(gòu)領(lǐng)域，但是在拍賣機(jī)制設(shè)計(jì)方面，不管使用的是單輪拍賣還是多輪拍賣，他們都假定投標(biāo)者在拍賣之前明確知道自己想要投標(biāo)的組合。然而，所有可能的允許組合數(shù)目呈指數(shù)次冪，一個(gè)投標(biāo)者要對(duì)所有允許組合定價(jià)并從中選擇有限多個(gè)進(jìn)行投標(biāo)，這往往是很困難的。此外，拍賣者在組合拍賣中需要求解的獲勝者確定問題（WDP）是 NP完全問題［7］。Parkes，等［8］指出，當(dāng)投標(biāo)者難以確定所要投標(biāo)的組合的價(jià)值時(shí)，迭代組合拍賣方式能夠減輕這種負(fù)擔(dān)。在迭代組合拍賣機(jī)制中，投標(biāo)者能夠根據(jù)價(jià)格信息做出反應(yīng)，從而調(diào)整投標(biāo)策略。Kwon，等［9］提出，內(nèi)生投標(biāo)機(jī)制能使投標(biāo)者在拍賣過程中根據(jù)單物品的價(jià)格信息不斷找出新的有價(jià)值的組合，而且拍賣者在每一輪求解的WDP的規(guī)模小于一般組合拍賣中WDP的規(guī)模。這樣，既避免了投標(biāo)者事先列舉所有允許組合的麻煩，同時(shí)也能提高物品的分配效率。這種基于單物品價(jià)格信息的拍賣機(jī)制類似于資源分配設(shè)計(jì)（RAD）機(jī)制中基于市場(chǎng)的優(yōu)化方法［10］。

筆者針對(duì)4PL公司的卡車運(yùn)輸作業(yè)指派問題的特點(diǎn)，提出基于內(nèi)生投標(biāo)的迭代下降組合拍賣機(jī)制設(shè)計(jì)，與原有關(guān)于卡車運(yùn)輸服務(wù)組合拍賣的文獻(xiàn)相比，具有以下特點(diǎn):①在多輪迭代拍賣的背景下，構(gòu)造出單條線路的近似價(jià)格，并利用這些價(jià)格對(duì)線路組合進(jìn)行定價(jià);②在內(nèi)生投標(biāo)拍賣機(jī)制中，給出了投標(biāo)者的具體要求報(bào)價(jià)形式。由于內(nèi)生投標(biāo)機(jī)制既能保持組合價(jià)格下降的性質(zhì)，又能保持投標(biāo)者的近視最佳反應(yīng)的性質(zhì)，而有效迭代拍賣機(jī)制的所有其它規(guī)則保持不變，因此本拍賣機(jī)制在拍賣結(jié)束時(shí)能實(shí)現(xiàn)系統(tǒng)的最優(yōu)指派。

首先介紹針對(duì)運(yùn)輸作業(yè)指派的一般（基于外生投標(biāo)）迭代組合下降采購(gòu)拍賣機(jī)制的實(shí)施規(guī)則，稍后提出的基于內(nèi)生投標(biāo)的迭代下降組合拍賣機(jī)制將以它作為基礎(chǔ)。

1 迭代下降組合采購(gòu)拍賣規(guī)則

組合采購(gòu)拍賣的迭代機(jī)制包括投標(biāo)形式和投標(biāo)要求報(bào)價(jià)、獲勝者確定規(guī)則、近視最佳反應(yīng)投標(biāo)策略和拍賣結(jié)束規(guī)則等方面的內(nèi)容。它們的共同作用使得拍賣者的所有運(yùn)輸作業(yè)實(shí)現(xiàn)最優(yōu)的指派。下面具體介紹相關(guān)規(guī)則。

1.1 投標(biāo)形式和投標(biāo)要求報(bào)價(jià)

基于運(yùn)輸作業(yè)采購(gòu)拍賣的實(shí)際情況，允許投標(biāo)者對(duì)多個(gè)不相交的運(yùn)輸作業(yè)組合進(jìn)行累或（OR）投標(biāo)，即如果一個(gè)OR投標(biāo)形式為{S1，S2}，則投標(biāo)者希望能中標(biāo)組合S1中的全部運(yùn)輸作業(yè)，或者中標(biāo)組合S2中的全部運(yùn)輸作業(yè)，或者同時(shí)中標(biāo)組合S1和S2中的全部運(yùn)輸作業(yè)。它和異或（XOR）投標(biāo)［8］是不一樣的，一個(gè)XOR投標(biāo)不允許投標(biāo)者同時(shí)中標(biāo)兩個(gè)以上的組合。本拍賣中，在第t輪對(duì)組合S的要求報(bào)價(jià)表示為（S），投標(biāo)者j對(duì)組合S的實(shí)際報(bào)價(jià)表示為（S）。投標(biāo)者j在第t輪對(duì)組合S的實(shí)際報(bào)價(jià)（S）必須等于或低于要求報(bào)價(jià)（S），并且至少低出ε，ε為本拍賣的最小投標(biāo)減少量。如果某個(gè)投標(biāo)者在第t-1輪是組合S的暫時(shí)獲勝者，則對(duì)其在第t輪的要求報(bào)價(jià)等于其在上一輪的獲勝投標(biāo)價(jià)，即。如果某個(gè)投標(biāo)者在第

t-1輪不是組合S的暫時(shí)獲勝者，則對(duì)其在第t輪的要求報(bào)價(jià)等于第t-1輪不中標(biāo)者的最低投標(biāo)價(jià)減去ε，即:

式中:unhappy代表在第t-1輪中未中標(biāo)的投標(biāo)者。

在拍賣的第1輪，無要求報(bào)價(jià)，各投標(biāo)者可以對(duì)預(yù)先決定的組合進(jìn)行初始報(bào)價(jià)。

1.2 獲勝者確定規(guī)則

在拍賣的每一輪結(jié)束之后，拍賣者需要計(jì)算一次獲勝者確定問題（WDP），以便明確當(dāng)前的暫時(shí)獲勝者，其優(yōu)化目標(biāo)是使總的采購(gòu)成本最小化。WDP的約束條件是:每一條線路的運(yùn)輸作業(yè)不重復(fù)拍賣，即最終只中標(biāo)且只能中標(biāo)1次。筆者假定投標(biāo)者的人數(shù)足夠多，使得WDP基本上總有最優(yōu)解，這一點(diǎn)通過4PL公司的網(wǎng)絡(luò)信息平臺(tái)是可以做到的。當(dāng)WDP的最優(yōu)解有多個(gè)時(shí)，選取獲勝者人數(shù)最多的最優(yōu)解;如果多個(gè)最優(yōu)解的獲勝者人數(shù)相同，則隨機(jī)選取1個(gè)最優(yōu)解。當(dāng)拍賣結(jié)束時(shí)，該輪的暫時(shí)獲勝者就是最終獲勝者。

1.3 近視最佳反應(yīng)投標(biāo)策略

本拍賣假定投標(biāo)者都是采用近視最佳反應(yīng)投標(biāo)策略，即其投標(biāo)行為都是基于當(dāng)前輪次效用最大化來考慮的。具體來說就是，在拍賣的任意一輪中，給定組合的要求報(bào)價(jià)，投標(biāo)者j會(huì)選取優(yōu)化問題BIP的最優(yōu)解所確定的運(yùn)輸作業(yè)組合進(jìn)行投標(biāo)，BIP的目標(biāo)函數(shù)是最大化投標(biāo)者j的擬線性效用。

1.4 拍賣結(jié)束規(guī)則

拍賣在下述兩種情況之一發(fā)生時(shí)即可結(jié)束［8］:

1）當(dāng)所有投標(biāo)者在連續(xù)兩輪的投標(biāo)中都遞交了相同的投標(biāo)。該條件表示所有投標(biāo)者已經(jīng)到了投標(biāo)個(gè)體理性的邊界，拍賣者的采購(gòu)成本不能再進(jìn)一步減少。

2）當(dāng)所有投標(biāo)者都是獲勝者，即每一個(gè)投標(biāo)者都得到她所投標(biāo)的所有組合。該條件表示此時(shí)的指派結(jié)果已經(jīng)不能再改進(jìn)系統(tǒng)的優(yōu)化目標(biāo)。

上述拍賣機(jī)制的有效性由下列性質(zhì)給出。

性質(zhì) 假定各投標(biāo)者采用近視最佳反應(yīng)投標(biāo)策略，則本拍賣模型在拍賣結(jié)束時(shí)能夠?qū)崿F(xiàn)系統(tǒng)的最優(yōu)指派（當(dāng)投標(biāo)減量足夠小時(shí)）。

性質(zhì)的證明類似于文獻(xiàn)［8］中應(yīng)用原-對(duì)偶算法來解釋迭代組合上升拍賣機(jī)制的有效性，故此略去。該性質(zhì)說明，在拍賣結(jié)束時(shí)組合價(jià)格逼近競(jìng)爭(zhēng)均衡價(jià)格，此時(shí)各投標(biāo)者的效用達(dá)到漸近最大化，同時(shí)拍賣者的采購(gòu)成本達(dá)到漸近最小化。

2 模型描述

假設(shè)一個(gè)4PL公司（拍賣者）要把n條不同線路的卡車運(yùn)輸作業(yè)指派給m個(gè)潛在的3PL企業(yè)（投標(biāo)者）。n條不同線路的運(yùn)輸作業(yè)構(gòu)成的集合記為I，即|I|=n。m個(gè)潛在的3PL企業(yè)構(gòu)成的集合記為J，即|J|=m。拍賣者允許投標(biāo)者根據(jù)自己的運(yùn)輸網(wǎng)絡(luò)需求將部分線路的運(yùn)輸作業(yè)進(jìn)行組合投標(biāo)，這樣的允許投標(biāo)組合（捆綁）記為S，S?I。

假定3PL企業(yè)j（j∈J）對(duì)組合S具有私人的擬線性效用uj（S）=Pj（S）-cj（S），其中cj（S）表示3PL企業(yè)j服務(wù)組合S的私有成本，而Pj（S）表示3PL企業(yè)j對(duì)組合S的報(bào)價(jià)。投標(biāo)者j為了確定向哪些線路組合進(jìn)行投標(biāo)，需求解下列整數(shù)規(guī)劃問題（BIP）:

式中:xj（S）為0-1變量，表示投標(biāo)者j對(duì)組合S是否進(jìn)行投標(biāo);δij（S）表示投標(biāo)者j所構(gòu)建的線路組合S是否包含線路i，若包含，則 δij（S）=1，否則，δij（S）=0;vj（S）表示服務(wù)組合S時(shí)投標(biāo)者j需要的運(yùn)輸能力;Vj表示投標(biāo)者j當(dāng)前擁有的最大運(yùn)力。

式（2）為目標(biāo)函數(shù)，表示最大化投標(biāo)者j的效用值;約束（3）表示投標(biāo)者j要投標(biāo)的各組合之間不相交，即不包含相同線路的運(yùn)輸作業(yè);約束（4）表示投標(biāo)者j要投標(biāo)的所有線路組合中需要的運(yùn)力不超過其最大運(yùn)力。

當(dāng)每一個(gè)投標(biāo)者都遞交了使其效用最大化的線路組合以后，拍賣者（4PL公司）需要考慮將運(yùn)輸作業(yè)如何有效地指派給投標(biāo)者，使得其總的采購(gòu)成本最小化。于是，拍賣者需要求解下列獲勝者確定問題（WDP）:

式中:yj（S）為0-1變量，表示投標(biāo)者j向拍賣者提交的組合S是否中標(biāo);Gj表示投標(biāo)者j根據(jù)效用最大化提交的線路組合所構(gòu)成的集合;pj（S）表示投標(biāo)者j對(duì)組合S的報(bào)價(jià);βij（S）表示投標(biāo)者j所提交的線路組合S是否包含線路i，若包含，則βij（S）=1，否則，βij（S）=0。

式（6）為WDP的目標(biāo)函數(shù)，表示最小化拍賣者的總采購(gòu)成本;約束（7）表示對(duì)于集合I中每一條線路的運(yùn)輸作業(yè)不重復(fù)拍賣，即最終只中標(biāo)且只能中標(biāo)一次。

根據(jù)基于外生投標(biāo)的迭代組合采購(gòu)拍賣機(jī)制，拍賣者通過求解WDP就可以實(shí)現(xiàn)所有運(yùn)輸作業(yè)在3PL企業(yè)之間的暫時(shí)指派（如果WDP有最優(yōu)解的話）。然后，拍賣者宣布獲得暫時(shí)指派的投標(biāo)者及其投標(biāo)價(jià)格。投標(biāo)者根據(jù)這些價(jià)格信息做出反應(yīng)，即調(diào)整下一輪的投標(biāo)策略。如此反復(fù)進(jìn)行下去，直到滿足拍賣結(jié)束的條件，則能實(shí)現(xiàn)4PL公司的作業(yè)在3PL企業(yè)之間的最終指派。

基于外生投標(biāo)的迭代組合采購(gòu)拍賣機(jī)制實(shí)際上假定投標(biāo)者在拍賣之前明確知道自己想要投標(biāo)的組合，即他能詳細(xì)列舉并定價(jià)所有可能的允許組合。正如引言中所說，這往往是很困難的，尤其是當(dāng)拍賣的運(yùn)輸作業(yè)數(shù)n很大時(shí)。

3 內(nèi)生投標(biāo)機(jī)制與單條線路運(yùn)輸作業(yè)定價(jià)

內(nèi)生投標(biāo)的基本思想是在多輪拍賣過程中投標(biāo)者可以不斷提交新的有利可圖的線路組合。利用單條線路的運(yùn)輸作業(yè)服務(wù)價(jià)格，投標(biāo)者能夠?qū)ε馁u開始之前未曾考慮的線路組合進(jìn)行定價(jià)和投標(biāo)。

3.1 近似單條線路運(yùn)輸作業(yè)定價(jià)

筆者對(duì)單條線路運(yùn)輸作業(yè)的服務(wù)價(jià)格做如下兩個(gè)假設(shè):

1）在拍賣的任意一輪中，對(duì)于已經(jīng)獲得暫時(shí)指派的組合來說，它所包含的各單條線路運(yùn)輸作業(yè)的服務(wù)價(jià)格加起來應(yīng)等于暫時(shí)獲勝者的投標(biāo)價(jià)格。

2）在拍賣的任意一輪中，對(duì)于暫時(shí)未獲得指派的組合來說，它所包含的各單條線路運(yùn)輸作業(yè)的服務(wù)價(jià)格加起來應(yīng)小于或等于不中標(biāo)的最小投標(biāo)價(jià)格。

為了使得迭代拍賣的下降性質(zhì)得以保持，上述兩個(gè)假設(shè)是必要的。如果假設(shè)1）不成立，例如，對(duì)于已經(jīng)獲得暫時(shí)指派的組合來說，如果各單條線路運(yùn)輸作業(yè)的服務(wù)價(jià)格之和大于暫時(shí)獲勝者的投標(biāo)價(jià)格，則那些未中標(biāo)的投標(biāo)者在下一輪將以單條線路運(yùn)輸作業(yè)的服務(wù)價(jià)格之和投相同的標(biāo)。然而，這樣的投標(biāo)將是無效的。因?yàn)榘凑盏陆档呐馁u性質(zhì)，作為暫時(shí)未獲得指派的投標(biāo)者來說，下一輪的投標(biāo)價(jià)格至多為本輪不中標(biāo)的最低投標(biāo)價(jià)減去ε。如果各單條線路運(yùn)輸作業(yè)的服務(wù)價(jià)格之和小于暫時(shí)獲勝者的投標(biāo)價(jià)格，這將會(huì)使得一些成本更低的投標(biāo)者失去獲得分配該組合的機(jī)會(huì)。如果假設(shè)2）不成立，則在下一輪投標(biāo)中，那些未中標(biāo)的投標(biāo)者將以單條線路運(yùn)輸作業(yè)的服務(wù)價(jià)格之和投標(biāo)相同的組合，由于導(dǎo)致更高的效用，該組合仍屬于其最佳反應(yīng)集中的元素，按照迭代下降的拍賣性質(zhì)這樣的投標(biāo)仍然是無效的。

下面構(gòu)造滿足上面兩個(gè)假設(shè)條件的單條線路運(yùn)輸作業(yè)的服務(wù)價(jià)格。

WDP的線性松弛問題（LP）為:

LP的對(duì)偶問題（DP）如下:

當(dāng)上述LP的最優(yōu)解為整數(shù)時(shí)，則其最優(yōu)解即為WDP的最優(yōu)解，從而最優(yōu)的對(duì)偶變量即為相應(yīng)的單條線路運(yùn)輸作業(yè)的服務(wù)價(jià)格。于是，可以把這些價(jià)格解釋為單條線路運(yùn)輸作業(yè)的邊際成本。那么，投標(biāo)者提交的任何線路組合就可以定價(jià)了，即把該組合中所有單條線路運(yùn)輸作業(yè)的服務(wù)價(jià)格加起來即等于該組合的價(jià)值。然而，LP的解經(jīng)常是分?jǐn)?shù)，互補(bǔ)松弛條件不能得以滿足。因此，單條線路運(yùn)輸作業(yè)的服務(wù)價(jià)格可能不存在。此時(shí)，DP的最優(yōu)目標(biāo)值只是代表了WDP最優(yōu)目標(biāo)值的一個(gè)嚴(yán)格下界。類似于資源分配設(shè)計(jì)（RAD）機(jī)制中價(jià)格的構(gòu)造方法，筆者對(duì)已經(jīng)獲得暫時(shí)指派的組合和未獲得暫時(shí)指派的組合分別設(shè)置約束條件，得到如下限制對(duì)偶問題（RDP）:

因?yàn)閞j（S）可以取任意大的值，所以RDP總有可行解。rj（S）可以解釋為價(jià)格歧視項(xiàng)，它可以避免暫時(shí)未獲得指派的組合S的投標(biāo)價(jià)小于該組合中各單條線路運(yùn)輸作業(yè)的價(jià)格之和。在多輪下降組合拍賣的背景下使用價(jià)格歧視，正的rj（S）將避免虛假套利。因?yàn)楫?dāng)投標(biāo)者j的組合S未獲得暫時(shí)指派時(shí)〔即yj（S）=0〕，如果單條線路運(yùn)輸作業(yè)的價(jià)格之和大于投標(biāo)者j的投標(biāo)價(jià)，則投標(biāo)者j在下一輪能夠?qū)M合S中的每一條單條線路運(yùn)輸作業(yè)分別投標(biāo)，并得到該組合的一個(gè)更高的投標(biāo)價(jià)。這必將引起誤導(dǎo)，因?yàn)樵谙乱惠?，?duì)該組合的要求報(bào)價(jià)至多為pj（S）-ε，從而導(dǎo)致不必要的投標(biāo)。

通過求解RDP，得到服務(wù)單個(gè)運(yùn)輸作業(yè)的近似價(jià)格（πi）和未獲得暫時(shí)指派組合的歧視項(xiàng)〔rj（S）〕。當(dāng)歧視項(xiàng)非零時(shí)，未獲得暫時(shí)指派的組合中所包含的單條線路運(yùn)輸作業(yè)的服務(wù)價(jià)格之和并不能真正代表其邊際成本，其值減去歧視項(xiàng)可能更能代表該組合的服務(wù)成本。

在拍賣的每一輪開始之前，拍賣者將宣布一組單條線路運(yùn)輸作業(yè)的服務(wù)價(jià)格πi（i∈I）和一組對(duì)應(yīng)具體組合的歧視項(xiàng)。每一個(gè)投標(biāo)者會(huì)求解其本身的決策子問題，在本輪要求報(bào)價(jià)的約束下，對(duì)使其效用最大化的所有組合進(jìn)行投標(biāo)。在拍賣第一輪開始時(shí)，投標(biāo)者可以根據(jù)拍賣者宣布的單個(gè)作業(yè)的最大服務(wù)價(jià)格對(duì)組合進(jìn)行定價(jià)和投標(biāo)。

3.2 內(nèi)生投標(biāo)機(jī)制

假設(shè)在拍賣的任意一輪中，關(guān)于當(dāng)前指派的RDP所構(gòu)造的單線路運(yùn)輸作業(yè)服務(wù)價(jià)格πi（i∈I）存在。于是，在拍賣的第t輪，給定一組運(yùn)輸作業(yè)的服務(wù)價(jià)格πi（i∈I）和一組對(duì)應(yīng)具體組合的歧視項(xiàng)rj（S），投標(biāo)者j的最佳反應(yīng)集為:

如果SDP有多組最優(yōu)解，則投標(biāo)者j可以任選其中一組最優(yōu)解對(duì)應(yīng)的線路組合進(jìn)行投標(biāo)。下面給出內(nèi)生投標(biāo)組合的定義:

設(shè)Hj={投標(biāo)者j在拍賣開始之前所提交的組合S?I}。若在第t（t＞1）輪，投標(biāo)者j提交的組合

由上述定義可見，內(nèi)生投標(biāo)保持了投標(biāo)者的近視最佳反應(yīng)的性質(zhì)。內(nèi)生投標(biāo)組合的產(chǎn)生使得投標(biāo)者在拍賣過程中可以不斷更新要提交的最優(yōu)組合，從而避免了在拍賣開始之前列舉和定價(jià)所有相關(guān)組合的麻煩。

3.3 內(nèi)生投標(biāo)的要求報(bào)價(jià)

由于在內(nèi)生投標(biāo)機(jī)制下也有外生投標(biāo)組合（即在拍賣開始之前就確定好了的組合），因而此時(shí)的要求報(bào)價(jià)分以下幾種情況:

1）對(duì)于在第t-1輪中未獲得暫時(shí)指派的內(nèi)生投標(biāo)組合S來說，在第t輪對(duì)它的投標(biāo)要求報(bào)價(jià)至多為:

式中:unhappy代表在第t-1輪中未中標(biāo)的投標(biāo)者。

2）如果某個(gè)在第t-1輪無人投標(biāo)的組合S在第t輪是某個(gè)投標(biāo)者的內(nèi)生投標(biāo)組合，則對(duì)它的要求報(bào)價(jià)至多為:

3）如果某個(gè)在第t-1輪獲得暫時(shí)指派的組合在第t輪是某個(gè)投標(biāo)者的內(nèi)生投標(biāo)，則該組合對(duì)于該投標(biāo)者在第t輪的投標(biāo)要求報(bào)價(jià)至多為第t-1輪的獲勝投標(biāo)價(jià)，即:

4）對(duì)于在第t-1輪中未獲得暫時(shí)指派的外生投標(biāo)組合S來說，在第t輪對(duì)它的投標(biāo)要求報(bào)價(jià)至多為:

這樣，內(nèi)生投標(biāo)保持了迭代拍賣中組合價(jià)格下降的性質(zhì)。

3.4 內(nèi)生投標(biāo)機(jī)制下的拍賣步驟

在內(nèi)生投標(biāo)機(jī)制下，按以下步驟進(jìn)行拍賣:

1）在拍賣第1輪開始時(shí)，投標(biāo)者根據(jù)拍賣者宣布的單獨(dú)服務(wù)每個(gè)作業(yè)的最大價(jià)格而對(duì)組合進(jìn)行定價(jià)和投標(biāo)。

2）拍賣者計(jì)算WDP，明確當(dāng)前的暫時(shí)獲勝者。若滿足拍賣結(jié)束規(guī)則（見1.4），則拍賣結(jié)束，該輪的暫時(shí)獲勝者就是最終獲勝者。

3）拍賣者求解RDP，得到服務(wù)單個(gè)運(yùn)輸作業(yè)的近似價(jià)格（πi）和未獲得暫時(shí)指派組合的歧視項(xiàng)〔rj（S）〕。

4）拍賣者宣布一組單條線路運(yùn)輸作業(yè)的服務(wù)價(jià)格πi和一組對(duì)應(yīng)具體組合的歧視項(xiàng)。每一個(gè)投標(biāo)者求解其本身的SDP，在本輪要求報(bào)價(jià)的約束條件下，對(duì)使其效用最大化的所有組合進(jìn)行投標(biāo)。然后，轉(zhuǎn)第2）步。

由于筆者所提出的內(nèi)生投標(biāo)機(jī)制既保持了迭代組合價(jià)格下降的性質(zhì)，又保持了投標(biāo)者的近視最佳反應(yīng)的性質(zhì)，而迭代拍賣機(jī)制的所有其它規(guī)則保持不變，因此根據(jù)關(guān)于拍賣機(jī)制有效性的性質(zhì)可知，本拍賣機(jī)制在拍賣結(jié)束時(shí)將實(shí)現(xiàn)系統(tǒng)的最優(yōu)指派。

4 算例分析

針對(duì)一個(gè)關(guān)于運(yùn)輸作業(yè)指派的采購(gòu)拍賣的例子，用以直觀地解釋基于外生投標(biāo)和基于內(nèi)生投標(biāo)的迭代下降組合拍賣在運(yùn)作上的差異。

假設(shè)一個(gè)4PL公司要把a(bǔ)，b，c，d等4條不同線路的運(yùn)輸作業(yè)通過采購(gòu)拍賣的方式指派給8個(gè)潛在的3PL企業(yè)（代理）。假定，每個(gè)代理指派到的線路總數(shù)最多不超過3條，且最終獲得指派的代理數(shù)最多不超過3個(gè)，各代理可以對(duì)運(yùn)輸作業(yè)進(jìn)行組合投標(biāo)，但各組合之間不相交，即不包含相同線路的運(yùn)輸作業(yè)。假設(shè)每1個(gè)代理的最大運(yùn)力都是30。表1給出了各代理對(duì)其投標(biāo)組合的成本信息。

表1 私人成本信息Table 1 Private costs information

表2和表3分別給出了外生投標(biāo)機(jī)制下和內(nèi)生投標(biāo)機(jī)制下迭代下降組合拍賣的結(jié)果。其中，外生投標(biāo)中各輪的組合價(jià)格在表4中給出。兩種情況下，投標(biāo)減量都取ε=1，上標(biāo)“*”表示各輪的暫時(shí)指派結(jié)果，上標(biāo)“D”表示投標(biāo)價(jià)格含有一個(gè)ε折扣（本拍賣允許投標(biāo)者在最大化其效用的ε鄰域內(nèi)對(duì)組合進(jìn)行投標(biāo)）。每一輪“暫時(shí)獲勝者”的選擇都是通過求解WDP問題而決定的，即考慮4PL公司的采購(gòu)成本最小化，并考慮先前提到的假設(shè)條件約束。

表2 外生投標(biāo)結(jié)果Table 2 Exogenous bidding results

表3 內(nèi)生投標(biāo)結(jié)果Table 3 Endogenous bidding results

表4 外生投標(biāo)中各輪的組合價(jià)格Table 4 Package prices for several rounds in exogenous bidding

在外生投標(biāo)中，由于連續(xù)兩輪出現(xiàn)了相同的投標(biāo)，故拍賣結(jié)束。最后，由代理2以成本6服務(wù)線路a，代理5以成本17服務(wù)線路b和d，代理6以成本6服務(wù)線路c，4PL公司總的采購(gòu)成本為29。該指派結(jié)果沒有實(shí)現(xiàn)系統(tǒng)的最優(yōu)指派。如前所述，這主要是由于外生投標(biāo)限制了可選組合的空間所致。

在內(nèi)生投標(biāo)中，由于存在單條線路運(yùn)輸作業(yè)的服務(wù)價(jià)格，一些成本更低的組合被找出，使得那些在外生投標(biāo)中未獲得指派的投標(biāo)者轉(zhuǎn)而去競(jìng)爭(zhēng)內(nèi)生投標(biāo)。價(jià)格歧視僅僅對(duì)于那些未獲得暫時(shí)指派的組合來說才會(huì)發(fā)生，它導(dǎo)致受歧視組合的一個(gè)非線性價(jià)格。價(jià)格歧視的出現(xiàn)是由于該組合與當(dāng)前獲得暫時(shí)指派的組合之間在價(jià)格上的沖突造成的，因?yàn)橐贒P問題中構(gòu)建線性價(jià)格來滿足這些組合的相應(yīng)約束條件變得不可能。在本例中，價(jià)格歧視的出現(xiàn)主要是由于受到每個(gè)代理指派到的線路數(shù)最多不超過3條這個(gè)約束條件限制而引起的。比如，在第2輪中，本來使得4PL公司的采購(gòu)成本最小化的暫時(shí)獲勝組合是代理4投標(biāo)的組合ab和組合cd，但由于受到中標(biāo)線路數(shù)的限制，只能選擇次優(yōu)指派結(jié)果，即代理1投標(biāo)的線路c，代理2投標(biāo)的線路d和代理4投標(biāo)的組合ab，于是組合cd受到歧視，同時(shí)組合bc也受到歧視。類似的情況出現(xiàn)在第5輪和第6輪中。在內(nèi)生投標(biāo)中，由于第7輪的所有投標(biāo)者都是獲勝者，故拍賣結(jié)束。最后，由代理3以成本15服務(wù)線路a和d，代理8以成本12服務(wù)線路b和c，4PL公司總的采購(gòu)成本為27。該指派結(jié)果實(shí)現(xiàn)了滿足相關(guān)約束條件下系統(tǒng)成本最小化的目標(biāo)。由此看出，內(nèi)生投標(biāo)機(jī)制與外生投標(biāo)機(jī)制相比，它能產(chǎn)生一個(gè)更有效的指派結(jié)果。

5 結(jié)語

考慮了4PL企業(yè)向3PL公司進(jìn)行運(yùn)輸作業(yè)指派的迭代下降組合拍賣機(jī)制，其中投標(biāo)者的內(nèi)生投標(biāo)組合決策被允許。內(nèi)生投標(biāo)機(jī)制的基礎(chǔ)是利用近似單條線路運(yùn)輸作業(yè)的服務(wù)價(jià)格來找出拍賣之前未曾考慮的新的有利可圖的組合。這些近似價(jià)格是通過一個(gè)限制對(duì)偶規(guī)劃來構(gòu)造的，它可以保持迭代拍賣的下降性質(zhì)，同時(shí)避免無效的投標(biāo)。數(shù)值試驗(yàn)顯示，基于內(nèi)生投標(biāo)的迭代拍賣機(jī)制與基于外生投標(biāo)的迭代拍賣機(jī)制相比具有更高的指派效率。在各3PL公司的成本函數(shù)為私有信息的情況下，4PL企業(yè)通過本拍賣機(jī)制可以淘汰成本結(jié)構(gòu)差的3PL公司，從而優(yōu)選出最有效率的3PL公司組合。因此，該模型為運(yùn)輸作業(yè)在3PL公司之間實(shí)現(xiàn)有效指派提供了決策支持。

（References）:

［1］ Caplice C G.An Optimization Based Bidding Process:A New Framework for Shipper-Carrier Relationships［M］.Cambridge，MA:MIT Department of Civil and Environmental Engineering，1996.

［2］ Ledyard J O，Olson M，Porter D，et al.The first use of a combined value auction for transportation services［J］.Interfaces，2002，32（5）:4-12.

［3］ Song J，Regan A C.Combinatorial auctions for transportation service procurement:the carrier perspective［J］.Transportation Research Board，2002，1833:40-46.

［4］ Sheffi Y.Combinatorial auctions in the procurement of transportation services［J］.Interfaces，2004，34（4）:245-252.

［5］ Lim A，Rodrigues B，Zhou X.Transportation procurement with seasonally varying shipper demand and volume guarantees［J］.Operations Research，2008，56（3）:758-771.

［6］ 楊華龍，東方，鄭斌，等.集裝箱航運(yùn)服務(wù)多屬性組合拍賣模型與算法［J］.交通運(yùn)輸工程學(xué)報(bào)，2009，9（5）:111-115.

Yang Hualong，Dong Fang，Zhen Bin，et al.Multi-attribute combinatorial auction model and algorithm for container shipping service［J］.Journal of Traffic and Transportation Engineering，2009，9（5）:111-115.

［7］ Rothkopf M，Pekec A，Harstad R.Computationally manageable combinatorial auctions［J］.Management Science，1998，44（8）:1131-1147.

［8］ Parkes D C，Ungar L H.Iterative Combinatoria1 Auctions:Theory and Practice［C］//Proceedings of 17th National Conference on Artificial Intelligence.Menlo Park，CA:AAAI Press，2000:74-81.

［9］ Kwon R H，Anandalingam G，Ungar L H.Iterative combinatorial auctions with bidder-determined combinations［J］.Management Science，2005，51（3）:407-418.

［10］ Guo Z，Koehler G J，Whinston A B.A market-based optimization algorithm for distributed systems［J］.Management Science，2007，53（8）:1345-1358.

Iterative Descending Combinatorial Auction Mechanism for Transportation Business Assignment Scheme

Li Liying
（School of Science，Chongqing Jiaotong University，Chongqing 400074，China）

An iterative descending combinatorial auction mechanism is proposed on the base of endogenous bidding，whose objective is to efficiently solve the truckload transportation business assignment problem of the 4PL company.By taking the dual of Winner Determination Problem（WDP），a restricted dual planning is structured;whose optimal solution provides a set of approximate single-lane prices.Bidders（3PL companies）can use this price information to determine new profitable packages before the next round under a myopic best response bidding strategy.Numerical experiment shows that the efficiency of assignments produced by using single-lane prices with endogenous bidding is greater than that of assignments produced in the exogenous bidding mechanism when bidding is restricted to a fixed set of packages determined before the start of the auction.

transportation business assignment;iterative combinatorial auction;myopic best response bidding strategy;endogenous bidding

F724.59

A

1674-0696（2013）02-0267-07

10.3969/j.issn.1674-0696.2013.02.21

2012-05-18;

2012-10-12

國(guó)家自然科學(xué)基金項(xiàng)目（70872123）

李莉英（1975—），女，四川自貢人，講師，博士，主要從事物流與供應(yīng)鏈管理等方面的研究。E-mail:lly-594@sohu.com。