馮鵬程 高社生 王 東

(西北工業(yè)大學(xué)自動(dòng)化學(xué)院1) 西安 710072) (武警后勤學(xué)院軍交運(yùn)輸系2) 天津 300309)

基于區(qū)域分層的車輛隊(duì)列行駛路徑優(yōu)化算法*

馮鵬程1,2)高社生1)王 東2)

(西北工業(yè)大學(xué)自動(dòng)化學(xué)院1)西安 710072) (武警后勤學(xué)院軍交運(yùn)輸系2)天津 300309)

為了滿足部隊(duì)摩托化機(jī)動(dòng)時(shí)車輛編組行駛組織指揮的需求，提出了車輛隊(duì)列行駛時(shí)的編組類型、行駛速度、隊(duì)列長(zhǎng)徑的具體概念.結(jié)合車輛隊(duì)列行駛對(duì)道路等級(jí)和行車速度的影響，建立了區(qū)域交通網(wǎng)絡(luò)路徑?jīng)Q策模型；基于單車區(qū)域橢圓、矩形區(qū)域選擇的算法不足，設(shè)計(jì)了基于車輛隊(duì)列長(zhǎng)徑參數(shù)、方圓結(jié)合的區(qū)域劃分方法和分層路徑優(yōu)化Dijkstra算法；并通過(guò)具體的道路交通網(wǎng)絡(luò)，進(jìn)行了仿真計(jì)算.結(jié)果表明，設(shè)計(jì)的算法穩(wěn)定、可行，能夠滿足部隊(duì)摩托化機(jī)動(dòng)時(shí)快速?zèng)Q策、快速到位的需求實(shí)際.

路徑優(yōu)化； 隊(duì)列行駛； 軍事物流；公路運(yùn)輸

0 引 言

車輛行駛路徑優(yōu)化算法，對(duì)研究信息化條件下的公路運(yùn)輸網(wǎng)絡(luò)路徑優(yōu)化問(wèn)題的求解有重要意義.對(duì)于這類問(wèn)題，目前的研究主要集中在單車[1]或多車配送問(wèn)題[2]，用于解決現(xiàn)代物流運(yùn)輸車輛調(diào)度問(wèn)題，沒(méi)有考慮車輛隊(duì)列行駛時(shí)對(duì)于道路的特殊需求.對(duì)于確定環(huán)境下有約束最短路徑問(wèn)題的研究，國(guó)內(nèi)外的研究大致可以歸納為有時(shí)間約束的最短路徑問(wèn)題[3]、點(diǎn)邊數(shù)有約束的最短路徑問(wèn)題[4]、多權(quán)最短路徑問(wèn)題[5]、邊權(quán)有時(shí)間依賴性[6]的最短路徑問(wèn)題和網(wǎng)絡(luò)中最關(guān)鍵點(diǎn)及最關(guān)鍵邊問(wèn)題[7].Dijkstra提出的網(wǎng)絡(luò)最短算法，被認(rèn)為是求解不含負(fù)邊長(zhǎng)一般網(wǎng)絡(luò)的最有效算法之一[8].確定環(huán)境下無(wú)約束單權(quán)網(wǎng)絡(luò)最短路徑算法的各種改進(jìn)算法，都是基于標(biāo)號(hào)算法基礎(chǔ)上的，所不同的在于數(shù)據(jù)結(jié)構(gòu)的定義[9].由于Dijkstra是一種遍歷NP-hard算法，當(dāng)節(jié)點(diǎn)規(guī)模較大時(shí)，很難得到問(wèn)題的精確解，因此，在單車配送算法中，通常采用橢圓模型和矩形模型[10],這2種區(qū)域劃分算法雖然都能夠達(dá)到減少了最短路徑算法的搜索空間的目的，但沒(méi)有考慮車輛隊(duì)列行駛長(zhǎng)徑的特性.

