一種運輸作業指派的迭代下降組合拍賣機制設計

李莉英

（重慶交通大學理學院，重慶 400074）

一種運輸作業指派的迭代下降組合拍賣機制設計

李莉英

（重慶交通大學理學院，重慶 400074）

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

運輸作業指派;迭代組合拍賣;近視最佳反應投標策略;內生投標

0 引言

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

在國外，許多大公司購買運輸服務〔特別是卡車運輸服務（TL）〕基本上都是通過參加投標過程來進行的，產生的合同價格在1～2a內有效。卡車運輸服務的特點是3PL企業在一些不規則的路線上運作，即從某個發點到某個收點做整車直達運送，中間無任何停留。運輸服務的采購投標過程與一般商品的采購投標過程有許多相同的特征。然而，在某些方面有些不同。其中，最不同的就是運輸成本受范圍經濟影響的程度大于受規模經濟影響的程度。3PL企業的收益不僅僅依賴于單個運輸作業的價格，更重要的是中標的各個作業能否與3PL企業整個運輸網絡中正在運作的其它運輸作業聯系起來，從而最大化裝備（卡車）和司機的利用率，使得整個運輸成本盡可能地減少。正因為這個原因，運輸服務拍賣主要采用組合拍賣的方式［1-5］。也就是，3PL企業可以將一些相關性較強的線路運輸作業進行組合投標，以便充分平衡其運輸網絡需求，發揮網絡的協同效應，達到降低總服務成本的目的。而且，采購商（4PL公司）也會提高討價還價能力，從而降低總的采購成本。因此，通過組合拍賣來采購運輸服務，可以同時降低采購商和3PL企業雙方的服務交易成本，達到物流系統整體優化的目的。

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

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

筆者針對4PL公司的卡車運輸作業指派問題的特點，提出基于內生投標的迭代下降組合拍賣機制設計，與原有關于卡車運輸服務組合拍賣的文獻相比，具有以下特點:①在多輪迭代拍賣的背景下，構造出單條線路的近似價格，并利用這些價格對線路組合進行定價;②在內生投標拍賣機制中，給出了投標者的具體要求報價形式。由于內生投標機制既能保持組合價格下降的性質，又能保持投標者的近視最佳反應的性質，而有效迭代拍賣機制的所有其它規則保持不變，因此本拍賣機制在拍賣結束時能實現系統的最優指派。

首先介紹針對運輸作業指派的一般（基于外生投標）迭代組合下降采購拍賣機制的實施規則，稍后提出的基于內生投標的迭代下降組合拍賣機制將以它作為基礎。

1 迭代下降組合采購拍賣規則

組合采購拍賣的迭代機制包括投標形式和投標要求報價、獲勝者確定規則、近視最佳反應投標策略和拍賣結束規則等方面的內容。它們的共同作用使得拍賣者的所有運輸作業實現最優的指派。下面具體介紹相關規則。

1.1 投標形式和投標要求報價

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

t-1輪不是組合S的暫時獲勝者，則對其在第t輪的要求報價等于第t-1輪不中標者的最低投標價減去ε，即:

式中:unhappy代表在第t-1輪中未中標的投標者。

在拍賣的第1輪，無要求報價，各投標者可以對預先決定的組合進行初始報價。

1.2 獲勝者確定規則

在拍賣的每一輪結束之后，拍賣者需要計算一次獲勝者確定問題（WDP），以便明確當前的暫時獲勝者，其優化目標是使總的采購成本最小化。WDP的約束條件是:每一條線路的運輸作業不重復拍賣，即最終只中標且只能中標1次。筆者假定投標者的人數足夠多，使得WDP基本上總有最優解，這一點通過4PL公司的網絡信息平臺是可以做到的。當WDP的最優解有多個時，選取獲勝者人數最多的最優解;如果多個最優解的獲勝者人數相同，則隨機選取1個最優解。當拍賣結束時，該輪的暫時獲勝者就是最終獲勝者。

1.3 近視最佳反應投標策略

本拍賣假定投標者都是采用近視最佳反應投標策略，即其投標行為都是基于當前輪次效用最大化來考慮的。具體來說就是，在拍賣的任意一輪中，給定組合的要求報價，投標者j會選取優化問題BIP的最優解所確定的運輸作業組合進行投標，BIP的目標函數是最大化投標者j的擬線性效用。

1.4 拍賣結束規則

拍賣在下述兩種情況之一發生時即可結束［8］:

