Faculty of Computer Systems and Technologies Collectionhttps://onlineresource.ucsy.edu.mm/handle/123456789/7152024-03-29T15:29:10Z2024-03-29T15:29:10ZA novel solution for simultaneously finding the shortest and possible paths in complex networksHlaing, Wai MarLiu, Shi-JianPan, Jeng-Shyanghttps://onlineresource.ucsy.edu.mm/handle/123456789/25412020-12-30T10:13:44Z2019-11-01T00:00:00ZA novel solution for simultaneously finding the shortest and possible paths in complex networks
Hlaing, Wai Mar; Liu, Shi-Jian; Pan, Jeng-Shyang
A Novel graph approach named Combined Forward
and Backward Heuristic Search (CFBHS) is proposed in
this paper, which can be used to solve optimization
problems in areas such as transportation and network
routing. There are two major aspects distinct our method
from the most cited ones. Firstly, though focuses on
getting the shortest path in a graph when both source and
destination are given, this work can also find other
possible paths as outputs. Secondly, the proposed
algorithm is a high-performance one, which is achieved
by (1) reducing unnecessary nodes and edges to reach a
target optimum based on dynamically calculated heuristic
values and (2) finding the results by using the subdivision scheme instead of computing over the whole
graph. Experiments are carried out for the complex road
network of Yangon Region. The comparisons show that
our algorithm is about 100 times faster than the bidirectional Dijkstra’s algorithm. Besides, benefit from the
heuristic forward and backward search, the proposed
method can achieve very low time complexity, which is
similar to the A*, but A* can only produce the shortest
path. By contrast, the proposed algorithm is competent
for finding not only the shortest but also many possible
paths in complex road networks such as undirected graph
and hypergraph networks.
2019-11-01T00:00:00ZNeighbor Search with Hash Map Indexing Technique for Complex NetworksHlaing, Wai MarSein, Myint Myinthttps://onlineresource.ucsy.edu.mm/handle/123456789/25402020-12-30T10:13:44Z2020-02-26T00:00:00ZNeighbor Search with Hash Map Indexing Technique for Complex Networks
Hlaing, Wai Mar; Sein, Myint Myint
Neighbor Search with Hash Map Indexing Technique is used to get the high performance when
the optimal path is searched in the complex networks. This system can also give advice the public bus
passengers about the travel route depend on the travel time and cost. Moreover, the proposed technique is
highly performance one if it compares about the response time of many other popular cited shortest path
algorithms. Especially it contains two main parts for finding the optimal path, the first one is dividing the
complex large tree into small sub-trees using divide and conquer at an optimal threshold value. The second
one is using heuristic neighbor search instead of searching the heuristic values of all expanded nodes at
current level. Heuristic neighbor search and hash-map indexing technique is used together to reduce the time
complexity when the heuristic values are searched dynamically depend on the user query to reach the target.
The proposed system is faster than the popular bi-directional heuristic search A* algorithm, previously
proposed combined forward and backward heuristic search algorithm and modified heuristic search algorithm.
Road network and bus network in Yangon Region is used as the case study for spatial database.
2020-02-26T00:00:00ZK-means Nearest Point Search Algorithm and Heuristic Search for TransportationHlaing, Wai MarSein, Myint Myinthttps://onlineresource.ucsy.edu.mm/handle/123456789/25392020-12-30T10:13:44Z2018-12-13T00:00:00ZK-means Nearest Point Search Algorithm and Heuristic Search for Transportation
Hlaing, Wai Mar; Sein, Myint Myint
This paper aims to support the most suitable
route for passengers of the taxi system using the proposed
heuristic search method. Furthermore, k-Means Nearest Point
Search (kMNPS) algorithm is proposed to produce the nearest
road point for start and end addresses. Yangon downtown in
Myanmar is selected as a case study for the transportation
system. The proposed heuristic method and kMNPS algorithm
reduce the distance calculations and achieve the very low time
complexity for the real time transportation applications.
Moreover, the proposed system can produce not only the
optimal route on the map but also the popular spots near the
optimal route.
2018-12-13T00:00:00ZSearch Space Reduction using K-means Clustering and Adjacency matrices for GIS Usage Information RetrievalHlaing, Wai MarSein, Myint Myinthttps://onlineresource.ucsy.edu.mm/handle/123456789/25382020-12-30T10:13:44Z2016-12-10T00:00:00ZSearch Space Reduction using K-means Clustering and Adjacency matrices for GIS Usage Information Retrieval
Hlaing, Wai Mar; Sein, Myint Myint
Nowadays, people widespread use of
smartphones and ubiquitous devices for map based services.
As the transport network is complicated and massive, people
may be confused to reach the desired location after finding a
location. Many searching techniques are used for finding the
shortest path, might still not be fast enough in certain realtime applications because of complexing transport network.
Search time can be reduced if we pruned unnecessary clusters
in a complex large graph. Memory utilization is safe for the
processing time if we reduce search space in complex network.
For removing unnecessary clusters, adjacency matrices,
distance based methods and K-means clustering can be used.
ArcGIS software and popular shortest path algorithms are
applied to find the shortest path from one location to another
on the Android mobile platform. In addition, the performance
of finding the shortest path using popular A* and Dijkstra
algorithms with bidirectional search can be compared before
and after removing unnecessary clusters.
2016-12-10T00:00:00Z