徐州工程學(xué)院2015屆物流工程專業(yè)畢業(yè)設(shè)計(jì)（論文）

1、<p><b>　　畢業(yè)設(shè)計(jì)（論文）</b></p><p>　圖書分類號(hào)：</p><p>　密 級(jí)：</p><p><b>　　摘要</b></p><p>　　現(xiàn)如今，中國已成為電子產(chǎn)品的消費(fèi)大國，隨著電子產(chǎn)品更新?lián)Q代速度的變快，社會(huì)中青年群體對(duì)新型電子產(chǎn)品的追捧性消費(fèi)也

2、在增加，使得電子材料產(chǎn)品的需求量也在不斷地加大，這也就導(dǎo)致了電子材料的運(yùn)輸費(fèi)用在不斷提高。如何使電子材料貨物運(yùn)輸流量最大化，提高貨物的輸送效率，使企業(yè)物流輸送成本降到最低成為刻不容緩的問題。</p><p>　　本文主要研究XX電子材料有限公司貨物運(yùn)輸網(wǎng)絡(luò)流量最大化的問題。首先闡述了研究背景、研究目的及其意義，并了解分析了國內(nèi)外研究現(xiàn)狀及理論成果，提出優(yōu)化貨物運(yùn)輸網(wǎng)絡(luò)流量的必然性和該研究在企業(yè)中所帶來的實(shí)際價(jià)值以

3、及現(xiàn)階段企業(yè)生產(chǎn)運(yùn)輸中存在的問題。其次，本文闡述了網(wǎng)絡(luò)最大流的相關(guān)定義理念、特點(diǎn)、模型設(shè)計(jì)、計(jì)算方法和研究價(jià)值。在本文中，選擇以鹽城市XX電子材料有限公司為研究的企業(yè)對(duì)象，分析了該企業(yè)在運(yùn)輸網(wǎng)絡(luò)上的現(xiàn)狀和存在的問題。而緊接著問題的發(fā)現(xiàn)，本文提出企業(yè)運(yùn)輸網(wǎng)絡(luò)流量優(yōu)化的計(jì)算方法，設(shè)計(jì)了簡單的運(yùn)輸模型：主要以標(biāo)號(hào)法，結(jié)合增廣路等進(jìn)行圖解。最后，以企業(yè)的客戶選擇、運(yùn)輸路線、運(yùn)輸流量優(yōu)化為目標(biāo)，以企業(yè)交通工具的實(shí)際設(shè)備情況為基礎(chǔ)，通過運(yùn)輸弧的最大

4、通過能力和實(shí)際運(yùn)輸流，制定合理的網(wǎng)絡(luò)優(yōu)化方案。</p><p>　　本文將理論引入實(shí)際研究，針對(duì)鹽城市XX電子材料有限公司貨物運(yùn)輸網(wǎng)絡(luò)流量的實(shí)際問題，收集各項(xiàng)數(shù)據(jù)，運(yùn)用標(biāo)號(hào)法求解，進(jìn)而得出鹽城市XX公司運(yùn)輸?shù)淖畲罅髁俊?lt;/p><p>　　關(guān)鍵詞 XX電子公司；貨物運(yùn)輸網(wǎng)絡(luò)；網(wǎng)絡(luò)最大流；標(biāo)號(hào)法</p><p><b>　　Abstract</b>

5、;</p><p>　　Today, China has become a big consumer electronic products, with the replacement of electronic products faster speeds, community youth groups to the pursuit of new electronic products, consumption

6、 has increased, so that the demand for electronic materials products are constantly increase, which also led to the transportation costs of electronic materials continues to increase. How to make electronic materials tra

7、nsport network to maximize traffic and improve the efficiency of transport and reduc</p><p>　　This paper studies a splendorous maximize Electronic Materials Co., Ltd. freight transport network flow problems.

8、 First describes the background, purpose and significance, and understand and analyze the current situation of domestic and foreign research and theoretical results, the study proposes inevitability and optimize the tran

9、sport of goods traffic in the enterprise brings real value and the stage production of transport Problems. Secondly, the paper describes the concept of maximum network</p><p>　　This paper studies the theory

10、into reality, for practical problem-Hui Electronic Materials Co., Ltd. Yancheng cargo transport network traffic, collecting the data, using reference method to solve, and then draw the maximum flow Yancheng Cheng-hui com

11、pany transport.</p><p>　　Keywords Chenghui electronic company Cargo transport network Network maximum flow Label method</p><p><b>　　目 錄</b></p><p><b>　　1 緒論

12、1</b></p><p>　　1.1 研究背景1</p><p>　　1.2 研究目的與意義1</p><p>　　1.3 國內(nèi)外研究現(xiàn)狀2</p><p><b>　　2 基本的理論5</b></p><p><b>　　2.1網(wǎng)絡(luò)與流5</b>&

13、lt;/p><p><b>　　2.2增廣路6</b></p><p>　　2.3截集與截量7</p><p>　　3 鹽城市XX電子材料有限公司的基本情況8</p><p>　　3.1 XX公司的概況8</p><p>　　3.2 XX公司運(yùn)輸網(wǎng)絡(luò)流量現(xiàn)狀分析8</p>&l

14、t;p>　　3.2.1以往運(yùn)輸狀況8</p><p>　　3.2.2運(yùn)輸問題分析9</p><p>　　4 利用標(biāo)號(hào)法找出XX公司運(yùn)輸網(wǎng)絡(luò)最大流13</p><p>　　4.1網(wǎng)絡(luò)最大流相關(guān)定理和算法13</p><p>　　4.1.1最大流相關(guān)定理13</p><p>　　4.1.2尋找最大流的算法：

15、標(biāo)號(hào)法14</p><p>　　4.2建立模型15</p><p>　　4.3模型的求解15</p><p>　　5 貨物運(yùn)輸流量的優(yōu)化建議與前后對(duì)比18</p><p>　　5.1優(yōu)化貨物運(yùn)輸流量的建議18</p><p>　　5.2企業(yè)貨物運(yùn)輸流量問題優(yōu)化前后的對(duì)比18</p><p

16、><b>　　結(jié)論19</b></p><p><b>　　致謝21</b></p><p><b>　　參考文獻(xiàn)22</b></p><p><b>　　1 緒論</b></p><p><b>　　1.1 研究背景</b&g

17、t;</p><p>　　當(dāng)今世界，在經(jīng)濟(jì)全球化的日益發(fā)展的軌跡上，物流業(yè)作為一個(gè)嶄新的研究領(lǐng)域，吸引了眾多的目光。那么就會(huì)有一個(gè)疑問，什么是物流？“物”，簡單的說，就是物質(zhì)，更準(zhǔn)確的術(shù)語是指物質(zhì)資料世界中具備物質(zhì)上的實(shí)體特點(diǎn)，同時(shí)也具備可以進(jìn)行物理性位移的物質(zhì)資料。[1]“流”是一種物理性的運(yùn)動(dòng)，這種物理性運(yùn)動(dòng)有著其限定的含義，那就是以地球?yàn)閰⒄瘴?，而這種物理性運(yùn)動(dòng)時(shí)相對(duì)于地球而發(fā)生的，它的范圍可以是地理性的宏

18、觀大范圍，也可以是同一個(gè)地域或者同一個(gè)環(huán)境中的微觀性小運(yùn)動(dòng)?！拔铩焙汀傲鳌眱烧叩慕M合，就成為了現(xiàn)今世界建立在目的（包括經(jīng)濟(jì)上、軍事上、社會(huì)條件上的有目的的活動(dòng)）和實(shí)物之間的運(yùn)動(dòng)形式。研究一個(gè)領(lǐng)域的根本性目的就是其為社會(huì)創(chuàng)造出有力的或者便利的價(jià)值。</p><p>　　作為社會(huì)生活中運(yùn)用極為廣泛的問題之一，網(wǎng)絡(luò)最大流問題在公路系統(tǒng)（車輛流量問題）、供電系統(tǒng)（電流量問題）、通訊網(wǎng)絡(luò)（信息流問題）等都有應(yīng)用，也是計(jì)算機(jī)

