(52d) Solving Robust Vehicle Routing Via a Branch-Price-and-Cut Approach

The Vehicle Routing Problem (VRP) is one of the most highly studied combinatorial optimization problems in the area of Supply Chains and Logistics [1]. It aims to determine a set of optimal routes for vehicles to serve customers such that all known demands are satisfied and in a way such that all vehicle capacities are respected. The Branch-Price-and-Cut (BP&C) method has been gradually accepted as the state-of-the-art algorithm to tackle deterministic VRP and its variants. The BP&C algorithm is sophisticated in a way that the linear relaxation at every node in the branch-and-bound tree is solved via Column Generation (CG) and cutting planes are added to strengthen the relaxation. In our VRP context, columns denote feasible routes, and they are generated by solving a Shortest Path Problem with Resource Constraints (SPPRC) via a labeling algorithm [2]. It has been shown that Rounded Capacity Inequalities (RCI) [3] and limited-memory subset row cuts [4] can effectively tighten the linear model in the deterministic setting.

Recently, VRP under demand uncertainty [5][6] 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) [7] and BP&C in order to develop an effective approach for robust VRP under demand uncertainty. When extending BP&C for a robust VRP, the optimal routing design has to be robust feasible. There are two different perspectives for how to achieve this. The first and most intuitive way is to generate deterministically feasible routes via solving a standard SPPRC and enforce robust feasibility via robust RCI [6]. This approach is very generic and can be ideally applied under any uncertainty set selection. Another approach is to directly generate robust feasible columns. This necessitates an efficient algorithm to exactly solve a robust SPPRC, which can be a tough proposition, since this problem is in general strongly NP-hard [8]. Recently, Pessoa et al. [9] showed that for some special structure uncertainty sets (e.g., Γ uncertainty set [10]), robust columns can be generated via solving a sequence of polynomially many deterministic SPPRC.

In this work, we first evaluate the two approaches and compare their performances using several well-known uncertainty sets, including the Γ set and budget set [6] among others. The comparison studies are mainly focused on the computational performance and theoretical limitations to different uncertainty sets. In addition, we consider combining the two techniques together and generating robust feasible columns in the CG stage as well as separating robust cuts in the cut generation stage to further tighten the linear relaxation.

References:

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

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

[3] 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.

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

[5] 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.

[6] 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.

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

[8] Alves Pessoa, A., Di Puglia Pugliese, L., Guerriero, F. and Poss, M., 2015. Robust constrained shortest path problems under budgeted uncertainty. Networks, 66(2), pp.98-111.

[9] Pessoa, A., Poss, M., Sadykov, R. and Vanderbeck, F., 2018, June. Solving the robust CVRP under demand uncertainty. In ODYSSEUS 2018-7th International Workshop on Freight Transportation and Logistics.

[10] Bertsimas, D. and Sim, M., 2003. Robust discrete optimization and network flows. Mathematical programming, 98(1-3), pp.49-71.