SADYKOV, Ruslan; PESSOA, Artur Alves; UCHOA, Eduardo

Métadonnées

Afficher la notice complète

Licence d’utilisation du document

SADYKOV, Ruslan
Reformulations based algorithms for Combinatorial Optimization [Realopt]

PESSOA, Artur Alves
Universidade Federal Fluminense [Rio de Janeiro] [UFF]

UCHOA, Eduardo
Universidade Federal Fluminense [Rio de Janeiro] [UFF]

Langue

Communication dans un congrès

Ce document a été publié dans

IFORS 2017 - 21st Conference of the International Federation of Operational Research Societies, 2017-07-17, Quebec City.

Résumé en anglais

In this work we propose a new Branch-Cut-and-Price algorithm for the distance constrained multi-depot vehicle routing problem. The algorithm combines many state-of-the-art techniques known to be efficient for routing problems : bi-directional ng-path based labelling algorithm to solve the pricing problem, generation of limited memory rank-1 cuts with up to 5 rows, reduced cost fixing of arcs, enumeration of elementary routes, and multi-phase strong branching with pseudo-costs. The main contribution of this work is an improvement of the labelling algorithm for the resource constrained shortest path problem with two resources. The labels with similar resource consumption are stored in buckets which are organised in so-called bucket graph. This organisation allows one to significantly reduce the number of dominance checks, exploit route symmetry, and perform reduced cost fixing of bucket arcs. Experiments showed that our algorithm is able to solve to optimality several open instances of the problem with up to 216 customers within the 2 hours time limit. The improvement of the solution time over the recent state-of-the-art algorithm by Contardo and Martinelli (2014) is up to two-three orders of magnitude.< Réduire

Métadonnées

Partager cette publication !

Licence d’utilisation du document

A branch-cut-and-price algorithm for the distance constrained multi-depot vehicle routing problem

Langue

Ce document a été publié dans

Résumé en anglais

URI

Origine

Unités de recherche