USA flag logo/image

An Official Website of the United States Government

Dynamic Modeling of Safe Routes

Award Information

Department of Defense
Office of the Secretary of Defense
Award ID:
Program Year/Program:
2008 / SBIR
Agency Tracking Number:
Solicitation Year:
Solicitation Topic Code:
Solicitation Number:
Small Business Information
Toyon Research Corporation
6800 Cortona Drive Goleta, CA 93117-3021
View profile »
Woman-Owned: No
Minority-Owned: No
HUBZone-Owned: No
Phase 1
Fiscal Year: 2008
Title: Dynamic Modeling of Safe Routes
Agency / Branch: DOD / OSD
Contract: N00014-08-C-0144
Award Amount: $100,000.00


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.

Principal Investigator:

Patrick A. Toole
Senior Scientist

Business Contact:

Marcella R. Lindbery
Director of Finance and Contracts
Small Business Information at Submission:

6800 Cortona Drive Goleta, CA 93117

EIN/Tax ID: 953526665
Number of Employees:
Woman-Owned: No
Minority-Owned: No
HUBZone-Owned: No