A Mixed-Integer Programming Framework for Drone Routing and Scheduling with Flexible Multiple Visits in Highway Traffic Monitoring

Abstract

Traffic crashes and congestion generate high social and economic costs, yet traditional traffic monitoring methods, such as police patrols, fixed cameras, and helicopters, are costly, labor-intensive, and limited in spatial coverage. This paper presents a novel Drone Routing and Scheduling with Flexible Multiple Visits (DRSFMV) framework, an optimization model for planning drone-based highway monitoring under realistic operational constraints, including battery limits, variable monitoring durations, recharging at a depot, and target-specific inter-visit time limits. A mixed-integer nonlinear programming (MINLP) model and a linearized version (MILP) are presented to solve the problem. Due to the NP-hard nature of the underlying problem structure, a heuristic solver, Hexaly, is also used. A case study using real traffic census data from three Southern California counties tests the models across various network sizes and configurations. The MILP solves small and medium instances efficiently, and Hexaly produces high-quality solutions for large-scale networks. Results show clear trade-offs between drone availability and time-slot flexibility, and demonstrate that stricter revisit constraints raise operational cost.