Dynamic route optimization with time-expanded graphs

Miguel R. Zuniga

doi:10.1117/12.242069

7 June 1996 Dynamic route optimization with time-expanded graphs

Miguel R. Zuniga

Proceedings Volume 2764, Digitization of the Battlefield; (1996) https://doi.org/10.1117/12.242069
Event: Aerospace/Defense Sensing and Controls, 1996, Orlando, FL, United States

Abstract

An important computer calculation in military planning is determining the optimal paths that a set of flying objects (airplanes, cruise missiles, UAVs) should take toward their targets. The current practice is to represent the problem with static graphs, then apply search algorithms (e.g. network flow) that can yield least cost paths. A number of significant problems must be solved in order to determine optimal and realistic paths. These include the difficulty associated with representing dynamic (time dependent) and realistic phenomena, and the associated difficulties of solving the graphs with polynomial-time algorithms. In this paper we discuss the limitations of modeling with graph theoretic techniques, and we present some results that permit significantly more accurate problem representation and solution than the previous state of the art. These include: a new method for graph representation of dynamic of phenomena associated with strike routing; some general relations that are important in modeling with graphs whose edge traversals represent independent probabilistic events; and a number of new models for use in optimizations. Some of the issues and solutions that we present are very general and they are also given detailed discussion in the context of two important military problems: general radar detection representation for optimization, and representation of the overflight problem (the increased threat to strike assets as they repeat flights over threats). Finally, the models and algorithms are considered in relation to single asset routing and joint routing of multiple assets.

Citation Download Citation

Miguel R. Zuniga "Dynamic route optimization with time-expanded graphs", Proc. SPIE 2764, Digitization of the Battlefield, (7 June 1996); https://doi.org/10.1117/12.242069

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available

Members: $17.00

Non-members: $21.00 ADD TO CART

PROCEEDINGS
12 PAGES

DOWNLOAD PAPER SAVE TO MY LIBRARY

GET CITATION

RIGHTS & PERMISSIONS

Get copyright permission Get copyright permission on Copyright Marketplace

KEYWORDS

Radar

Failure analysis

Optimization (mathematics)

Solids

Missiles

Computer programming

Data modeling

Show All Keywords

Keywords/Phrases

Search In:

Publication Years