We consider the Time Constrained Travelling Salesman Problem (TCTSP), which minimises the route length and satisfies the associated time-window constraints. In this paper we present a branch and bound algorithm for solving the TCTSP. The lower bound calculation is based on the dynamic programming (DP) formulation and the state-space relaxation procedure (SSR), referred to as the shortest q-path relaxation. A special data structure, which holds all the undominated paths, is implemented for the lower bound calculation. The lower bound is improved by using a subgradient optimisation procedure and then embedded into a tree-search procedure to solve the problem optimally. The algorithm is tested computationally and results for problems with up to 100 cities are presented.
展开▼
