基于分支凍結算法的供應商選擇與訂單分配

劉丹陽LIU Dan-yang；高翔宇GAO Xiang-yu

（沈陽大學機械工程學院，沈陽 110044）

0 引言

隨著現(xiàn)代市場經(jīng)濟的快速發(fā)展，企業(yè)之間的競爭已經(jīng)演變成供應鏈之間的競爭。核心企業(yè)將其核心技術與產(chǎn)品控制在自己的手里，業(yè)務轉(zhuǎn)交給供應鏈下游的供應商，從而對供應鏈上的物流、資金流、信息流進行整體優(yōu)化，通過實現(xiàn)供應鏈的整體效益最大化來獲得企業(yè)的競爭優(yōu)勢。本文通過對供應商選擇于訂單分配的研究以增加企業(yè)的競爭能力。

現(xiàn)有研究中，Garfamy[1]利用DEA 法來評估供應商，該模型主要利用成本指標，能以最低的成本提供最佳的供應商選擇。Lee 等[2]利用FAHP 法整合德爾菲法來進行供應商評估。德爾菲法被用來區(qū)分評估傳統(tǒng)供應商與綠色供應商的指標。范志強[3]建立了更加符合實際需求的訂單分配多目標混合整數(shù)規(guī)劃模型，并設計了一種模擬退火算法，解決訂單分配過程中的產(chǎn)品缺陷問題。Nima 等[4]提出了一種模糊偏好規(guī)劃和基于區(qū)間的理想解法相結合的供應商評價方法，建立了模糊多目標線性規(guī)劃模型。Sudhir Barange 等[5]建立了可持續(xù)供應鏈管理的層次分析法，利用可持續(xù)供應商選擇決策標準的主動整合開發(fā)動態(tài)策略，使其在整個供應鏈中有效地發(fā)揮作用。牟能冶等[6]為構建不確定環(huán)境下的可持續(xù)供應商選擇模型，提出基于PDHFLTS 與群決策理論的三階段決策方法，以降低可持續(xù)供應商選擇的復雜度。劉森等[7]針對從環(huán)境管理體系和員工權益等四方面衡量供應商的可持續(xù)性，提出了基于模糊最優(yōu)最劣法決策模型，計算出更加客觀的指標權重。Shan-Yong You 等[8]建立了多目標線性規(guī)劃（MOLP）模型以在選定的供應商之間分配合理的訂單數(shù)量，采用雙層次猶豫語言術語集（DHHLTS）處理評估替代供應商的可持續(xù)績效時的不確定。

綜上所述，國內(nèi)外眾多學者在供應商選擇領域取得了豐富的研究成果，但大部分研究仍局限于環(huán)境因素以及社會因素對可持續(xù)供應商選擇與訂單分配的影響，相較其經(jīng)濟因素研究的較少，考慮到運輸提前期或最低起訂量要求的更少。因此，本文研究經(jīng)濟因素中的運輸特性（運輸提前期和供應商的能力）和買方的貨幣限制對可持續(xù)供應商選擇與訂單分配的影響。

1 供應商選擇問題建模

1.1 問題描述與參數(shù)設置

本文針對兩個或多個異構供應商和一個買方之間的供應商選擇問題進行研究。供應商之間的區(qū)別在于所提供物品的類型和銷售價格、交貨提前期以及最小訂單數(shù)量要求?？紤]到每個供應商的特點，買方必須在每個周期開始時做出SSS & OA 決策。買方試圖實現(xiàn)的目標是最小化整個計劃范圍內(nèi)相關成本的凈現(xiàn)值。相關參數(shù)如下：

i：物料編號；

j：三重底線原則，即j=經(jīng)濟，社會，環(huán)境；

k：供應商編號；

t：周期（計劃展望期的結束期）；

r：每期折扣；

M：一個無限大的數(shù)字；

K：銷售商品的供應商編號；

I：供應商出售商品編號；

vi：i 項目數(shù)量

wct：買方在t 期的庫存容量；

hi：項目i 的持有成本；

bi：項目i 的短缺成本；

Dit：物料i 未來期間的預測；

ξit：Dit誤差的標準偏差；

