,,

(1.湖南師范大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院,長(zhǎng)沙 410081; 2.湖南警察學(xué)院 信息技術(shù)系,長(zhǎng)沙 410138)

0 概述

近年來(lái),研究者對(duì)智能交通系統(tǒng)(Intelligent Transportation Systems,ITS)的研究越來(lái)越多,而智能交通系統(tǒng)中的車輛路徑問(wèn)題(Vehicle Routing Problem,VRP)是目前電子商務(wù)物流配送決策中的熱點(diǎn)問(wèn)題[1],也是帶多個(gè)約束條件的NP-難問(wèn)題,如帶時(shí)間窗約束的車輛路徑問(wèn)題[2](Vehicle Routing Problem with Time Windows,VRPTW)難以用常規(guī)方法求解,因而人們多致力于啟發(fā)式算法的研究。車輛路徑問(wèn)題目前要處理來(lái)自多個(gè)數(shù)據(jù)源向其提供的數(shù)據(jù)收集服務(wù)[3],文獻(xiàn)[4]描述已經(jīng)改變了傳統(tǒng)智能交通系統(tǒng)(TTS)的數(shù)據(jù)驅(qū)動(dòng)。通過(guò)從各種來(lái)源收集大量的數(shù)據(jù)加工成有用的數(shù)據(jù)信息,數(shù)據(jù)驅(qū)動(dòng)可以為車輛路徑優(yōu)化提供新的服務(wù)[5],為動(dòng)態(tài)車輛路徑問(wèn)題提供新的依據(jù)。收集和組織來(lái)自多個(gè)實(shí)時(shí)不同來(lái)源數(shù)據(jù),為智能交通供應(yīng)鏈的決策提供依據(jù)是目前的主要挑戰(zhàn)[6],這主要是因?yàn)閿?shù)據(jù)庫(kù)的規(guī)模非常大,同時(shí)沒(méi)有可用的實(shí)時(shí)分析工具。

當(dāng)前智能交通系統(tǒng)路徑算法主要面臨的困難[7]有:從廣泛攜帶傳感器的車輛搜集所需位置數(shù)據(jù)集;收集從大量實(shí)時(shí)車輛數(shù)據(jù)提高及時(shí)警報(bào);大量數(shù)據(jù)需要組織和實(shí)時(shí)處理;用于數(shù)據(jù)收集系統(tǒng)結(jié)構(gòu)應(yīng)該較易部署、低成本,以確保廣泛使用。本文利用大數(shù)據(jù)平臺(tái)對(duì)多源大量數(shù)據(jù)計(jì)算的優(yōu)勢(shì),構(gòu)建動(dòng)態(tài)車輛路徑調(diào)度模塊的體系框架,同時(shí)提出基于大數(shù)據(jù)平臺(tái)的動(dòng)態(tài)車輛路徑調(diào)度算法(BDVRA)。該算法采用動(dòng)態(tài)時(shí)間序列構(gòu)建目標(biāo)函數(shù)模型[8],實(shí)時(shí)設(shè)置警報(bào)標(biāo)志動(dòng)態(tài)修改車輛路徑調(diào)度策略。

1 基本問(wèn)題模型

為說(shuō)明動(dòng)態(tài)車輛路徑問(wèn)題[9],通過(guò)實(shí)例來(lái)說(shuō)明實(shí)時(shí)更新路線的車輛路徑調(diào)度策略,如圖1所示。此問(wèn)題涉及到食品供應(yīng)鏈的供應(yīng)節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn),供應(yīng)節(jié)點(diǎn)可以是新鮮食品生產(chǎn)收集中心或暫時(shí)存儲(chǔ)食品倉(cāng)庫(kù)的任意分布點(diǎn),目的地可以是出售新鮮食品零售商店或被運(yùn)送到其他地點(diǎn)之前冷藏保存食品倉(cāng)庫(kù)的任意分布點(diǎn)。圖1中涉及到的所有車輛可以在任意位置開始或結(jié)束路線,路線的數(shù)量等于車輛的數(shù)量,即每輛車安排一條路線。每輛車在有限能力提供有限車載量的食品給目標(biāo)節(jié)點(diǎn),初始方案是每輛車在每個(gè)供應(yīng)節(jié)點(diǎn)僅訪問(wèn)一次。大數(shù)據(jù)分析計(jì)算平臺(tái)用于實(shí)時(shí)監(jiān)控從所有的車輛和車輛路線上獲取的數(shù)據(jù),如果在運(yùn)輸途中供應(yīng)食物的可能在某種條件導(dǎo)致變質(zhì),那么車輛路徑要實(shí)時(shí)更新變化。圖1顯示了從車輛實(shí)時(shí)數(shù)據(jù)分析后生成一個(gè)動(dòng)態(tài)調(diào)度的實(shí)例,如:車輛P1在路徑1-2上產(chǎn)生一個(gè)警報(bào)而延誤了目標(biāo)節(jié)點(diǎn)3的如期交貨時(shí)間,這個(gè)警報(bào)觸發(fā)了創(chuàng)建新路徑模塊,車輛1從節(jié)點(diǎn)2重新路由到目標(biāo)節(jié)點(diǎn)4,而車輛2重新路由到目標(biāo)節(jié)點(diǎn)3,車輛3重新路由到目標(biāo)節(jié)點(diǎn)6。

