Back to the program.
Metaheuristics for GPS Surveying Network Design
Hussain Aziz Saleh
IRIDIA
Université Libre de Bruxelles
Brussels, Belgium
hsaleh@ulb.ac.be

Abstract

The satellite-based Global Positioning System (GPS) has an impact on all related fields in geoscience and engineering, in particular, on surveying work in determining locations and changes in locations within short observational periods and over long distances with unprecedented accuracy. On other hand, the complexity of observing GPS networks increases with their size and become highly difficult to solve effectively. The network in GPS can be defined as a number of stations which are co-ordinated by placing receivers on them to determine sessions between them. The problem is to search for the best order in which these sessions can be organised to give the best schedule of minimal cost to observe all sessions. Exact algorithms can solve only small networks and are not practical as the size of the network increases. Hence, it is crucial to have approximate techniques which can provide an optimal or near-optimal schedule for large networks in reasonable amount of computational time. Computational results are presented to show the effectiveness and performance of the developed Simulated Annealing and Tabu Search metaheuristic techniques with respect to schedule quality and the computational effort using different types and sizes of GPS networks. Other metaheuristics such Ant Colony System could explore the solution space more effectively and provide good results.

Keywords

Global Positioning System (GPS), Metaheuristics, Network, Simulated Annealing, Tabu Search, Ant Colony System.

References

  1. A. Leick. (1995) GPS Satellite Surveying. Wiley, Chichester, UK. 2nd edition.
  2. P. Dare and H. Saleh. (2000) GPS Network Design: Logistic Solution using optimal and near-optimal methods, Journal of Geodesy, 74:467-478.
  3. H. A. Saleh. (1999) A Heuristic Approach to the design of GPS Networks. Ph.D. Thesis. School of Surveying, University of East London, Dagenham, Essex, UK.
  4. H. Saleh and P. Dare. (2001) Effective Heuristics for the GPS survey Network of Malta: Simulated Annealing and Tabu Search techniques, Journal of Heuristics, 7(6):533-549.
  5. M. Dorigo, V. Maniezzo, and A. Colorni. (1996) The ant system: Optimization by a colony of cooperating agents, IEEE Transactions on Systems, Man, and Cybernetics-Part B, 26(1):29-41.