Stabilized branch and price with dynamic parameter updating for discontinuous tour scheduling

In this paper we address the problem of staff scheduling at check-in counters with time varying demand. The main objective is to minimize a cost function based on the assigned shifts for a given workforce subject to flexible labor regulations and flexible assignments of lunch breaks. To solve the problem we developed a branch and price algorithm that uses master variable branching. However, since convergence of the column generation subroutine was really slow, we integrated stabilization techniques to speed up the algorithm. We introduced a new dynamic parameter updating procedure for the stabilized column generation. Our computational results show the superior behavior of stabilized column generation compared to the non-stabilized version. Since slow convergence might occur at each node in the search tree and consequently reductions are realized at each node investigated. Furthermore, we perform an in-depth investigation of the updating parameters and give useful insights to choose them. Finally, we tackle realistic problem instances with up to 65 service workers and show the efficiency of the algorithm. (C) 2013 Elsevier Ltd. All rights reserved.