This paper proposes a heuristic function for multi-criteria route planning problems. The Analytical Hierarchy Process (AHP) is used for the multi-criteria aggregation process both for actual and heuristic cost functions. Travel distance, travel time, safety and fuel consumption are considered to be the selected criteria. Additionally, while considering real data sets, road safety and fuel consumption models are developed. The proposed multi-criteria heuristic function is consistent; therefore, the A* algorithm finds optimal routes. The proposed algorithm is tested and compared with existing algorithms in the literature using a real dataset for a specific region in Eskisehir, Turkey.