Optimization Online


The Home Service Assignment, Routing, and Appointment Scheduling (H-SARA) problem with Uncertainties

Syu-Ning Johnn (shunee.johnn***at***sms.ed.ac.uk)
Yiran Zhu (y.zhu-95***at***sms.ed.ac.uk)
Andrés Miniguano-Trujillo (Andres.Miniguano-Trujillo***at***ed.ac.uk)
Akshay Gupte (akshay.gupte***at***ed.ac.uk)

Abstract: The Home Service Assignment, Routing, and Appointment scheduling (H-SARA) problem integrates the strategical fleet-sizing, tactical assignment, operational vehicle routing and scheduling subproblems at different decision levels, with a single period planning horizon and uncertainty (stochasticity) from the service duration, travel time, and customer cancellation rate. We propose a two-stage stochastic mixed-integer linear programming model for the H-SARA problem. Additionally, a reduced deterministic version is introduced which allows to solve small-scale instances to optimality with two acceleration approaches. For larger instances, we develop a tailored two-stage decision support system that provides high-quality and in-time solutions based on information revealed at different stages. Our solution method aims to reduce various costs under stochasticity, create reasonable routes with balanced workload and team-based customer service zones, and increase customer satisfaction by introducing a two-stage appointment times update at different times before the actual service. Our two-stage heuristic is competitive to CPLEX's exact solution methods in providing time and cost-effective decisions and can update previously-made decisions based on an increased level of information. Results show that our two-stage heuristic is able to tackle reasonable-size instances and provides good-quality solutions using less time compared to the deterministic and stochastic models on the same set of simulated instances.

Keywords: Stochastic Mixed Integer Programming, Vehicle Routing Problem, A Priori Optimisation, Adaptive Large Neighbourhood Search Heuristics, Home Health Care

Category 1: Applications -- OR and Management Sciences (Transportation )

Category 2: Integer Programming ((Mixed) Integer Linear Programming )

Category 3: Stochastic Programming

Citation: working paper

Download: [PDF]

Entry Submitted: 07/04/2021
Entry Accepted: 07/04/2021
Entry Last Modified: 08/07/2021

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society