Time-space network based exact models for periodical monitoring routing problem

Unmanned Air Vehicles (UAVs) have been used cooperatively with Unattended Ground Sensors (UGSs) to monitor and identify intruders on a road network system. The current practice includes four phases. In the patrol phase, UAVs visits UGSs periodically to detect the possible alarms. Once an alarm is detected, the second isolation phase is activated to determine the region of the intruders on the network. Delivery/ classification and response are the two following phases, which need more human involvements. This work focuses on the first patrol phase to determine the optimal patrol route visiting the UGSs periodically with minimal weighted revisit time interval. Since the objective focuses on a single UGS with worst performance (longest revisit time) and there are large number of alternative optimal solutions, a secondary objective is considered to minimize the duration of the total reiterative tour. Two mixed integer programming models are considered on a time-space discretized network. Numerical experiments show the nontrivial solutions on a small network. The second model improves the computational performance from the first model. The quality of the solutions are evaluated by upper and lower bounds.