圖1 基于警報(bào)實(shí)時(shí)更新路線示意圖

定義1(VRPTW問(wèn)題) 設(shè)物流中心倉(cāng)庫(kù)有k輛車,N={s},s=1,2,…,k,其中k為待定車輛數(shù),每輛車載重能力為Ns=D;要為q個(gè)節(jié)點(diǎn)用戶供應(yīng),用戶節(jié)點(diǎn)集為U={m},m=0,1,…,q,當(dāng)m=0時(shí)為中心倉(cāng)庫(kù);用戶m的需求量為dm,因此d0=0;用戶m的時(shí)間窗口為[xm,ym];從用戶m到用戶n的路程為Umn,行駛時(shí)間為Tmn;設(shè)車輛s到達(dá)用戶m的時(shí)間為Wms,則Wms∈[xm,ym]。如何進(jìn)行車輛路徑調(diào)度,使調(diào)用的車輛數(shù)k最少,且總行車成本P最小。

根據(jù)VRPTW問(wèn)題定義,其數(shù)學(xué)模型可以概述為:如果車輛s訪問(wèn)客戶m后訪問(wèn)客戶n,則Ymns=1;否則Ymns=0,其目標(biāo)函數(shù)的一般形式[10]為:

(1)

n=1,2,…,k,s=1,2,…,q,n≠s

(2)

(3)

為了得出圖1中基于警報(bào)實(shí)時(shí)更新車輛路徑問(wèn)題的數(shù)學(xué)模型,用一個(gè)時(shí)間序列的路線圖來(lái)描述,如圖2所示。

圖2 車輛路線時(shí)序示意圖

在圖2中,N是目標(biāo)總數(shù),K是車輛數(shù),M是一輛車在一條路徑最大目標(biāo)數(shù),Di是從供應(yīng)節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)i所需時(shí)間,Tmk0是車輛k第m趟開始時(shí)間,Tmk1是車輛k第m趟到達(dá)目標(biāo)節(jié)點(diǎn)時(shí)間,Tmk2是車輛k第m趟到達(dá)目標(biāo)節(jié)點(diǎn)時(shí)間,Si是在目標(biāo)節(jié)點(diǎn)i的處理時(shí)間,Ri是車輛行駛到目標(biāo)節(jié)點(diǎn)i的時(shí)間窗口,Wj0是到達(dá)目標(biāo)節(jié)點(diǎn)j時(shí)間窗口的開始時(shí)間,Wj1是到達(dá)目標(biāo)節(jié)點(diǎn)j時(shí)間窗口的結(jié)束時(shí)間。Xikm∈{0,1}是決策變量,其中,i∈{1,2,…,N},k∈{1,2,…,K},m∈{1,2,…,M}。如果目標(biāo)節(jié)點(diǎn)i有車輛k的第m趟,則Xikm=1;否則Xikm=0。根據(jù)圖1的數(shù)學(xué)模型,可以得出圖2中食物供應(yīng)運(yùn)輸總成本的目標(biāo)函數(shù)F:

(4)

k=1,2,…,K,s=1,2,…,q,n≠s

(5)

(6)

其中,ai是與目標(biāo)節(jié)點(diǎn)i關(guān)聯(lián)的遲到罰款系數(shù),即目標(biāo)函數(shù)F的值由從供應(yīng)節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)運(yùn)輸成本和從供應(yīng)節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)延遲罰款組成。