pikt：買方在t 期間向供應商k 支付的項目i 的單位購買價格；

pikt：在t 期內(nèi)供應商k 項目i 現(xiàn)貨市場單價；

owclt：t 期運營資金限額；

captt：最初分配給t 期的資金；

ict：t 期庫存控制相關成本；

rct：t 期補貨相關成本；

moqik：供應商k 為i 指定的每期最小訂單數(shù)量；

mpak：供應商k 設定的每期最低采購金額；

mpilik：供應商k 指定的i 的最大采購限額；

scjk：供應商k 的三重底線原則j 因子得分；

targetjt：三重底線因子j 在t 期目標得分；

fkt：t 期間供應商k 的每輛車的運費；

Vk：供應商k 每輛車的容量；

NVkt：t 時間內(nèi)供應商k 可用于運輸?shù)能囕v數(shù)；

xikt：在過去t 期開始時供應商k 交付的項目i 已經(jīng)進行的采購；

IPio：計劃開始時物料i 的庫存容量；

IPit：t 期結束時i 項的庫存狀態(tài)；

IP+a：IPit的有利狀態(tài)；

IP-a：IPit的損失狀態(tài)；

Xki：從供應商k 處購買i 項的金額；

Xkit：t 期間從供應商k 處購買i 項的計劃金額；

zi：本期從現(xiàn)貨市場購買商品i 的數(shù)量；

zit：t 期從現(xiàn)貨市場購買i 項目的計劃數(shù)量；

RLit：計劃在t 期開始時訂單到達后物料i 的補充水平。

1.2 混合整數(shù)規(guī)劃模型構建

等式（1）中的目標函數(shù)是最小化預期總成本的現(xiàn)值，該現(xiàn)值是庫存和補充相關成本的總和；等式（2）強制規(guī)定物料I 的補充水平是初始庫存、現(xiàn)貨市場采購和計劃在此期間從每個供應商處到達的訂單的總和；等式（3）規(guī)定，在周期t 結束時，物料I 的凈庫存等于周期t 開始時的庫存狀況減去由于周期t 期間物料I 的需求而導致的損耗；等式（4）規(guī)定，在周期t 結束時，物料的凈庫存IPit，等于周期t 結束時物料I 的現(xiàn)有庫存水平IP+it減去周期t 結束時物料的短缺水平IPit；等式（5）-（8）描述了供應商設定的客戶服務水平（t 期庫存控制相關成本和t 期補貨相關成本），等式（9）和（10）描述了最大購買限額的約束；等式（11）和（12）是針對最小訂貨量要求的，約束是供應商k 的最小訂單量，是一個二元變量，用于按計劃加強關系，變量M是一個非常大的數(shù)字，僅在下訂單時用于激活最小訂單約束。因此，如果買方從供應商k 處購買物品，則等式（11）中的參數(shù)將變?yōu)?，從而驗證等式（12）并實施最小訂單量要求。

2 分支凍結算法

BF 算法可以形式化描述如下:

步驟1：（初始化）設定當前周期為周期1，當前庫存水平zio，i=1，2，3，…，I。所有未來期間的預測需求dit，t=1，2，3，…，t。

步驟2：（為第一次運行生成子問題）通過移除最小訂單量和物料需求計劃約束MIP1 中的等式（12）來構造子問題。

步驟3：（運行子問題）運行當前子問題。

步驟4：（檢查狀態(tài)和分支）檢查步驟3 的輸出。如果狀態(tài)是PF 或CF，其是部分可行或完全不可行的情況，如果沒有約束可加，則給定問題不可行，終止。如果狀態(tài)為PF，請轉(zhuǎn)到步驟5，否則，請轉(zhuǎn)到步驟6。

步驟5：（部分可行性案例）對于步驟5，可分為凍結輸出、重新初始化以及添加一個子問題。對于凍結輸出，屬于凍結可行期間的輸出；對于重新初始化，讓起始周期成為第一個不可行周期，將當前庫存水平重置為最后一個可行周期的凈庫存水平。

