畢業(yè)設(shè)計(jì)（論文）英文文獻(xiàn)英文文獻(xiàn)：最短路徑算法在空間移動(dòng)對(duì)象網(wǎng)絡(luò)數(shù)據(jù)庫(kù)中的應(yīng)用

Availableonlineat

ProgressinNaturalScience18(2008)893–899

/locate/pnsc

Ashortestpathalgorithmformovingobjectsinspatial

networkdatabases

c

XiaolanYina,b,*,ZhimingDing,JingLi

a

a

TechnologyCenterofSoftwareEngineering,InstituteofSoftware,ChineseAcademyofScience,P.O.Box8718,Beijing100080,China

b

GraduateUniversity,ChineseAcademyofSciences,Beijing100049,China

TechnologyCenterofBasicSoftware,InstituteofSoftware,ChineseAcademyofSciences,Beijing100080,China

c

Received7January2008;receivedinrevisedform11January2008;accepted14January2008

Abstract

OneofthemostimportantkindsofqueriesinSpatialNetworkDatabases(SNDB)tosupportlocation-basedservices(LBS)isthe

shortestpathquery.Givenanobjectinanetwork,e.g.alocationofacaronaroadnetwork,andasetofobjectsofinterests,e.g.hotels,

gasstation,andcar,theshortestpathqueryreturnstheshortestpathfromthequeryobjecttointerestedobjects.Thestudiesofshortest

pathqueryhavetwokindsofways,onlineprocessingandpreprocessing.Thestudiesofpreprocessingsupposethattheinterestobjects

arestatic.Thispaperproposesashortestpathalgorithmwithasetofindexstructurestosupportthesituationofmovingobjects.This

algorithmcantransformadynamicproblemtoastaticproblem.Inthispaperwefocusonroadnetworks.However,ouralgorithmsdo

notuseanydomainspeci?cinformation,andthereforecanbeappliedtoanynetwork.Thisalgorithm’scomplexityisO(klogi),and

2

2

traditionalDijkstra’scomplexityisO((i+k)).

2008NationalNaturalScienceFoundationofChinaandChineseAcademyofSciences.PublishedbyElsevierLimitedandSciencein

ChinaPress.Allrightsreserved.

Keywords:Movingobject;Spatialnetworkdatabases;Shortestpathindex;Shortestpath

1.Introduction

[14–17].Thebestboundinprecomputationappearsin

[18].In[19–21],thesecond-bestalgorithmontheshortest

pathisstudied.Previousworkonexactalgorithmswith

preprocessingincludesthoseusinggeometricinformation

[22,23],hierarchicaldecomposition[24–26],thenotionof

reach[27],andA*searchcombinedwithlandmarkdis-

tances[28,29].In[30],themethodistocomputethebest

pathinatimeintervalaccordingtotherealtime.This

methodcansolvethedynamicchangeofthenetwork

andthemovingobjects,butitneedstoomanyresources

ineachcomputation.Therefore,thecomputationtimeis

toolongwhenthenetworkscaleisbiggeranditcannot

providethereal-timeresult.InRef.[31],itisdiscussed

howtore-computethepathquicklyifthenetworkstruc-

tureischangedwhentheshortestpathiscomputed.

Inthispaper,wepresentthealgorithminthetranspor-

tationnetwork,butouralgorithmdoesnotuseanyinfor-

mationrelatedtothenetworkenvironment.Therefore,the

Withcontinualgrowingofwirelesscommunicationand

developingofpositioningtechnology,toanswerhighlye?-

cientqueriesofmanymovingobjectsandthequeriesbased

onlocation-basedservices(LBS)isbecomingmoreandmore

important.Furthermore,theshortestpathqueryinSpatial

NetworkDatabaseisoneofthemostwidelyusedservices.

AftertheinitiativeworkofDijkstra,alotofresearches

usingmanymethodsandalgorithmstosolvethequestion

oftheshortestpathqueryhavebeenconducted[1–13].

Therearetwo?eldsintheresearchontheshortestpath

algorithm:onlinecomputationandprecomputation.

Onlinecomputationhasbeenaddressed,forexample,in

*

Correspondingauthor.Tel.:+861062661582635.

E-mailaddress:xlyin@(X.Yin).

1002-0071/$-seefrontmatter2008NationalNaturalScienceFoundationofChinaandChineseAcademyofSciences.PublishedbyElsevierLimited

