基于模擬退火算法的供應(yīng)鏈協(xié)調(diào)機(jī)制問題

朱美樺，王興芳，韓 瑛

（蘭州交通大學(xué) 交通運(yùn)輸學(xué)院，甘肅 蘭州 730070）

1 供應(yīng)鏈中分級(jí)協(xié)調(diào)機(jī)制的問題闡述和模型建立

1.1 問題描述

圖1為庫存系統(tǒng)圖，圖中箭頭方向表示物流的方向，有向線段表示銷售商、供應(yīng)商、生產(chǎn)商之間的物流。

圖1 供應(yīng)調(diào)查

為了滿足銷售商的要求，生產(chǎn)商需從供應(yīng)商那里提前訂購零件，但由于種種原因，有時(shí)供應(yīng)商不能按時(shí)交貨，這樣產(chǎn)品就不能按時(shí)被生產(chǎn)商生產(chǎn)出來，進(jìn)而影響了銷售商的銷售市場。但是，任何事物都是有規(guī)則的，供應(yīng)商、生產(chǎn)商、銷售商也不例外，為了彼此達(dá)到“互利共贏”的目的，一張合同將它們緊密聯(lián)系在了一起。

因此，為了協(xié)調(diào)這種關(guān)系，提出方法—懲罰費(fèi)用。對(duì)于供應(yīng)商不能按時(shí)交貨，給出懲罰費(fèi)用，對(duì)于生產(chǎn)商不能按時(shí)交貨，也給出一個(gè)懲罰費(fèi)用。

1.2 供應(yīng)鏈的基本數(shù)學(xué)模型

1.2.1 模型假設(shè)

本文所做的假設(shè)如下：①生產(chǎn)商和供應(yīng)商是長期的合作伙伴，并且相互信任；②生產(chǎn)商和供應(yīng)商信息不對(duì)稱，也就是說，他們之間保持一定的隱私，不透漏其所有數(shù)據(jù)；③供應(yīng)商、生產(chǎn)商和銷售商是一個(gè)相互合作的團(tuán)隊(duì)，所有參與者都為了使一個(gè)共同的目標(biāo)得到最優(yōu)化；④在整個(gè)供應(yīng)鏈中，已知的量是銷售商訂單；⑤在整個(gè)供應(yīng)鏈中，只考慮成本不考慮時(shí)間，供應(yīng)商的模型是線性的；⑥零件費(fèi)用相等；⑦零件最大供量應(yīng)該相同。

1.2.2 模型建立

1.2.2.1 生產(chǎn)商的模型（P）

假設(shè)供應(yīng)鏈中有i∈（i＝1，2，…I）個(gè)零件，j∈（j＝1，2，…，J）作業(yè)。在計(jì)劃期t∈（t＝1，2，…T）內(nèi)，按定單滿足客戶產(chǎn)品量和時(shí)間需求。

1）目標(biāo)函數(shù)

2）約束條件

生產(chǎn)力約束

網(wǎng)絡(luò)約束

物質(zhì)平衡約束

訂單交貨約束

整數(shù)約束

3）參數(shù)和變量

參數(shù)：i為零件，j為作業(yè)，t為時(shí)間，I為總零件數(shù)，J為總作業(yè)數(shù)，c為生產(chǎn)力單位成本，Y為單周期最大生產(chǎn)力，Pi為購買單個(gè)零件i的費(fèi)用，hpi為生產(chǎn)商對(duì)零件i的單位庫存成本，Δt為延期時(shí)間，F(xiàn)為延期交付的單位懲罰費(fèi)用（P→C），k為延期交付的單位懲罰費(fèi)用（S→P）。

變量：qi為購買零件i的數(shù)量，Ipi為生產(chǎn)商對(duì)零件i的庫存量，ei為延期交付零件i的數(shù)量（S→P），di為要交付零件i的數(shù)量（S→P），aj為作業(yè)j的生產(chǎn)消耗，Dj為作業(yè)j的生產(chǎn)持續(xù)時(shí)間，Ei為預(yù)期交付時(shí)間（P→C），vij為開始作業(yè)j需要的零件量i。

從上面可以看出：生產(chǎn)商的模型為總成本最小，它包含存儲(chǔ)費(fèi)用、購買費(fèi)用和懲罰費(fèi)用。

1.2.2.2 供應(yīng)商的模型（S）

1）目標(biāo)函數(shù)

2）約束條件

物質(zhì)平衡約束

訂單交貨約束

整數(shù)約束

3）參數(shù)和變量

