In this paper we propose solution metaheuristics for the integrated fleet sizing and replenishment planning problem based on the problem space search approach utilizing fix and optimize algorithm. The problem is about deciding both the composition of a fleet for distributing a single item and the replenishment planning based on a predetermined delivery frequency. This problem integrates two important logistical issues namely fleet sizing and replenishment planning. The objective is minimizing all relevant costs composed of vehicle ownership, inventory, and approximate routing costs. We suggest two heuristics based on the problem space search. These heuristics rely on both perturbing data and perturbing the sequence of subproblems in the fix and optimize algoritm. We show the effectiveness of the proposed solution methods on a set of fairly large size randomly generated problems.