Altmetric

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

File Description SizeFormat 
AMP_RobustCVRP_Revision1.pdfAccepted version801.44 kBAdobe PDFView/Open
Title: An Adaptive Memory Programming Framework for the Robust Capacitated Vehicle Routing Problem
Authors: Gounaris, CE
Repoussis, PP
Tarantilis, CD
Wiesemann, W
Floudas, CA
Item Type: Journal Article
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.
Issue Date: 11-Dec-2014
Date of Acceptance: 1-May-2014
URI: http://hdl.handle.net/10044/1/52875
DOI: https://dx.doi.org/10.1287/trsc.2014.0559
ISSN: 0041-1655
Publisher: INFORMS
Start Page: 1239
End Page: 1260
Journal / Book Title: Transportation Science
Volume: 50
Issue: 4
Copyright Statement: © 2016 INFORMS
Keywords: Science & Technology
Technology
Operations Research & Management Science
Transportation
Transportation Science & Technology
vehicle routing
robust optimization
adaptive memory programming
STOCHASTIC DEMANDS
OPTIMIZATION APPROACH
TABU SEARCH
TIME WINDOWS
ALGORITHM
UNCERTAINTY
PRICE
PACKING
FLOW
0102 Applied Mathematics
1507 Transportation And Freight Services
Logistics & Transportation
Publication Status: Published
Conference Place: Mykonos, GREECE
Appears in Collections:Imperial College Business School



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

Creative Commonsx