2 大數(shù)據(jù)平臺(tái)動(dòng)態(tài)車輛路徑調(diào)度策略

基于大數(shù)據(jù)平臺(tái)動(dòng)態(tài)車輛路徑的體系框架如圖3所示。數(shù)據(jù)收集器從車輛主節(jié)點(diǎn)和傳感裝置收集動(dòng)態(tài)時(shí)序數(shù)據(jù),每個(gè)傳入的數(shù)據(jù)流映射到一個(gè)數(shù)據(jù)收集器節(jié)點(diǎn)。每個(gè)數(shù)據(jù)收集器節(jié)點(diǎn)有數(shù)據(jù)聚合器、數(shù)據(jù)過(guò)濾器和數(shù)據(jù)存儲(chǔ)服務(wù)器模塊。對(duì)大量原始位置和傳感器車輛數(shù)據(jù)流形式的原始數(shù)據(jù),使用大數(shù)據(jù)分析軟件Hadoop進(jìn)行預(yù)處理數(shù)據(jù)分析,Hadoop是一個(gè)能夠?qū)Υ罅繑?shù)據(jù)進(jìn)行分布式處理的軟件框架,對(duì)數(shù)據(jù)預(yù)處理更有效率[11]。另外,Hadoop實(shí)現(xiàn)了一個(gè)分布式文件系統(tǒng)(Hadoop Distributed File System,HDFS)。在分布式計(jì)算中,MapReduce框架負(fù)責(zé)處理了并行編程中分布式存儲(chǔ)、工作調(diào)度、負(fù)載均衡、容錯(cuò)均衡、容錯(cuò)處理以及網(wǎng)絡(luò)通信等復(fù)雜問(wèn)題,把處理過(guò)程高度抽象為2個(gè)函數(shù):map和reduce,map負(fù)責(zé)把任務(wù)分解成多個(gè)任務(wù),reduce負(fù)責(zé)把分解后多任務(wù)處理的結(jié)果匯總起來(lái)。

圖3 大數(shù)據(jù)平臺(tái)動(dòng)態(tài)車輛路徑體系結(jié)構(gòu)

對(duì)收集到的數(shù)據(jù)進(jìn)行處理以生成警報(bào),在用戶指定的過(guò)濾器創(chuàng)建警報(bào)。警報(bào)創(chuàng)建模塊收集到一個(gè)警報(bào)位置(警報(bào)數(shù)據(jù)庫(kù)),被組織成一個(gè)HDFS可管理的數(shù)據(jù)結(jié)構(gòu)。通過(guò)較少時(shí)間窗口的實(shí)時(shí)車輛位置和傳感器收集到的數(shù)據(jù)創(chuàng)建實(shí)時(shí)警報(bào),也可以從過(guò)去的車輛位置和傳感器數(shù)據(jù)創(chuàng)建離線警報(bào)。因?yàn)槭笻DFS和MapReduce優(yōu)化處理大文件、數(shù)據(jù)轉(zhuǎn)到一個(gè)記錄結(jié)構(gòu)文件更有效,所以數(shù)據(jù)挖掘要將聚集本地磁盤的車輛位置和傳感器非結(jié)構(gòu)化流數(shù)據(jù)轉(zhuǎn)換為結(jié)構(gòu)化記錄文件,并通過(guò)在非結(jié)構(gòu)化序列文件中解析記錄和提取傳感器相關(guān)知識(shí),最后數(shù)據(jù)挖掘模塊將結(jié)構(gòu)化的記錄移動(dòng)到HDFS中?？刂破髂K通過(guò)動(dòng)態(tài)車輛路徑調(diào)度算法向所有車輛發(fā)送生成的新路徑線路,同時(shí)控制器能將當(dāng)前附近的車輛新路徑線路和附加信息增加到動(dòng)態(tài)車輛路徑數(shù)據(jù)中,用于實(shí)時(shí)更新路徑數(shù)據(jù)。

