最小費(fèi)用最大流模型在運(yùn)輸網(wǎng)絡(luò)優(yōu)化中的應(yīng)用

郭京生　劉璘

摘要：運(yùn)用圖論的相關(guān)理論知識(shí)，針對(duì)物流系統(tǒng)中運(yùn)輸網(wǎng)絡(luò)的特點(diǎn)，以最大限度的提高運(yùn)輸效率，同時(shí)以節(jié)約運(yùn)輸總成本為目標(biāo)，提出了解決運(yùn)輸網(wǎng)絡(luò)優(yōu)化問(wèn)題的最小費(fèi)用最大流網(wǎng)絡(luò)模型，并利用matlab編程實(shí)現(xiàn)，為優(yōu)化物流運(yùn)輸網(wǎng)絡(luò)路線提供了一種可行方法。

關(guān)鍵詞：運(yùn)輸網(wǎng)絡(luò)；最小費(fèi)用最大流；網(wǎng)絡(luò)流量；matlab

中圖分類號(hào)：F25文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：16723198（2015）17005302

0引言

運(yùn)輸作為現(xiàn)代物流過(guò)程的主要職能之一，是物流各項(xiàng)業(yè)務(wù)的中心活動(dòng)。同時(shí)，運(yùn)輸產(chǎn)生的費(fèi)用也是供應(yīng)鏈和整個(gè)物流系統(tǒng)成本結(jié)構(gòu)的重要組成部分。可以說(shuō)，一個(gè)高效率、低成本和高反應(yīng)能力的運(yùn)輸網(wǎng)絡(luò)對(duì)一個(gè)成功的物流配送體系至關(guān)重要，這就使得運(yùn)輸網(wǎng)絡(luò)的優(yōu)化成為配送體系中一項(xiàng)重要的運(yùn)營(yíng)決策，關(guān)系到物流設(shè)計(jì)體系的成功與否。運(yùn)輸網(wǎng)絡(luò)的優(yōu)化主要是對(duì)運(yùn)輸路線的安排，即選擇合理的配送路線，既能保證配送效率的最大化，又能同時(shí)使運(yùn)輸成本最低。

圖論是運(yùn)籌學(xué)中一個(gè)重要的分支，是用來(lái)描述運(yùn)輸網(wǎng)絡(luò)的數(shù)學(xué)理論基礎(chǔ)。本文基于圖論的相關(guān)理論知識(shí)，針對(duì)物流運(yùn)輸中最小費(fèi)用最大流問(wèn)題，建立了基于matlab的優(yōu)化數(shù)學(xué)模型，以求最大限度的提高運(yùn)輸效率，同時(shí)節(jié)約運(yùn)輸費(fèi)用。

1最小費(fèi)用最大流模型

1.1網(wǎng)絡(luò)流量基本概念及定義

為了實(shí)現(xiàn)對(duì)網(wǎng)絡(luò)流量最大流值和最低成本的優(yōu)化，首先需明確幾個(gè)基本定義：

定義1：容量—費(fèi)用網(wǎng)絡(luò)。給定一個(gè)有向圖D=V，A，對(duì)任意的弧vi，vj∈A，設(shè)lij，uij為弧的運(yùn)輸容量上下界函數(shù)，其中0≤lij≤uij，也稱uij為弧的容量；cij是弧vi，vj上單位流量的費(fèi)用，稱之為費(fèi)用函數(shù)；對(duì)任意的節(jié)點(diǎn)vi∈V，稱avi為節(jié)點(diǎn)vi的供應(yīng)量或需求量，稱之為供需函數(shù)，且滿足vi∈Va（vi）=0。由此得到的網(wǎng)絡(luò)稱為容量—費(fèi)用網(wǎng)絡(luò)。

定義2：可行流及其總費(fèi)用。設(shè)fij是給定網(wǎng)絡(luò)N上的由節(jié)點(diǎn)vi到節(jié)點(diǎn)vj的一個(gè)流量，且滿足：

f+（vi）-f-（vi）=f（vi）

lij≤fij≤uij （1）

式中，f+vi=vj∈Vfij，f-vi=vj∈Vfji，分別稱為流出和流入節(jié)點(diǎn)vi的流量，fvi為該節(jié)點(diǎn)的凈輸出量。

