何珮洋, 李昆鵬, 李文莉

(1.華北水利水電大學(xué) 管理與經(jīng)濟(jì)學(xué)院,河南 鄭州 450046; 2.華中科技大學(xué) 管理學(xué)院,湖北 武漢 430074; 3.武漢紡織大學(xué) 管理學(xué)院,湖北 武漢 430299)

0 引言

作為實施制造強(qiáng)國戰(zhàn)略的第一個十年行動綱領(lǐng)，《中國制造2025》重點提到了智能制造，對快速生產(chǎn)和定制化制造提出了更高要求。隨著市場競爭的日益激烈，提升供應(yīng)鏈響應(yīng)速度已成為當(dāng)前備件制造企業(yè)贏得客戶的關(guān)鍵因素。為了增強(qiáng)備件制造企業(yè)的供應(yīng)鏈競爭力，智能制造和即時配送的高效協(xié)同成為必然趨勢。馬士華等[1]指出在這種趨勢下，未來的工廠將直接建設(shè)在物流中心，當(dāng)產(chǎn)品生產(chǎn)完成后立即通過物流中心配送至客戶，這種模式可大大提高供應(yīng)鏈整體響應(yīng)速度。作為世界上最大的快遞承運商與包裹遞送公司，UPS在智能制造與即時配送領(lǐng)域做了積極嘗試，將3D打印生產(chǎn)與自身物流配送相結(jié)合，打造定制化生產(chǎn)和即時配送的一體化服務(wù)。在智能制造和即時配送高效協(xié)同背景下，采用3D打印技術(shù)實現(xiàn)備件的本地生產(chǎn)成為現(xiàn)實，越來越多的公司開始將生產(chǎn)中心轉(zhuǎn)移到離客戶更近的位置[2]。備件制造企業(yè)通過引進(jìn)大型工業(yè)級3D打印設(shè)備，采用“隨時需要隨時生產(chǎn)”的新型備件供應(yīng)模式，滿足客戶對備件的個性化需求和高時效性要求。智能制造環(huán)境下的備件供應(yīng)鏈具有去庫存、選址靈活、響應(yīng)速度快等特點，可有效解決傳統(tǒng)備件制造模式下庫存壓力大、生產(chǎn)成本高、供貨周期長等棘手問題。在此背景下，本文以提升基于3D打印技術(shù)的備件供應(yīng)鏈運作效率為目標(biāo)，深入研究該新型場景下的備件供應(yīng)鏈運作問題。備件制造企業(yè)通過線上獲得客戶訂單后，根據(jù)客戶的訂單需求、地理位置、生產(chǎn)資源及運輸資源，綜合決策各訂單對應(yīng)備件的生產(chǎn)順序、每個訂單分配至哪輛車進(jìn)行配送、每輛車的出發(fā)時間及配送路線。

梳理相關(guān)文獻(xiàn)發(fā)現(xiàn)，由于生產(chǎn)與運輸協(xié)同調(diào)度問題的高復(fù)雜性，大多數(shù)研究設(shè)計啟發(fā)式算法進(jìn)行求解。在極少數(shù)使用精確算法的研究中，算例求解規(guī)模又十分有限。如Chang等[14]設(shè)計分支定價算法對并行機(jī)生產(chǎn)和多車運輸?shù)膮f(xié)同問題進(jìn)行求解，算例最大規(guī)模為5個客戶。生產(chǎn)與運輸協(xié)同調(diào)度領(lǐng)域亟需豐富對求解效率更高的精確算法的研究。因此，本文以最小化所有客戶等待時間為目標(biāo)，研究智能制造環(huán)境下的備件生產(chǎn)與運輸協(xié)同調(diào)度問題。建立混合整數(shù)規(guī)劃模型，并提出新的集合覆蓋模型，該模型能夠獲得高質(zhì)量下界；根據(jù)問題特點提出協(xié)同調(diào)度的最優(yōu)解性質(zhì)，以便更有效地獲得最優(yōu)解；使用改進(jìn)的分支定價算法對問題進(jìn)行求解，并設(shè)計新的加速策略和分支策略，使得算例求解規(guī)模更大。本文改進(jìn)的分支定價算法求解技巧可以為其他相關(guān)研究提供借鑒，進(jìn)一步豐富了現(xiàn)有生產(chǎn)與運輸協(xié)同調(diào)度問題的模型和算法研究。

1 問題描述與數(shù)學(xué)模型

1.1 問題描述

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

(1)

(2)

(3)

(4)

(5)

(6)

(7)

Ci+Tnj-Cj≤(1-zij)M,?i∈V,j∈N

(8)

C0=0

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

xijk∈{0,1},?i∈V,j∈N,k∈W

(17)

