(34h) A Unified Branch-Price-and-Cut Framework for Various Classes of Periodic Vehicle Routing Problems

In the literature, lots of efforts have been devoted to heuristic methods for solving the PVRP and its variants. A prominent example is the work of [5], in which the authors proposed a hybrid genetic algorithm that managed to obtain high quality solutions for large scale PVRP instances efficiently. Due to the inherent combinatorial complexity of this problem class, there are sporadic works on exact solution methods. A notable work comes from [4], in which the authors proposed a set partitioning formulation to model the classic PVRP and applied a dual ascent algorithm for solving it to guaranteed optimality. However, most PVRP variants have to-date only been approached by either heuristic methods or branch-and-cut exact algorithms [5,6,7,8,9]. This motivates us to develop a general framework that utilizes a state-of-the-art Branch-Price-and-Cut (BPC) algorithm to address various classes of PVRPs.

More specifically, we focus on the archetypal PVRP and many of its extensions with features of practical importance, such as time windows [6], multiple depots [5], driver consistency [4], optional visits [7], and tactical planning aspects [4, 9]. In our context, these PVRP variants are formulated as a set partitioning model with exponentially many binary variables. Therefore, solving this mixed-integer linear programming model necessitates the employment of the branch-price-and-cut algorithm [10]. In particular, at each node of the branch-and-bound tree, the linear programming relaxation is solved via column generation and cutting planes are added to strengthen the relaxation. In the broader VRP context, columns represent feasible routes, and they are dynamically generated by solving a Shortest Path Problem with Resource Constraints (SPPRC) via dynamic programming. Various techniques, namely variable fixing [12], ng-routes [11], and route enumeration [13] are also consolidated to accelerate the solution of SPPRC. Moreover, in order to further tighten the relaxation space, valid cuts, such as rounded capacity inequalities and limited-memory subset row cuts are incorporated [10].

We evaluate our unified branch-price-and-cut framework on benchmark instances from the literature that cover the PVRP and its aforementioned variants. Our preliminary computational studies verify the success of our framework in managing to solve the various classes of PVRP efficiently and demonstrate its superiority over the branch-and-cut approach in terms of computational tractability.

References:

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

[2]. Campbell, A. M., & Wilson, J. H. (2014). Forty years of periodic vehicle routing. Networks, 63(1), 2-15.

[3]. Fauske, M. F., Mannino, C., & Ventura, P. (2020). Generalized Periodic Vehicle Routing and Maritime Surveillance. Transportation Science, 54(1), 164-183.

[4]. Baldacci, R., Bartolini, E., Mingozzi, A., & Valletta, A. (2011). An exact algorithm for the period routing problem. Operations research, 59(1), 228-241.

[5]. Vidal, T., Crainic, T. G., Gendreau, M., Lahrichi, N., & Rei, W. (2012). A hybrid genetic algorithm for multidepot and periodic vehicle routing problems. Operations Research, 60(3), 611-624.

[6]. Pirkwieser, S., & Raidl, G. R. (2009). Multiple variable neighborhood search enriched with ILP techniques for the periodic vehicle routing problem with time windows. In International Workshop on Hybrid Metaheuristics (pp. 45-59). Springer, Berlin, Heidelberg.

[7]. Rodríguez-Martín, I., Salazar-González, J. J., & Yaman, H. (2019). The periodic vehicle routing problem with driver consistency. European Journal of Operational Research, 273(2), 575-584.

[8]. Larrain, H., Coelho, L. C., Archetti, C., & Speranza, M. G. (2019). Exact solution methods for the multi-period vehicle routing problem with due dates. Computers & Operations Research, 110, 148-158.

[9]. Subramanyam, A., Mufalli, F., Lainez-Aguirre, J. M., F., Pinto, J. M., & Gounaris, C. E. (2020). Robust multi-period vehicle routing under customer order uncertainty. Operations Research. In-press

[10]. Pecin, D., Pessoa, A., Poggi, M. and Uchoa, E. (2017). Improved branch-cut-and price for capacitated vehicle routing. Mathematical Programming Computation, 9(1), pp.61-100.

[11]. Baldacci, R., Mingozzi, A. and Roberti, R. (2011). New route relaxation and pricing strategies for the vehicle routing problem. Operations Research, 59(5), pp.1269-1283.

[12]. Irnich, S., Desaulniers, G., Desrosiers, J. and Hadjar, A. (2010). Path-reduced costs for eliminating arcs in routing and scheduling. INFORMS Journal on Computing, 22(2), pp.297-313.

[13]. Baldacci, R. and Mingozzi, A., (2009). A unified exact method for solving different classes of vehicle routing problems. Mathematical Programming, 120(2), p.347