基于 Floyd 算法的制造/再制造閉環(huán)物流網(wǎng)絡(luò)優(yōu)化

段麗梅,唐克生,李依蓉,王藝丹

(昆明冶金高等?？茖W(xué)校商學(xué)院，云南 昆明 650033)

0 引 言

我國的《物流術(shù)語》中將逆向物流定義為“不合格物品的返回、維修以及周轉(zhuǎn)使用的包裝容器，從需求方返回到供應(yīng)方所形成的回收物流和將經(jīng)濟(jì)活動(dòng)中失去原有使用價(jià)值的物品，根據(jù)實(shí)際需要進(jìn)行收集、分類、加工、包裝、搬運(yùn)和儲(chǔ)存，并分送到專門處理場(chǎng)所時(shí)所形成的廢棄物物流”。逆向物流根據(jù)不同的處理方式、不同的回流節(jié)點(diǎn)可以分為再制造、再利用、再循環(huán)和廢棄處理等方式[1]，如圖1所示。

圖1 逆向物流不同的處理方式Fig.1 Different treatment methods of reverse logistics

本文僅討論逆向物流中的再制造類型。再制造網(wǎng)絡(luò)通常針對(duì)具有較高回收價(jià)值的電子產(chǎn)品，汽車，電器等部件。再制造物流包含將廢舊產(chǎn)品從消費(fèi)地運(yùn)回生產(chǎn)地的逆向物流，以及將再制造產(chǎn)品從生產(chǎn)地運(yùn)往消費(fèi)地的正向物流，涉及廢舊產(chǎn)品收集、檢測(cè)/分類、再制造和再分銷等諸多環(huán)節(jié)，是一種閉環(huán)物流。

在逆向物流所涉及的各種處理方式中，再制造逆向物流網(wǎng)絡(luò)研究是熱點(diǎn)，很多學(xué)者針對(duì)再制造逆向物流網(wǎng)絡(luò)設(shè)計(jì)進(jìn)行了研究。Lee等[2]給出了一個(gè)再制造系統(tǒng)三層物流網(wǎng)絡(luò)設(shè)計(jì)模型，目標(biāo)確定為逆向物流中的運(yùn)輸成本和固定成本之和最小，為求解模型，提出了一個(gè)改進(jìn)的基于權(quán)重進(jìn)行編碼和運(yùn)用新的交叉算子的遺傳算法。Zarei等[3]研究生產(chǎn)商延伸責(zé)任制下的報(bào)廢車輛再制造逆向物流網(wǎng)絡(luò)設(shè)計(jì)，將新車的配送和報(bào)廢汽車的回收結(jié)合起來考慮，假設(shè)新汽車的配送商也負(fù)責(zé)報(bào)廢汽車的回收，建立了建設(shè)成本以及相關(guān)的運(yùn)輸成本最小化網(wǎng)絡(luò)設(shè)計(jì)模型，最后設(shè)計(jì)了遺傳算法對(duì)模型求解。Alumur等[4]研究可再制造產(chǎn)品的逆向物流網(wǎng)絡(luò)設(shè)計(jì)，包括報(bào)廢的電腦、洗衣機(jī)、烘干機(jī)等，指出企業(yè)如果只關(guān)注于生產(chǎn)商延伸責(zé)任，則將逆向物流外包給第三方。王圣池等[5]研究了跨國企業(yè)再制造逆向物流網(wǎng)絡(luò)布局，并考慮了物流網(wǎng)絡(luò)運(yùn)營收益和物流績效指標(biāo)雙目標(biāo)。馬祖軍等[6]對(duì)再制造逆向物流與正向物流網(wǎng)絡(luò)的集成優(yōu)化設(shè)計(jì)進(jìn)行了研究，建立了混合整數(shù)非線性規(guī)劃模型，其重點(diǎn)在于集成制造系統(tǒng)與再制造系統(tǒng)的正向-逆向物流網(wǎng)絡(luò)。

