We study a two-stage stochastic combinatorial optimization problem that integrates fleet-sizing, assignment, routing, and scheduling problems. Although this problem has wide applicability, it arises in particular in the home healthcare industry where a service team of caregivers have to be assigned to patients and put in vehicle fleet that have to be routed amongst the patients they are going to serve, and one also needs to schedule within a single planning horizon and amidst uncertainty from factors such as service duration, travel time, and customer cancellation rates. A stochastic mixed- integer linear programming model is proposed. For the solution method, we first devise a Benders decomposition algorithm with a heuristic-based warm-start. To accelerate the convergence process, we present a closedform solution to the primal formulation for the subproblem to allow the computational time to increase linearly with the instance size. Furthermore, we provide a set of valid inequalities for the master problem that proved to be beneficial for reducing the number of feasibility cuts needed to be added and overall speeding up the convergence of the algorithm. In order to handle larger instances, we develop a two-stage decision support system to provide highquality and timely solutions based on the information available at each stage. The proposed approach aims to reduce costs, create efficient routes with balanced workloads and teambased customer service zones, and increase customer satisfaction by implementing a twostage appointment notification system that is updated at different stages before the actual service. The results from the computational experiments indicate that the proposed twostage heuristic is highly effective in addressing our problem, as it can provide good-quality solutions for reasonable-sized instances and efficiently handle the uncertainty present in the problem. In particular, the heuristic is competitive with CPLEX’s exact solution methods in terms of providing time and cost-effective decisions and can update previously-made decisions based on an increased level of information.
Citation
Extended and full-length version of proceedings paper in ATMOS 2021, OASIcs vol. 96, DOI: 10.4230/OASIcs.ATMOS.2021.4
Article
View Stochastic programming for an integrated assignment, routing, and scheduling problem