Solving the home service assignment, routing, and appointment scheduling (H-SARA) problem with uncertainties

Syu Ning Johnn, Yiran Zhu, Andrés Miniguano-Trujillo, Akshay Gupte

Research output: Chapter in Book/Report/Conference proceedingConference contribution

10 Downloads (Pure)

Abstract

The Home Service Assignment, Routing, and Appointment scheduling (H-SARA) problem integrates the strategic fleet-sizing, tactical assignment, operational vehicle routing and scheduling problems 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 stochastic mixedinteger 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, to create reasonable routes with balanced workload and team-based customer service zones, and to increase customer satisfaction by introducing a two-stage appointment notification system updated at different time stages 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 reasonablesize instances and provides good-quality solutions using less time compared to the deterministic and stochastic models on the same set of simulated instances.

Original languageEnglish
Title of host publication21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)
EditorsMatthias Muller-Hannemann, Federico Perea
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
ISBN (Electronic)9783959772136
DOIs
Publication statusPublished - 27 Sep 2021
Event21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems 2021 - Virtual, Lisbon, Portugal
Duration: 9 Sep 202110 Sep 2021

Publication series

NameOpenAccess Series in Informatics
Volume96
ISSN (Print)2190-6807

Conference

Conference21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems 2021
Abbreviated titleATMOS 2021
Country/TerritoryPortugal
CityVirtual, Lisbon
Period9/09/2110/09/21

Keywords

  • Adaptive Large Neighbourhood Search
  • Home Health Care
  • Mixed-Integer Linear Programming
  • Monte-Carlo Simulation
  • Two-stage Stochastic
  • Uncertainties A Priori Optimisation

ASJC Scopus subject areas

  • Geography, Planning and Development
  • Modelling and Simulation

Fingerprint

Dive into the research topics of 'Solving the home service assignment, routing, and appointment scheduling (H-SARA) problem with uncertainties'. Together they form a unique fingerprint.

Cite this