Branch-and-Bound for the Precedence Constrained Generalized Traveling Salesman Problem

Authors

  • Raad Salman Fraunhofer-Chalmers Research Centre for Industrial Mathematics
  • Fredrik Ekstedt Fraunhofer-Chalmers Research Centre for Industrial Mathematics
  • Peter Damaschke Chalmers University of Technology

Abstract

The Precedence Constrained Generalized Traveling Salesman Problem (PCGTSP) combines the Generalized Traveling Salesman Problem (GTSP) and the Sequential Ordering Problem (SOP). We present a novel branching technique for the GTSP which enables the extension of a powerful pruning technique. This is combined with some modifications of known bounding methods for related problems. The algorithm manages to solve problem instances with 12-26 groups within a minute, and instances with around 50 groups which are denser with precedence constraints within 24 hours.

Downloads

Published

2021-09-01