19、科學(xué)和運(yùn)籌學(xué)重要的研究和探索的內(nèi)容。20世紀(jì)50年代，由福特（Ford），富克遜（Fulkerson）建立的“網(wǎng)絡(luò)流理論”成為網(wǎng)絡(luò)流問題應(yīng)用的重要組成部分。近半個(gè)世紀(jì)以來，關(guān)于網(wǎng)絡(luò)最大流方面的研究，不但研究成果層出不窮，眾多學(xué)者們發(fā)展突破的速度也令人吃驚。[2]</p><p>　　在這樣的大背景上，如何將網(wǎng)絡(luò)最大流運(yùn)用到實(shí)際的生產(chǎn)生活中顯得尤為關(guān)鍵。本文基于以往學(xué)者的研究成果上，對(duì)網(wǎng)絡(luò)最大流問題進(jìn)行了個(gè)人的研究

20、與學(xué)習(xí)，結(jié)合網(wǎng)絡(luò)最大流中的標(biāo)號(hào)算法以及一個(gè)發(fā)點(diǎn)一個(gè)收點(diǎn)的情況，將其應(yīng)用于鹽城XX電子材料有限公司的運(yùn)輸流量優(yōu)化上。</p><p>　　1.2 研究目的與意義</p><p>　　網(wǎng)絡(luò)最大流理論是圖論網(wǎng)絡(luò)中十幾個(gè)著名理論結(jié)果的證明理論基礎(chǔ)，而且是企業(yè)運(yùn)作生活中人員分派、運(yùn)輸?shù)葐栴}的重要解決方法之一。比如，港口物流運(yùn)輸操作中需要了解港口的最大運(yùn)輸流量；信息網(wǎng)絡(luò)中對(duì)其信息承載和運(yùn)輸能力的研究；

21、電力系統(tǒng)中對(duì)電的流量進(jìn)行的估算；金融企業(yè)對(duì)企業(yè)本身現(xiàn)金流量的統(tǒng)計(jì)等等。涉及的范圍可以是一個(gè)地域，也可以是一個(gè)研究點(diǎn)。從簡化角度來講，網(wǎng)絡(luò)最大流問題是一個(gè)經(jīng)典的組合優(yōu)化的問題，也可以說是一個(gè)較為特殊的線性規(guī)劃問題，作為一個(gè)運(yùn)籌學(xué)和計(jì)算機(jī)領(lǐng)域重要的研究內(nèi)容，網(wǎng)絡(luò)最大流問題是切實(shí)的把社會(huì)生活生產(chǎn)中的物流問題具體模型化，從而轉(zhuǎn)化為運(yùn)輸網(wǎng)絡(luò)中流的問題。從宏觀角度，就是解決現(xiàn)實(shí)企業(yè)的網(wǎng)絡(luò)中流量問題和費(fèi)用問題，找出其中最優(yōu)的解決方案，也能夠利用圖論以

22、及線性規(guī)劃等數(shù)學(xué)方法，將那些表面上看起來和網(wǎng)絡(luò)流量無關(guān)的問題轉(zhuǎn)變?yōu)榕c網(wǎng)絡(luò)流有關(guān)的問題。以此同時(shí)，網(wǎng)絡(luò)最大流問題經(jīng)常作為一些子問題出現(xiàn)在圖論、組合優(yōu)化以及線性規(guī)劃等問題中，占有一定的重要比重。[3]</p><p>　　多年來，盡管有著近半個(gè)世紀(jì)的研究歷史，并且眾多學(xué)者極大地推進(jìn)了最大流問題的研究進(jìn)展，但關(guān)于網(wǎng)絡(luò)最大流問題的研究還遠(yuǎn)遠(yuǎn)沒有結(jié)束。首先，在純粹的理論算法與研究方面，當(dāng)今社會(huì)還未計(jì)算出網(wǎng)絡(luò)最大流問題涉及到

23、的算法時(shí)間復(fù)雜度的精確下界，現(xiàn)有的研究只是確定一個(gè)大概的界限，也沒有任何一個(gè)通用算法達(dá)到或接近問題的下界，即只能是講問題優(yōu)化，并不是百分之百的能夠達(dá)到最大流中的“最”；其次，在眾多算法的實(shí)際應(yīng)用性能方面，目前算法的實(shí)際優(yōu)化性能并不能夠滿足過多的應(yīng)用問題的要求；同時(shí)，網(wǎng)絡(luò)最大流問題作為特殊的線性規(guī)劃問題，遠(yuǎn)比一般的線性規(guī)劃問題容易解決，在實(shí)際操作中發(fā)現(xiàn)企業(yè)應(yīng)用領(lǐng)域中的問題和最大流問題兩者之間的聯(lián)系，可以使應(yīng)用問題更好地得到解決。因此，在網(wǎng)

24、絡(luò)最大流問題的研究方面，有著十分重要的理論意義和實(shí)用價(jià)值。同樣的，在該問題的應(yīng)用與研究趨勢(shì)上，最大流的應(yīng)用研究一直是富有意義和實(shí)用價(jià)值的探索工作，對(duì)于流量最大化問題上做著深入研究的學(xué)者們和致力于探尋解決具體問題的工程師們從不同的角度，以各自獨(dú)特的發(fā)散性思維充實(shí)著這方面的研究。不管是從線性規(guī)劃來看，還是從組合優(yōu)化角度來看， 最大流問題都是值得深入研究的問題，存在</p><p>　　除此之外，網(wǎng)絡(luò)最大流雖然涉及的領(lǐng)

25、域非常廣泛，但是所能運(yùn)用的問題方面有一定的限制，而這些限制并沒有一定的聯(lián)系特征，在現(xiàn)實(shí)的企業(yè)實(shí)際生產(chǎn)操作中，由于不同企業(yè)的生產(chǎn)特點(diǎn)不一樣，網(wǎng)絡(luò)并不是一直存在，構(gòu)建網(wǎng)絡(luò)也是一個(gè)難點(diǎn)。比如人員的指派，在網(wǎng)絡(luò)流問題中，并沒有考慮到企業(yè)人員的個(gè)人因素等。再者，網(wǎng)絡(luò)最大流中“弧”也屬于較難定義的一個(gè)范疇，飽和弧和非飽和弧的定義也并不是絕對(duì)的，與理論知識(shí)不同，實(shí)際操作問題中還要考慮運(yùn)輸中“弧”的飽和值并不是一成不變，如蔬果等產(chǎn)業(yè)在運(yùn)輸過程中，由于貯

26、存方式的不一樣，就會(huì)造成運(yùn)輸網(wǎng)絡(luò)中弧的飽和值改變，進(jìn)而影響整個(gè)網(wǎng)絡(luò)流量優(yōu)化的方案。這些種種的問題，使得網(wǎng)絡(luò)最大流問題實(shí)際研究的必要性可見一斑。</p><p>　　1.3 國內(nèi)外研究現(xiàn)狀</p><p>　　網(wǎng)絡(luò)最大流問題于不同的學(xué)術(shù)領(lǐng)域，無論是工科學(xué)類、文科學(xué)類、商業(yè)學(xué)、經(jīng)濟(jì)學(xué)等方面起到的作用越來越重要。同時(shí)，在各種社交網(wǎng)絡(luò)的分析中，也有網(wǎng)絡(luò)最大流的身影，如電子郵件網(wǎng)絡(luò)、商品網(wǎng)絡(luò)、留言網(wǎng)

27、絡(luò)等。[5]</p><p>　　半個(gè)世紀(jì)以來網(wǎng)絡(luò)最大流的研究已有豐富的成果，眾多學(xué)者們提出了一系列的求解網(wǎng)絡(luò)最大流的算法，這些算法為最大流問題建立了非常完善的理論知識(shí)體系。而網(wǎng)絡(luò)最大流這個(gè)問題最初是在1955年由Ford和Fulkerson提出的。該問題的出現(xiàn)，以及之后許多相關(guān)的理論和算法的相繼問世，不僅密切地聯(lián)系了運(yùn)籌學(xué)和圖論兩大模型處理方法，而且開辟了網(wǎng)絡(luò)最大流應(yīng)用的新篇章。[6]</p>&

