江玉杰

（三江學(xué)院商學(xué)院，江蘇 南京 210012）

基于改進(jìn)Floyd算法的裝配供應(yīng)鏈網(wǎng)絡(luò)路徑選擇研究

江玉杰

（三江學(xué)院商學(xué)院，江蘇 南京 210012）

運(yùn)用Floyd算法從鏈上整體效益角度研究裝配供應(yīng)鏈網(wǎng)絡(luò)路徑選擇問(wèn)題，并綜合考慮響應(yīng)速度、服務(wù)質(zhì)量、物流成本對(duì)網(wǎng)絡(luò)路徑選擇的影響，引進(jìn)綜合修正因子，以改進(jìn)傳統(tǒng)Floyd算法。結(jié)合實(shí)例分析結(jié)果表明，運(yùn)用改進(jìn)Floyd算法選擇裝配供應(yīng)鏈最優(yōu)網(wǎng)絡(luò)路徑更加貼近現(xiàn)實(shí)、更加節(jié)省，從而增進(jìn)鏈上各節(jié)點(diǎn)企業(yè)之間的合作程度，最終實(shí)現(xiàn)裝配供應(yīng)鏈穩(wěn)健高效的運(yùn)行。

Floyd算法；裝配供應(yīng)鏈；網(wǎng)絡(luò)路徑選擇

0 前言

裝配供應(yīng)鏈?zhǔn)侵敢匝b配制造商為核心，集聚零部件供應(yīng)商、集配商、分銷商、零售商以及配送中心等相關(guān)輔助企業(yè)，為滿足顧客不同需求而形成的供需網(wǎng)絡(luò)。而裝配供應(yīng)鏈各節(jié)點(diǎn)企業(yè)，由于空間距離的限制、各企業(yè)的經(jīng)營(yíng)特點(diǎn)，需借助運(yùn)輸、配送等物流方式將所需調(diào)運(yùn)的物資按時(shí)送達(dá)指定的地點(diǎn)，此時(shí)所消耗的費(fèi)用高低、響應(yīng)速度的快慢、物流質(zhì)量的優(yōu)劣必然會(huì)影響裝配供應(yīng)鏈穩(wěn)定、高效的運(yùn)行。因此，合理、有效的裝配供應(yīng)鏈網(wǎng)絡(luò)路徑，能夠降低鏈上各節(jié)點(diǎn)企業(yè)之間的距離、降低物流成本、提高物流質(zhì)量，進(jìn)而提高供應(yīng)鏈的柔性，最終實(shí)現(xiàn)鏈上的整體收益大于各自單獨(dú)運(yùn)營(yíng)時(shí)所獲收益的總和[1]。

目前，專門研究裝配供應(yīng)鏈網(wǎng)絡(luò)路徑的文獻(xiàn)相對(duì)較少，文獻(xiàn)《基于時(shí)間Petri網(wǎng)的供應(yīng)鏈網(wǎng)絡(luò)關(guān)鍵路徑分析》[2]采用時(shí)間 Petri網(wǎng)研究供應(yīng)商、生產(chǎn)商、分配中心、零售商、顧客5級(jí)供應(yīng)鏈網(wǎng)絡(luò)關(guān)鍵路徑；文獻(xiàn)《基于VRP模型的兩階段物流網(wǎng)絡(luò)路徑優(yōu)化模型》[3]基于VRP模型研究供應(yīng)商、物流中心2級(jí)供應(yīng)鏈物流網(wǎng)絡(luò)最優(yōu)化路徑；文獻(xiàn)《動(dòng)態(tài)閉環(huán)復(fù)雜配送網(wǎng)絡(luò)路徑優(yōu)化算法研究》[4]將正向配送與逆向配送相結(jié)合，運(yùn)用動(dòng)態(tài)規(guī)劃算法研究閉環(huán)配送網(wǎng)絡(luò)最優(yōu)化路徑；文獻(xiàn)《基于復(fù)雜網(wǎng)絡(luò)理論的物流配送路徑優(yōu)化研究》[5]以復(fù)雜網(wǎng)絡(luò)理論為基礎(chǔ)，利用動(dòng)態(tài)規(guī)劃算法研究物流配送最優(yōu)化路徑；文獻(xiàn)《供應(yīng)鏈彈性綜合優(yōu)化路徑選擇模型分析》[6]根據(jù)木桶理論與效價(jià)理論找出供應(yīng)鏈中的彈性瓶頸，構(gòu)造供應(yīng)鏈彈性綜合優(yōu)化路徑；文獻(xiàn)《基于Floyd算法的供應(yīng)鏈網(wǎng)絡(luò)路徑研究》[7]以拉動(dòng)式生產(chǎn)為前提條件，運(yùn)用Floyd算法研究制造商、配送中心、銷售商3級(jí)供應(yīng)鏈網(wǎng)絡(luò)路徑優(yōu)化。

