Rectangle.
with text and connection points. Can be stretched to any dimensions.
Root Entry CompObj Pictures Current User SummaryInformation PowerPoint Document DocumentSummaryInformation
Times New Roman Monotype Sorts Blank Presentation
OlePres000 OlePres000
VISIO Visio.Drawing.40 VISIO 4 Drawing Times New Roman Symbol ew Roman Monotype Sorts Few (O(log n/log log n)) moving targets 
Efficient (1+)-approximation algorithm
 is performance bound of a heuristic for stationary TSP Blank Presentation
OlePres000
Times New Roman Symbol ew Roman Monotype Sorts Targets intercept origin 
Implicit change in target velocity
Valid tour: No target passes through the origin
Theorem: If the tour in which pursuer intercepts
Targets moving away in ascending order of di/vi
Approaching targets in descending order of di/vi
is valid, then it is optimal Blank Presentation When targets approach the origin, they may eventually reach the origin and move away from it. In other words, there is an implicit direction change in the target velocity, which is defined relative to the origin.
Thus, we created the concept of the “valid” tour, where to target passes through the origin before being intercepted by the pursuer.
Given the concept of the valid tour, we can show that if this tour is valid, where the pursuer first intercepts targets which move away from the origin in ascending order of di/vi and then targets approaching the origin in descending order of di/vi is valid, then this tour is optimal.
This leads to a natural question. What heuristics work if this tour is not valid?
Times New Roman Symbol ew Roman Monotype Sorts Problem: Find the fastest valid tour
Theorem: The tour where the pursuer intercepts targets in descending order of di/vi is always valid and the slowest
Theorem: Slowest tour  2(optimal valid tour) Blank Presentation We can formulate this problem as the problem of defending the origin.
The goal is for the pursuer to intercept each target before it intercepts the origin, and do this in a minimum amount of time. In effect, we are adding a new constraint that the tour must be valid.
First, we make the observation that a valid tour is always possible. In fact, the tour in which the pursuer intercepts targets in descending order of di/vi is always valid, but it is the slowest possible tour which does not involve some form of waiting. Notice that di is the initial distance of the target from the origin and vi is its velocity. Notice also that distance over velocity equals time. In fact, di/vi is exactly the amount of time before the target will intercept the origin. Thus, a target with smaller di/vi will hit the origin sooner, and can be considered more “dangerous”. Since the pursuer is faster than all targets, it can intercept the most dangerous target and return to the origin strictly before any other target will reach the origin. Thus, if we intercept targets in order of most dangerous to least dangerous, the tour will be valid.
Though this is also the slowest possible tour, we have shown that it
is still no worse than twice optimal.
Next, we consider the variant of Moving-Target TSP when there may be more than one pursuer. OlePres000
Times New Roman Monotype Sorts Blank Presentation OlePres000
Root Entry CompObj Pictures Current User SummaryInformation PowerPoint Document DocumentSummaryInformation Times New Roman Monotype Sorts
Blank Presentation OlePres000
Blank Presentation OlePres000 OlePres000
VISIO Visio.Drawing.40 VISIO 4 Drawing Times New Roman
VISIO Visio.Drawing.40 VISIO 4 Drawing Times New Roman Monotype Sorts
Times New Roman Symbol ew Roman Monotype Sorts Given:
A set S = {s1, s2,..., sn} of targets
Each target si has constant velocity vi
Each target si starts moving from a position pi  n
A pursuer starting at origin with maximum speed v > |vi|
Find:
A fastest tour which intercepts all targets
Variations (Moving-Target Vehicle Routing Problem):
Multiple pursuers j = 1.. k
Pursuers have a given capacity to fill target demand Blank Presentation
Page-1
Black fill
White fill
Blue fill
Red fill
Green fill
Cyan fill
Yellow fill
Magenta fill
Gray fill
10% Gray fill
White line
30% Gray fill
Long dashed line
Blue dark fill
Cyan dark fill
Green dark fill
Magenta dark fill
Red dark fill
Yellow dark fill
50% Gray fill
70% Gray fill
90% Gray fill
1pxl line
3pxl line
9pxl line
Hairline
Short dashed line
Arial centered
Arial top left
Arial top
Times centered
Times top
Times top left
Arial 8pt centered
Rectangle
Rectangle.3
Rectangle.43
Rectangle.16
Rectangle.18
Rectangle.19
Rectangle.25
Rectangle.26
Rectangle.27
Rectangle.28
Rectangle.29
Rectangle.30
Rectangle.31
Rectangle.32
Rectangle.33
Rectangle.34
Rectangle.35
Rectangle.39
Rectangle.40
Rectangle.41
Rectangle.42
Guide
Gesture Format
Arial Unicode MS
Symbol
Wingdings
Arial
SimSun
PMingLiU
MS PGothic
Dotum
Sylfaen
Estrangelo Edessa
Vrinda
Shruti
Mangal
Tunga
Sendnya
Raavi
Dhenu
Latha
Gautami
Cordia New
MS Farsi
Gulim
Times New Roman