The development of sound routing strategies for dynamic traffic routing is a complex task that requires the use of an automated traffic-routing decision support system (DSS). In this study, heuristic search algorithms were used to build prototype DSSs for on-line traffic routing. Specifically, two DSSs were developed for a real-world highway network: the first was developed by using simulated annealing ( SA) and the second was constructed by using genetic algorithms (GAs). The use of such algorithms allows more accurate modeling of traffic dynamics than is possible by traditional analytical techniques. To evaluate and compare the performances of the developed DSSs, a test set consisting of 10 randomly generated problems was used. Results demonstrated that the DSSs are capable of yielding high-quality solutions in a reasonable amount of time. In addition, for on-line traffic routing, SA tends to perform better than GAs.