andScienceinChinaPress.Allrightsreserved.

doi:10.1016/j.pnsc.2008.01.031

894

X.Yinetal./ProgressinNaturalScience18(2008)893–899

algorithmwouldbeabletobeusedinothernetwork

environments.

?rst.ThenetworkismodelizedtoadigraphG=(R,J,C),

inwhichJisagroupofvertices.Weassumethat(J,J)

i

j

Wenowdiscusssomeworkrelatedtoprecomputation

below.Therearetwocompositepartsinthesealgorithms:

preprocessalgorithmtocomputetheauxiliarydata,and

queryalgorithmtocomputetheshortestpathwiththeaux-

iliarydata.

isthesingledirectededgefromJtoJconnectingany

ij

twodi?erentpointsJandJinJ.Jisthestartingpoint

i

j

i

oftheedge,andJistheendingpointoftheedge.Theedge

j

doesnotpassanyotherverticesinJ(ifthedirectededge

passesanyothervertexdi?erentfromJandJ,wesuppose

i

j

Gutman[27]de?nedReachofavertex.Simplyput,

Reachofavertexisanumber.ThevalueofReachisbigger

whenthevertexisinthemiddleoftheshortestpath,other-

wisethevalueissmaller.Gutmanshowedhowtomodify

thepathfromtheorigintothedestinationusingReach

ofavertex(upperlimit)andthedistanceofavertex(lower

limit).HeusedEuclideandistanceaslowerlimit,andsaid

that(J,J)isanemptyset).ThenRstandsforthesetofall

ij

thesesingledirectededges,andeveryelement(J,J)inR

i

j

correspondstooneandonlyonesingledirectededge.C

isaweightedfunction,andeverydirectededgeinRcorre-

spondstoaweightofapositiverealnumber.

IntheabovedigraphG,thepathfromoriginedgeto

destinationedgep(u,v)consistsofagroupofedgeseries

(r,...,r),inwhichu=r,v=r,"i,r2R(06i6k1).

thatthee?ciencycouldbeimprovedbyusingthequery

basedonEuclideanA*.

0

k

0

k

i

Thestartingpointofristhesameastheendingpointof

i

GoldbergandHarrelson[28,29]raisedthatthee?ciency

couldbeimprovedbasedonthequeryofA*usingland-

markaslowerlimit.Therefore,theygavetheALT(A*

r

,andk+1isthenumberofedgesofpathp(u,v).A

i+1

pathcannotincludealoop,whichis"r,r2p(u,v)

i

j

(i<j),thenthestartingpointofrisnotthesameasthe

i

search,landmarks,andtriangleinequality)method.This

methodcanimprovethee?ciencyofReachalgorithm.

SandersandSchultes[24,25]gavetheHighwayHierar-

chy(HH)algorithm.Theydescribedthisalgorithminthe

undigraphandpresentedhowtoexpandthisalgorithm

tothedigraph.Therealizationandtheexperimentofthis

algorithmarebasedontheundigraph.Wethinkthatthis

algorithmwouldnotlosee?ciencyinthedigraph.Under

thisassumption,HHalgorithmhasthecomplexityofthe

fastestqueryspeed,lessusedmemoryandreasonable

preprocess.

Thereisdi?erentmotiveinReachalgorithmandHH

algorithm.Theformeroneistoreducetoashortestpath,

andthelatteroneistolimitthealgorithmintoasmaller

subgraphbyusinginnerhierarchialpaths.Evenso,there

isacorrelationbetweenthesetwoalgorithms.

endingpointofr.Theweightofthepathisthesumof

j

weightsofalledgesexceptoriginedgeanddestination

P

k1

edge,whichis

CerT.Ifthereexistsapathfromuto

i?2

i

v,wecansaythatvcanbereachedfromu.Thedistance

d(u,v)betweentheedgesuandvthatcanbereachedis

R

de?nedastheleastweightamongallthepathsbetween

thesetwoedges,otherwise,thedistanced(u,v)wouldbe

R

unlimited.Ifk=1or0,thedistanced(u,v)is0.Theshort-

R

estpathp(u,v)betweenedgesuandvisde?nedasthepath

R

withtheleastweight,ofwhichtheleastweight=d(u,v).

R

Basedontheabovede?nitionofthenetworkmodeliza-

tion,wecande?nesomedatatypestomodelizethemoving

objects.

