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

The authors 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 the authors 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. The authors present two classes of uncertainty sets for which route feasibility can be established much more efficiently. Although the authors discuss the implementation in the context of the AMP framework, the authors 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, the authors obtain new best solutions for a total of 123 benchmark instances.

Language

  • English

Media Info

Subject/Index Terms

Filing Info

  • Accession Number: 01631015
  • Record Type: Publication
  • Files: TRIS
  • Created Date: Mar 7 2017 4:11PM