考慮倉(cāng)庫(kù)作業(yè)能力限制的器材年度供應(yīng)任務(wù)分配

張育銘，劉世倫，王 兵，金 峰

（陸軍裝甲兵學(xué)院 裝備保障與再制造系，北京 100072）

0 引言

陸軍裝備維修器材（下稱“器材”），是裝備保障工作的重要物質(zhì)基礎(chǔ)。器材及時(shí)足量供應(yīng)，是完成裝備維修、恢復(fù)部隊(duì)?wèi)?zhàn)斗力的重要保證。陸軍現(xiàn)行的器材供應(yīng)保障分為年度供應(yīng)和臨時(shí)供應(yīng)兩部分，其中以年度供應(yīng)為主、臨時(shí)供應(yīng)為輔。年度供應(yīng)由部隊(duì)提出器材需求，主管單位匯總后將供應(yīng)任務(wù)分配至儲(chǔ)供基地、戰(zhàn)役倉(cāng)庫(kù)等倉(cāng)儲(chǔ)供應(yīng)點(diǎn)位。

為提高器材供應(yīng)保障效益，學(xué)者從不同角度開(kāi)展了廣泛研究。田堯，等[1]針對(duì)軍事物流基地配送策略展開(kāi)研究，考慮配送能力，以配送費(fèi)用、儲(chǔ)備費(fèi)用、懲罰費(fèi)用最低為優(yōu)化目標(biāo)，通過(guò)Lingo求解，提升配送效率，降低配送成本。賈琦，等[2]考慮超儲(chǔ)器材調(diào)劑供應(yīng)，以總成本最小、時(shí)間最短、閑置率最低為目標(biāo)，采用改進(jìn)人工魚(yú)群算法進(jìn)行求解，得到最優(yōu)供應(yīng)方案。李浩[3]針對(duì)器材庫(kù)存補(bǔ)充供應(yīng)優(yōu)化，考慮器材保障經(jīng)費(fèi)、供應(yīng)點(diǎn)位庫(kù)存、倉(cāng)儲(chǔ)布局等因素影響，結(jié)合器材消耗量預(yù)測(cè)方法和庫(kù)存限額確定方法，構(gòu)建了隊(duì)屬倉(cāng)庫(kù)階段性需求確定和供應(yīng)點(diǎn)位階段性供應(yīng)方案確定模型，以保障成本和保障率為優(yōu)化目標(biāo)，設(shè)計(jì)了兩階段粒子群優(yōu)化算法求解。楊帆[4]在建立需求確定模型的基礎(chǔ)上，針對(duì)確定性任務(wù)下的器材供應(yīng)問(wèn)題，構(gòu)建了二階段供應(yīng)模型，采用改進(jìn)灰色遺傳算法對(duì)模型進(jìn)行求解；針對(duì)不確定任務(wù)的器材供應(yīng)問(wèn)題，構(gòu)建了滾動(dòng)多階段供應(yīng)模型，采用改進(jìn)的動(dòng)態(tài)粒子群算法進(jìn)行求解。

在年度供應(yīng)保障任務(wù)分配中，傳統(tǒng)做法是采用就近分配原則，即部隊(duì)的需求優(yōu)先由距離最近的倉(cāng)庫(kù)來(lái)供應(yīng)。但倉(cāng)庫(kù)建設(shè)規(guī)模、庫(kù)存容量、力量結(jié)構(gòu)和硬件設(shè)施條件各不相同，其作業(yè)能力也有較大差距。就近分配容易造成有的倉(cāng)庫(kù)供應(yīng)任務(wù)扎堆，導(dǎo)致器材發(fā)出時(shí)間遲滯，進(jìn)而影響整體保障效果。而現(xiàn)有文獻(xiàn)中未發(fā)現(xiàn)將倉(cāng)庫(kù)作業(yè)能力納入供應(yīng)保障任務(wù)全局進(jìn)行研究。因此，考慮倉(cāng)庫(kù)作業(yè)能力的限制，如何最優(yōu)地分配器材年度供應(yīng)保障任務(wù)，是值得研究的問(wèn)題。

