In this thesis, we develop two exact algorithms and a heuristic procedure for Multiobjective
Combinatorial Optimization Problems (MOCO). Our exact algorithms
guarantee to generate all nondominated solutions of any MOCO problem. We test the
performance of the algorithms on randomly generated problems including the Multiobjective
Knapsack Problem, Multi-objective Shortest Path Problem and Multi-objective
Spanning Tree Problem. Although we showed the algorithms work much better than the
previous ones, we also proposed a fast heuristic method to approximate efficient frontier
since it will also be applicable for real-sized problems. Our heuristic approach is based
on fitting a surface to approximate the efficient frontier. We experiment our heuristic on
randomly generated problems to test how well the heuristic procedure approximates the
efficient frontier. Our results showed the heuristic method works well.
Identifer | oai:union.ndltd.org:METU/oai:etd.lib.metu.edu.tr:http://etd.lib.metu.edu.tr/upload/12608443/index.pdf |
Date | 01 June 2007 |
Creators | Lokman, Banu |
Contributors | Koksalan, Murat |
Publisher | METU |
Source Sets | Middle East Technical Univ. |
Language | English |
Detected Language | English |
Type | M.S. Thesis |
Format | text/pdf |
Rights | To liberate the content for public access |
Page generated in 0.002 seconds