楊帆， 王鐵寧

(裝甲兵工程學院 技術保障工程系， 北京 100072)

?

多目標優(yōu)化的多品種維修器材分配問題研究

楊帆， 王鐵寧

(裝甲兵工程學院 技術保障工程系， 北京 100072)

為了更好地滿足部隊維修器材需求，優(yōu)化需求數(shù)量超過供應中心庫存數(shù)的多品種維修器材分配整合供應問題，建立了保障重點、兼顧公平、效用最大的多目標優(yōu)化模型。提出了采用灰色關聯(lián)度方法對多目標進行處理，將多目標轉化為單目標問題，并將之內嵌到改進遺傳算法中。實例驗證表明，該算法最優(yōu)適應度值及平均適應度值可分別降低31.538 5%和37.371 1%，驗證了該模型能有效減少器材分配失衡，提高器材供應效率。

兵器科學與技術； 維修器材； 多目標優(yōu)化； 灰色關聯(lián)度； 遺傳算法

0 引言

部隊的維修器材作為維修保障作業(yè)中至關重要的資源，對裝備的維修及保障能力有著重大影響。當前部隊維修機構對裝備進行維修時，主要采取換件修理的方式，由此導致的大量維修器材的消耗就對部隊維修器材庫存控制和需求滿足提出了很高的要求。如何對維修器材的庫存范圍進行合理控制，更好地滿足部隊維修需求，對我軍的維修保障有著重要的意義。

部隊維修器材的庫存水平主要受訂貨、存儲與供應影響。而決定部隊維修器材庫存水平的主要是器材訂貨決策及供應決策。傳統(tǒng)的訂貨策略及供應策略主要是針對單品種器材，即每次僅對一個需求點進行供應，隨著信息化程度的不斷加深，信息共享條件下，器材供應保障系統(tǒng)的建設使得多品種供應方式得以發(fā)展[1]。多品種維修器材供應主要指整合供應方式，即供應中心向某需求點進行器材供應時，同時對該保障區(qū)域內的多個需求點的多種器材需求進行供應。多品種器材的整合供應，較傳統(tǒng)的單一“請領- 供應”器材供應方式能夠更好地降低成本，節(jié)約時間，滿足部隊需求。當前對多品種器材的聯(lián)合訂貨策略研究已較為成熟[2-3]，而對多品種器材供應的研究仍然是一項十分迫切的任務。

本文主要研究供應中心器材數(shù)量有限時，多品種器材的分配問題。對多品種維修器材進行分配時，對部隊任務性質、分配效用等均有要求，因此是一個多目標的優(yōu)化問題。多目標優(yōu)化是目前備受關注的一個重要問題，在車輛調度、生產設計、投資、生產調度領域等均有廣泛應用。早期求解多目標問題時，一般通過加權求和等方式將多目標轉化為單目標，再采用數(shù)學方法按單目標求解，但是求解效率低，且受權重的影響很大[4]。之后逐漸提出多目標優(yōu)化的智能算法，如多目標進化算法NSGA2、SPE2等，運行效率較高，且可行解的分布良好，但是求解高維問題解集多樣性缺陷較為明顯[5]；多目標模擬退火算法對目標函數(shù)的要求很低，適應性較強，但是收斂速度慢、效率較低[6]；多目標蟻群算法和多目標遺傳算法在全局空間的搜索能力較強，但是易出現(xiàn)停滯早熟問題[7]。因此，選擇合適的方法，并針對所選方法的不足進行改進，應用于多品種維修器材分配的多目標優(yōu)化，對于提高分配效率，保障維修需求有著顯著意義。

本文建立了有限多品種維修器材分配的多目標優(yōu)化模型，研究了同時對多需求點分配多品種器材時的約束條件，基于灰色關聯(lián)度方法將多目標問題轉化為單目標問題。將灰色關聯(lián)度方法與遺傳算法相結合，設計了灰色- 遺傳優(yōu)化求解方法。最后用10次仿真實例驗證了該方法的可行性，為部隊供應中心解決有限多品種器材分配問題提供一種新思路。

1 基于灰色關聯(lián)度的模型構建

1.1 多品種維修器材分配模型構建

1.1.1 重點任務部隊優(yōu)先

