The Multi-Depot Cumulative Vehicle Routing Problem with Mandatory Visit Times and Minimum Delayed Latency

Alan Osorio-Mora, Mauricio Soto-Bustos, Gustavo Gatica, Pedro Palominos, Rodrigo Linfati

Research output: Contribution to journalArticlepeer-review

12 Citations (Scopus)


This paper introduces a novel variant of the cumulative vehicle routing problem (CCVRP) that deals with home health care (HHC) logistics. It includes multiple nonfixed depots and emergency trips from patients to the closest depot. The aim is to minimize the system's delayed latency by satisfying mandatory visit times. Delayed latency corresponds to caregivers' total overtime hours worked while visiting patients. A new mixed-integer linear programming model is proposed to address this problem. Computational experiments, with more than 165 new benchmark instances, are carried out using the CPLEX and Gurobi MIP solvers. The results indicate that patients' geographical distribution directly impacts the complexity of the problem. An analysis of the model parameters proves that instances with more depots/vehicles or longer workdays are significantly easier to solve than are original cases. The results show that Gurobi outperforms CPLEX in 55% of the instances analyzed, while CPLEX performs better in only 16% of them. To the best of our knowledge, this is the first VRP that minimizes delayed latency and the first HHC routing study to use a cumulative objective function.

Original languageEnglish
Article number9350647
Pages (from-to)27210-27225
Number of pages16
JournalIEEE Access
Publication statusPublished - 2021


  • HHC
  • home health care
  • mixed integer programming

ASJC Scopus subject areas

  • General Computer Science
  • General Materials Science
  • General Engineering


Dive into the research topics of 'The Multi-Depot Cumulative Vehicle Routing Problem with Mandatory Visit Times and Minimum Delayed Latency'. Together they form a unique fingerprint.

Cite this