An improved lower bound for the asymmetric traveling salesman problem based on the assignment problem

An improved lower bound for the asymmetric traveling salesman problem based on the assignment problem

0.00 Avg rating0 Votes
Article ID: iaor2006618
Country: Portugal
Volume: 25
Issue: 1
Start Page Number: 63
End Page Number: 83
Publication Date: Jun 2005
Journal: Investigao Operacional
Authors: ,
Abstract:

In this article we describe how to compute a lower bound for the asymmetric traveling salesman problem that dominates the bound that comes from the assignment relaxation, through the solving of a sequence of assignment problems. The algorithm that we propose is a first-order method based on the exponential penalty function. Directions of movement are derived from a disjunctive relaxation that we proposed as being one of two possible classes, one based on cycles, the other based on cliques.

Reviews

Required fields are marked *. Your email address will not be published.