在對各需求部隊分配有限器材時，必須考慮各個需求點所執(zhí)行任務的情況。對執(zhí)行重點任務的部隊，應該優(yōu)先滿足其器材需求。一般認為，若重點任務部隊能分配得到的器材數(shù)量等于其請領上限，則該需求點部隊器材需求得到滿足。

(1)

式中：dj為需求部隊的所屬情況。

(2)

式中：Zij為第Sj個需求點對第Ri種需求上限的滿足情況。

因此，該目標可以通過需求點某種器材得到完全滿足的情況來衡量，即用執(zhí)行重點任務的部隊中被滿足數(shù)量與總數(shù)之比f1來計算。

(3)

f1為多品種維修器材分配問題中考慮重點任務部隊優(yōu)先的一個目標，該目標越大越好。

同時，由于器材數(shù)量有限，不能完全保障所有需求得到滿足，因此，對于執(zhí)行重點任務的部隊，其最低需求量必須得到滿足，即

(4)

1.1.2 兼顧公平

在對各需求點進行器材分配時，由于總器材數(shù)有限，不可能滿足所有需求點的需求上限。但是在對各需求點需求器材進行協(xié)調時，應該盡量秉持著公平原則，縮小分配過程中的不平衡。該目標用各個需求點部隊滿足率與平均滿足率之間絕對差值f2大小來計算。

(5)

該目標值越小越好。

1.1.3 效益最大

多品種維修器材的合理分配問題，最重要的目標之一就是器材分配之后，考慮各個需求點獲得的軍事效益f3，即尋求所有需求點軍事效益的最大化。效益最大目標就是從總體角度考慮，分析各個需求點在得到一定數(shù)量的維修器材之后，保障能力的大小，以此表征軍事效益的大小，保障能力越高，則帶來的軍事效益越高，反之亦然。保障軍事效益是考慮需求點在需求下限基礎上所分配得到的超出下限的器材數(shù)量，該數(shù)量反映了在有維修需要時，需求點能夠更好地滿足裝備維修保障需求的能力大小。

設對于需求點j，當收到某種數(shù)量的器材Rij時，其保障能力函數(shù)為uij(R1j，R2j，…，Rmj)。由于不同的需求部隊重要性不同，因此，在考慮保障能力時，需要考慮各個需求點的權重wj，即得到每個需求點的效益函數(shù)qj為

qj=wjuj(R1j，R2j，…，Rmj).

(6)

由此可得歸一化后效益函數(shù)Qj為

Qj(R1j，R2j，…，Rmj)=

(7)

(8)

式中：

(9)

(10)

該目標越大越好。

1.2 多目標優(yōu)化設計的灰色關聯(lián)度方法

由上述分析，可建立有限多品種維修器材分配的多目標模型。

s.t.

Qj(R1j，R2j，…，Rmj)=

1≤i≤m，1≤j≤n.

在得到多品種維修器材分配的多目標模型之后，通過灰色關聯(lián)度方法，可將上述多目標問題轉換為單目標問題。

設目標函數(shù)的參考序列為f0=(f01，f02，f03)；比較序列為f=(f1，f2，f3)。則f0與f的灰色關聯(lián)度[8]為

(11)

式中：Δ(k)=|f0k-fk|，k=1，2，3；Δmax、Δmin分別為Δ(k)的最小值和最大值；ρ是介于0、1之間的分辨系數(shù)，一般取0.5。灰色關聯(lián)度越小，表示比較序列與參考序列之間的差別越大，相似程度越小。f0與f的灰色相似系數(shù)μ[9]為

(12)

ε=αr+βμ,

(13)

式中：系數(shù)α≥0，β≥0，且α+β=1.

將多目標問題轉化為求最小值問題的單目標問題進行求解，因此引入灰色差異度c：

c=1-ε.

(14)

c越小，表示比較序列與參考序列越接近，即結果越優(yōu)。參考序列在尋優(yōu)過程中動態(tài)取最小值即可，無需事先確定[11]。

2 基于灰色- 遺傳算法的問題求解

2.1 編碼

