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

馬金麟，錢麗娟，劉志強

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

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

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

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

1.1 問題提出及解決思路

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

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

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

1.2 基本假設

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

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

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

3）采購方的所有服務產(chǎn)品，都要在招投標中得以采購實現(xiàn).

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

5）采購方可以根據(jù)自身情況，限定最?。畲笾袠苏叩臄?shù)量，以控制采購質(zhì)量.

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

7）投標方的服務質(zhì)量和信譽可以通過專家打分實現(xiàn)定量化.

2 算法設計

2.1 混合集合規(guī)劃數(shù)據(jù)模型

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

1）輸入數(shù)據(jù)模型

表1 服務產(chǎn)品信息表（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）輸出數(shù)據(jù)模型

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

2.2 約束規(guī)劃算法

在約束規(guī)劃中，各變量之間的邏輯關(guān)系十分重要.所有的采購和投標數(shù)據(jù)經(jīng)過上述2.1中的數(shù)據(jù)模型規(guī)劃后，從邏輯關(guān)系上轉(zhuǎn)變成為集合之間的約束：

1）中標服務組合約束

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

2）中標者約束

3）關(guān)聯(lián)約束

2.3 滿意解設計

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

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

3 算例

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

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

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

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

4 結(jié)論

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

［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］段 喆，朱道立.多階段多產(chǎn)品供應量分配的綜合模型［J］.系統(tǒng)工程，2004，22（6）：21－24.

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

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

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

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