基于量子粒子群算法求解供應(yīng)鏈集成計劃問題

李 敏 （上海理工大學 管理學院，上海 200093）

隨著科學技術(shù)的發(fā)展，經(jīng)濟一體化趨勢越來越明顯，產(chǎn)品生命周期越來越短，對訂單的響應(yīng)速度越來越快，客戶對產(chǎn)品和服務(wù)的交付時間和質(zhì)量期望越來越高。企業(yè)無法憑借自身力量在激烈的競爭中取得優(yōu)勢，這使得他們不得不拋棄以前的單打獨斗的競爭思想，開始考慮企業(yè)內(nèi)部業(yè)務(wù)流程重組或者是與上下游企業(yè)之間的業(yè)務(wù)集成，與不同的企業(yè)為了共同的市場利益而結(jié)成戰(zhàn)略聯(lián)盟。

PSO（Particle Swarm Optimization）粒子群算法[1]是繼遺傳算法、蟻群算法等進化算法之后出現(xiàn)的一種新的智能優(yōu)化算法，它具有控制參數(shù)少，編碼簡單、計算速度快、容易實現(xiàn)等特點。目前量子優(yōu)化算法在求解經(jīng)典組合優(yōu)化問題上的應(yīng)用較為廣泛，如TSP問題[2-4]，0/1背包問題[5]，單目標和多目標流水車間調(diào)度問題[6]等。同時在解決現(xiàn)實生活中的各種問題，如路由問題[7]，投資組合優(yōu)化[8]，圖像分割[9]，易逝品多目標定價問題[10]等也表現(xiàn)出良好的性能。

1 模型描述

為了比較分散決策和集成決策之間的成本費用上的差異，將生產(chǎn)、采購集成模型分解成獨立的多時間段的資源受限的生產(chǎn)計劃決策模型和考慮價格折扣和運輸成本的采購計劃決策模型。

其中，每個時間段生產(chǎn)計劃的批量決策問題只需要考慮計劃周期內(nèi)每個時間段外部需求和自身能力資源限制即可，見下公式 （1）。采購計劃模型是在已求出的優(yōu)化生產(chǎn)計劃批量Qmt的前提下，考慮價格折扣和庫存成本以及運輸成本，在最小化這些成本的基礎(chǔ)上來制定相應(yīng)的原材料采購批量計劃，見下公式 （9）。

1.1 模型建立。首先根據(jù)要求先定義模型中的變量，如表1所示。

表1 符號的定義

約束式 （2）和 （10）表示工廠產(chǎn)品和原材料采購、生產(chǎn)、需求及庫存的動態(tài)平衡方程。約束式 （3）表示工廠生產(chǎn)的最大能力資源限制。約束式 （4）表示原材料的采購數(shù)量大于0時，即決定采購時，才存在相應(yīng)的訂貨調(diào)整費用。約束式 （5）和（13）表示Xmt、Ymt是0或1的調(diào)整變量。約束式 （6）和 （7）表示原材料的生產(chǎn)數(shù)量、采購數(shù)量都是非負的。約束式 （8）和（16）表示產(chǎn)品和原材料在計劃周期的開始時間段和結(jié)束時間段的庫存水平是0。約束式 （11）表示當生產(chǎn)數(shù)量大于0時，即發(fā)生生產(chǎn)時，才存在相應(yīng)的生產(chǎn)調(diào)整費用。約束式 （12）表示根據(jù)采購批量的不同，享受不同的價格折扣下的采購成本計算公式。約束式 （14）、 （15）表示產(chǎn)品的生產(chǎn)數(shù)量和庫存水平都是非負的。

1.2 模型求解?；诹孔恿Ｗ尤核惴ㄇ蠼馍a(chǎn)、采購集成決策計劃問題的具體流程如下：

（1）初始化量子粒子群算法的參數(shù)，包括確定種群的規(guī)模N，慣性權(quán)重w，加速系數(shù)c1和c2，初始速度v［N］，進化代數(shù)k。

（2）量子染色體的初始化，設(shè)置初始角度θ，一般設(shè)置為45°。

（3）隨機觀察產(chǎn)生求解問題的一個解，根據(jù)角度，產(chǎn)生Qk，Qk表示第k代粒子群量子比特對應(yīng)的概率矩陣。Qk通過隨機觀察生成Pk，具體操作過程如下：隨機產(chǎn)生一個［0,1 ］之間的隨機數(shù)，若它大于Qk，則對應(yīng)的Pk粒子的量子比特位取值為1，否則取值為0。

（4）計算每個粒子的適應(yīng)值，根據(jù)生成的Pk產(chǎn)生n個粒子，并計算出該狀態(tài)下各個粒子的適應(yīng)值。

（5）量子進化

（6）循環(huán)迭代，直到滿足終止條件。

1.3 仿真實驗。仿真實驗求解結(jié)果如表2所示，可以看出集成決策生產(chǎn)、采購計劃能夠有效降低供應(yīng)鏈的總成本。最優(yōu)解的迭代曲線如圖1所示。

表2 集成決策和分散決策求解結(jié)果比較

2 小 結(jié)

本章構(gòu)建了多周期、多產(chǎn)品、單工廠的生產(chǎn)和采購集成計劃模型，將原材料的采購成本和運輸成本考慮到優(yōu)化的模型中去，以生產(chǎn)商為中心，統(tǒng)一制定采購計劃和生產(chǎn)計劃，并設(shè)計了用于求解該問題的量子粒子群算法方案。分別建立了分散決策下的生產(chǎn)計劃模型和原材料采購計劃模型，并對模型進行求解，得到獨立計劃時各個時間段生產(chǎn)批量和原材料的采購批量。仿真實驗的結(jié)果表明：量子粒子群算法在求解供應(yīng)鏈集成計劃上的有效性，集成化決策比分散決策能夠有效地降低供應(yīng)鏈的總費用。

[1] Kennedy J,Eberhart RC.Particle a warm optimization[J].Proceedings of IEEE International Conference on Neural Networks,1995(17):1942-1948.

[2] 王宇平，李英華.求解TSP的量子遺傳算法[J].計算機學報，2007,30(5):748-755.

[3] 武妍，包建軍.一種新的求解TSP的混合量子進化算法[J].計算機應(yīng)用，2006,26(10):2433-2436.

[4] 楊麗，李平，秦亞玲.改進的量子進化算法及其在TSP問題中的應(yīng)用[J].信息與電子工程，2006,4(6):412-416.

[5] 鐘艷花，余超凡.0/1背包問題的量子算法[J].計算機信息，2006,22(12-13):176,273-274.

[6] Wang L,Wu H,Tang F,et al.A hybrid quantum-inspired genetic algorithm for flow shop scheduling[J].Lecture Notes in Computer Science,2005(1):636-644.

[7] 秦潔，須文波.基于QPSO的QoS組播路由算法[J].計算機應(yīng)用，2007,27(2):285-288.

[8] 須文波，江家寶，孫俊.基于QPSO算法的多階段投資組合優(yōu)化[J].計算機應(yīng)用，2006,26(7):1682-1685.

[9] 龍海俠，須文波，孫俊.基于量子行為的微粒群優(yōu)化算法的圖像分割[J].計算機工程與應(yīng)用，2006,28:54-55.

[10] 陸海燕，須文波.量子粒子群算法在易逝品多目標定價中的應(yīng)用[J].計算機工程與應(yīng)用，2007,43(19):237-239.