部隊(duì)在進(jìn)行遂行多樣化任務(wù)公路運(yùn)輸保障時(shí)，通常采用車輛編組行進(jìn)，受到行軍縱隊(duì)長(zhǎng)徑、編組車輛性能和安全防衛(wèi)等因素的影響，對(duì)路徑的選擇有不同的要求.針對(duì)部隊(duì)車輛隊(duì)列行駛路徑?jīng)Q策的實(shí)際問(wèn)題，考慮車輛隊(duì)列長(zhǎng)徑、不同道路的運(yùn)行速度，劃分標(biāo)號(hào)的選擇方式和范圍，定義合適的數(shù)據(jù)結(jié)構(gòu)，減少計(jì)算工作量；并基于車輛隊(duì)列通過(guò)需求，設(shè)計(jì)高等級(jí)道路優(yōu)先選擇算法，以期實(shí)現(xiàn)車輛隊(duì)列快速、安全到位的目的.

1 車輛隊(duì)列行駛定義

美國(guó)聯(lián)邦公路局智能車輛高速公路系統(tǒng)項(xiàng)目中，將車輛隊(duì)列行駛定義為多輛車排成一列，以一定的速度等速行駛，而且車輛之間保持較小的縱向間距[11].這是一個(gè)定性的定義，難以進(jìn)行定量分析.因此，本文在分析近年來(lái)部隊(duì)車輛隊(duì)列行駛案例的基礎(chǔ)上，給出車輛隊(duì)列行駛定義如下.

定義1 小編組行車

在行駛中，車輛按照小編組、大間距的原則編組行進(jìn)；是一種小規(guī)模車輛隊(duì)列行駛方法，適用于執(zhí)行倒短、接力運(yùn)輸任務(wù)；特點(diǎn)是靈活機(jī)動(dòng)，工作時(shí)效性好，有利于提高行車速度.

定義2 大編組行車

在行駛中，車輛按照建制大編組、多梯次的原則編組行進(jìn)；是一種大規(guī)模車輛隊(duì)列行駛方法，適用于執(zhí)行運(yùn)量集中、運(yùn)距較長(zhǎng)的運(yùn)輸任務(wù)；特點(diǎn)是運(yùn)量大，保持部隊(duì)建制完整.

定義3 車輛隊(duì)列長(zhǎng)徑

車輛隊(duì)列長(zhǎng)徑是指隊(duì)列頭車至尾車的長(zhǎng)度.

小編組行車隊(duì)列長(zhǎng)徑=[車長(zhǎng)(m)×車數(shù)+車輛間隔(m)×(車數(shù)-1)] ×1/1 000

大編組行車隊(duì)列長(zhǎng)徑=[車長(zhǎng)(m)×車數(shù)+車輛間隔(m)×(車數(shù)-1)+單位間隔(m)×(單位數(shù)-1)] ×1/1 000

其中，車長(zhǎng)取值為實(shí)際車身長(zhǎng)度的近似值；車輛間隔按照道路通行條件和行車速度有所不同，見(jiàn)表1；單位間隔是指為了保持單位建制和便于管理，大編組內(nèi)各單位之間所保持的較大間隔，取1 000 m.

表1 車輛隊(duì)列行駛速度和間隔距離

定義4 車輛隊(duì)列行駛時(shí)間

車輛隊(duì)列行駛時(shí)間的計(jì)算是確定車輛隊(duì)列到達(dá)或者通過(guò)時(shí)間，保證按時(shí)限完成行進(jìn)任務(wù)的重要參數(shù).車輛隊(duì)列行駛時(shí)間可分為總持續(xù)時(shí)間和通過(guò)節(jié)點(diǎn)時(shí)的時(shí)間.

車輛隊(duì)列行駛總持續(xù)時(shí)間(h)=[總行程(km)+車輛隊(duì)列長(zhǎng)徑(km)]/隊(duì)列行駛速度(km/h)+休息時(shí)間(h)

休息時(shí)間可區(qū)分為小休息和大休息.小休息，通常是指每?jī)尚r(shí)組織一次，時(shí)間為0.5 h；大休息，是在日行程過(guò)半時(shí)，間隔4 h，時(shí)間為小1.5 h，通常含一次進(jìn)餐時(shí)間；如果總持續(xù)時(shí)間超過(guò)1 d，則還要另行計(jì)算宿營(yíng)時(shí)間.

