基于ＧＰＳ的煙草物流配送線路規(guī)劃

摘要：文章以煙草物流配送為研究對象，介紹了GPS/GIS技術(shù)在煙草物流配送中的應(yīng)用，在GPS實時監(jiān)控的基礎(chǔ)上提出以在途時間來衡量配送運輸線路的工作量，據(jù)此來進(jìn)行配送運輸線路規(guī)劃，得出適合煙草物流實際的配送運輸線路規(guī)劃方法。

關(guān)鍵詞：全球定位系統(tǒng)（GPS）；在途時間；物流；配送；煙草；地理信息系統(tǒng)（GIS）；車輛路線問題（VRP）

中圖分類號：U116.2文獻(xiàn)標(biāo)識碼：A

文章編號：1002-3100(2008)09-0018-03

Abstract: This thesis uses logistics and distribution of a tobacco company， introduces the application of the GPS/GIS technology in logistics and distribution. In the basis of GPS real-time monitoring， using transit time to measure the distributed delivery route will be advanced， and then plan the delivery route， educe the suitable planning method for the actual distribution transportation route of this tobacco company.

Key words: global positioning system(GPS）; the transit time; logistics; distribution; tobacco; geographic information system （GIS）; vehicle routing problem（VRP）

1前言

物流配送路線規(guī)劃的核心是車輛路線問題。Dantzig和Ramser于1959 年首次提出了車輛路線問題（Vehicle Routing Problem，VRP），很快得到了運籌學(xué)理論、概率論和隨機理論等學(xué)科的專家學(xué)者的關(guān)注，Bodlin、Christofider、Golden、Assad、Ball 等人對該問題進(jìn)行了更深入的研究，他們進(jìn)行了大量的理論和實踐研究，取得了很大進(jìn)展。車輛路線問題定義為：對一系列發(fā)貨點、收貨點，組織適當(dāng)?shù)男熊嚶肪€，使車輛有序地通過它們，在滿足一定的約束條件（如貨物需求量、發(fā)送量、交發(fā)貨時間、車輛容量限制、行駛里程限制、時間限制等）下，達(dá)到一定的目標(biāo)（如路程最短、費用最小、時間最短等）。

1.1GPS概念

GPS（Global Positioning Systems）是美國歷經(jīng)20年，耗資超過300億美元建立的全球衛(wèi)星定位系統(tǒng)，包括繞地球運行的２４顆衛(wèi)星，它們均勻地分布在６個軌道上。每顆衛(wèi)星距離地面約１.７萬公里，能連續(xù)發(fā)射一定頻率的無線電信號，實時提供三維位置、速度和高精度的時間信息。

GPS信號接收設(shè)備中常見的是便攜式信號接收儀，包括GPS接收卡或外接設(shè)備，由天線、接收單元和電源組成，體積很小，可方便地裝載在汽車等交通工具上。只要持有便攜式信號接收儀，無論身處陸地、海上還是空中，都能收到衛(wèi)星發(fā)出的特定信號。

1.2GIS概念

GIS（Geographical Information System）是20世紀(jì)60年代開始迅速發(fā)展起來的地理學(xué)研究技術(shù)，是多種學(xué)科交叉的產(chǎn)物。GIS以地理空間數(shù)據(jù)庫為基礎(chǔ)，在計算機軟硬件支持下，實現(xiàn)對空間信息的采集、存儲、管理、操作、分析模擬和顯示，采用地理模型分析方法，適時提供多種空間的和動態(tài)的地理信息，為地理研究和地理決策服務(wù)的計算機技術(shù)系統(tǒng)。

1.3GPS/GIS在物流配送中的應(yīng)用

在物流配送中的應(yīng)用主要是: （1）用于汽車自定位、跟蹤調(diào)度、陸地救援。（2）用于內(nèi)河及遠(yuǎn)洋船隊最佳航程和安全航線的測定、航向的實時調(diào)度、監(jiān)測及水上救援。（3）用于空中交通管理、精密進(jìn)場著陸、航路導(dǎo)航

和監(jiān)視。（4）用于鐵路運輸管理。

