The pilot method: A strategy for heuristic repetition with application to the Steiner problem in graphs

Abstract

As a metaheuristic to obtain solutions of enhanced quality, we formulate the so-called pilot method. It is a tempered greedy method that is to avoid the greedy trap by looking ahead for each possible choice (memorizing the best result). Repeatedly, a so-called master solution is modified, each time in a minimal fashion to account for the “best” choice, where all choices have been judged by means of a separate heuristic result, the “pilot” solution. We apply the method to the well-known Steiner problem in a weighted graph, that is, the problem is to determine a subgraph of minimum total weight spanning a set of given vertices. The pilot method may be seen as a system for heuristic repetition. As a higher time complexity order is usually associated with repetition, we propose policies to reduce the running times, while retaining an enhanced solution quality. Where possible, to encourage application of the pilot method to other combinatorial problems, we formulate in general terms. © 1999 John Wiley & Sons, Inc. Networks 34: 181–191, 1999