

![0_image_0.png](0_image_0.png)

more instances were solved within 10,000 visited nodes than by the other combinations.  On average they produced faster solutions than the other combinations.

The same observations as for A(n, d, 4.0) can be made when charting the fastest solutions of the hard instances of H ( n, d, 4.0) (see Figure 11). About 29% (21,307) of the solved instances are inconsistent. Most of them were, again, solved faster than the consistent instances.  More than 75% of the hard instances can be solved with at most 150 visited nodes.

90% can be solved with at most 1,300 visited nodes. Since the H 8 /dynamic/local heuristic alone solves more than 86% of the instances, it seems difficult to combine different heuristics in a way that more hard instances can be solved while using not more than 10,000 visited nodes altogether. However, when orthogonally combining the two best performing heuristics
( H s / dynamic/local and H s / static/global ) allowing each of them a maximal number of 5,000 visitable nodes, we can solve 92% (69,056) of the hard instances.

We tried to solve the 2,640 hard instances of H ( n, d, 4.0) which are not solvable using orthogonal combination of heuristics with at most 10,000 visited nodes by using a maximal nmber of 100,000 visited nodes. 471 of these instances are still not solvable, more than 75% of the solved instances are inconsistent. The fastest response for the solved instances is charted in Figure 12(b).  The most successful heuristics in giving the fastest response are Hs /dynamic/local (42.5%) and Hs /static/global (26.6%).  The three heuristics using static/global computation of constrainedness combined with using Qs,Cs, and B as a split set gave the fastest response for 15.9% of the solved instances where the B strategy was by far the best among the three (9.4%).

## 8. Combining Heuristics For Solving Large Instances

In the previous section we found that combining different heuristics orthogonally can solve more instances using the same amount of visited nodes than any heuristic alone can solve.  In this section we use these results in order to identify the size of randomly generated instances