基于MILP模型和QPSO算法的綠色物流調(diào)度方法*

劉　嵐，　蘭小毅

(西安工業(yè)大學(xué) 經(jīng)管學(xué)院，陜西 西安 710021)

為了應(yīng)對競爭激烈的全球市場，廠家選擇一個(gè)有效的供應(yīng)鏈網(wǎng)絡(luò)(supply chain network，SCN)來降低庫存成本變得尤為重要.供應(yīng)鏈?zhǔn)且?guī)劃、實(shí)施和控制貨物或服務(wù)的流程[1].準(zhǔn)時(shí)制(just-in-time，JIT)是其中一種供應(yīng)鏈策略，它通過頻繁的生產(chǎn)，大大減少了工作流程中的庫存，從而提高了企業(yè)的生產(chǎn)效率[2].然而，頻繁進(jìn)行小規(guī)模生產(chǎn)，對運(yùn)輸需求的響應(yīng)能力要求更高，會(huì)導(dǎo)致環(huán)境污染和運(yùn)輸成本上升等問題.在準(zhǔn)時(shí)制的基礎(chǔ)上，[3]提出了一種多準(zhǔn)則決策模型，實(shí)現(xiàn)產(chǎn)品的生產(chǎn)、質(zhì)量、價(jià)格、成本、設(shè)備、技術(shù)和交貨都能滿足客戶需求和出口質(zhì)量標(biāo)準(zhǔn).[4]提出了一種新的準(zhǔn)時(shí)制決策，研究結(jié)果表明準(zhǔn)時(shí)制對豐田工廠的銷售、設(shè)計(jì)、改進(jìn)和生產(chǎn)產(chǎn)生了積極的影響.[5]在雙層非線性優(yōu)化模型的基礎(chǔ)上提出了決策支持系統(tǒng).為解決準(zhǔn)時(shí)配送問題，[6]在三級分銷網(wǎng)絡(luò)的基礎(chǔ)上開發(fā)了多目標(biāo)數(shù)學(xué)模型.此前傳統(tǒng)的數(shù)學(xué)建模并未涉及對環(huán)境的影響.考慮到供應(yīng)鏈管理相關(guān)過程對環(huán)境的影響，在傳統(tǒng)的供應(yīng)鏈管理中加入“綠色”概念.物流作為與SCM相關(guān)的主要組成部分，直接影響環(huán)境污染源——溫室氣體排放.盡管對綠色物流的研究在過去有所增加，但目前實(shí)際物流中很少遵守環(huán)境約束.從綠色的視角來看，模糊的多目標(biāo)化技術(shù)是解決綠色供應(yīng)鏈網(wǎng)絡(luò)的主要方法.通常，所提出的數(shù)學(xué)模型目的是在兩個(gè)相互沖突的目標(biāo)之間進(jìn)行權(quán)衡，即將二氧化碳當(dāng)量作為一個(gè)指標(biāo)來量化物流活動(dòng)對環(huán)境的影響，以總成本最小化和環(huán)境影響最小化為目標(biāo)，實(shí)現(xiàn)一個(gè)優(yōu)化的整合前向和反向閉環(huán)的供應(yīng)鏈網(wǎng)絡(luò)[7].經(jīng)典的生產(chǎn)和分配模型關(guān)注的是成本最小化，這取決于生產(chǎn)的約束.考慮到綠色物流的目標(biāo)和約束，將產(chǎn)生新的組合優(yōu)化模型.為此，本文開發(fā)了一個(gè)多目標(biāo)的混合整數(shù)線性規(guī)劃模型(mixed integer linear programming, MILP)來構(gòu)建物流調(diào)度網(wǎng)絡(luò)模型，包含了多個(gè)制造工廠、配送中心、零售商和產(chǎn)品屬性.該模型的目標(biāo)是盡量減少在配送中心和經(jīng)銷商處的交貨時(shí)間，以及最小化碳排放.為了求解該MILP模型，本文采用了一種量子粒子群優(yōu)化(quantum particle swarm optimization,QPSO)算法，以此快速地獲得最優(yōu)調(diào)度方案.