器材供應(yīng)保障任務(wù)分配具有排序與調(diào)度問(wèn)題特征，可看做具有處理集限制的同類機(jī)排序與調(diào)度問(wèn)題，Leung，等[5,6]持續(xù)對(duì)處理集限制的調(diào)度問(wèn)題進(jìn)行研究，綜述了相關(guān)問(wèn)題的研究成果。Ebenlendr，等[7]針對(duì)此類問(wèn)題的一個(gè)特例，設(shè)計(jì)了一個(gè)近似求解算法。本文參考排序與調(diào)度的相關(guān)原理，考慮倉(cāng)庫(kù)作業(yè)能力限制，建立陸軍器材年度供應(yīng)保障任務(wù)分配模型，并進(jìn)行算例實(shí)驗(yàn)分析。

1 問(wèn)題描述和模型假設(shè)

本文考慮年度器材供應(yīng)保障任務(wù)的分配問(wèn)題，在器材需求、庫(kù)存和位置布局已知的情況下，優(yōu)化倉(cāng)庫(kù)向部隊(duì)的器材供應(yīng)任務(wù)。倉(cāng)庫(kù)受作業(yè)能力和庫(kù)存限制，整體目標(biāo)追求最短送達(dá)時(shí)間和最低成本的加權(quán)最優(yōu)。

1.1 問(wèn)題描述

考慮M個(gè)倉(cāng)庫(kù)向G個(gè)部隊(duì)供應(yīng)器材J類，其中第m個(gè)倉(cāng)庫(kù)位中第j類器材的庫(kù)存水平為qmj，各類器材總庫(kù)存數(shù)量為Q；第g個(gè)部隊(duì)總需求數(shù)量為sg，第j類器材需求數(shù)量為dgj，器材需求總數(shù)量為D。時(shí)間以T表示，單位為天。倉(cāng)庫(kù)作業(yè)能力W指一天內(nèi)作業(yè)總體能力數(shù)值，不同倉(cāng)庫(kù)作業(yè)能力各不相同，每類器材規(guī)格參數(shù)為vj，該數(shù)值越大，表示需要的倉(cāng)庫(kù)作業(yè)能力和運(yùn)輸成本越高。倉(cāng)庫(kù)和部隊(duì)具有部署位置L，運(yùn)輸時(shí)間為L(zhǎng)Tmg，同距離Rmg正相關(guān)，運(yùn)輸時(shí)間系數(shù)為kt；運(yùn)輸費(fèi)用LC同器材數(shù)量、規(guī)格和距離正相關(guān)，系數(shù)為kc。各部隊(duì)需求分配計(jì)劃至各倉(cāng)庫(kù)，以各部隊(duì)最大完成供應(yīng)時(shí)間Dmax和運(yùn)輸成本LC的加權(quán)和最小為優(yōu)化目標(biāo)。符號(hào)公式見(jiàn)表1。

表1 符號(hào)公式說(shuō)明

1.2 模型假設(shè)

根據(jù)上述問(wèn)題描述，提出如下模型假設(shè)：

（1）器材需求和庫(kù)存狀況已知，總庫(kù)存滿足部隊(duì)器材需求，不同倉(cāng)庫(kù)對(duì)同類器材的作業(yè)能力相同，作業(yè)準(zhǔn)備時(shí)間、裝卸載時(shí)間忽略不計(jì)；（2）不考慮庫(kù)存持有成本，忽略備貨作業(yè)過(guò)程中產(chǎn)生的其他費(fèi)用，運(yùn)輸費(fèi)用同器材總規(guī)格和運(yùn)輸距離正相關(guān)，不考慮零擔(dān)、整車(chē)運(yùn)輸費(fèi)用差異和固定費(fèi)用；（3）倉(cāng)庫(kù)可以在作業(yè)能力范圍內(nèi)同時(shí)完成多類多件器材的備貨，單件器材不允許跨天作業(yè)；（4）倉(cāng)庫(kù)完成一個(gè)部隊(duì)的全部作業(yè)任務(wù)即可進(jìn)行運(yùn)輸；（5）作業(yè)和運(yùn)輸時(shí)間單位為天，不滿1天分別按照1天計(jì)算。

2 模型構(gòu)建

