A unified exact approach for Clustered and Generalized Vehicle Routing Problems

• Published in: Computers & operations research 2023-01, Vol.149, p.106040, Article 106040
• Main Authors: Freitas, Matheus, Silva, João Marcos Pereira, Uchoa, Eduardo
• Format: Article
• Language: English
• Subjects: Column generation; Modeling; Vehicle routing
• ISSN: 0305-0548; 1873-765X
• DOI: 10.1016/j.cor.2022.106040

The Clustered Vehicle Routing Problem (CluVRP) and the Generalized Vehicle Routing Problem (GVRP) are variants of the classic capacitated vehicle routing where customers are partitioned into clusters. In the first problem, all customers in the same cluster must be visited in sequence by a single route. In the second problem, all customers in a cluster are served by visiting a single customer in it. This article proposes a model for GVRP, together with new reduction tests. Then, three different models for CluVRP are proposed and discussed. The best performing CluVRP model is actually a reduction of the problem to a GVRP. All models are implemented and solved by the branch-cut-and-price algorithm in the VRPSolver package. The computational results show that the new approach can solve instances with up to 1,200 customers, much larger than those that could be solved by previous exact algorithms. •We propose exact methods for clustered and generalized Vehicle Routing Problems.•Methods are defined as VRPSolver models.•The best clustered VRP model is an original reduction to a generalized VRP.•Extensive experiments obtain results that are significantly better than the literature.