AgraphpointGP(r,pos)standsforamovingobject,

wherer=(J,J)2R,andpos2[0,1]standsfortherelative

i

j

valueoftheposition(o?set)ofthemovingobjectonthe

Themethodsdescribedabovegavemanywaystosolve

thequeryoftheshortestpathinaspacialnetwork,butthe

destinationobjectsareallassumedmotionlessinthesemeth-

ods.Sofar,thereisnoe?ectivealgorithmforthecasethatthe

originandthedestinationaremoving,fortheoldqueryalgo-

rithmscannotbeusedformovingqueryobjects,especially

themovingdestinationobjects.However,thequeryofthe

shortestpathformovingdestinationisawidelyaskedser-

vice,soitisaproblemthatneedstobesolvedquickly.To

solvethisproblemweestablishedagroupofindexedstruc-

turestochangethecomputationoftheshortestpathbetween

twomovingpointsintothecomputationoftheshortestpath

betweentwomotionlesssides.Thecomputationspeedis

improved,andthecomputationcomplexityisreduced

greatly.Inthetransportationnetwork,likethatinthe

metropolisofBeijingandShanghai,theshortestpathcan

begivenoutinrealtimebyusingourmethod.

edge.Ifpos=0,themovingobjectisonthevertexofJi,

andifpos=1,itisonthevertexofJ.Wecanusedmgp

j

todigressivelystandforthemovingtrailofthemoving

n

i

?1

object.dmgpisaseriesanddmgp?eet;gp;vmTTwhere

i

i

i

tisthetimepoint,gpisthegraphpointtodescribethe

i

i

movingobjectatthetimeoft,vmisthevelocityofthe

i

i

movingobjectatthetimeoft,and(t,gp,vm)=lis

i

i

i

i

i

calledthemovingunitattheorderiofdmgp.Weassume

thatthemovingobjectmovesintheaveragevelocityof

thepathbetweentwomovingunits;therefore,thelocation

ofthemovingobjectcanbecomputedthrough

interpolation.

Theshortestpathbetweentwographpointsgp(r,pos)

1

1

1

andgp(r,pos)isde?nedasp(gp,gp)=p(r,r).

2

2

2

R

1

2

R

1

2

3.Theshortestpathalgorithm

Thenetworkaftertheabovemodelizationbecomesa

digraphwithweight,andthemovingobjectismodelized

toagraphpoint.Thegraphpointmovesinthedigraph.

Becauseofthemovementoftheobject,especiallythatof

thedestinationobject,thecomputationoftheshortestpath

2.Networkmodel

InSpatialNetworkDatabase,movingobjectsarelim-

itedbythenetwork,soweneedtomodelizethenetwork

X.Yinetal./ProgressinNaturalScience18(2008)893–899

895

betweenobjectsbecomesmorecomplex.Welowerthe

complexityofthecomputationbybuildingtheindexof

theshortestpathtochangeacontinuallydynamicproblem

toastaticproblem.

3.1.Indexstructure

3.1.1.Indexoftheshortestpath

Consideringthatthemovingobjectmovesinthenet-

work,andtheshortestpathbetweentwopointsinthenet-

workcanbechangedtotheshortestpathbetweentwo

edgeswherethetwopointsare,wecanchangethecompu-

tationproblemoftwomovingpointstothecomputation

problemofstaticedges.

Fig.1.Indexstructureofshortestpath.

First,theedgesofthemodelizedgraphcanbemapped

tothevertices,andtheverticescanbemappedtotheedges.

Second,runningDijkstraalgorithmafterntimesmodi-

?cationtogettheshortestpathamongallverticesinthe

changedgraph.Thealgorithmisasfollows:

1)Initialization.Thestartingpointcanbesetas:

od=0,pisempty;

s

s

oAllotherpoints:d=1,p=?;

i

i

oMarkthestartingpointass.Nowk=s,andall

otherpointsarenotmarked.

2)Checktheweightfromallmarkedpointktothe

unmarkedpointjthatdirectlyisconnectedtok,

andsetd=min[d,d+l],inwhichlistheweight

Fig.2.Indexstructureofmovingobjects.

timeDt,theshortestpathalgorithmfrompmtopk

(16k6n)isasfollows:

j

j

k

k

k

ofvertexk.Ifk=s,thenl=0.

k

3)Choosenextpoint.Fromtheunmarkedpoints,