多品種的維修器材分配問題為離散整數(shù)問題，因此，在使用遺傳算法進行編碼時，為了提高運算效率和準確率，本文采用一維整數(shù)編碼形式，表示各種器材分配給各個需求部隊的數(shù)量。例如，假設有3種維修器材分配給3個需求點，則1個種群個體可以編碼為(5，10，2，7，8，15，3，9，12)，前3個位置表示分配給第1個需求點的3種器材數(shù)量，中間3個位置表示分配給第2個需求點的3種器材數(shù)量，最后3個位置表示分配給第3個需求點的3種器材數(shù)量。

2.2 適應度函數(shù)

由于遺傳算法對于約束條件的處理較為復雜，因此在根據(jù)灰色關聯(lián)度方法轉化的目標函數(shù)中，加入動態(tài)罰函數(shù)[12]來構造遺傳算法的適應度函數(shù)F(Rij，δ)。

(15)

式中：δ為懲罰因子。隨著迭代次數(shù)增加，越來越接近最優(yōu)解時，動態(tài)懲罰因子也會隨之越來越小。

2.3 最優(yōu)個體保持策略

計算每個個體的適應度值，采用精英保留策略[13]，適應度函數(shù)值中最小的若干個體，即視為父代中的精英部分。該部分不進行交叉變異操作直接繼承到子代。精英數(shù)目需要根據(jù)種群大小進行設定。除去精英個體之外的個體再按照設定的交叉與變異概率進行操作。例如種群大小為50，精英數(shù)目為3，則適應度值最小的3個染色體直接進入子代，剩下的47個染色體再進行交叉與變異操作。

2.4 遺傳算子

采用輪盤賭法進行選擇操作，計算個體的適應度值與種群總體適應度值的比值，將比值結果作為選擇概率。由于本算法求目標函數(shù)的最小值，因此，比值越小的個體，被選擇的概率就越大。

采用多點交叉的遺傳算子，在染色體中隨機選擇3個切點，將第1與第2切點之間、第3切點之后的子串進行交叉[14]。變異操作時，從染色體中隨機選擇3個子點，在合理范圍內，對該3個點進行替換，得到新的染色體序列。

3 實例仿真

文獻[1]中對遺傳算法進行改進后，采用各個目標加權求和方式求解多目標問題，并將改進算法與傳統(tǒng)遺傳算法進行對比。本文為了驗證灰色- 遺傳融合改進算法在解決多品種維修器材分配過程中多目標優(yōu)化問題的優(yōu)點，采用文獻[1]給出的某防空旅的器材供應仿真實例進行驗證，并把本文算法與文獻[1]中列出的兩種算法進行比較。實例驗證程序如圖1所示。

設該旅供應中心有3種維修器材A、B、C要分配給下屬6個單位，每種器材的數(shù)量見表1.

表1 供應中心器材數(shù)Tab.1 Quantity of inventory materials in supply center

圖1 實例驗證流程圖Fig.1 Flow chart of example verification

各單位的請領量和需求下界見表2.

表2 各需求點需求上下限Tab.2 Max and min demands of each demand point

表2中，單位2與單位5執(zhí)行重點任務。從表2中可以看出，各單位請領總數(shù)大于供應中心現(xiàn)儲器材數(shù)。因此需要對這些器材進行合理分配以最大化實現(xiàn)部隊的保障需求。對于器材請領數(shù)小于供應中心可分配數(shù)的器材，直接按需分配即可，非本文研究內容。本文沿用文獻[1]算法，對各個需求點的效用函數(shù)采用加權求和的形式，各個需求點對不同器材的權重及各個需求點部隊自身的權重見表3.

由(9)式、(10)式可得單位1的最大效用和最小效用：

0.1×(0.4×0+0.25×2+0.35×1)=0.085，

表3 器材及需求點權重Tab.3 Weights of materials and demand points

0.1×(0.4×20+0.25×65+0.35×20)=3.125.

同理，可求得各個需求點的最大效用和最小效用，見表4.

表4 各需求點最大和最小效用Tab.4 Maximum and minnimum utilities of each demand point

各單位獲得一定數(shù)量的器材效用函數(shù)在仿真過程中，遺傳算法的基本參數(shù)設置為：種群規(guī)模50，最大迭代數(shù)為50，精英保留數(shù)目為5，交叉概率為0.3，變異概率0.1. 在MATLAB 2014(a)環(huán)境下進行仿真運算。

