(518h) Solving the Robust Vehicle Routing Problem Via Adaptive Memory Programming

Vehicle Routing constitutes one of the key decision areas in supply chain optimization.  We address the Capacitated Vehicle Routing Problem (CVRP) [1, 2], which seeks the minimum cost depot-returning routes for a fleet of capacitated vehicles to serve a set of geographically scattered customers.  We consider uncertainty in the customer demands, and we aim at identifying vehicle routes that are robust-feasible, i.e., routes that are feasible for any possible realization of the demand vector within a prespecified uncertainty set [3, 4, 5].

Earlier efforts to address demand uncertainty in the CVRP [6, 7] have focused on problems where each customer demand can attain its worst-case individually, independent of the other customers.  Problems of this type can be solved via deterministic CVRP methods, but their solutions may be very conservative.  A recent contribution [8] addressed the more general case where the vector of all customer demands lies in a prespecified (typically non-rectangular) uncertainty set.  Four families of robust CVRP formulations that do not exhibit any over-conservatism beyond the specification of the uncertainty set were presented, and a branch-and-cut procedure was developed that can solve instances with up to 50 customers to guaranteed optimality.

In this presentation, we propose an Adaptive Memory Programming (AMP) metaheuristic to push the envelope in terms of size of instances that can be addressed.  AMP is a general-purpose metaheuristic framework that has been successfully applied to a range of difficult combinatorial optimization problems in the vehicle routing domain [9, 10, 11, 12].  Our framework incorporates novel methods to identify, select and combine elite solution components, and employs a sophisticated Tabu Search algorithm to conduct search in both the robust-feasible and robust-infeasible solution spaces.  Two broad classes of polyhedral uncertainty sets for which robust-feasibility can be checked efficiently are considered.  Results on benchmark data sets involving up to 483 customers are reported, including new best solutions for a total of 123 instances.

[1] Laporte G. "Fifty years of vehicle routing", Transportation Science, 43:408-416 (2009).

[2] Baldacci R., P. Toth and D. Vigo. "Exact algorithms for routing problems under vehicle capacity constraints", Annals of Operations Research, 175:213-245 (2010).

[3] Ben-Tal A. and A. Nemirovski. "Robust convex optimization". Mathematics of Operations Research, 23:769-805 (1998).

[4] Bertsimas D. and M. Sim. "The price of robustness". Operations Research, 52:35-53 (2004).

[5] Bertsimas D., D.B. Brown and C. Caramanis. "Theory and applications of robust optimization". SIAM Review, 53:464-501 (2011).

[6] Sungur I., F. Ordonez and M. Dessouky. "A robust optimization approach for the capacitated vehicle routing problem with demand uncertainty". IIE Transactions, 40:509-523 (2008).

[7] Sungur I., Y. Ren, F. Ordonez, M. Dessouky and H. Zhong. "A Model and Algorithm for the Courier Delivery Problem with Uncertainty". Transportation Science, 44:193-205 (2010).

[8] Gounaris C.E, W. Wiesemann and C.A. Floudas. "The Robust Capacitated Vehicle Routing Problem Under Demand Uncertainty".  Operations Research, Articles In Advance (2013), DOI 10.1287/opre.1120.1136.

[9] Repoussis P.P. and C.D. Tarantilis, "Solving the Fleet Size and Mix Vehicle Routing Problem with Time Windows via Adaptive Memory Programming", Transportation Research Part C, 18:695-712 (2010).

[10] Rochat Y. and E.D. Taillard, "Probabilistic Diversification and Intensification in Local Search for Vehicle Routing", Journal of Heuristics, 1:147-167 (1995).

[11] Tarantilis C.D. and C.T. Kiranoudis, "Boneroute: An Adaptive Memory-Based Method for Effective Fleet Management", Annals of Operations Research, 115:227-241 (2002)

[12] Tarantilis C.D., "Solving the Vehicle Routing Problem with Adaptive Memory Programming Methodology", Computers & Operations Research, 32:2309-2327 (2005).