在公路汽車運輸物流配送中的具體應(yīng)用主要體現(xiàn)在以下兩方面：

（1）車輛和貨物跟蹤：利用 GPS/GIS技術(shù)可以實時顯示出車輛的實際位置，并任意放大、縮小、換圖；可以隨目標(biāo)移動，使目標(biāo)始終保持在屏幕上；還可實現(xiàn)多窗口、多車輛、多屏幕同時跟蹤，可對重要車輛和貨物進(jìn)行跟蹤運輸，以便進(jìn)行合理調(diào)度和管理。

（2）貨物配送路線規(guī)劃和導(dǎo)航：利用 GPS/GIS技術(shù)，設(shè)計最佳行駛路線，包括最快的路線、最簡單的路線、通過高速公路路段次數(shù)最少的路線等。路線規(guī)劃好之后，利用 GPS的三維導(dǎo)航功能，通過顯示器顯示設(shè)計路線及汽車運行路線和運行方法。

2煙草物流配送相關(guān)理論方法

2.1煙草物流配送問題描述

煙草物流配送的實際情況如下：

煙草物流中心負(fù)責(zé)全市煙草零售網(wǎng)點的物流配送任務(wù)，零售網(wǎng)點分布在全市各地，其總體數(shù)量大致穩(wěn)定，但仍有少量增長，零售網(wǎng)點的地理位置有時會有改變，甚至撤銷該網(wǎng)點。

物流配送車輛由單個物流中心出發(fā)，配送到全市各零售網(wǎng)點，配送完成后車輛返回該物流中心，而且所有配送車輛為同一型號，裝載量相同。

物流配送的工作量最終根據(jù)配送所需的時間（在途時間）來衡量，由于配送車輛上都裝有GPS定位終端，GPS監(jiān)控中心能實時監(jiān)控每一輛物流車輛的動態(tài)信息，為以時間作為工作量考核標(biāo)準(zhǔn)打下了基礎(chǔ)。

總體工作量（配送所需的總時間）一定的情況下，在物流配送線路規(guī)劃時考慮各配送線路的配送工作量大致平衡，避免出現(xiàn)某些配送運輸線路超負(fù)荷工作，而其他卻有些配送運輸線路工作量很低。

2.2配送運輸線路規(guī)劃

2.2.1配送運輸線路規(guī)劃步驟

煙草物流配送運輸線路規(guī)劃步驟如圖1：

首先，根據(jù)以往數(shù)據(jù)統(tǒng)計各零售網(wǎng)點的平均需求量，以平均需求量作為該網(wǎng)點的需求計算數(shù)值，忽略極端峰值和極端低值；

其次，集合經(jīng)驗豐富的老調(diào)度員，根據(jù)以往的調(diào)度經(jīng)驗對全市范圍內(nèi)的零售網(wǎng)點進(jìn)行配送運輸線路的區(qū)域劃分；

再次，以上述區(qū)域劃分為基礎(chǔ)，根據(jù)Gillett和Miller的Sweep算法，形成零售點的徑向區(qū)域，從物流中心發(fā)出的射線掃過這個區(qū)域，是不超過車輛容量的零售點組成一個區(qū)域，一個區(qū)域就是一個配送運輸線路，再根據(jù)各配送運輸線路的配送工作量大致平衡的原則進(jìn)行微調(diào)；

最后，對具體配送運輸線路上各零售點的配送順序進(jìn)行優(yōu)化。

2.2.2以在途時間來衡量配送運輸線路的工作量

煙草物流配送的一個原則就是要使各配送運輸線路的配送工作量大致平衡，這就涉及到工作量的計算方法。本文提出了一個新的計算辦法，不是直接根據(jù)配送路程的長短、送貨量的多少、經(jīng)過的零售點的數(shù)量來計算工作量，而是把這些指標(biāo)都換算成在途時間這一個指標(biāo)來進(jìn)行衡量，即只要能保證從物流中心出發(fā)，完成每條配送運輸線路的配送任務(wù)并返回物流中心這一過程的在途時間相等，我們就認(rèn)為各配送運輸線路的配送工作量相等。

