Μια Android εφαρμογή για το «Ερώτημα Σχεδιασμού Ταξιδιού»

Καββαλάκης, Κωνσταντίνος Σ.

An android application for the “Trip Planning Query”

Master Thesis

Author

Καββαλάκης, Κωνσταντίνος Σ.

Date

2014-02-20

Abstract

The objective of the current master thesis is the implementation of an efficient android application that utilizes the Iterative Doubling algorithm. It runs in a mobile device with known computational processing limitations. Finally as the user of the application imposes, the optimal path should start from a specified source, pass through several points of interest (POIs) and reach specified destination. These problems are generally known as “Trip Planning Queries” (TPQ). Trip Planning Queries (TPQ) belong to NP-hard problems. In general there are many proposed algorithms which result in an approximate or inefficient in terms of complexity solution. The previously mentioned drawbacks prevent the use of those algorithms in many implementations. However the solution presented in this thesis reduces complexity by imposing the order of visiting locations. The algorithm which is used manages to find a route of minimum length by visiting points from each category sequentially before it steps to the next category. This type of queries are named “Sequenced Route Queries” (SRQ) and their implementation could be feasible even in a mobile device as it is proposed and utilized by an android application in the current thesis. The algorithm used is the Iterative Doubling, an alternative to the EDJ (Enhanced Dijkstra - section 2.3.3) layered approach. The current approach helps to avoid exploring facilities that are far away from the starting point. The algorithm manages to reduce the computational cost of exploring every possible facility and therefore it performs better in case that we have to process local data. Realistic sequenced route queries mainly refer to such local geographical data. The application manages to exclude such distant facilities by setting an initial threshold that defines a range in kilometers. Also the user has as an option to choose between some initial ranges, depending on the minimum trip distance that he is willing to cover. With this threshold nodes of POIs without range does not take part during Dijkstra computations and so this fastens the running time. If the initial range although could not resume to an optimal path then the threshold is doubled and the algorithm is executed again. The data for the needs of the application were collected from OpenStreetMaps project and mainly concern mainly Attica. They represent several geographical points and each of them belongs to a respective category of interest such as hotels, restaurants etc. The basic data element keeps information about its geographic coordinates, the label that identifies the facility and its category. They are initially formed as xml separated files (per category) and they are utilized as node objects. Another advantage of the implemented algorithm is that it does not require the explicit construction of the graph that is built during each Dijkstra’s computation. The final outcome is a route with the minimum distance that passes through a point from each category.