軍事逆向物流網(wǎng)絡(luò)優(yōu)化模型及算法研究

趙方庚

(蚌埠汽車士官學(xué)校，安徽 蚌埠233011)

1 引言

軍事逆向物流，是指在平戰(zhàn)時(shí)，從軍事力量手中回收不合格或者失去原軍事使用價(jià)值的軍用物資，為滿足一定的軍事需求，從軍事消費(fèi)點(diǎn)一端返回并加以適當(dāng)處理，直至最終完成再利用所進(jìn)行計(jì)劃、管理和控制的過(guò)程［1］。軍事逆向物流的網(wǎng)絡(luò)結(jié)構(gòu)不僅直接影響資源的回收利用，還關(guān)系到軍事物流保障的效率和效益，科學(xué)、合理的網(wǎng)絡(luò)結(jié)構(gòu)是系統(tǒng)高效運(yùn)行的重要保證。

隨著人們對(duì)環(huán)保問(wèn)題的日益關(guān)注，軍事逆向物流也逐漸成為相關(guān)領(lǐng)域的研究熱點(diǎn)，但現(xiàn)有研究主要針對(duì)軍事逆向物流的運(yùn)作模式［2］、運(yùn)行機(jī)制［3］和管理措施［4］等問(wèn)題進(jìn)行定性的分析，基本沒(méi)有涉及軍事逆向物流的網(wǎng)絡(luò)優(yōu)化問(wèn)題。在民用領(lǐng)域，逆向物流網(wǎng)絡(luò)優(yōu)化得到了相對(duì)較多的關(guān)注。王亞楠等［5］通過(guò)建立物流逆向配送網(wǎng)絡(luò)關(guān)系的數(shù)學(xué)模型，利用雙向反饋信息加權(quán)算法進(jìn)行網(wǎng)絡(luò)配送優(yōu)化計(jì)算，達(dá)到了提高網(wǎng)絡(luò)運(yùn)行效率的目的;高陽(yáng)和劉軍［6］在考慮產(chǎn)品回收量和消費(fèi)市場(chǎng)需求量不確定的條件下，以第三方物流企業(yè)收益和制造商收益最大化為目標(biāo)，建立了基于第三方回收多周期再制造逆向物流網(wǎng)絡(luò)模型;吳洪波和謝夢(mèng)星［7］以各種設(shè)施的投資和運(yùn)營(yíng)成本之和最小為優(yōu)化目標(biāo)建立了隨機(jī)規(guī)劃模型，確定了網(wǎng)絡(luò)中各設(shè)施的數(shù)量和位置，并對(duì)各條路徑上的物流量進(jìn)行了合理分配;王雁鳳和黃有方［8］構(gòu)建了基于雙層規(guī)劃的過(guò)期藥品逆向物流網(wǎng)絡(luò)優(yōu)化模型，并設(shè)計(jì)了求解該模型的分層遺傳算法;Pishvaee 等［9］以運(yùn)輸和開(kāi)設(shè)成本為優(yōu)化目標(biāo)，建立多階段逆向物流網(wǎng)絡(luò)的混合整數(shù)規(guī)劃模型，并研究了其模擬退火算法;Niknejad 和Petrovic［10］建立了包括產(chǎn)品回收過(guò)程的庫(kù)存與生產(chǎn)規(guī)劃優(yōu)化模型，并提出了求解問(wèn)題的兩階段模糊混合整數(shù)優(yōu)化算法;Roghanian 和Pazhoheshfar［11］建立了逆向物流網(wǎng)絡(luò)的隨機(jī)混合整數(shù)規(guī)劃模型，并研究了基于優(yōu)先級(jí)的遺傳算法。上述研究雖對(duì)商業(yè)逆向物流網(wǎng)絡(luò)建設(shè)有較強(qiáng)的指導(dǎo)作用，但都以經(jīng)濟(jì)效益為優(yōu)化目標(biāo)，無(wú)法適用于軍事逆向物流環(huán)境。此外，在基本逆向物流網(wǎng)絡(luò)優(yōu)化算法方面，Pishvaee等［9］應(yīng)用的模擬退火算法雖取得了較好的優(yōu)化結(jié)果，但在組合優(yōu)化領(lǐng)域，模擬退火算法并不是最高效的智能優(yōu)化方法，其計(jì)算效率仍有一定的提高空間?；诖耍疚慕⒘塑娛履嫦蛭锪骶W(wǎng)絡(luò)優(yōu)化的數(shù)學(xué)模型，并研究了求解模型的遺傳算法。

2 軍事逆向物流網(wǎng)絡(luò)優(yōu)化模型