28、lt;p>　　網(wǎng)絡(luò)最大流的求解算法有：</p><p>　?。?）通過路徑推進(jìn)流量的增廣鏈算法，其中應(yīng)用比較廣泛的算法有Ford&Fulkerson算法（又稱2F標(biāo)號(hào)算法）和Dinic（1970）的增量網(wǎng)絡(luò)算法，Edmonds-Karp（1972）的最短增廣路算法；</p><p>　?。?）預(yù)留推進(jìn)算法，這種算法是通過弧的推流能夠返回多余的流量，這種算法受到普遍的借鑒與應(yīng)用

29、，譬如Karzanov的網(wǎng)絡(luò)阻斷流算法，而后又有以Karzanov的理論為基礎(chǔ)，由Goldberg和Tarjan（1986）兩位學(xué)者共同提出且不斷改進(jìn)的推進(jìn)重標(biāo)號(hào)算法（即二分長度阻斷流算法，進(jìn)一步降低了算法時(shí)間的復(fù)雜度）等。[7]</p><p>　　表1-1 網(wǎng)絡(luò)最大流算法時(shí)間簡表[8]</p><p>　　在過去的十幾年時(shí)間里，隨著一直在進(jìn)行的最大流問題深入性研究，許多研究人員們?cè)谥髁?/p>

30、算法的基礎(chǔ)上又提出了許多改進(jìn)的算法。其中“消鏈”算法就是眾多算法之一，該算法是在Ford-Fulkerson標(biāo)記法在求解網(wǎng)絡(luò)最大流的時(shí)候需要經(jīng)過多次的標(biāo)號(hào)和反復(fù)的調(diào)整基礎(chǔ)上，受到水流概念的啟發(fā)，引入極大一致鏈的概念，該算法主要是通過反復(fù)并尋找極大一致鏈，并求得最終的最大流。[9]其他還有推薦技術(shù)、距離概念、建立動(dòng)態(tài)樹等等。而對(duì)于特殊的一些網(wǎng)絡(luò)，如雙容量網(wǎng)絡(luò)、無向網(wǎng)絡(luò)等算法更是不勝枚舉。盡管最大流理論正在被不斷地充實(shí)和完善，每種算法本身也

31、存在著一定的弊端，而未來的時(shí)間長河中，對(duì)這些算法的改進(jìn)仍是一項(xiàng)紛繁復(fù)雜的工作，也是一個(gè)巨大的挑戰(zhàn)。</p><p><b>　　2 基本的理論</b></p><p><b>　　2.1網(wǎng)絡(luò)與流</b></p><p>　　先看一個(gè)例子，來引出網(wǎng)絡(luò)流的概念。</p><p>　　v2 v

32、</p><p>　　4 1 24</p><p>　　V 3 v 2V</p><p>　　4 3 3</p><p><b>　　V</b></p><p>　　圖2-1 簡單的網(wǎng)絡(luò)圖</p><p

33、>　　如圖，將圖2-1看做是某基地運(yùn)輸貨物的網(wǎng)絡(luò)圖，Vs為發(fā)點(diǎn)，Vt為終點(diǎn)，v，v，v，v為基地中轉(zhuǎn)站，邊上（弧上）的數(shù)表示該運(yùn)輸網(wǎng)絡(luò)的最大運(yùn)貨能力，如何安排各網(wǎng)絡(luò)弧上的輸送量，才能使從Vs到Vt的總運(yùn)輸流量最大？</p><p>　　運(yùn)輸網(wǎng)絡(luò)中，貨物整體的最大通過能力是有限的，且是一個(gè)固定值。而實(shí)際的運(yùn)輸流量并不是恒等于運(yùn)輸?shù)目赏ㄟ^容量，上述的問題就是要討論如何將運(yùn)輸裝置的輸送能力充分利用，進(jìn)而取得最好的

34、運(yùn)輸效果（即流量最大），這類問題通常稱為最大流問題。[10]</p><p>　　定義1：設(shè)有向連通的網(wǎng)絡(luò)圖G=（V，E），網(wǎng)絡(luò)G的每條邊（v，v）上有非負(fù)數(shù)C稱為邊（也稱為?。┑娜萘?，僅有一個(gè)入次為0的點(diǎn)Vs稱為發(fā)點(diǎn)Send（源點(diǎn)s），一個(gè)出次為0的點(diǎn)Vt稱為收點(diǎn)Take（匯點(diǎn)t），其余的點(diǎn)為中間點(diǎn)，這樣的網(wǎng)絡(luò)G稱為容量網(wǎng)絡(luò)，常記做G=（V，E，C）。注：這里所說的發(fā)點(diǎn)v是指只有從v發(fā)出去的弧，而沒有指向v的弧

35、；收點(diǎn)v只有弧指向v，而沒有從v發(fā)出去的弧。[11]</p><p>　　定義2：對(duì)任一G中的邊（v，v）有流量?，稱集合?=｛?｝為網(wǎng)絡(luò)G上的一個(gè)流（Flow）。</p><p>　　定義3：稱滿足下列條件的流?為可行流：</p><p>　　容量限制條件：對(duì)G中每條邊（v，v），有0≦?≦C；</p><p>　　平衡條件：對(duì)中間點(diǎn)v，有

36、?=?（即中間點(diǎn)v的物資輸入量與輸出量相等，也稱為反對(duì)稱性?=-?，也就是說，從節(jié)點(diǎn)i到j(luò)的凈流量值等于從j到i的凈流量值的相反數(shù)）；對(duì)收、發(fā)點(diǎn)v，v，有?=?=W（即從v點(diǎn)發(fā)出的物資總量等于 v點(diǎn)輸入的量，也稱為網(wǎng)絡(luò)流的流量守恒條件）W為網(wǎng)絡(luò)流的總流量。</p><p>　　可行流總是存在的，例如?=｛0｝就是一個(gè)流量為0的可行流。圖2-1中，每條弧上的數(shù)字給出的就是一個(gè)可行流?=｛?｝，它滿足定義中的條件（1

37、）和（2）。</p><p>　　最大流問題和圖的緊密聯(lián)系，但同時(shí)也是一個(gè)線性規(guī)劃問題，求解能夠更為直觀簡便。所謂最大流問題就是在限定的容量網(wǎng)絡(luò)中，求一個(gè)流?=｛?｝，使得總流量v（?）達(dá)到最大，即</p><p><b>　　Max v（?）</b></p><p><b>　　?-?=0</b></p>

38、<p><b>　　?=v（?）</b></p><p><b>　　?=v（?）</b></p><p>　　0≦?≦C（i，j≠s，t）</p><p>　　定義4：一個(gè)流?=｛?｝，當(dāng)?=C，則稱流?對(duì)邊（v，v）是飽和弧，否則稱?對(duì)（v，v）不飽和弧。將?=0的弧稱為零流弧，將?>0的弧稱為非零流弧

39、。</p><p><b>　　2.2增廣路</b></p><p><b>　　定義5（增廣路）：</b></p><p>　　若μ是網(wǎng)絡(luò)中連接發(fā)點(diǎn)v和收點(diǎn)v的一條路，定義路的方向是從v到v，則路上的弧可分為兩類：[12]</p><p>　　(1)弧的方向和路的方向一致，稱此類弧為前向弧，所有前

40、向弧的集合記為μ</p><p>　　(2)弧的方向和路的方向不一致，稱此類弧為后向弧，所有前向弧的集合記為μ</p><p>　　設(shè)?是一個(gè)可行流，若μ滿足下列條件，稱之為（關(guān)于可行流?的）增廣鏈。</p><p>　　在?。╲，v）∈μ上，0≦?<C，即μ中每一弧都是非飽和弧。</p><p>　　在?。╲，v）∈μ上，0<?

41、≦C，即μ中每一弧都是非零流弧。</p><p>　　這也稱μ為從v到v的可增廣鏈。</p><p>　　可增廣鏈的實(shí)際意義是：沿著這條鏈從v到v輸送的流，還有潛力可挖，按照一定的調(diào)整方法（下文中的定理），就可以把流量提高，調(diào)整后的流，在各點(diǎn)仍滿足平衡條件及容量限制條件，即仍為可行流。這樣就得到了尋找最大流的方法：從一個(gè)可行流開始，尋求關(guān)于這個(gè)可行流的一條可增廣鏈，如果存在，則可以經(jīng)過調(diào)整

