Ruslan Sadykov

We propose a new family of formulations with route-based variables for the split delivery vehicle routing problem with and without time windows. Each formulation in this family is characterized by the maximum number of different demand quantities that can be delivered to a customer during a vehicle visit. As opposed to previous formulations in the literature, the exact delivery quantities are not always explicitly known in this new family. The validity of these formulations is ensured by an exponential set of nonrobust constraints. Additionally, we explore a property of optimal solutions that enables us to determine a minimum delivery quantity based on customer demand and vehicle capacity, and this number is often greater than one. We use this property to reduce the number of possible delivery quantities in our formulations, improving the solution times of the computationally strongest formulation in the family. Furthermore, we propose new variants of nonrobust cutting planes that strengthen the formulations, namely limited-memory subset-row covering inequalities and limited-memory strong k-path inequalities. Finally, we develop a branch-cut-and-price (BCP) algorithm to solve our formulations enriched with the proposed valid inequalities, which resorts to state-of-the-art algorithmic enhancements. We show how to effectively manage the nonrobust cuts when solving the pricing problem that dynamically generates route variables. Numerical results indicate that our formulations and BCP algorithm establish new state-of-the-art results for the variant with time windows, as many benchmark instances with 50 and 100 customers are solved to optimality for the first time. Several instances of the variant without time windows are solved to proven optimality for the first time. Funding: This work was supported by the Conselho Nacional de Desenvolvimento Científico e Tecnológico [Grants 306033/2019-4, 313220/2020-4, and 314088/2021-0], the Région Nouvelle Aquitaine, France [Grant AAPR2020A-2020-8601810], the Agence Nationale de la Recherche [Grant ANR-20-CE40-0021-01], the Fundação de Amparo à Pesquisa do Estado de São Paulo [Grants 13/07375-0, 16/01860-1, and 19/23596-2], and the Paraíba State Research Foundation [Grants 261/2020 and 041/2023]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2022.0085 .

“Nonrobust Strong Knapsack Cuts for Capacitated Location Routing and Related Problems,” by Liguori et al., presents a novel BCP algorithm for the CLRP and for other problems that share a nested knapsack structure. It outperforms existing exact algorithms in the literature, making it a powerful tool for solving instances with a large number of depot locations. A key methodological contribution is the introduction of RLKCs, a family of nonrobust cuts derived from the “outer” knapsack constraints. These cuts are strong in the sense that they contain all facets of the master knapsack polytope, dominating the cover cuts by Dabia et al. (2019) . By exploring their monotonicity and superadditivity properties, it is possible to adapt the labeling algorithm for handling RLKCs efficiently. The overall positive impact of RLKCs on the BCP performance varies depending on the problem and instance characteristics, but they have proven particularly effective for CLRP instances with tight depot capacities, making the final BCP algorithm more reliable.