Branch and Bound Implementations for the Traveling Salesperson Problem - Part 1: A solution with nodes containing partial tours with constraints
By: Richard Wiener
Abstract
This first in a series of several columns outlines a well known branch and bound algorithm for solving the Traveling Salesperson Problem (TSP). A single-threaded Java implementation of this algorithm is presented and discussed along with some results on several moderate sized potentially intractable problems. The implementation provides an opportunity to discuss several important Java implementation issues.
Cite as:
Richard Wiener, “Branch and Bound Implementations for the Traveling Salesperson Problem - Part 1: A solution with nodes containing partial tours with constraints”, Journal of Object Technology, Volume 2, no. 2 (March 2003), pp. 65-86, doi:10.5381/jot.2003.2.2.c7.
PDF | HTML | DOI | BiBTeX | Tweet this | Post to CiteULike | Share on LinkedIn