Staff scheduling at the United States Postal Service

The purpose of this paper is to present a full-scale model of the tour scheduling problem as it arises in the United States Postal Service, and to examine several scenarios aimed at reducing the size of the workforce. The problem is formulated as a pure integer linear program and solved with CPLEX. The baseline model includes both full-time and part-time workers, as well as the principal constraints defined by the union contract. The scenarios include requirements for two days off in a row, variable daily start times, the use of part-time flexible workers, and a parametric analysis of full-time to part-time restrictions. The results indicate that problem instances of realistic size can be solved within 1 h, and that measurable savings can be achieved by departing from current practice.