zbMATH — the first resource for mathematics

A survey and annotated bibliography of multiobjective combinatorial optimization. (English) Zbl 1017.90096
The paper gives a structured overview of the field of MultiObjective Combinatorial Optimization (MOCO) with a focus on recent developments (since 1994) while referring to earlier survey articles for most of the previous work. After an introduction and formulation of the problem, including an outline of different notions of optimality, theoretical properties of MOCO problems are discussed. Solution methods applied to MOCO problems are reviewed, covering exact methods as well as approximation methods such as simulated annealing, tabu search, genetic algorithms and other recent developments. The subsequent annotated literature review is organized according to the combinatorial structure of MOCO problems and using a classification scheme based on four categories, namely the combinatorial structure, the type of objective function, the problem type and the suggested solution method. Problems included are shortest path problems, assignment problems, transportation and transshipment problems, network flow problems, spanning tree problems, matroids and matroid intersections, the travelling salesman problem, knapsack problems, location problems, set covering problems, and others.

90C29 Multi-objective and goal programming
90-00 General reference works (handbooks, dictionaries, bibliographies, etc.) pertaining to operations research and mathematical programming
90C27 Combinatorial optimization
Full Text: DOI