Titre :

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

Auteur(s) :

Gendron, Bernard [Auteur]
Centre Interuniversitaire de Recherche sur les Réseaux d'Entreprise, la Logistique et le Transport [CIRRELT]
Khuong, Paul-Virak [Auteur]
Centre Interuniversitaire de Recherche sur les Réseaux d'Entreprise, la Logistique et le Transport [CIRRELT]
Semet, Frédéric [Auteur]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Integrated Optimization with Complex Structure [INOCS]

Titre de la revue :

Transportation Science

Pagination :

1286 - 1299

Éditeur :

INFORMS

Date de publication :

2016-06

ISSN :

0041-1655

Mot(s)-clé(s) en anglais :

Telecommunications
Plant location
Neighborhoods
Mixed integer programming
Heuristic methods
Freight traffic
Branch and bound algorithms

Discipline(s) HAL :

Computer Science [cs]/Operations Research [math.OC]

Résumé en anglais : [en]

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 ...
Lire la suite >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.Lire moins >

Langue :

Anglais

Comité de lecture :

Oui

Audience :

Internationale

Vulgarisation :

Non

Collections :

• Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL