食用農產品采購合同組合反向拍賣的優化

顧 小 林，浦 徐 進，曹文彬

（1.江南大學,江蘇 無錫 214122；2.河海大學,江蘇 南京210098）

一、引言

目前食用農產品采購的特點是品種繁多、批量龐大，包括交貨期限、支付形式等許多不同因素。采購模式是非信息對稱博弈過程，響應用戶需求時間緩慢，供需關系是短期的或臨時的，且競爭多于合作，[1]對供應商產品質量無法進行事前控制，因此導致采購成本較高。

由此提出在食用農產品采購中采用網上反向拍賣采購模式。這一模式不影響企業原有的供應鏈管理模式，可以降低采購成本，防止暗箱操作，特點是買方確定采購標準，賣方進行競標，競價過程中價格隨時間的推移不僅不上升反而下降，買方將待購物品列出，賣方通過競價獲得訂單，買賣雙方簽訂采購合同，可以對采購合同組合反向拍賣進行優化，達到降低采購成本的目的。[2]

二、食用農產品采購合同組合反向拍賣的優化

1.建立食用農產品采購合同組合反向拍賣的相關模型

（1）規定建立食用農產品采購合同組合反向拍賣模型的若干前提

在此實施食用農產品采購合同組合反向拍賣及建立模型的前提，需要以下幾個方面均符合。[3]第一，在規定時間內，各投標供應商密封并提交其標書，投標供應商中采購成本最低的中標。第二，限制每個供應商單項產品供應量的上限、下限及供應總量的上限、下限。第三，每種產品的采購數量較大，供應商因此可以進行價格折扣。第四，每個供應商對若干種或所有的采購合同競標。第五，不同質產品的采購合同由多個供應商競標。第六，同一時間拍賣多個不同質產品的采購合同。第七，限制中標的供應商人數。第八，采購方只有一個。

（2）食用農產品供應商的供應函數

通常供應商供應產品的單位價格是采購量的下降階梯函數，供應函數見公式1。[4]

其中，供應參數是{（l，Q1，Q2，Q3，h），（Z1，Z2，Z3，Z4）}。[l，h]是供應商的供應能力區間，Qi（i=1，2，3）、Zi（i=1，2，3，4）、l和 h 是正值常數，lZ2>Z3>Z4。

（3）食用農產品采購合同組合反向拍賣最優供應模式的模型

假定一個食用農產品采購商為了滿足采購需求以及采購價格最低，借助采購合同組合反向拍賣模式采購食用農產品，在眾多供應商提供的多種食用農產品供應情況中，采購商需要決策選擇最佳的一組供應模式組合，由此建立食用農產品采購合同組合反向拍賣的最優組合供應模式的數學模型，以便進行智能決策，數學模型[5]如下所示。

其中相關符號定義如下：M定義為需要采購的農產品種類數量；Qm定義為每種農產品的需求量；V=（a1v，a2v，…，amv）定義為對 M 種農產品的供應數量為v的供應模式；N定義為供應商的數目；Vn定義為供應商n的供應模式集合；定義為第n個供應商對第m個農產品供應量的下限；定義為第n個供應商對第m個農產品供應量的上限。

則供應商n提供農產品總量的限制定義為：

對第n個供應商提供數量為v的采購成本定義為：

相關決策變量定義如下：

式（2）目標函數表明采購成本需達到極小，式（3）約束限制了食用農產品的采購需求，式（4）限制了每個食用農產品供應商對某個食用農產品的供應數量，式（5）限定每個食用農產品供應商有且只有一種供應模式，式（6）限制了符合標的的食用農產品供應商人數，式（7）約束了食用農產品供應商的模式選擇。上述式（2）~（7）表明需求解0-1整數規劃問題。

由式（2）~（7）模型分析可以得出，隨著供應商數量N及采購食用農產品數量M的增加，食用農產品多物品采購合同供應模式的組合數呈現指數增長。為了滿足食用農產品的采購需求以及實現采購價格最低，食用農產品多個供應商的供應模式組合具備組合意義，理論上最優組合供應模式存在并可解。[6]

2.基于OO競爭策略的自適應遺傳算法確定食用農產品組合供應模式的最優解

求解食用農產品最優組合供應模式的問題可轉化為兩個層面的優化問題，[7]如圖1所示。

