This paper discusses a unique formulation of en-route flight planning problem in a constrained airspace with the objective of minimizing the total cost while all safety rules are respected. A mixed integer programming (MIP) model that considers mid-air collision avoidance, separation distance between aircrafts, speed changes, speed-dependent fuel consumption rate and exact traveling times has been developed using a non-time indexed modeling approach. A 3-dimensional (3D) mesh network is used to provide alternative routing options for aircrafts. The MIP solution provides a en-route flight plan as a list of consecutive nodes to be visited by an aircraft, time of arrival at each node and average speed on each link. Consequently, the cost incurred from delays, earliness and fuel usage is minimized. Fuel consumption is modeled as a function of aircraft speed without loosing the linearity of the mathematical model. The proposed non-time indexed model guarantees separation distances between aircrafts and ensures the mid-air collision avoidance during flight, particularly around airports. The MIP model is NP-hard. While only small to medium size problems can be solved using CPLEX on a personal computer, a real-time decision making capability is achieved through decentralized and hybrid solution strategies.