yjk∈{0,1},?j∈N,k∈W

(18)

zij∈{0,1},?i∈V,j∈N

(19)

目標(biāo)函數(shù)(1)表示最小化所有客戶的總等待時間；式(2)和(3)表示每個客戶只能被訪問一次；式(4)為流量平衡約束；式(5)(6)確保每輛車從工廠出發(fā)，最終又回到工廠且只被使用一次；式(7)為車容約束；式(8)為連續(xù)生產(chǎn)兩個訂單的生產(chǎn)完成時間需要滿足的約束；式(9)表示機(jī)器從0時刻開始工作；式(10)、(11)和(12)表示訂單生產(chǎn)需要滿足的約束；式(13)、(14)為車輛服務(wù)客戶的先后順序約束；式(15)表示每輛車只有在其配送的訂單全部生產(chǎn)完成后才能從工廠出發(fā)；式(16)表示若一輛車服務(wù)某個客戶，則該車需要裝載該客戶對應(yīng)的訂單；式(17)～(19)為整數(shù)約束。優(yōu)化軟件CPLEX可以直接對該模型進(jìn)行求解，但通過初步試驗發(fā)現(xiàn)CPLEX的求解能力和效率有限。隨著算例規(guī)模的增大，使用CPLEX求解器在一定時間內(nèi)不能得到最優(yōu)解，甚至無法獲得較好的下界。

1.3 集合覆蓋模型

為求解上述混合整數(shù)規(guī)劃模型，根據(jù)Dantzig-Wolfe分解原理[19]，將其分解為一個結(jié)構(gòu)較為簡單但變量數(shù)目更大的線性主問題(Linear Master Problem，LMP)和一個具有資源約束的最短基本路徑問題(Elementary Shortest Path Problem With Resource Constraints，ESPPRC)。

1.3.1 線性主問題模型

(20)

(21)

(22)

(23)

(24)

xr∈{0,1},r∈Ω

(25)

式(20)為目標(biāo)函數(shù)；式(21)表示每個客戶至少被訪問一次；式(22)表示每個產(chǎn)品至多被一輛車配送；式(23)表示最優(yōu)解中至多選擇一條加工完成第p個備件的時間節(jié)點出發(fā)的路徑，體現(xiàn)了對生產(chǎn)階段和運輸階段的協(xié)同約束；式(24)是對車輛數(shù)的限制；式(25)為0-1變量約束。顯而易見，即使對于小規(guī)模算例，LMP涉及的可行路徑數(shù)量就十分龐大。因此，本文使用一種迭代方法——列生成算法，為限制線性主問題(Restricted Linear Master Problem,RLMP)的松弛問題迭代地加入可行列。

1.3.2 滿足資源約束的最短基本路徑問題

(26)

?i∈V,j∈N,p∈P

(27)

(28)

(29)

(30)

(31)

(32)

(33)

目標(biāo)函數(shù)(28)表示被選中的弧組成的路徑使得檢驗數(shù)值最??；式(29)為車容約束；式(30)表示只有產(chǎn)成品才能被配送，式(31)表示車輛在時刻Tp從3D打印中心出發(fā)；式(32)為消除子回路約束；式(33)為0-1變量約束。

2 最優(yōu)解性質(zhì)推導(dǎo)

深入分析問題特性后提出最優(yōu)解滿足的性質(zhì)。

性質(zhì)1在以所有客戶總等待時間最小為目標(biāo)的單機(jī)生產(chǎn)與多車運輸協(xié)同調(diào)度問題中，批次的生產(chǎn)順序為R1≤R2≤…≤Rb的決策優(yōu)于其他生產(chǎn)順序決策。

