Abstract
Traveling salesman problems with revenues form a generalization of traveling salesman problems. Here, next to travel costs an explicit revenue is generated by visiting a city. We analyze routing problems with revenues, where a predetermined route on all cities determines the tours along subgroups. Corresponding routing games with revenues are analyzed. It is shown that these games have a nonempty core and a complete description of the core is provided.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Brânzei R, Iñarra E, Tijs S, Zarzuelo J (2006) Asimple algorithm for the nucleolus of airport profit problems. Int J Game Theory 34: 259–272
Derks J, Kuipers J (1997) On the core of routing games. Int J Game Theory 26: 193–205
Estévez-Fernández A, Borm P, Hamers H (2006) On the core of multiple longest traveling salesman games. Eur J Oper Res 174: 1816–1827
Fishburn PC, Pollak HO (1983) Fixed-route cost allocation. Am Math Monthly 90: 366–378
Kuipers J (1993) A note in the 5-person traveling salesman game. Zeitschrift für Operations Research 21: 339–351
Lawler EL, Lenstra JK, Kan AHGR, Shmoys DB, Hurkens CAJ (1997) The traveling salesman problem: a guided tour of combinatorial optimization. Wiley-Interscience, Chichester
Littlechild SC, Owen G (1976) A further note on the nucleolus of the “airport game”. Int J Game Theory 5: 91–95
Meertens M, Potters J (2006) The nucleolus of trees with revenues. Math Methods Oper Res 64: 363–382
Nemhauser GL, Wolsey LA (1988) Integer and combinatorial optimization. Wiley-Interscience, New York
Okamoto Y (2004) Traveling salesman games with the monge property. Discrete Appl Math 138: 349–369
Owen G (1975) On the core of linear production games. Math Program 9: 358–370
Potters JA, Curiel IJ, Tijs SH (1992) Traveling salesman games. Math Program 53: 199–211
Suijs J, Borm P, Hamers H, Quant M, Koster M (2005) Communication and cooperation in public network situations. Ann Oper Res 137: 117–140
Tamir A (1989) On the core of a traveling salesman cost allocation game. Oper Res Lett 8: 31–34
Open Access
This article is distributed under the terms of the Creative Commons Attribution Noncommercial License which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
Author information
Authors and Affiliations
Corresponding author
Additional information
The authors thank two referees for their valuable suggestions for improvement. Special thanks go to Herbert Hamers for his helpful discussion and comments.
Rights and permissions
Open Access This is an open access article distributed under the terms of the Creative Commons Attribution Noncommercial License (https://creativecommons.org/licenses/by-nc/2.0), which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
About this article
Cite this article
Estévez-Fernández, A., Borm, P., Meertens, M. et al. On the core of routing games with revenues. Int J Game Theory 38, 291–304 (2009). https://doi.org/10.1007/s00182-009-0154-9
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00182-009-0154-9