The uncapacitated facility location problem with client matching
成果类型：
Article
署名作者：
Gourdin, E; Labbé, M; Laporte, G
署名单位：
Universite Libre de Bruxelles; Universite Libre de Bruxelles; Universite de Montreal
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.48.5.671.12410
发表日期：
2000
页码：
671-685
关键词：
摘要：
The Uncapacitated Facility Location Problem,vith 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.