The 'EGASP' method for traveling salesman-like resource allocation problems
William H. Press, C. Callan · Guidance, Navigation and Control Conference · 1987
In resource allocation problems, it is possible to define the local efficiency of a small change, namely the ratio of change in value to marginal cost. This efficiency can be used to guide the exploration of an otherwise stochastic method like simulated annealing. An algorithm embodying this idea, termed EGASP (Efficiency-Guided Addition, Subtraction, and Permutation) is described for problems akin to the traveling salesman problem. I. Introduction We discuss in this paper a method for approximately solving a class of resource allocation problems that are loosely based on the traveling salesman problem. The method and its variants are named EGASP, an acronym for EfficiencyGuided Addition, Subtraction, and Permutation. The EGASP method is stochastic, and it is somewhat related to the method of simulated annealing',213. More precisely, EGASP can be thought of as a sub-strategy for choosing random moves within the context of the simulated annealing method.