原文传递
Complexity Analysis of Green Light Optimal Velocity Problem: An NP-complete Result for Binary Speed Choices
| 题名： | Complexity Analysis of Green Light Optimal Velocity Problem: An NP-complete Result for Binary Speed Choices |
| 正文语种： | 中文 |
| 作者： | Zheng Yang LiSheng-bo Eben Xu iao Li Ke-qiang Wang Jian-qiang |
| 作者单位： | The State Key Lab of utomotive Safety and Energy,Tsinghua University,Beijing 100084, hina |
| 关键词： | ITS traffic network green light complexity analysis optimal speed |
| 摘要： | The motion of ground vehicles in a signalized traffic can significantly affect the throughput and efficiency.This paper presents the complexity analysis of a known green light optimal velocity (GLOV) problem, i.e., using the traffic light timing information to find optimal speed profiles that can avoid idling at red lights and minimize the trip time.A mathematical model for GLOV is formulated for the signalized traffic network, and then its problem complexity is analyzed by polynomial-time reducing a known NP-complete problem, i.e., partition problem, into GLOV.The complexity analysis shows that GLOV with binary speed choices belongs to NP-complete, which means it cannot be numerically solved in polynomial time unless P =NP. |
| 会议日期： | 20150427 |
| 会议举办地点： | 南京 |
| 会议名称： | 2015年南京第十四届亚太智能交通论坛 |
| 出版日期： | 2015-04-27 |
| 母体文献： | 2015年南京第十四届亚太智能交通论坛论文集 |
相关文献
- A More Practical Traffic Lights Cellular Automata Model for Traffic Flow Simulation
- Structural Analysis and Sizing Optimization of Low Control arm for Multilink Suspension
- AERODYNAMIC MULTI-OBJECTIVE OPTIMIZATION DESIGN STUDY ON AIR DEFLECTOR OF LIGHT DUTY TRUCK
- Robot Driver's Motion Analysis and Simulation Based on Vehicle Speed Control
- Simulation Analysis Technique for Low Speed Road Noise to Automobile
- Numerical Simulation Analysis and Test of Standing Wave Border Speed about Radial Tire
检索历史
应用推荐
