×

zbMATH — the first resource for mathematics

Single-allocation ordered median hub location problems. (English) Zbl 1231.90271
Summary: The discrete ordered median location model is a powerful tool in modeling classic and alternative location problems that have been applied with success to a large variety of discrete location problems. Nevertheless, although hub location models have been analyzed from the sum, maximum and coverage point of views, as far as we know, they have never been considered under an alternative unifying point of view. In this paper we consider new formulations, based on the ordered median objective function, for hub location problems with new distribution patterns induced by the different users’ roles within the supply chain network. This approach introduces some penalty factors associated with the position of an allocation cost with respect to the sorted sequence of these costs. First we present basic formulations for this problem, and then develop stronger formulations by exploiting properties of the model. The performance of all these formulations is compared by means of a computational analysis.

MSC:
90B80 Discrete location and assignment
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alumur, S.; Kara, B.Y., Network hub location problems: the state of the art, European journal of operational research, 190, 1, 1-21, (2008) · Zbl 1146.90455
[2] Berman, O; Kalcsics, J; Krass, D; Nickel, S, The ordered gradual covering location problem on a network, Discrete applied mathematics, 157, 18-28, 3689-3707, (2009) · Zbl 1228.90015
[3] Boland, N.; Domínguez-Marín, P.; Nickel, S.; Puerto, J., Exact procedures for solving the discrete ordered Median problem, Computers and operations research, 33, 3270-3300, (2006) · Zbl 1113.90099
[4] Boland, N.; Krishnamoorthy, M.; Ernst, A.T.; Ebery, J., Preprocessing and cutting for multiple allocation hub location problems, European journal of operational research, 155, 3, 638-653, (2004) · Zbl 1049.90034
[5] Bollapragada, R.; Li, Y.; Rao, U.S., Budget-constrained, capacitated hub location to maximize expected demand coverage in fixed-wireless telecommunication networks, INFORMS journal on computing, 18, 4, 422-432, (2006) · Zbl 1241.90022
[6] Cánovas, L.; García, S.; Labbé, M.; Marín, A., A strengthened formulation for the simple plant location problem with order, Operations research letters, 35, 2, 141-150, (2007) · Zbl 1149.90363
[7] Cánovas, L.; García, S.; Marín, A., Solving the uncapacitated multiple allocation hub location problem by means of a dual-ascent technique, European journal of operational research, 179, 3, 990-1007, (2007) · Zbl 1163.90595
[8] Campbell, J.F., Hub location and the p-hub Median problem, Operations research, 44, 6, 923-935, (1996) · Zbl 0879.90127
[9] Campbell JF, Ernst A, Krishnamoorthy M. Hub location problems. In: Facility location. Berlin: Springer; 2002. p. 373-407. · Zbl 1061.90069
[10] Campbell, A.M.; Lowe, T.J.; Zhang, L., The p-hub center allocation problem, European journal of operational research, 176, 2, 819-835, (2007) · Zbl 1103.90057
[11] Contreras, I.; Díaz, J.A.; Fernández, E., Lagrangian relaxation for the capacitated hub location problem with single assignment, OR spectrum, 31, 3, 483-505, (2009) · Zbl 1163.90617
[12] Elloumi, S.; Labbé, M.; Pochet, Y., A new formulation and resolution method for the p-center problem, INFORMS journal on computing, 16, 1, 84-94, (2004) · Zbl 1239.90103
[13] Ernst, A.T.; Krishnamoorthy, M., Efficient algorithms for the uncapacitated single allocation p-hub Median problem, Location science, 4, 3, 139-154, (1996) · Zbl 0927.90065
[14] Ernst, A.T.; Krishnamoorthy, M., Solution algorithms for the capacitated single allocation hub location problem, Annals of operations research, 86, 141-159, (1999) · Zbl 0918.90096
[15] Espejo, I.; Marín, A.; Puerto, J.; Rodríguez-Chía, A.M., A comparison of formulations and solution methods for the minimum-envy location problem, Computers and operations research, 36, 1966-1981, (2009) · Zbl 1179.90206
[16] Fonseca, MC; García-Sánchez, A; Ortega-Mier, M; Saldanha-da-Gama, F, A stochastic bi-objective location model for strategic reverse logistics, Top, 18, 1, 158-184, (2010) · Zbl 1201.90113
[17] Hamacher, H.; Labbé, M.; Nickel, S.; Sonneborn, T., Adapting polyhedral properties from facility to hub location problems, Discrete applied mathematics, 145, 1, 104-116, (2004) · Zbl 1058.90033
[18] Kalcsics, J.; Nickel, S.; Puerto, J.; Rodríguez-Chía, A.M., Distribution systems design with role dependent objectives, European journal of operational research, 202, 491-501, (2010) · Zbl 1175.90264
[19] Kalcsics, J; Nickel, S; Puerto, J; Rodríguez-Chía, AM, The ordered capacitated facility location problem, Top, 18, 1, 203-222, (2009) · Zbl 1201.90118
[20] Kara, B.Y.; Tansel, B.C., On the single-assignment p-hub center problem, European journal of operational research, 125, 3, 648-655, (2000) · Zbl 0971.90042
[21] Kara, B.Y.; Tansel, B.C., The single-assignment hub covering problem: models and linearizations, Journal of the operational research society, 54, 1, 59-64, (2003) · Zbl 1088.90035
[22] Kolen, A., Solving covering problems and the uncapacitated plant location problem on trees, European journal of operational research, 12, 3, 266-278, (1983) · Zbl 0508.90035
[23] Kratica, J.; Stanimirovic, Z., Solving the uncapacitated multiple allocation p-hub center problem by genetic algorithm, Asia-Pacific journal of operational research, 23, 4, 425-437, (2006) · Zbl 1202.90175
[24] Labbé, M.; Yaman, H., Projecting the flow variables for hub location problems, Networks, 44, 2, 84-93, (2004) · Zbl 1055.90045
[25] Labbé, M.; Yaman, H., Solving the hub location problem in a star-star network, Networks, 51, 1, 19-33, (2008) · Zbl 1146.90035
[26] Labbé, M.; Yaman, H.; Gourdin, E., A branch and cut algorithm for hub location problems with single assignment, Mathematical programming, 102, 2, 371-405, (2005) · Zbl 1079.90080
[27] Marín, A., Formulating and solving splittable capacitated multiple allocation hub location problems, Computers and operations research, 32, 12, 3093-3109, (2005) · Zbl 1146.90458
[28] Marín, A., Uncapacitated Euclidean hub location: strengthened formulation, new facets and a relax-and-cut algorithm, Journal of global optimization, 33, 3, 393-422, (2005) · Zbl 1093.90022
[29] Marín, A.; Cánovas, L.; Landete, M., New formulations for the uncapacitated multiple allocation hub location problem, European journal of operational research, 172, 1, 274-292, (2006) · Zbl 1116.90071
[30] Marín, A.; Nickel, S.; Puerto, J.; Velten, S., A flexible model and efficient solution strategies for discrete location problems, Discrete applied mathematics, 157, 5, 1128-1145, (2009) · Zbl 1163.90609
[31] Meyer, T.; Ernst, A.T.; Krishnamoorthy, M., A 2-phase algorithm for solving the single allocation p-hub center problem, Computers and operations research, 36, 12, 3143-3151, (2009) · Zbl 1176.90360
[32] Nickel, S.; Puerto, J., Location theory—a unified approach, (2005), Springer · Zbl 1229.90001
[33] Ogryczak, W.; Tamir, A., Minimizing the sum of the k largest functions in linear time, Information processing letters, 85, 117-122, (2003) · Zbl 1050.68155
[34] O’Kelly, M.E., A quadratic integer problem for the location of interacting hub facilities, European journal of operational research, 32, 393-404, (1987) · Zbl 0627.90030
[35] Puerto, J.; Fernández, F.R., Geometrical properties of the symmetrical single facility location problem, Journal of nonlinear and convex analysis, 1, 3, 321-342, (2000) · Zbl 0974.90009
[36] Rodríguez-Chía, A.M.; Nickel, S.; Puerto, J.; Fernández, F.R., A flexible approach to location problems, Mathematical methods of operations research, 51, 69-89, (2000) · Zbl 1031.90009
[37] Rodríguez-Martín, I.; Salazar-González, J.J., Solving a capacitated hub location problem, European journal of operational research, 184, 2, 468-479, (2008) · Zbl 1149.90317
[38] Tan, P.Z.; Kara, B.Y., A hub covering model for cargo delivery systems, Networks, 49, 1, 28-39, (2007) · Zbl 1131.90422
[39] Wagner, B., Model formulations for hub covering problems, Journal of the operational research society, 59, 7, 932-938, (2008) · Zbl 1144.90340
[40] Yaman, H., Polyhedral analysis for the uncapacitated hub location problem with modular arc capacities, SIAM journal on discrete mathematics, 19, 2, 501-522, (2005) · Zbl 1122.90098
[41] Zhou, G.; Min, H.; Gen, M., The balanced allocation of customers to multiple distribution centers in a supply chain network: a genetic algorithm approach, Computers and industrial engineering, 43, 251-261, (2002)
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.