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 our specialized branch-and-bound algorithm.


    Access

    Access via TIB

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

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




    Publication date :

    2016




    Type of media :

    Article (Journal)


    Type of material :

    Print


    Language :

    English



    Classification :

    Local classification TIB:    770/1935/7000
    BKL:    55.80 / 55.80 Verkehrswesen, Transportwesen: Allgemeines



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

    Gendron, Bernard / Khuong, Paul-Virak / Semet, Frédéric | British Library Online Contents | 2016



    The Dynamic Uncapacitated Hub Location Problem

    Contreras, I. / Cordeau, J.-F. / Laporte, G. | British Library Online Contents | 2011


    The Dynamic Uncapacitated Hub Location Problem

    Contreras, Ivan | Online Contents | 2011


    Uncapacitated Facility Location with Allocation of Matched and Unmatched Clients

    Gourdin, E. / Labbe, M. / Laporte, G. et al. | British Library Conference Proceedings | 1997