Dynamic Modeling of Safe Routes

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

US Flag An Official Website of the United States Government