王慶澤

【摘要】物流業(yè)在我國(guó)得到了迅速的發(fā)展，尤其近年來(lái)，第三方物流企業(yè)和電子商務(wù)平臺(tái)的逐漸興起更是使得國(guó)家和政府對(duì)物流企業(yè)予以了重視。然而，由于我國(guó)地域跨度大，物流尚處于初中期發(fā)展階段，物流路線并沒(méi)有得到很好的規(guī)劃。論文應(yīng)用圖論的方法，以X物流企業(yè)在浙江省各個(gè)城市的配送路線規(guī)劃為例，介紹了最小樹(shù)算法和最鄰近算法在對(duì)物流配送路線規(guī)劃中的應(yīng)用，并對(duì)其優(yōu)缺點(diǎn)進(jìn)行了評(píng)價(jià)。

【關(guān)鍵詞】物流配送；最小樹(shù)算法；最鄰近算法

中圖分類號(hào)：F27 文獻(xiàn)標(biāo)識(shí)碼A： 文章編號(hào)：1006-0278（2014）05-071-02

一、引言

物流是供應(yīng)鏈活動(dòng)的一部分，是為了滿足客戶需要而對(duì)商品、服務(wù)以及相關(guān)信息從產(chǎn)地到消費(fèi)地的高效、低成本流動(dòng)和儲(chǔ)存進(jìn)行的規(guī)劃、實(shí)施與控制的過(guò)程?，F(xiàn)代物流作為一種先進(jìn)的組織方式和管理技術(shù)，已成為世界經(jīng)濟(jì)發(fā)展的熱點(diǎn)之一。

物流有七個(gè)基本職能：運(yùn)輸、包裝、信息處理、裝卸搬運(yùn)、流通加工、倉(cāng)儲(chǔ)和配送。物流配送是指按照客戶的要求，經(jīng)過(guò)分貨、揀選等貨物配備工作，把最終產(chǎn)品從生產(chǎn)線的末端到消費(fèi)者手中的移動(dòng)和存儲(chǔ)過(guò)程。在物流配送中，最為關(guān)鍵的是物流配送路線的設(shè)計(jì)與規(guī)劃。合理確定配送路線就是用最少的動(dòng)力，走最短的里程，花最少的費(fèi)用，經(jīng)最少的環(huán)節(jié)，以最快的速度把貨物運(yùn)至用戶手中。合理規(guī)劃配送路線對(duì)配送成本的影響要比一般運(yùn)輸大得多，所以必須在全面計(jì)劃的基礎(chǔ)上，制定高效的運(yùn)輸路線，選擇合理的運(yùn)輸方式和運(yùn)輸工具。

據(jù)統(tǒng)計(jì)，在我國(guó)，物流費(fèi)用占了貨品總成本的30%，運(yùn)輸成本比西方發(fā)達(dá)國(guó)家高出3倍。另外，從產(chǎn)品的供應(yīng)鏈結(jié)構(gòu)來(lái)看，90%的時(shí)間消耗在流通環(huán)節(jié)，在生產(chǎn)環(huán)節(jié)的時(shí)間只占10%。另?yè)?jù)統(tǒng)計(jì)，2011年，全國(guó)社會(huì)物流總額達(dá)158.4萬(wàn)億元，同比增長(zhǎng)12.3%。國(guó)內(nèi)現(xiàn)代物流業(yè)實(shí)現(xiàn)增加值3.2萬(wàn)億元，同比增長(zhǎng)13.9%。全國(guó)社會(huì)現(xiàn)代物流總費(fèi)用為88.4萬(wàn)億元，同比增長(zhǎng)18.5%，但第三方物流在整個(gè)物流需求中所占的份額不足4%，遠(yuǎn)低于發(fā)達(dá)國(guó)家。另外，我國(guó)實(shí)際完成的貨運(yùn)總量遠(yuǎn)少于需要運(yùn)輸?shù)膶?shí)物量，使貨物在途時(shí)間延長(zhǎng)，壓港、壓航、壓庫(kù)嚴(yán)重。同時(shí)在我國(guó)的外包物流服務(wù)中，85%來(lái)自基礎(chǔ)性服務(wù)，其中53%來(lái)自運(yùn)輸管理，32%來(lái)自倉(cāng)儲(chǔ)管理，增值服務(wù)及物流信息的財(cái)務(wù)收益只占15%。而在美國(guó)，來(lái)自基礎(chǔ)性服務(wù)的收益占62%，增值服務(wù)的比例已達(dá)38%。因此我們不難看出：盡管目前我國(guó)社會(huì)物流需求持續(xù)高速增長(zhǎng)，物流業(yè)增加值穩(wěn)步上升，物流服務(wù)在我國(guó)仍占主導(dǎo)地位，但物流發(fā)展的總體水平還比較低，問(wèn)題比較突出。

二、圖論應(yīng)用

（一）圖論應(yīng)用方法介紹

