基于GPS技術(shù)的動態(tài)路由算法在物流配送系統(tǒng)中的應(yīng)用

摘 要 本文通過對傳統(tǒng)物流配額送算法和因特網(wǎng)中的動態(tài)路由算法的研究，提出了基于GPS技術(shù)的動態(tài)路由算法，研發(fā)基于可視化的實(shí)時(shí)交通信息數(shù)據(jù)挖掘分析算法，最終計(jì)算出可以代表整個(gè)路況的權(quán)值，即時(shí)間最短權(quán)值，為每個(gè)站點(diǎn)的路由表更新提供動態(tài)的權(quán)值數(shù)據(jù)。從而確保路由表的路徑為時(shí)間權(quán)值最小，最終確保整個(gè)物流配送時(shí)間最短，達(dá)到高效、 合理、 暢通的物流配送要求。

關(guān)鍵詞 動態(tài)路由 GPS交通分析系統(tǒng) 大數(shù)據(jù)處理 物流配送

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

0 引言

物流配送是物流企業(yè)日常生產(chǎn)中一個(gè)非常重要的環(huán)節(jié)，是電子商務(wù)發(fā)展中的“瓶頸”，其效率高低直接影響物流企業(yè)的運(yùn)作效益。因此必須建設(shè)一個(gè)高效、 合理、 暢通的物流配送系統(tǒng)，以達(dá)到提高效益、 增加利潤和減少成本的目的。在配送管理中，經(jīng)常需要決策的一個(gè)問題就是如何尋找一組最優(yōu)的車輛路徑，將貨物配送到每個(gè)客戶手中，也即所謂的車輛路徑問題。VRP本質(zhì)上是一個(gè)NP—hard問題，是組合優(yōu)化領(lǐng)域的前沿與熱點(diǎn)問題之一。對于這類間題，當(dāng)問題的規(guī)模較大時(shí)，將很難得到全局最優(yōu)解或滿意解。而且隨著問題規(guī)模的增大，算法的計(jì)算時(shí)間將以指數(shù)速度增加。目前主要的物流優(yōu)化路徑算法為基于圖論的Dijkstra算法、蟻群算法等。

本文要提出的是一種新型的物流配送算法，該算法是基于GPS技術(shù)的動態(tài)路由思想的。基于IP/TCP協(xié)議的因特網(wǎng)將報(bào)文打包分組，報(bào)文到達(dá)一個(gè)路由器然后查找路由表，進(jìn)行存儲轉(zhuǎn)發(fā)，最終到達(dá)目的地。路由器使用動態(tài)路由算法來找到到達(dá)目的地的最佳路由，當(dāng)說“最佳路由”時(shí)，考慮的參數(shù)包括諸如跳躍數(shù)、延時(shí)以及分組數(shù)據(jù)包傳輸通信耗時(shí)，并且每個(gè)路由表實(shí)時(shí)更新的。將此路由轉(zhuǎn)發(fā)思想應(yīng)用到物流配送系統(tǒng)中，物品中轉(zhuǎn)站相當(dāng)于路由器，貨品類比于數(shù)據(jù)報(bào)。同樣最佳路由線路就是完成某個(gè)物流分配任務(wù)時(shí)間最少，每個(gè)物流中轉(zhuǎn)站的路由表總是根據(jù)GPS提供的交通道路情況實(shí)時(shí)更新的，這樣就滿足了物流配送系統(tǒng)實(shí)時(shí)更新時(shí)間最短的要求。

1 算法的理論研究

1.1 分組路由思想

路由器的某一個(gè)接口在收到一個(gè)報(bào)文后：首先進(jìn)行幀的拆封以便從中分離出相應(yīng)的IP分組；然后利用子網(wǎng)掩碼求“與”方法從IP分組中提取出目標(biāo)網(wǎng)絡(luò)號；將目標(biāo)網(wǎng)絡(luò)號與路由表進(jìn)行比對看能否找到一種匹配，即確定是否存在一條到達(dá)目標(biāo)網(wǎng)絡(luò)的最佳路徑信息；若存在匹配，則將IP分組重新進(jìn)行封裝成出去端口所期望的幀格式并將其從路由器相應(yīng)端口轉(zhuǎn)發(fā)出去；若不存在匹配，則將相應(yīng)的IP分組丟棄。

