The two most prominent link state routing protocols used for intra-domain routing are the Open Shortest Paths First (OSPF) and Intermediate System to Intermediate System (IS-IS) protocols. For different topologies and weight changes these protocols are easily updated to adjust the path between source and destination. However, it is computationally hard to obtain link weights that optimize network performance for a given topology and traffic situation. Furthermore, it is even more difficult to take into account, variations and uncertainty in the traffic demands. In this paper we study search heuristics for determining a set of OSPF/IS-IS link weights to optimize performance of the network for uncertain traffic demands. Robust routing is the capacity of dealing effectively with the variation from nominal operating conditions of routing. The common approach in robust routing is finding a path that minimizes the worst case scenario. The search heuristics combines the network performance and cost function which deviates from the robust weight settings using an objective function. We consider link load and inter-domain traffic uncertainties and compare their performance with the optimal solution. To evaluate the search heuristics we will first consider small network topologies then we will take larger network topologies with different traffic demands. The results show that for hop count link weight setting the search heuristic does not show any progress. However, for a random weight setting the search heuristic shows better result and the maximum utilization of the link load traffic uncertainty can be improved as close to the optimum. Given different traffic demand and random start weights the search heuristics perform close to optimal for inter-domain traffic uncertainty.