袁建清，修建新，王澤彬

(1.黑龍江東方學(xué)院;2.哈爾濱工業(yè)大學(xué))

基于GPS/GIS/GPRS技術(shù)的動態(tài)車輛調(diào)度系統(tǒng)設(shè)計與實現(xiàn)*

袁建清1，修建新1，王澤彬2

(1.黑龍江東方學(xué)院;2.哈爾濱工業(yè)大學(xué))

針對車輛配送動態(tài)調(diào)度問題，在以基于并行節(jié)約法和禁忌搜索的混合禁忌搜索算法為理論進行靜態(tài)調(diào)度求解的基礎(chǔ)上，將新的客戶需求設(shè)置為虛擬點并以局部調(diào)整策略實現(xiàn)VRPB的動態(tài)調(diào)度計算.開發(fā)基于GPS/GIS/GPRS技術(shù)的動態(tài)車輛調(diào)度系統(tǒng).該系統(tǒng)能夠?qū)崟r跟蹤車輛位置，檢測新的客戶需求，以這些參數(shù)作為輸入動態(tài)地優(yōu)化車輛配送方案和行駛路徑，并通過GPRS將調(diào)度結(jié)果快速準確地傳送給車輛.

動態(tài)調(diào)度;GPS/GIS/GPRS;禁忌搜索;節(jié)約法

0 引言

車輛調(diào)度問題［1］(VSP)是物流配送中心配送決策中的重要內(nèi)容.目前國內(nèi)已有利用啟發(fā)式算法開發(fā)出的車輛調(diào)度系統(tǒng)，用于解決物流中運輸車輛的路線選擇和車輛分配等問題，使得運輸車輛利用率提高，并降低了運輸成本.但多數(shù)系統(tǒng)的都是靜態(tài)調(diào)度系統(tǒng)，無法滿足實時動態(tài)優(yōu)化的需求.

該文用一種混合禁忌搜索算法求解帶時間窗靜態(tài)車輛調(diào)度問題，通過將新的客戶需求設(shè)置虛擬點的方法和局部調(diào)整策略將動態(tài)車輛調(diào)度轉(zhuǎn)化成靜態(tài)車輛調(diào)度問題進行計算.并在此基礎(chǔ)上，開發(fā)設(shè)計了動態(tài)車輛調(diào)度系統(tǒng)，系統(tǒng)中通過GPS和GIS［2］技術(shù)實時反映每個時間點的車輛和客戶情況，作為系統(tǒng)進行動態(tài)調(diào)度數(shù)據(jù)基礎(chǔ)，通過GPRS及時發(fā)送動態(tài)調(diào)度方案，保證調(diào)度計劃的高效執(zhí)行.

1 動態(tài)調(diào)度算法設(shè)計

1.1 動態(tài)車輛調(diào)度設(shè)計策略

動態(tài)車輛調(diào)度有兩種情況:一是有新增客戶需求，以最低成本動態(tài)的添加到現(xiàn)有車輛路徑中.二是車輛在行駛過程遇到車輛故障等突發(fā)情況，應(yīng)將運輸任務(wù)動態(tài)的安排到其他現(xiàn)有車輛完成.

目前的很多車輛調(diào)度算法都是靜態(tài)的，即在分配和安排車輛運輸路線總是從配送中心出發(fā)，而在動態(tài)車輛調(diào)度中，當新客戶需求發(fā)生或條件發(fā)生變化時運輸車輛可能已經(jīng)駛離了配送中心.為此，引入“虛擬點”概念，即將車輛的當前位置作為一個任務(wù)點來處理，稱為虛擬任務(wù)點［3］.這里虛擬任務(wù)點的約束定義如下:

(1)虛擬任務(wù)點處于各條路徑的起點.

(2)對于配送任務(wù)，要求對于已出發(fā)的車輛必須經(jīng)過原來已經(jīng)分配的配送任務(wù)點;如果是集貨任務(wù)，沒有此要求.

(3)虛擬任務(wù)點貨物量設(shè)置為已完成的各需求點貨物量的總和.

(4)將虛擬任務(wù)點的時間窗約束收縮到那個對應(yīng)的時間點上，因為車輛經(jīng)過虛擬任務(wù)點的事實已經(jīng)發(fā)生且時間也是確定的.

通過引入虛擬任務(wù)點并添加相應(yīng)約束，就可以將動態(tài)車輛調(diào)度問題轉(zhuǎn)化成為靜態(tài)問題進行求解，采用局部調(diào)整的優(yōu)化策略，進行實時的車輛調(diào)度.具體的動態(tài)調(diào)度流程如圖1所示.

圖1 動態(tài)車輛調(diào)度流程

1.2 靜態(tài)車輛調(diào)度算法

將行使里程與車輛數(shù)量統(tǒng)一作為優(yōu)化目標，采用混合禁忌搜索算法對該問題進行有效求解.