42、，得到一個(gè)新的可行流，其流量要比原來的可行流要大，重復(fù)這個(gè)過程，直到不存在關(guān)于該流的可增廣鏈?zhǔn)蔷偷玫搅俗畲罅鳌13]</p><p><b>　　2.3截集與截量</b></p><p>　　設(shè)S，TV，S∩T=?，將始點(diǎn)在S中，終點(diǎn)在T中的所有弧構(gòu)成的集合，記為（S，T）</p><p>　　定義6：給出網(wǎng)絡(luò)D=(V，A，C)，若點(diǎn)集V被剖

43、分為兩個(gè)非空集合V和，使v∈V，v∈，則把弧集（V，）稱為是（分離v和v的）截集。[14]</p><p>　　顯然，若把某一截集的弧從網(wǎng)絡(luò)中丟失，則從v到v便不存在路。所以，直觀上說，截集是從v到v的必經(jīng)之路。</p><p>　　定義7：給一個(gè)截集（V，），把截集（V，）中所有弧的容量之和稱為這個(gè)截集的容量（簡稱截量），記為c（V，），即c（V，）=C .不難證明，任何一個(gè)可行流的流量

44、v（?）都不會(huì)超過任一截集的容量。即v（?）≦c（V，）</p><p>　　顯然，若對(duì)于一個(gè)可行流?，網(wǎng)絡(luò)中有一個(gè)截集（V，），使得v（?）=c（V，），則?必是最大流，而（V，）必定是D的所有截集中，容量最小的一個(gè)，即最小截集。[15]</p><p>　　3 鹽城市XX電子材料有限公司的基本情況</p><p>　　3.1 XX公司的概況</p>

45、<p>　　鹽城市XX電子材料有限公司，隸屬于江蘇省，位于阜寧縣益林鎮(zhèn)（如圖3-1） 。是一家專業(yè)生產(chǎn)絕緣凡立水，稀釋劑的廠家，主營行業(yè)包括密封材料、絕密設(shè)備、保護(hù)材料，主營行業(yè)為電源（整流）變壓器、其他變壓器以及電感線圈。其生產(chǎn)的產(chǎn)品在電機(jī)線圈、變壓器、電器及各種工業(yè)馬達(dá)線圈等精密器件中得到的廣泛的應(yīng)用。公司的廠房區(qū)占地面積10000多平方米，員工200多名，其中工程師10名，技術(shù)人員28名。公司生產(chǎn)設(shè)備和檢測(cè)儀器都配備齊

46、全。鹽城市XX電子材料有限公司（鹽城市一元石油化工有限公司）是專業(yè)生產(chǎn)銷售絕緣凡立水、稀釋劑系列產(chǎn)品的企業(yè)，已有十多年的歷程基礎(chǔ)，現(xiàn)公司擁有絕緣凡立水、稀釋劑系列的高級(jí)工程師、技師等，配備有自帶化驗(yàn)室研制設(shè)備和生產(chǎn)設(shè)備，以達(dá)到自主研發(fā)絕緣漆、稀釋劑系列產(chǎn)品的目的。其中部分產(chǎn)品取得美國UL認(rèn)證及美國DuPout杜邦公司EIS電器絕緣系統(tǒng)UL1446絕緣漆，而主要生產(chǎn)的高品質(zhì)液態(tài)電器絕緣材料，產(chǎn)品涵蓋B、F、H、C級(jí)浸漬，被應(yīng)用于變壓器、安

47、定器、工業(yè)馬達(dá)線圈以及其他機(jī)械設(shè)備。而下圖3-1則為XX公司的地理位置。[16]</p><p>　　圖3-1 鹽城市XX電子材料有限公司地理圖</p><p>　　3.2 XX公司運(yùn)輸網(wǎng)絡(luò)流量現(xiàn)狀分析</p><p>　　3.2.1以往運(yùn)輸狀況</p><p>　　XX電子材料公司在運(yùn)輸貨物上，配備有微型1.8噸貨車2輛，7噸卡車1輛。&l

48、t;/p><p>　?。?）運(yùn)輸?shù)闹饕浳锶绫?-1</p><p>　　表3-1 運(yùn)輸貨物表</p><p>　?。?）訂單分類見表3-2（表中數(shù)據(jù)為該類訂單數(shù)量所占的比例）</p><p>　　表3-2 訂單比例表</p><p>　?。?）貨物流量流向分析見表3-3</p><p>　　表3-

49、3 貨物流量表</p><p>　　3.2.2運(yùn)輸問題分析</p><p>　　2013年整個(gè)年度，XX公司將貨物運(yùn)輸?shù)馁M(fèi)用匯總，發(fā)現(xiàn)隨著貨物運(yùn)輸量的增加，運(yùn)輸費(fèi)用不減反增。主要沒問題有一下幾點(diǎn)。</p><p><b>　?。?）油價(jià)上漲</b></p><p>　　今年油價(jià)上漲導(dǎo)致運(yùn)輸成本上升，每逢春運(yùn)期間，油價(jià)更是

50、水漲船高。這是無法解決的問題，公司只能從其他方面入手。</p><p><b>　　（2）地理位置</b></p><p>　　XX公司的地處益林鎮(zhèn)工業(yè)園與民居邊緣，交通以三輪車、電瓶車、小轎車等為主，每當(dāng)有周邊企業(yè)訂購貨物時(shí)，一般用小型的貨車來運(yùn)輸，而周邊的企業(yè)大多是合同簽訂的客戶，每次運(yùn)輸?shù)呢浳镞\(yùn)量較大，這就使得微型貨車必須來返幾次來完成運(yùn)輸任務(wù)。而7噸的卡車由于

51、道路的限制不得在鎮(zhèn)內(nèi)運(yùn)輸，這就造成了運(yùn)輸成本的增加。雖然客戶支付了一部分的運(yùn)輸費(fèi)用，但是這樣的運(yùn)輸方式使得公司承擔(dān)著比重不低的運(yùn)輸金額。管理體系曾考慮一個(gè)臨時(shí)倉庫，但是也只是杯水車薪，且建立倉庫又要一定的管理和建設(shè)成本，只能另想他法。</p><p>　?。?）零單比例超出預(yù)料</p><p>　　XX公司除了一些固定的合約客戶，零單客戶也是公司的一個(gè)銷售途徑。近年來，零單比例超出預(yù)期，其

52、中鹽城市內(nèi)、市外、周邊地區(qū)，三個(gè)均高出原來預(yù)計(jì)10個(gè)百分點(diǎn)左有，而零單的成本比整車成本要高出15％，而室內(nèi)外兩類地區(qū)的成本比平均成本要高出20－30%。由于客戶的銷售地區(qū)結(jié)構(gòu)隨著很多不定因素著變化，沒有可行的規(guī)律去預(yù)料和改變，這也就造成了上述的這些狀況的發(fā)生。如圖3-2，每個(gè)季度的地區(qū)貨物比例一覽無余，就拿市內(nèi)地區(qū)來說，在第一季度第一個(gè)月小于市外地區(qū)的票數(shù)都是領(lǐng)先的，即使在第二個(gè)季度也是僅次于市外地區(qū)，因此小單還是占大多數(shù)的。而顯而易見

53、，與之形成鮮明對(duì)比的是周邊地區(qū)，因?yàn)榇髥味啾憧梢圆捎眉b式運(yùn)輸，可以大大的節(jié)約成本，因此，大單數(shù)量過少也是造成其虧損的重要原因。[17]</p><p>　　由于零單過多，過于分散，造成多次運(yùn)輸，往返運(yùn)輸，甚至?xí)l(fā)生空箱運(yùn)輸，這都是不科學(xué)化，不合理的。[18]</p><p>　　當(dāng)然，我們也可以看出周邊地區(qū)單數(shù)還是屬于比較多的，我們可以采用拼箱作業(yè)法，把這種中大單和零碎的小單一起運(yùn)輸派送

