Branch and Bound Implementations for the Traveling Salesperson Problem - Part 2: Single threaded solution with many inexpensive nodes

Abstract

In the first column published in the March/April, 2003 issue, a branch and bound algorithm that involves generating nodes that represent partial tours with constraints was presented and implemented. The computational cost as well as the memory overhead required to generate each node was shown to be significant. Furthermore, the algorithm assumes that the cost matrix that specifies the cost of traveling from one city to another is symmetric. All of these problems are overcome using the algorithm presented and implemented in this column.

Cite as:

Richard Wiener, “Branch and Bound Implementations for the Traveling Salesperson Problem - Part 2: Single threaded solution with many inexpensive nodes”, Journal of Object Technology, Volume 2, no. 3 (May 2003), pp. 65-76, doi:10.5381/jot.2003.2.3.c7.