1）當所有投標者在連續兩輪的投標中都遞交了相同的投標。該條件表示所有投標者已經到了投標個體理性的邊界，拍賣者的采購成本不能再進一步減少。

2）當所有投標者都是獲勝者，即每一個投標者都得到她所投標的所有組合。該條件表示此時的指派結果已經不能再改進系統的優化目標。

上述拍賣機制的有效性由下列性質給出。

性質 假定各投標者采用近視最佳反應投標策略，則本拍賣模型在拍賣結束時能夠實現系統的最優指派（當投標減量足夠小時）。

性質的證明類似于文獻［8］中應用原-對偶算法來解釋迭代組合上升拍賣機制的有效性，故此略去。該性質說明，在拍賣結束時組合價格逼近競爭均衡價格，此時各投標者的效用達到漸近最大化，同時拍賣者的采購成本達到漸近最小化。

2 模型描述

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

假定3PL企業j（j∈J）對組合S具有私人的擬線性效用uj（S）=Pj（S）-cj（S），其中cj（S）表示3PL企業j服務組合S的私有成本，而Pj（S）表示3PL企業j對組合S的報價。投標者j為了確定向哪些線路組合進行投標，需求解下列整數規劃問題（BIP）:

式中:xj（S）為0-1變量，表示投標者j對組合S是否進行投標;δij（S）表示投標者j所構建的線路組合S是否包含線路i，若包含，則 δij（S）=1，否則，δij（S）=0;vj（S）表示服務組合S時投標者j需要的運輸能力;Vj表示投標者j當前擁有的最大運力。

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

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

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

式（6）為WDP的目標函數，表示最小化拍賣者的總采購成本;約束（7）表示對于集合I中每一條線路的運輸作業不重復拍賣，即最終只中標且只能中標一次。

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

基于外生投標的迭代組合采購拍賣機制實際上假定投標者在拍賣之前明確知道自己想要投標的組合，即他能詳細列舉并定價所有可能的允許組合。正如引言中所說，這往往是很困難的，尤其是當拍賣的運輸作業數n很大時。

3 內生投標機制與單條線路運輸作業定價

內生投標的基本思想是在多輪拍賣過程中投標者可以不斷提交新的有利可圖的線路組合。利用單條線路的運輸作業服務價格，投標者能夠對拍賣開始之前未曾考慮的線路組合進行定價和投標。

3.1 近似單條線路運輸作業定價

筆者對單條線路運輸作業的服務價格做如下兩個假設:

1）在拍賣的任意一輪中，對于已經獲得暫時指派的組合來說，它所包含的各單條線路運輸作業的服務價格加起來應等于暫時獲勝者的投標價格。

2）在拍賣的任意一輪中，對于暫時未獲得指派的組合來說，它所包含的各單條線路運輸作業的服務價格加起來應小于或等于不中標的最小投標價格。

為了使得迭代拍賣的下降性質得以保持，上述兩個假設是必要的。如果假設1）不成立，例如，對于已經獲得暫時指派的組合來說，如果各單條線路運輸作業的服務價格之和大于暫時獲勝者的投標價格，則那些未中標的投標者在下一輪將以單條線路運輸作業的服務價格之和投相同的標。然而，這樣的投標將是無效的。因為按照迭代下降的拍賣性質，作為暫時未獲得指派的投標者來說，下一輪的投標價格至多為本輪不中標的最低投標價減去ε。如果各單條線路運輸作業的服務價格之和小于暫時獲勝者的投標價格，這將會使得一些成本更低的投標者失去獲得分配該組合的機會。如果假設2）不成立，則在下一輪投標中，那些未中標的投標者將以單條線路運輸作業的服務價格之和投標相同的組合，由于導致更高的效用，該組合仍屬于其最佳反應集中的元素，按照迭代下降的拍賣性質這樣的投標仍然是無效的。

下面構造滿足上面兩個假設條件的單條線路運輸作業的服務價格。

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

LP的對偶問題（DP）如下:

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

因為rj（S）可以取任意大的值，所以RDP總有可行解。rj（S）可以解釋為價格歧視項，它可以避免暫時未獲得指派的組合S的投標價小于該組合中各單條線路運輸作業的價格之和。在多輪下降組合拍賣的背景下使用價格歧視，正的rj（S）將避免虛假套利。因為當投標者j的組合S未獲得暫時指派時〔即yj（S）=0〕，如果單條線路運輸作業的價格之和大于投標者j的投標價，則投標者j在下一輪能夠對組合S中的每一條單條線路運輸作業分別投標，并得到該組合的一個更高的投標價。這必將引起誤導，因為在下一輪，對該組合的要求報價至多為pj（S）-ε，從而導致不必要的投標。

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

