For industrial gas providers, fleet planning is important to their financial and operational performance. This article considers long-term vehicle purchase decisions, medium-term vehicle relocation decisions, and short-term rental decisions that are useful for increasing flexibility to meet time-varying demand. A mixed-integer programming model is developed to minimize total distribution costs and fleet investment costs over multiple time periods and multiple depots. To solve the industrial-sized problem efficiently, a two-phase approach is proposed. In Phase I, routes are generated to capture the characteristics of typical gas delivery operations. A reduced model is solved to select routes for meeting customer demands, estimate distribution costs, and determine the preferred fleet size. Phase II addresses the trailer purchase, relocation, and rental decisions based on the outputs of Phase I. The numerical studies, conducted using a data set from a leading industrial gas company, demonstrate the effectiveness and efficiency of the decomposition approach. Different routing algorithms are compared to evaluate the impact of candidate routes. When compared with the integrated optimization model, the two-phase approach obtains quality solutions within reasonable computational time.