For air express service providers offering various express delivery services such as overnight delivery and next-business day delivery services, establishing quickly cargo loading plans is one of important issues owing to the characteristics of air express business, i.e., a short amount of time is available to complete all cargo loading operations before flight departure after receiving air express containers, pallets and bulks. On the other hand, one of major concerns in the air cargo loading planning is to make a plan that insures the stability of an aircraft to avoid take-off, flight, and landing accidents. To this end, this paper considers an air cargo loading planning problem, which is the problem of determining locations in the aircraft cargo space where air containers, pallets and bulks to be loaded while insuring the aircraft stability, motivated from DHL and Air Hong Kong. The objective of the problem is to maximize the total revenue gained from loading air express containers, pallets and bulks. To solve the problem, this paper suggests a simulated annealing algorithm to overcome impracticality of the integer programming model developed by a previous study requiring excessive computation time. The results of computational experiments show that the heuristic algorithm is a viable tool for establishing express cargo loading plans as giving robust and good solutions in a short amount of computation time. Scenario analyses are performed to investigate the effect of the current activities of air express carriers on the revenue change and to draw practical implications for air express service providers.