在拍賣的每一輪開始之前，拍賣者將宣布一組單條線路運輸作業的服務價格πi（i∈I）和一組對應具體組合的歧視項。每一個投標者會求解其本身的決策子問題，在本輪要求報價的約束下，對使其效用最大化的所有組合進行投標。在拍賣第一輪開始時，投標者可以根據拍賣者宣布的單個作業的最大服務價格對組合進行定價和投標。

3.2 內生投標機制

假設在拍賣的任意一輪中，關于當前指派的RDP所構造的單線路運輸作業服務價格πi（i∈I）存在。于是，在拍賣的第t輪，給定一組運輸作業的服務價格πi（i∈I）和一組對應具體組合的歧視項rj（S），投標者j的最佳反應集為:

如果SDP有多組最優解，則投標者j可以任選其中一組最優解對應的線路組合進行投標。下面給出內生投標組合的定義:

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

由上述定義可見，內生投標保持了投標者的近視最佳反應的性質。內生投標組合的產生使得投標者在拍賣過程中可以不斷更新要提交的最優組合，從而避免了在拍賣開始之前列舉和定價所有相關組合的麻煩。

3.3 內生投標的要求報價

由于在內生投標機制下也有外生投標組合（即在拍賣開始之前就確定好了的組合），因而此時的要求報價分以下幾種情況:

1）對于在第t-1輪中未獲得暫時指派的內生投標組合S來說，在第t輪對它的投標要求報價至多為:

式中:unhappy代表在第t-1輪中未中標的投標者。

2）如果某個在第t-1輪無人投標的組合S在第t輪是某個投標者的內生投標組合，則對它的要求報價至多為:

3）如果某個在第t-1輪獲得暫時指派的組合在第t輪是某個投標者的內生投標，則該組合對于該投標者在第t輪的投標要求報價至多為第t-1輪的獲勝投標價，即:

4）對于在第t-1輪中未獲得暫時指派的外生投標組合S來說，在第t輪對它的投標要求報價至多為:

這樣，內生投標保持了迭代拍賣中組合價格下降的性質。

3.4 內生投標機制下的拍賣步驟

在內生投標機制下，按以下步驟進行拍賣:

1）在拍賣第1輪開始時，投標者根據拍賣者宣布的單獨服務每個作業的最大價格而對組合進行定價和投標。

2）拍賣者計算WDP，明確當前的暫時獲勝者。若滿足拍賣結束規則（見1.4），則拍賣結束，該輪的暫時獲勝者就是最終獲勝者。

3）拍賣者求解RDP，得到服務單個運輸作業的近似價格（πi）和未獲得暫時指派組合的歧視項〔rj（S）〕。

4）拍賣者宣布一組單條線路運輸作業的服務價格πi和一組對應具體組合的歧視項。每一個投標者求解其本身的SDP，在本輪要求報價的約束條件下，對使其效用最大化的所有組合進行投標。然后，轉第2）步。

由于筆者所提出的內生投標機制既保持了迭代組合價格下降的性質，又保持了投標者的近視最佳反應的性質，而迭代拍賣機制的所有其它規則保持不變，因此根據關于拍賣機制有效性的性質可知，本拍賣機制在拍賣結束時將實現系統的最優指派。

4 算例分析

針對一個關于運輸作業指派的采購拍賣的例子，用以直觀地解釋基于外生投標和基于內生投標的迭代下降組合拍賣在運作上的差異。

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

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

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

表2 外生投標結果Table 2 Exogenous bidding results

表3 內生投標結果Table 3 Endogenous bidding results

表4 外生投標中各輪的組合價格Table 4 Package prices for several rounds in exogenous bidding

在外生投標中，由于連續兩輪出現了相同的投標，故拍賣結束。最后，由代理2以成本6服務線路a，代理5以成本17服務線路b和d，代理6以成本6服務線路c，4PL公司總的采購成本為29。該指派結果沒有實現系統的最優指派。如前所述，這主要是由于外生投標限制了可選組合的空間所致。

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

5 結語

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

（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］ 楊華龍，東方，鄭斌，等.集裝箱航運服務多屬性組合拍賣模型與算法［J］.交通運輸工程學報，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

國家自然科學基金項目（70872123）

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