Branch-cut-and-price algorithms for the clustered and generalized vehicle routing problems

• Ano de defesa: 2023
• Autor(a) principal: Antunes, Matheus Freitas Soares
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: eng
• Palavras-chave em Português: Vehicle routing; Column generation; Branch-cut-and-price; Modeling; CVRP; CluVRP; GVRP; Clustered routes; Roteamento; Modelagem; Veículo automotivo; Grafo; Roteamento de veículos; Geração de colunas; Rotas clusterizadas
• Link de acesso: http://app.uff.br/riuff/handle/1/29968

[EN] The Clustered Vehicle Routing Problem (CluVRP) and the Generalized Vehicle Routing Problem (GVRP) are variants of the classic Capacitated Vehicle Routing Problem (CVRP) 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 work proposes a model for GVRP, together with new reduction tests. Then, three different models for CluVRP are proposed and discussed. GVRP’s model had superior performance compared to other exact methods in the literature. 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 and 240 clusters, much larger than those that could be solved by previous exact algorithms