Recently, the Vehicular Ad hoc Networks (VANETs) have been gaining a lot of importance to improve road safety to ensure the comfort of car drivers. These networks need an infrastructure that is robust with channels of communication that are efficient and effective protocols of routing. The VANETs have become a very challenging area of research since they have certain specificities in identifying ideal strategies for routing and making sure the challenge of quality of service is met. There is a Quadratic Assignment Problem (QAP), which is another challenging issue in combinatorial optimization. For obtaining results that are satisfactory within a reasonable time frame, several heuristic algorithms are applied. One among them is the algorithm known as the Simulated Annealing (SA). The proposed algorithm called the slow heat SA is based on Road-Based using Vehicular Traffic-Reactive (RBVT-R) and modified SA. The results of the experiment have proved that the proposed method achieves better performance in terms of packet delivery ratio and the end to end delay when compared to the Geographic Source Routing (GSR), RBVT-R, and SA routing protocol.