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 di↵er 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 con- tributions 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 in- stances of the literature and was shown to be significantly better than pre- vious exact algorithms, finding optimal solutions for many instances with up to 200 customers and also for some larger instances. A new set of set of benchmark instances is also proposed.
Type de document :
Article dans une revue
European Journal of Operational Research, Elsevier, 2018, 270 (2), pp.530-543. 〈10.1016/j.ejor.2018.04.009〉
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 7 février 2019 - 14:53:35

Identifiants

Citation

Artur Alves Pessoa, Ruslan Sadykov, Eduardo Uchoa. Enhanced Branch-Cut-and-Price Algorithm for Heterogeneous Fleet Vehicle Routing Problems. European Journal of Operational Research, Elsevier, 2018, 270 (2), pp.530-543. 〈10.1016/j.ejor.2018.04.009〉. 〈hal-01664844〉

Partager

Métriques

Consultations de la notice

230