Dynamic Modeling of Safe Routes

Award Information
Agency:
Department of Defense
Branch
Office of the Secretary of Defense
Amount:
$100,000.00
Award Year:
2008
Program:
SBIR
Phase:
Phase I
Contract:
N00014-08-C-0144
Award Id:
86113
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. (Currently TOYON RESEARCH CORPORATION)
6800 Cortona Drive, Goleta, CA, 93117
Hubzone Owned:
N
Minority Owned:
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


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

Enviromental Protection Agency logo

National Aeronautics and Space Administration logo

National Science Foundation logo
US Flag An Official Website of the United States Government