An exact algorithm and a metaheuristic for the generalized vehicle routing problem with flexible fleet size

Abstract

Abstract The generalized vehicle routing problem (GVRP) involves finding a minimum- length set of vehicle routes passing through a set of clusters, where each cluster contains a number of vertices, such that the tour includes exactly one vertex from each cluster and satisfies capacity constraints. We consider a version of the GVRP where the number of vehicles is a decision variable. This paper introduces a new mathematical formulation based on a two-commodity flow model. We solve the problem using a branch-and-cut algorithm ...