Iain Dunning, Swati Gupta, and John Silberholz (Operations Research Center, Massachusetts Institute of Technology) state: “Though empirical testing is broadly used to evaluate heuristics, there are shortcomings with how it is often applied in practice”. Although their paper focuses on Max-Cut and Quadratic Unconstrained Binary Optimization, their ideas are interesting for other problems as well. The corresponding paper can be downloaded here.