A Lagrangian-Based Branch-and-Bound Algorithm for the Two-Level Uncapacitated Facility Location Problem with Single-Assignment Constraints

Abstract : We consider the two-level uncapacitated facility location problem with single-assignment constraints (TUFLP-S), a problem that arises in industrial applications in freight transportation and telecommunications. We present a new Lagrangian relaxation approach for the TUFLP-S, based on solving a single-level uncapacitated facility location problem (UFLP) as the Lagrangian subproblem. We also develop a Lagrangian heuristic that includes a mixed-integer programming–based large neighborhood search heuristic exploring neighborhoods by solving a series of small UFLPs. The dual and primal bounds thus obtained are used within an enumerative algorithm that implements specialized branching rules. Our computational experiments on instances derived from an industrial application in freight transportation as well as on large, hard, artificial instances confirm the efficiency of the authors specialized branch-and-bound algorithm.
Type de document :
Article dans une revue
Transportation Science, INFORMS, 2016, 50 (4), pp.1286 - 1299. 〈10.1287/trsc.2016.0692〉
Liste complète des métadonnées

Littérature citée [21 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01663639
Contributeur : Frédéric Semet <>
Soumis le : jeudi 14 décembre 2017 - 10:27:12
Dernière modification le : mardi 3 juillet 2018 - 11:41:13

Fichier

CIRRELT-2013-21.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Bernard Gendron, Paul-Virak Khuong, Frédéric Semet. A Lagrangian-Based Branch-and-Bound Algorithm for the Two-Level Uncapacitated Facility Location Problem with Single-Assignment Constraints. Transportation Science, INFORMS, 2016, 50 (4), pp.1286 - 1299. 〈10.1287/trsc.2016.0692〉. 〈hal-01663639〉

Partager

Métriques

Consultations de la notice

172

Téléchargements de fichiers

89