本問(wèn)題為具有處理集限制的同類機(jī)排序與調(diào)度和運(yùn)輸成本的組合優(yōu)化問(wèn)題。按照傳統(tǒng)排序與調(diào)度理論，需要對(duì)所有器材需求在倉(cāng)庫(kù)進(jìn)行作業(yè)順序排序?？紤]到器材年度供應(yīng)保障任務(wù)器材類別相對(duì)集中的特點(diǎn)，弱化單件器材揀選先后順序，構(gòu)建了一個(gè)基于器材類別的供應(yīng)保障任務(wù)分配模型。并實(shí)現(xiàn)了傳統(tǒng)器材任務(wù)分配的最短距離優(yōu)先分配(SDFA，Shortest Distant First Assignment)算法，作為對(duì)比分析的參照。

2.1 基于器材類別的供應(yīng)保障任務(wù)分配模型

定義如下決策變量：

pgjmt∈{0 ,1}，表示第m個(gè)倉(cāng)庫(kù)第t天進(jìn)行第g個(gè)部隊(duì)的第j類器材備貨，反之為0。

xgjmt∈N，表示第m個(gè)倉(cāng)庫(kù)第t天進(jìn)行第g個(gè)部隊(duì)的第j類器材件數(shù)備貨。

由上述變量，構(gòu)建混合整數(shù)規(guī)劃模型的約束條件。

其中，式（1）表示倉(cāng)庫(kù)作業(yè)能力限制，任何時(shí)刻進(jìn)行備貨的器材作業(yè)能力需求不能超過(guò)倉(cāng)庫(kù)作業(yè)能力。式（2）表示滿足需求約束，必須滿足所有部隊(duì)所有器材需求。式（3）表示庫(kù)存限制，分配器材供應(yīng)任務(wù)不能超過(guò)該單位庫(kù)存。式（4）表示最大任務(wù)完成時(shí)間，為最后一個(gè)部隊(duì)完成收貨的時(shí)刻。式（5）表示運(yùn)輸成本。

可以看到，在約束條件構(gòu)建中存在一個(gè)0-1決策變量同整數(shù)變量乘積的二次約束pgjmtxgjmt，對(duì)于此形式二次規(guī)劃問(wèn)題的求解是非常困難的。為解決此問(wèn)題，引入決策變量bgjmt∈[0 ,U]，U為xgjmt中的最大值，使得bgjmt=pgjmtxgjmt。得到改進(jìn)后的混合整數(shù)規(guī)劃模型約束。

其中，式（6）-（10）為式（1）-（5）決策變量對(duì)應(yīng)替代后的約束條件。式（11）-（14）為約束決策變量bgimt和xgimt、pgimt的關(guān)系。式（11）、式（12）對(duì)約束變量bgimt的上界，式（13）約束變量bgimt的下界，三個(gè)約束是緊約束，保證了bgimt=pgimtxgimt。以最大完成任務(wù)時(shí)間和運(yùn)輸成本的加權(quán)和最小為優(yōu)化目標(biāo)，完成供應(yīng)分配模型構(gòu)建。

2.2 SDFA算法

在實(shí)際工作中，傳統(tǒng)的器材任務(wù)分配是按照距離優(yōu)先準(zhǔn)則進(jìn)行就近分配，為了檢驗(yàn)最優(yōu)任務(wù)分配與傳統(tǒng)任務(wù)分配效果的差別，這里給出傳統(tǒng)的距離優(yōu)先分任務(wù)分配（SDFA，Shortest Distant First Assignment）的實(shí)現(xiàn)算法，其基本思路是：首先計(jì)算倉(cāng)儲(chǔ)點(diǎn)、部隊(duì)間的距離矩陣，對(duì)距離進(jìn)行排序，首選安排距離最近倉(cāng)庫(kù)、部隊(duì)組合的器材分配，按照距離遠(yuǎn)近依次分配，最終完成全部器材需求分配。完成計(jì)劃分配后，倉(cāng)庫(kù)以遠(yuǎn)距離優(yōu)先安排備貨的原則進(jìn)行作業(yè)排班，計(jì)算最大完成時(shí)間和運(yùn)費(fèi)。偽代碼見(jiàn)表2。

表2 SDFA算法偽代碼

