International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV. Part B2. Istanbul 2004
3. OPTIMAL PATH BETWEEN RESERVOIRS
Optimal path problem is the problem of finding the minimum-
cost path from a node to the other in a network. This study
finds an optimal path between two points or distribution
reservoirs using Dijkstra’s algorithm and calculates the
construction cost based on the found optimal route.
3.1 Applying Dijkstra's algorithm
Dijkstra's algorithm is one of the popular shortest path
algorithms that explore minimum-cost path in a network. It has
been frequently applied in transportation field that searches a
shortest path from the origin to the destination. In Dijkstra's
algorithm, the process starts from an origin and gradually
explores the neighbour of nodes to determine the minimum-cost
path until it reaches the destination. The process finds the
shortest paths from a given source to all nodes in a network;
therefore this problem is sometimes called the single source
shortest problem (Morris 1998, Skiena 1998). Dijkstra's
algorithm is introduced in numerous books about computer
algorithms, so it is not described here further.
The study finds optimal paths using two types of cost; first
the length of links as traditional Dijkstra's algorithm would use
and second, the aggregate distance between a link and all small
blocks included in a large-sized reservoir block. To use the
second method, each segment of the street is first assigned the
aggregate length from the all small blocks in a reservoir block
to the link segment. Then, the same Dijkstra's algorithm is
applied, this time, using the aggregate block length as the cost,
resulting in a path of optimal distance to the small blocks. It
turns out that the second method prevents a path from being
located inclined to one side in a reservoir block.
3.2 Calculating the construction cost
Along with the process for generating the optimal paths, the
study also calculated the construction cost along the path using
the equations in Table 3.(Ha 2000)
Table 3. Cost of buried unit pipe
Diameter Cost of buried unit pipe R MAE
(mm) (Won/m) (99)
675-350 | e-19904419.659xd' ^ | 0.9995 0.9
> 400 e = 41685+1.3302xd'™ | 0.9973 0.3
4. SYSTEM DEVELOPMENT
Two management systems — the pipe monitoring system and
the optimal path system — were integrated in a user interface.
The study used Visual Basic and ESRI's MapObject component
to develop the interface. Along with such basic functions as
zooming and panning, the system included two major modules,
each with many sub functions. Figure 2 shows an example of
pipe superannuation management. One of the key aspects of
this module is the block designing function. Instead of using
the traditional blocks which have been used so far, the system
allows the user to create different blocks based on the current
street network and water consumption of each parcel. This way,
the system made it possible to design blocks dynamically
according to varying attributes such as continuously changing
street network or water use. Figure 3 illustrates a process for
creating an optimal path between two user-provided points.
When entering the points, the user is guided by the system that
shows location of distribution reservoirs.
10x
lex
0 z] en | vem]
EET
|
|
8
Greater than 86
3 uox
— wages |
{ a
SHE AMD
din
AJ BE? Mel
UTER
xs = RER ETES
Lau | Iur +
d
a TE 0mm gf RAHIES QS 3 LE
Figure 3. Optimal path creation system
5. CONCLUDING REMARKS
Since construction for water pipes usually requires time and
money on a large scale, the decision should be made based on
proper estimation and analysis. The study, with the aim to
support such decision making, developed a prototype system
that can help in two areas; firstly, block designing and pipe
monitoring and second, optimal path simulation between major
reservoirs. With further refinement, the system is expected to
help in following aspects:
. Block-designing can be made more reasonable by
incorporating up-to-date street network and water
consumption.
. The pipe management module also helps the
decision makers by allowing them to use various
factors affecting the superannuation.
. Alternative pipe routes can be created by simple user
“operations on the screen showing existing reservoirs
and pipe network.
To make the system more practical, it should be equipped with
such functionality as elevation-extraction from DEM maps te
calculate the superannuation and the pipe route considering the
elevation differences. ^ Also, other separate systems such as
water-leak monitoring can be integrated into the system to help
comparison of logical superannuation with field values.
Interna
ACKN
This wt
Engine
REFER
Ha, S-I
using tl
Civil Ei
Morris,
http://ci
| (acces
Office (
plan of
2003)
Skiena,
Verlag,
