ComplexityAnalysisofGreenLightOptimalVelocityProblemAnNPcompleteResultforBinarySpeedChoices
ComplexityAnalysisofGreenLightOptimalVelocityProblemAnNPcompleteResultforBinarySpeedChoices.pdf
Themotionofgroundvehiclesinasignalizedtrafficcansignificantlyaffectthethroughputandefficiency.Thispaperpresentsthecomplexityanalysisofaknowngreenlightoptimalvelocity(GLOV)problem,i.e.,usingthetrafficlighttiminginformationtofindoptimalspeedprofilesthatcanavoididlingatredlightsandminimizethetriptime.AmathematicalmodelforGLOVisformulatedforthesignalizedtrafficnetwork,andthenitsproblemcomplexityisanalyzedbypolynomial-timereducingaknownNP-completeproblem,i.e.,partitionproblem,intoGLOV.ThecomplexityanalysisshowsthatGLOVwithbinaryspeedchoicesbelongstoNP-complete,whichmeansitcannotbenumericallysolvedinpolynomialtimeunlessP=NP.
作者：ZhengYangLiSheng-boEbenXuBiaoLiKe-qiangWangJian-qiang
作者单位：TheStateKeyLabofAutomotiveSafetyandEnergy,TsinghuaUniversity,Beijing100084,China
母体文献：2015年南京第十四届亚太智能交通论坛论文集
会议名称：2015年南京第十四届亚太智能交通论坛
会议时间：2015年4月27日
会议地点：南京
主办单位：交通运输部
语种：chi
分类号：
关键词：ITStrafficnetworkgreenlightcomplexityanalysisoptimalspeed
在线出版日期：2019年1月18日
基金项目：
相似文献
相关博文
页:
[1]