1　構(gòu)建物流調(diào)度的MILP模型

1.1　物流網(wǎng)絡(luò)模型

物流網(wǎng)絡(luò)模型分為3個(gè)級：第1級為制造商，第2級為分銷商，第3級為經(jīng)銷商[8].在開發(fā)物流調(diào)度模型時(shí)，建立了以下假設(shè)：(1) 模型是專為多個(gè)制造商、分銷商、經(jīng)銷商、產(chǎn)品進(jìn)行規(guī)劃調(diào)整的；(2) 需求量與初期的需求有關(guān)；(3) 貨物、分銷商、經(jīng)銷商和供應(yīng)商的位置是固定的；(4) 制造商、分銷商和經(jīng)銷商的生產(chǎn)銷售能力是已知的；(5) 各期的持續(xù)時(shí)間等于生產(chǎn)時(shí)間的總和；(6) 在配送的開始或結(jié)束，經(jīng)銷商沒有庫存；(7) 在交付給分銷商之前，產(chǎn)品暫時(shí)存放于經(jīng)銷商；(8) 運(yùn)輸方式與各類型固定容量的卡車相關(guān)；(9) 假設(shè)所有產(chǎn)品品質(zhì)完全合格，也就是說在系統(tǒng)里沒有報(bào)廢、返工或退回.另外，模型中的一些限制約束：(1) 在執(zhí)行期間所有的需求必須被滿足；(2) 生產(chǎn)時(shí)間被限制；(3) 每個(gè)合格產(chǎn)品的庫存能力有限；(4) 制造商、經(jīng)銷商和分銷商的能力有限.模型的參數(shù)和決策變量如表1所示.

表1　模型中的參數(shù)及含義

1.2　構(gòu)建MILP模型

物流調(diào)度的MILP模型包含目標(biāo)函數(shù)和約束條件，分別表述如下.

第一個(gè)目標(biāo)函數(shù)，即在配送中心和經(jīng)銷商之間，最小化產(chǎn)品交付時(shí)間的表達(dá)式為：

第二目標(biāo)函數(shù)，即在整個(gè)物流網(wǎng)絡(luò)中，總碳排放量最小化的表達(dá)式為：

這里設(shè)定了2個(gè)目標(biāo)函數(shù)，其中總碳排放量最小化將導(dǎo)致交貨期增加，而交付時(shí)間最小化會(huì)增加運(yùn)輸次數(shù)，從而對環(huán)境造成不利影響.用戶可根據(jù)具體需求設(shè)定兩個(gè)目標(biāo)函數(shù)的權(quán)重構(gòu)成最終目標(biāo)函數(shù)，此時(shí)需要對minZ1和minZ2進(jìn)行歸一化，總目標(biāo)函數(shù)表示如下：

O=k·Norm(minZ1)+(1-k)·Norm(minZ2),

式中Norm(minZ1)表示minZ1的歸一化，即實(shí)際交付時(shí)間與允許最大交付時(shí)間的比值.同樣，Norm(minZ2)為實(shí)際碳排放量與最大排放量的比值.

碳排放量的計(jì)算采用廣泛認(rèn)可的溫室氣體協(xié)議方法.每個(gè)產(chǎn)品的等效碳排放量可以作為一個(gè)線性函數(shù)來計(jì)算，它取決于運(yùn)載車輛行駛距離(公里)和碳排放(每公里二氧化碳排放量).我們將這個(gè)碳排放模型應(yīng)用于給定的供應(yīng)模式，而碳排放與運(yùn)輸產(chǎn)品的數(shù)量成比例.

在分銷商處的庫存表示為(注意在每個(gè)分銷商的計(jì)劃開始和結(jié)束時(shí)沒有庫存)：

