An Algorithm for the Traveling Salesman Problem

TLDR

The algorithm builds on techniques commonly used for assignment problems. The paper presents a branch‑and‑bound algorithm for the traveling salesman problem. The method recursively partitions tours into subsets, computes lower bounds for each, and identifies a subset containing a single tour whose length is no greater than any tour’s lower bound. Computational experiments show the algorithm can solve larger instances than previously possible without problem‑specific techniques.

Abstract

A “branch and bound” algorithm is presented for solving the traveling salesman problem. The set of all tours (feasible solutions) is broken up into increasingly small subsets by a procedure called branching. For each subset a lower bound on the length of the tours therein is calculated. Eventually, a subset is found that contains a single tour whose length is less than or equal to some lower bound for every tour. The motivation of the branching and the calculation of the lower bounds are based on ideas frequently used in solving assignment problems. Computationally, the algorithm extends the size of problem that can reasonably be solved without using methods special to the particular problem.