上述文獻(xiàn)采用不同的理論（時(shí)間Petri網(wǎng)、VRP模型、動(dòng)態(tài)規(guī)劃算法等）對(duì)供應(yīng)鏈中部分節(jié)點(diǎn)企業(yè)之間路徑進(jìn)行優(yōu)化，各有優(yōu)勢(shì)，但總體上僅局限于以最低物流成本為指標(biāo)選擇供應(yīng)鏈網(wǎng)絡(luò)路徑。鑒于此，本文將以改進(jìn)Floyd算法研究針對(duì)包含響應(yīng)速度、服務(wù)質(zhì)量、物流成本3項(xiàng)指標(biāo)的，由供應(yīng)商、集配商、制造商所組成的裝配供應(yīng)鏈網(wǎng)絡(luò)路徑選擇問(wèn)題。

1 問(wèn)題描述

1.1 研究對(duì)象

裝配供應(yīng)鏈中的核心企業(yè)即裝配制造商，依據(jù)TOC理論中關(guān)于生產(chǎn)企業(yè)分類原則屬于A型企業(yè)。而A型企業(yè)最大的特點(diǎn)是生產(chǎn)過(guò)程所需原材料種類很多，甚至有些零部件是最終產(chǎn)品的專用件（即屬于卡拉杰克模型中的戰(zhàn)略項(xiàng)目）。因而，裝配供應(yīng)鏈最大的特點(diǎn)是裝配制造商的某項(xiàng)需求將驅(qū)動(dòng)上游多家供應(yīng)商提前通過(guò)集配商的運(yùn)輸、配送等物流方式，將所需調(diào)運(yùn)的物資及時(shí)、有效的送到指定的地點(diǎn)?；诖?，本文研究3個(gè)供應(yīng)商、2個(gè)集配商、1個(gè)制造商所組成的裝配供應(yīng)鏈網(wǎng)絡(luò)路徑選擇問(wèn)題。所研究的裝配供應(yīng)鏈網(wǎng)絡(luò)路徑如圖1所示。

圖1 裝配供應(yīng)鏈網(wǎng)絡(luò)路徑

當(dāng)5者建立虛擬的動(dòng)態(tài)聯(lián)盟時(shí)，裝配制造商（M集）首先根據(jù)銷售商反饋的銷售信息，制定各區(qū)域生產(chǎn)計(jì)劃，利用多級(jí)滾動(dòng)計(jì)劃向S集（各供應(yīng)商）、H集（各集配商）發(fā)布物料需求計(jì)劃；其次，各供應(yīng)商根據(jù)制造商發(fā)布的生產(chǎn)計(jì)劃、各集配商反饋的庫(kù)存信息以及自身生產(chǎn)系統(tǒng)能力大小合理的組織零部件生產(chǎn)；再者，各集配商則會(huì)根據(jù)各供應(yīng)商的供貨批量大小合理的組織貨物的運(yùn)輸，并對(duì)其進(jìn)行集中管理，同時(shí)依據(jù)制造商的物料需求計(jì)劃將零部件配送至各生產(chǎn)部；當(dāng)遇到特殊情況時(shí)，并征求供應(yīng)商、制造商都同意的前提下，集配商之間可以相互調(diào)撥物資以滿足裝配制造商的需求[1]。在此運(yùn)作模式下，裝配供應(yīng)鏈便形成復(fù)雜交錯(cuò)的網(wǎng)絡(luò)路徑。

1.2 假設(shè)前提

在現(xiàn)實(shí)社會(huì)中，裝配供應(yīng)鏈各節(jié)點(diǎn)企業(yè)通常處于多條供應(yīng)鏈中，為了便于研究裝配供應(yīng)鏈網(wǎng)絡(luò)路徑選擇問(wèn)題，本文做出如下假設(shè)：

1）裝配供應(yīng)鏈各節(jié)點(diǎn)企業(yè)能實(shí)現(xiàn)信息完全共享且鏈條運(yùn)作正常。

2）S集中的各供應(yīng)商的供貨能力相同且無(wú)明顯限制，并通過(guò)H集中的集配商統(tǒng)一供貨給制造商各區(qū)域生產(chǎn)部。

3)在緊急情況下（如供應(yīng)商突發(fā)停產(chǎn)、自然災(zāi)害以及其他不可抗力情況等），并獲得其他供應(yīng)商以及制造商同意的情況下，集配商之間可以相互調(diào)撥物資。

