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 toadjust 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 thetraffic demands.In this paper we study search heuristics for determining a set of OSPF/IS-IS link weights tooptimize performance of the network for uncertain traffic demands. Robust routing is thecapacity of dealing effectively with the variation from nominal operating conditions ofrouting. The common approach in robust routing is finding a path that minimizes the worstcase scenario. The search heuristics combines the network performance and cost functionwhich 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 anyprogress. 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 theoptimum. Given different traffic demand and random start weights the search heuristics perform close to optimal for inter-domain traffic uncertainty.