供應鏈服務組合招標采購獲勝者確定的優化算法研究

馬金麟，錢麗娟，劉志強

（1.江蘇大學 汽車與交通工程學院，江蘇 鎮江 212013；2.江蘇大學 理學院，江蘇 鎮江 212013）

供應鏈服務組合采購的招標問題一直是國內外學者研究的一個重要問題，該類問題主要是解決在供應鏈環境下如何確定服務采購的獲勝者.早期文獻對于供應鏈服務采購的研究大多只是圍繞單個服務采購獲勝者進行建模求解，而較少涉及多項服務組合采購的情況.但事實上，企業的服務采購是以多產品模式為主的，直到近年來國內外學者才對多產品和多服務的組合采購問題進行了較深入的研究.國外學者ELSEVIER（1984）研究了隨機需求下多產品的采購周期問題［1］，ABAD（1989）分析了多產品多市場的采購策略［2］，SONG（2002）等探討了運輸服務組合招標采購的模式［3］，SHEFFI（2004）建立了以運費最小化為目標的服務組合招標采購模型［4］，SAWIK（2007）使用整數目標規劃對多產品的生產計劃排程和控制問題進行了討論［5］.國內學者段喆和朱道立（2004）提出了一個多階段多產品供應量分配的綜合模型［6］，關志民等（2005）研究了多產品采購條件下的供應商選擇與訂購量分配問題研究［7］，陳培友等（2006）建立了多物品最優組合供應模式確定的定量模型［8］，黃河等研究了采購組合投標的均衡策略及多因素采購的獲勝者確定問題［9］，楊華龍等探討了航運服務組合招標采購的算法模型［10］.

上述文獻從定性和定量角度都較好地探討了多物品多服務的采購問題，推動了供應鏈組合采購研究的向前發展.本文的主要工作則是研究設計供應鏈服務組合招標采購中獲勝者確定的高效算法.根據供應鏈對多項服務組合采購的需要，建立分散的目標規劃模型，借助于混合集合規劃的迭代，巧妙地建立模型變量和約束條件之間的數據關系模型，為克服優化目標方向和量綱不同的問題，設計了模糊的歐幾里得距離來確定獲勝者.求解編碼使用NCL語言，優化平臺為POEM軟件.

1 供應鏈服務組合招標采購問題的數學描述

1.1 問題提出及解決思路

設供應鏈中某企業需要采購N種服務，標記為j，j∈ ｛1，2，…，N｝，采購方根據服務的特點和要求面向M個服務提供商進行招標采購，投標者標記為i，i∈ ｛1，2，…，M｝.各投標者能夠提供其中一種或幾種服務產品，并且在報價、服務質量、企業信譽等方面有較大或略微的差異.假設投標者i的 投 標 組 合 為 ServiceSupplier＿｛i｝， 則 集 合ServiceSupplier＿｛i｝在內容上是全部N 種產品的任意組合，各個ServiceSupplier之間在服務組合的評價屬性分別為：priceServiceSupplier＿｛i，j｝、qualityServiceSupplier＿｛i，j｝和reputationService－Supplier＿｛i，j｝.

該問題的解決是以效用最大化為原則擇優選擇中標企業集合.然而，分別以低成本、高質量和高信譽為目標得到的最優解未必是同一投標者的報價、質量和信譽，因此要經過量綱處理后將所有投標者的屬性與最優解price＊、quality＊和reputation＊做歐幾里得距離比較，距離最小的投標者將被確定為組合投標的獲勝者.

圖1 供應鏈服務組合招標采購的優化思路Fig.1 The optimizing thought of combinatorial bidding purchase in supply chain

1.2 基本假設

針對該問題，做出如下基本假設：

1）采購方的N類服務產品可同時向一個或多個投標者采購，同一個投標者只有一次投標機會，其投標內容要么是其中的一種服務，要么是多種服務產品的組合，對應著服務產品的報價也是一種或多種服務的報價.

2）不重復中標.即同一種服務的投標者中只有一個獲勝者，也就是說任意一種服務產品j，不可能出現多個投標者同時中標的情況.

3）采購方的所有服務產品，都要在招投標中得以采購實現.

4）參與投標的企業“要么組合獲勝，要么投標失敗”，即如果某投標者i中標，其投標的服務組合ServiceSupplier＿｛i，j｝將全部中標；反之，如果投標者的ServiceSupplier＿｛i，j｝中出現某一投標服務j沒有被選中，則 ServiceSupplier＿｛i，j｝全體中標失敗.

5）采購方可以根據自身情況，限定最?。畲笾袠苏叩臄盗?，以控制采購質量.

6）采購方考慮到與供應鏈合作伙伴的關系，可以指定某以往合作企業為獲勝者之一.由于增加新的供應鏈伙伴可能會帶來額外的成本，因此采購方在服務采購計劃中有指派某投標者的權力.

7）投標方的服務質量和信譽可以通過專家打分實現定量化.

2 算法設計

