Vol 7 No 2 (2012)
Articles

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

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
Published December 12, 2012
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

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.