4）裝配供應(yīng)鏈最優(yōu)網(wǎng)絡(luò)路徑選擇以綜合指標(biāo)值最小為衡量標(biāo)準(zhǔn)。

2 建立數(shù)學(xué)模型

2.1 基于傳統(tǒng)Floyd算法的網(wǎng)絡(luò)路徑選擇

Floyd算法，又稱弗洛伊登算法、插點(diǎn)法，是一種用于尋找給定的加權(quán)網(wǎng)絡(luò)圖中任意2個(gè)頂點(diǎn)之間最短路徑的算法，邊權(quán)可正可負(fù)[8]。

2.1.1 符號(hào)描述

本文所研究的裝配供應(yīng)鏈中涉及8個(gè)節(jié)點(diǎn)，根據(jù)Floyd算法原理可設(shè)：

1）供應(yīng)商1~3分別為v1、v2、v3，集配商1~2分別為v4、v5，裝配制造商中的生產(chǎn)部1~3分別為v6、v7、v8，則裝配供應(yīng)鏈網(wǎng)絡(luò)路徑中頂點(diǎn)的集合可表示為：V=｛v1,v2,v3,v4,v5,v6,v7,v8｝；

2）（vi,vj）表示一條從頂點(diǎn)vi（i=1,2,…,8）指向vj（j=1,2,…,8）的弧，則裝配供應(yīng)鏈網(wǎng)絡(luò)路徑中弧的集合可表示為：A=｛（vi,vj）｝。

3）裝配供應(yīng)鏈網(wǎng)絡(luò)路徑的權(quán)矩陣：D=（dij）8x8。

其中，d=lij表示：頂點(diǎn)vi到vj有直接相通的弧時(shí)，通過(guò)此路時(shí)所花費(fèi)的費(fèi)用；dij=∞表示；頂點(diǎn)頂點(diǎn)vi到vj沒有直接相通的弧時(shí)，無(wú)法通過(guò)此路，即想要通過(guò)此路時(shí)將花費(fèi)無(wú)窮大的費(fèi)用。進(jìn)而簡(jiǎn)化的裝配供應(yīng)鏈網(wǎng)絡(luò)路徑如圖2所示。

2.1.2 算法步驟[8]

1）根據(jù)裝配供應(yīng)鏈網(wǎng)絡(luò)各弧路權(quán)值（即通過(guò)此路所花費(fèi)的費(fèi)用），可寫出初始權(quán)矩陣D（0）=D。

圖2 簡(jiǎn)化的裝配供應(yīng)鏈網(wǎng)絡(luò)路徑

2）依次計(jì)算D（k）=（）8×8，其中d=min（k=1,2,…,8）。而（dij）（k）表示從頂點(diǎn)vi到vj取其直接有弧或借v1、v2、…vk、點(diǎn)為中間點(diǎn)時(shí)的最小費(fèi)用中的最小值[8]。

3）迭代到第8次即可得到裝配供應(yīng)鏈網(wǎng)絡(luò)路徑的最優(yōu)解，此時(shí)任意兩點(diǎn)間的最小費(fèi)用為：D（8）=（）8×8。值得注意的是在每次迭代時(shí)可保留下標(biāo)信息，既可給出每次迭代后任意兩點(diǎn)間的最小費(fèi)用，也可給出具體路徑的最低費(fèi)用。

2.2 基于改進(jìn)Floyd算法的網(wǎng)絡(luò)路徑優(yōu)化

運(yùn)用傳統(tǒng) Floyd算法選擇網(wǎng)絡(luò)路徑只是基于最低物流成本指標(biāo)，并沒有考慮因路徑的長(zhǎng)短導(dǎo)致裝配供應(yīng)鏈的響應(yīng)速度、物流質(zhì)量的差異。在現(xiàn)實(shí)社會(huì)中，任意兩點(diǎn)間的路長(zhǎng)與通過(guò)此路所花費(fèi)的費(fèi)用并不成正比。倘若僅以最低物流成本為指標(biāo)選擇網(wǎng)絡(luò)路徑，可能因路長(zhǎng)相對(duì)過(guò)遠(yuǎn)而使供應(yīng)商供貨提前期拉長(zhǎng)、集配商物流服務(wù)質(zhì)量下降、制造商因缺短貨而停工待產(chǎn)，致使影響裝配供應(yīng)鏈的穩(wěn)定性[6]。

