The scheduling of air transport capacity by a mail distribution center involves fixed capacity and alternative capacity. This study establishes an optimization model to minimize transportation costs under the premise of sufficient air transport capacity and proposes an improved crow search algorithm. First, depending on the mathematical model of the problem, the penalty function method is employed to convert some constraints into penalty terms which then form a fitness function together with the objective function. Second, the Logistic chaotic map is utilized to improve the diversity of the initial population. In addition, considering the characteristics of the problem, the study proposes a location update strategy based on the individual optimal follow mechanism and the sine-cosine algorithm. Finally, a cross-mutation mechanism is introduced to enrich population diversity in the search process. The effectiveness and superiority of the algorithm are proved by a large number of cases.