1.背景介紹。圖論是應(yīng)用十分廣泛的運(yùn)籌學(xué)分支，它很好地應(yīng)用于物理學(xué)、化學(xué)、控制論、信息論、科學(xué)管理、電子計(jì)算機(jī)等各個(gè)領(lǐng)域。在實(shí)際生活、生產(chǎn)和科學(xué)研究中，有很多問(wèn)題可以用圖論的理論和方法來(lái)解決。例如，完成工程任務(wù)的時(shí)間最少、距離最少、距離最短、費(fèi)用最省等。圖論受到數(shù)學(xué)、工程技術(shù)及經(jīng)營(yíng)管理等各個(gè)方面越來(lái)越廣泛的重視。

在物流配送中，由于配送成本主要受到運(yùn)輸路程的影響，因此對(duì)配送路線的合理規(guī)劃與設(shè)計(jì)顯得尤其重要。本文以某物流企業(yè)在浙江省的配送情況為例，對(duì)該企業(yè)在浙江省幾個(gè)城市的物流配送路線進(jìn)行了規(guī)劃設(shè)計(jì)。

2.基本概念。首先將論文中所用到的基本概念簡(jiǎn)單介紹如下：（1）圈：任選一個(gè)頂點(diǎn)為起點(diǎn)，沿著不重復(fù)的頂點(diǎn)為途徑，之后又回到起點(diǎn)的閉合途徑稱為圈。（2）樹(shù)：一個(gè)無(wú)圈的連通圖稱為樹(shù)。（3）支撐樹(shù)：設(shè)圖T=（V，E）是圖G=（V，E）的支撐子圖，如果圖T=（V，E）是一個(gè)樹(shù)，則稱T是G的一個(gè)支撐樹(shù)。（4）連通圖：在圖G中，若任何兩點(diǎn)之間至少有一條鏈，則稱G是連通圖，否則稱為不連通圖。（5）最小支撐樹(shù)：假設(shè)連通圖中每個(gè)邊都有一個(gè)權(quán)，如果支撐樹(shù)T上所有邊的權(quán)之和是所有支撐樹(shù)中權(quán)的最小者，則稱T是G的最小支撐樹(shù)。

（二）論文數(shù)據(jù)來(lái)源及前提假設(shè)

1.數(shù)據(jù)來(lái)源。物流運(yùn)輸費(fèi)用包括貨車的燃油費(fèi)用、收費(fèi)路段的路橋費(fèi)、運(yùn)輸人員的工資、車輛維修費(fèi)用等，由于本論文側(cè)重于從減少整個(gè)物流配送網(wǎng)絡(luò)的運(yùn)輸距離，從而減少路費(fèi)，因此主要用到的數(shù)據(jù)是浙江省各城市之間的距離，數(shù)據(jù)來(lái)源《中國(guó)交通地圖冊(cè)》。所選取的城市有杭州、湖州、嘉興、舟山、寧波、紹興、衢州、金華、麗水、溫州、臺(tái)州。因此本文選取了11個(gè)城市進(jìn)行分析與計(jì)算。各城市間距離如圖1所示：假設(shè)除舟山外，浙江省各城市均可以直接相連，而舟山僅與寧波直接相連。匯總浙江省各城市間直接到達(dá)距離如表1所示（單位：公里）：

2.前提假設(shè).物流配送是一個(gè)復(fù)雜的過(guò)程，需要考慮的問(wèn)題很多。本文重點(diǎn)考慮圖論在物流配送路線規(guī)劃中的作用，因此論文有如下前提假設(shè)：（1）論文假設(shè)使用的交通工具只有貨車（因此舟山是一個(gè)懸掛點(diǎn)，只與寧波直接相連）；（2）在計(jì)算路橋費(fèi)的時(shí)候，雖然每條路線都是部分路段是收費(fèi)路段，但論文為了簡(jiǎn)化計(jì)算過(guò)程，沒(méi)有細(xì)分哪些是收費(fèi)路段；（3）論文假設(shè)設(shè)定的線路上貨車可以裝載所有的貨物，與車型和車輛數(shù)無(wú)關(guān)，因此運(yùn)輸費(fèi)用只與運(yùn)輸距離相關(guān)；（4）論文假設(shè)往返運(yùn)貨量和運(yùn)輸距離是等量的，例如，從杭州到溫州和從溫州到杭州的運(yùn)貨量和運(yùn)輸距離是相同的；（5）論文假設(shè)每配送到一個(gè)城市，都會(huì)對(duì)貨物進(jìn)行整合。

（三）避圈法在某企業(yè)浙江省主要城市中物流配送的路線研究

1.方法介紹

由上述假設(shè)可以看出，如果只考慮運(yùn)輸距離，那么對(duì)于運(yùn)輸費(fèi)用最小化的求解恰是一個(gè)典型的求解最小支撐樹(shù)的問(wèn)題。

求解支撐樹(shù)有兩種簡(jiǎn)單而又常用的方法：