What are some "cookbook" methods for neighborhood structure design in simulated annealing for combinatorial optimization?
Are some reviews or books that contain some "cookbook" methods for neighborhood structure design?
Useful state transition tend to be such that parts of the solution can be preserved while rearranging the relationships between the parts. For instance, for TSP, a state transition should preserve large parts of the tour and only modify a handful of edges; a typical transition chooses two random edges and swaps their endpoints, i.e. turns $AB$ and $CD$ into $AD$ and $BC$ (taking care to match the endpoints such that the tour remains connected). For spin models, a useful state transition flips entire blocks of spins to keep the relative orientations inside the block intact. There are nifty methods for selecting the blocks such that the boundary includes many mismatched spin pairs without disturbing detailed balance; you can find information on these by searching e.g. for "cluster algorithm" and "spin model".