As a challenging problem of the upcoming next-generation networks, multi-constrained quality-of- service routing (QoSR) is to find a feasible path that satisfies the multiple constraints simultaneously. For the NP complete problem, the heuristic SA_MCP by applying the simulated annealing to Dijkstra’s algorithm is proposed. SA_MCP first uses a non-linear energy function to convert multiple QoS weights to a single metric and then seeks to find a feasible path by simulated annealing. This paper overviews the simulated annealing method and analyzes the issues when it is applied to QoSR. Extensive simulations show the following conclusions: (1) SA_MCP has a high performance w.r.t. routing success ratio. (2) It has a good scalability in both network scale and weight number k. (3) It is insensitive to the distribution of QoS constraints. Furthermore, when most QoS requests are feasible, the running time of SA_MCP is about O(k(m+nlogn)), which is k times that of the traditional Dijkstra’s algorithm.