車輛隊(duì)列行駛通過(guò)節(jié)點(diǎn)時(shí)間(h，min)=隊(duì)列頭車到達(dá)出發(fā)點(diǎn)時(shí)間(h，min)+出發(fā)點(diǎn)至節(jié)點(diǎn)距離(km)/隊(duì)列行駛速度(km/h)+休息時(shí)間(min)

定義5：隊(duì)列行駛速度

車輛間隔按照道路通行條件有所不同，預(yù)設(shè)情況見(jiàn)表1[12].

2 區(qū)域交通網(wǎng)絡(luò)路徑模型建立

將有限區(qū)域內(nèi)，含有n個(gè)節(jié)點(diǎn)，m條有向邊的路網(wǎng)系統(tǒng)抽象成一個(gè)模型交通網(wǎng)絡(luò)[13]，即G={V,E,C,L}.

式中：V為有限節(jié)點(diǎn)集合，V={v1,v2,…,vn}；E為有限弧集，E={e1,e2,…,em}；C為公路等級(jí)，C={c1,c2,…,cm}，ci為對(duì)每個(gè)弧(vi,vj)∈E對(duì)應(yīng)的公路等級(jí),ci=0,1,2,3，分別為高速、一、二、三級(jí)公路；L為對(duì)每個(gè)弧(vi,vj)∈E，對(duì)應(yīng)的距離，km，L={l1,l2,…,lm}.

設(shè)P={xij|(vi,vj)∈E}表示從起點(diǎn)v1到終點(diǎn)vn的一條路徑.

(1)

起點(diǎn)v1到終點(diǎn)vn的模型可以描述為

(2)

(3)

式中:T為優(yōu)化目標(biāo);Tij為網(wǎng)絡(luò)中從vi到vj的車輛隊(duì)列通行時(shí)間，計(jì)算方法按照定義4進(jìn)行.如果弧(vi,vj)?E，則時(shí)間為+.

3 車輛隊(duì)列行駛區(qū)域分層路徑優(yōu)化算法設(shè)計(jì)

3.1 節(jié)點(diǎn)區(qū)域劃分

區(qū)域劃分是針對(duì)道路網(wǎng)絡(luò)的空間分布特征提出的，其目的是合理選擇道路網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)目，提高算法效率.本文針對(duì)橢圓算法相對(duì)復(fù)雜、矩形算法精度較低的不足，本文提出利用車輛隊(duì)列行駛在不同道路環(huán)境下速度不同的特點(diǎn)來(lái)構(gòu)建方圓結(jié)合區(qū)域的方法，使得迂回距離的大小和因道路環(huán)境不同而能節(jié)省的時(shí)間相一致，并便于區(qū)域動(dòng)態(tài)擴(kuò)展.

步驟2 按照車輛隊(duì)列編組類型，結(jié)合表1，分別計(jì)算在這一空間距離下，兩種極限道路條件下(高速公路與三級(jí)公路)的車輛隊(duì)列行駛的時(shí)間差Δtmax.

步驟3 用這一時(shí)間差乘以車輛隊(duì)列行駛的最大速度，得到一個(gè)可迂回的距離ΔLmax.

步驟4 分別以S和E為圓心，以ΔLmax/2為半徑做圓.

步驟5 做平行于SE的2個(gè)頂點(diǎn)圓的切線形成圖1所示區(qū)域，選擇這一區(qū)域中的道路網(wǎng)絡(luò)節(jié)點(diǎn)，作為優(yōu)化搜索區(qū)域.

步驟6 如果道路等級(jí)達(dá)不到預(yù)設(shè)條件，按比例增加劃分區(qū)域圓的半徑.

道路網(wǎng)絡(luò)區(qū)域的劃分見(jiàn)圖1.

圖1 車輛隊(duì)列行駛道路網(wǎng)絡(luò)區(qū)域的劃分

3.2 道路分層算法設(shè)計(jì)