制造/再制造物流網(wǎng)絡(luò)的優(yōu)化設(shè)計(jì)，就是根據(jù)流通總成本最小化的原則，來確定每一件產(chǎn)品和廢舊回收品的流通渠道。本文提出了一種基于Floyd算法的物流網(wǎng)絡(luò)優(yōu)化選擇模型，在考慮正向物流設(shè)施能力限制的條件下，選擇一條總成本最小的流通路徑，使得整個(gè)物流網(wǎng)絡(luò)的流通總成本最小。物流設(shè)施的運(yùn)營能力限制通常會(huì)出現(xiàn)在正向物流網(wǎng)絡(luò)中，逆向物流由于物流量通常較小，故不需要考慮設(shè)施的能力限制。

1 模型描述

本文改進(jìn)的Floyd算法模型僅計(jì)算兩設(shè)施之間的最小總成本，未考慮設(shè)施能力限制因素。為了模型計(jì)算的簡便和準(zhǔn)確，特作如下假設(shè)。

1.1 模型假設(shè)

1)僅考慮回收再制造一種廢舊產(chǎn)品，且通過回收中心進(jìn)行回收，正/逆向物流共用設(shè)施，即同一生產(chǎn)企業(yè)可以生產(chǎn)新產(chǎn)品和循環(huán)產(chǎn)品，新產(chǎn)品分銷中心同時(shí)也是廢舊產(chǎn)品回收中心，新產(chǎn)品的末端配送中心可以是廢舊產(chǎn)品回收點(diǎn)。

2)各設(shè)施運(yùn)營成本、設(shè)施間的運(yùn)輸成本等是確定的和已知的。

3)不同的生產(chǎn)企業(yè)都可以對(duì)回收產(chǎn)品再制造，即存在A產(chǎn)地生產(chǎn)的產(chǎn)品回收至B產(chǎn)地再制造的情況。

4)不考慮原材料供應(yīng)環(huán)節(jié)。

1.2 算法說明

我們將整個(gè)制造/再制造系統(tǒng)以圖的方式來簡化表達(dá)，節(jié)點(diǎn)代表設(shè)施，節(jié)點(diǎn)間的連線代表物流運(yùn)輸，連線上的數(shù)值代表兩設(shè)施節(jié)點(diǎn)間的單件運(yùn)輸成本。

我們采用改進(jìn)的Floyd算法[7-8]來計(jì)算制造/再制造閉環(huán)物流網(wǎng)絡(luò)中所有設(shè)施頂點(diǎn)對(duì)之間的最小運(yùn)營和運(yùn)輸成本。Floyd算法是一種基于迭代思想的動(dòng)態(tài)規(guī)劃算法，本文增加了設(shè)施的運(yùn)營成本(比如企業(yè)的生產(chǎn)成本和分銷中心的周轉(zhuǎn)成本)，算法也相應(yīng)地作出了改進(jìn)。算法的主要部分如下：

聲明并初始化成本代價(jià)矩陣C(0)[i][j]，正向物流設(shè)施運(yùn)營成本數(shù)組F[k]，逆向物流設(shè)施運(yùn)營成本數(shù)組R[k]。

for(i=1;i=G.vnum();i++)

for(j=1;j=G.vnum();j++)

if(i==j){C[i][j].cost=0;}

if(i>j){C[i][j].cost=R[i]+C[i][j]+R[j];}

C[i][j].cost=F[i]+C[i][j]+F[j];//C(0)[i][j]直達(dá)兩節(jié)點(diǎn)間賦初值for(k=0;k

