Vehicle Routing Problems with Synchronized Visits and Stochastic Travel and Service Times: Applications in Healthcare

Hossein Hashemi Doulabi (), Gilles Pesant () and Louis-Martin Rousseau ()
Additional contact information
Hossein Hashemi Doulabi: Department of Mechanical, Industrial and Aerospace Engineering, Concordia University, Montreal, Quebec H3G 1M8, Canada; Interuniversity Research Center on Enterprise Networks, Logistics and Transportation, Montreal, Quebec H3C 3J7, Canada;
Gilles Pesant: Interuniversity Research Center on Enterprise Networks, Logistics and Transportation, Montreal, Quebec H3C 3J7, Canada; Department of Computer and Software Engineering, Polytechnique Montreal, Montreal, Quebec H3T 1J4, Canada;
Louis-Martin Rousseau: Interuniversity Research Center on Enterprise Networks, Logistics and Transportation, Montreal, Quebec H3C 3J7, Canada; Department of Mathematics and Industrial Engineering, Polytechnique Montreal, Montreal, Quebec H3T 1J4, Canada

Transportation Science, 2020, vol. 54, issue 4, 1053-1072

Abstract: This paper, for the first time, studies vehicle routing problems with synchronized visits (VRPS) and stochastic travel and service times. In addition to considering a home healthcare scheduling problem, we introduce an operating room scheduling problem with stochastic durations as a novel application of VRPS. We formulate VRPS with stochastic times as a two-stage stochastic integer programming model that, unlike the deterministic models in the VRPS literature, does not have any big-M constraints. This advantage comes at the cost of a large number of second-stage integer variables. We prove that the integrality constraints on second-stage variables can be relaxed, and therefore, we can apply the L-shaped algorithm and its branch-and-cut implementation to solve the problem. We enhance the model by developing valid inequalities and a lower bounding functional. We analyze the subproblems of the L-shaped algorithm and devise a specialized algorithm for them that is significantly faster than standard linear programming algorithms. Computational results show that the branch-and-cut algorithm optimally solves stochastic home healthcare scheduling instances with 15 patients and 10%–30% of synchronized visits. It also finds solutions with an average optimality gap of 3.57% for instances with 20 patients. Furthermore, the branch-and-cut algorithm optimally solves stochastic operating room scheduling problems with 20 surgeries.

Keywords: vehicle routing with synchronized visits; stochastic travel and service times; two-stage stochastic integer programming (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (13)

Downloads: (external link)
https://doi.org/10.1287/trsc.2019.0956 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:54:y:2020:i:4:p:1053-1072

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().