Skip to main content

An Adaptive Memory Programming Framework for the Robust Capacitated Vehicle Routing Problem

Author(s): Gounaris, Chrysanthos E; Repoussis, Panagiotis P; Tarantilis, Christos D; Wiesemann, Wolfram; Floudas, Christodoulos A

To refer to this page use:
Abstract: We present an adaptive memory programming (AMP) metaheuristic to address the robust capacitated vehicle routing problem under demand uncertainty. Contrary to its deterministic counterpart, the robust formulation allows for uncertain customer demands, and the objective is to determine a minimum cost delivery plan that is feasible for all demand realizations within a prespecified uncertainty set. A crucial step in our heuristic is to verify the robust feasibility of a candidate route. For generic uncertainty sets, this step requires the solution of a convex optimization problem, which becomes computationally prohibitive for large instances. We present two classes of uncertainty sets for which route feasibility can be established much more efficiently. Although we discuss our implementation in the context of the AMP framework, our techniques readily extend to other metaheuristics. Computational studies on standard literature benchmarks with up to 483 customers and 38 vehicles demonstrate that the proposed approach is able to quickly provide high-quality solutions. In the process, we obtain new best solutions for a total of 123 benchmark instances.
Publication Date: 2016
Citation: Gounaris, Chrysanthos E., Panagiotis P. Repoussis, Christos D. Tarantilis, Wolfram Wiesemann, and Christodoulos A. Floudas. "An Adaptive Memory Programming Framework for the Robust Capacitated Vehicle Routing Problem." Transportation Science 50, no. 4 (2016): 1239-1260. doi: 10.1287/trsc.2014.0559
DOI: doi:10.1287/trsc.2014.0559
ISSN: 0041-1655
EISSN: 1526-5447
Pages: 1239 - 1260
Type of Material: Journal Article
Journal/Proceeding Title: Transportation Science
Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.