3 模型分析

首先考察一種簡(jiǎn)化的情況，以分析模型的適用性。

考慮2個(gè)倉(cāng)庫(kù)，4個(gè)部隊(duì)，1類器材需求，庫(kù)存充足，倉(cāng)庫(kù)作業(yè)能力各不相同，4 個(gè)部隊(duì)圍繞作業(yè)能力較大倉(cāng)儲(chǔ)點(diǎn)分布。布局如圖1所示，圖中點(diǎn)位連接線為路徑和運(yùn)輸時(shí)間，令倉(cāng)儲(chǔ)點(diǎn)庫(kù)存為T(mén)M=(+∞,+∞)T，器材需求為T(mén)D=(10,20,30,40)T，倉(cāng)儲(chǔ)點(diǎn)到部隊(duì)的運(yùn)輸時(shí)間矩陣為，倉(cāng)儲(chǔ)點(diǎn)作業(yè)能力W={20,10}，器材規(guī)格V={5}，運(yùn)輸成本系數(shù)kc=0.01。根據(jù)最短距離優(yōu)先算法，以橫向代表倉(cāng)庫(kù)、縱向代表部隊(duì)，易得完成供應(yīng)的時(shí)間為26，運(yùn)輸成本為5。以算法計(jì)算的時(shí)間、成本值對(duì)兩個(gè)變量進(jìn)行無(wú)量綱處理，并調(diào)整模型中權(quán)重θ1，θ2，通過(guò)COPT求解器求解模型的精確解。表3為SDFA算法和模型求解供應(yīng)保障計(jì)劃時(shí)間、成本對(duì)比表，表中時(shí)間減少和成本增加均為同SDFA算法得到的時(shí)間、成本數(shù)值，不同權(quán)重對(duì)應(yīng)分配計(jì)劃見(jiàn)表4。

圖1 供需點(diǎn)位布局示意圖

表4 供應(yīng)保障任務(wù)

從結(jié)果可以看到，通過(guò)調(diào)整權(quán)重θ1,θ2的取值，可以得到不同權(quán)重下的最優(yōu)任務(wù)分配策略，模型求解較SDFA算法在供應(yīng)完成時(shí)間上有明顯改進(jìn)。傳統(tǒng)就近分配原則，造成了供應(yīng)任務(wù)積壓在01倉(cāng)庫(kù)，如果給臨近的02倉(cāng)庫(kù)分擔(dān)一些任務(wù)，可有效縮短供應(yīng)時(shí)間。但舍近求遠(yuǎn)難免會(huì)產(chǎn)生運(yùn)輸成本的增加，實(shí)際工作中需要在時(shí)間和成本中做出權(quán)衡。

4 算例實(shí)驗(yàn)

下面結(jié)合陸軍器材年度供應(yīng)保障業(yè)務(wù)，生成不同規(guī)模算例進(jìn)行實(shí)驗(yàn)，通過(guò)python調(diào)用COPT求解器進(jìn)行求解，運(yùn)行環(huán)境為Intel(R) Core(TM) i7-9700F 3.00GHz CPU，32.0 GB RAM。參考業(yè)務(wù)實(shí)際，構(gòu)建3個(gè)倉(cāng)庫(kù)，15個(gè)部隊(duì)，100類共計(jì)30 000 件器材需求，倉(cāng)庫(kù)作業(yè)能力各不相同，點(diǎn)位在1 000×1 000范圍內(nèi)分布。

4.1 基本信息

倉(cāng)庫(kù)器材類別、數(shù)量、作業(yè)能力和部署位置見(jiàn)表5。庫(kù)存器材基礎(chǔ)數(shù)量指與部隊(duì)器材需求相等的庫(kù)存數(shù)量。

表5 倉(cāng)庫(kù)信息表

部隊(duì)需求器材類別、數(shù)量和部署位置見(jiàn)表6。

表6 部隊(duì)基本信息表

器材數(shù)量和作業(yè)能力需求見(jiàn)表7。器材的規(guī)格代表了器材的尺寸大小，分為5類：極小件、小件、中間、大件和極大件，對(duì)應(yīng)不同運(yùn)輸成本和作業(yè)能力消耗，分別為1,10,50,100,200。

