Độ chính xác và đánh giá hiệu suất của một cửa sổ dựa trên thuật toán Heuristic định tuyến thời gian thực trong ứng dụng di động dựa trên Bản đồ | 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 School of Information Sciences University of Pittsburgh 2SAHRA-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 . 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. Introduction Routing is a fundamental function in numerous map-based mobile applications. Example applications are navigation location-based services and automatic vehicle 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 .
