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.
Type de document :
Article dans une revue
Computers and Operations Research, Elsevier, 2014, 43, pp.9-19. 〈10.1016/j.cor.2013.08.017〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01105383
Contributeur : Nathalie Bostel <>
Soumis le : mardi 20 janvier 2015 - 11:31:57
Dernière modification le : mercredi 16 mai 2018 - 11:48:03

Identifiants

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〉

Partager

Métriques

Consultations de la notice

104