How to Estimate, Take Into Account, and Improve Tr

HowtoEstimate,TakeIntoAccount,andImproveTravelTimeReliabilityinTransportationNetworksRueyL.Cheu,VladikKreinovich,Fran¸coisModave,GangXiang,TaoLi,andTanjaMagocCenterforTransportationInfrastructureSystems,UniversityofTexas,ElPaso,TX79968,USA,[e-mail]fferfromtrafficcongestion.Intuitively,itmayseemthataroadexpansion(e.g.,theopeningofanewroad)shouldalwaysimprovethetrafficconditions.However,inreality,anewroadcanactuallyworsentrafficcongestion.Itisthereforeextremelyimportantthatbeforewestartaroadexpansionproject,wefirstpredicttheeffectofthisprojectontrafficcongestion.Traditionalapproachtothispredictionisbasedontheassumptionthatforanytimeoftheday,weknowtheexactamountoftrafficthatneedstogofromeachorigincityzoneAtoeveryotherdestinationcityzoneB(thesevaluesformanOD-matrix),andthatweknowtheexactcapacityofeachroadsegment.Underthisassumption,knownefficientalgorithmsproducetheequilibriumtrafficflows.Inreality,theroadcapacitymayunpredictablychangeduetoweatherconditions,accidents,etc.Driverstakethisuncertaintyintoaccountwhenplanningtheirtrips:e.g.,ifadriverdoesnotwanttobelate,heorshemayfollowaslowerroutebutwithaguaranteedarrivaltimeinsteadofa(onaverage)fasterbutunpredictableone.Wemustthereforetakethisuncertaintyintoaccountintrafficsimulations.Inthispaper,wedescribealgorithmsthattakethisuncertaintyintoaccount.Keywords:transportationnetworks,trafficassignment,reliability,risk-takingbehavior1.DecreasingTrafficCongestion:FormulationoftheProblemDecreasingtrafficcongestion:apracticalproblem.Manyurbanareassufferfromtrafficcongestion.Itisthereforedesirabletodecreasethiscongestion:e.g.,bybuildingnewroads,orbyaddingnewlanestotheexistingroads.Importantdifficulty:anewroadcanworsentrafficcongestion.Intuitively,itmayseemthataroadexpansion(e.g.,theopeningofanewroad)shouldalwaysimprovethetrafficconditions.However,inreality,anewroadcanactuallyworsentrafficcongestion.Specifically,iftoomanycarsmovetoanewroad,thisroadmaybecomeevenmorecongestedthantheoldroadsinitiallywere,andsothetrafficsituationwillactuallydecrease–promptingpeopletoabandonthisnewroad.Thispossiblenegativeeffectofanewroadoncongestionisaverywellknown“paradox”oftransportationscience,aparadoxwhichexplainstheneedforadetailedanalysisintheplanningofthenewroad;see,e.g,(Ahujaetal.,1993;Sheffi,1985).ThisparadoxwasfirstdiscoveredbyA.c2008byauthors.PrintedinUSA.REC2008-RueyL.Cheu,VladikKreinovich,etal.2RueyL.Cheu,VladikKreinovich,etal.Doig(see(Appa,1973))andfirstpublishedin(Braess,1968;CharnesandKlingman,1971;Szwarc,1971).Importanceofthepreliminaryanalysisoftheresultsofroadexpansion.Ourobjectiveistodecreasetrafficcongestion.Wehavejustmentionedthatanadditionofanewroadcanactuallyworsenthetrafficcongestion.Itisthereforeextremelyimportantthatbeforewestartaroadexpansionproject,wefirstpredicttheeffectofthisprojectontrafficcongestion.Traditionalapproachtopredictingtheresultsofroadexpansion.Traditionalapproachtopredictingtheresultsofroadexpansionisbasedontheassumptionthatforanytimeoftheday,weknowtheexactamountoftrafficthatneedstogofromeachorigincityzoneAtoeveryotherdestinationcityzoneB(thesevaluesformanOD-matrix),andthatweknowtheexactcapacityofeachroadsegment.Underthisassumption,knownefficientalgorithmsproducetheequilibriumtrafficflows;see,e.g.,(Sheffi,1985).Limitationsofthetraditionalapproachtopredictingtheresultsofroadexpansion.Inreality,theroadcapacitymayunpredictablychangeduetoweatherconditions,accidents,etc.Driverstakethisuncertaintyintoaccountwhenplanningtheirtrips:e.g.,ifadriverdoesnotwanttobelate,heorshemayfollowaslowerroutebutwithaguaranteedarrivaltimeinsteadofa(onaverage)fasterbutunpredictableone.Wemustthereforetakethisuncertaintyintoaccountintrafficsimulations.Whatwedointhispaper.Inthispaper,wedescribealgorithmsthattaketheaboveuncertaintyintoaccount.Comment.Someoftheresultspresentedinthispaperfirstappearedinourresearchreport(Cheuetal.,2007).Thisreportalsodescribesasoftwarepackagethatimplementsouralgorithms.2.TrafficAssignment:BriefReminderRoadassignmentproblem:informaldescription.Inordertoselectthebestroadexpansionproject,wemustbeabletopredicthowdifferentprojectswillaffectroadcongestion.Forthat,weneedtobeable,basedonthetrafficdemandandontheroadcapacities,topredictthetrafficondifferentplacesofdifferentroadsatdifferenttimesoftheday.Thispredictionproblemiscalledthetrafficassignmentproblem.Todescribethisprobleminpreciseterms,weneedtodescribehowexactlythetrafficdemandisdescribed,howtheroadcapacitiesaredescribed,andwhatexactlyassumptionsdowemakeaboutthedrivers’behavior.Granulation.Todescribetrafficdemand,wedividetheurbanareaintozonesanddescribehowmanydriversneedtogetfromonezonetoanother.Similarly,todescriberoadcapacity,wedividealltheroadsintoroadsegments(links),anddescribethecapacityofeachlink.Thetimeofthedayissimilarlydividedintotimeintervals.Comment.Howtoselectanappropriatesizeofazone,ofaroadlink,andofatimeinterval?REC2008-RueyL.Cheu,VladikKreinovich,etal.TravelTimeReliability3−Ontheonehand,thefinerthedivision,wemoreaccurateistheresultingtrafficpicture.−Ontheotherhand,thefinerthedivision,themorezonesandlinksweneedtoconsiderandhence,them