USA flag logo/image

An Official Website of the United States Government

Dynamic Modeling of Safe Routes

Award Information

Agency:
Department of Defense
Branch:
Office of the Secretary of Defense
Award ID:
86113
Program Year/Program:
2008 / SBIR
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-
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
 

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.

Principal Investigator:

Patrick A. Toole
Senior Scientist
8059686787
ptoole@toyon.com

Business Contact:

Marcella R. Lindbery
Director of Finance and Contracts
8059686787
mlindbery@toyon.com
Small Business Information at Submission:

TOYON RESEARCH CORP.
6800 Cortona Drive Goleta, CA 93117

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