University of houston clear lake
Download 112.71 Kb.
|
- Navigate this page:
- 2. Software Requirement Specification
- 3. SOFTWARE REQUIREMENTS
- 4. Technical Details
- 4.3 XML
- 5. Design implementation
- 6. SYSTEM ARCHITECHTURE
- Implementation on GUI
- 10. LIMITATIONS and future directions
- 11. TESTING
- 12. CONCLUSION
- 13. REFERENCES
- 14. Appendices
- 14.2 Appendix B - Major tasks and contribution
- 14.2 Appendix C –ScReen Shots
|
Application for Travelling Salesman Problem (TSP) on Android Mobile Operating System CSCI 6838- Spring 2010 
UNIVERSITY OF HOUSTON CLEAR LAKE Instructor and Mentor Dr. Alfredo Perez-Davila Team Members Shravani Reddy Tappati Tejasri Yelamanchili Divya Karukonda Nikunj Tibdewal Project Website: http://dcm.uhcl.edu/caps10g4/home.html Semester: Spring 2010 report date: 30 april 2010 Acknowledgement Our sincere thanks to Dr. Perez Alfredo Davila for giving us effective and valuable guidance that motivates us to strive for the completion of Android project. We heart fully thank him for sharing knowledge and for all the constructive feedback during weekly mentor meetings which helped us better understand the project goals. We are grateful for his continues support, guidance and encouragement throughout the project. We would also like to thank our friends and all those people who were directly or indirectly involved in this project. ABSTRACT Android is the first complete, open and free mobile platform. It is developed by the Open Handset Alliance, which is formed by a group of 30 technologies and mobile companies. It is supported by Google and this project uses a Google Android Mobile SDK for testing an application. The aim of our project is to develop an Android mobile application to solve a classical problem called as “Travelling Salesman Problem (TSP)”. To solve this TSP problem we implemented “Android Mobile Application for TSP” for Google G1 development phone using Android platform. The application allows the user to enter multiple locations that salesman interested to visit and it finds the optimized route between entered locations and displays it on the Google map with travelling directions.
4.1 Java Eclipse 3.5…………………………………………....................10 4.2 Google Android SDK 1.0……………………………….....................10 4.3 XML…………………………………………………………….........10 4.4 Windows XP (32-bit) or Vista (32- or 62-bit) ……………………….10 4.5 Other Requirements…………………………………………………..10 5. Design & Implementation…………………………………………………11 5.1 Assumptions………………………………………………………….11 5.2 Constraints…………………………………………………………...11 6. System Architecture……………………………………………………….12 7. Design Details……………………………………………………………..13 7.1 Use Case Diagram…………………………………………………....13 7.2 Class Diagram………………………………………………………..14 7.3 Sequence Diagram……………………………………………………15 7.4 Design of the Application…………………………………………….16 8. Implementation on GUI……………………………………………………17 9. What we learnt……………………………………………………………...18 9.1 Issues faced…………………………………………………………...18 10. Limitations and Future directions…………………………………………19 11. Testing……………………………………………………………………..20 12. Conclusion…………………………………………………………………21 13. References…………………………………………………………………22 14. Appendices………………………………………………………………...23 14.1 APPENDIX A- Project Management………………………..............23 14.2 APPENDIX B-Major Tasks & Contribution………..........................26 14.3 APPENDIX C-Screen Shots ………..................................................31 14.4 APPENDIX D –Acronyms, Abbreviations, Glossary........................45 INTRODUCTION
This Project uses the Google Android Platform to develop the mobile application where the user can enter different addresses and find the shortest route. The main objective of the project is that the Google map plots out a route if there are only two addresses i.e. source and destination address and gives an estimated travel time. But if it includes multiple points, the user has to specify the sequence of locations himself before Google map can give a route. The application will use Google maps to plot the locations and helps in choosing the shortest path.
Interesting thing about the application is, it facilitates the users, displaying the shortest route for a set of given addresses, where such option is not available with Google maps. This mobile application benefits the user by saving gas and time so that the user can choose the shortest route and save his time. It is user friendly. 2. Software Requirement Specification2.1 Problem definition The aim of this project is to develop an Application on Android Mobile operating system. This is a Mobile Application on G1 phone which works on Android Operating System developed in JAVA Eclipse. We used the Travelling sales person Algorithm for the development of this Application. This Application should be used real-time and this work should also enable the user to find an optimal path when he/she enters a set of desired destinations. This application aims, to find the optimal path. Project should be extendible such that it can be used for other domains in the future. 2.2 Overview Most of us have visited Google Maps (www.maps.google.com) Website. Our application is based on similar concepts. But, here we generate the shortest path. This is the major difference. There are a number of customized Google Map applications that have been developed according to the need of different users and our application is a similar one. 2.2.1 Introduction to Android Android is a software stack for mobile devices that includes an operating system, middleware and key applications that uses a modified version of the Linux kernel [1]. Android Inc developed Android. This Firm was later purchased by Google and then by the Open Handset Alliance. Android allows the developers to write code in the Java language, controlling the device via Google-developed Java libraries. We used the Google Android 1.1 for the development of our Application. 2.2.2 Implementation of the Algorithm The Travelling sales person problem is NP hard and NP complete. There are n! Possible routes when a user starts from a location and travels n locations. So, therefore when we are finding the shortest path between those n locations, we call the Google maps square (n) times. But instead of this we assume that two locations are geographically closer and hence the Google maps API calls only once for the positions of the locations i.e., latitude and longitude which would reduce the no of calls. We used the Nearest Neighbor (NN) Algorithm which is a greedy algorithm. This algorithm first selects the location which is not visited, and then it calculates the distance between all the locations and the location which was initially selected. Similar process continues while it calculates the distance between all the nearest locations which are not visited and all the remaining locations. There are several other algorithms which can be used, but we selected the Nearest Neighbor (NN) Algorithm because of its performance and it is less complex compared to the other Algorithms. 3. SOFTWARE REQUIREMENTS3.1 Operating environment
3.2 Dependencies
3.3 User Classes and Characteristics Mobile application for TSP should cater to the following user classes.
4. Technical DetailsThis section will details the technologies used to built this application and the rationale for deciding on the technologies compared to the alternatives. 4.1 Java Eclipse 3.5
4.2 Google Android SDK 1.0
4.3 XML
4.4 Windows XP (32-bit) or Vista (32- or 62-bit):
4.5 Other Requirements
5. Design & implementationAll of the assumptions and constraints that were considered during the design of the application are provided here in this section. 5.1 Assumptions
5.2 Constraints
6. SYSTEM ARCHITECHTURE
Figure (1): System Architecture Diagram 7. Design Details7.1 Use Case Diagram  Diagram (1): Use case Diagram for Android Mobile Application for TSP
7.2 CLASS DIAGRAM 
Diagram (2): Class diagram for the Travelling sales person application. 7.3 SEQUENCE DIAGRAM: 
Diagram (3): Sequence diagram 7.4 Design of the Application Description: Our application uses the Google Maps API to plot the route. Once the user starts the application, he/she has an option for entering the addresses. When the user submits his/her request, the information is requested from the web data sources, which returns the data in XML format. The data obtained is plotted on the Google Maps using pins. In order to use this application, the User should have a mobile phone which runs on Android Mobile Operating System, with an active internet connection. Also the web server of the data source should be up and running as data is retrieved from it once the user uses this function. At any point of time only one search can be performed on the map. The search should include valid addresses.
We developed a graphical user interface for the travelling sales person problem on android mobile operating system. This GUI is successfully accepting a number of valid addresses as input and generating an optimal route. The number of locations can be added dynamically as per the requirement of the user. This is possible using the add location button. When the user enters a valid address and clicks on the show map button an optimal route is generated. getLatitude( ) and getLongitude( ) are used for the generation of the path. When the user enters the address of his desired locations these are converted in to latitude and longitude. Then the route is calculated using the androids location class and the final map is displayed.
Being a project team we learned following lessons,
This project provided us a platform to learn various new technologies. This was an excellent learning experience. Team work, Time management, Team spirit are the most important things without which any project could not be completed efficiently. 9.1 Issues Faced
10. LIMITATIONS and future directionsUser has to enter a valid address as input. If the user enters an invalid address the nearest location is selected by default. This is done automatically, while the User is not prompted. A valid button can be added and the input address can be validated. Auto fill can be added sparing the user from entering a complete valid address. This would make the application much more user friendly. Our application is generating a reasonable optimal path, but this is not the best path. This is because of the NP nature of the problem. For the development of the application in the future we would recommend heuristic algorithm. 11. TESTINGSoftware testing is an investigation conducted to provide stakeholders with information about the quality of the product or service under test [1]. Our Application was tested thoroughly in all the phases to provide a quality output, fulfilling all the requirements. We conducted various testing techniques like Black box testing, Negative Testing and White Box testing on the application. The team tested the entire application with different inputs thoroughly. We gave different input destinations and the final output came out as desired, meeting all the requirements. Every module developed was rigorously tested to ensure that the module provides the accurate results. All the team members tested the entire application to make sure it meets all the specifications and that it works as intended. 12. CONCLUSIONOur Application can be used real-time and this work enables the user to find an optimal path when he/she enters a set of desired destinations. The application is able to find an optimal path successfully meeting the requirements of the project. All the requirements are met and the application is working as intended. Next capstone team can work with the existing version of TSP app to enhance its features. In conclusion, we had a wonderful experience working on this project and this also proved to be a very good learning experience for all the team members, taught us how to maintain the team spirit and coordination by setting the goals and meeting the challenges in time. 13. REFERENCESThe following references have been used in order to understand the underlying technologies used in developing this prototype.
14. Appendices14.1Appendix A- Project Management & TEAM INFORMATIONTeam Leader (Shravani Reddy Tappati): The Team Leader is responsible for organizing the team work, progress and satisfying mentor and professor requirements. The team leader along with the project members and mentor of the project decides on the timeline for each and every task related with the project. Webmaster (Shravani Reddy Tappati): The Webmaster is responsible for maintenance of the Project Web site. It is the Webmasters responsibility of upload all the documents, the latest updates and progress of the project in the website. Programmers (Nikunj, Tejasri, Shravani and Divya): The primary duty of a programmer is to develop computer programs. The computer programmer may perform various tasks like the development of architecture of the classes in conjunction with others, establishing a coding standard for the project, and guiding the coding efforts of other team members. Technical Writer (Nikunj, Tejasri, Shravani and Divya): The Technical Writer is responsible for the documentation of the project. This involves documents such as Software Requirement Specifications, Design documents, and Final report, meeting minutes. To create a technical document, a technical writer gathers information by studying existing material and also gathers information from all the team members ensures that these were well documented. Testing (Tejasri, Shravani and Nikunj): Software testing is an activity aimed at evaluating an attribute or capability of a program or system and determining that it meets its required results. This is one of the most important phases of the project. All the team members are involved in this phase. Project timeline 
TEAM DETAILSShravani Reddy Tappati: Email address: tappati@uhcl.edu Cell Phone: 612-812-1879 Major: Computer Science Student Id: 0865804 Role: Team Lead/Webmaster/Programmer/technical writer Tejasri Yelamanchili Email address: yelamanchilit8554@uhcl.edu Cell Phone: 832-298-9795 Major: Computer Science Student Id: 0859126 Role: Architectural Designer/Research and development/Programmer Divya Karukonda Email address: karukondad9030@yahoo.com Cell Phone: 702-217-8078 Major: Computer Science Student Id: 0866358 Role: Research & Development/ Technical writer/Programmer Nikunj Tibedwala Email address: tibdewaln9188@uhcl.edu Cell Phone: 832-630-4814 Major: Computer Science Student id: 0865799 Role: Research & Development/Programmer/Technical writer 14.2 Appendix B - Major tasks and contributionContribution
DESCRIPTION OF MAJOR TASKS PERFORMED BY EACH MEMBER Shravani Tappati: Team Leader, Web Master, Programmer and Technical writer.
Plays the role to identify the project tasks and distribute the tasks evenly among the team, organize and monitor team meetings and communicate with the instructor and mentor regarding the progress of the project.
In the role of a programmer the tasks involved were to setup the environment required to develop, run and test the application, coordinate with other programmers in the team and develop the modules assigned. Testing and debugging was also done in coordination with other team members.
Webmaster for the project to update the documents and maintain the website. The website can be viewed at http://dcm.uhcl.edu/caps10g4/about.html
Technical writer worked on documenting the requirements, design and implementation of the application. Communication with all members of the team as well as the team mentor was done and the information provided by them was used to detail the tasks performed. Tejasri Yelamanchili: Architectural Designer, Programmer and Technical Writer
Involved in the architectural design of the project and used the set of requirements gathered by the team and developed models and diagrams for designing the architecture of the application. She designed the structure of classes and user interface.
In the role of a programmer the tasks involved were to setup the environment required to develop, run and test the application, coordinate with other programmers in the team and develop the modules assigned. Testing and debugging was also done in coordination with other team members.
Technical writer worked on documenting the requirements, design and implementation of the application. Communication with all members of the team as well as the team mentor was done and the information provided by them was used to detail the tasks performed. Divya Karukonda: Research and Development, Programmer, Technical Writer.
Research and development is mainly working on the ground work of the project. It involves the gathering of information regarding the application, technologies to be used for the development of the application. The development of the project is not possible without a proper research. She is responsible for the Algorithm used to develop the application.
In the role of a programmer the tasks involved were to setup the environment required to develop, run and test the application, coordinate with other programmers in the team and develop the modules assigned. Testing and debugging was also done in coordination with other team members.
Technical writer worked on documenting the requirements document and final report of the application. Communication with all members of the team as well as the team mentor was done and the information provided by them was used to detail the tasks performed. Nikunj Tibedwala: Research & Development, Programmer, Technical Writer.
Research and development is mainly working on the ground work of the project. It involves the gathering of information regarding the application, technologies to be used for the development of the application. The development of the project is not possible without a proper research. He is responsible for the Algorithm used to develop the application.
In the role of a programmer the tasks involved were to setup the environment required to develop, run and test the application, coordinate with other programmers in the team and develop the modules assigned. Testing and debugging was also done in coordination with other team members.
Technical writer worked on documenting the requirements, design documents of the application. He is responsible for the use case diagrams. Communication with all members of the team as well as the team mentor was done and the information provided by them was used to detail the tasks performed. 14.2 Appendix C –ScReen Shots
Directory: caps10g4 caps10g4 -> Software requirements specification caps10g4 -> Software Design Document On Android Application for Travelling Salesman Problem (tsp) Submitted By Download 112.71 Kb. Share with your friends:
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||
