Algorithms for the Precedence Constrained Generalized Travelling Salesperson Problem

R. Salman, Master thesis, Chalmers University of Technology, supervisor F. Ekstedt, August 27, 2015


This thesis aims to implement and evaluate heuristic algorithms as well as formulating a MILP model for solving the precedence constrained travelling salesperson problem (PCGTSP). Numerical experiments are carried out on synthetic and real problem instances of di fferent types.The MILP model is tested together with a generic solver to produce lower bounds on the optimal values of the problem instances. Results indicate that k-opt algorithms and metaheuristic algorithms that have been previously employed for related problems need further adaptation to be truly e ffective for the PCGTSP. The MILP model is shown to produce lower bounds of varying quality depending on the problem instance.

Photo credits: Nic McPhee