Effective air traffic management (ATM) is crucial for ensuring the safety, efficiency, and sustainability of air travel. Traditional ATM systems, while capable of monitoring aircraft, often lack the capability to optimize aircraft trajectories, resulting in inefficient airspace usage and increased environmental impact. This paper introduces a novel approach utilizing the column generation algorithm for optimizing four-dimensional (4D) trajectories in ATM. Unlike previous methods, this approach incorporates an optimization method that simultaneously integrates multi-aircraft 4D trajectories with considerations for fuel efficiency, timing delays, and adjustments in aircraft altitude and speed. The column generation framework decomposes the 4D trajectory optimization problem into a master problem and subproblems. The master problem selects suitable 4D trajectories for aircraft, and subproblems generate new 4D trajectories. Computational results indicate that the framework gives high-quality solutions with very small provable optimality gaps in short run time, confirming the method’s effectiveness in enhancing real-time decision-making in ATM systems.