(44f) A Branch-Price-and-Cut Approach for Robust Optimization in Vehicle Routing

The Vehicle Routing Problem (VRP) is one of the most highly studied combinatorial optimization problems [1-2] in the area of Supply Chains and Logistics. It aims to determine a set of minimum-cost routes for vehicles to serve customers such that all known demands are satisfied and in a way such that all vehicle capacities are respected. Recently, VRP under demand uncertainty [3-4] has attracted considerable attention. It is motivated by the fact that customer demands are often not readily available at the time the distributor needs to commit to some routing plan. In this work, we combine Robust Optimization (RO) [5] and the Branch-Price-and-Cut (BP&C) optimization method for mixed-integer linear programming, in order to develop a BP&C approach for robust VRP under demand uncertainty.

Traditionally, the Branch-and-Cut (B&C) approach was the most popular method for solving deterministic VRPs; however, BP&C has been gradually accepted as the state-of-the-art algorithm to do so, and is especially advantageous for large size and complex, “rich” VRP variants [6]. The BP&C algorithm is a sophisticated combination of Column Generation (CG) and cut generation in the context of Branch-and-Bound (B&B). The linear relaxation of every node in the whole B&B tree is solved by CG and cutting planes are added to strengthen the relaxation. In our VRP case, columns denote feasible routes, and they are generated by solving the Shortest Path Problems with Resource Constraints (SPPRC) using a Dynamic Programming (DP) technique [7-8]. It has been shown that Rounded Capacity Cuts (RCC) [9] and Limited-Memory Subset Row Cuts [10] can efficiently tighten the linear model in the deterministic setting.

In the context of VRPs, RO can be a promising approach to deal with uncertainty in customer demands, guaranteeing the immunity of the optimal solution from all demand realization in a given uncertainty set. Though some progress has been made in the past via a B&C approach for robust VRP under demand uncertainty [4], these algorithms cannot address VRP instances of a large size and cannot be readily extended to VRP variants such as the Heterogeneous Vehicle Routing Problem, among others.

In this study, we propose for the first time a BP&C approach for robust VRP under demand uncertainty. In our approach, the columns that are dynamically added denote robust feasible routes under a postulated demand uncertainty set. Since our computational experience suggested that solving SPPRC under uncertainty to guaranteed optimality is very expensive, and in order to alleviate the burden in the DP phase, we propose a Tabu Search method [11] to heuristically generate robust feasible columns, and we resort to the exact solution of SPPRC instances only when our heuristic fails. We also add robust RCC [4] to tighten the relaxations at each node of the B&B tree. To the best of our knowledge, BP&C and RO are incorporated together for the first time, enabling us to tackle robust VRPs under uncertainty from a totally new perspective.

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

[2]. Baldacci, R., Toth, P., & Vigo, D. (2007). Recent advances in vehicle routing exact algorithms. 4OR: A Quarterly Journal of Operations Research, 5(4), 269-298.

[3]. Sungur, I., Ordónez, F., & Dessouky, M. (2008). A robust optimization approach for the capacitated vehicle routing problem with demand uncertainty. IIE Transactions, 40(5), 509-523.

[4]. Gounaris, C. E., Wiesemann, W., & Floudas, C. A. (2013). Demand Uncertainty The Robust Capacitated Vehicle Routing Problem Under Demand Uncertainty. Operations Research, 61(3), 677–693.

[5]. Ben-Tal, A., El Ghaoui, L., & Nemirovski, A. (2009). Robust optimization. Princeton University Press.

[6]. Toth, P., & Vigo, D. (Eds.). (2014). Vehicle routing: problems, methods, and applications. Society for Industrial and Applied Mathematics.

[7]. Irnich, S., Desaulniers, G., & others. (2005). Shortest path problems with resource constraints. Column Generation, 33–65.

[8]. Pecin, D. G. (2014). Exact Algorithms for the Capacitated Vehicle Routing Problem (Doctoral dissertation, PUC-Rio).

[9]. Fukasawa, R., Lysgaard, J., Poggi de Aragão, M., Reis, M., Uchoa, E., & Werneck, R. (2004). Robust branch-and-cut-and-price for the capacitated vehicle routing problem. Integer programming and combinatorial optimization, 11-17.

[10]. Pecin, D., Pessoa, A., Poggi, M., & Uchoa, E. (2014, June). Improved branch-cut-and-price for capacitated vehicle routing. In International Conference on Integer Programming and Combinatorial Optimization (pp. 393-403). Springer International Publishing.

[11]. Desaulniers, G., Lessard, F., & Hadjar, A. (2008). Tabu Search, Partial Elementarity, and Generalized k -Path Inequalities for the Vehicle Routing Problem with Time Windows. Transportation Science, 42(3), 387–404.