2.1 問(wèn)題描述

本文以軍事逆向物流中的常見(jiàn)形式裝備維修保障為例，研究其逆向物流網(wǎng)絡(luò)優(yōu)化問(wèn)題。裝備維修逆向物流是一個(gè)多階段物流網(wǎng)絡(luò)問(wèn)題(如圖1 所示)，其網(wǎng)絡(luò)節(jié)點(diǎn)由部隊(duì)用戶、收集/檢測(cè)點(diǎn)、維修點(diǎn)和報(bào)廢點(diǎn)組成。其中，收集/檢測(cè)點(diǎn)負(fù)責(zé)從部隊(duì)用戶處收集故障裝備或器材，經(jīng)過(guò)必要的檢測(cè)后，將故障裝備或器材分為可修復(fù)件和不可修復(fù)件;然后可修復(fù)件被送往維修點(diǎn)進(jìn)行維修，不可修復(fù)件則送往報(bào)廢點(diǎn)進(jìn)行相應(yīng)的報(bào)廢處置。問(wèn)題中，收集/檢測(cè)點(diǎn)、維修點(diǎn)和報(bào)廢點(diǎn)均有能力約束。逆向物流網(wǎng)絡(luò)優(yōu)化的目的是選擇合適的收集/檢測(cè)點(diǎn)，并確定網(wǎng)絡(luò)中各節(jié)點(diǎn)間的裝備或器材流量。

圖1 裝備維修逆向物流網(wǎng)絡(luò)結(jié)構(gòu)示意圖

為簡(jiǎn)化研究，在模型中作如下假設(shè):①?gòu)牟筷?duì)用戶返回的所有裝備或物資都必須收集;②部隊(duì)用戶的位置固定且已知;③維修點(diǎn)、報(bào)廢點(diǎn)的數(shù)量、位置和能力已知。

2.2 數(shù)學(xué)模型

模型中參變量及符號(hào)定義為:I為候選收集/檢測(cè)點(diǎn)集合;J為已知的修理點(diǎn)集合;K為已知的報(bào)廢點(diǎn)集合;L為已知的部隊(duì)用戶集合;r為平均報(bào)廢率;dl為部隊(duì)用戶l返回的物資數(shù)量;fi為開(kāi)設(shè)收集/檢測(cè)點(diǎn)i的固定成本;si為收集/檢測(cè)點(diǎn)i的安全系數(shù);cfli為從部隊(duì)用戶l到收集/檢測(cè)點(diǎn)i的單位運(yùn)輸成本;cmij為從收集/檢測(cè)點(diǎn)i到維修點(diǎn)j的單位運(yùn)輸成本;cdik為從收集/檢測(cè)點(diǎn)i到報(bào)廢點(diǎn)k的單位運(yùn)輸成本;pfi為收集/檢測(cè)點(diǎn)i的能力約束;pmj為維修點(diǎn)j的能力約束;pdk為報(bào)廢點(diǎn)k的能力約束。Xli為從部隊(duì)用戶l到收集/檢測(cè)點(diǎn)i的返回物資數(shù)量;Zij為從收集/檢測(cè)點(diǎn)i到維修點(diǎn)j的可修件數(shù)量;Wik為從收集/檢測(cè)點(diǎn)i到報(bào)廢點(diǎn)k的不可修件數(shù)量;Yi為變量，如果在位置i開(kāi)設(shè)收集/檢測(cè)點(diǎn)，則Yi =1，否則Yi =0。

模型中，目標(biāo)函數(shù)(1)為最小化逆向物流系統(tǒng)的總經(jīng)濟(jì)成本，其中第一項(xiàng)為收集/檢測(cè)點(diǎn)的開(kāi)設(shè)成本，第二項(xiàng)為物資從部隊(duì)用戶到收集/檢測(cè)點(diǎn)的總運(yùn)輸成本，第三項(xiàng)為可修件從收集/檢測(cè)點(diǎn)到維修點(diǎn)的總運(yùn)輸成本，第四項(xiàng)為不可修件從收集/檢測(cè)點(diǎn)到報(bào)廢點(diǎn)的總運(yùn)輸成本;目標(biāo)函數(shù)(2)為最大化系統(tǒng)的軍事效益，使系統(tǒng)中物資的安全性最大;約束(3)用以確保部隊(duì)用戶返回的所有物資都被收集;約束(4)和(5)用以保證收集/檢測(cè)點(diǎn)的流量平衡;約束(6)用以確保部隊(duì)用戶返回的物資只被送往開(kāi)設(shè)的收集/檢測(cè)點(diǎn)，且不超過(guò)收集/檢測(cè)點(diǎn)的能力限制;約束(7)和(8)用以保證送往維修點(diǎn)和報(bào)廢點(diǎn)的物資數(shù)量均不超過(guò)它們的能力限制;約束(9)和(10)定義了變量的取值范圍。