為此，本文綜合考慮裝配供應(yīng)鏈的響應(yīng)速度、物流質(zhì)量的影響，引入通過(guò)vi到vj路物流費(fèi)用的綜合修正因子ij，并以lij+ij作為新的路權(quán)值。然后重新運(yùn)用傳統(tǒng)的Floyd算法求解，即通過(guò)8次迭代后便可求出裝配供應(yīng)鏈網(wǎng)絡(luò)路徑的最優(yōu)解。值得注意的是通過(guò)路徑仿真技術(shù)、先驗(yàn)數(shù)據(jù)挖掘技術(shù)等，可以在既定的置信區(qū)間內(nèi)估計(jì)求得綜合修正因子ij值。

3 實(shí)例分析

C.M汽車裝配集團(tuán)成立于1980年6月，座落在風(fēng)景秀麗的深圳。受到今年4、5月份汽車供銷量的下滑，加之原先部分零部件供應(yīng)商終止供貨，公司高層需要重新規(guī)劃零部件進(jìn)貨渠道。經(jīng)過(guò)幾月磋商，已建立新的裝配供應(yīng)鏈網(wǎng)絡(luò)路徑。目前，該公司的生產(chǎn)部1、2、3需進(jìn)一批零部件，可選進(jìn)貨路線如圖3所示。其中，各節(jié)點(diǎn)之間的物流費(fèi)用為每條弧上的權(quán)值，單位為萬(wàn)元；v1、v2、v3分別表示供應(yīng)商A、B、C；v4、v5分別表示集配商1、2；v6、v7、v8分別表示C.M汽車裝配集團(tuán)的生產(chǎn)部1、2、3。

3.1 背景資料

1）供應(yīng)商A、B、C向C.M汽車裝配集團(tuán)的生產(chǎn)部1、2、3供應(yīng)相同的零部件，即克萊斯勒發(fā)動(dòng)機(jī)、采埃孚自動(dòng)變速箱、普萊德電池，且產(chǎn)品性價(jià)比相當(dāng)。

圖3 裝配供應(yīng)鏈賦權(quán)網(wǎng)絡(luò)路徑

2）根據(jù)公司高層之間的磋商，集配商2可向集配商1調(diào)貨，但集配商1不可以向集配商2調(diào)貨，并約定供應(yīng)商向 C.M汽車裝配集團(tuán)生產(chǎn)部供貨需事先將零部件提前轉(zhuǎn)運(yùn)到集配商1、2處進(jìn)行統(tǒng)一管理，以便實(shí)現(xiàn)共同配送。

3）由于供應(yīng)商A所處地理位置因素，只能將零部件轉(zhuǎn)運(yùn)到集配商1處。4）因生產(chǎn)部2的生產(chǎn)規(guī)模相對(duì)較小，只需由集配商1負(fù)責(zé)配送零部件。

3.2 運(yùn)用傳統(tǒng)Floyd算法的網(wǎng)絡(luò)路徑選擇

1）基于傳統(tǒng)Floyd算法步驟，結(jié)合圖3數(shù)據(jù)，易得初始權(quán)矩陣。

3.3 運(yùn)用改進(jìn)Floyd算法的網(wǎng)絡(luò)路徑優(yōu)化

通過(guò)路徑仿真技術(shù)、先驗(yàn)數(shù)據(jù)挖掘技術(shù)，結(jié)合C.M汽車裝配集團(tuán)生產(chǎn)部進(jìn)貨路線的特點(diǎn)，易知通過(guò)vi到vj路物流費(fèi)用的綜合修正因子ij，并用lij+ij作為新的路權(quán)值，其變化情況如圖4所示。

1）基于傳統(tǒng)Floyd算法步驟，結(jié)合圖4數(shù)據(jù)，易得改進(jìn)后的初始權(quán)矩陣。

圖4 改進(jìn)后的裝配供應(yīng)鏈賦權(quán)網(wǎng)絡(luò)路徑

3.4 兩種路徑選擇的比較

把基于傳統(tǒng)Floyd算法的進(jìn)貨分配方案與基于改進(jìn)Floyd算法的的進(jìn)貨分配方案進(jìn)行比較，可以看出：1）運(yùn)用改進(jìn)Floyd算法進(jìn)行裝配供應(yīng)鏈網(wǎng)絡(luò)路徑選擇時(shí)，可以避免出現(xiàn)兩種或多種方案都符合篩選條件，以致影響領(lǐng)導(dǎo)層的決策力；2）運(yùn)用改進(jìn)Floyd算法所得進(jìn)貨方案是運(yùn)用傳統(tǒng)Floyd算法所得進(jìn)貨方案的子集，這樣可以縮小備選方案的數(shù)量，降低決策失誤的可能性；3）經(jīng)過(guò)對(duì)vi到vj路物流費(fèi)用的修正，所得綜合指標(biāo)值更能體現(xiàn)現(xiàn)實(shí)情況。因此，改進(jìn)后的進(jìn)貨方案更有助于供應(yīng)商、集配商以及裝配制造商之間的合作，從而間接地提高裝配供應(yīng)鏈穩(wěn)定高效的運(yùn)行，最終實(shí)現(xiàn)整體收益大于各自單獨(dú)運(yùn)營(yíng)時(shí)所獲收益的總和。