Input:Originobjectp,destinationobjectp,andtime

m

k

choosethesmallestifromd,whered=min[d,all

Dt.

j

i

j

unmarkedpointj].Pointiischosenasthepointin

theshortestpath,andsetasmarked.

Output:Theshortestpath.

4)Findthepointbeforepointi.Findthepointj

amongthemarkedpointsasthepointbeforei,which

isconnecteddirectlytopointi,thenseti=j.

5)Markpointi.Ifallverticesaremarked,thealgorithm

isderivedcompletely.Otherwise,markk=i,and

turntostep2tocontinue.

1:i=1,j=n

2:l=[(i+j)/2]

3:Ifl=m,thenpmisfound.Thesearchis?nished.

Otherwise,changethesearchingcondition,continue

tosearch.

4:i=1,j=n

5:l=[(i+j)/2]

Finally,arrangealltheshortestpathaccordingtothe

orderofserialnumberofedges.Thedatastructureisillus-

tratedinFig.1.

6:Ifl=t+Dt,then?ndgp(r,pos)ofpatt+Dt.

0

m

m

m

m

0

Thesearchis?nished.Otherwise,changethesearch-

ingcondition,continuetosearch.

7:i=1,j=n

3.1.2.Indexofmovingobjects

8:l=[(i+j)/2]

Sincethemovingtrailsofthemovingobjectscanbe

describeddiscretely,wecanbuildtheindexonthemov-

ingtrailsofthemovingobjectstosearchthelocationof

movingobjects.Therefore,wearereadytochangethe

shortestpathbetweenthepointstotheshortestpath

betweentheedges.Theindexstructureisindicatedin

Fig.2.

9:Ifl=k,then?ndp.Thesearchis?nished.Other-

wise,changethesearchingcondition,continueto

search.

10:i=1,j=n

k

11:l=[(i+j)/2]

12:Ifl=t+Dt,then?ndgp(r,pos)ofpatt+Dt.

0

k

k

k

k

0

Thesearchis?nished.Otherwise,changethesearch-

ingcondition,continuetosearch.

3.2.Theshortestpathalgorithm

13:i=1,j=n

14:l=[(i+j)/2]

Initialtimeist.Therearenmovingobjects.Origin

objectispm(16m6n).Destinationobjectisp.After

k

15:Ifl=m,then?ndr.Thesearchis?nished.Otherwise,

changethesearchingcondition,continuetosearch.

0

m

896

X.Yinetal./ProgressinNaturalScience18(2008)893–899

16:i=1,j=n

17:l=[(i+j)/2]

18:Ifl=k,then?ndtheshortestpathbetweenrandr.

Thesearchis?nished.Otherwise,changethesearch-

ingcondition,thencontinuetosearch.

4.1.Experimentaldata

Toruntheexperiment,ourdataarethegraphsgener-

atedrandomly.Thegenerationruleisasfollows:

m

k

1)Thereareatmost5andatleast1directlyconnected

verticestoeveryvertex.Amongthem,1%verticesare

directlyconnectedto1or5vertices,respectively,5%

verticesaredirectlyconnectedto3vertices,andthe

rest93%verticesaredirectlyconnectedto4vertices.

2)Theweightofeachedgeisfrom1to10.Among

them,1%edgeshaveweight1or10,respectively,

5%edgeshaveweight2or9,respectively,8%edges

haveweight3or8,respectively,15%edgeshave

weight4or7,respectively,and21%edgeshave

weight5or6,respectively.

Accordingtowhatisdescribedabove,themainidea

ofthealgorithmistochangetheproblemofcomputing

theshortestpathbetweentwomovingpointstothe

problemofcomputingtheshortestpathbetweentwosta-

ticedges.Tochangethenetworktoadigraphthrough

themodelizationandchangeofthenetwork,itiseasy

tobuildtheindexforshortestpath.Buildingtheindex

ofshortestpathcanchangetheshortestpathbetween

twopointstotheshortestpathbetweentwoedges.The

continuousquerywouldbepossiblethroughtheinterpo-

lationcomputationonthelocationofthemovingobjects

aftertimeDt,throughmodelizingandtreatingdigres-

sivelythemovingobjects.

Thealgorithm?rstdeterminesthelocationofthemov-

ingobjectaftertimeDtthroughtheindexofthemoving

objects(1–12above).Next,itgetstheshortestpathof