在上述軍事逆向物流網(wǎng)絡(luò)優(yōu)化模型中，目標(biāo)函數(shù)(2)是求安全性的最大值，為便于計(jì)算，在不影響優(yōu)化效果的前提下，可將該目標(biāo)修改為求目標(biāo)函數(shù)最小值的情況:

對(duì)上述多目標(biāo)優(yōu)化模型，本文采用如下方法將之轉(zhuǎn)化為單目標(biāo)優(yōu)化模型:

3 軍事逆向物流網(wǎng)絡(luò)優(yōu)化模型的優(yōu)化算法

由前可知，軍事逆向物流網(wǎng)絡(luò)優(yōu)化模型是一個(gè)混合整數(shù)規(guī)劃模型，變量、約束眾多，傳統(tǒng)的精確算法求解規(guī)模較大的此類問(wèn)題時(shí)效率較低，難以滿足解決實(shí)際問(wèn)題的需要。為此，本文采用遺傳算法對(duì)問(wèn)題進(jìn)行求解。

3.1 算法流程

應(yīng)用遺傳算法求解軍事逆向物流網(wǎng)絡(luò)優(yōu)化問(wèn)題首先初始化所用到的參數(shù);然后生成pop_size 個(gè)可行解構(gòu)成初始種群，并對(duì)各可行解進(jìn)行適應(yīng)度評(píng)估;接著利用各遺傳操作算子進(jìn)行迭代搜索，直到滿足預(yù)定的終止條件算法結(jié)束。在每步迭代過(guò)程中，算法按照輪盤賭策略從種群中隨機(jī)地選擇兩個(gè)個(gè)體，并將個(gè)體進(jìn)行交叉和變異，得到新的子個(gè)體。上述遺傳操作過(guò)程將進(jìn)行pop_size/2 次，得到的子個(gè)體在進(jìn)入種群的同時(shí)，種群中較差的(適應(yīng)度低的)個(gè)體將被淘汰，以保持種群規(guī)模不變。在每次迭代的最后，算法還將在種群中的最佳個(gè)體上應(yīng)用局部搜索過(guò)程，以加速算法收斂。另外，算法的終止規(guī)則設(shè)定為迭代固定的次數(shù)。

3.2 染色體表示及解碼方法

圖2 染色體表示示例

表1 解碼過(guò)程及結(jié)果

本文采用基于優(yōu)先級(jí)的編碼方法構(gòu)造軍事逆向物流網(wǎng)絡(luò)優(yōu)化模型的解。染色體由［L］+3［I］+［J］+［K］個(gè)正整數(shù)組成，其中［L］、［I］、［J］、［K］分別表示部隊(duì)用戶、候選收集/檢測(cè)點(diǎn)、維修點(diǎn)和報(bào)廢點(diǎn)的數(shù)量，各數(shù)字則分別表示對(duì)應(yīng)節(jié)點(diǎn)的優(yōu)先級(jí)。圖2 所示為一染色體示例，該示例由4 個(gè)部隊(duì)用戶、3 個(gè)候選收集/檢測(cè)點(diǎn)、3 個(gè)維修點(diǎn)和2 個(gè)報(bào)廢點(diǎn)組成。染色體分為三部分，第一部分表示部隊(duì)用戶和候選收集/檢測(cè)點(diǎn)之間的物資供給關(guān)系，第二部分表示候選收集/檢測(cè)點(diǎn)與維修點(diǎn)間的物資供給關(guān)系，最后一部分則表示候選收集/檢測(cè)點(diǎn)與報(bào)廢點(diǎn)間的物資供給關(guān)系。

