No label defined (Q4801580)

Within this contribution the author deals with possibilities of approximation solving techniques for quadratic assignment problems and for their simplification to semi-quadratic problems or their generalization to nonlinear assignment problems. The introductory part of the contribution is devoted to a general overview of all possible heuristic approaches beginning with simple improving-exchange or insertion heuristics, continuing over greedy randomised adaptive search and associated optimisation systems, to a broad class of meta-heuristics including tabu search, simulated annealing, evolutional approaches and ant colony systems. There is given a rough principle explanation of the associated methods and some specific features and operations are described in detail, making use of examples related to the quadratic assignment problem. The next part of the contribution is focused on heuristic efficiency, when the heuristics are used for quadratic assignment optimisation. The individual heuristic are dealt with and experience with various ways of their implementation and settings are reported. This part includes some problems from practice and some more enhanced assignment problems as multi-index assignment problem and biquadratic assignment problem. The concluding part of the contribution concerns the quadratic semi-assignment problem together with its practical instances of public transport mean scheduling. This part is completed with a specific two phase heuristic for the problem. The contribution ends with some recommendation on future research directions. Big stress is laid on investigation of the pilot meta-heuristic and the associated look-ahead investigation. As regards the metaheuristics, the author assumes that it could be worth to find out, under which circumstances an individual heuristic performs better than the other ones. For the entire collection see [Zbl 0996.00025].