nach oben

OR Spectrum

Erschienen in:

31.01.2020 | Regular Article

One-way and two-way cost allocation in hub network problems

verfasst von: G. Bergantiños, J. Vidal-Puga

Erschienen in: OR Spectrum | Ausgabe 1/2020

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We consider a cost allocation problem arising from a hub network problem design. Finding an optimal hub network is NP-hard, so we start with a hub network that could be optimal or not. Our main objective is to divide the maintenance and/or building cost of such network among the nodes. We consider two cases. In the one-way flow case, we assume that the cost paid by a set of nodes depends only on the flow they send to other nodes (including nodes outside the set), but not on the flow they receive from nodes outside. In the two-way flow case, we assume that the cost paid by a set of nodes depends on the flow they send to other nodes (including nodes outside the set) and also on the flow they receive from nodes outside. In both cases, we study the core and the Shapley value of the corresponding cost game.

Vorheriger Artikel Enhancing Benders decomposition algorithm to solve a combat logistics problem

Nächster Artikel A long-term unit commitment problem with hydrothermal coordination for economic and emission control in large-scale electricity systems

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Assume that you are from Spain but you are in Argentina. If you receive a phone call from Spain, some phone companies consider it as an international call. The cost of this international call is divided by your company into two parts. The people who phone you pay the cost of a local call (inside Spain) and you pay the difference between the cost of an international call and the cost of a local call.

A generalization would be to assume that these costs are given by another cost matrix \(C^{h}=\left( c_{ij}^{h}\right) _{i,j\in N}\) with \(c_{ij}^{h}\le c_{ij}\) for all \(i,j\in N\). In our case, \(C^{h}=\alpha C\).

These tables correct some irrelevant typos presented in Matsubayashi et al. (2005).

Due to the symmetry of the matrices, the fact that all flows are positive, and the low congestion rate, both the one-way case and two-way case give very similar values for the Shapley rule.

Alcalde-Unzu J, Gómez-Rúa M, Molis E (2015) Sharing the costs of cleaning a river: the upstream responsibility rule. Games Econ Behav 90:134–150CrossRef

Alumur S, Kara BY (2008) Network hub allocation problems: the state of the art. Eur J Oper Res 190:1–21CrossRef

Bailey J (1997) The economics of Internet interconnection agreements. In: McKnight L, Bailey J (eds) Internet economics. MIT Press, Cambridge, pp 115–168CrossRef

Bergantiños G, Kar A (2010) On obligation rules for minimum cost spanning tree problems. Games Econ Behav 69:224–237CrossRef

Bergantiños G, Gómez-Rúa M, Llorca N, Pulido M, Sánchez-Soriano J (2014) A new rule for source connection problems. Eur J Oper Res 234(3):780–788CrossRef

Bogomolnaia A, Moulin H (2010) Sharing the cost of a minimal cost spanning tree: beyond the folk solution. Games Econ Behav 69(2):238–248CrossRef

Bryan D, O’Kelly M (1999) Hub-and-spoke networks in air transportation: an analytical review. J Reg Sci 39(2):275–295CrossRef

Dutta B, Mishra D (2012) Minimum cost arborescences. Games Econ Behav 74(1):120–143CrossRef

Farahani RZ, Hekmatfar M, Arabani AB, Nikbakhsh E (2013) Hub location problems: a review of models, classification, solution techniques, and applications. Comput Ind Eng 64(4):1096–1109CrossRef

Gillies D (1959) Solutions to general non-zero sum games, chapter 3. In: Tucker A, Luce R (eds) Contributions to the theory of games. Volume IV of annals of mathematics studies. Princeton, Princeton UP, pp 47–85

Greenfield D (2000) Europe’s virtual conundrum. Netw Mag 15:116–123

Guardiola LA, Meca A, Puerto J (2009) Production-inventory games: a new class of totally balanced combinatorial optimization games. Games Econ Behav 65(1):205–219. (Special Issue in Honor of Martin Shubik)CrossRef

Helme M, Magnanti T (1989) Designing satellite communication networks by zero-one quadratic programming. Networks 19:427–450CrossRef

Matsubayashi N, Umezawa M, Masuda Y, Nishino H (2005) A cost allocation problem arising in hub-spoke network systems. Eur J Oper Res 160:821–838CrossRef

Moulin H (2014) Pricing traffic in a spanning network. Games Econ Behav 86:475–490CrossRef

Perea F, Puerto J, Fernandez F (2009) Modeling cooperation on a class of distribution problems. Eur J Oper Res 198:726–733CrossRef

Roni MS, Eksioglu SD, Cafferty KG, Jacobson JJ (2017) A multi-objective, hub-and-spoke model to design and manage biofuel supply chains. Ann Oper Res 249(1):351–380CrossRef

Shapley LS (1953) A value for n-person games. In: Kuhn HK, Tucker A (eds) Contributions to the theory of games. Volume II of annals of mathematics studies. Princeton University Press, Princeton, pp 307–317

Shapley LS (1971) Cores of convex games. Int J Game Theory 1:11–26CrossRef

Sim T, Lowe TJ, Thomas BW (2009) The stochastic-hub center problem with service-level constraints. Comput Oper Res 36(12):3166–3177CrossRef

Skorin-Kapov D (1998) Hub network games. Networks 31:293–302CrossRef

Skorin-Kapov D (2001) On cost allocation in hub-like networks. Ann Oper Res 106:63–78CrossRef

Trudeau C (2012) A new stable and more responsible cost sharing solution for mcst problems. Games Econ Behav 75(1):402–412CrossRef

Trudeau C, Vidal-Puga J (2017) On the set of extreme core allocations for minimal cost spanning tree problems. J Econ Theory 169:425–452CrossRef

Wieberneit N (2008) Service network design for freight transportation: a review. OR Spectrum 30(1):77–112CrossRef

Yang T-H (2009) Stochastic air freight hub location and flight routes planning. Appl Math Model 33(12):4424–4430CrossRef

Titel: One-way and two-way cost allocation in hub network problems
verfasst von: G. Bergantiños
J. Vidal-Puga
Publikationsdatum: 31.01.2020
Verlag: Springer Berlin Heidelberg
Erschienen in: OR Spectrum / Ausgabe 1/2020
Print ISSN: 0171-6468
Elektronische ISSN: 1436-6304
DOI: https://doi.org/10.1007/s00291-020-00573-1

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft"

Springer Professional "Wirtschaft+Technik"

Weitere Artikel der Ausgabe 1/2020

A new matheuristic approach for the multi-depot vehicle routing problem with inter-depot routes

A matheuristic for the swap body vehicle routing problem

Enhancing Benders decomposition algorithm to solve a combat logistics problem

A multi-cover routing problem for planning rapid needs assessment under different information-sharing settings

Balance in resource allocation problems: a changing reference approach

A column generation-based decomposition and aggregation approach for combining orders in inland transportation of containers