對(duì)于上述基于優(yōu)先級(jí)的染色體表示方法，需要將之進(jìn)行解碼，以獲得各節(jié)點(diǎn)之間的物資供給關(guān)系。為便于說(shuō)明，以圖3 所示的單級(jí)染色體為例，介紹其解碼方法。圖3 中，(a)為染色體編碼，(b)為供應(yīng)方和需求方之間的運(yùn)輸成本，(c)為供需量及解碼后得到的物資供給關(guān)系(箭頭表示流向，其上數(shù)字表示流量)。具體解碼過(guò)程為:首先選擇優(yōu)先級(jí)最高的節(jié)點(diǎn)，圖3(a)中對(duì)應(yīng)為節(jié)點(diǎn)(供應(yīng)節(jié)點(diǎn)1);然后查找成本矩陣，找出該節(jié)點(diǎn)向?qū)?yīng)最低運(yùn)輸成本(min{13，17，16}= 13)所指向的節(jié)點(diǎn)(需求節(jié)點(diǎn)1);再根據(jù)兩個(gè)節(jié)點(diǎn)的供需量，在二者之間安排最大可能的物資供給(min{350，600}=350);繼續(xù)在染色體中尋找次高的優(yōu)先級(jí)，并按上述過(guò)程安排物資流。如此反復(fù)，直至所有需求都得到滿足，即完成解碼過(guò)程。圖3 所示算例，其解碼運(yùn)算過(guò)程及結(jié)果見(jiàn)表1。

圖3 染色體解碼方法示意圖

3.3 適應(yīng)度評(píng)估及初始種群的生成

染色體的適應(yīng)度反映了其所表示的解的質(zhì)量。在本文算法中，公式(12)所定義的目標(biāo)函數(shù)被用于評(píng)價(jià)染色體的適應(yīng)度。

初始種群中的個(gè)體均采用隨機(jī)生成的方法，即對(duì)染色體中的各級(jí)分別隨機(jī)生成長(zhǎng)度為［L］+［I］、［I］+［J］和［I］+［K］的數(shù)字串，經(jīng)解碼算法運(yùn)算后，計(jì)算相應(yīng)的適應(yīng)度值。

3.4 交叉算子

選擇算子得到的兩個(gè)父代個(gè)體將進(jìn)行交叉，以產(chǎn)生新的子個(gè)體。本文對(duì)各部分染色體均分別應(yīng)用相同的單點(diǎn)交叉方法，交叉所得到的兩個(gè)子個(gè)體中，選擇其中較優(yōu)的子個(gè)體進(jìn)入新種群。

3.5 變異算子

為避免遺傳搜索過(guò)程過(guò)早的陷入局部最優(yōu)解，算法以一定的概率進(jìn)行變異。變異方法較為簡(jiǎn)單:首先在各段染色體中均隨機(jī)選擇兩個(gè)編碼位，然后分別交換它們的位置，即可得到變異后的個(gè)體。

3.6 局部搜索過(guò)程

在每次迭代的最后，算法將應(yīng)用局部搜索過(guò)程對(duì)種群中的最佳個(gè)體進(jìn)行優(yōu)化，以加快算法收斂速度。局部搜索過(guò)程應(yīng)用2－opt 的思想，分別對(duì)各段染色體的任意兩個(gè)編碼位進(jìn)行交換操作，算法將嘗試所有可能的編碼位組合，以期發(fā)現(xiàn)更優(yōu)的個(gè)體。

4 計(jì)算實(shí)驗(yàn)及分析

4.1 算法實(shí)現(xiàn)及參數(shù)設(shè)置

本文所提出求解軍事逆向物流網(wǎng)絡(luò)優(yōu)化問(wèn)題的遺傳算法利用C 語(yǔ)言在Visual C ++.net 環(huán)境中實(shí)現(xiàn)。算法中的參數(shù)設(shè)置如下:種群規(guī)模pop_size =30，交叉和變異概率分別設(shè)為0.8 和0.1，算法終止條件為迭代300 代。

4.2 算例及計(jì)算結(jié)果

由于沒(méi)有可用的軍事逆向物流網(wǎng)絡(luò)優(yōu)化算例，本文自行設(shè)計(jì)了6 個(gè)算例，算例中，部隊(duì)用戶的規(guī)模分別是{50，60，70，80，90，100}，候選收集/檢測(cè)點(diǎn)的數(shù)量均為8 個(gè)，其開(kāi)設(shè)固定成本(fi =1000)均相同，各候選收集/檢測(cè)點(diǎn)的安全系數(shù)si ={0.05，0.08，0.1，0.12，0.15，0.18，0.22，0.1}，維修點(diǎn)和報(bào)廢點(diǎn)的數(shù)量均分別為5 和3，各節(jié)點(diǎn)的位置坐標(biāo)均在區(qū)間［0，100］內(nèi)隨機(jī)生成，節(jié)點(diǎn)之間的運(yùn)輸成本為相應(yīng)節(jié)點(diǎn)之間的歐幾里得距離，各部隊(duì)用戶的返回物資量為區(qū)間［1，10］范圍內(nèi)的隨機(jī)數(shù)，各收集/檢測(cè)點(diǎn)的能力上限各維修點(diǎn)的能力上限各報(bào)廢點(diǎn)的能力上限pdk平均報(bào)廢率r =0.2。