參數(shù)：pi為購買單個(gè)零件i的 費(fèi)用，hsi為供應(yīng)商對(duì)零件i的庫存成本，k為延期交付的單位懲罰費(fèi)用（S→P），Qi為零件i的最大供應(yīng)量。

變量：di為要交付零件i的數(shù)量（S→P），Isi為供應(yīng)商對(duì)零件i的庫存量，ei為延期交付零件i的數(shù)量（S→P）。

從上面可以看出：供應(yīng)商的模型為總利潤最大，它也包含購買費(fèi)用、存儲(chǔ)費(fèi)用和懲罰費(fèi)用。

2 模擬退火算法及求解

2.1 模擬退火算法的基本流程

根據(jù)模擬退火算法的基本框架，針對(duì)具體問題時(shí)還需要具體的設(shè)計(jì)。模擬退火具有兩層循環(huán)，內(nèi)循環(huán)模擬的是在給定的溫度下系統(tǒng)達(dá)到平衡的過程。在此循環(huán)中，每次從當(dāng)前i的領(lǐng)域中隨機(jī)找出一個(gè)新解j，然后按照Metropolis的準(zhǔn)則概率接受新解。算法中的random（0，1）是指在區(qū)間［0，1］上按均勻分布產(chǎn)生一個(gè)隨機(jī)數(shù)，而所謂的內(nèi)層達(dá)到熱平衡也是一個(gè)籠統(tǒng)的說法，可以定義為循環(huán)一定的代數(shù)，或者基于接受率定義平衡等。算法的外層循環(huán)是一個(gè)降溫的過程，當(dāng)在一個(gè)溫度下達(dá)到平衡后，開始外層的降溫，然后在新的溫度下重新開始內(nèi)循環(huán)。降溫的方法可以根據(jù)具體問題具體設(shè)計(jì)，而且算法流程圖中給出了初始溫度T 也需要算法的使用者根據(jù)具體的問題而制定。

在用模擬退火算法求解最優(yōu)化問題時(shí)，涉及以下幾個(gè)方面的基本要素。

2.1.1 初始溫度

影響模擬退火算法全局搜索性能的重要因素之一是初始溫度t0的設(shè)置。實(shí)驗(yàn)表明，要獲得高質(zhì)量解，初溫就得越大，但花費(fèi)的計(jì)算時(shí)間也將越多。因此，初溫的確定應(yīng)折中考慮優(yōu)化效率和優(yōu)化質(zhì)量，常用方法有以下幾種：

1）以個(gè)狀態(tài)目標(biāo)值的方差為初溫，均勻抽樣一組狀態(tài)；

2）利用經(jīng)驗(yàn)公式給出初溫；

3）隨機(jī)產(chǎn)生一組狀態(tài)，確定出兩兩狀態(tài)間最大目標(biāo)差值｜△max｜，然后根據(jù)差值，利用一定的函數(shù)確定初溫。例如t＝－△max／pr，其中pr為初始接受概率。

2.1.2 領(lǐng)域函數(shù)

領(lǐng)域函數(shù)（狀態(tài)產(chǎn)生函數(shù)）通常有兩部分組成，即候選解產(chǎn)生的概率分布和產(chǎn)生候選解的方式。概率分布可以是均勻分布、指數(shù)分布、正態(tài)分布等，候選解一般采用某一概率密度函數(shù)對(duì)解空間進(jìn)行隨機(jī)采樣獲得。

2.1.3 接受概率

指從一個(gè)可行解Xk向另一個(gè)可行解Xnew的轉(zhuǎn)移概率，通俗的理解是接受一個(gè)新解為當(dāng)前解的概率。與它有關(guān)的是當(dāng)前的溫度參數(shù)tk，隨著溫度的下降而減小。一般采用Metropolis準(zhǔn)則。

2.1.4 冷卻控制

指的是降溫管理表（降溫方式）即從某一較高溫的狀態(tài)t0向較低溫狀態(tài)冷卻。假設(shè)用tk來表示時(shí)刻k的溫度，則經(jīng)典模擬退火算法的降溫方式為

而快速模擬退火算法的降溫方式為

這2 種方式都能使模擬退火算法收斂于全局最小點(diǎn)。

2.1.5 內(nèi)層平衡

內(nèi)層平衡也稱Metropolis抽樣穩(wěn)定準(zhǔn)則，相當(dāng)于由各溫度下產(chǎn)生候選解的數(shù)目決定。以下幾項(xiàng)是常用的抽樣穩(wěn)定準(zhǔn)則：預(yù)先設(shè)定的抽樣數(shù)目，內(nèi)循環(huán)代數(shù)；目標(biāo)值變化較?。ㄟB續(xù)若干步）；目標(biāo)函數(shù)的均值是否穩(wěn)定。

