Munich Personal RePEc Archive

Generation of the exact Pareto set in multi-objective traveling salesman and set covering problems

Florios, Kostas and Mavrotas, George (2014): Generation of the exact Pareto set in multi-objective traveling salesman and set covering problems. Published in: Applied Mathematics and Computation , Vol. 237, (15 June 2014): pp. 1-19.

[img]
Preview
PDF
MPRA_paper_105074.pdf

Download (1MB) | Preview

Abstract

The calculation of the exact set in Multi-Objective Combinatorial Optimization (MOCO) problems is one of the most computationally demanding tasks as most of the problems are NP-hard. In the present work we use AUGMECON2 a Multi-Objective Mathematical Programming (MOMP) method which is capable of generating the exact Pareto set in Multi-Objective Integer Programming (MOIP) problems for producing all the Pareto optimal solutions in two popular MOCO problems: The Multi-Objective Traveling Salesman Problem (MOTSP) and the Multi-Objective Set Covering problem (MOSCP). The computational experiment is confined to two-objective problems that are found in the literature. The performance of the algorithm is slightly better to what is already found from previous works and it goes one step further generating the exact Pareto set to till now unsolved problems. The results are provided in a dedicated site and can be useful for benchmarking with other MOMP methods or even Multi-Objective Meta-Heuristics (MOMH) that can check the performance of their approximate solution against the exact solution in MOTSP and MOSCP problems.

Logo of the University Library LMU Munich
MPRA is a RePEc service hosted by
the University Library LMU Munich in Germany.