基于車輛實(shí)時(shí)數(shù)據(jù)的動(dòng)態(tài)車輛路徑模塊的目的是降低新鮮食品的變質(zhì)程度達(dá)到最小化。由于交通狀況變化,原來(lái)的路徑計(jì)劃進(jìn)度一般會(huì)發(fā)生偏差,此外環(huán)境的變化,如:溫度的增加會(huì)導(dǎo)致冷卻系統(tǒng)故障。大數(shù)據(jù)分析平臺(tái)可以對(duì)所有動(dòng)態(tài)車輛有一個(gè)全局視圖,在大數(shù)據(jù)計(jì)算平臺(tái)上動(dòng)態(tài)車輛路徑模塊能為發(fā)生警報(bào)的車輛及時(shí)創(chuàng)建新線路。例如,一輛汽車在預(yù)定時(shí)間內(nèi)不能達(dá)到預(yù)定目的地,可以在一個(gè)的食物變質(zhì)有限時(shí)間窗口開始前,重新選擇到一個(gè)最接近目標(biāo)的線路。應(yīng)用大數(shù)據(jù)平臺(tái),動(dòng)態(tài)車輛路徑模塊了解車輛的狀態(tài)變量(如卡車容量、位置、速度、容器溫度等)對(duì)創(chuàng)建新線路很重要,這個(gè)新的路線能降低運(yùn)輸車輛產(chǎn)生成本和食品變質(zhì)率。目前常見(jiàn)的研究主要是利用車輛靜態(tài)的時(shí)間窗口優(yōu)化車輛路徑減低運(yùn)輸成本,本文利用大數(shù)據(jù)分析計(jì)算平臺(tái)支持多種車輛動(dòng)態(tài)路徑算法的優(yōu)勢(shì),提出了一種新的動(dòng)態(tài)車輛路徑算法。

基于大數(shù)據(jù)計(jì)算平臺(tái)動(dòng)態(tài)車輛路徑調(diào)度算法,依托大數(shù)據(jù)計(jì)算平臺(tái)對(duì)數(shù)據(jù)處理的效率,如果某輛車在當(dāng)前路徑有一個(gè)警報(bào)發(fā)生時(shí),算法將基于當(dāng)前位置和現(xiàn)有車載能力為車輛生成一個(gè)新的順序路徑表。如果找到一個(gè)可行的解決方案,新的順序路徑表通過(guò)車輛由控制器模塊發(fā)送到當(dāng)前所有連接平臺(tái)的在線車輛。如果沒(méi)有找到可行解,當(dāng)前車輛獲得本地生成的警報(bào)進(jìn)行修復(fù)車輛路徑,例如:當(dāng)前某車輛可以路由到最近的交貨地點(diǎn),轉(zhuǎn)向原來(lái)沒(méi)有計(jì)劃的車輛路徑。本文算法應(yīng)用大數(shù)據(jù)計(jì)算平臺(tái)為工具,采用目標(biāo)函數(shù)及約束條件實(shí)現(xiàn)車輛運(yùn)輸總成本最小化的優(yōu)化解。

算法基于大數(shù)據(jù)計(jì)算平臺(tái)動(dòng)態(tài)車輛路徑算法

輸入設(shè)車輛集K={1,2,…,k},目標(biāo)節(jié)點(diǎn)集N={0,1,…,n},N=0時(shí)為中心倉(cāng)庫(kù)

輸出每輛車的最優(yōu)路徑及路徑序列S={s1,s2,…,sk}

步驟1從大數(shù)據(jù)計(jì)算平臺(tái)獲取處理車輛路徑數(shù)據(jù)集;

步驟2初始化,從源端N0開始,初始化一個(gè)空路由表S,并置N=0;

步驟3如果所有目標(biāo)節(jié)點(diǎn)N都被路由,則轉(zhuǎn)步驟5;

步驟4否則,計(jì)算其他沒(méi)有被路由目標(biāo)點(diǎn)的成本函數(shù)F;

步驟4.1如果有目標(biāo)節(jié)點(diǎn)發(fā)生警報(bào),則獲得當(dāng)前的位置和未路由的其他目標(biāo)節(jié)點(diǎn)Ni;

步驟4.2目標(biāo)節(jié)點(diǎn)Ni作為一個(gè)新的輸入,N=N+1;

步驟4.3找到了可行解,發(fā)送新的解給所有的車輛Ki;

步驟4.4否則,在當(dāng)前位置標(biāo)記警報(bào),獲得局部解并為車輛提高警惕,轉(zhuǎn)步驟3;

步驟5整理調(diào)度序列S={s1,s2,…,sk},并輸出,結(jié)束。

3 實(shí)驗(yàn)分析