表7 器材需求總量和規(guī)格參數(shù)

4.2 結(jié)果分析

設(shè)置相同器材類型布局下三種庫(kù)存數(shù)量（對(duì)應(yīng)器材種類為基礎(chǔ)數(shù)量的庫(kù)存、2倍基礎(chǔ)數(shù)量的庫(kù)存、數(shù)量不限的庫(kù)存）和所有倉(cāng)庫(kù)全品種器材不限庫(kù)存4種情況進(jìn)行器材分配求解，按照第3 節(jié)求解方法，θ1，θ2分別取0.8 和0.2，kc=0.001，進(jìn)行求解分析。表8為四種情形SDFA算法和模型求解的完成供應(yīng)時(shí)間和成本。

表8 計(jì)算結(jié)果

從結(jié)果上看，基礎(chǔ)數(shù)量庫(kù)存時(shí)，算例的可優(yōu)化空間很??；隨著庫(kù)存數(shù)量和品種的增加，SDFA算法的供應(yīng)完成時(shí)間呈先增后減的趨勢(shì)，運(yùn)輸成本呈大致下降趨勢(shì)，表明就近分配原則主要起到了節(jié)約運(yùn)輸成本的效果，但容易造成倉(cāng)庫(kù)作業(yè)任務(wù)積壓而導(dǎo)致供應(yīng)時(shí)間變長(zhǎng)；模型算法求解的供應(yīng)時(shí)間得到明顯縮短，同時(shí)不可避免的會(huì)引起運(yùn)輸成本的小幅上漲。另外，在本算例中兩倍基礎(chǔ)數(shù)量庫(kù)存情況下已經(jīng)達(dá)到較好的供應(yīng)時(shí)效，提高器材數(shù)量和品種的儲(chǔ)備，對(duì)降低運(yùn)輸成本略有改善，但不會(huì)進(jìn)一步縮短供應(yīng)任務(wù)完成時(shí)間；考慮到現(xiàn)實(shí)中增加庫(kù)存帶來(lái)的采購(gòu)成本和庫(kù)存持有成本增加，增加庫(kù)存來(lái)?yè)Q取運(yùn)輸成本的降低是不可取的。

圖2展示的是兩倍庫(kù)存情況下的SDFA算法和模型求解的任務(wù)分配流向圖，箭頭的粗細(xì)代表器材數(shù)量，不同線型箭頭代表不同倉(cāng)庫(kù)的器材供應(yīng)，可以看出倉(cāng)庫(kù)2作業(yè)壓力較重，模型優(yōu)化了任務(wù)分配后，將部隊(duì)11、15、9、1的就近保障任務(wù)由倉(cāng)庫(kù)1和倉(cāng)庫(kù)3進(jìn)行分擔(dān)，減輕了倉(cāng)庫(kù)2的作業(yè)壓力，提高了保障任務(wù)整體時(shí)效。

圖2 流向圖

5 結(jié)語(yǔ)

本文考慮倉(cāng)庫(kù)作業(yè)能力限制對(duì)陸軍裝備維修器材年度供應(yīng)保障任務(wù)的影響，構(gòu)建了兼顧任務(wù)完成時(shí)間和運(yùn)輸成本的供應(yīng)保障任務(wù)分配模型，并通過(guò)算例與傳統(tǒng)就近分配方式進(jìn)行對(duì)比。結(jié)果表明：

（1）傳統(tǒng)就近分配方式，能夠得出運(yùn)輸成本較低的方案，但容易導(dǎo)致作業(yè)任務(wù)積壓，使任務(wù)完成時(shí)間變長(zhǎng)；（2）最優(yōu)任務(wù)分配模型能夠以較小的運(yùn)輸成本漲幅得到任務(wù)時(shí)效的顯著改善，從而提高整體供應(yīng)保障效益；（3）倉(cāng)庫(kù)保持較高的庫(kù)存量和較全的庫(kù)存品類可以提供更豐富的任務(wù)分配方案，對(duì)降低運(yùn)輸成本有一定效果，但由于倉(cāng)庫(kù)作業(yè)能力的限制，對(duì)改善整體任務(wù)完成時(shí)間的效果有限。