In view of an improvement of the tourism service competitiveness, the backward integration of tourism service integrators has been adopted by online travel agencies for improving tourism service quality. However, due to the cost disparity between the two backward integration strategies of self construction and mergers and acquisitions (M&A), the way for a maximization of the integration of tourism resources in multiple tourism destinations becomes an urgent issue for online travel agencies. By constructing a backward integration model of online travel agencies with cost constraints taken into consideration, an improved genetic algorithm solution model is designed on the basis of the hill climbing algorithm, followed by an analysis of the integration strategies of online travel agencies in each tourism destination under different cost constraints by a numerical simulation. The results show that the marginal revenue of online travel agencies decreases with the increase of input integration cost, which makes it necessary for online travel agencies to determine the cost input so as to avoid the capital waste; the improved genetic algorithm is characterized with a better optimization performance than the traditional genetic algorithm.