On the K Windy Rural Postmen Problem with a Patrol Routing Application by Multiple Unmanned Autonomous Vehicles

Abstract

With more advanced AI and IoT unmanned autonomous vehicles can replace partial manpower for patrol routing Current patrol routing practices usually exploit the nearest first heuristics for visit patrol boxes located in different places Such routes take a longer time and are more predictable Here we aim at the design of optimal patrol routes in a systematic way considering travel costs security requirements and fair workloads among coordinated unmanned patrol vehicles To be more realistic we consider a windy graph with arcs of different lengths in different directions This leads to a K windy rural postmen problem In particular we seek optimal tours for all the unmanned vehicles such that all required road segments are patrolled with minimum travel costs We propose two integer program (IP) formulation on a level-space network The first IP formulation can only deal with small networks The second IP formulation is conducted on a reduced network where we only consider the nodes adjacent to the required patrolling arcs and treat a shortest path between any two nodes as an arc in this reduced graph This second IP formulation can solve larger cases but still cannot deal with practical cases We design three fast heuristics on the reduced network: Greedy algorithm Genetic Algorithm (GA) and Local search (LS) Computational experiments indicate the initial solution obtained by GA and further improved by LS can calculate solutions of satisfactory qualities for larger problems

Date of Award	2019
Original language	English
Supervisor	I-Lin Wang (Supervisor)