54、。[19]</p><p>　　圖3-2 各季度不同地區(qū)貨物比例圖</p><p>　　根據(jù)貨物運(yùn)輸和配送的分析圖也能夠反映一部分的原因：</p><p>　　圖3-3 貨物運(yùn)輸和配送的分析圖</p><p>　?。?）客戶銷售地區(qū)的結(jié)構(gòu)變化如圖3-4</p><p>　　圖5客戶銷售地區(qū)結(jié)構(gòu)增長比例圖</p&

55、gt;<p>　　圖3-4 各季度需求增加比例圖</p><p>　　圖中分別為鹽城市內(nèi)、市外和公司周邊地區(qū)各個(gè)季度整體的結(jié)構(gòu)增加和變化的比例，圖中可以反映客戶的需求是變化的。這些情況是由客戶的銷售需求結(jié)構(gòu)、意向，也有季度的部分原因造成的，并沒有什么實(shí)際可行的措施來改變這些情況。既然我們無法改變和預(yù)測(cè)客戶的需求變化，那我們只能想辦法改變自己的供給方式與方法。而為了尋求更多的機(jī)會(huì)集拼，所以只能壓單和多

56、次裝卸，有時(shí)候也是因?yàn)檎{(diào)車價(jià)格太高，尋求更低成本的承運(yùn)車輛而耽誤了時(shí)間，這些都違背了客戶滿意原則，是不可行的。</p><p><b>　　（5）路線問題</b></p><p>　　其貨物不斷遭到擠壓導(dǎo)致破損，大批訂單的擠壓，可見其在運(yùn)輸方面也存在很大的問題：</p><p>　　①運(yùn)輸路線所運(yùn)貨物并不是運(yùn)輸貨物流量最大值</p>

57、<p>　　②運(yùn)輸路橋費(fèi)用增加：計(jì)重收費(fèi)，收費(fèi)基準(zhǔn)費(fèi)高，超載罰款</p><p>　?、圻\(yùn)輸業(yè)務(wù)虧損：壓單、多次裝卸，調(diào)車價(jià)格高，成本差異大，破損賠償，零單比例大，油價(jià)上漲</p><p>　?、芎艚兄行模轰浫氩患皶r(shí)，信息虛假，異常成本高，跟蹤手段落后，系統(tǒng)跟蹤模塊落后</p><p>　?、萦停毫銌芜\(yùn)輸，貨物小而散，車輛資源難掌握，零單成本高&l

58、t;/p><p>　　由于XX公司企業(yè)在管理制度上在運(yùn)輸方面存在著一定的漏洞和疏忽，就造成了運(yùn)輸成本控制不力，運(yùn)力浪費(fèi)嚴(yán)重。而其管理下的車輛調(diào)度的作業(yè)流程不規(guī)范，在裝卸時(shí)經(jīng)常出現(xiàn)拖延現(xiàn)象，導(dǎo)致出貨作業(yè)被拖延、效率低，出貨的車輛在運(yùn)行途中缺乏有力地監(jiān)控，也會(huì)有部分延時(shí)運(yùn)輸現(xiàn)象，這也是急需改進(jìn)力度的運(yùn)輸問題。[20]</p><p>　　對(duì)于以上五點(diǎn)問題，本文針對(duì)運(yùn)輸流量問題，進(jìn)行網(wǎng)絡(luò)流量的優(yōu)化。

59、</p><p>　　4 利用標(biāo)號(hào)法找出XX公司運(yùn)輸網(wǎng)絡(luò)最大流</p><p>　　4.1網(wǎng)絡(luò)最大流相關(guān)定理和算法</p><p>　　4.1.1最大流相關(guān)定理</p><p>　　由割集的定義不難看出，在容量網(wǎng)絡(luò)中割集是由v到v的必經(jīng)之路，無論拿掉哪個(gè)割集，v到v便不再相通，所以任何一個(gè)可行流的流量不會(huì)超過任一割集的容量，也即網(wǎng)絡(luò)的最大流與

60、最小割容量（最小割）滿足下面定理。</p><p>　　定理1：設(shè)?為網(wǎng)絡(luò)G=（V，E，C）的任一可行流，流量為W，（S，）是分離v，v的任一割集，則有W≦C（S，）[21]</p><p>　　由此可知，若能找到一個(gè)可行流?，一個(gè)割集（S，），使得?的流量W=C（S，），則?一定是最大流，定理的證明實(shí)際就是給出了尋找最大流的方法。</p><p>　　定理2：可行

61、流?是最大流，當(dāng)且僅當(dāng)不存在關(guān)于?的增廣鏈。</p><p>　　為了便于理解這個(gè)定理，在這里做進(jìn)一步的闡述證明：若?是最大流，設(shè)D中存在關(guān)于?的增廣鏈μ，令</p><p>　　θ=min｛（C-?），?｝</p><p>　　由增廣鏈的定義可知θ>0，令</p><p>　　?+θ （v，v）∈μ</p><

62、;p>　　?= ?-θ （v，v）∈μ</p><p>　　? （v，v）?μ</p><p>　　而｛ ?｝是一個(gè)可行流，且v（?）=v（?）+θ>v（?）。這與?是最大流的假設(shè)矛盾。</p><p>　　現(xiàn)在設(shè)D中不存在關(guān)于?的增廣鏈，證明?是最大流。則利用下面的方法來定義V：</p><p>&l

63、t;b>　　令v∈V</b></p><p>　　若v∈V，且?<C，則令v∈V</p><p>　　若v∈V，且?>0，則令v∈V</p><p>　　因?yàn)椴淮嬖陉P(guān)于?的增廣鏈，故v?V</p><p>　　記=V\V，于是得到一個(gè)截集（V，）則必有</p><p>　　C，（v，v）∈

64、（V，）</p><p><b>　　?= </b></p><p>　　0， （v，v）∈（V，）</p><p>　　所以v（?）=C（V，）。于是?必是最大流。</p><p>　　由上述可知，若?是最大流，則網(wǎng)絡(luò)中必存在一個(gè)截集（V，），使</p><p>　　v（?）=C（V，）&

65、lt;/p><p>　　于是就有如下重要結(jié)論：</p><p>　　最大流量最小截量定理：任一個(gè)網(wǎng)絡(luò)D中，從v到v的最大流的流量等于分離v，v的最小截集的容量。</p><p>　　定理2為社會(huì)生產(chǎn)生活提供了尋求網(wǎng)絡(luò)中最大流的一個(gè)方法。若給了一個(gè)可行流?，只要判斷D中有無關(guān)于?的增廣鏈。如果有增廣鏈，則可以按照定理2的前半部分闡述證明中的方法，改進(jìn)?，得到一個(gè)流量增大的

66、新的可行流。如果沒有增廣鏈，則得到最大流。而利用定理2后半部分證明中定義V的方法，可以根據(jù)v是否屬于V來判斷D中有無關(guān)于?的增廣鏈。[22]</p><p>　　實(shí)際計(jì)算時(shí)，用給頂點(diǎn)標(biāo)號(hào)的方法來定義V。在標(biāo)號(hào)過程中，有標(biāo)號(hào)的頂點(diǎn)表示是V中的點(diǎn)，沒有標(biāo)號(hào)的點(diǎn)表示不是V中的點(diǎn)。一旦v有了標(biāo)號(hào)，就表明找到一條增廣鏈；如果標(biāo)號(hào)過程進(jìn)行不下去，而v尚未標(biāo)號(hào)，則說明不存在增廣鏈，于是得到最大流，同時(shí)得到一個(gè)最小截集。[23]

67、</p><p>　　4.1.2尋找最大流的算法：標(biāo)號(hào)法</p><p>　　設(shè)已有一個(gè)可行流?，標(biāo)號(hào)的方法可分為兩步：第1步是標(biāo)號(hào)過程，通過標(biāo)號(hào)來尋找可增廣鏈；第2步是調(diào)整過程，沿可增廣鏈調(diào)整?以增加流量。</p><p><b>　　標(biāo)號(hào)過程:</b></p><p>　　在這個(gè)過程中，網(wǎng)絡(luò)中的點(diǎn)或者標(biāo)號(hào)點(diǎn)（又分為已