應(yīng)用所研究的算法，對(duì)上述各算例均獨(dú)立運(yùn)算10 次，得到的計(jì)算結(jié)果見(jiàn)表2。其中，第三列給出了10 次運(yùn)算中得到的最佳解的目標(biāo)函數(shù)值，第四列為10 次運(yùn)算結(jié)果的平均目標(biāo)函數(shù)值。

為驗(yàn)證算法性能，應(yīng)用所研究的遺傳算法求解了文獻(xiàn)［9］中的15 個(gè)有代表性的逆向物流網(wǎng)絡(luò)優(yōu)化基準(zhǔn)算例(算例基本情況見(jiàn)表3)，并將本文算法所得10 次獨(dú)立運(yùn)算的平均結(jié)果與文獻(xiàn)［9］中模擬退火算法的優(yōu)化結(jié)果進(jìn)行了比較(見(jiàn)表4)。從表4可知，在15 個(gè)算例中，本文算法求得的13 個(gè)算例的平均結(jié)果優(yōu)于文獻(xiàn)［9］中算法的計(jì)算結(jié)果。

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

表3 基準(zhǔn)算例基本情況［9］

表4 本文算法與文獻(xiàn)［9］中算法的平均計(jì)算結(jié)果比較

11 654823 659542 0.715 12 1112097 1115163 0.275 13 1573641 1582957 0.589 14 2189368 2205633 0.737 15 3079756 3098121 0.593

5 結(jié)束語(yǔ)

優(yōu)化的網(wǎng)絡(luò)結(jié)構(gòu)是軍事逆向物流系統(tǒng)高效運(yùn)行的關(guān)鍵。本文建立了軍事逆向物流網(wǎng)絡(luò)的優(yōu)化模型，研究了求解模型的遺傳算法并完成了算法程序設(shè)計(jì)。為驗(yàn)證算法性能，應(yīng)用本文算法求解了文獻(xiàn)［9］中的基準(zhǔn)算例，實(shí)驗(yàn)結(jié)果表明:所研究的算法具有比文獻(xiàn)［9］中的算法更高的精度。

［1］ 毛軍凌.軍事逆向物流及其發(fā)展策略研究［D］.北京:后勤指揮學(xué)院，2007.

［2］ 姜玉宏，樊玉強(qiáng)，顏華.基于物聯(lián)網(wǎng)技術(shù)的軍事逆向物流系統(tǒng)研究［J］.軍隊(duì)采購(gòu)與物流，2012(4):65 -67.

［3］ 張義桂，黎明.軍事逆向物流運(yùn)行機(jī)制淺析［J］.軍隊(duì)采購(gòu)與物流，2011(3):64 -66.

［4］ 任嵐燕，何婧.加強(qiáng)軍事逆向物流管理，建設(shè)資源節(jié)約型后勤［J］.軍隊(duì)采購(gòu)與物流，2009(3):65 -67.

［5］ 王亞楠，司玲玲，杜海艷.基于雙向反饋信息的逆向物流網(wǎng)絡(luò)優(yōu)化方法［J］.計(jì)算機(jī)仿真，2012，29(10):162 -164.

［6］ 高陽(yáng)，劉軍.基于第三方回收再制造逆向物流網(wǎng)絡(luò)設(shè)計(jì)［J］.計(jì)算機(jī)系統(tǒng)應(yīng)用，2013，22(7):16 -21.

［7］ 吳洪波，謝夢(mèng)星.汽車再制造逆向物流網(wǎng)絡(luò)模型研究［J］. 科技與管理，2014，16(2):80 -84.

［8］ 王雁鳳，黃有方.考慮居民選擇行為的過(guò)期藥品逆向物流網(wǎng)絡(luò)設(shè)計(jì)［J］.華中師范大學(xué)學(xué)報(bào)(自然科學(xué)版)，2015，49(1):52 -59.

［9］ NIKNEJAD A，PETROVIC D. Optimisation of integrated reverse logistics networks with different product recovery routes［J］. European Journal of Operational Research，2014，238(1):143 -154.

［10］ ROGHANIAN E，PAZHOHESHFAR P. An optimization model for reverse logistics network under stochastic environment by using genetic algorithm［J/OL］. ［2014 -09］http://dx. doi.org/10.1016/j.jmsy.2014.02.007.

［11］ PISHVAEE MS，KIANFAR K，KARIMI B. Reverse logistics network design using simulated annealing［J］. International Journal of Advanced Manufacturing Technology，2010，47:269-281.