Tour Scheduling with Skill Based Costs

Abstract. We present a new formulation of the tour scheduling problem with assignment costs that are a function of employee capabilities. The objective also incorporates a quadratic term to encourage compact shifts and equal interday shift lengths for each employee. The problem is solved using a tabu-like probabilistic local search algorithm. The algorithm is applied in two phases with employee conflicts removed in the first and soft constraints and the objective function value improved in the second. Solutions provide minimum cost templates for employee schedules. The efficacy of the algorithm is demonstrated with a computational study and conclusions are presented regarding the approach.