證明只需證明當(dāng)CustNb一定時，目標(biāo)函數(shù)與JobNb成正比；當(dāng)JobNb一定時，目標(biāo)函數(shù)與CustNb成反比。假設(shè)存在m個批次l1,l2,…,lm滿足CustNl1=…=CustNlm，JobNl1≤…≤JobNlm。當(dāng)批次的生產(chǎn)順序為l1,l2,…,lm時，目標(biāo)函數(shù)C1=(T*JobN1*CustNl1+Disl1)+(T*(JobNl1+JobNl2)*CistNl2+Disl2)+…+(T*(JobNl1+JobNl2+…+JobNlm)*CustNlm+Dislm)=TCustNl1*(mJobNl1+(m-1)JobNl2+…+JobNlm)+(Disl1+Disl2+…+Dislm),其中Dislm(1≤w≤m)為批次lw對應(yīng)的目標(biāo)函數(shù)中運輸階段相應(yīng)的總時間花費。當(dāng)批次的生產(chǎn)順序為除了l1,l2,…,lm外的任一順序如lm,l2,…,lm-1,l1時，目標(biāo)函數(shù)，C2=TCustNl1*(mJobNlm+(m-1)JobNl2+…+JobNl1)+(Disl1+Disl2+…+Dislm)顯然有C1≤C2，因此當(dāng)CusNb一定時，目標(biāo)函數(shù)與JobNb成正比。同樣地，假設(shè)存在m個批次l1,l2,…,lm滿足CustNl1≤…≤CustNlm，JobNl1=…JobNlm。當(dāng)批次的生產(chǎn)順序為l1,l2,…,lm時，目標(biāo)函數(shù)C3=TJobNl1*(CustNl1+2CustNl2+…+mCustNlm)+(Disl1+Disl2+…+Dislm)，當(dāng)批次的生產(chǎn)順序為除了l1,l2,…,lm外的任一順序如lm,l2,…,lm-1,l1時目標(biāo)函數(shù)C4=TJobNl1*(CustNlm+2CustNl2+…+mCustNl1)+(Disl1+Disl2+…+Dislm)，顯然有C3≥C4，因此當(dāng)JobNb一定時，目標(biāo)函數(shù)與CustNb成反比。

3 分支定價算法

3.1 分支定價算法框架

Desrochers等[20]提出的分支定價算法是分支定界算法的一種拓展，它使用列生成在分支的每一個節(jié)點處求取下界。在本文改進(jìn)的列生成算法中，每個列所屬的集合Rp(p∈P)體現(xiàn)了該列對應(yīng)車輛能夠進(jìn)行配送的訂單以及車輛的出發(fā)時間；每個列中的點序列既包含了客戶對應(yīng)訂單的生產(chǎn)順序也體現(xiàn)了訂單的配送順序。該算法從包含部分列的RLMP出發(fā)，根據(jù)當(dāng)前求解RLMP得到的對偶值，通過標(biāo)簽算法求解滿足資源約束的最短基本路徑問題。如果能夠找到檢驗數(shù)值小于0的列，則將該列添加到RLMP中進(jìn)行重新計算。不斷迭代，直至沒有檢驗數(shù)值小于0的路徑產(chǎn)生，此時得到松弛主問題的最優(yōu)解。若當(dāng)前解為整數(shù)解，則當(dāng)前解即為原問題的最優(yōu)解；否則，利用分支策略對當(dāng)前非整數(shù)解進(jìn)行分支，求得最優(yōu)整數(shù)解。

3.2 初始解和上界

通過構(gòu)造簡單的啟發(fā)式算法求得一個可行解，將其作為RLMP的初始上界，并將構(gòu)成該解的路徑作為RLMP的初始列。上界隨著分支定價算法的迭代計算不斷更新。設(shè)計的啟發(fā)式算法可概括如下：首先隨機(jī)產(chǎn)生第一個客戶點，將其作為第一輛車的第一個訪問點。然后尋找距離該客戶點最近且未被訪問的客戶點，在滿足車容約束的條件下將其作為該車的下一個訪問點，否則由第二輛車進(jìn)行訪問。所有客戶點按照上述規(guī)則插入車輛，直至所有客戶被分配完成。最后對車輛按照性質(zhì)1進(jìn)行排序，確定每輛車的出發(fā)時間，計算每條路徑的時間花費及總目標(biāo)值。

3.3 動態(tài)規(guī)劃算法

在Feillet等[21]中提到，動態(tài)規(guī)劃算法經(jīng)常被用來求解ESPPRC。本文設(shè)計了一個符合所研究問題特點的動態(tài)規(guī)劃算法——改進(jìn)的標(biāo)簽法，以此來求解含有生產(chǎn)階段制約和車容約束的最短基本路徑問題。給定一個有向圖G′=(P,V,E),p∈P={1,2,…,H}，表示加工完成的第p個備件；頂點集合V={0,1,2,…,n}由3D打印中心和客戶點組成；邊集合E是圖G′中的所有弧集合。

3.3.1 標(biāo)簽定義與擴(kuò)展

3.3.2 占優(yōu)原則

3.3.3 加速策略

根據(jù)所研究問題特點，設(shè)計兩種加速策略來提高列生成算法的求解效率。

使用啟發(fā)式算法生成高質(zhì)量路徑。參考文獻(xiàn)Luo等[23]，通過改進(jìn)的禁忌搜索算法求解滿足資源約束的最短基本路徑問題。首先使用當(dāng)前RLMP最優(yōu)解中的基變量作為禁忌搜索算法的初始路徑，然后將進(jìn)行禁忌搜索后目標(biāo)檢驗數(shù)小于0的路徑添加到當(dāng)前主問題中。本算法使用了三種鄰域結(jié)構(gòu)，分別是(a)“加”操作：在當(dāng)前路徑中添加一個客戶點；(b)“刪除”操作：在當(dāng)前路徑中刪去一個客戶點；(c)“交換”操作：當(dāng)前路徑中的一個客戶點和非當(dāng)前路徑中的一個客戶點進(jìn)行交換。在保證p相同的情況下，每一種鄰域結(jié)構(gòu)均能產(chǎn)生相應(yīng)的鄰域解。