theedgesbetweenthedestinationobjectandoriginobject,

throughsearchingtheshortestpathindexoftheedgewhere

theoriginobjectis(13–18above).

Fivegraphsweregeneratedrandomly.Theyarewith

1000verticesand3942edges,2000verticesand7862

edges,3000verticesand11,778edges,5000verticesand

19,634edges,and8000verticesand31,404edges,

respectively.

4.2.Experimentalquery

Werun?vegroupsofqueriesagainsteachgraphwith

di?erentmovingobjects,respectively.Theshortestpaths

3.3.Analysisofthecomputationcomplexity

arequeriedwithoriginobjectpand1,5,10,20,and50

0

Assumethatthereareivertex,nedgesandkinterest

movinginterestsobjects,andeachgroupisqueried100

times.Theoriginobjectandinterestsobjectsareselected

randomly.Ourmeasurementstandardistheaveragetime

ofeachquery.

objectsingraphG.Itwouldtake(logn)+1timesat

2

mosttocomputebyrunning1–6above,(logn)+1

2

timesatmosttocomputebyrunning7–12,and

(logn)+1timesatmosttocomputebyrunning13–

2

18.So,itwouldtake3(logn)+3timesatmosttocom-

2

4.3.Experimentalresult

putewithouralgorithm.Therefore,theestimationofthe

timecomplexityofouralgorithmisO(logn).Weassume

thatthereisatmostoneedgebetweentwovertices,then

TheexperimentalresultsareillustratedbyTable1and

Figs.3and4.

2

thereareatmost(n*(n1))/2edgesingraphG.The

IneachpartofFig.3,thedestinationobjectsarethe

samebutthenumberofthegraphnodesincrease.

IneachpartofFig.4,thenumberofthegraphnodesis

thesamebutthedestinationobjectsincreases.

FromFigs.3and4wecandrawthefollowing

conclusions:

First,obviously,wecanseethatwhenthedestination

objectsandgraphnodeschange,theresultofusingthe

shortestpathindexalgorithmisbetterthanthatofusing

directlyDijkstraalgorithm.

timecomplexityisO(logi)intermsofi.Thetimecom-

2

plexityisO(klogi)whenweneedto?ndtheshortest

2

pathbetweenoriginobjectandkinterestsobjects.If

weusetraditionalDijkstraalgorithm,13–18woulduse

thetraditionalalgorithm.Thedestinationobjectswould

beturnedintovertices,andafterthecomputationof

theshortestpathinDijkstraalgorithm,theestimation

2

ofthetimecomplexityisO((i+k)).Therefore,theesti-

mationofthetimecomplexityofouralgorithm

O(klogi)ismuchlessthanthatofDijkstraalgorithm

2

2

O((i+k)).Inthespacecomplexity,thespacecomplexity

2

oftheshortestpathindexisO(n),andthespacecom-

2

Table1

Thetimeofbuildingindex

plexityofmovingobjectindexisO(n).

Vertices

Time(s)

4.Analysisoftheexperiment

1000verticesgraph

2000verticesgraph

3000verticesgraph

4000verticesgraph

5000verticesgraph

14.5

44.6

81.3

185

Below,wewillcomparetheexperimentalresults

obtainedusingtheshortestpathindexandtheresultsusing

theshortestpathquerywithDijkstraalgorithm.

462.3

X.Yinetal./ProgressinNaturalScience18(2008)893–899

897

Fig.3.Thenumberofdestinationobjectschanged.

Second,inonesame?gure,asthenumberofthedesti-

nationobjectsincreases,thee?ciencyofDijkstraalgo-

rithmkeepssteady,butthee?ciencyoftheshortestpath

indexalgorithmdecreases.However,evenwhenthereare

moredestinationobjects,thee?ciencyoftheshortestpath

indexalgorithmishigherthanthatofDijkstraalgorithm.

Finally,asthenumberofthegraphnodesincreases,the

e?ciencyofbothalgorithmsdecreases,butthee?ciencyof

theshortestpathindexalgorithmishigherthanthatofDijk-

straalgorithm.Evenwhentherearefewergraphvertices,the

e?ciencyoftheshortestpathindexalgorithmishigher.

networkdatabase.Thismethodisaprecomputation

method.Itstationizesthedynamicproblembybuilding

index.Inthealgorithmcomplexityandtheexperimental

analysis,theperformanceofourmethodisbetterthanthat