68、檢查和未檢查兩種），或者是未標(biāo)號(hào)點(diǎn)。每個(gè)標(biāo)號(hào)點(diǎn)的標(biāo)號(hào)包含兩部分：第一個(gè)標(biāo)號(hào)表明它的標(biāo)號(hào)是從哪一點(diǎn)得到的，以便找出增廣鏈；第二個(gè)標(biāo)號(hào)是為確定增廣鏈的調(diào)整量θ用的。</p><p>　　標(biāo)號(hào)過程開始，總先給v標(biāo)上（0，+∞），這時(shí)v是標(biāo)號(hào)而未檢查的點(diǎn)，其余都是未標(biāo)號(hào)的點(diǎn)。一般地，取一個(gè)標(biāo)號(hào)而未檢查的點(diǎn)v，對(duì)一切未標(biāo)號(hào)點(diǎn)v：</p><p>　　（1）若在?。╲，v）上，?<C，則給v標(biāo)號(hào)

69、（v，l（v））這里l（v）=min[l（v），C-?]。這時(shí)點(diǎn)v稱為標(biāo)號(hào)而未檢查的點(diǎn)</p><p>　?。?）若在?。╲，v）上，?>0，則給v標(biāo)號(hào)（-v，l（v））這里l（v）=min[l（v），?]。這時(shí)點(diǎn)v成為標(biāo)號(hào)而未檢查的點(diǎn)</p><p>　　于是v成為標(biāo)號(hào)而已檢查過的點(diǎn)。重復(fù)上述步驟，一旦v被標(biāo)上號(hào)，表明得到一條從v到v的增廣鏈μ，轉(zhuǎn)入調(diào)整過程。</p>

70、<p>　　若所有標(biāo)號(hào)都是已檢查過的，而標(biāo)號(hào)過程進(jìn)行不下去的時(shí)，則算法結(jié)束，這時(shí)的可行流就是最大流。[24]</p><p><b>　　調(diào)整過程:</b></p><p>　　首先按v及其他點(diǎn)的第一個(gè)標(biāo)號(hào)，利用“反向追蹤”的辦法，找出增廣鏈μ。例如設(shè)v的第一個(gè)標(biāo)號(hào)為v（或-v），則?。╲，v）（或相對(duì)應(yīng)的?。╲，v））是μ上的弧。接下來檢查v的第一個(gè)標(biāo)號(hào)

71、，若為v（或-v），則找出（v，v）（或相對(duì)應(yīng)的?。╲，v））。再檢查v的第一個(gè)標(biāo)號(hào)，依此下去，知道v為止。這時(shí)被找出來的弧就構(gòu)成了增廣鏈μ。令調(diào)整量θ是l（v），即v的第二個(gè)標(biāo)號(hào)。</p><p><b>　?、倭?lt;/b></p><p>　　?+θ （v，v）∈μ</p><p>　　?= ?-θ （v，v）∈μ<

72、;/p><p>　　? （v，v）?μ</p><p>　?、谌サ羲袠?biāo)號(hào)，對(duì)新的可行流?=｛?｝，重新進(jìn)入標(biāo)號(hào)過程。</p><p><b>　　4.2建立模型</b></p><p>　　首先，結(jié)合公司的實(shí)際銷售情況，建立一個(gè)運(yùn)輸網(wǎng)絡(luò)的模型，將運(yùn)輸點(diǎn)簡化為網(wǎng)絡(luò)圖中的節(jié)點(diǎn)，利用標(biāo)號(hào)法找出最大流。根據(jù)找出的最

73、大流，配置一定的運(yùn)輸路徑和運(yùn)輸車輛。</p><p>　　下圖4-1中，有5家待發(fā)展客戶，XX公司擬訂和其中兩至三家家客戶進(jìn)行長期的合約交易，如果交涉成功，就會(huì)每月運(yùn)輸一定的絕緣凡立水和稀釋劑，而從XX公司出發(fā)到這5家客戶，每家客戶的運(yùn)輸量都不一定，這就會(huì)造成每次運(yùn)輸時(shí)，運(yùn)輸貨物流量未優(yōu)化而使得運(yùn)輸費(fèi)用增加。故而為了尋找最大需求運(yùn)貨量、尋找出貨物運(yùn)輸網(wǎng)絡(luò)的最大流以及找出最大流的運(yùn)輸路線，以XX公司倉庫為發(fā)點(diǎn)s以距

74、離最遠(yuǎn)的安華玻璃廠為收點(diǎn)t，其他4家合約客戶分別設(shè)為節(jié)點(diǎn)v，v，v，v，每條弧即為運(yùn)輸?shù)穆窂?，弧上的?shù)字是XX公司能力范圍內(nèi)的運(yùn)輸最大流量和實(shí)際運(yùn)輸車輛所能承受的運(yùn)輸流量。即標(biāo)號(hào)法中的（C，?）</p><p>　　圖4-1 最大流模型簡圖</p><p><b>　　4.3模型的求解</b></p><p>　　利用上文中介紹的標(biāo)號(hào)法來進(jìn)行初

75、步的數(shù)據(jù)處理：</p><p><b>　　標(biāo)號(hào)過程：</b></p><p>　?、偈紫冉o發(fā)點(diǎn)v標(biāo)上(0，+∞)</p><p>　　②檢查v，在弧（v，v）上，?=C=3，易知這并不滿足標(biāo)號(hào)條件。在?。╲，v）上，?=1，C=5，?<C，則v的標(biāo)號(hào)為（v，l（v）），其中</p><p>　　l（v）=min[

76、l（v），(C-?)]=min[+∞，5-1]=4</p><p>　?、蹤z查v，在?。╲，v）上，?=2，C=2，不滿足標(biāo)號(hào)條件。</p><p>　　在弧（v，v）上，?=1>0，則給v記下標(biāo)號(hào)為（-v，l（v）），這里</p><p>　　l（v）=min[l（v），?]=min[4，1]=1</p><p>　?、軝z查v，在?。?/p>

77、v，v）上，?=3，C=4，?<C，則給v標(biāo)號(hào)（v，l（v）），這里l（v）=min[l（v），（C-?）]=min[1，1]=1</p><p>　　在?。╲，v）上，?=1>0，給v標(biāo)號(hào)：（-v，l（v）），這里</p><p>　　l（v）=min[l（v），?]=min[1，1]=1</p><p>　?、菰趘，v中任選一個(gè)進(jìn)行檢查。例如<

78、/p><p>　　在?。╲，v）上，?<C，給v標(biāo)號(hào)為（v，l（v）），這里</p><p>　　l（v）=min[l（v），（C-?）]=min[1，1]=1</p><p>　　因?yàn)檫@里的v有了標(biāo)號(hào)，故而轉(zhuǎn)入調(diào)整過程。</p><p><b>　　調(diào)整過程：</b></p><p>　　按照

79、點(diǎn)的第一個(gè)標(biāo)號(hào)找到一條增廣鏈，如圖4-2中雙線箭頭表示。</p><p>　　圖4-2 調(diào)整后的增廣鏈模型圖</p><p>　　易見 </p><p>　　μ={（v，v），（v，v）}</p><p>　　μ={(v，v)，(v，v)}</p><p>　　按θ=1在μ上調(diào)整?。</p>

80、;<p>　　μ上：?+θ=1+1=2</p><p><b>　　?+θ=1+1=2</b></p><p>　　μ上：?-θ=1-1=0</p><p><b>　　?-θ=1-1=0</b></p><p><b>　　其余的?不變。</b></p&g

81、t;<p>　　調(diào)整后就會(huì)得到如圖4-3的可行流，對(duì)這個(gè)可行流進(jìn)入標(biāo)號(hào)過程，尋找增廣鏈。</p><p>　　圖4-3 含有可行流的最終圖解</p><p>　　開始給v標(biāo)以（0，+∞），于是檢查v，給v標(biāo)以（v，3），檢查v，弧（v，v） 上，?=C，?。╲，v）上，?=0均不符合條件，標(biāo)號(hào)過程無法進(jìn)行下去，算法結(jié)束。</p><p>　　這時(shí)的可行