3.4 分支策略

4 算例與結(jié)果分析

本實驗的計算機(jī)參數(shù)配置為Intel(R)Core(TM) i5-2400S CPU @ 2.50GHz 2.50 GHz。

4.1 數(shù)據(jù)生成

本文實驗數(shù)據(jù)是基于CVRP經(jīng)典數(shù)據(jù)集(來源http://vrp.atd-lab.inf.puc-rio.br/index.php/en/)進(jìn)行修改，以生成符合本文研究問題特征的數(shù)據(jù)，具體做法如下：3D打印中心和客戶點坐標(biāo)均從A組算例中隨機(jī)選取；由于本文研究問題是基于備件制造行業(yè)，客戶需求量有限，每個客戶所需備件數(shù)為[1,5]之間的隨機(jī)數(shù)；為了方便計算同時不失一般性，單位產(chǎn)品的生產(chǎn)時間設(shè)為2。

4.2 計算結(jié)果與分析

4.2.1 模型及算法的驗證分析

為了評估模型正確性和算法有效性，使用CPLEX求解器IBM ILOG CPLEX12.2對小規(guī)模算例進(jìn)行求解，將CPLEX求得的全局最優(yōu)解或當(dāng)前上界與分支定價算法所得結(jié)果進(jìn)行對比。選取5組不同規(guī)模的算例進(jìn)行測試，n為客戶和工廠總數(shù)。在前四個算例和第五個算例中車輛數(shù)分別為2和3。算例9和10中“-”表示CPLEX在顯示的求解時間內(nèi)沒有求得最優(yōu)解，只有相應(yīng)的上下界。由表1可知使用CPLEX求解器與分支定價算法求得的結(jié)果吻合，驗證了模型正確性和算法有效性；通過兩者求解時間對比體現(xiàn)了改進(jìn)分支定價算法的高效性。

表1 CPLEX與改進(jìn)分支定價算法求解小規(guī)模算例的結(jié)果對比

4.2.2 較大規(guī)模算例結(jié)果

表2 較大規(guī)模算例結(jié)果

4.2.3 加速策略效果分析

為了證明本文所設(shè)計加速策略的有效性，分別給出不使用任何加速策略、僅使用最優(yōu)解性質(zhì)加速策略、僅使用啟發(fā)式加速策略以及同時使用兩種加速策略對不同規(guī)模算例的求解時間。n表示客戶和工廠總數(shù)，由表3可知，兩種加速策略均具有較為顯著的加速效果，特別是當(dāng)兩種加速策略同時使用時，加速效果最為顯著，平均求解時間由528.28s縮短為270.51s，求解效率提高了48.79%。

表3 加速策略效果對比

5 結(jié)論

智能制造和即時配送環(huán)境下的備件生產(chǎn)與運輸協(xié)同調(diào)度問題研究對實現(xiàn)制造強(qiáng)國具有重大意義。在此背景下，本文以提升基于3D打印技術(shù)的備件供應(yīng)鏈運作效率為目標(biāo)，研究了智能制造環(huán)境下的備件生產(chǎn)與運輸協(xié)同調(diào)度問題。建立了協(xié)同調(diào)度的混合整數(shù)規(guī)劃模型和集合覆蓋模型。深入分析問題特性后，提出最優(yōu)解性質(zhì)，使用改進(jìn)的分支定價算法進(jìn)行求解，并設(shè)計了新的加速策略和分支策略，使算例求解規(guī)模更大。多組算例測試結(jié)果表明，所得整數(shù)解與下界Gap均不超過1%，可知所構(gòu)建模型和算法能夠獲得高質(zhì)量解、所建立集合覆蓋模型能夠提供高質(zhì)量下界，有效解決了智能制造環(huán)境下較大規(guī)模的備件生產(chǎn)與運輸協(xié)同調(diào)度問題。有效幫助備件制造企業(yè)在實際生產(chǎn)和運輸環(huán)節(jié)進(jìn)行協(xié)同決策，極大提升了備件供應(yīng)鏈的響應(yīng)速度。

進(jìn)一步研究可考慮生產(chǎn)階段使用并行機(jī)生產(chǎn)、運輸階段使用不同車型車輛進(jìn)行配送的情況，在豐富問題特性的同時探索更高效的精確求解算法。