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

李 敏 （上海理工大學(xué) 管理學(xué)院，上海 200093）

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

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

1 模型描述

為了比較分散決策和集成決策之間的成本費(fèi)用上的差異，將生產(chǎn)、采購(gòu)集成模型分解成獨(dú)立的多時(shí)間段的資源受限的生產(chǎn)計(jì)劃決策模型和考慮價(jià)格折扣和運(yùn)輸成本的采購(gòu)計(jì)劃決策模型。

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

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

表1 符號(hào)的定義

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

1.2 模型求解。基于量子粒子群算法求解生產(chǎn)、采購(gòu)集成決策計(jì)劃問題的具體流程如下：

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

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

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

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

（5）量子進(jìn)化

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

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

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

2 小 結(jié)

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

[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].計(jì)算機(jī)學(xué)報(bào)，2007,30(5):748-755.

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

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

[5] 鐘艷花，余超凡.0/1背包問題的量子算法[J].計(jì)算機(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].計(jì)算機(jī)應(yīng)用，2007,27(2):285-288.

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

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

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