82、流（圖4-3）即為所要求解的最大流。最大流量為</p><p>　　V（?）=?+?=?+?=5</p><p>　　與此同時(shí)可找到最小截集（V，），其中V為標(biāo)號(hào)點(diǎn)集合，為未標(biāo)號(hào)點(diǎn)的集合。弧集合（V，）即為最小截集。[25]</p><p>　　這也就是說，在這5家待發(fā)展的客戶中，可以選擇客戶v和v，數(shù)量為兩家客戶。路線就是從XX公司出發(fā)，分別到達(dá)兩家客戶進(jìn)而達(dá)成最

83、大貨物運(yùn)輸流量。其中雖然v、v和v同樣運(yùn)輸流量為5，但是v為第五家客戶，且離XX公司路程較為遠(yuǎn)。</p><p>　　在這個(gè)模型中，V={V，V}，={v，v，v，v}，于是（V，）={（V，v），（v，v）}是最小截集，它的容量也是5.</p><p>　　由此可見，XX公司運(yùn)勢(shì)流量模型用標(biāo)號(hào)法找到增廣鏈的結(jié)果，同時(shí)也得到了一個(gè)最小的截集。最小集容量的大小影響總的運(yùn)貨輸送量的提高。因此，

84、為了提高XX公司總的運(yùn)貨輸送量，必須首先考慮改善最小截集中各弧的輸送狀況，提高他們的通過能力。另外，一旦最小截集中弧的通過能力被降低，就是的總的輸送量減少。[26]</p><p>　　5 貨物運(yùn)輸流量的前后對(duì)比與優(yōu)化建議</p><p>　　5.1企業(yè)貨物運(yùn)輸流量問題優(yōu)化前后的對(duì)比</p><p>　　針對(duì)模型計(jì)算得出的貨物流量最大值以及最大流量所選擇的運(yùn)輸路線，

85、XX公司進(jìn)行了1個(gè)月的測(cè)試，并對(duì)運(yùn)輸方面的問題進(jìn)行了改善</p><p><b>　　零單比例的處理</b></p><p>　　在零單這方面的銷售途徑上，XX公司采取兩個(gè)方案：</p><p>　　①零單和定期運(yùn)輸合并</p><p>　　零單的銷售量只增不減，由于零單客戶有一部分并不需要立刻送到，這就使得XX公司可以

86、將這部分的零單產(chǎn)品并入順路的定期運(yùn)輸中，這樣就不用再次運(yùn)送；也有一部分是將各個(gè)零單暫時(shí)滯留發(fā)貨，等零單有一定的貨物量，再進(jìn)行運(yùn)送。</p><p><b>　?、谛≡O(shè)備運(yùn)送零單</b></p><p>　　在眾多的零單貨物中，針對(duì)于對(duì)運(yùn)送時(shí)間有要求的客戶，XX公司選擇用電瓶車等較為輕便的運(yùn)輸工具運(yùn)送，極大的減少了運(yùn)輸費(fèi)用。</p><p>　　

87、③定期運(yùn)輸?shù)穆肪€優(yōu)化</p><p>　　在運(yùn)輸路線的選擇上，XX公司采納了由標(biāo)號(hào)法所得出的最大流量路線。定期運(yùn)輸?shù)谋壤遣淮_定的，事先找出最大流的路線，縮短了行駛的路線，減少了在運(yùn)輸路線上的油價(jià)、收費(fèi)等問題費(fèi)用。</p><p>　　5.2優(yōu)化貨物運(yùn)輸流量的建議</p><p>　　在上述的計(jì)算和模型求解中，我們可以知道，通過標(biāo)號(hào)法計(jì)算出運(yùn)輸流量的最大值，這是較為

88、簡便的計(jì)算方式之一。XX公司對(duì)于貨物運(yùn)輸這一方面的關(guān)注比較少，在之后的生產(chǎn)生活中可以加大對(duì)貨物運(yùn)輸?shù)牧髁績?yōu)化。特別是在選擇客戶時(shí)，在選擇運(yùn)輸工具也是一個(gè)切合實(shí)際的模型。本文中的模型計(jì)算中，最大流量為5，這也就確定了所需要的運(yùn)輸工具，可以是中小型的貨車，貨物流量是多少就用多少的運(yùn)輸車輛，極大地減少了車輛的空間浪費(fèi)和資源浪費(fèi)。具體如下：</p><p>　?、倨刚?qǐng)物流相關(guān)工作人員，加強(qiáng)最大流優(yōu)化的關(guān)注；</p&

89、gt;<p>　?、诮Y(jié)合企業(yè)的實(shí)際情況，配備有相應(yīng)噸位的運(yùn)輸車輛；</p><p>　?、鄹鶕?jù)網(wǎng)絡(luò)最大流的標(biāo)號(hào)法模型所得出的值，來制定出合理的車輛和運(yùn)輸路線，同時(shí)也可以用于對(duì)客戶的選擇；</p><p>　　④加大對(duì)零單、散貨情況的運(yùn)輸管理力度，針對(duì)散貨情況，購入電瓶三輪等較為輕便的運(yùn)輸車輛；</p><p><b>　　結(jié)論</b&g

90、t;</p><p>　　隨著科學(xué)技術(shù)的高速發(fā)展、市場競爭的日益激烈，使得產(chǎn)品的生命周期越來越短，消費(fèi)者更新產(chǎn)品的速度加快。尤其是消費(fèi)類電子產(chǎn)品，其更新周期更是較其他產(chǎn)品更短。而伴隨而至的資源日益匱乏和環(huán)境保護(hù)法規(guī)的實(shí)施，使得人們不得不對(duì)逆向物流給予更多的關(guān)注。</p><p>　　本文是一篇研究企業(yè)貨物運(yùn)輸網(wǎng)絡(luò)流量最大化的論文。首先闡述了研究背景、研究目的及其意義，并了解分析了國內(nèi)外研究

91、現(xiàn)狀及理論成果，提出優(yōu)化貨物運(yùn)輸網(wǎng)絡(luò)流量的必然性和該研究在企業(yè)中所帶來的實(shí)際價(jià)值以及現(xiàn)階段企業(yè)生產(chǎn)運(yùn)輸中存在的問題。其次，本文在本文中，選擇以鹽城市XX電子材料有限公司為研究的企業(yè)對(duì)象，分析了該企業(yè)在運(yùn)輸網(wǎng)絡(luò)上的現(xiàn)狀和存在的問題。而緊接著問題的發(fā)現(xiàn)，本文提出企業(yè)運(yùn)輸網(wǎng)絡(luò)流量優(yōu)化的計(jì)算方法，設(shè)計(jì)了簡單的運(yùn)輸模型：主要以標(biāo)號(hào)法，結(jié)合增廣路等進(jìn)行圖解。最后，以企業(yè)的客戶選擇、運(yùn)輸路線、運(yùn)輸流量優(yōu)化為目標(biāo)，以企業(yè)交通工具的實(shí)際設(shè)備情況為基礎(chǔ)，通

92、過運(yùn)輸弧的最大通過能力和實(shí)際運(yùn)輸流，制定合理的網(wǎng)絡(luò)優(yōu)化方案。</p><p>　　本文將理論引入實(shí)際研究，針對(duì)鹽城市XX電子材料有限公司貨物運(yùn)輸網(wǎng)絡(luò)流量的實(shí)際問題，收集各項(xiàng)數(shù)據(jù)，運(yùn)用標(biāo)號(hào)法求解，進(jìn)而得出鹽城市XX公司運(yùn)輸?shù)淖畲罅髁俊?lt;/p><p>　　本文綜述了網(wǎng)絡(luò)最大流的國內(nèi)外研究成果及現(xiàn)狀，闡述了網(wǎng)絡(luò)最大流的相關(guān)定義理念、特點(diǎn)、模型設(shè)計(jì)、計(jì)算方法和研究價(jià)值，并對(duì)XX公司運(yùn)輸系統(tǒng)進(jìn)行最

