Considering the transformation in roles of existing air traffic management technologies, future flight operations and flight deck systems will need additional avionics and operational procedures that involve adaptive algorithms and advanced decision support tools. The main purpose of this article is to provide a theoretical framework for tactical 4D-trajectory planning and conflict resolution of an aircraft equipped with novel automation tools. The proposed 4D-trajectory-planning method uses recent algorithmic advances in both probabilistic and deterministic methods to fully benefit from both approaches. We have constructed an aircraft performance model based on Base of Aircraft Data 4 with high-level hybrid flight template automatons and low-level flight maneuver automatons. This multi-modal flight trajectory approach is utilized to generate cost-efficient local trajectory segments instead of solving complex trajectory-generation problems globally. The proposed sampling-based trajectory planning algorithm spatially explores the airspace and provides proper separation through local trajectory segments and guarantees asymptotic optimality under certain conditions. Moreover, we have integrated the cross-entropy method, which transforms the sampling problem into a stochastic optimization problem, rapidly converges on the minimum cost trajectory sequence by utilizing available flight plans, and reduces the amount of sampling. The integration of the proposed strategies lets us solve challenging, real-time in-tactical 4D-trajectory planning problems within the current and the envisioned future realm of air traffic management systems.