Free Route Airspace (FRA) permits users to freely plan routes between defined entry and exit waypoints with the possibility of routing via intermediate waypoints, which is beneficial to improve flight efficiency. Dynamic management of sectors is essential for the future promotion of full-time FRA applications. In this paper, considering the demand uncertainty at the pre-tactical level, we construct an FRA complexity indicator system and use the XGBoost algorithm to predict the ATC workload. A two-stage sector boundary optimization method is proposed, using Binary Space Partition (BSP) to generate sector boundaries and an A*-based heuristic algorithm to automatically tune them to conform to the operational structure and “direct to” characteristics of FRA. Finally, this paper verifies the effectiveness of the proposed method for balancing ATC workload in a pre-designed Lanzhou FRA in China.