Enhanced Branch-Cut-and-Price Algorithm for Heterogeneous Fleet Vehicle Routing Problems

Artur Alves Pessoa 1 Ruslan Sadykov 2 Eduardo Uchoa 1
2 Realopt - Reformulations based algorithms for Combinatorial Optimization
LaBRI - Laboratoire Bordelais de Recherche en Informatique, IMB - Institut de Mathématiques de Bordeaux, Inria Bordeaux - Sud-Ouest
Abstract : This paper considers a family of Vehicle Routing Problem (VRP) variants that generalize the classical Capacitated VRP by taking into account the possibility that vehicles differ by capacity, costs, depot allocation, or even by the subset of customers that they can visit. This work proposes a branch-cut-and-price algorithm that adapts advanced features found in the best performing exact algorithms for homogeneous fleet VRPs. The original contributions include: (i) the use of Extended Capacity Cuts, defined over a pseudo-polynomially large extended formulation, together with Rank-1 Cuts, defined over the Set Partitioning Formulation; (ii) the concept of vehicle-type dependent memory for Rank-1 Cuts; and (iii) A new family of lifted Extended Capacity Cuts that takes advantage of the vehicle-type dependent route enumeration. The algorithm was extensively tested in instances of the literature and was shown to be significantly better than previous exact algorithms, finding optimal solutions for many instances with up to 200 customers and also for some larger instances. Several new best solutions were found too.
Type de document :
Rapport
[Research Report] Cadernos do LOGIS 2017/3, Universidade Federal Fluminense. 2017
Liste complète des métadonnées

https://hal.inria.fr/hal-01664844
Contributeur : Ruslan Sadykov <>
Soumis le : vendredi 15 décembre 2017 - 11:38:22
Dernière modification le : jeudi 11 janvier 2018 - 01:49:30

Identifiants

  • HAL Id : hal-01664844, version 1

Collections

Citation

Artur Alves Pessoa, Ruslan Sadykov, Eduardo Uchoa. Enhanced Branch-Cut-and-Price Algorithm for Heterogeneous Fleet Vehicle Routing Problems. [Research Report] Cadernos do LOGIS 2017/3, Universidade Federal Fluminense. 2017. 〈hal-01664844〉

Partager

Métriques

Consultations de la notice

34