在規(guī)劃期間內(nèi)，向分銷商運(yùn)輸貨物的總輸入和輸出之間的平衡關(guān)系為：

在t時(shí)間段內(nèi)，總運(yùn)輸量沒有超過產(chǎn)品生產(chǎn)能力的關(guān)系表示為：αijpt+βjkpt≤χipt.

確保交付給配送商和經(jīng)銷商的價(jià)值為非負(fù)數(shù)表示為：αijpt,βjkpt,χipt≥0.

2　基于QPSO算法求解MILP模型

對于MILP模型的求解，通常采用數(shù)學(xué)規(guī)劃軟件GAMS中的CPLEX模塊[9].由于目前各種智能優(yōu)化算法的發(fā)展，出現(xiàn)了一些快速且高精度的優(yōu)化算法，為此本文采用了一種QPSO算法來求解物流調(diào)度的MILP模型.近些年，產(chǎn)生了一種新的進(jìn)化算法，稱為量子進(jìn)化算法(QEA)，在尋優(yōu)方面優(yōu)于遺傳算法.由于傳統(tǒng)QEA中通過量子旋轉(zhuǎn)門來更新量子角增量，操作復(fù)雜且更新角度固定，使其容易陷入局部最優(yōu).為此，學(xué)者引入了PSO算法中的位置更新公式替代QEA中的量子旋轉(zhuǎn)門來更新角增量，形成量子粒子群優(yōu)化(Quantum-PSO，QPSO)算法[10].

QPSO使用PSO的群智能概念，將群體中的所有多量子比特視為智能種群，稱為量子群.首先，QPSO找到局部最佳量子角，并從局部最佳量子角中找到全局最佳量子角.然后根據(jù)這些值，用量子角更新公式更新量子角.基于QEA的QPSO步驟如下：

(3) 計(jì)算P(t)的適應(yīng)度，其通過適應(yīng)度函數(shù)F，對每個(gè)二進(jìn)制解P(t)進(jìn)行評估，確定本次迭代中的個(gè)體最佳和全局最佳.

(4) 使用以下PSO位置更新公式替換傳統(tǒng)“量子門更新Q(t)”步驟，量子角度更新公式為：

3　實(shí)驗(yàn)及分析

3.1　實(shí)驗(yàn)設(shè)置

3.2　性能分析

將傳統(tǒng)QEA與本文應(yīng)用的QPSO對求解物流調(diào)度MILP模型的能力進(jìn)行比較.設(shè)定一個(gè)物流調(diào)度方案的總目標(biāo)函數(shù)O，其中對交付時(shí)間和碳排放量這兩個(gè)目標(biāo)賦予相同的權(quán)重，即系數(shù)k設(shè)置為0.5.在不同迭代次數(shù)下的收斂結(jié)果如圖1所示.QPSO的收斂速度較快，在200次迭代之后基本收斂到最優(yōu)解，而傳統(tǒng)QEA則需要大約320次才能收斂，且最終解的質(zhì)量略微低于QPSO.這是因?yàn)镼PSO采用了PSO位置更新方程和動(dòng)態(tài)慣性權(quán)重，有效提高了收斂速度和收斂精度.

將本文方法與[6]提出的物流調(diào)度優(yōu)化方法進(jìn)行比較.[6]方法中的物流模型與本文方法一樣，都采用三級結(jié)構(gòu)，但該方法只考慮一個(gè)目標(biāo).為了公平比較，本文設(shè)定的目標(biāo)函數(shù)也作為文獻(xiàn)[6]方法的目標(biāo).

