370 E.L. Pasiliao Jr.
The standard exchanges are only between elements that are already in the solution,
while expanded exchanges allow outside elements to come into the solution. The
expanded versions can find better solutions due to its larger neighborhood but with
more computation effort.
Escape from local minima is possible through the use of local neighborhood
extensions such as variable depth interchange, path relinking, and variable neigh-
borhood search. Path relinking may be implemented with either interpermutation
and intrapermutation linking. Variable neighborhood search is done using differ-
ent combinations of the intrapermutation 2- and n-exchanges and interpermutation
2-exchange neighborhoods.
The neighborhoods and their extensions may be implemented to find better so-
lutions of heuristics or to tighten lower bounds in exact algorithms. Careful consid-
eration must be given to the selection of local neighborhood definitions and to the
techniques for escaping local minima. The choice of local search has the potential
to be more important than the selection of heuristic or exact algorithm to solve the
multidimensional assignment problem.
References
1. Ahuja, R.K., Ergun, Ö., Orlin, J.B., Punnen, A.P.: A survey of very large-scale neighborhood
search techniques. Discrete Appl. Math. 123(1–3), 75–102 (2002)
2. Aiex, R.M., Pardalos, P.M., Resende, M.G.C., Toraldo, G.: GRASP with path relinking for the
three-index assignment problem. INFORMS J. Comput. 17(2), 224–247 (2005)
3. Balas, E., Saltzman, M.J.: An algorithm for the three-index assignment problem. Oper. Res.
39(1), 150–161 (1991)
4. Blackman, S.S.: Multiple-Target Tracking with Radar Applications. Artech House, Norwood
(1986)
5. Burkard, R.E., Çela, E.: Quadratic and three-dimensional assignment problems: An annotated
bibliography. In: DellAmico, M., Maffioli, F., Martello, S. (eds.) Annotated Bibliographies in
Combinatorial Optimization, pp. 373–392. Wiley, New York (1997). Chap. 21
6. Burkard, R.E., Çela, E.: Linear assignment problems and extensions. In: Du, D., Pardalos, P.M.
(eds.) Handbook of Combinatorial Optimization, pp. 75–149. Kluwer Academic, Dordrecht
(1999). Chap. 21
7. Çela, E.: Assignment problems. In: Pardalos, P.M., Resende, M.G.C. (eds.) Handbook of Ap-
plied Optimization, pp. 661–678. Oxford University Press, New York (2002). Chap. 17.9
8. Gilbert, K., Hofstra, R.: Multidimensional assignment models. Decis. Sci. 19, 306–321 (1988)
9. Hansen, P., Mladenovi
´
c, N.: Variable neighborhood search: Principles and applications. Eur.
J. Oper. Res. 130, 449–467 (2001)
10. Hansen, P., Mladenovi
´
c, N.: Variable neighborhood search. In: Pardalos, P.M., Resende,
M.G.C. (eds.) Handbook of Applied Optimization, pp. 221–234. Oxford University Press,
New York (2002). Chap. 3.6.9
11. Laguna, M., Martí, R.: GRASP and path relinking for 2-layer straight line crossing minimiza-
tion. INFORMS J. Comput. 11, 44–52 (1999)
12. Lin, S., Kernighan, B.W.: An effective heuristic algorithm for the traveling salesman problem.
Oper. Res. 21, 498–516 (1973)
13. Lourenço, H.R., Martin, O.C., Stützle, T.: Iterated local search. In: Glover, F., Kochen-
berger, G. (eds.) Handbook of Metaheuristics. International Series in Operations Research
and Management Science, vol. 57, pp. 321–353. Kluwer Academic, Dordrecht (2002)