4 結(jié)語(yǔ)

從供應(yīng)鏈整體效益角度研究供應(yīng)商、集配商和制造商所構(gòu)成的裝配供應(yīng)鏈最優(yōu)網(wǎng)絡(luò)路徑選擇問(wèn)題。綜合考慮三維虛擬動(dòng)態(tài)聯(lián)盟網(wǎng)絡(luò)路徑選擇的影響因素，對(duì)傳統(tǒng) Floyd算法進(jìn)行改進(jìn)，采用兼顧供貨提前期、物流質(zhì)量以及物流成本的網(wǎng)絡(luò)路徑優(yōu)化方案。實(shí)例分析表明，改進(jìn)的 Floyd算法選擇最優(yōu)網(wǎng)絡(luò)路徑更加貼近現(xiàn)實(shí)，從而保證裝配供應(yīng)鏈穩(wěn)健牢固運(yùn)行。

總體而言，運(yùn)用改進(jìn)的 Floyd算法選擇最優(yōu)網(wǎng)絡(luò)路徑，對(duì)裝配供應(yīng)鏈的進(jìn)一步研究具有一定的指導(dǎo)意義，對(duì)汽車、造船等企業(yè)具有一定的現(xiàn)實(shí)應(yīng)用價(jià)值。但不可否認(rèn)，對(duì)到路的物流費(fèi)用的綜合修正因子的確定需進(jìn)一步的研究。

[1]江玉杰.基于改進(jìn)Shapley值法的裝配供應(yīng)鏈?zhǔn)找娣峙溲芯縖J].山東交通學(xué)院學(xué)報(bào)，2015(01)：36-40.

[2]劉振峰,陳燕.基于時(shí)間Petri網(wǎng)的供應(yīng)鏈網(wǎng)絡(luò)關(guān)鍵路徑分析[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2006(11)：32-37.

[3]陳岱蓮,李鵬.基于VRP模型的兩階段物流網(wǎng)絡(luò)路徑優(yōu)化模型[J].重慶交通大學(xué)學(xué)報(bào)(自然科學(xué)版)，2009(06)：1131-1134.

[4]張旭鳳,張永安,楊麗.動(dòng)態(tài)閉環(huán)復(fù)雜配送網(wǎng)絡(luò)路徑優(yōu)化算法研究[J].中國(guó)流通經(jīng)濟(jì)，2010(04)：34-37.

[5]曾云,劉宗武.基于復(fù)雜網(wǎng)絡(luò)理論的物流配送路徑優(yōu)化研究[J].物流技術(shù)，2011(17)：113-114.

[6]劉家國(guó),周粵湘,李俊,等.供應(yīng)鏈彈性綜合優(yōu)化路徑選擇模型分析[J].哈爾濱工業(yè)大學(xué)學(xué)報(bào)，2014(05)：101-106.

[7]樓振凱.基于Floyd算法的供應(yīng)鏈網(wǎng)絡(luò)路徑研究[J].物流工程與管理，2014(05)：127-128.

[8]胡運(yùn)權(quán).運(yùn)籌學(xué)教程（第二版）[M].北京:清華大學(xué)出版社,2003:226-228.

Research of Network Path Selection of Assembly Supply Chain Based on Floyd Algorithm Improvement

JIANG Yu-jie
(School of Business,Sanjiang University,Nanjing 210012,China)

This paper studies the network path selection of assembly supply chain from the overall efficiency on the chain by using Floyd algorithm.By taking the effect of the response speed,service quality and logistics costonnetworkpathintoconsideration,comprehensivecorrectionfactorshavebeenintroducedsoastoimprove the traditional Floyd algorithm.Based on the example analysis,the result shows that it is closer to reality and moreeconomicalto use theimprovedFloyd algorithmto choosetheoptimalnetwork path,which mayenhance the cooperation between each node in the chain of enterprises and finally realize the stable and efficient operation of assembly supply chain.

Floyd algorithm;assembly supply chain;network path selection

TP301.6

A

1674-2346(2015)04-0067-06

(責(zé)任編輯：田 犇)

10.3969/j.issn.1674-2346.2015.04.014

2015－08－23

江玉杰，男。研究方向：供應(yīng)鏈管理