為了驗(yàn)證基于大數(shù)據(jù)計(jì)算平臺(tái)動(dòng)態(tài)車輛路徑算法的正確性和效率,采用Sioux Fall網(wǎng)絡(luò)[12]進(jìn)行數(shù)值模擬,網(wǎng)絡(luò)中包括24個(gè)節(jié)點(diǎn)和76條路段,節(jié)點(diǎn)之間的線路雙向運(yùn)行的時(shí)間做了簡(jiǎn)單修正,數(shù)值模擬的網(wǎng)絡(luò)如圖4所示。

圖4 Sioux Fall網(wǎng)絡(luò)

初始路線通過(guò)數(shù)據(jù)收集器從車輛主節(jié)點(diǎn)和傳感裝置收集動(dòng)態(tài)時(shí)序數(shù)據(jù)得到,使用大數(shù)據(jù)分析軟件Hadoop進(jìn)行預(yù)處理數(shù)據(jù)分析,MapReduce框架負(fù)責(zé)處理并行編程中分布式存儲(chǔ)、工作調(diào)度、負(fù)載均衡、容錯(cuò)均衡、容錯(cuò)處理以及網(wǎng)絡(luò)通信等復(fù)雜問(wèn)題。本文求解BDVRA問(wèn)題得到的初始路線如表1所示。

表1 初始線路

在模擬過(guò)程中,分別采用4條初始線路對(duì)本文算法以及傳統(tǒng)推動(dòng)插入啟發(fā)式(Push-forward Insertion Heuristic,PFIH)算法[13]和基于禁忌(Tabu)搜索車輛路徑算法[14]進(jìn)行數(shù)值模擬實(shí)驗(yàn)。從表2可以看出,采用本文算法獲取的線路優(yōu)化結(jié)果明顯優(yōu)于傳統(tǒng)算法,表明本文算法是有效的;采用本文算法獲取的最優(yōu)解,明顯優(yōu)于PFIH和Tabu搜索算法,具體的結(jié)果如表2所示。

表2 3種算法優(yōu)化結(jié)果比較

將模擬數(shù)值增加,進(jìn)一步測(cè)試本文算法的時(shí)間性能,分別用10/4、50/10、100/20、500/50、1 000/100(分別表示路徑節(jié)點(diǎn)數(shù)/車輛數(shù))數(shù)值對(duì)3種算法進(jìn)行測(cè)試。本文為了評(píng)估大數(shù)據(jù)計(jì)算平臺(tái)框架處理的性能,進(jìn)行了上述不同數(shù)量的車輛,同時(shí)使用Amazon Elastic Compute Cloud(EC2)基礎(chǔ)設(shè)施[15]進(jìn)行實(shí)驗(yàn)。圖5和圖6顯示了本文BDVRA算法與傳統(tǒng)基于推動(dòng)插入啟發(fā)式(PFIH)算法和基于禁忌(Tabu)搜索車輛路徑算法在時(shí)間性能上進(jìn)行比較。

圖5 3種算法運(yùn)行的時(shí)間性能比較

圖6 3種算法目標(biāo)函數(shù)F值比較

可以看出,隨著數(shù)據(jù)量增加時(shí)3種算法的運(yùn)行時(shí)間和目標(biāo)函數(shù)F值都隨之上升。但數(shù)據(jù)量在500/50時(shí),PFIH和禁忌(Tabu)搜索算法明顯急劇上升,BDVRA由于利用大數(shù)據(jù)計(jì)算平臺(tái)對(duì)初始數(shù)據(jù)處理,在時(shí)間性能上有明顯優(yōu)勢(shì),如圖5所示。在整個(gè)車輛運(yùn)輸總成本上,由于利用標(biāo)記警報(bào)動(dòng)態(tài)修改路徑算法,目標(biāo)函數(shù)F的值也比其他2種算法優(yōu)越,如圖6所示。

4 結(jié)束語(yǔ)