圖中，上層是求解食用農產品供應商的組合優化問題，下層是求解在限定供應商范圍內的多種物品最優組合的供應問題。通過對一個食用農產品最優組合供應模式確定的動態規劃算法的多次循環調用，來求解下層優化問題，下層優化問題的計算結果用于解決上層優化問題。[8]但是在求解上層優化問題時存在NP難題，因為如果食用農產品的供應商人數N太大，則從N中選取b（L≤b≤H）的組合數過大，于是求解0-1整數規劃模型形成NP難題。[9]自適應遺傳算法可用于求解變長染色體的離散組合優化問題，且求解組合優化問題較傳統算法效果較為明顯，[10]在此采取基于OO競爭策略的自適應遺傳算法對上述0-1規劃模型求解。[11]

（1）基于OO競爭策略的自適應遺傳算法

OO（One to One）競爭策略的自適應遺傳算法的主要思想，是在遺傳算法中借助Player Killing賽式的競爭篩選尋找全局最優解。執行變異操作前即時檢測全程最優解，并且配合交叉率自適應地動態調整個體粒度，以避免算法陷入局部極值點，而且減少退化現象，同時引入復活賽機制，提高算法收斂到全局最優解的概率。[12]

圖1 食用農產品多物品最優組合供應模式兩層優化

基于OO競爭策略的自適應遺傳算法有以下特點：

①從算法內部解決遺傳算法的局部搜索能力不足問題。傳統上均從外部引入優化算法，[13]基于OO競爭策略的自適應遺傳算法不從外部引入任何方法，而是在算法中首先設置較大的交叉率與變異率，可以提高全局及局部的搜索能力。[14]其次，變異算子僅當算法檢測到當前代種群的最佳適應度和父代對比未改進時，才參與執行變異并進行局部搜索。

②提高了算法搜索到全局最優解的概率。此算法采取兩種方式，首先設定較大的種群規模，有利于提高全局搜索效率。其次采用復活賽機制，復活賽機制中借助選擇算子配合替換算子來實現，在算法執行過程中，每一代的最優個體取代最劣個體，在算法結束的前一代剩下一優一劣兩個個體，兩個個體執行替換操作后變得相同，當進行選擇操作時，兩個個體都進入下一代的進化并進行下一輪的競賽。引入復活賽機制提高了全局最優解與全程最優個體吻合的概率。[15]

③交叉率與變異率的自適應調整細化到了個體粒度上。傳統方法交叉率與變異率的自適應調整局限在種群粒度上，而在此算法中，每一代每一種群中的每一個體的交叉率及變異率，均依據自身的適應度和當前種群的平均適應度進行自適應的動態調整。在此是求適應度函數的最小值，則交叉率與變異率分別按式（14）設置，即當本代平均適應度小于被選中進行交叉的兩個個體的適應度時，則交叉率自動升高，反之則自動降低，減少進化過程中的退化現象。

④適應度函數不再局限于非負的范圍，在此將目標函數作為適應度函數，避免了目標函數和適應度函數相互轉化時產生的映射誤差，不僅降低了轉換計算的復雜度，而且提高了算法的效率。[16]

⑤采用不同于傳統的方法設定初始種群規模。種群規模會影響傳統遺傳算法的運算效率，過大的種群規模會導致程序運行時間太長及算法收斂非常緩慢，而過小的種群規模會導致搜索能力不足及找不到全局最優解。而在此算法中，初始種群規模越大，算法的搜索能力越強，因為種群規模幾乎以減半的速度隨算法的運行不斷減小。[17]

⑥總體的進化策略與傳統遺傳算法不同。此算法在進化過程中，不再固定種群規模，同時不再限定進化代數，系統通過個體的競爭，自動選擇更符合優化目標的個體進入下一代。采用這種選擇策略結合最優個體保存策略，隨著進化代數的增加種群規模不斷減小，直至最后只剩下一個全程最優個體，即為全程最優解。此進化篩選策略保證算法能夠以極快的速度收斂。

（2）基于OO競爭策略的自適應遺傳算法的編碼方法

基于OO競爭策略的自適應遺傳算法的編碼方法采取二元組編碼，[18]一個染色體個體可用X=[（i1，d1），（i2，d2），…，（im，dm）]表示。其中im代表基因座編號，對應的基因值是dm。其值的選取需符合染色體兩個方面的要求：

①染色體長度的要求。在此設定常規染色體的長度為H，最短染色體的長度為L。用im∈I={1，2，…，H}表示基因座編號，用 dm∈D={1，2，…，N}表示某一標書的編號，即是對應的基因值。