為了驗證算法可靠性，一共進行了10次實驗，仿真適應度函數(shù)最優(yōu)值及平均值如圖2、圖3所示。從圖2、圖3中可以看出，灰色- 遺傳算法在求解多目標問題中，能夠更快地找到最優(yōu)解，并且優(yōu)化過程比較平穩(wěn)，而文獻[1]遺傳算法較之效率低。因為文獻[1]僅僅是對交叉算子和變異算子進行簡單改進，對于多目標向單目標的轉化也只是進行簡單的加權求和。將本文算法與文獻[1]中列出的兩種算法進行比較，3種算法的對比結果如表5所示。從表5中可以看出，灰色- 遺傳算法與傳統(tǒng)遺傳算法及文獻[1]中改進的遺傳算法相比，能更很好地解決多品種維修器材分配的多目標優(yōu)化問題。

圖2 本文算法結果Fig.2 Algorithm results in the present paper

圖3 文獻[1]中改進的遺傳算法結果Fig.3 Inproved GA algorithm results in Ref.[1]

表5 仿真結果比較Tab.5 Comparison of simulated results

計算可得，平均10次計算結果中，灰色- 遺傳算法適應度最優(yōu)值分別比文獻[1]遺傳算法和標準遺傳算法小31.538 5%和97.050 5%，平均適應度函數(shù)值分別小37.371 1%和36.714 7%，優(yōu)化了運算結果。最終器材分配結果見表6，與文獻[1]結果相比，都能夠保障重點部隊與重點任務，同時，本文能夠縮小各個需求點之間的分配不平衡性，較原分配方案有著更高的總體軍事效益。

表6 器材分配結果Tab.6 Result of material distribution

4 結論

本文針對多品種維修器材分配的多目標優(yōu)化問題，將灰色關聯(lián)度方法內嵌到遺傳算法模型中，提出了灰色- 遺傳算法，并通過10次仿真實例進行驗證?？梢缘贸?，該算法能夠更好地解決多目標優(yōu)化問題，提高維修器材分配的決策效率?；疑Ｐ椭饕鉀Q小樣本問題，因此本文中模型的優(yōu)點是對于小數(shù)據(jù)問題，能夠進行高效準確地計算，而對于大規(guī)模數(shù)據(jù)的器材分配問題，需要在本文基礎上，結合大數(shù)據(jù)的相關理論與方法做進一步的實驗研究。

References)

[1] 聶成龍,張建榮.多品種維修器材庫存決策優(yōu)化技術[M].北京:國防工業(yè)出版社,2015. NIE Cheng-long, ZHANG Jian-rong. Inventory decision optimization technique of multi-item maintenance materials[M]. Beijing: National Defense Industry Press, 2015.(in Chinese)

[2] 劉亞東,孫志剛. 多品種維修器材統(tǒng)一訂購策略的庫存決策模型[J].火力與指揮控制,2013,38(1):133-137. LIU Ya-dong, SUN Zhi-gang. Inventory decision model of unanimous ordering policy with multi-item maintenance materials[J]. Fire Control & Command Control, 2013,38(1):133-137.(in Chinese)

[3] 張建榮,于永利,張柳,等. 維修器材聯(lián)合訂貨的庫存決策模型[J].系統(tǒng)工程與電子技術,2013,35(1):109-112. ZHANG Jian-rong, YU Yong-li, ZHANG Liu, et al. Inventory decision model of joint ordering policy with maintenance materials[J]. Systems Engineering and Electronics, 2013, 35(1):109-112.(in Chinese)

[4] 張迷,賀興時. 多目標優(yōu)化問題的花授粉算法改進[J].西安工程大學學報,2016,30(3):343-399. ZHANG Mi, HE Xing-shi. An improvement of flower pollination algorithm in multi-objective optimization[J]. Journal of Xi’an Polytechnic University, 2016,30(3):343-399.(in Chinese)

[5] Kundu P K, Zhang Y, Ray A K. Multi-objective optimization of simulated countercurrent moving bed chromatographic reactor for oxidative coupling of methane [J]. Chemical Engineering Science, 2009,64(19):4137-4149.

[6] 肖曉偉,肖迪,林錦國,等.多目標優(yōu)化問題的研究概述[J].計算機應用研究,2011,28(3):805-827. XIAO Xiao-wei, XIAO Di, LIN Jin-guo, et al. Overview on multi-objective optimization problem research[J]. Application Research of Computers, 2011,28(3):805-827.(in Chinese)

