Unmanned aerial vehicle (UAV) was introduced for nondeterministic traffic monitoring, and a real-time UAV cruise route planning approach was proposed for road segment surveillance. First, critical road segments are defined so as to identify the visiting and unvisited road segments. Then, a UAV cruise route optimization model is established. Next, a decomposition-based multi-objective evolutionary algorithm (DMEA) is proposed. Furthermore, a case study with two scenarios and algorithm sensitivity analysis are conducted. The analysis result shows that DMEA outperforms other two commonly used algorithms in terms of calculation time and solution quality. Finally, conclusions and recommendations on UAV-based traffic monitoring are presented.