由于在區(qū)域劃分時(shí)，考慮了最大迂回道路的時(shí)間延誤問(wèn)題，因此，在區(qū)域內(nèi)的點(diǎn)，高等級(jí)道路優(yōu)先的原則，等同于時(shí)間最短原則.為了盡可能選擇高等級(jí)的路徑，減少算法節(jié)點(diǎn)，提高運(yùn)輸效率，同時(shí)減少計(jì)算時(shí)間，本文提出了道路分層優(yōu)化算法，算法流程見(jiàn)圖2.

圖2 分層路徑優(yōu)化算法流程

4 算 例

4.1 道路模型及節(jié)點(diǎn)區(qū)域劃分

某部隊(duì)執(zhí)行應(yīng)急運(yùn)輸保障任務(wù)，采用大編組隊(duì)列行車，車輛隊(duì)列長(zhǎng)徑約為5 km，所在地域的有向交通網(wǎng)絡(luò)見(jiàn)圖3，出發(fā)點(diǎn)為節(jié)點(diǎn)v1，目的地為節(jié)點(diǎn)v12.

按照區(qū)域劃分算法，在此區(qū)域內(nèi)，有效的交通網(wǎng)絡(luò)模型可表示為

C={2,3,3,2,1,2,0,2,2,1,0,3,0,2,2,2,2,2,3,2,2,0}

L={50,80,40,40,60,70,50,80,40,125,110,100,70,70,40,50,60,80,60,50,120,120}

km.

節(jié)點(diǎn)v16，v17，v18，v19，v20及其他未標(biāo)明節(jié)點(diǎn)在區(qū)域范圍之外，不予考慮.

圖3 道路交通網(wǎng)絡(luò)模型及區(qū)域劃分

4.2 路徑分層選擇優(yōu)化計(jì)算

按照公路等級(jí)矩陣C分層，可以得到：E0={e7,e11,e14,e23}，為高速公路.

E1={e5,e10,e13}，為一級(jí)公路.

E2={e1,e4,e6,e8,e9,e15,e16,e17,e18,e19,e21,e22}，為二級(jí)公路.

E3={e2,e3,e12,e20}為三級(jí)公路.

按照定義4和定義5計(jì)算車輛隊(duì)列通過(guò)各有向邊的時(shí)間得到時(shí)間矩陣T，這里采用大編組白天行車參數(shù).

T={1.43,2.67,1.33,1.14,1,2,0.83,2.29,1.14,2.78,1.83,3.33,1.17,2,1.14,1.43,1.71,2.29,2,1.67,3.43,2}h.

由分層算法得到新起點(diǎn)S0與新終點(diǎn)E0，對(duì)應(yīng)路徑e11，通過(guò)時(shí)間為1.83h，連通后進(jìn)入第三層得到S至S0的最小通過(guò)時(shí)間路徑e1，通過(guò)時(shí)間為1.43h，E0至E的最小通過(guò)時(shí)間路徑e17，通過(guò)時(shí)間是1.71 h.

已知車輛隊(duì)列長(zhǎng)徑為5km，e1為二級(jí)公路，依據(jù)表1，白天大編組行車速度為35km/h，則車輛隊(duì)列通過(guò)時(shí)間為0.14h；按節(jié)點(diǎn)和目標(biāo)函數(shù)分析，應(yīng)安排1次小休息，1次大休息，共計(jì)2h；則車輛隊(duì)列行駛總持續(xù)時(shí)間為7.11h，也就是7h7min.

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

車輛隊(duì)列行駛路徑優(yōu)化方法是信息化條件下部隊(duì)機(jī)動(dòng)決策的重要依據(jù), 限制搜索區(qū)域算法，是提高最短路徑搜索效率的一種常用的有損算法.本文給出了車輛隊(duì)列行駛的基本定義，提出了一種區(qū)域分層優(yōu)化的算法，并通過(guò)算例進(jìn)行驗(yàn)證，結(jié)果表明算法可靠、高效，符合部隊(duì)摩托化機(jī)動(dòng)編組行車的路徑優(yōu)化決策需求.值得說(shuō)明的是，本文在層次算法中套用的確定環(huán)境下的Dijkstra路徑選擇算法，適用于區(qū)域較小，節(jié)點(diǎn)較少的情況；如果區(qū)域過(guò)大，節(jié)點(diǎn)過(guò)多時(shí)應(yīng)采用啟發(fā)式算法，以提高計(jì)算效率；如果路網(wǎng)密度過(guò)小，區(qū)域內(nèi)線路不足，則應(yīng)擴(kuò)大區(qū)域劃分半徑.

