A Large-Scale Neighborhood Search Algorithm for Multi-Activity Tour Scheduling Problems

Abstract

In this research, we study multi-activity tour scheduling problems with heterogeneous employees in a service sector where demand varies greatly during the day. This problem relates to assigning the employees’ working days throughout the planning horizon and working periods on each working day. In each period, an activity type is given which requires certain skill of the employees. The goal is to reduce the overall over- and under-coverage for each period and activity. The shifts and breaks defined with variable starting slots and durations make the problem flexible and hard to solve. In order to address the problem, an integer programming (IP) approach is first proposed. Due to the problems’ high degree of flexibility, it is impossible to solve instances involving numerous employees and activities in a timely and efficient manner. This leads to the proposal of a heuristic method based on a large neighborhood search (LNS) algorithm. We first create the daily schedules by a context-free grammar (CFG). Then we solve a resource-constrained shortest path problem (RCSPP) to create weekly schedules. Heuristic search is performed on weekly schedules. Moreover, when a constraint on task repetition is added, a CFG is unable to express this constraint, so we incorporate an extension of the IP into our proposed algorithm. Importantly, our approach does not use any closed-source commercial solver like CPLEX. Computational experiments are carried out on the industrial and randomly generated instances to evaluate the performance of the IP solved by CPLEX and the proposed algorithm. Results reveal that our method outperforms CPLEX in both solution time and solution quality in larger instances.