Approximative solution methods for multiobjective combinatorial optimization

被引：1
作者：
Matthias Ehrgott
Xavier Gandibleux
机构：
[1] University of Auckland,Department of Engineering Science
[2] University of Valenciennes,LAMIH — UMR CNRS 8530
[3] Campus “Le Mont Houy”,undefined
来源：
Top | 2004年 / 12卷 / 1期
关键词：
Multiobjective optimization; combinatorial optimization; heuristics; metaheuristics; approximation; 90C29; 90C27; 90C59;
D O I：
10.1007/BF02578918
中图分类号：
学科分类号：
摘要：
In this paper we present a review of approximative solution methods, that is, heuristics and metaheuristics designed for the solution of multiobjective combinatorial optimization problems (MOCO). First, we discuss questions related to approximation in this context, such as performance ratios, bounds, and quality measures. We give some examples of heuristics proposed for the solution of MOCO problems. The main part of the paper covers metaheuristics and more precisely non-evolutionary methods. The pioneering methods and their derivatives are described in a unified way. We provide an algorithmic presentation of each of the methods together with examples of applications, extensions, and a bibliographic note. Finally, we outline trends in this area.
引用
收藏
页码：1 / 63
页数：62
相关论文
共 176 条
  • [1] Alves M.J.(2000)An interactive method for 0–1 multiobjective problems using simulated annealing and tabu search Journal of Heuristics 6 385-403
  • [2] Climaco J.(1996)On bicriterion minimal spanning trees: An approximation Computers and Operations Research 23 1171-1182
  • [3] Andersen K.A.(2001)Goal programming using the multiple objective tabu search Journal of the Operational Research Society 52 1359-1369
  • [4] Jørnsten K.(2001)MOAPPS 1.0: Aggregate production planning using the multiple objective tabu search International Journal of Production Research 39 3685-3702
  • [5] Lind M.(1999)A taboo search based approach to find the Pareto optimal set in multiple objective optimisation Journal of Engineering Optimization 31 731-748
  • [6] Baykasoglu A.(1989)Algorithmische Untersuchungen zu bikriteriellen kostenminimalen Flüssen in Netzwerken Wissenschaftliche Zeitung der Technischen Hochschule Leipzig 13 333-341
  • [7] Baykasoglu A.(1999)A comprehensive survey of evoutionary-based multiobjective optimization techniques Knowledge and Information Systems 1 269-308
  • [8] Baykasoglu A.(2000)An updated survey of GA-based multiobjective optimization techniques ACM Computing Surveys 32 109-143
  • [9] Owen S.(1985)Efficient spanning trees Journal of Optimization Theory and Applications 45 481-485
  • [10] Gindy N.(1996)A multiobjective metaheuristic approach to the localization of a chain of petrol stations by the capital budgeting model Control and Cybernetics 25 177-187
12345678910