ofthemethodusingdirectlyDijkstraalgorithm.

Comparedwithotherqueryalgorithmsoftheshortestpath,

therearethefollowingspecialitiesorinitiativesinthispaper:

(1)Itsolvestheshortestpathproblembetweenmoving

objects.

(2)Throughthealgorithmofbuildingtheshortestpath

index,itchangestheproblemofcomputingtheshort-

estpathbetweentwomovingpointstotheproblem

ofcomputingtheshortestpathbetweentwomotion-

lessedges,thereforethecomplexityofthecomputa-

tionislowered.

5.Conclusions

Inthisstudy,weproposed,realized,andanalyzeda

shortestpathqueryalgorithmformovingobjectsinspatial

898

X.Yinetal./ProgressinNaturalScience18(2008)893–899

Fig.4.Thenumberofgraphnodeschanged.

(3)Thisalgorithmdoesnotdependonthespecialityof

[3]DenardoEV,FoxBL.Shortest-routemethodsI.Reaching,pruning,

andbuckets.OperRes1979;27:161–86.

[4]DijkstraEW.Anoteontwoproblemsinconnexionwithgraphs.

NumerMath1959;1:269–71.

thede?nednetwork,soitcanbeusedinmanyother

networks.

[5]FredmanML,TarjanRE.Fibonacciheapsandtheirusesin

improvednetworkoptimizationalgorithms.JAssocComputMach

1987;34:596–615.

Acknowledgements

[6]GalloG,PallottinoS.Shortestpathsalgorithms.AnnalOperRes

1988;13:3–79.

[7]GoldbergAV.Asimpleshortestpathalgorithmwithlinearaverage

time.In:Proc.9thESA,lecturenotesincomputerscienceLNCS,vol.

2161,Springer;2001,p.230–41.

ThisworkwassupportedbyNationalNaturalScience

FoundationofChina(GrantNo.60573164).

References

[8]GoldbergAV.Shortestpathalgorithms:engineeringaspects.In:

Proc.ESAAC’01,lecturenotesincomputerscience.Springer;2001.

[9]GoldbergAV,SilversteinC.ImplementationsofDijkstra’salgorithm

basedonmulti-levelbuckets.In:Lecturenotesineconomicsand

mathematicalsystems450(refereedproceedings),Springer;1997.p.

292–327.

[1]CherkasskyBV,GoldbergAV,RadzikT.Shortestpathsalgorithms:

theoryandexperimentalevaluation.MathProg1996;73:129–74.

[2]DantzigGB.Linearprogrammingandextensions.Princeton:Prince-

tonUniv.Press;1962.

X.Yinetal./ProgressinNaturalScience18(2008)893–899

899

[10]JacobR,MaratheMV,NagelK.Acomputationalstudyofrouting

algorithmsforrealistictransportationnetworks.OperRes

1962;10:476–99.

[11]MeyerU.Single-sourceshortestpathsonarbitrarydirectedgraphsin

linearaveragetime.In:Proc.12thACM-SIAMsymposiumon

discretealgorithms,Washington,DC,USA;2001.p.797–806.

[12]ThorupM.Undirectedsingle-sourceshortestpathswithpositive

integerweightsinlineartime.JAssocComputMach1999;46:362–94.

[13]ZhanFB,NoonCE.Shortestpathalgorithms:anevaluationusing

realroadnetworks.TranspSci1998;32:65–73.

[22]LautherU.Anextremelyfast,exactalgorithmfor?ndingshortest

pathsinstaticnetworkswithgeographicalbackground.In:IfGI-

prints22.InstitutfuerGeoinformatik,UniversitaetMuenster(ISBN

3-936616-22-1);2004.p.219–30.

[23]WagnerD,WillhalmT.Geometricspeed-uptechniquesfor?nding

shortestpathsinlargesparsegraphs.In:Europeansymposiumon

algorithms,Budapest,Hungary;2003.

[24]SandersP,SchultesD.Fastandexactshortestpathqueriesusing

highwayhierarchies.In:Proc.13thannualEuropeansymposium

algorithms,PalmadeMallorca,Spain;2005.

[14]IkedaT,HsuMY,ImaiH,etal.Afastalgorithmfor?ndingbetter

routesbyAIsearchtechniques.In:Proc.vehiclenavigationand

informationsystemsconference.IEEE,Yokohama,Japan;1