This paper introduces the new algorithm MOCAA* (Multi-Objective Context-Aware A*) Enhanced that is a new pathfinding algorithm that has been tested on 900,000 cases in 15 metropolitan regions and maintains classical optimality guarantees but uses machine learning pattern recognition. The hybrid admissible heuristics are novel in that they combine Graph Neural Network (GNN) and Multi-Layer Perceptron (MLP) models with mathematically rigorous minimum function optimization principles to ensure that learned approximations do not violate admissibility requirements that limited previous machine learning approaches. The GNN component learned topology-sensitive spatial features that would not be achievable with hand-crafted heuristics, and the MLP component is the only one with asymmetric loss functions that are extremely sensitive to overestimation. By using dynamic edge weighting solutions, the system takes into account the context-aware routing-based multi-objective optimization problem that prioritizes four distinct preferences: the shortest distance, the safest route, and the most economical options. A thorough analysis displays that there is significant improvement in performance. The computational nodes have reduced by 43.2%. They do so with 0.31% optimality gap and 96.8% admissibility rate. Statistical validation in different geographic areas shows that the results are significant (p < 0.001) and that the effect sizes are large (Cohen’s d > 1.4).