The uncapacitated facility location problem with demand-dependent setup and service costs and customer-choice allocation. (English) Zbl 1163.90587

Summary: We consider a generalization of the uncapacitated facility location problem, where the setup cost for a facility and the price charged for service may depend on the number of customers patronizing the facility. Customers are represented by the nodes of the transportation network, and facilities can be located only at nodes; a customer selects a facility to patronize so as to minimize his (her) expenses (price for service + the part of transportation costs paid by the customer). We assume that transportation costs are paid partially by the service company and partially by customers. The objective is to choose locations for facilities and balanced prices so as to either minimize the expenses of the service company (the sum of the total setup cost and the total part of transportation costs paid by the company), or to maximize the total profit. A polynomial-time dynamic programming algorithm for the problem on a tree network is developed.


90B80 Discrete location and assignment
90C27 Combinatorial optimization
Full Text: DOI


[1] Averbakh, I.; Berman, O.; Drezner, Z.; Wesolowsky, G., The plant location problem with demand-dependent setup costs and centralized allocation, European journal of operational research, 111, 543-554, (1998) · Zbl 0937.90054
[2] Cho, D.C.; Padberg, M.W.; Rao, M.R., On the uncapacitated plant location problem, Mathematics of operations research, 8, 579-612, (1983) · Zbl 0536.90030
[3] Cornuejols, G.; Fisher, M.L.; Nemhauser, G., On the uncapacitated location problem, Annals of discrete mathematics, 1, 163-177, (1977)
[4] Cornuejols, G.; Thizy, J.M., A primal approach to the simple plant location problem, SIAM journal on algebraic and discrete methods, 3, 504-510, (1982) · Zbl 0494.90022
[5] Drezner, Z.; Wesolowsky, G., Location-allocation on a line with demand-dependent costs, European journal of operational research, 90, 444-450, (1996) · Zbl 0913.90199
[6] Drezner, Z.; Wesolowsky, G.O., Review of location-allocation models with demand-dependent costs, Studies in locational analysis, 10, 13-24, (1996) · Zbl 0898.90083
[7] Erlenkotter, D., A dual based procedure for uncapacitated facility location, Operations research, 26, 992-1009, (1978) · Zbl 0422.90053
[8] Kariv, O.; Hakimi, S.L., An algorithmic approach to network location problems. part 2. the p-medians, SIAM journal on applied mathematics, 37, 539-560, (1979) · Zbl 0432.90075
[9] Kolen, A.W.J., Solving covering problems and the uncapacitated plant location problems on trees, European journal of operational research, 12, 266-278, (1983) · Zbl 0508.90035
[10] ()
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.