To handle the increasing air-traffic demand, the world's major air traffic management systems are being transformed towards the trajectory-based operation concept that enables us to shift the conflict detection and resolution task to the strategic planning level. In this work, we present an efficient methodology to address such strategic 4D trajectory planning. In reality, when an aircraft flies on its trajectory, there can be uncertainty on the curvilinear abscissa due to external events (wind, connected passenger delay, etc.). Therefore, in addition to ensuring the separation of aircraft in the 3D space domain, the minimum time separation between trajectories must be also taken into account. To ensure such a separation between trajectories, the approach proposed in this work allocates an alternative route, an alternative departure time, and an alternative flight level to each participating flight. This route / departure-time / flight level allocation problem is formulated under the form of mixed-integer optimization problem. The objective is to minimize the total number of interactions (occuring when multiple trajectories occupy the same space at the same period of time) between trajectories during a full day of traffic over France. A hybrid-metaheuristic optimization algorithm is developed in order to solve this high combinatorics problem (national-scale context, involving more than 8,000 flights) The proposed methodology is successfully implemented and tested on a full-day simulated air traffic over the French airspace, yielding to an interaction-free trajectory plan.