×

A cost allocation problem arising in hub-spoke network systems. (English) Zbl 1061.90015

Summary: This paper studies a cost allocation problem arising from hub–spoke network systems. When a large-scale network is to be constructed jointly by several agents, both the optimal network design and the fair allocation of its cost are essential issues. We formulate this problem as a cooperative game and analyze the core allocation, which is a widely used solution concept. The core of this game is not necessarily non-empty as shown by an example. A reasonable scheme is to allocate the cost proportional to the flow that an agent generates. We show that, if the demand across the system has a block structure and the fixed cost is high, this cost allocation scheme belongs to the core. Numerical experiments are given with real telecommunication traffic data in order to illustrate the usefulness of our analytical findings.

MSC:

90B18 Communication networks in operations research
90B80 Discrete location and assignment
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bailey, J. P., The economics of Internet interconnection agreements, (McKnight, L. W.; Bailey, J. P., Internet Economics (1997), MIT Press: MIT Press Cambridge, MA), 155-168
[2] Bryan, D. L.; O’Kelly, M. E., Hub-and-spoke networks in air transportation: An analytical review, Journal of Regional Science, 39, 2, 275-295 (1999)
[3] Campbell, J. F., Integer programming formulations of discrete hub location problems, European Journal of Operational Research, 72, 387-405 (1994) · Zbl 0790.90048
[4] Campbell, J. F., Hub location and the p-hub median problem, Operations Research, 44-6, 923-935 (1996) · Zbl 0879.90127
[5] Campbell, J. F.; Ernst, A. T.; Krishnamoorthy, M., Hub location problems, (Drezner, Z.; Hamacher, H. W., Facility Location (2002), Springer), 373-407 · Zbl 1061.90069
[6] Chung, S.; Myung, Y.; Tcha, D., Optimal design of a distributed network with a two-level hierarchical structure, European Journal of Operational Research, 62, 105-115 (1992) · Zbl 0758.90072
[7] 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
[8] Ernst, A. T.; Krishnamoorthy, M., Exact and heuristic algorithms for the uncapacitated multiple allocation p-hub median problem, European Journal of Operational Research, 104, 100-112 (1998) · Zbl 0955.90055
[9] Granot, D.; Huberman, G., Minimum cost spanning tree games, Mathematical Programming, 21, 1-18 (1981) · Zbl 0461.90099
[10] Greenfield, D., Europe’s virtual conundrum, Network Magazine, November, 116-122 (2000)
[11] (Gregory, C. S., TeleGeography (1993), TeleGeography Inc: TeleGeography Inc Washington, DC)
[12] Hamers, H.; Borm, P.; van de Leensel, R.; Tijs, S., Cost allocation in the Chinese postman problem, European Journal of Operational Research, 118, 153-163 (1999) · Zbl 0945.90072
[13] Helme, M. P.; Magnanti, T. L., Designing satellite communication networks by zero-one quadratic programming, Networks, 19, 427-450 (1989) · Zbl 0669.90075
[14] Klincewicz, J. G., Hub location in backbone/tributary network design: A review, Location Science, 6, 307-335 (1998)
[15] Mendelson, H., Pricing computer services: Queueing effects, Communication of the ACM, 28-3, 427-450 (1985)
[16] Mendelson, H.; Whang, S., Optimal incentive-compatible priority pricing for the M/M/1 queue, Operations Research, 38, 870-883 (1990) · Zbl 0723.90023
[17] Naor, P., The regulation of queue size by levying tolls, Econometrica, 37, 15-24 (1969) · Zbl 0172.21801
[18] Nikkan-Kogyo newspaper, 2001. The concentration of the Internet exchanges, August 24 (in Japanese); Nikkan-Kogyo newspaper, 2001. The concentration of the Internet exchanges, August 24 (in Japanese)
[19] O’Kelly, M., A quadratic integer program for the location of interacting hub facilities, European Journal of Operational Research, 32, 393-404 (1987) · Zbl 0627.90030
[20] O’Kelly, M.; Skorin-Kapov, D.; Skorin-Kapov, J., Lower bounds for the hub location problem, Management Science, 41-4, 713-721 (1995) · Zbl 0836.90109
[21] Park, K.; Lee, K.; Park, S.; Lee, H., Telecommunication node clustering with node compatibility and network survivability requirements, Management Science, 46-3, 363-374 (2000) · Zbl 1231.90121
[22] Pirkul, H.; Schilling, D. A., An efficient procedure for designing single allocation hub and spoke systems, Management Science, 44-12, S235-S242 (1998) · Zbl 0989.90537
[23] Potters, J. A.M.; Curiel, I. J.; Tijs, S. H., Traveling salesman games, Mathematical Programming, 53, 199-211 (1987) · Zbl 0749.90094
[24] Skorin-Kapov, D., On a cost allocation problem arising from a capacitated concentrator covering problem, Operations Research Letters, 13, 315-323 (1993) · Zbl 0789.90102
[25] Skorin-Kapov, D., Hub network games, Networks, 31, 293-302 (1998) · Zbl 1015.91007
[26] Skorin-Kapov, D.; Skorin-Kapov, J.; O’Kelly, M., Tight linear programming relaxations of uncapacitated p-hub median problems, European Journal of Operational Research, 94, 582-593 (1996) · Zbl 0947.90602
[27] Varian, H. R., Microeconomic Analysis (1992), W.W. Norton and Company
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.