School of Electrical and Computer Engineering, NTUA
- Contact person: Yannis Stavrakas
Abstract. The scope of this thesis was to develop an application to group addresses based on their coordinates and on a series of constraints and then classify them. The thesis was developed to solve a problem of EL.STAT. (Hellenic Statistical Authority). The EL.STAT. conduct regular surveys. In every survey surveyed are allocated among a number of surveyors. The developed system facilitates the attribution of the surveyed to surveyors and suggests a path for each surveyor bearing in mind his preferences in terms of number of surveyed and location. Specifically, ways of finding the addresses' coordinates were studied. The application uses the Google Geocoding API. Then, the problem of clustering addresses was studied. A map was used for the dynamic assignment of surveyed to surveyors. The proposed route was carried out by Christofides algorithm, which solves with 3/2 approximation the travelling salesman problem. The application implemented can be used to solve problems similar to that of EL.STAT. For example in the position of the surveyors may be trucks and in the position of the surveyed may be shops.