A Heuristic Approach to the Design of GPS Networks

This thesis deals with logistics of the satellite-based Global Positioning System (GPS) surveys. Heuristic techniques, within the field of Operational Research (OR), for hard Combinatorial Optimization Problems (COPs), have been applied to the design of GPS surveying networks. The aim of a COP is to search and determine the most suitable
solution for optimizing (minimizing or maximizing) an objective function (cost, accuracy time, distance etc) over a discrete set of feasible solutions. The designing of a GPS
network as a COP consists of set of feasible schedules and the goal is to determine the cheapest schedule. When related to GPS, a network can be defined as a set of stations which are co-ordinated by placing receivers on them to determine sessions between them.
A session can be defined as a period of time during which two or more receivers are simultaneously recording satellite signals. The required minimum number of receivers is two, and the problem of network designing becomes crucial as this number increases.
The problem addressed is to search for the best order in which these sessions can be organised to give the best schedule (minimal cost) to complete all sessions. In practice this means determining how each GPS receiver should be moved between the stations to be surveyed in an efficient manner taking into consideration some important factors such as time, cost etc. Exact methods can solve only small networks and are not practical as the
size of the network increases. Hence, it is important to have approximate techniques (heuristic techniques) which can provide an optimal or near-optimal schedule for large
networks in a reasonable amount of computational time.
In this thesis, new techniques of research based on effective computer based heuristic optimization techniques for the above mentioned problem have been researched, designed, developed, implemented and analysed theoretically and empirically. These heuristics, which are based on ideas from Artificial Intelligence (AI), are the most recent and
powerful development techniques applicable to a wide range of important problems which occur in a variety of disciplines, such as, statistics, engineering, mathematical
programming and operational research. A heuristic technique starts with an initial starting solution (within this context, an initial schedule). It iteratively attempts to improve upon the current schedule by a series of local improving changes (swapping sessions) generated
by a suitably defined mechanism until a stopping criterion is met.
The heuristics that have been implemented in this research are Local Descent Search(LDS), Simulated Annealing (SA) and Tabu Search (TS). The LDS method accepts only a schedule that generates a reduction in the objective function value. On the other hand, both SA and TS techniques combine different operational and organizational strategies based on
robustness and computer models in order to obtain high-quality schedules. Computational results for several case studies are presented for these techniques. Within the GPS surveying and OR literature, this is the first attempt of its kind to have been carried out.
The main contribution of this thesis is the development of the above heuristics for solving the GPS network logistics design problem. Their performance was investigated,
evaluated and compared with networks with known optimal schedule with respect to schedule quality and the computational effort. The new concept of a sessions-interchange mechanism was developed and implemented. To assist in the evaluation, tests were carried
out using two large and different types of networks observed in Malta and the Seychelles.
For both networks, the developed SA and TS techniques yielded high-quality schedules than those actually observed.
The main limitation with the SA method is the amount of computational time required.
This is considerably improved by the use of the sequential sessions structure. The use of a new cooling optimization scheme is developed and implemented to remedy the most time
consuming part of process, but the design of a network still needs higher computation times. It is concluded that the SA approach of finding the cheapest schedule for large
networks is time consuming. The superiority of TS has been proven both with respect to the GPS schedule quality and computational effort on large GPS networks.
For the GPS surveyor, it has been shown that the techniques developed can reduce significantly the cost of carrying out a GPS survey. As these techniques have both theoretical and practical interest, not only the best results have been reported, but some variants of these techniques have been proposed. This provides a strong motivation and
fertile opportunity for innovation in adapting heuristics for solving other practical surveying optimization problems where feasibility and good solutions are difficult to
obtain.

This thesis supplied via ROAR to UEL-registered users is protected by copyright and other intellectual property rights, and duplication of any part of the material is not permitted, except for your personal use for the purposes of non-commercial research and private study in electronic or print form. You must obtain permission from the copyright-holder for any other use. Electronic or print copies may not be offered, for sale or otherwise, to anyone. No quotation from the thesis may be published without proper acknowledgement.