We describe a problem of optimal planning for unmanned vehicles and illustrate two distinct procedures for its solution. The problem under consideration, which we refer to as the search tour problem, involves the determination of multi-stage plans for unmanned vehicles conducting search operations. These types of problems are important in situations where the searcher has varying performance in diﬀerent regions throughout the domain due to environmental complexity. The ability to provide robust planning for unmanned systems under diﬃcult environmental conditions is critical for their use in search operations. The problem we consider consists of searches with variable times for each of the stages, as well as an additional degree of freedom for each stage to select from one of a ﬁnite set of operational conﬁgurations. As each combination of conﬁguration and stage time leads to a diﬀerent performance level, there is a need to determine the optimal conﬁguration of these stages. When the complexity of constraints on total time, as well as resources expended at each stage for a given conﬁguration, are added, the problem becomes one of non-trivial search eﬀort allocation and numerical methods of optimization are required. We show two solution approaches for this numerical optimization problem. The ﬁrst solution technique is to use a mixed-integer linear programming formulation, for which commercially available solvers can ﬁnd optimal solutions in a reasonable amount of time. We use this solution as a baseline and compare against a new inner/outer optimization formulation. This inner/outer optimization compares favorably to the baseline solution, but is also amenable to adaptation as the search operation progresses. Numerical examples illustrate the utility of the approach for unmanned vehicle search planning.