EJECTION CHAINS, REFERENCE STRUCTURES AND ALTERNATING PATH METHODS FOR TRAVELING SALESMAN PROBLEMS

Ejection chain procedures are based on the notion of generating compou nd sequences of moves, leading from one solution to another, by linked steps in which changes in selected elements cause other elements to b e ''ejected from'' their current state, position or value assignment. This paper introduces new ejection chain strategies designed to genera te neighborhoods of compound moves with attractive properties for trav eling salesman problems. These procedures derive from the principle of creating a reference structure that coordinates the options for the m oves generated. We focus on ejection chain processes related to altern ating paths, and introduce three reference structures, of progressivel y greater scope, that produce both classical and non-standard alternat ing path trajectories. Theorems and examples show that various rules f or exploiting these structures can generate moves not available to cus tomary neighborhood search approaches. We also provide a reference str ucture that makes it possible to generate a collection of alternating paths that precisely expresses the symmetric difference between two to urs. In addition to providing new results related to generalized alter nating paths, in directed and undirected graphs, we lay a foundation f or achieving a combinatorial leverage effect, where an investment of p olynomial effort yields solutions dominating exponential numbers of al ternatives. These consequences are explored in a sequel.