Because of the rapid and continuous developments in the GPS technology it has been necessary to find an economical method of using it. Especially in designing GPS surveying networks where the time required to make the necessary observations to the satellites reduces, so the need for an efficient schedule increases. To accomplish this task, a new research based on the heuristic techniques within the field of Operational Research (OR) for hard Combinatorial Optimization Problems (COPs) have been applied to the design of a GPS surveying network. The designing of a GPS network as a combinatorial problem consists of set of feasible schedules and the goal is to determine the cheapest schedule. Exact algorithms can solve only small networks and are not practical as the size of the network increases. Hence, it is important to have heuristic techniques which can provide optimal or near-optimal schedule for large networks in reasonable amount of computational time.
A heuristic technique, which is based on ideas from Artificial Intelligence (AI), is an approximate procedure for quickly identifying a high-quality solution for a given problem. This technique starts with an initial starting solution (within this context, an initial schedule). It iteratively attempts to improve upon current schedule by a series of local improving changes (swapping sessions) generated bu a suitably defined mechanism until a stopping criterion is met. The fundamental concepts of any heuristic consists of: representation and construction of initial solution; generation of neighboring solutions; acceptance strategy and stopping criterion.
Heuristic techniques differ in the way choices are made at each step of the above general framework. They are divided into several types, for example; Local Descent Search (LDS); Simulated Annealing (SA); Tabu Search (TS); Genetic Algorithms (GAs). The first one is based on the concept of exploring the vicinity of a current solution. The second derives from physical science, more specially from statistical mechanics. The third stems from the general tenets of intelligent problem solving. The last one is inspired by principles derived from biological sciences. The main contribution of this reserach 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 solution with respect to solution quality and the computational effort. To assist in the evaluation, tests were carried out using two large and different types of networks obserevd in Malta and the Seychelles.
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 interests, 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. Within the GPS surveying and OR literature, this is the first attempt of its kind to have been carried out.