②染色體中基因座對應基因值的要求。因為L表示染色體的最短長度，所以對某個單項農產品假定有L個供應商，采購商對該項農產品的需求，通過L個供應商對該項農產品的總供應能夠得到滿足。為了符合染色體的要求，在基因值對應供應商的供應模式中，對每種農產品至少有L個供應商進行供應。

（3）適應度函數

此算法把適應度函數作為目標函數。[19]因為在實際應用中的優化問題大多數都可以轉化為數值函數的優化問題。

給定一個染色體等于給定了一組固定的供應商集合，由此可以用動態規劃算法算出該組供應商的最優組合供應目標函數值。

對于求最小值的問題，目標函數f（X）可為如下適應度函數F（X）：

其中，Cmax是本代染色體中目標函數的最大值。

（4）設定交叉率和變異率

在基于OO競爭策略的自適應遺傳算法中，遺傳操作的控制變量是根據個體的評估賦值情況隨時修正的。交叉率與變異率根據優化目標分別按如下公式計算。[20]

（5）基于OO競爭策略自適應遺傳算法的計算步驟

第一步：初始化。設置種群規模SP、交叉率pc、變異率 pm，置 m=0；隨機生成初始種群 POP（0）={X1，X2，…，Xm}；對于第二層優化， 用動態規劃算法精確求解，對每個個體解碼，計算每個個體目標函數值，設置初始歷史最好解 X（*），最優目標值 F（*）=F（X（*））。

第二步：m=m+1。當種群規模大于1時，用動態規劃算法精確求解進行第二層優化，對每個個體解碼，計算每個個體的適應度函數F（Xj），按由大到小順序排列。

第三步：執行雜交操作。由上面給出的雜交算子產生中間后代，用動態規劃算法精確求解進行第二層優化，求出中間后代的適應度以及所有中間后代中的最優個體。

第四步：記錄到當前代為止最符合優化目標個體的最小適應度。如果新的最優目標值與歷史最優目標值相等，則執行變異操作。由上面給出的變異算子對每一個被選的后代進行變異，產生后代。用動態規劃算法精確求解進行第二層優化，求出變異后代的適應度。

第五步：當第i個個體的適應度小于等于當前代種群的平均適應度時，進行選擇操作。由上面給出的選擇算子，在當前種群和所有后代中選出最優個體。記錄新的最優目標值、最劣值，用歷史最優目標值代替最劣值。

第六步：當種群規模大于SP時，輸出最優解X（*）及最優目標值 F（X（*）），進化結束。

否則結束本次循環，轉第二步。

3.基于OO競爭策略自適應遺傳算法組合招標的仿真實例

在計算機上對此問題進行仿真，實驗環境是Windows XP，編程語言為Java，編制基于OO競爭策略自適應遺傳算法，此問題用“標書數/待組合反向拍賣采購的食用農產品數/允許中標的食用農產品供應商人數區間”描述，在此列舉一個由20/8[3，6]組成的多食用農產品最優組合供應模式說明，其中20是供應商的標書個數，8是待組合反向拍賣采購的食用農產品種類數，[3，6]是允許中標的食用農產品供應商人數區間。

在此食用農產品供應商的標書標號分別用1～20表示，食用農產品種類分別用英文字母S1~S8表示。表1是食用農產品采購合同的信息，其中規定了食用農產品供應商對每種產品提供數量的下限和上限，基于OO競爭策略自適應遺傳算法的參數Pc=0.95，Pm=1，SP=1000，表 2 給出食用農產品采購合同最優組合供應模式的計算結果。

表2中的后五列單元格內的括號外數字表示此單元格所在列對應的食用農產品供應商采購此單元格所在行對應食用農產品的采購量，括號內的數字表示此單元格括號外的食用農產品供應商采購量的采購價格。

表1 食用農產品采購合同的信息

表2 最優組合供應模式的計算結果

最后中標的食用農產品供應商的標號為（4，7，10，16，18）。 采購總支出的計算過程如下：

采購總支出=130*21+105*12+100*14+90*22+70*17+50*21+45*12+113*20+82*15+60*23+60*16+70*20+45*13+130*20+100*11+85*13+90*20+60*23+100*22+110*11+60*11+107*12+88*16+80*15=32782（元）。

綜上所述，一個由20/8[3，6]組成的多食用農產品最優組合供應模式的采購總支出為32782元。

三、結語