for(i=0;i

for(j=i;jC[i][k].cost +C[k][j].cost+F[k])

{C[i][j].cost=C[i][k].cost+C[k][j].cost+F[k];

C[i][j].pre=k;}//正向物流部分

for(j=i;j==0;j--)

if(C[i][j].cost>C[i][k].cost +C[k][j].cost+R[k])

{C[i][j].cost=C[i][k].cost+C[k][j].cost+R[k];

C[i][j].pre=k;}//逆向物流部分其中，G.vnum()為節(jié)點(diǎn)數(shù)函數(shù)，C[i][j].cost為節(jié)點(diǎn)Vi與節(jié)點(diǎn)Vj之間的運(yùn)輸成本代價(jià)，C[i][j].pre為存儲(chǔ)節(jié)點(diǎn)Vi與節(jié)點(diǎn)Vj之間的前驅(qū)節(jié)點(diǎn)(跳節(jié)點(diǎn))。根據(jù)模型運(yùn)行結(jié)果，可以得出所有節(jié)點(diǎn)對(duì)(兩設(shè)施)之間的最小總成本，計(jì)算一次循環(huán)(產(chǎn)品/廢舊品的正向/逆向物流完成)所經(jīng)過的各個(gè)設(shè)施的各種可能路徑的總成本，通過比較得出其中一條總成本最小路徑，算出最小成本，并給出本次循環(huán)的途經(jīng)設(shè)施節(jié)點(diǎn)順序。

2 算法仿真

某產(chǎn)品制造商已經(jīng)建設(shè)有一個(gè)制造/再制造集成物流網(wǎng)絡(luò)，現(xiàn)需要對(duì)現(xiàn)有網(wǎng)絡(luò)的流通渠道進(jìn)行優(yōu)化設(shè)計(jì)。已知有2處生產(chǎn)地，3個(gè)分銷物流中心/回收中心(正/逆向物流共用)，3個(gè)消費(fèi)地配送中心/回收點(diǎn)(正/逆向物流共用)，它們的設(shè)施處理/需求能力、運(yùn)營成本和符號(hào)表示如表1所示。在正向物流過程中，我們對(duì)部分設(shè)施的能力上限作了設(shè)定，逆向物流由于通常物流量均較小，在此不予考慮。

表1 集成物流網(wǎng)絡(luò)的設(shè)施運(yùn)營成本、處理/需求能力Tab.1 Facility operating cost,processing/demand capacity of integrated logistics network

續(xù)表Continued

集成物流網(wǎng)絡(luò)示意如圖2所示，節(jié)點(diǎn)間的連線表示運(yùn)輸，單件運(yùn)輸成本用數(shù)字標(biāo)注在連線上，無符號(hào)線段表示雙向運(yùn)輸?shù)某杀鞠嗤?，有向線段表示雙向運(yùn)輸?shù)某杀静煌?，其中括?hào)外數(shù)字表示正向物流的單件成本，括號(hào)內(nèi)數(shù)字表示逆向物流的單件成本。

圖2 集成物流網(wǎng)絡(luò)Fig.2 Integrated logistics network

接下來進(jìn)行集成網(wǎng)絡(luò)優(yōu)化。過程如下：

步驟1 根據(jù)Floyd算法，得出初始成本代價(jià)矩陣C0(i,j)(表2)、前驅(qū)節(jié)點(diǎn)矩陣P0(i,j)(表3)、正向物流設(shè)施運(yùn)營成本數(shù)組F[i]={5,4.5,2,1,1,1,1,1}、逆向物流設(shè)施運(yùn)營成本數(shù)組R[i]={4,3,1.5,0.5,1,2,2,2.5}。其中，V1→V3的單件成本為正向運(yùn)輸成本與兩端節(jié)點(diǎn)V1、V3的正向物流設(shè)施成本之和，即：5+3+2=10；V3→V1 的單件成本為逆向運(yùn)輸成本與兩端節(jié)點(diǎn)V1、V3的逆向物流設(shè)施成本之和，即：1.5+3+4=8.5；同一節(jié)點(diǎn)間不發(fā)生位移，成本為 0；因?yàn)橥粚蛹?jí)的節(jié)點(diǎn)間不發(fā)生聯(lián)系，故它們之間的運(yùn)輸成本為無窮，比如V1→V2，用符號(hào)“∝”表示；初始矩陣中，非直接相連的節(jié)點(diǎn)間的運(yùn)輸成本因?yàn)闀翰豢蛇_(dá)，記為近似無窮，比如V1→V6，用符號(hào)“∞”表示。

