This paper studies the flight path planning problem for a large-scale air traffic management (ATM) system. The goal is to find the optimal 4D path plan, represented by a sequence of waypoints and the corresponding time stamps, for each individual flight subject to weather and sector-capacity constraints of the overall system. We decompose the overall functionality of the ATM system into two interactive stages: traffic regulation and performance optimization. In the first stage, the ATM system, based on the existing flight plans, sets up traffic rules, namely, decides which sectors are still open to use over each future time slot, while in the second stage it optimizes the path plans for new flights subject to these traffic rules as well as the weather constraints. Through this decomposition, the performance optimization task can be done in a fully decentralized way and can be easily solved using dynamic programming. Such a decentralized strategy can handle a large number of flights, respects the structure of the current ATM system, and has a great potential to improve its performance with safety guarantees. The proposed algorithm is validated through a simulation based on real traffic data over the entire US airspace.