Robust Multiperiod Vehicle Routing Under Customer Order Uncertainty

Anirudh Subramanyam (), Frank Mufalli (), José M. Lí?nez-Aguirre (), Jose M. Pinto () and Chrysanthos E. Gounaris ()
Additional contact information
Anirudh Subramanyam: Department of Chemical Engineering, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213; Center for Advanced Process Decision-making, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213
Frank Mufalli: Linde.Digital, Linde plc, Tonawanda, New York 14150
José M. Lí?nez-Aguirre: Linde.Digital, Linde plc, Tonawanda, New York 14150
Jose M. Pinto: Linde.Digital, Linde plc, Danbury, Connecticut 06810
Chrysanthos E. Gounaris: Department of Chemical Engineering, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213; Center for Advanced Process Decision-making, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213

Operations Research, 2021, vol. 69, issue 1, 30-60

Abstract: In this paper, we study multiperiod vehicle routing problems where the aim is to determine a minimum cost visit schedule and associated routing plan for each period using capacity-constrained vehicles. In our setting, we allow for customer service requests that are received dynamically over the planning horizon. In order to guarantee the generation of routing plans that can flexibly accommodate potential service requests that have not yet been placed, we model future potential service requests as binary random variables, and we seek to determine a visit schedule that remains feasible for all anticipated realizations of service requests. To that end, the decision-making process can be viewed as a multistage robust optimization problem with binary recourse decisions. We approximate the multistage problem via a nonanticipative two-stage model for which we propose a novel integer programming formulation and a branch-and-cut solution approach. In order to investigate the quality of the solutions we obtain, we also derive a valid lower bound on the multistage problem and present numerical schemes for its computation. Computational experiments on benchmark data sets show that our approach is practically tractable and generates high-quality robust plans that significantly outperform existing approaches in terms of both operational costs and fleet utilization.

Keywords: robust optimization; vehicle routing; uncertain customer orders; two-stage problems; branch-and-cut; multiperiod planning; rolling-horizon simulations (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
https://doi.org/10.1287/opre.2020.2009 (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:oropre:v:69:y:2021:i:1:p:30-60

Access Statistics for this article

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