Robust Optimization of a Broad Class of Heterogeneous Vehicle Routing Problems Under Demand Uncertainty

Anirudh Subramanyam (), Panagiotis P. Repoussis () and Chrysanthos E. Gounaris ()
Additional contact information
Anirudh Subramanyam: Department of Chemical Engineering and Center for Advanced Process Decision-making, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213
Panagiotis P. Repoussis: School of Business, Stevens Institute of Technology, Hoboken, New Jersey 07030; Department of Marketing and Communication, Athens University of Economics and Business, Athens 104 34, Greece
Chrysanthos E. Gounaris: Department of Chemical Engineering and Center for Advanced Process Decision-making, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213

INFORMS Journal on Computing, 2020, vol. 32, issue 3, 661-681

Abstract: This paper studies robust variants of an extended model of the classical heterogeneous vehicle routing problem (HVRP), where a mixed fleet of vehicles with different capacities, availabilities, fixed costs, and routing costs is used to serve customers with uncertain demand. This model includes, as special cases, all variants of the HVRP studied in the literature with fixed and unlimited fleet sizes, accessibility restrictions at customer locations, and multiple depots. Contrary to its deterministic counterpart, the goal of the robust HVRP is to determine a minimum cost set of routes and fleet composition that remains feasible for all demand realizations from a prespecified uncertainty set. To solve this problem, we develop robust versions of classical node and edge exchange neighborhoods that are commonly used in local search and establish that efficient evaluation of the local moves can be achieved for five popular classes of uncertainty sets. The proposed local search is then incorporated in a modular fashion within two metaheuristic algorithms to determine robust HVRP solutions. The quality of the metaheuristic solutions is quantified using an integer programming model that provides lower bounds on the optimal solution. An extensive computational study on literature benchmarks shows that the proposed methods allow us to obtain high-quality robust solutions for different uncertainty sets and with minor additional effort compared with deterministic solutions.

Keywords: robust optimization; vehicle routing; demand uncertainty; local search; metaheuristics; branch-and-cut (search for similar items in EconPapers)
Date: 2020
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/ijoc.2019.0923 (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:orijoc:v:32:y:3:i:2020:p:661-681

Access Statistics for this article

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