Robust Optimization of the Capacitated Vehicle Routing Problem Under Demand Uncertainty

Vehicle Routing has evolved as one of the core operations research and combinatorial optimization problem classes and covers a wide range of supply chain and production scheduling applications.  In this presentation, we focus on the well-known “Capacitated Vehicle Routing Problem” (CVRP) [1,2].  The CVRP considers a set of geographically scattered customers that should be served by a fleet of identical finite-capacity vehicles. All vehicles are stationed at a depot, and the objective is to select a set of round-trip routes that serve all customer demands at minimum cost. The routes must be designed such that each customer is visited only once by exactly one vehicle, and the cumulative demand serviced by any given vehicle must not exceed the vehicle capacity.

In the deterministic version of the CVRP, the demand of each customer is known a priori. Instances of this problem with up to a few hundred customers can be solved efficiently by branch-and-cut [3,4] or branch-and-cut-and-price [5,6,7] methods.  Here, we consider uncertainty in the customer demands, that is, the demand realizations are unknown at the time the vehicle routes are selected.  In this setting, we aim at choosing robust vehicle routes, i.e., routes that are feasible for any possible realization of the demand vector within a prespecified uncertainty set [8,9,10,11].  Previous efforts to address demand uncertainty in the CVRP [12,13] 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.

We address the more general case where the vector of all customer demands lies in a prespecified (typically non-rectangular) uncertainty set [14].  Suitable uncertainty sets can be derived from statistical estimation procedures, and they produce significantly less conservative solutions in practice. We derive four families of robust CVRP formulations, which are based on Generalized Subtour Elimination constraints, Miller-Tucker-Zemlin constraints, commodity-flow models, and a novel vehicle-to-customer assignment model. All of these formulations are exact, that is, they do not exhibit any over-conservatism beyond the specification of the uncertaint set. We present a branch-and-cut procedure that allows us to solve instances with up to 50 customers to optimality, and we provide computational results that illustrate our approach.

[1] Laporte G. “Fifty years of vehicle routing”, Transportation Science, 43(4):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(1):213-245 (2010).

[3] Lysgaard J., A.N. Letchford and R.W. Eglese. “A new branch-and-cut algorithm for the capacitated vehicle routing problem”. Mathematical Programming, Ser.A 100:423-445 (2004).

[4] Gounaris C.E., P.P. Repoussis, C.D. Tarantilis, and C.A. Floudas "A Hybrid Branch-and-Cut Approach for the Capacitated Vehicle Routing Problem". In: E.N. Pistikopoulos, M.C. Georgiadis and A. Kokossis (Eds.) 21st European Symposium on Computer Aided Process Engineering – ESCAPE 21 (2011).

[5] Fukasawa R., H. Longo, J. Lysgaard, M.P. de Aragao, M. Reis, E. Uchoa and R.F. Werneck. “Robust branch-and-cut-and-price for the capacitated vehicle routing problem”. Mathematical Programming, Ser.A 106:491-511 (2006).

[6] Baldacci R., N. Chrstofides and A. Mingozzi. "An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts". Mathematical Programming, 115:351-385 (2008).

[7] Baldacci R., E. Bartolini, A. Mingozzi and R. Roberti. "An exact solution framework for a broad class of vehicle routing problems". Computational Management Science 7:229-268(2010).

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

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

[10] Lin X., S.L. Janak and C.A. Floudas. “A new robust optimization approach for scheduling under uncertainty: I. Bounded uncertainty“. Computers & Chemical Engineering, 28(6-7):1069-1085 (2004).

[11] Janak S.L., X. Lin and C.A. Floudas. “A new robust optimization approach for scheduling under uncertainty: II. Uncertainty with known probability distribution“. Computers & Chemical Engineering, 31(3):171-195 (2007).

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

[13] 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(2):193-205 (2010).

[14] Gounaris C.E., W. Wiesemann and C.A. Floudas. “Robust Vehicle Routing“. In preparation (2011).