The Uncapacitated Facility Location Problem with Client Matching

Éric Gourdin (), Martine Labbé () and Gilbert Laporte ()
Additional contact information
Éric Gourdin: SMG and ISRO, Université Libre de Bruxelles, Boulevard du Triomphe, CP210/01, B-1050 Brussels, Belgium
Martine Labbé: SMG and ISRO, Université Libre de Bruxelles, Boulevard du Triomphe, CP210/01, B-1050 Brussels, Belgium
Gilbert Laporte: Centre de Recherche sur les Transports, Université de Montréal, Case Postale 6128, Succursale “Centre-ville,” Montreal, Canada H3C 3J7

Operations Research, 2000, vol. 48, issue 5, 671-685

Abstract: The Uncapacitated Facility Location Problem with Client Matching (LCM) is an extension of the Uncapacitated Facility Location Problem (UFLP), where two clients allocated to a facility can be matched. As in the UFLP, facilities can be opened at any of m predefined locations with given fixed costs, and n clients have to be allocated to the open facilities. In classical location models, the allocation cost is the distance between a client and an open facility. In the LCM, the allocation cost is either the cost of a return trip between the facility and the client, or the length of a tour containing the facility and two clients. The similarities of the LCM with the classical UFLP and the matching problem are exploited to derive valid inequalities, optimality cuts, and polyhedral results. A greedy heuristic and a branch-and-cut algorithm are developed, and several separation procedures are described. Computational experiments confirm the efficiency of the proposed approach.

Keywords: Facilities; location; discrete: client matching; Transportation; vehicle routing: depot location; Programming; integer; branch and cut; Algorithms; cutting plane; facet generation (search for similar items in EconPapers)
Date: 2000
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (10)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.48.5.671.12410 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:48:y:2000:i:5:p:671-685

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().