Dynamic Modeling of Safe Routes

The timely determination of the safest routes and schedules for supply convoys is a critical need for post-conflict operations; however, the computational challenge increases exponentially with the number of destinations and the number of supply convoys. We will combine a form of A* algorithm with a combinatorial optimization algorithm to solve for the best convoy schedules. We will utilize a discrete directed graph with dynamic edge costs that represent a degree of ‘safe-ness’ by incorporating factors which include neighborhood hostility, traffic, and time of day. We propose to develop and compare two combinatorial optimization methods, Simulated Annealing and Genetic Algorithm, to provide timely near-optimal, multiple-convoy to multiple-destination delivery schedules. This work will build upon one of our existing operationally deployed GIS applications featuring an optimization module and routing algorithms. Deliverables will include two performance demonstrations: (a) planning for supply convoy scheduling and, (b) rapid re-planning for the convoy commander. We will also deliver a standalone software application which can be used in live exercises to evaluate the efficacy of the developed technology. Phase II will advance the optimization method and develop the capability as a web service application.