表2 初始成本代價(jià)矩陣C0(i,j)Tab.2 Initial cost cost matrix C0(i，j)

表3 初始前驅(qū)節(jié)點(diǎn)矩陣P0(i,j)Tab.3 Initial precursor node matrix P0(i,j)

步驟2 按照算法，應(yīng)該從V1節(jié)點(diǎn)開始更新2個(gè)矩陣。本例中，由于V1、V2和V6、V7、V8 為網(wǎng)絡(luò)的起止節(jié)點(diǎn)，同層節(jié)點(diǎn)之間無連線，且非相鄰層之間節(jié)點(diǎn)也無連線(與實(shí)際的物流系統(tǒng)相符)，故只需考慮從中間層節(jié)點(diǎn)V3、V4、V5開始更新矩陣即可。經(jīng)過中間節(jié)點(diǎn)V3更新后，得到了單件成本矩陣C3(i,j)(表4)和前驅(qū)節(jié)點(diǎn)矩陣P3(i,j)(表5)。

表4 成本代價(jià)矩陣C3(i,j)Tab.4 Cost cost matrix C3(i,j)

表5 前驅(qū)節(jié)點(diǎn)矩陣P3(i,j)Tab.5 Precursor node matrix P3(i,j)

其中，V1→V6的值經(jīng)過V3節(jié)點(diǎn)中轉(zhuǎn)后，更新為15，即V1→V3→V6的值為V1→V3的值10加上V3→V6的值7減去2(V3的運(yùn)營成本多算了一次)，同時(shí)前驅(qū)節(jié)點(diǎn)矩陣中V1→V6的值更新為3(V3的節(jié)點(diǎn)序號(hào))。同理，V6→V1的值經(jīng)過V3節(jié)點(diǎn)中轉(zhuǎn)后，更新為13.5，同時(shí)前驅(qū)節(jié)點(diǎn)矩陣中V6→V1的值更新為3。

步驟3 經(jīng)過中間節(jié)點(diǎn)V4更新后，得到了單件成本矩陣C4(i,j)(表6)和前驅(qū)節(jié)點(diǎn)矩陣P4(i,j)(表7)。其中，V1→V8的值經(jīng)過V4節(jié)點(diǎn)中轉(zhuǎn)后，更新為14，同時(shí)前驅(qū)節(jié)點(diǎn)矩陣中V1→V8的值更新為4，即V1→V4→V8的值為14，而V1→V3→V8的值為16，根據(jù)算法，取小值。

表6 成本代價(jià)矩陣C4(i,j)Tab.6 Cost cost matrix C4(i,j)

表7 前驅(qū)節(jié)點(diǎn)矩陣P4(i,j)Tab.7 Precursor node matrix P4(i,j)

步驟4 經(jīng)過中間節(jié)點(diǎn)V5更新后，得到了單件成本矩陣C5(i,j)(表8)和前驅(qū)節(jié)點(diǎn)矩陣P5(i,j)(表9)。

表8 成本代價(jià)矩陣C5(i,j)Tab.8 Cost cost matrix C5(i，j)

表9 前驅(qū)節(jié)點(diǎn)矩陣P5(i,j)Tab.9 Precursor node matrix P5(i,j)

根據(jù)結(jié)果分析，V1→V6的值為12.5(中轉(zhuǎn)節(jié)點(diǎn)為V5)，V2→V6的值為13(中轉(zhuǎn)節(jié)點(diǎn)為V5)，故于V6而言，最優(yōu)單件成本12.5,順序?yàn)閂1→V5→V6。網(wǎng)絡(luò)優(yōu)化結(jié)果見表10。

