Looking Ahead with the Pilot Method

摘要

The pilot method as a meta-heuristic is a tempered greedy method aimed at avoiding the greedy trap by looking ahead for each possible choice (memorizing best results). Repeatedly a master solution is modified; each time in a minimal fashion to account for best choices, where choices are judged by means of a separate heuristic result, the pilot solution. The pilot method may be seen as a system for heuristic repetition. As usually a higher time complexity is associated with repetition, we propose policies to reduce the running times, while retaining an enhanced solution quality. While the basic idea of the pilot method was developed to account for feasible solutions of enhanced quality one may also in-corporate these ideas, e.g., into local search and tabu search hybrids. In this paper we briefly survey the pilot method and re-lated ideas such as the rollout method and provide numeri-cal results for some well-known combinatorial optimization problems. Experiments show that the pilot method can be competitive in a head to head comparison with well-known and accepted meta-heuristics.