A unified exact approach for Clustered and Generalized Vehicle Routing Problems. (January 2023)

• Record Type: Journal Article
• Authors: Freitas, Matheus; Silva, João Marcos Pereira; Uchoa, Eduardo
• Is Part Of: Computers & operations research. Volume 149(2023)
• Publication Date: 2023-01
• Subjects: Vehicle routing -- Column generation -- Modeling; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2022.106040
• Languages: English
• ISSNs: 0305-0548

Abstract

Abstract: 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. Highlights: 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.