93、大流測(cè)試分析。除此之外，對(duì)于網(wǎng)絡(luò)最大流的研究背景、研究目的及其意義進(jìn)行了一定的論述，了解到了國內(nèi)外研究現(xiàn)狀及理論成果，提出優(yōu)化貨物運(yùn)輸網(wǎng)絡(luò)流量的必然性和該研究在企業(yè)中所帶來的實(shí)際價(jià)值以及現(xiàn)階段企業(yè)生產(chǎn)運(yùn)輸中存在的問題。同時(shí)本文以XX公司貨物運(yùn)輸為研究對(duì)象，論述了網(wǎng)絡(luò)最大流在企業(yè)生產(chǎn)生活中起到的作用。在此基礎(chǔ)上給出本文對(duì)XX公司貨物運(yùn)輸網(wǎng)絡(luò)流量最大化構(gòu)建的三個(gè)特征明顯的基本問題，即研究區(qū)域、研究方法、流量優(yōu)化，圍繞這三個(gè)問題，本文的主要結(jié)

94、論及成果如下：</p><p>　?。?）本文以XX電子材料公司為研究區(qū)域，該企業(yè)的客戶主要分散在鹽城市內(nèi)、市外以及周邊地區(qū)，是XX公司所生產(chǎn)的絕緣凡立水、稀釋劑等的主要用戶群體，而且根據(jù)這些客戶的心理特征共同購買習(xí)慣，追求的是值得信賴的商家、優(yōu)良的產(chǎn)品和快速的運(yùn)輸，這就使得，除了需要企業(yè)的生產(chǎn)技術(shù)之外，還必須配備有優(yōu)良的貨物運(yùn)輸系統(tǒng)，這就對(duì)運(yùn)輸系統(tǒng)有著一定的要求。</p><p>　?。?/p>

95、2）本文采用模型設(shè)計(jì)研究和標(biāo)號(hào)法相結(jié)合的理念，首先在遵循企業(yè)貨物運(yùn)輸網(wǎng)絡(luò)構(gòu)建的原則的前提下，根據(jù)模型和圖解的方法，確定五個(gè)網(wǎng)絡(luò)主體的備選客戶地址，同時(shí)為標(biāo)號(hào)法計(jì)算提供基礎(chǔ)數(shù)據(jù)。然后建立標(biāo)號(hào)法的圖解模型，由于研究對(duì)象、研究產(chǎn)品數(shù)量相對(duì)確定，而且研究結(jié)構(gòu)也較簡單，故相對(duì)了運(yùn)用了一定的相性規(guī)劃等知識(shí)為基本數(shù)學(xué)模型，代入數(shù)據(jù)，確定最大流量的選擇，從而構(gòu)建出企業(yè)在模型客戶的運(yùn)輸路線選擇和客戶選擇。</p><p>　?。?

96、）針對(duì)XX公司的貨物運(yùn)輸系統(tǒng)的研究，本文以企業(yè)與客戶的運(yùn)輸流量和位置距離為構(gòu)建模型的基本，進(jìn)行模型設(shè)計(jì)后，結(jié)合調(diào)查數(shù)據(jù)進(jìn)行求解，確定出較優(yōu)的客戶以及最大的運(yùn)輸流量。</p><p><b>　　致謝</b></p><p>　　值此論文定稿之際，首先我想要對(duì)給與我指導(dǎo)的我的導(dǎo)師傅X表示衷心感謝。大學(xué)四年期間的研究和學(xué)習(xí)都是在物流工程教研室各位老師的悉心指導(dǎo)和鼓勵(lì)下度過

97、的，作為老師，他們?cè)谖颐鞔_自身的研究方向給與了正確且合適的指點(diǎn)和忠告，在我遇到難題或者瓶頸時(shí)，為我點(diǎn)亮前進(jìn)的學(xué)習(xí)之燈。而關(guān)于畢業(yè)設(shè)計(jì)的研究方案、模型、方法等，他們用自身豐富的教學(xué)和實(shí)踐經(jīng)驗(yàn)，給了我眾多的經(jīng)驗(yàn)之談，讓我的畢業(yè)設(shè)計(jì)得到完善的同時(shí)也讓我的研習(xí)之路獲益匪淺。</p><p>　　以此同時(shí)，在本論文的寫作過程中，參考了大量的文獻(xiàn)資料，向這些文獻(xiàn)作者表示衷心的感謝！還有鹽城市XX電子材料有限公司的工作人員們，

98、在我獲取模型數(shù)據(jù)等資料時(shí)，提供了各類幫助，對(duì)此我表示感謝感激！</p><p><b>　　參考文獻(xiàn)</b></p><p>　　[1]華波.大規(guī)模網(wǎng)絡(luò)最大流問題研究[D]，2012</p><p>　　[2]石小法.物流工程[M].上海：同濟(jì)大學(xué)出版社，2009</p><p>　　[3]Fisher M L，Vehi

99、cle Routing[J].Handbooks in Operations Research ＆ Management Science Vol 8，1995，（3）：1-33.</p><p>　　[4]Dantzig G， Ramser J. The truck dispatching problem[J]. Management Science， 1959，（6）:80-91. </p>&l

100、t;p>　　[5]Clarke G， Wright JW. Scheduling of vehicles from a central depot to a number of delivery points[J].Operations Research 1964，12（4）:568-81.</p><p>　　[6]Fisher M， Jaikumar R. A Generalized Assignmen

101、t Heuristic for the vehicle routing problem[J].Networks 1981，（11）:109-24.</p><p>　　[7]王之泰.物資淺談[J].物資經(jīng)濟(jì)研究通訊，1981，（37）:32-34.</p><p>　　[8]Paolo Toth，Daniele Vigo. The vehicle routing problem [M].S

102、ociety for Industrial and Applied Mathematics philadephia.2002</p><p>　　[9]吳艷;楊有龍;劉三陽;;基于網(wǎng)絡(luò)流矩陣求解網(wǎng)絡(luò)最大流[J];系統(tǒng)工程;2007年10期</p><p>　　[10]孫小軍;王志強(qiáng);;無環(huán)網(wǎng)絡(luò)最大流的一種新算法[J];江西師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2009年03期</p>

103、<p>　　[11]張憲超 ，陳國良 ，萬穎瑜;網(wǎng)絡(luò)最大流問題研究進(jìn)展[J];計(jì)算機(jī)研究與發(fā)展;2003年09期</p><p>　　[12]凌永發(fā);徐宗本;;一種求解網(wǎng)絡(luò)最大流問題的算法[J];計(jì)算機(jī)科學(xué);2006年06期</p><p>　　[13]張憲超;江賀;;一個(gè)新的最大流問題增載軌算法[J];小型微型計(jì)算機(jī)系統(tǒng);2006年09期</p><p>

104、;　　[14]李穎;用蟻群算法求解最小極大流問題[D];河南理工大學(xué);2010年</p><p>　　[15]孟令玉;基于網(wǎng)絡(luò)流的開放式車間調(diào)度問題研究[D];哈爾濱工程大學(xué);2010年</p><p>　　[16]孫丹丹;無向網(wǎng)絡(luò)中有流量需求的轉(zhuǎn)運(yùn)節(jié)點(diǎn)的最大流算法[D];西安電子科技大學(xué);2010年</p><p>　　[17]孟曉婉;網(wǎng)絡(luò)最大流算法與應(yīng)用研究[D

105、];南京郵電大學(xué);2013年</p><p>　　[18]鄢長偉;一類動(dòng)態(tài)規(guī)劃問題的約束指標(biāo)的決策方法[D];遼寧工程技術(shù)大學(xué);2012年</p><p>　　[19]喬銀華;基于動(dòng)態(tài)規(guī)劃的應(yīng)急資源運(yùn)輸調(diào)度研究[D];鄭州輕工業(yè)大學(xué);2010年</p><p>　　[20]張晨;基于近似動(dòng)態(tài)規(guī)劃的隨機(jī)車輛路徑問題研究[D];清華大學(xué);2012年</p>

106、<p>　　[21]董白波.運(yùn)輸管理學(xué)[M].上海：上海大學(xué)出版社，2009年</p><p>　　[22]邢以群.管理學(xué)[M].北京：高等教育出版社，2011年</p><p>　　[23]盧松泉.供應(yīng)鏈管理[M].鄭州：河南科學(xué)技術(shù)出版社，2010年</p><p>　　[24]芮明杰，錢平凡著.再造流程[M].浙江：浙江人民出版社，2005年<