×

zbMATH — the first resource for mathematics

The discrete facility location problem with balanced allocation of customers. (English) Zbl 1207.90071
Summary: We consider a discrete facility location problem where the difference between the maximum and minimum number of customers allocated to every plant has to be balanced. Two different Integer Programming formulations are built, and several families of valid inequalities for these formulations are developed. Preprocessing techniques which allow to reduce the size of the largest formulation, based on the upper bound obtained by means of an ad hoc heuristic solution, are also incorporated. Since the number of available valid inequalities for this formulation is exponential, a branch-and-cut algorithm is designed where the most violated inequalities are separated at every node of the branching tree. Both formulations, with and without the improvements, are tested in a computational framework in order to discriminate the most promising solution methods. Difficult instances with up to 50 potential plants and 100 customers, and largest easy instances, can be solved in one CPU hour.

MSC:
90B80 Discrete location and assignment
90C10 Integer programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Erkut, E., Inequality measures for location problems, Location science, 1, 199-217, (1993) · Zbl 0923.90101
[2] Berman, O.; Kaplan, E.H., Equity maximizing facility location schemes, Transportation science, 24, 137-144, (1990) · Zbl 0705.90047
[3] Drezner, T.; Drezner, Z.; Guyse, J., Equitable service by a facility: minimizing the gini coefficient, Computers and operations research, 36, 3240-3246, (2009) · Zbl 1176.90353
[4] Marsh, M.T.; Schilling, D.A., Equity measurement in facility location analysis: A review and framework, European journal of operations research, 74, 1-17, (1994) · Zbl 0800.90631
[5] Eiselt, H.A.; Laporte, G., Objectives in location problems, () · Zbl 0917.90225
[6] Marín, A.; Nickel, S.; Velten, S., An extended covering model for flexible discrete and equity location problems, Mathematical methods of operations research, 71, 125-163, (2010) · Zbl 1193.49036
[7] Marín, A.; Nickel, S.; Puerto, J.; Velten, S., A flexible model and efficient solution strategies for discrete location problems, Discrete applied mathematics, 157, 1128-1145, (2009) · Zbl 1163.90609
[8] Espejo, I.; Marín, A.; Puerto, J.; Rodríguez-Chía, A., A comparison of formulations and solution methods for the minimum-envy location problem, Computers and operations research, 36, 1966-1981, (2009) · Zbl 1179.90206
[9] Berger, P.D.; Bechwati, N.N., The allocation of promotion budget to maximize customer equity, Omega, 29, 49-61, (2001)
[10] Berman, O.; Drezner, Z.; Tamir, A.; Wesolowsky, G.O., Optimal location with equitable loads, Annals of operations research, 167, 307-325, (2009) · Zbl 1163.90591
[11] Kalcsics, J.; Nickel, S.; Puerto, P.; Rodríguez-Chía, A., The ordered capacitated facility location problem. top, 18, 203-222, (2010) · Zbl 1201.90118
[12] Kalcsics, J.; Nickel, S.; Schröder, M., Towards a unified territory design approach – applications, algorithms and GIS integration, Top, 13, 1-56, (2005) · Zbl 1072.90058
[13] Hansen, P.; Thisse, J.F., Outcomes of voting and planning, Journal of public economics, 16, 1-15, (1981)
[14] Carrizosa, E.; Conde, E.; Muñoz-Márquez, M.; Puerto, J., Simpson points in planar problems with locational constraints. the polyhedral-gauge case, Mathematics of operations research, 22, 291-300, (1997) · Zbl 0883.90076
[15] Hakimi, S.L., Locations with spatial interactions: competitive locations and games, () · Zbl 0747.90057
[16] Labbé, M., Outcomes of voting and planning in single facility location problems, European journal of operations research, 20, 299-313, (1985) · Zbl 0567.90022
[17] Wagner, J.L.; Falkson, L.M., The optimal nodal location of public facilities with price-sensitive demand, Geographical analysis, 7, 69-83, (1975)
[18] Contreras, I.; Fernández, E.; Marín, A., Lagrangian bounds for the optimum communication spanning tree problem, Top, 18, 140-157, (2010) · Zbl 1201.90044
[19] Marín, A., Discrete location for bundled demand points, Top, 18, 242-256, (2010) · Zbl 1201.90121
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.