A two-phase method for bi-objective combinatorial optimization and its application to the TSP with profits

Authors

  • Carlo Filippi Department of Economics and Management, University of Brescia, Contrada S. Chiara 50, 25122 Brescia, Italy
  • Elisa Stevanato Department of Economics and Management, University of Brescia, Contrada S. Chiara 50, 25122 Brescia, Italy

Abstract

We study a variant of the two-phase method for general bi-objective combinatorial optimization problems. First, we analyze a basic enumerative procedure, often used in literature to solve specific bi-objective combinatorial optimization problems, making it suitable to solve general problems. We show that the procedure generates the exact set E of efficient points by solving exactly 2[notdef]E[notdef] − 1 single objective problems. Second, we embed the procedure in a classic two-phase framework, where supported points are computed in the first phase and unsupported points are computed in the second phase. We test the refined approach on a hard problem, namely the Traveling Salesman Problem with Profits, a bi-objective generalization of the well known Traveling Salesman Problem. On the tested instances, the procedure outperforms the [epsilon1]-constraint method, one of the most used approaches to solve exactly general bi-objective combinatorial optimization problems.

Downloads

Published

2012-12-12

How to Cite

Filippi, C., & Stevanato, E. (2012). A two-phase method for bi-objective combinatorial optimization and its application to the TSP with profits . Algorithmic Operations Research, 7(2). Retrieved from https://journals.lib.unb.ca/index.php/AOR/article/view/20401

Issue

Section

Articles