1.2 最短路徑算法—Dijkstra算法

1.3 實(shí)時(shí)路況數(shù)據(jù)采集，計(jì)算各個(gè)路徑權(quán)值

GPS導(dǎo)航系統(tǒng)是以全球24顆定位人造衛(wèi)星為基礎(chǔ)，向全球各地全天候地提供三維位置、三維速度等信息的一種無線電導(dǎo)航定位系統(tǒng)。它由三部分構(gòu)成，一是地面控制部分，由主控站、地面天線、監(jiān)測站及通訊輔助系統(tǒng)組成。二是空間部分，由24顆衛(wèi)星組成，分布在6個(gè)軌道平面。三是用戶裝置部分，由GPS接收機(jī)和衛(wèi)星天線組成。民用的定位精度可達(dá)10米內(nèi)。其數(shù)據(jù)具體數(shù)據(jù)格式包括：（車ID，經(jīng)度，緯度，速度GPS）→原始數(shù)據(jù)，GPS預(yù)處理數(shù)據(jù)，GPS匹配后的數(shù)據(jù)。

1.4 物流配送算法的流程

GPS根據(jù)智能終端，統(tǒng)一發(fā)送數(shù)據(jù)到交通信息中心，通過對大數(shù)據(jù)進(jìn)行清洗和整合，最終計(jì)算出各個(gè)物流中轉(zhuǎn)站（站點(diǎn)）的時(shí)間權(quán)值，各個(gè)節(jié)點(diǎn)根據(jù)最新的權(quán)值信息更新路由表，物流配送車輛根據(jù)最新路由信息，選擇路徑，最終到達(dá)目的地。

2 基于動態(tài)路由算法的物流配送實(shí)例分析

3 結(jié)語

本文主要是將互聯(lián)網(wǎng)中的動態(tài)路由轉(zhuǎn)發(fā)思想應(yīng)用到物流配送系統(tǒng)中，通過動態(tài)路由算法和物流配送的理論研究，結(jié)合GPS交通情況的分析，最終解決了物流配送的路徑問題。該算法是針對復(fù)雜的物流配送系統(tǒng)的，GPS交通分析系統(tǒng)需要大量終端的支持，即采集樣本信息，可以提高權(quán)值的準(zhǔn)確性和實(shí)時(shí)性。GPS交通分析系統(tǒng)采集實(shí)時(shí)GPS信息，并對大數(shù)據(jù)進(jìn)行清洗和處理，更新各個(gè)表以及對應(yīng)的權(quán)值，各個(gè)中轉(zhuǎn)站根據(jù)最新的權(quán)值信息更新自己的路由表，通過實(shí)時(shí)的GPS信息更新可以確保路由表的項(xiàng)目是最新的路由，物流配送車輛到達(dá)每個(gè)節(jié)點(diǎn)之后只需查找路由表進(jìn)行轉(zhuǎn)發(fā)，從而可以確保時(shí)間最短的需求，節(jié)約時(shí)間和資源，確保物流配送系統(tǒng)的高效運(yùn)行。

參考文獻(xiàn)

[1] 李原.基于狀態(tài)穩(wěn)定性更新的距離向量路由算法.計(jì)算機(jī)工程，2007.

[2] 姜桂艷.基于GPS浮動車的交通信息采集系統(tǒng)的數(shù)據(jù)組織方法.吉林大學(xué)學(xué)報(bào)，2010.

[3] 胡祥培.物流配送系統(tǒng)干擾管理模型研究.管理科學(xué)學(xué)報(bào)，2011.