Geography Reference
In-Depth Information
(Dreyfus 1969 ; Ford and Fulkerson 1958 , 1962 ; Kaufman and Smith 1993 ; Kohler
et al. 2002 ;OrdaandRom 1991 ; Pallottino and Scuttella 1998 ). This model
duplicates the original network for each discrete time unit t D 0,1, :::, T where
T represents the extent of the time horizon. The expanded network has edges
connecting a node and its copy at the next instant in addition to the edges in
the original network, replicated for every time instant. This significantly increases
the network size and is very expensive with respect to memory. Because of the
increased problem size due to replication of the network, the computations become
expensive. In addition, time expanded graphs (TEG) have representational issues
when modeling non-flow networks. This model incorporates the time dependent
edge attributes into the graph in the process of graph expansion, making it more
application-dependent, and thus making physical data independence harder to
achieve.
As noted previously, in order for TEG to show the changes in edge connections
over time, they must duplicate the network for every time step. This repetition
is excessive in models with many time-steps. A TEG has one copy of the set of
nodes for each discrete time instant. Figure 6.4 shows a TEG representation of the
example path presented before as a space-time trajectory (Fig. 6.2 a). The location
of person P at different time-instants is shown via the bolded nodes and edges. This
representation may be quite natural for the last question in Table 6.1 , however it will
require more exerted effort to answer the other questions.
Corresponding to each edge with transit time t in the original network, there is
a copy of an edge (called the cross edge) between each pair of copies of nodes
separated by the transit time t (Ford and Fulkerson 1958 ; Hamacher and Tjandra
2002 ; Kohler et al. 2002 ). Thus, a time-dependent flow in a dynamic network can
be interpreted as a static flow in a time expanded network. This allows application
of static algorithms on such networks to solve dynamic flow problems. Apart from
the “enormous increase in the size of the underlying network” (Kohler et al. 2002 ),
this model may be suitable for some application domains of linear programming
(Luenberger 1973 ).
A time expanded graph assumes that the edge weight represents a flow parameter,
and it represents the time taken by the flow to travel from the source node to the end
node. This is represented by the cross edges between the copies of the graph. Since
the cross edges in a time expanded graph represent a flow across the nodes, the
representation of non-flow networks using this model is not obvious.
In most spatio-temporal networks, the length of the time period (indicated by T
in this paper) might not be known in advance since data arrives as a sequence at
discrete time instants. For example, sensors in transportation networks collect data
at a rate of about once every 30 s. Crimes are reported whenever an incident occurs.
It is not clear how they would handle time series of infinite length. In addition, the
need for prior knowledge of T may lead to problems in the algorithms based on
time expanded networks since an underestimation of T can result in failure to find a
solution, and lead to high storage and run time costs that would adversely affect the
scalability of the algorithms.
Search WWH ::




Custom Search