2.1.6 終止條件

常用的算法中止準(zhǔn)則包括以下幾項(xiàng)：外循環(huán)迭代次數(shù)；終止溫度的閥值；連續(xù)若干步保持不變直到算法搜索到最優(yōu)值；檢驗(yàn)系統(tǒng)熵是否穩(wěn)定。

2.2 模擬退火算法的描述和實(shí)現(xiàn)

2.2.1 一般過程描述

模擬退火的一般過程可以描述為：

步驟1 給定初溫Tk＝T0，隨機(jī)產(chǎn)生初始生產(chǎn)順序向量（di，ei，I0p）＝（d0，e0，Ip0），計(jì)算目標(biāo)值Cp。令k＝0。

步驟2 如果停止準(zhǔn)則不滿足，重復(fù)以下過程。

步驟2.1 執(zhí)行以下過程Lk次：

步驟2.1.1 從狀態(tài)i的領(lǐng)域解中隨機(jī)選取新狀態(tài)j；

步驟2.1.2 令Δ＝f（j）－f（i）；

步驟2.1.3 若△＜＝0，則令i＝j(luò)，否則以概率exp（－△／tk）令i＝j(luò)。

步驟2.2 退溫：令k＝k＋1，計(jì)算tk＝d（tk），同時(shí)按規(guī)則更新Lk。

步驟3 輸出i。

2.2.2 參數(shù)設(shè)定

根據(jù)模擬退火算法的演算流程，表1是對(duì)模擬退火算法的參數(shù)設(shè)定。

表1 模擬退火算法的參數(shù)設(shè)定

3 實(shí) 例

為了說明該算法的有效性及可靠性，而且能夠直觀反映出一些模擬退火特征，實(shí)驗(yàn)結(jié)果如表2～表4所示。

假設(shè)整個(gè)供應(yīng)鏈中有7個(gè)作業(yè)，7個(gè)訂單，其中一個(gè)訂單對(duì)應(yīng)一個(gè)作業(yè)。

表2 訂單數(shù)據(jù)和作業(yè)在第一階段的生產(chǎn)消耗

表3 生廠商的數(shù)據(jù)

表4 供應(yīng)商的數(shù)據(jù)

4 結(jié)束語

在本文中研究了一個(gè)供應(yīng)商和制造商的供應(yīng)鏈中的分級(jí)協(xié)調(diào)機(jī)制問題。根據(jù)其模型，運(yùn)用模擬退火算法，提出求解該問題的一種求解方法。通過運(yùn)用c＋＋對(duì)該問題進(jìn)行了求解，得到了接近最優(yōu)解的生產(chǎn)總成本最小，供應(yīng)總利潤最大的解，最后的算例證明了針對(duì)供應(yīng)鏈角色，模擬退火算法是一種高效算法。但是，兩個(gè)模型僅僅提供了解決在確定條件下供應(yīng)商和生產(chǎn)商之間關(guān)系的框架，為了解決更廣泛的問題，并求得更精確的解，還需對(duì)模型添加相應(yīng)的決策變量和約束條件，或考慮有關(guān)模糊條件下的建模。

［1］林勇，馬士華.供應(yīng)鏈管理［M］.北京：高等教育出版社，2003.

［2］蔡連僑，陳劍.供應(yīng)鏈建模與優(yōu)化［J］.系統(tǒng)工程理論與實(shí)踐，2001（6）：26－33.

［3］邢文訓(xùn)，謝金星.現(xiàn)代優(yōu)化計(jì)算方法［M］.北京：清華大學(xué)出版社，2005.

［4］黃平，孟永鋼.最優(yōu)化理論與方法［M］.北京：清華大學(xué)出版社，2009.

［5］汪定偉，王俊偉，王洪峰，張瑞友，郭哲.智能優(yōu)化方法［M］.北京：高等教育出版社，2007.

［6］何利英.面向客戶的供應(yīng)鏈優(yōu)化模型研究［D］.成都：西南交通大學(xué)，2003.

［7］孫文瑜，袁亞湘.最優(yōu)化理論與方法［M］.蘭州：科學(xué)出版社，1997.

［8］張文修，梁怡.遺傳算法的數(shù)學(xué)基礎(chǔ)［M］.西安：西安交通大學(xué)出版社，2003.