Document Type

Conference Paper

Rights

This item is available under a Creative Commons License for non-commercial use only

Disciplines

Applied mathematics, Computer Sciences

Publication Details

Presented at ICIT, 2009: The 4th International Conference on Information Technology, Amaan, Jordan, 2009.

Abstract

The Sparse Travelling Salesman Problem (Sparse TSP) which is a variant of the classical Travelling Salesman Problem (TSP) is the problem of finding the shortest route of the salesman when visiting cities in a region making sure that each city is visited at least once and returning home at the end. In the Sparse TSP, the distance between cities may not obey the triangle inequality; this makes the use of algorithms and formulations designed for the TSP to require modifications in order to produce near-optimal results. A lower bound for optmisation problems gives us the quality guarantee of the near-optimal solution obtained by using heuristic methods. In this paper we propose two methods of finding tight lower bound for the Sparse TSP. The first method uses the integer linear programming relaxation for the Sparse TSP and the Embedded Flow Formulation (EFF) for the Sparse TSP. The second method proposes a strategy for quickly generating some of the violated arc-cutset constraints which we call an Arc-cutset Partial Enumeration Strategy (APES).