在食用農產品供應采購中采用網上反向拍賣采購模式，從根本上對采購方式及其交易模式進行了變革，通過對食用農產品供應采購合同的組合反向拍賣優化降低了采購成本，解決了目前供應采購中存在的問題。

在食用農產品采購合同組合反向拍賣的優化中，建立了食用農產品最優組合供應模式的模型，設計了求解此模型的算法，算法包括第一層優化采取動態規劃算法精確求解，第二層優化采取OO競爭策略的自適應遺傳算法求解，并通過仿真實例證明了設計算法的有效性和模型的普適性。

食用農產品采購合同組合反向拍賣的優化還需要進一步完善，今后的研究可以從以下兩方面進行：

在現有算法基礎上改進算法。進一步提高算法的收斂速度以及運算效率。

在按需應變環境下改進模型及算法。為了適應動態環境的多變性，增強現有模型和算法的普適性和靈活性，需要改造現有模型和算法，構建下層的仿真模型、設計上層的優化算法以及提高仿真優化的計算效率等。

[1]陳培友，汪定偉．多物品最優組合供應模式確定問題的模型研究[J]．中國管理科學，2006，14（4）：35-39．

[2]Wurman P．R．，Walsh W．E．，Wellman M．P．.Flexible Double Auctions for Electronic Commerce：Theory and Implementation[J]．Decision Support Systems，1998，24（1）：17-27.

[3]Emiliani M．L.．Business to Business Online Auctions:Key Issues for Purchasing Process Improvement[J]．Supply Chain Management，2000，5（4）：305-315.

[4]高鴻業．西方經濟學（微觀部分）[M]．北京：中國人民大學出版社，2011：24-26．

[5]尹伯成．西方經濟學簡明教程[M]．上海：格致出版社，2011：65-66．

[6]于春田，李法朝，惠紅旗．運籌學[M]．北京：科學出版社，2011：143-145．

[7]王旭，葛顯龍，林云．供應商選擇的雙層規劃模型及求解分析[J]．計算機工程與應用，2009，45（23）：11-14．

[8]唐立新，孫德剛．單一品種項目的生產批量問題的動態規劃算法[J]．東北大學學報（自然科學版），1999，20（4）：373-375．

[9]Cohen L.，K.Diether C.Malloy.Supply and Demand Shift in the Shorting Market[J]．Journal of Finance，2007，59：1845-1875.

[10]Lebrun B..A Continuity of the First Price Auction Nash Equilibrium Correspondence [J]．Economic Theory，2002，20（3）：435-453.

[11]諸克軍，李蘭蘭，郭海湘．一種融合遺傳算法和粒子群算法的改進模糊C-均值算法[J]．系統管理學報，2011（6）：728-733．

[12]N.van Hoom J.Togelius D.Wierstra，J.Schmidhuber.Robust Player Imitation Using Multiobjective Evolution[M]．//Proceedings of IEEE Congress on Evolutionary Computation，2009：652-659.

[13]J.Wu，L.Chen，L.Yang，Q.Zhang，L.Peng.A Collision Detection Algorithm based on Self-adaptive Genetic Method in Virtual Environment[M]．//Proceedings of the 1st International Conference on Swarm Intelligence，2010：461-468.

[14]B.B.Li，Z.H.Zhao.Fitness Function Optimized in Genetic Algorithm for Fabric Dynamic Simulation[M]．//Proceedings of IEEE Pacific-Asia Workshop on Computational Intelligence and Industrial Application，2008：59-63.

[15]謝安世，周傳華，徐新衛，張芬．基于PK模型的一種自適應遺傳算法研究 [J]．計算機工程與應用，2010，46（7）：52-56．

[16]江中央，蔡自興，王勇．用于全局優化的混合正交遺傳算法[J]．計算機工程，2009，35（4）：204-206．

[17]張思才，張方曉．一種遺傳算法適應度函數的改進方法[J]．計算機應用與軟件，2006，23（2）：108-110．

[18]徐文婷，李承鵬．基于自適應遺傳算法的離散化方法[J]．合肥師范學院學報，2011（3）：14-17．

[19]郭華芳，劉海利，李海生，張嚴林．用變長度染色體遺傳算法優化加工路徑的方法[J]．計算機工程與應用，2009，45（6）：207-209．

[20]黃江波，付志紅．基于自適應遺傳算法函數優化與仿真[J]．計算機仿真，2011（5）：237-240．