車輛路徑最優(yōu)調(diào)度問(wèn)題是一種組合優(yōu)化問(wèn)題,如果節(jié)點(diǎn)數(shù)量較多、車輛狀態(tài)無(wú)掌控、實(shí)時(shí)環(huán)境變化等,則無(wú)法獲取準(zhǔn)確的最優(yōu)解。為對(duì)車輛的運(yùn)行路線進(jìn)行合理的規(guī)劃,確保車輛總成本最小化,本文提出基于大數(shù)據(jù)計(jì)算模型的車輛路徑調(diào)度算法。該算法首先應(yīng)用大數(shù)據(jù)計(jì)算平臺(tái)對(duì)數(shù)據(jù)進(jìn)行收集、存儲(chǔ)、處理和分析計(jì)算,然后利用平臺(tái)MapReduce實(shí)現(xiàn)以幾秒鐘的時(shí)間上限創(chuàng)建實(shí)時(shí)警報(bào)并修改車輛路徑。該算法提高了數(shù)據(jù)分析處理速度,對(duì)推動(dòng)啟發(fā)式搜索PFIH和禁忌(Tabu)搜索算法進(jìn)行了優(yōu)化,增強(qiáng)了算法實(shí)時(shí)動(dòng)態(tài)處理能力,提高了算法尋優(yōu)性能。下一步繼續(xù)將本文BDVRA算法應(yīng)用到多個(gè)目標(biāo)的動(dòng)態(tài)車輛路徑調(diào)度問(wèn)題中,求得多個(gè)解以有利于決策者做出正確的決策,為研究動(dòng)態(tài)車輛路徑調(diào)度問(wèn)題提供一種新的途徑與方法。

[1] 曹劍東,鄭四發(fā),李 兵,等.動(dòng)態(tài)車輛調(diào)度系統(tǒng)設(shè)計(jì)與開發(fā)[J].計(jì)算機(jī)工程,2008,34(7):280-282.

[2] 王 君,李 波,盧志剛.帶時(shí)間窗動(dòng)態(tài)車輛路徑問(wèn)題的優(yōu)化調(diào)度策略[J].計(jì)算機(jī)工程,2012,38(13):137-141.

[3] 李妍峰,高自友,李 軍.基于實(shí)時(shí)交通信息的城市動(dòng)態(tài)網(wǎng)絡(luò)車輛路徑優(yōu)化問(wèn)題[J].系統(tǒng)工程理論與實(shí)踐,2013,33(7):1813-1819.

[4] ZHANG J,WANG F,WANG K,et al.Data-driven Intelligent Transportation Systems:A Survey[J].IEEE Transactions on Intelligent Transportation Systems,2011,12(4):1624-1639.

[5] CLAES R,HOLVOET T,WEYNS D.A Decentralized Approach for Anticipatory Vehicle Routing Using Delegate Multi-agent Systems[J].IEEE Transactions on Intelligent Transportation Systems,2011,12(2):364-373.

[6] STEIL D A,PATE J R,KRAFT N A,et al.Patrol Routing Expression,Execution,Evaluation,and Engage-ment[J].IEEE Transactions on Intelligent Trans-portation Systems,2011,12(1):58-72.

[7] SCHMITT E,JULA H.Vehicle Route Guidance Systems:Classification and Comparison[C]//Proceedings of IEEE ITSC’06.Toronto,Canada:[s.n.],2006:242-247.

[6] PEARAFTIS H N.Dynamic;Vehicle Routing Problems[M].Berlin,Germany:Springer,1988.

[8] GHIANI G,GUERRIERO F,LAPORTE G,et al.Real-time Vehicle Routing:Solution Concepts,Algorithms and Parallel Computing Strategies[J].European Journal of Operational Research,2003,151(1):1-11.

[9] PILLAC V,GENDREAU M,GUERET C,et al.A Review of Dynamic Vehicle Routing Problems[J].European Journal of Operational Research,2013,225(1):1-11.

[10] POTVIN J Y,XU Y,BENYAHIA I.Vehicle Routing and Scheduling with Dynamic Travel Times[J].Com-puter & Operation Research,2006,33(4):1129-1137.

[11] TANIGUCHI E,SHIMAMOTO H.Intelligent Transportation System Based Dynamic Vehicle Routing and Scheduling with Variable Travel Times[J].Transportations Research Part C:Emerging Technologies,2004,12(3/4):235-250.

[12] LEBLANC L,MORLOK E K J,PIERSKALLA W P.An Efficient Approach to Solving the Road Network Equilibrium Traffic Assignment Problem[J].Trans-portations Research,1975,9(5):309-318.

[13] SOLOMON M M.Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints[J].Operations Research,1987,35(2):254-265.

[14] GLOVER F.Tabu Search Part I[J].ORSA Journal on Computing,1989,1(3):190-206.

[15] THANGIAH S R,OSMAN I H,VINAYAGAMOORTHY R.Algorithms for the Vehicle Routing Problems with Time Deadlines[J].American Journal of Mathematical and Management Sciences,1993,13(3/4):323-355.