步驟6：（完成不可行案例）步驟6 重復步驟5 部分可行中的不可行部分，通過添加供應商的最小起訂量或最大生產(chǎn)量約束條件產(chǎn)生一個新的子問題，如果在之前的運行中造成了不可行性，則轉(zhuǎn)到步驟3。（圖1）

圖1 分支凍結算法的流程圖

3 數(shù)值實驗

本文進行數(shù)值實驗時考慮了兩個目標，第一個是通過與商業(yè)軟件工具（GAMS/XPRESS 求解器）進行比較用以測試BF 算法的準確性；數(shù)值實驗中使用的GAMS 是一種非常流行的建模語言，包含許多強大的解算器。因此，通過該商業(yè)軟件工具驗證BF 算法的準確性，以及其在解決最大可解問題規(guī)模的優(yōu)勢。

3.1 分支凍結算法的精準度

該實驗的目的是通過將使用分支凍結算法獲得的結果與GAMS/XPRESS 解算器的結果進行比較來判斷BF 算法的準確性。比較實驗是在假設物品的需求是從一個穩(wěn)定的需求過程中產(chǎn)生的情況下進行的。之前大多數(shù)關于庫存管理的研究都是通過假設需求遵循一個平穩(wěn)的需求過程進行實驗的，本實驗也是假設其滿足正態(tài)分布進行的。項目類型的數(shù)量設置為五個。每個項目的實際需求數(shù)據(jù)由五個不同的正態(tài)分布生成

為了獲得平均總成本，對每個設置重復實驗10 次。以這種方式獲得的平均成本被插入到下面的百分比偏差度量中，以確定BF 算法的準確性。

對于此次實驗，假設系統(tǒng)中有10 個供應商，運輸提前期為零，每一個供應商可以交付五種類型的產(chǎn)品，單位周期長度為四周，規(guī)劃期限為48 周，其輸入?yún)?shù)如表1-表3 所示。

表1 對比實驗的參數(shù)

表2 每個項目的參數(shù)

表3 每個供應商的參數(shù)

實驗的結果如表4 所示。通過采用BF 算法與商業(yè)求解器（GAMS/XPRESS 求解器）和NSGAⅡ?qū)Ρ瓤芍?，BF 算法在解決問題的平均年貼現(xiàn)成本、平均百分比偏差、平均處理時間和解決子問題的平均數(shù)等四個方面均優(yōu)于NSGAⅡ和GAMS 算法。因此可知，BF 算法能夠找到接近最優(yōu)的解，其作為一種啟發(fā)式算法，其求解大型問題上，可以解決其現(xiàn)有工具不能有效解決的問題。

表4 精準度測試結果

3.2 分支凍結算法求解最大問題規(guī)模實驗

為解決優(yōu)化模型而開發(fā)的各種軟件工具，其對在合理的計算時間內(nèi)可以解決的問題有最大數(shù)量限制?？紤]到這一限制，本文通過對比商業(yè)軟件工具和BF 算法在解決問題的最大規(guī)模用以分析BF 算法的有效性。在實驗中，選擇GAMS/XPRESS 和GAMS/COINGLPK 解算器進行比較，問題的計劃范圍被固定為12 個時間段，并且供應商的數(shù)量被設置為項目數(shù)量的10 倍。最大計算時間限制設置為24 小時。此次實驗增加了項目的數(shù)量，直到每個方法都無法在時間限制內(nèi)找到解決方案，表明BF 算法在解決問題的項目數(shù)、變量數(shù)和約束數(shù)均優(yōu)于GAMS 求解器，并且其求解問題規(guī)模高于GAMS2.4 倍。

4 結論

①本文研究買方從兩個或兩個以上的異質(zhì)供應商選擇以及訂單分配問題。首先對供應商選擇與訂單分配問題進行了描述，在此基礎商構建了包含最小起訂量和最大生產(chǎn)量的限制、營運資金限制及3BL 可持續(xù)性目標的優(yōu)化模型；

②通過數(shù)值實驗對算法進行了測試，測試結果表明本文所構建的模型反映供應商選擇與訂單分配的有效性，所設計的算法能夠在允許的時間內(nèi)獲得穩(wěn)定的滿意解，同時在解決問題的時間和子問題的數(shù)量上均優(yōu)于NSGA Ⅱ。