Abstract
The Cumulative Assignment Problem is an NP-complete problem obtained by substituting the linear objective function of the classic Linear Assignment Problem, with a non-linear cumulative function. In this paper we present a first attempt to solve the Cumulative Assignment Problem with metaheuristic techniques. In particular we consider two standard techniques, namely the Simulated Annealing and the Multi-Start methods, and we describe the eXploring Tabu Search: a new structured Tabu Search algorithm which uses an iterative multi-level approach to improve the search. The new method is analyzed through extensive computational experiments and proves to be more effective than the standard methods.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Aarts, E., J.H.M. Korst, and P.J.M. van Laarhoven. (1997). “Simulated Annealing.” In E. Aarts and J.K. Lenstra (eds.), Local Search in Combinatorial Optimization. Chichester: J. Wiley & Sons, pp. 91–120.
Aarts, E. and J.K. Lenstra (eds.). (1997). Local Search in Combinatorial Optimization. Chichester: J. Wiley & Sons.
Balas, E. and E.J. Saltzman. (1989). “Facets of the Three-Index Assignment Polytope,” Discrete Applied Mathematics 23, 201–229.
Balas, E. and E.J. Saltzman. (1991). “An Algorithm for the Three-Index Assignment Problem,” Operations Research 39, 150–161.
Burkard, R.E. and R. Rudolf. (1993). “Computational Investigation on Three-Dimensional Axial Assignment Problems,” Belgian J. Oper. Res. Statist. Comput. Sci. 32, 85–98.
Burkard, R.E., R. Rudolf, and G.J. Woeginger. (1996). “Three-Dimensional Axial Assignment Problems with Decomposable Coefficients,” Discrete Applied Mathematics 65, 123–139.
Camerini, P., L. Fratta, and F. Maffioli. (1975). “On Improving Relaxation Methods by Modified Gradient Techniques,” Math. Prog. Study 3, 26–34.
Camerini, P.M., G. Galbiati, and F. Maffioli. (1980). “Complexity of Spanning Tree Problems: Part I,” European J. Oper. Res. 5, 346–352.
Dell'Amico, M., M. Labbé, and F. Maffioli. (1996). “Complexity of Spanning Tree Problems with Leaf-Dependent Objective Function,” Networks 27, 175–181.
Dell'Amico, M. and F. Maffioli. (1996). “ANewTabu Search Approach to the 0–1 Equicut Problem.” In I.H. Osman and P. Kelly (eds.), Meta-Heuristics: Theory and Applications. Kluwer Academic Publishers, pp. 361–377.
Dell'Amico, M. and S. Martello. (1997a). “The K-Cardinality Assignment Problem,” Discrete Applied Mathematics 76, 103–121.
Dell'Amico, M. and S. Martello. (1997b). “Linear Assignment.” In M. Dell'Amico, F. Maffioli, and S. Martello (eds.), Annotated Bibliographies in Combinatorial Optimization. Chichester: J. Wiley & Sons, pp. 355–371.
Dell'Amico, M., F. Maffioli, and M. Trubian. (1997). “New Bounds for Optimum Traffic Assignment in Satellite Communication,” Computers & Operations Research 25, 729–743.
Dell'Amico, M. and M. Trubian. (1997). “Solution of LargeWeighted Equicut Problems,” European J. Oper. Res. 106, 500–521.
Fischetti, M., G. Laporte, and S. Martello. (1993). “The Delivery Man Problem and Cumulative Matroids,” Operations Research 41, 1055–1064.
Garey, M.R. and D.S. Johnson. (1979). Computers and Intractability: A Guide to the Theory of NP-completeness. San Francisco: W.H. Freeman.
Glover, F. (1997). “A Template for Scatter Search and Path Relinking.” In J.K. Hao, E. Lutton, E. Ronald, M. Schoenauer, and D. Snyers (eds.), Artificial Evolution XI, Lecture Notes in Computer Science, Vol. 1363, pp. 1–45.
Glover, F. and M. Laguna. (1997). Tabu Search. Hingham: Kluwer Academic Publishers.
Haas, O. (1995). “The Cumulative Assignment Problem—Local Search and Heuristics.” Master Thesis, Department of Mathematics, University of Kaiserslautern, Germany.
Laguna, M. and F. Glover. (1993). “Tabu Search.” In C.R. Reeves (ed.), Modern Heuristic Techniques for Combinatorial Problems. Oxford: Blackwell Scientific Publications, pp. 70–141.
Lawler, E. (1976). Combinatorial Optimization: Networks and Matroids. Holt, Reinehart and Winston.
Pierskalla, W.P. (1968). “The Multidimensional Assignment Problem,” Operations Research 16, 422–431.
Qi, L., E. Balas, and G. Gwan. (1994). “A New Facet Class and a Polyhedral Method for the Three-Index Assignment Problem.” In D.Z. Du (ed.), Advances in Optimization and Approximation. Kluwer Academic Publishers, pp. 256–274.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Dell'amico, M., Lodi, A. & Maffioli, F. Solution of the Cumulative Assignment Problem With a Well-Structured Tabu Search Method. Journal of Heuristics 5, 123–143 (1999). https://doi.org/10.1023/A:1009647225748
Issue Date:
DOI: https://doi.org/10.1023/A:1009647225748