关键词: 城市交通, 空地协同巡逻, 自适应大邻域搜索, 路径优化, 帕累托前沿

Abstract: In the routine patrol operations of urban traffic police, ground patrol vehicles are constrained by the road network topology and traffic congestion, which limits their mobility and makes it difficult to simultaneously achieve full-area patrol visibility and rapid response at congested locations. This paper proposes a bi-objective mixed-integer programming model for air-ground collaborative traffic police patrol routing, with the joint objective to maximize the risk capture of congestion and the scale of covered patrol nodes. The model characterizes the heterogeneous motion constraints of ground patrol vehicles and police UAVs, as well as incorporates a collaborative task logic of "airborne detection- ground response- task reassignment". To address the computational challenges over large-scale road networks, an improved adaptive large neighborhood search algorithm is developed: an improved Shaw removal operator incorporating dual weights of spatial distance and congestion risk difference is proposed to enhance identification of risk-clustered zones; a unified greedy repair operator is designed to enable dynamic air-ground resource allocation; and a local incremental time evaluation formula is derived to reduce computational overhead. Experiments are conducted on a real road network in the cross-river district of Hangzhou. Results show that the proposed algorithm outperforms the genetic algorithm, NSGA- II, and tabu search baselines in terms of captured risk score, number of covered nodes, and composite score. Compared with the tabu search, the proposed algorithm improves the composite score by 19.3% and the number of covered nodes by 24.7%. The ablation study shows that, after incorporating the improved Shaw operator, the proposed algorithm improves the composite score by 4.5%, the captured risk score by 12.5%, and reduces the running time by 21.6% compared with ALNS-G; Pareto frontier analysis shows that the proposed algorithm clearly dominates the tabu search in the bi-objective space of risk capture and node coverage, which provides decision-makers with patrol scheme options under different operational preferences.

Key words: urban transportation, air- ground collaborative patrol, adaptive large neighborhood search, route optimization, Pareto frontier