[1]CHERKASSKYBV,GOLDBE-RGAV,RADZIKT.Shortestpath′salgorithms:theoryandexperimentalevaluation[J].MathematicalProgramming,1996,73:129-174.

[2]LIWenquan,WANGWei.Capacityofmultivehicletypesmixedtrafficflow[J].JournalofSystemsScienceandSystemsEngineering,2001(1):122.

[3]丁秋雷,胡祥培,李永先.求解有時(shí)間窗的車輛路徑問(wèn)題的混合蟻群算法[J].系統(tǒng)工程理論與實(shí)踐, 2007(10):98-104.

[4]何方國(guó),齊 歡,范 瓊.有約束的隨機(jī)最短路問(wèn)題模型及算法[J].武漢理工大學(xué)學(xué)報(bào),2008,32(6):1125-1128.

[5]肖曉偉,肖 迪,林錦國(guó),等.多目標(biāo)優(yōu)化問(wèn)題的研究概述[J].計(jì)算機(jī)應(yīng)用研究,2011,28(3):805-808.

[6]王江晴,康 立.動(dòng)態(tài)車輛路徑問(wèn)題仿真器的設(shè)計(jì)與實(shí)現(xiàn)[J].核電子學(xué)與探測(cè)技術(shù),2007,27(5):991-994.

[7]夏 珩,鄭四發(fā),李 兵,等.干線運(yùn)輸優(yōu)化的兩階段局部搜索啟發(fā)式算法[J].系統(tǒng)仿真學(xué)報(bào),2008,20(15):4141-4145.

[8]PAOLOT,DANIELEV.Thevehicleroutingproblem[M].北京：清華大學(xué)出版社,2011.

[9]YANGH，BELLMGH.Modelsandalgorithmsforroadnetworkdesign:areviewandsomenewdevelopments[J].TransportReview, 1998,18:257-278.

[10]王海梅,周獻(xiàn)中.一種限制搜索區(qū)域的最短路徑改進(jìn)算法[J].南京理工大學(xué)學(xué)報(bào)：自然科學(xué)版,2009,33(5):638-642.

[11]MICHAEL Z,STEFANO F,BROWAND F K.Drag measurements on 2,3 and 4 car platoons[C].SAE Paper, 940421.

[12]FENG Pengcheng,GAO Shesheng，SONG Feibiao.Area-layered paths optimizing algorithms of platoon vehicle[C]∥International Conference on Industrial Control & Electronics Engineering,2011:2780-2788.

[13]STIG N,BENGT R.Computer cartography shortest route program[M].Sweden:The Royal University of Lund,1969.

Paths Optimizing Algorithms for Platoon Vehicle Based on Area-layered

FENG Pengcheng1,2)GAO Shesheng1)WANG Dong2)

(CollegeofAutomation,NorthwesternPolytechnicalUniversity,Xi’an710072，China)1)(MilitaryTransportationDepartment,CAPFLogisticsUniversity,Tianjin300309，China)2)

According to the organizing and command demand for the vehicle platoon in military transportation, the attribute of the vehicle platoon were defined firstly,including type, speed and length. Secondly,combined with the influence of road grad and vehicle platoon speed, the model of paths optimizing area traffic net was built.Finally,based on the deficiency of the single vehicle ellipse and rectangle area partition,an area-layered paths optimizing algorithms for platoon vehicle was designed in consideration of the vehicle platoon length.The testing results showed that the algorithm described herein was stable and feasible, and should be useful to military transportation based on the quick and safety demands.

path optimizing； platoon vehicle； military logistics； road conveyance

2015-02-08

*武警總部后勤部課題資助

U492.7

10.3963/j.issn.2095-3844.2015.03.007

馮鵬程(1974- )：男，博士生，副教授，主要研究領(lǐng)域?yàn)槲锪骷夹g(shù)與裝備