Map-based Mobile Services Design,Interacton and Usability Phần 8 pot

12 Accuracy and Performance Assessment of a

Window-Based Heuristic Algorithm for Real-Time

Routing in Map-Based Mobile Applications

Hassan A. KARIMI1

, Peter SUTOVSKY1

, Matej DURCIK2

1School of Information Sciences, University of Pittsburgh

2

SAHRA-HWR, University of Arizona

Abstract. The demand for routing algorithms that produce optimal

solutions in real time is continually growing. Real-time routing algorithms

are needed in many existing and emerging applications and services. An

example is map-based mobile applications where real-time routing is

required. Conventional optimal routing algorithms often do not provide

acceptable real-time responses when applied to large real road network

data. As a result, in certain real-time applications, especially those with

limited computing resources (e.g., mobile devices), heuristic algorithms that

can provide good solutions, though not necessarily optimal, in real time are

employed. In this chapter, we present two approaches for limiting the

search space using a window-based heuristic algorithm to compute shortest

routes and analyze their solutions and performances using real road network

data. The results of a set of experiments on the two approaches show that

the window-based heuristic algorithm produces aceptable response times

using real road network data and that window sizes and orientations impact

accuracy and performance of the algorithm.

12.1 Introduction

Routing is a fundamental function in numerous map-based mobile applications.

Example applications are navigation, location-based services, and automatic vehi￾cle location. In such real-time map-based mobile applications, the overall accuracy

and performance of the underlying routing algorithm is of particular interest. This

is because routing accuracy influences the user’s confidence on and routing time

performance impacts the real-time response time of the maps produced. Providing

a reasonable level of confidence on the routes (which in some applications are the

only maps produced) to the users and having a fast routing solution (which im￾proves response time to real-time activities), will enhance the usability of real￾time map-based mobile applications. Therefore, it is imperative to realize the

12 Accuracy and Performance of a Window-Based Heuristic Algorithm 249

Routing belongs to a class of problems widely known as optimization and is

computed by using either conventional algorithms or heuristic algorithms. Con￾ventional routing algorithms are suitable in applications where the network size is

not large and there is no real-time processing constraint. However, in applications

where the network size is very large and routes must be computed in real time,

heuristic routing algorithms are considered, which may not guarantee optimal so￾lutions. This is because conventional routing algorithms’ performance lowers as

the size of the network increases resulting in unacceptable response times; most

conventional algorithms have O(N2

) time complexity in the worst case scenario,

where N is the number of nodes (intersections) in the road network. Routing algo￾rithms with such a time complexity are impractical in map-based mobile applica￾tions where real-time optimal routes, some on large networks, are needed and

where they typically feature mobile devices with limited CPU, memory, and

power. Therefore, heuristic routing algorithms play a major role in map-based

mobile applications and their proper design requires a thorough understating of

their accuracy and time performance.

Much research in the past few decades has been focused on developing fast al￾gorithms resulting mostly in heuristic routing algorithms that produce local￾optimal solutions. For example, see Fu et al. (2006) for a survey of heuristic short￾est path algorithms and Cherkassky et al. (1996) for an overview of theoretical

and experimental studies of various shortest route algorithms. Any real-time rout￾ing algorithm can be of practical use in map-based mobile applications only when

it produces reasonable solutions in an acceptable response time with real road

network data. To date, there have been very few new routing algorithms that are

tested for real-time processing using real road network data (Jacob et al. 1999; Ja￾gadeesh et al. 2002; Kim et al. 2005a). A review of the differences between using

real road network data and randomly generated network data along with the com￾putational study of routing algorithms using realistic networks can be found in Ja￾kob et al. (1999) and Liu (1997).

Chabini and Shan (2002) adapted A* algorithm to shortest path problems in

dynamic deterministic networks. They evaluated the algorithm on the randomly

generated network containing 3000 nodes and 10,000 links, and 100 time inter￾vals. They compared the dynamically adapted A* algorithm and the dynamically

adapted Dijkstra’s algorithm and reported that the dynamically adapted A* algo￾rithm resulted in a saving ratio of 11 in terms of nodes selected and a saving ratio

of five in terms of computational times. Huang et al. (2006) extended Lifelong

Planning A* algorithm to solve dynamic deterministic shortest path problems.

They suggest the use of an ellipse to prune the unnecessary nodes to be searched

and experimentally showed that the number of examined nodes could be 70-80%

less than that of the A* algorithm. This corresponds to 17-31% savings in compu￾tational time needed to calculate shortest paths using test road networks in the ex￾periments. Kim et al. (2005b) proposed to model the problem of computing dy￾namic stochastic shortest paths with traffic congestion information as discrete￾time finite horizon Markov decision process. They developed decision-making

accuracy and time performance of routing algorithms and their impact on such ap￾plications.

250

procedures for determining optimal driver attendance times, optimal departure

times, and optimal routing policies under time-varying traffic flows for just-in–

time delivery services. They tested their method using real-time traffic congestion

information for the road network in southeast Michigan. They achieved reduction

in travel time of approximately 9.8216.19%. (Kim et al. 2005a) also improved ef￾ficiency of their previous algorithm.

Map-based mobile applications’ effectiveness is often measured by the accu￾racy and time performance of the routing algorithms on which they are based. Ja￾gadeesh et al. (2002) have suggested a routing approach that combines hierarchi￾cal and heuristic techniques based on road classification. They tested their

approach using the road network of Singapore. On average, the routes computed

by their approach were 3.31% longer than the shortest routes. Zhao and Wey￾mouth (1991) proposed an adaptive route guidance technique that alternates be￾tween two different heuristic search algorithms based on the time available for

route computation. Jung and Pramanik (2002), Chabini and Shan (2002), and

Karimi (1996) developed a heuristic routing algorithm that limits the number of

nodes used in computation by devising a window with two of its sides parallel

with the straight line connecting the origin and destination nodes. However, while

this window-based heuristic routing algorithm provides reasonable time perform￾ance, further research was required to realize accuracy and time performance of

the algorithm based on a variety of possible windows (or subnetworks); windows

can geometrically have different size and structure.

The work presented in this chapter is based on the window-based heuristic rout￾ing algorithm developed by Karimi (1996), and is focused on different approaches

(window size and orientation) in limiting the search space that contains real road

network data. The objective of this work was to test the hypothesis that the size

and orientation of a subnetwork impact the accuracy and time performance of the

window-based heuristic routing algorithm. To test this hypothesis, two subnet￾work approaches (window size and orientation) were taken to reduce the search

space in the window-based heuristic routing algorithm. The impacts of different

sizes and orientations of windows on accuracy of the solutions and the time per￾formance by the window-based heuristic routing algorithm were analyzed. Both

approaches were tested using real road network data providing meaningful results

applicable to real-world map-based mobile applications.

The main contributions of this chapter are: (a) analysis of different approaches

for reducing the search space in the window-based heuristic routing algorithm and

(b) testing of the window-based heuristic routing algorithm using real road net￾work data. Realization of the impact of window size and orientation on accuracy

and time performance by the window-based heuristic routing algorithm will help

developing optimal solutions that meet the requirements of map-based mobile ap￾plications. The structure of the chapter is as follows. The window-based heuristic

algorithm is described in section 12.1. In section 12.2 the experiments conducted

are discussed. The results are discussed in section 12.3. Conclusions and ideas for

future research are given in section 12.4.

Hassan A. KARIMI, Peter SUTOVSKY, Matej DURCIK