[7] 蘭世海.改進蟻群算法研究及其在車輛調度中的應用[D].上海:東華大學,2007. LAN Shi-hai. Study on improved ant colony algorithm and its application in the vehicle scheduling[D]. Shanghai: Donghua University, 2007.(in Chinese)

[8] Qin M Y, Liu D W, Luo Y S. Multi-objective optimization of turning parameters based on gray system theory[J]. Hydromechatronics Engineering, 2013,41(24):97-100.

[9] 扶名福,謝明祥,饒泓,等.基于綜合關聯(lián)度分析的風機故障診斷[J].中國機械工程,2007,18(20):2403-2405. FU Ming-fu,XIE Ming-xiang,RAO Hong,et al. Fault diagnosis of suction fan based on the synthetically relational analysis[J].China Mechanical Engineering,2007,18(20):2403-2405.(in Chinese)

[10] 韓朝暉,葉南海.混合離散變量的多目標優(yōu)化設計灰色綜合關聯(lián)度算法[J].湖南農業(yè)大學學報:自然科學版,2008,34(4):495-497. HAN Zhao-hui,YE Nan-hai. Grey synthetically relational degree algorithm of multi-objective design with hybrid discrete variables[J].Journal of Hunan Agricultural University:Natural Sciences,2008,34(4):495-497.(in Chinese)

[11] 駱清國,尹洪濤,寧興興.一種基于有向圖的冷卻系統(tǒng)原理方案設計方法[J].兵工學報,2016,37(1):10-16. LUO Qing-guo, YIN Hong-tao, NING Xing-xing. A design method of cooling system principle scheme based on directed graph[J].Acta Armamentarii,2016,37(1):10-16.(in Chinese)

[12] 車曉毅,羅佑新,汪超. 高維多目標優(yōu)化設計的灰色微粒群算法[J].機械傳動,2009,33(1):55-58. CHE Xiao-yi, LUO You-xin, WANG Chao. Grey particle swarm optimal algorithm for high dimension multi-objective optimization design[J]. Journal of Mechanical Transmission, 2009, 33(1):55-58.(in Chinese)

[13] 郭惠昕,車曉毅,肖偉躍.混沌遺傳優(yōu)化算法及其在機械優(yōu)化設計中的應用[J].機械設計,2003,20(10):23-25. GUO Hui-xin,CHE Xiao-yi,XIAO Wei-yue. Chaos-genetic optimal algorithm and application in mechanical optimal design[J].Journal of Machine Design, 2003,20(10):23-25.(in Chinese)

[14] 董朝陽,路遙,王青.改進的遺傳算法求解火力分配優(yōu)化問題[J].兵工學報,2016,37(1)：97-102. DONG Chao-yang, LU Yao, WANG Qing. Improved genetic algorithm for solving firepower distribution[J].Acta Armamentarii, 2016,37(1)：97-102.(in Chinese)

Research on Multi-objective Optimization of Multi-itemMaintenance Material Distribution Problem

YANG Fan， WANG Tie-ning

(Department of Technical Support Engineering, Academy of Armored Force Engineering, Beijing 100072, China)

A multi-objective optimization model is established for multi-item maintenance material distribution to help the supply centers satisfy the maintenance material demands of troops. In the proposed model, the priority, fairness and efficiency are taken as the multi-objects. An improved genetic algorithm is combined with grey correlation degree method, which can transfer multi-objective problem to single-objective problem. The example verification shows that the best and mean fitness values are reduced by 31.538 5% and 37.371 1%, respectively. The proposed model can be used to reduce the unfairness of multi-item maintenance material distribution, and improve the efficiency of materials supply.

ordnance science and technology; maintenance material; multi-objective optimization；grey correlation degree；genetic algorithm

2016-11-04

軍隊科研計劃項目(2016年)

楊帆(1990—)，女，博士研究生。E-mail：673729309@qq.com

王鐵寧(1962—)，男，教授，博士生導師。E-mail：wtn0728@163.com

E92

A

1000-1093(2017)06-1186-06

10.3969/j.issn.1000-1093.2017.06.019