表10 未考慮設(shè)施能力限制的優(yōu)化結(jié)果Tab.10 Optimization results that do not take into account facility capacity limitations

步驟5 考慮設(shè)施能力限制，給出最終優(yōu)化結(jié)果。我們僅以正向物流為例來加以考慮。我們以末端需求量為基準(zhǔn)來考慮流通渠道中的設(shè)施能力限制，本例以配送中心V6、V7、V8的處理/需求能力為基準(zhǔn)，根據(jù)給出的未考慮設(shè)施能力限制的優(yōu)化結(jié)果，按照最優(yōu)單件成本從低到高的順序?qū)ζ湟来芜M(jìn)行分析。根據(jù)表10的優(yōu)化結(jié)果，最優(yōu)單件成本最低為V8，V6和V7的單件成本相同。我們給出2個(gè)組合方案，分別為方案1(依次分析V8、V6、V7的需求)和方案2(依次分析V8、V7、V6的需求)。以方案1為例闡述如下：

V8需求量為 20 000 件，未考慮設(shè)施能力限制，最優(yōu)解為V2→V4→V8(單件成本11.5元)，V4無限制，V2能力為 40 000 件，即V2生產(chǎn)能力中的 20 000 件經(jīng)V4送達(dá)V8。V6需求量為 50 000 件，未考慮能力限制，最優(yōu)路徑為V1→V5→V6(單件成本12.5元)，其中，V1無能力限制，V5能力上限為 40 000 件，也即V6的需求中 40 000 件選擇最優(yōu)路徑V1→V5→V6，V6需求尚欠 10 000 件。從表8來分析，次優(yōu)解為V2→V5→V6(單件成本13元)，由于同樣經(jīng)過V5節(jié)點(diǎn)，所以此條路徑仍然不可行。接下來，從表6分析，V2→V4→V6(單件成本13.5元)為次優(yōu)解，V4無能力限制，V2生產(chǎn)能力尚余 20 000 件，即V2生產(chǎn)能力中的 10 000 件，經(jīng)過V4送達(dá)V6，也即對(duì)于V6而言，流通渠道有2條，分別是V1→V5→V6和V2→V4→V6。V7需求量為 30 000 件，最優(yōu)解為V2→V4→V7(單件成本12.5)，V2生產(chǎn)能力尚余 10 000 件，經(jīng)過V4送達(dá)V7。V7需求尚欠 20 000 件，從表8可以看出，次優(yōu)解為V1→V3→V7(單件成本14)，V1和V3均無能力限制，即V1生產(chǎn) 20 000 件經(jīng)V3送達(dá)V7，對(duì)于V7而言，流通渠道有2條，分別是V2→V4→V7和V1→V3→V7。方案1的正向物流流通總成本為127萬元。

以此類推，方案2的正向物流流通總成本為127萬元。即方案1和方案2的總成本相同。具體結(jié)果如表11所示。

表11 考慮設(shè)施能力限制的正向物流優(yōu)化結(jié)果Tab 11 Results of forward logistics optimization considering facility capacity constraints

3 結(jié) 語

正/逆向物流集成的制造/再制造網(wǎng)絡(luò)中，網(wǎng)絡(luò)優(yōu)化的目的就是根據(jù)某一方面的考量來選擇最優(yōu)的流通渠道?；贔loyd算法的制造/再制造網(wǎng)絡(luò)優(yōu)化，可以基于成本因素，也可以基于時(shí)間因素來進(jìn)行渠道優(yōu)化?？紤]到設(shè)施處理能力限制，通常以末端需求量為基準(zhǔn)來考慮流通渠道中的設(shè)施能力情況，選擇符合條件的最優(yōu)路徑。與整數(shù)線性規(guī)劃模型相比，F(xiàn)loyd算法建模簡單，算法清晰，可以通過編程將其融入現(xiàn)有的物流信息系統(tǒng)，讓系統(tǒng)自動(dòng)做出選擇。