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
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.