Stochastic Programming Models for a Fleet Sizing and Appointment Scheduling Problem with Random Service and Travel Times

We propose a new stochastic mixed-integer linear programming model for a home service fleet sizing and appointment scheduling problem (HFASP) with random service and travel times. Specifically, given a set of providers and a set of geographically distributed customers within a service region, our model solves the following decision problems simultaneously: (i) a fleet sizing problem that determines the number of providers required to serve customers; (ii) an assignment problem that assigns providers to customers; and (iii) a sequencing and scheduling problem that decides the sequence of service start times of customers assigned to each provider. Here, a sequence of customers assigned to a provider is equivalent to the provider’s route. The objective is to minimize the fixed cost of hiring providers plus the expectation of a weighted sum of customers’ waiting time and providers’ travel time, overtime, and idle time. We present extensive computational results to show the size and characteristics of problem instances that can be solved with our proposed model and an extension of an existing model in the literature, demonstrating where significant improvements in performance can be gained with our proposed model. In addition, we use a case study based on a service region in Lehigh County to derive insights into the HFASP.