當(dāng)滿足式（1）時(shí)，則稱f=fij為網(wǎng)絡(luò)N 上的一個(gè)可行流，且可行流f的總費(fèi)用為

c（f）=（vi，vj）∈Acijfij （2）

1.2最小費(fèi)用問(wèn)題概念及數(shù)學(xué)模型

最小費(fèi)用問(wèn)題是物流運(yùn)輸網(wǎng)絡(luò)優(yōu)化的核心問(wèn)題，目標(biāo)是在滿足供應(yīng)條件的前提下，尋求供應(yīng)網(wǎng)絡(luò)總成本最小的最優(yōu)解。

根據(jù)上述定義，最小費(fèi)用問(wèn)題屬于線性規(guī)劃問(wèn)題。其數(shù)學(xué)模型如下：

min z=c（f）=（vi，vj）∈Acijfij （3）

約束條件為式（1）。

其中，目標(biāo)函數(shù)是通過(guò)網(wǎng)絡(luò)N供應(yīng)的總成本最小。決策變量fij指通過(guò)弧vi，vj的流量。約束條件有供應(yīng)點(diǎn)的凈流量（總流出量減去總流入量）為正，所有需求點(diǎn)的凈流量為負(fù)，對(duì)于所有中轉(zhuǎn)點(diǎn)（中間點(diǎn)）的凈流量為0，所有弧的流量受到弧的容量lij，uij的限制，且弧的流量為非負(fù)。

1.3最大流問(wèn)題概念及數(shù)學(xué)模型

最大流問(wèn)題也與網(wǎng)絡(luò)中的流有關(guān)，但是其優(yōu)化目標(biāo)與最小費(fèi)用流不同，最大流問(wèn)題是尋求一個(gè)可行流的方案，使得通過(guò)網(wǎng)絡(luò)的流量最大。

根據(jù)最大流問(wèn)題的概念，最大流問(wèn)題也屬于線性規(guī)劃問(wèn)題。其數(shù)學(xué)模型如下：

max z=fvs （4）

除滿足約束條件式（1）外，還應(yīng)滿足式（5）：

f+（vi）-f-（vi）=fvs，i=s（源）

-fvs，i=t（匯）

0，i≠s，t（中轉(zhuǎn)點(diǎn)）（5）

其中，目標(biāo)函數(shù)是通過(guò)供應(yīng)點(diǎn)vs的凈流出量f（vs）（或需求點(diǎn)vt的凈流入量f（vt））最大，決策變量是通過(guò)各個(gè)弧的流量fij，約束條件有所有中轉(zhuǎn)點(diǎn)的凈流量為0，所有弧的流量受到弧的容量lij，uij的限制，且弧的流量為非負(fù)。

1.4最小費(fèi)用最大流問(wèn)題概念及數(shù)學(xué)模型

前面小節(jié)中介紹的“最小費(fèi)用流問(wèn)題”的目標(biāo)是在完成規(guī)定任務(wù)的條件下，使得網(wǎng)絡(luò)供應(yīng)的總成本最小，即解決流量一定成本最小的路線安排問(wèn)題?！白畲罅鲉?wèn)題”的目標(biāo)是尋求一個(gè)可行流的方案，使得通過(guò)供應(yīng)網(wǎng)絡(luò)的流量最大，即不考慮成本的情況下，解決單純的流量最大的路線安排問(wèn)題。但是實(shí)際情況往往比較復(fù)雜，不僅考慮流量還需要兼顧費(fèi)用。例如，物流系統(tǒng)中一個(gè)運(yùn)輸網(wǎng)絡(luò)，不僅要爭(zhēng)取網(wǎng)絡(luò)中貨運(yùn)量最大，還要力求使總費(fèi)用最小，即解決更貼合實(shí)際的流量最大成本最低的路線安排問(wèn)題，這就是“最小費(fèi)用最大流問(wèn)題”。

因此，我們可以把“最小費(fèi)用最大流問(wèn)題”看成是“最小費(fèi)用流問(wèn)題”和“最大流問(wèn)題”的結(jié)合。求解該問(wèn)題自然可以分為兩步：首先，按照“最大流量問(wèn)題”的求解方法找到網(wǎng)絡(luò)可通過(guò)的最大流量；其次，在保證該最大流量的前提下找到成本最小的線路。

根據(jù)最小費(fèi)用最大流問(wèn)題的概念，最小費(fèi)用最大流問(wèn)題也屬于線性規(guī)劃問(wèn)題。其數(shù)學(xué)模型如下：