根據(jù)在途時間來最終衡量配送運輸線路是否公平，其最大的問題是無法對配送運輸車輛的狀態(tài)進(jìn)行實時監(jiān)控，這樣會導(dǎo)致一系列的問題，如：配送人員不根據(jù)規(guī)劃好的配送線路行駛、配送人員把車停下消極應(yīng)付時間、或者是到某一零售點后長時間閑聊不走等。這些問題隨著GPS系統(tǒng)的使用而一一解決，在配送車輛上都裝有GPS定位終端，GPS監(jiān)控中心就能實時監(jiān)控每一輛物流車輛的動態(tài)信息，為以時間作為工作量考核標(biāo)準(zhǔn)打下了基礎(chǔ)。

2.2.3在途時間的計算

上文提到以在途時間作為煙草物流配送運輸線路工作量的衡量標(biāo)準(zhǔn)，其在途時間的組成可分為以下幾部分：物流中心到配送運輸線路區(qū)域中心的時間；配送運輸線路區(qū)域中心到本線路區(qū)域內(nèi)各零售點的總時間；各零售點停車配送的總時間。

物流配送區(qū)域如圖2所示。

區(qū)域中心為某一具體配送運輸線路上各零售點組成的多邊形的幾何中心。

下文對在途時間的幾個組成部分加以描述：

為了計算方便，且這里總時間的計算是為了保證各配送運輸線路工作量的公平，所以只單純的計算從區(qū)域中心到本線路區(qū)域內(nèi)各零售點的時間總和，沒考慮類似旅行商問題的從區(qū)域中心出發(fā)，訪問區(qū)域內(nèi)所有零售點后再回到區(qū)域中心的問題。由于其他各條配送運輸線路都采用相同的算法，總體來說是相對公平的。實際針對每條配送運輸線路進(jìn)行煙草配送時，具體的配送節(jié)點順序在下文有詳細(xì)描述。

其中，n為本線路區(qū)域內(nèi)零售點的總數(shù)；t為各零售點停車配送的平均時間，這里取某煙草公司長期統(tǒng)計的平均數(shù)據(jù)30分鐘（0.5h）。

綜上，某一具體配送運輸線路的在途時間T為：

2.2.4具體配送運輸線路節(jié)點配送順序

完成對配送運輸線路的區(qū)域劃分后，需要對具體配送運輸線路上各零售點的配送順序進(jìn)行優(yōu)化，這時已經(jīng)把復(fù)雜的配送運輸線路規(guī)劃問題轉(zhuǎn)化為單一的旅行商問題。旅行商問題是基本車輛路線問題之一，長期以來已有很多學(xué)者針對這一問題給出了許多改進(jìn)算法，本文對其具體算法不作詳細(xì)介紹。

3結(jié)論

本文在GPS實時監(jiān)控的基礎(chǔ)上提出以在途時間來衡量配送運輸線路的工作量，據(jù)此來進(jìn)行配送運輸線路規(guī)劃，從而得出適合煙草物流實際的配送運輸線路。

隨著社會經(jīng)濟(jì)的發(fā)展，整合了GPS 技術(shù)、GIS 技術(shù)和現(xiàn)有的GPRS資源技術(shù)優(yōu)勢于一體的物流配送技術(shù)，在現(xiàn)代物流企業(yè)邁向信息化、科技化和系統(tǒng)化過程中，應(yīng)用范圍將會越來越廣泛。

參考文獻(xiàn)：

[1] 郭耀煌，李軍. 車輛優(yōu)化調(diào)度問題的研究現(xiàn)狀評述[J]. 西南交通大學(xué)學(xué)報， 1995(4):376-382.

[2] 孔祥強.GIS/GPS 在物流配送中的應(yīng)用[J]. 價值工程，2006(11):87-88.

[3] 張超，陳丙咸，鄔倫. 地理信息系統(tǒng)[M]. 北京：高等教育出版社，1998.

[4] 郭令. 現(xiàn)代物流管理中的3G技術(shù)[J]. 三晉測繪，2003，10(3):22-24.

[5] 陳子俠. 基于GIS物流配送線路優(yōu)化與仿真[M]. 北京：經(jīng)濟(jì)科學(xué)出版社，2007.