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

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 and a metaheuristic that is a hybrid of the greedy randomized adaptive search procedure (GRASP) and the evolutionary local search (ELS) proposed in [18]. We perform computational experiments on instances from the literature to demonstrate the performance of our algorithms.
Document type :
Journal articles
Liste complète des métadonnées

https://hal.inria.fr/hal-01105383
Contributor : Nathalie Bostel <>
Submitted on : Tuesday, January 20, 2015 - 11:31:57 AM
Last modification on : Wednesday, April 17, 2019 - 12:15:34 PM

Identifiers

Collections

Citation

Minh Hoang Ha, Nathalie Bostel, André Langevin, Rousseau Louis-Martin. An exact algorithm and a metaheuristic for the generalized vehicle routing problem with flexible fleet size. Computers and Operations Research, Elsevier, 2014, 43, pp.9-19. ⟨10.1016/j.cor.2013.08.017⟩. ⟨hal-01105383⟩

Share

Metrics

Record views

119