2.1 混合集合規劃數據模型

在該問題中，price為數值型信息，將quality、reputation信息做量綱處理，使之也成為數值型信息，通過集合的混合規劃描述為如下數據模型：

1）輸入數據模型

表1 服務產品信息表（OPT＿SERVICE）Tab.1 Information table of service product

表2 投標者信息表（OPT＿SUPPLIER）Tab.2 Information table of service suppliers

表3 投標者與服務組合的匹配表（OPT＿CONSISTENCY）Tab.3 Consistency information between services and suppliers

2）輸出數據模型

表4 中標企業信息表（OPT＿ACTIVESUPPLIER）Tab.4 The winning information of winning suppliers

2.2 約束規劃算法

在約束規劃中，各變量之間的邏輯關系十分重要.所有的采購和投標數據經過上述2.1中的數據模型規劃后，從邏輯關系上轉變成為集合之間的約束：

1）中標服務組合約束

投標者i的服務投標組合記為ServiceSupplier＿｛i｝，通過布爾值變量（0－1變量）將ServiceSupplier＿｛i｝部分放入到模糊的集合ActiveService中.

2）中標者約束

3）關聯約束

2.3 滿意解設計

（1）～（3）的分別所得的最優解所對應的最優目標值為：price＊，quality＊，reputation＊.假設某個虛擬的投標者ActiveSupplier＊，其報價組合為price＊，質量組合為quality＊，信譽組合為reputation＊，采用模糊的歐幾里得距離求出與虛擬投標者ActiveSupplier＊距離最相近的解ActiveSupplier’.

通過約束條件對解空間切割、枚舉、回溯，得到滿意解ActiveSupplier’和ActiveService’.

3 算例

模擬一組供應鏈服務組合招標采購的應用數據，假設某供應鏈采購商所采購的服務類型為A、B、C、D，采購形式為組合招標采購，參加投標的供應商共有22家，相應的投標組合信息如下表所示，其中質量和信譽的數值信息是通過專家打分法定量化以后得到的數據.

表5 各投標者的投標信息Tab.5 The bidding information of each supplier

采用權重系數來調整采購方對價格、質量、信譽的重視程度，在該算例中，取ω1＝0.4，ω2＝0.35，ω3＝0.25.按照上述算法規則，很快可以得到以下獲勝信息：

分析該結果，該供應鏈服務采購的獲勝者為：A →S1，B→S5，C→S7，D →S8.算法設計的中間過程中出現的price＊＝57，quality＊＝35和reputation＊＝34，其獲勝者的結果不一致，因此假設某一虛擬獲勝者組合的服務價格、質量和信譽組合為57，35和34，用實際的各種投標商組合價格、質量和信譽與此虛擬獲勝者做歐幾里得距離的比較，得到最小值min d＝1.8027755，確定出實際投標者中獲勝者組合為S1，S5，S7和S8.采購總價格為59，質量總評分為33，信譽總評分為33，使用PEOM 軟件平臺總的用時為3.218s（2.875s＋0.156s＋0.078s＋0.109119s）.

4 結論

本文主要從優化算法上對供應鏈服務組合采購問題進行了研究，通過混合集合規劃的數據建模并假設一中間虛擬獲勝者組合，求出虛擬組合的最優目標函數值price＊、quality＊和reputation＊，借助price＊、quality＊、reputation＊使用模糊的歐幾里得距離計算出實際中的獲勝者組合.采購方可以調整權重系數以表示其對價格、質量、信譽等條件的不同重視度.算法使用混合集合表達約束關系，通過模擬算例的實證，證明了該優化算法的實用性和高效性.

［1］Elsevier A.Multi－product stochastic－demand periodic－review inventory and production cycling policies［J］.Inventory in Theory and Practice，1986，3：489－503.

［2］Abad P L.Multi－product multi－market model for co－ordination of marketing and production decisions［J］.International Journal Systems Science，1989，20（11）：2011－2027.

［3］Song J，Rrgan A C.Combinatorial auctions for transportation service procurement：the carrier perspective［J］.Transportation Research Record，2002（1833）：40－46.

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

［5］SAWIK T.A multi－objective customer orders assignment and resource leveling in make－to－order manufacturing［J］.International Transactions in Operational Research，2007，14（6）：491－508.

［6］段 喆，朱道立.多階段多產品供應量分配的綜合模型［J］.系統工程，2004，22（6）：21－24.

［7］關志民，周寶剛，馬欽海.多產品采購條件下的供應商選擇與訂購量分配問題研究［J］.計算機集成制造系統，2005，11（11）：1626－1632.

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

［9］黃 河，徐鴻雁，陳 劍.多因素采購組合拍賣獲勝者確定問題研究［J］.系統工程理論與實踐，2008，28（7）：27－33.

［10］楊華龍，東 方，鄭 斌，等.集裝箱航運服務多屬性組合拍賣模型與算法［J］.交通運輸工程學報，2009，9（5）：111－115.