Developing A Roundtrip Planner Using Openstreetmap Computer Science
To develop a roundtrip planner based on OpenStreetMap data that could serve as a comprehensive location guide for a tourist (or) visitor showing him places of interest in the location.Introduction and Motivation:
"A Geographical Information System (or) Geo-Spatial Information System (GIS) is a system that captures, stores, analyses, presents data that are linked to locations." [Wiki] OpenStreetMap is an open source GIS providing geographical data for free and accessible to all. It allows to use the data, edit the data and to build applications which would play a key role in serving the purposes like travelling, knowing information about places, states (or) provinces, countries etc.
Travelling and exploring new places is one of the hobbies which we can find in everyone's life serving their leisure, recreational, academic, family (or) with any business assignments. In the past, travel guide(s) and travel agencies have been the vital centres for providing the location information. But with the advent of digital information into tourism, the usability have greatly increased and can be efficiently used to quickly find the locality and nearest destinations.
Visitors (or) Tourists show interest in visiting the places of interest like historic buildings, modern architecture, pubs, parks, places of faith etc. By developing a roundtrip planner application for tourist suggesting Places of Interest in the city would reduce effort of an individual to plan and giving him the cheaper options available.
OpenStreetMap with a wide range of information about a place can be made use of building sophisticated applications, automating tasks for finding relevant information and decision-making, thus substituting the human effort.Objectives:
The prime objectives of the application include:
Implementing Travelling Salesman Problem in constructing a round-trip planner.
Designing Interactive Application and Graphical User Interface (GUI) providing options to the user and authorising the user. Supplying the user with the comprehensive details.2.2 Challenges:
Identifying Places of Interest and classifying the information to Leisure, pubs, restaurants and historic prominence.
Collecting the OpenStreetMap data about the places identified.
Studying Travelling Salesman problem.
To understand Heuristic Algorithms about Travelling Salesman Problem.
Understanding the OpenStreetMap data format, data primitives and extracting useful features of the map like street name, address, latitude and longitude coordinates etc.
Transforming OpenStreetMap extracted information into weighted graph.
Applying the Travelling Salesman Problem and analyzing the working of it with the graph constructed.
Understanding JGrpahT Java library.
Constructing a data structure for graph transformations.
Designing User Interface (UI) for the user to enter the constraints, preferences about the roundtrip.Requirements:3.1 Technical Requirements:
Platform: Java 1.6
Development Environment: Netbeans /Eclipse IDE
Data format: OpenStreetMap, XML.
APIs applicable: JavaOpenStreetMap (JOSM) v 0.6, JGraphT.3.2 Details of the Requirements:
The aimed roundtrip planner application is built using Java with the help of the development environments either Eclipse or Netbeans. The application would be stand-alone providing required information to the user.
The data to be traversed and transferred between the applications is done using XML and OpenStreetMap formats. (OpenStreetMap is also a data format built using XML)
Construction of graph from the OSM/XML can be done using the JGraphT API. JGraphT API is a predefined library of functions that is used to develop graph related objects from Java.
Using JGraphT, we can construct any type of graphs like directed, non-directed, weighted, non-weighted etc.
With JGraphT, transformations are possible and graphs can be developed from the data with different formats.
JOSM API v0.6 helps to retrieve the information from the OpenStreetMap database and also to retrieve relations between the OpenStreetMap data.
With the help of Java Abstract Window Toolkit (AWT), Graphical User Interface (UI) will be designed.Project Time plan:
Milestone - 1
( Data Structure)
Fig 1: Time plan TSP: Travelling Salesman Problem.
Planning is one of the important phases in the Project. The detailed time plan of the project is explained below:4.1 Literature Review:
Indicating the start of the project and to overcome the challenges in developing it, a deep and thorough research on background material has been done on the XML data and its primitives, also about OpenStreetMap data formats, travelling salesman problem. It also included collecting the GPX traces of places of faith etc. It gave the basic understanding and working of the OpenStreetMap and also details of the designing have been dealt in it. As OpenStreetMap is the collection of Geo-spatial data, collecting the GPS traces gave the working template and the importance of latitude and longitudinal coordinates for finding a place in the world.4.2 Preliminary Report (Week2):
Preliminary Report summarises the research background, aims, objectives, Schedule of the project and expected deliverables of the project.4.3 Analysing Simple Travelling Salesman Problem:
This phase primarily concentrates on the applying the simple travelling salesman problem over a graph, analysing it's working. By using the working solution, we potentially identify the complexity by applying it on the actual xml data. It helps giving a much better and precise idea of the actual application.4.4 Milestone-I (Week4):
Accomplishing the work and carrying it out based on the preliminary report, building a model and implementing it over a small amount of data from OpenStreetMap (For ex: consider Leicester City Centre) which leads to solution. In this phase, we also concentrate on using the necessary data structure for carrying out transformations.4.5 Design and Implementation:
The solution to the actual problem is being developed in this phase of the project. In this stage, the prime concentration is coming up with a feasible and optimal solution finding a roundtrip planner. The challenge of constructing graphs, working on the graphs exactly, retrieving information from OpenStreetMap and building a data structure by which the graph transformation between the different formats become feasible. The challenges of using JgrpahT library, JOSM v0.6 API will be handled.
A graph showing the distance travelled between two selected places of interest in compliance with the constraints of travelling salesman problem is being developed.
Also in this phase, we concentrate on developing a good user interface, where a user gets his authorisation and giving options to the user in expressing his/her own preferences about the trip like the opening hours of the places of interest, availability, modes etc.4.6 Interim Report (Week6):
At this juncture, the challenges of implementation will be handled; designing the User Interface will be initiated and also steps in optimising the travel planner.4.7 Milestone-II (Week7):
The challenges of the UI design, optimising the planner will be analysed and further refined, if needed. Deep analysis of the work done so far will be reviewed.4.8 Testing:
Checking the developed project for errors and estimating the developed project in terms of it working, accuracy and performance. The metrics would be satisfying the requirements/preferences of the user.4.9 Submission Draft-I (Week10):
It the second last step of the project and a detailed draft of the work done are submitted including the important task accomplished etc for the final revision.4.10 Final Submission (Week13):
This is the final submission of the work done concluding the project. All the deliverables, code, accomplishments are submitted.Risks:
Identifying and protecting from risks is also equally important phase of the project.
The primary risk of the project will be the accuracy and the optimization of the roundtrip planner. The other risk involved is the backing of the data that can be done by using the svn (subversion) regularly.
Article name: Developing A Roundtrip Planner Using Openstreetmap Computer Science essay, research paper, dissertation