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

Vol. 7 No. 2 (2012)

Section

Articles

License

The copyright of the submitted article is hereby transferred to “Preeminent Academic Facets Inc. (the “publisher”) to the extent possible by the laws in the respective countries of the author(s). The author(s) retain all other rights including the following: 1. Any patents and trademark rights. 2. Right to post a pre-print version of the paper on the author’s personal website which is not used for commercial purposes. The author(s) warrant that the work is original, it has not been published elsewhere, it is not currently under consideration for publication in any form, and it does not infringe any copyright laws. The signing author or agent further warrants that all authors, if applicable, have been informed of the terms of this agreement and obtained the approval and authority to sign the agreement.