Flexible weekly tour scheduling for postal service workers using a branch and price

This paper addresses the problem of flexible shift scheduling of service employees at mail processing and distribution centers. Our main objective is to determine staffing levels for different worker categories subject to a host of union restrictions and general labor regulations. The problem is modeled as a mixed-integer linear program and solved with branch and price algorithm. Using real data provided by a US Postal Service a variety of computational experiments are performed to quantify the benefits of scheduling flexibility. These include different shift starting times, different shift lengths, a lunch break allowance, and different days-off assignments. In addition, the ratio between regular and flexible workers is varied to investigate its effect on costs. The results show the efficiency of the proposed procedure. Finally, we offer some managerial insights gained from the analysis.