Dynamic Modeling of Safe Routes

Award Information
Agency: Department of Defense
Branch: Navy
Contract: N00014-08-C-0144
Agency Tracking Number: O081-CR4-4087
Amount: $100,000.00
Phase: Phase I
Program: SBIR
Awards Year: 2008
Solicitation Year: 2008
Solicitation Topic Code: OSD08-CR4
Solicitation Number: 2008.1
Small Business Information
6800 Cortona Drive, Goleta, CA, 93117
DUNS: 054672662
HUBZone Owned: N
Woman Owned: N
Socially and Economically Disadvantaged: N
Principal Investigator
 Patrick Toole
 Senior Scientist
 (805) 968-6787
 ptoole@toyon.com
Business Contact
 Marcella Lindbery
Title: Director of Finance and Contracts
Phone: (805) 968-6787
Email: mlindbery@toyon.com
Research Institution
N/A
Abstract
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.

* Information listed above is at the time of submission. *

Agency Micro-sites

SBA logo
Department of Agriculture logo
Department of Commerce logo
Department of Defense logo
Department of Education logo
Department of Energy logo
Department of Health and Human Services logo
Department of Homeland Security logo
Department of Transportation logo
Environmental Protection Agency logo
National Aeronautics and Space Administration logo
National Science Foundation logo
US Flag An Official Website of the United States Government