min z=（i，j）∈Acijfij （6）

s.t.f+（vi）-f-（vi）=fvs，i=s（源）

-fvs，i=t（匯）

0，i≠s，t（中轉(zhuǎn)點(diǎn)）

0≤lij≤fij≤uij（（i，j）∈A） （7）

2算例

基于上述分析，本文以某公司鏈接產(chǎn)地到銷地的物流運(yùn)輸體系為例進(jìn)行說(shuō)明。其中，產(chǎn)品運(yùn)輸網(wǎng)絡(luò)如下圖1所示，圖中各弧表示運(yùn)輸?shù)缆贰Ｓ捎诘缆穼?shí)際地質(zhì)情況不同，使得每條道路上的運(yùn)輸費(fèi)用也不同，因此優(yōu)化該運(yùn)輸系統(tǒng)除考慮貨物的最大流外，還需要考慮道路運(yùn)輸?shù)淖钚≠M(fèi)用，即可基于本文所提的最小費(fèi)用最大流模型予以求解。

圖1某公司產(chǎn)品運(yùn)輸網(wǎng)絡(luò)圖1中弧上括號(hào)內(nèi)的數(shù)字分別表示對(duì)應(yīng)運(yùn)輸?shù)缆返娜萘肯拗坪蛦挝贿\(yùn)費(fèi)。

對(duì)算例按照最小費(fèi)用最大流問(wèn)題建模，過(guò)程如下：

（1）建立最大流模型。

maxz=fvs=fs1+fs2 （8）

滿足約束條件（1）。

（2）建立最小費(fèi)用模型。

minz=（vi，vj）∈Acijfij （9）

滿足約束條件（7）。

（3）利用MATLAB軟件實(shí)現(xiàn)算例，在命令窗口中編寫(xiě)MATLAB程序并執(zhí)行，得到結(jié)果如圖2所示。

圖2程序仿真結(jié)果由圖2所示，該運(yùn)輸網(wǎng)絡(luò)最大運(yùn)輸量為14噸，最小運(yùn)輸總成本為20500元，優(yōu)化后的運(yùn)輸方案如圖3所示。

圖3優(yōu)化運(yùn)輸方案3結(jié)束語(yǔ)

隨著電子商務(wù)和物流業(yè)的迅速發(fā)展，物流運(yùn)輸?shù)牡匚辉絹?lái)越受到重視。本文將最小費(fèi)用最大流模型運(yùn)用到物流運(yùn)輸網(wǎng)絡(luò)的優(yōu)化中，為優(yōu)化運(yùn)輸網(wǎng)絡(luò)路線提供了一種可行方法，實(shí)現(xiàn)了在實(shí)際優(yōu)化中既考慮最大運(yùn)量同時(shí)也尋求運(yùn)輸總成本最小化的目標(biāo)。需要指出的是：在優(yōu)化運(yùn)輸網(wǎng)絡(luò)過(guò)程中，優(yōu)化運(yùn)輸路線只是其中的一個(gè)部分，還需要對(duì)物流節(jié)點(diǎn)進(jìn)行優(yōu)化，比如物流節(jié)點(diǎn)的選址問(wèn)題，這兩類問(wèn)題應(yīng)該綜合考慮進(jìn)行優(yōu)化，這些問(wèn)題有待進(jìn)一步的研究。

參考文獻(xiàn)

[1]杜潔，郝妍，王璐.多目標(biāo)應(yīng)急物流運(yùn)輸問(wèn)題優(yōu)化研究[J].物流工程與管理，2010，32（4）：113114.

[2]王桂平，王衍，任嘉辰.圖論算法理論、實(shí)現(xiàn)及應(yīng)用[M].北京：北京大學(xué)出版社，2011：131208.

[3]王銳，甘凱.圖論優(yōu)化法在物流運(yùn)輸中的運(yùn)用[J].商場(chǎng)現(xiàn)代化，2005，（28）：137138.

[4]張建林.MATLAB&EXCEL定量預(yù)測(cè)與決策[M].北京：電子工業(yè)出版社，2012.

[5]林方明，馬建軍，龐淵.物流配送決策中的運(yùn)輸網(wǎng)絡(luò)優(yōu)化問(wèn)題研究[J].山西建筑，2004，30（08）：8485.