[devit]

It's probably not done due to political reasons.

Most of the complication is probably accidental, due to history or human traditions.

From first principles, the problem is obviously straightforward to formulate (assign nonoverlapping regions of spacetime to aircraft containing their position and destination, that they can maneuver in and such that the travel time is approximately optimal).

Applying simplifying constraints to the form of the regions (e.g. a discrete set of departure slots and fixed takeoff/landing envelopes, a route that follows the optimal trajectory in latitude/longitude plus a discrete lateral offset, discrete set of altitudes that change only at route crossings), it should be possible to reduce to a discrete optimization problem solvable in linear time.

[namaria]

"assign nonoverlapping regions of spacetime to aircraft containing their position and destination, that they can maneuver in and such that the travel time is approximately optimal"

Very 'draw the rest of the owl'. If you handwave any harder, you'd need ATC to bring you down to Earth.