Abstract
Tabu search is a metastrategy for guiding known heuristics to overcome local optimality with a large number of successful applications reported in the literature. In this paper we investigate two dynamic strategies, the reverse elimination method and the cancellation sequence method. The incorporation of strategic oscillation as well as a combination of these methods are developed. The impact of the different methods is shown with respect to the traveling purchaser problem, a generalization of the classical traveling salesman problem. The traveling purchaser problem is the problem of determining a tour of a purchaser buying several items in different shops by minimizing the total amount of travel and purchase costs. A comparison of the tabu search strategies with a simulated annealing approach is presented, too.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
G. Clarke and J.W. Wright, Scheduling of vehicles from a central depot to a number of delivery points, Operations Research 12(1964)568–581.
F. Dammeyer, P. Forst and S. Voß, On the cancellation sequence method of tabu search, ORSA Journal on Computing 3(1991)262–265.
F. Dammeyer and S. Voß, Application of tabu search strategies for solving multiconstraint zero-one knapsack problems, Working Paper, TH Darmstadt (1991).
F. Dammeyer and S. Voß, Dynamic tabu list management using the reverse elimination method, Annals of Operations Research 41(1993)31–46.
W. Domschke, P. Forst and S. Voß, Tabu search techniques for the quadratic semi-assignment problem, in:New Directions for Operations Research in Manufacturing, ed. G. Fandel, T. Gulledge and A. Jones (Springer, Berlin, 1992) pp. 389–405.
K.A. Dowsland, Simulated annealing, in:Modern Heuristic Techniques for Combinatorial Problems, ed. C.R. Reeves (Blackwell, Oxford, 1993) pp. 20–69.
M.R. Garey and D.S. Johnson,Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, San Francisco, 1979).
F. Glover, Tabu search - part I, ORSA Journal on Computing 1(1989)190–206.
F. Glover, Tabu search - part II, ORSA Journal on Computing 2(1990)4–32.
F. Glover and M. Laguna, Tabu search, in:Modern Heuristic Techniques for Combinatorial Problems, ed. C.R. Reeves (Blackwell, Oxford, 1993) pp. 70–150.
F. Glover, M. Laguna, E. Taillard and D. de Werra (eds.),Tabu Search, Annals of Operations Research 41 (Baltzer, Basel, 1993).
B. Golden, L. Levy and R. Dahl, Two generalizations of the traveling salesman problem, Omega 9(1981)439–441.
S.K. Jacobsen, Heuristics for the capacitated plant location model, European Journal of Operational Research 12(1983)253–261.
R.K. Karg and G.L. Thompson, A heuristic approach to solving traveling salesman problems, Management Science 10(1964)225–248.
J.P. Kelly, B.L. Golden and A.A. Assad, Large-scale controlled rounding using tabu search with strategic oscillation, Annals of Operations Research 41(1993)69–84.
S. Lin and B.W. Kernighan, An effective heuristic algorithm for the traveling salesman problem, Operations Research 21(1973)498–516.
N. Metropolis, A.W. Rosenbluth, M.N. Rosenbluth, A.H. Teller and E. Teller, Equation of state calculation by fast computing machines, Journal of Chemical Physics 21(1953)1087–1091.
H.L. Ong, Approximate algorithms for the travelling purchaser problem, Operations Research Letters 1(1982)201–205.
I.H. Osman, Heuristics for the generalised assignment problem: Simulated annealing and tabu search approaches, OR Spektrum 17(1995)211–225.
I.H. Osman and N. Christofides, Capacitated clustering problems by hybrid simulated annealing and tabu search, International Transactions in Operational Research 1(1994)317–336.
H. Paessens and H.K. Weuthen, Tourenplanung in städtischen Straßennetzen mit einem heuristischen Verfahren, in:Tourenplanung bei der Abfallbeseitigung, ed. H.H. Hahn (Schmidt, Bielefeld, 1977) pp. 101–130.
T. Ramesh, Travelling purchaser problem, Opsearch 18(1981)78–91.
S. Voß, ADD- and DROP-procedures for the travelling purchaser problem, Methods of Operations Research 53(1986)317–318.
S. Voß, The traveling purchaser problem with fixed costs, Working Paper, TH Darmstadt (1989).
S. Voß,Steiner-Probleme in Graphen (Hain, Frankfurt am Main, 1990).
S. Voß, Intelligent search, Manuscript, TH Darmstadt (1993).
S. Voß, Solving quadratic assignment problems using the reverse elimination method, in:The Impact of Emerging Technologies on Computer Science and Operations Research, ed. S.G. Nash and A. Sofer (Kluwer, Dordrecht, 1995) pp. 281–296.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Voß, S. Dynamic tabu search strategies for the traveling purchaser problem. Ann Oper Res 63, 253–275 (1996). https://doi.org/10.1007/BF02125457
Issue Date:
DOI: https://doi.org/10.1007/BF02125457