實(shí)驗(yàn)中設(shè)定權(quán)重系數(shù)k為[0.4，0.6]之間不同的值，以此構(gòu)建不同的總目標(biāo)函數(shù)O.統(tǒng)計(jì)各種方法獲得的最終調(diào)度方案的目標(biāo)函數(shù)值、歸一化交付時(shí)間Norm(minZ1)和歸一化碳排放量Norm(minZ2)，結(jié)果如表2所示.隨著k值的增加，Norm(minZ1)值隨之減低，而Norm(minZ2)值隨之增加.這是因?yàn)閗值增加，總目標(biāo)函數(shù)中對Norm(minZ2)的考慮比重降低，而更看重Norm(minZ1)值，所以優(yōu)化模型優(yōu)先考慮降低Norm(minZ1)值.從對比結(jié)果來看，在不同的k值下，本文方法獲得的結(jié)果都優(yōu)于[6]方法.這是因?yàn)楸疚膶⑽锪髡{(diào)度問題科學(xué)建模為一個(gè)MILP模型，并通過智能算法進(jìn)行求解，獲得了最優(yōu)的調(diào)度方案.

表2　物流調(diào)度方案的性能結(jié)果

4　結(jié)　論

基于MILP模型和QPSO算法提出一種求解物流網(wǎng)絡(luò)中物流調(diào)度方案的方法，以優(yōu)化供應(yīng)鏈時(shí)效性和降低對環(huán)境的影響.具體目標(biāo)是優(yōu)化從制造商到配送中心、從配送中心到經(jīng)銷商的交貨期，并盡量減少整個(gè)物流系統(tǒng)中的碳排放量.為了獲得有效調(diào)度方案，將調(diào)度問題構(gòu)建為一個(gè)MILP模型，并利用一種快速智能優(yōu)化算法QPSO來求解該模型.在一個(gè)汽車銷售物流網(wǎng)絡(luò)上的實(shí)驗(yàn)取得了較好的結(jié)果.

[1]尹小悅, 王娟, 陳昭玖. 基于模糊評價(jià)的綠色供應(yīng)鏈管理可行性評估方案[J]. 湘潭大學(xué)自然科學(xué)學(xué)報(bào), 2016, 38(4):116-120.

[2]張鑫磊. 準(zhǔn)時(shí)制生產(chǎn)方式視角下的物流管理研究[J]. 物流工程與管理, 2016, 38(10):47-48.

[3]WU K J, TSENG M L, CHIU A S F, et al. Achieving competitive advantage through supply chain agility under uncertainty: A novel multi-criteria decision-making structure[J]. International Journal of Production Economics, 2016, 19(4):132-137.

[4]覃愛民, 夏松. 基于JIT的裝配式建筑FDC階段供應(yīng)鏈集成管理研究[J]. 信陽師范學(xué)院學(xué)報(bào):自然科學(xué)版, 2017, 30(3):489-493.

[5]MEMARI A, RAHIM A R B A, AHMAD R B. Production planning and inventory control in automotive supply chain networks[C]// International Conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems. Springer International Publishing, 2014:430-439.

[6]EREN ?zceylan, TURAN Paksoy. Fuzzy multi-objective linear programming approach for optimising a closed-loop supply chain network[J]. International Journal of Production Research, 2013, 51(8):2443-2461.

[7]RYU J H, HAN J H, LEE I B. Development an optimization model for green supply chains: integration of CO2disposal and renewable energy supply[J]. Computer Aided Chemical Engineering, 2012, 30(3):317-321.

[8]秦小輝. 基于碳交易的已存供應(yīng)鏈物流網(wǎng)絡(luò)優(yōu)化研究[J]. 計(jì)算機(jī)應(yīng)用研究, 2017, 34(5):1374-1378.

[9]依俊楠, 劉攀, 徐小偉,等. 基于混合整數(shù)線性規(guī)劃模型的水電站日優(yōu)化調(diào)度研究[J]. 水電能源科學(xué), 2011, 29(7):33-35.

[10]XIN J, XIAO F H. A quantum-PSO-based SVM algorithm for fund price prediction[J]. Journal of Convergence Information Technology, 2012, 7(3):267-273.