禁忌搜索算法［4］(TS)是對局部領(lǐng)域搜索的一種擴展，是一種全局逐步尋優(yōu)算法.但其全局尋優(yōu)能力對初始解有較強的依賴性，一個好的初始解是TS算法求出理想解的一個重要條件［5］.因此，先采用C-K節(jié)約算法［6］構(gòu)造一個好的初始可行解，然后采用改進的禁忌搜索算法進行優(yōu)化.混合禁忌搜索算法與以往禁忌搜索算法主要改進有以下三點:

(1)初始解的形成:利用C-K節(jié)約算法構(gòu)造初始可行解，提供了一個較好的初始解［7］.

(2)鄰域結(jié)構(gòu)的構(gòu)造:根據(jù)連續(xù)未找到更好解的迭代步數(shù)R動態(tài)地調(diào)整2-opt交換算子，用這種方法來構(gòu)造候選解的個數(shù)C，具體策略如式(1)所示.

其中m是根據(jù)問題規(guī)模設(shè)定的調(diào)整因子.

(3)禁忌長度的選取:采用動態(tài)選取策略，在開始迭代R0步后，每搜索R步設(shè)置一個檢測點，判斷當前目標值Sk相對于R步前的目標值SK-R的下降程度，如果下降程度小，就相應(yīng)的減小禁忌長度;否則就相應(yīng)的增加禁忌長度.通過這種動態(tài)選取的方法大大提高了算法的收斂速度.

2 動態(tài)調(diào)度系統(tǒng)設(shè)計

2.1 系統(tǒng)支撐技術(shù)

一個高效的動態(tài)車輛調(diào)度系統(tǒng)中，必須有一定的關(guān)鍵技術(shù)作支撐，本系統(tǒng)中引入GPS、GIS和GPRS技術(shù)，通過這些技術(shù)得到實時的調(diào)度數(shù)據(jù)，并在調(diào)度中心和移動車輛等目標間進行數(shù)據(jù)傳輸，提高系統(tǒng)的動態(tài)優(yōu)化效率.

(1)通過GPS/GIS技術(shù)［8］對運輸車輛進行實時跟蹤調(diào)度，返回車輛的運行位置和方向.

(2)GIS技術(shù)是計算配送中心和各戶點間距離的基礎(chǔ)，為車輛路徑優(yōu)化提供很好的條件.

(3)通過GPRS技術(shù)將車輛的調(diào)度指令和行駛路線等動態(tài)調(diào)度結(jié)果實時、準確地發(fā)送實施車輛，以保證調(diào)度計劃的高效執(zhí)行.

2.2 系統(tǒng)結(jié)構(gòu)

系統(tǒng)結(jié)構(gòu)如圖2所示.

該系統(tǒng)結(jié)構(gòu)能夠?qū)崟r監(jiān)測客戶需求，實時跟蹤車輛位置，并根據(jù)此信息進行動態(tài)的車輛路徑規(guī)劃，實現(xiàn)動態(tài)調(diào)度，并將動態(tài)調(diào)度結(jié)果發(fā)送給車輛.主要包括客戶、車輛和系統(tǒng)調(diào)度核心模塊三個部分.

(1)客戶向調(diào)度系統(tǒng)提出服務(wù)請求.

(2)調(diào)度中心按照客戶提供的資料和要求的緊急度，根據(jù)當前環(huán)境和系統(tǒng)狀態(tài)，決定是否接受該客戶的請求，當調(diào)度中心接受客戶請求后，將客戶信息加入數(shù)據(jù)模塊，進行動態(tài)調(diào)度，動態(tài)調(diào)度結(jié)果存入數(shù)據(jù)庫以供查詢，并在調(diào)度客戶端通過GIS顯示調(diào)度結(jié)果.

(3)動態(tài)調(diào)度結(jié)果通過通信服務(wù)器直接發(fā)送給車輛終端，保證車輛及時獲得調(diào)度結(jié)果.

圖2 動態(tài)調(diào)度系統(tǒng)結(jié)構(gòu)圖

2.3 系統(tǒng)功能模塊劃分

系統(tǒng)采用Client/Server結(jié)構(gòu).各系統(tǒng)功能及模塊劃分如圖3所示.

圖3 動態(tài)車輛調(diào)度系統(tǒng)功能劃分

動態(tài)車輛調(diào)度系統(tǒng)各層功能如下:

(1)顯示層:為調(diào)度系統(tǒng)提供交互界面，是整個調(diào)度系統(tǒng)的門戶，主要包括信息顯示，如客戶、車輛及其路徑等，車輛行駛跟蹤以及一些用戶參數(shù)設(shè)置等.

(2)邏輯層:為調(diào)度系統(tǒng)提供邏輯處理和優(yōu)化計算，是整個調(diào)度系統(tǒng)的核心，主要包括客戶距離計算、調(diào)度路徑規(guī)劃計算與優(yōu)化等.

