王慶澤

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

【關鍵詞】物流配送；最小樹算法；最鄰近算法

中圖分類號：F27 文獻標識碼A： 文章編號：1006-0278（2014）05-071-02

一、引言

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

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

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

二、圖論應用

（一）圖論應用方法介紹

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

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

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

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

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

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

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

1.方法介紹

由上述假設可以看出，如果只考慮運輸距離，那么對于運輸費用最小化的求解恰是一個典型的求解最小支撐樹的問題。

求解支撐樹有兩種簡單而又常用的方法：