Optimal Models for Meal-Break and Start-Time Flexibility in Continuous Tour Scheduling

This paper presents a compact integer-programming model for large-scale continuous tour scheduling problems that incorporate meal-break window, start-time band, and start-time interval policies. For practical scheduling environments, generalized set-covering formulations (GSCFs) of such problems often contain hundreds of millions of integer decision variables, usually precluding identification of optimal solutions. As an alternative, we present an implicit integer-programming model that frequently has fewer than 1,500 variables and can be formulated and solved using PC-based hardware and software platforms. An empirical study using labor-requirement distributions for customer service representatives at a Motorola, Inc. call center was used to demonstrate the importance of having a model that can evaluate tradeoffs among the various scheduling policies.