(3)數(shù)據(jù)層:為調(diào)度系統(tǒng)提供數(shù)據(jù)支持，是整個調(diào)度系統(tǒng)的基礎(chǔ)，主要包括數(shù)據(jù)的組織管理、數(shù)據(jù)的通信與傳輸?shù)?

3 應(yīng)用實例

將該動態(tài)車輛調(diào)度系統(tǒng)應(yīng)用于遍布東北三省12個主要城市的市內(nèi)集貨或配送業(yè)務(wù)，系統(tǒng)在某個調(diào)度周期內(nèi)的運行結(jié)果如圖4所示.圖中紅色點為新的客戶需求，黃色線為系統(tǒng)運行后的最佳動態(tài)車輛調(diào)度路線.

圖4 動態(tài)車輛調(diào)度系統(tǒng)運行結(jié)果

系統(tǒng)反復(fù)運行5次，調(diào)度結(jié)果均在5 s內(nèi)完成，且系統(tǒng)穩(wěn)定性較好.說明系統(tǒng)的應(yīng)用能夠?qū)蛻舻膭討B(tài)需求做出快速的反映，系統(tǒng)的實時性、穩(wěn)定性等方面都符合設(shè)計要求.

4 結(jié)束語

提出了一種基于并行節(jié)約法和禁忌搜索的混合算法，能對帶時間窗的、單車場多車型的VRPB進行有效求解.該系統(tǒng)設(shè)計與開發(fā)方法的主要改進有以下兩點:

(1)處理策略:通過引入虛擬任務(wù)點將帶時間窗的動態(tài)車輛調(diào)度問題轉(zhuǎn)化為靜態(tài)問題處理，并采用局部調(diào)整的優(yōu)化策略，實現(xiàn)車輛實時調(diào)度.

(2)求解算法:用一種基于并行節(jié)約法和禁忌搜索的混合算法，并且在算法中提出采用動態(tài)構(gòu)造鄰域解的方法和動態(tài)禁忌長度的選取策略，大大提高了解的全局更優(yōu)性和算法的收斂速度，在保證解全局性的前提下使得系統(tǒng)運行耗時較少.

基于GPS/GIS/GPRS技術(shù)的動態(tài)車輛調(diào)度系統(tǒng)設(shè)計開發(fā)，滿足調(diào)度人員實時準確的調(diào)度需求，對降低配送和集貨成本具有重要意義.

［1］肖增敏，李軍.動態(tài)網(wǎng)絡(luò)車輛路徑問題:研究現(xiàn)狀及展望.系統(tǒng)工程，2004，22(7):68-71.

［2］Devlin G J，McDonnell K，Ward S.Timber haulage routing in Ireland:An analysis using GIS and GPS.Journal of Transport Geography，2008，16(1):63-72.

［3］曹劍東，鄭四發(fā)，李兵，等.動態(tài)車輛調(diào)度系統(tǒng)設(shè)計與開發(fā).計算機工程，2008，7(34):180-182.

［4］Osman I H，Wassan N A.A Reactive Tabu Search Meta Heuristic for the Vehicle Routing Problem with Backhauls.Journal of Scheduling，2002，5(4):263-285.

［5］王訓(xùn)斌，陸慧娟，張火明.物流動態(tài)車輛調(diào)度問題的混合禁忌搜索算法.計算機工程與應(yīng)用，2010，46(8):228-231.

［6］Clarke G，Wright J W.Scheduling of Vehicles from a Central Depot to a Number of Delivery Points.Operations Research，1964，12(4):568-581.

［7］劉霞，齊歡.基于禁忌搜索的動態(tài)車輛路徑問題.武漢理工大學(xué)學(xué)報(交通科學(xué)與工程版)，2010，34(2):293-296.

［8］G.Loganathan.GPS and GIS Technology Trends.IEEE，2002:292-294.

Design and Implementation of Dynamic Vehicle Scheduling System Based on GPS/GIS/GPRS

Yuan Jianqing1，Xiu Jianxin1，Wang Zebin2
(1.Heilongjiang East Academy;2.Harbin Institute of Technology)

In order to solve vehicle distribution and scheduling solution，a mixture algorithm based on a paralleleconomical method and tabu search algorithms is designed and introduced to solve static vehicle scheduling solution.Dynamic vehicle scheduling of the typical VRPB problems is worked out through setting a new customers needs as a virtual site and through local adjusting Strategy.Dynamic vehicle scheduling system based on GPS/GIS/GPRS technology is developed afterwards.The system follows up the vehicle location real-time;and inspects the consignment requirements of new customer，which is used as input to optimize the vehicle routing dynamic.The routing result is as well quickly transmitted to the vehicle by GPRS.

Dynamic vehicle scheduling;GPS/GIS/GPRS;Tabu search algorithm;Parallel-economical method

2010-09-12

*黑龍江省教育廳科學(xué)技術(shù)研究(指導(dǎo))項目(11544037)

(責任編輯:李佳云)