IDEAS home Printed from https://ideas.repec.org/p/hhs/sdueko/2017_008.html
   My bibliography  Save this paper

On the submodularity of multi-depot traveling salesman games

Author

Listed:

Abstract

The Steiner traveling salesman problem (STSP) is the problem of finding a minimum cost tour for a salesman that must visit a set of locations while traveling along costly streets before returning to his starting point at the depot. A solution to the problem is a minimum cost tour that both starts and ends at the depot and visits all the required locations. If different players are associated with the destinations to be visited, the STSP induces a cooperative traveling salesman (TS) game that poses the question of how to allocate the total cost of the tour between the different players involved. This cost allocation problem can be tackled using tools and solutions from cooperative games. The purpose of this paper is to generalise the notion of a traveling salesman (TS) game to allow for multiple depots in the underlying STSP and to analyse the submodularity of such multi-depot TS games. A multi-depot STSP can be represented by a connected (di)graph in which a fixed set of nodes are denoted depots, and a non-negative weight function is defined on the edges of the graph. The submodularity of multi-depot TS games is analysed by characterising graphs and digraphs that induce submodular multi-depot TS games for any position of the depots and for at least one position of the depots, respectively.

Suggested Citation

  • Platz, Trine Tornøe, 2017. "On the submodularity of multi-depot traveling salesman games," Discussion Papers on Economics 8/2017, University of Southern Denmark, Department of Economics.
    • Handle: RePEc:hhs:sdueko:2017_008
    as

    Download full text from publisher

    File URL: http://www.sdu.dk/-/media/files/om_sdu/institutter/ivoe/disc_papers/disc_2017/dpbe8_2017.pdf?la=da
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Curiel, I. & Potters, J.A.M. & Rajendra Prasad, V. & Tijs, S.H. & Veltman, B., 1994. "Sequencing and cooperation," Other publications TiSEM be67f9e9-7a4a-47f1-9fb9-7, Tilburg University, School of Economics and Management.
    2. Hamers, Herbert & Borm, Peter & van de Leensel, Robert & Tijs, Stef, 1999. "Cost allocation in the Chinese postman problem," European Journal of Operational Research, Elsevier, vol. 118(1), pages 153-163, October.
    3. Trine Platz & Herbert Hamers, 2015. "On games arising from multi-depot Chinese postman problems," Annals of Operations Research, Springer, vol. 235(1), pages 675-692, December.
    4. Granot, D. & Hamers, H.J.M. & Tijs, S.H., 1999. "On some balanced, totally balanced and submodular delivery games," Other publications TiSEM e0496604-0162-4a27-992c-a, Tilburg University, School of Economics and Management.
    5. Imma Curiel & Jos Potters & Rajendra Prasad & Stef Tijs & Bart Veltman, 1994. "Sequencing and Cooperation," Operations Research, INFORMS, vol. 42(3), pages 566-568, June.
    6. Potters, J.A.M. & Curiel, I. & Tijs, S.H., 1992. "Traveling salesman games," Other publications TiSEM 0dd4cf3d-25fa-4179-80f6-6, Tilburg University, School of Economics and Management.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Trine Platz & Herbert Hamers, 2015. "On games arising from multi-depot Chinese postman problems," Annals of Operations Research, Springer, vol. 235(1), pages 675-692, December.
    2. Daniel Granot & Jeroen Kuipers & Sunil Chopra, 2002. "Cost Allocation for a Tree Network with Heterogeneous Customers," Mathematics of Operations Research, INFORMS, vol. 27(4), pages 647-661, November.
    3. Peter Borm & Herbert Hamers & Ruud Hendrickx, 2001. "Operations research games: A survey," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 9(2), pages 139-199, December.
    4. Behzad Hezarkhani & Marco Slikker & Tom Woensel, 2016. "A competitive solution for cooperative truckload delivery," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 38(1), pages 51-80, January.
    5. van Velzen, Bas & Hamers, Herbert & Solymosi, Tamas, 2008. "Core stability in chain-component additive games," Games and Economic Behavior, Elsevier, vol. 62(1), pages 116-139, January.
    6. van Velzen, S. & Hamers, H.J.M., 2002. "On the Balancedness of Relaxed Sequencing Games," Discussion Paper 2002-49, Tilburg University, Center for Economic Research.
    7. Flip Klijn & Dries Vermeulen & Herbert Hamers & Tamás Solymosi & Stef Tijs & Joan Pere Villar, 2003. "Neighbor games and the leximax solution," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 58(2), pages 191-208, November.
    8. Gerichhausen, M. & Hamers, H.J.M., 2007. "Partitioning Sequencing Situations and Games," Other publications TiSEM 2bddbf5c-c56d-4b10-ba47-5, Tilburg University, School of Economics and Management.
    9. Atay, Ata & Trudeau, Christian, 2024. "Queueing games with an endogenous number of machines," Games and Economic Behavior, Elsevier, vol. 144(C), pages 104-125.
    10. Imma Curiel & Herbert Hamers & Stef Tijs & Jos Potters, 1997. "Restricted component additive games," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 45(2), pages 213-220, June.
    11. Hamers, H.J.M. & Miquel, S. & Norde, H.W., 2011. "Monotonic Stable Solutions for Minimum Coloring Games," Other publications TiSEM efae8d09-83e6-4fe4-9623-e, Tilburg University, School of Economics and Management.
    12. René Brink, 2012. "On hierarchies and communication," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 39(4), pages 721-735, October.
    13. Fragnelli, V. & Llorca, N. & Sánchez-Soriano, J. & Tijs, S.H., 2006. "Convex Games with Countable Number of Players and Sequencing Situations," Discussion Paper 2006-119, Tilburg University, Center for Economic Research.
    14. Estevez Fernandez, M.A. & Mosquera, M.A. & Borm, P.E.M. & Hamers, H.J.M., 2006. "Proportionate Flow Shop Games," Discussion Paper 2006-63, Tilburg University, Center for Economic Research.
    15. Pedro Calleja & Peter Borm & Herbert Hamers & Flip Klijn & Marco Slikker, 2002. "On a New Class of Parallel Sequencing Situations and Related Games," Annals of Operations Research, Springer, vol. 109(1), pages 265-277, January.
    16. Min Ji & Sai Liu & Xiaolin Zhang & Keke Cao & T. C. E. Cheng, 2017. "Sequencing Games with Slack Due Windows and Group Technology Considerations," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 68(2), pages 121-133, February.
    17. Hamers, H.J.M. & Miquel, S. & Norde, H.W., 2011. "Monotonic Stable Solutions for Minimum Coloring Games," Discussion Paper 2011-016, Tilburg University, Center for Economic Research.
    18. Herbert Hamers & Flip Klijn & Bas Velzen, 2005. "On the Convexity of Precedence Sequencing Games," Annals of Operations Research, Springer, vol. 137(1), pages 161-175, July.
    19. Çiftçi, BarIs & Borm, Peter & Hamers, Herbert, 2010. "Highway games on weakly cyclic graphs," European Journal of Operational Research, Elsevier, vol. 204(1), pages 117-124, July.
    20. Hamers, Herbert & Klijn, Flip & Solymosi, Tamas & Tijs, Stef & Vermeulen, Dries, 2003. "On the nucleolus of neighbor games," European Journal of Operational Research, Elsevier, vol. 146(1), pages 1-18, April.

    More about this item

    Keywords

    Traveling salesman problem; cooperative game; submodularity;
    All these keywords.

    JEL classification:

    • C71 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Cooperative Games

    NEP fields

    This paper has been announced in the following NEP Reports:

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:hhs:sdueko:2017_008. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Astrid Holm Nielsen (email available below). General contact details of provider: https://edirc.repec.org/data/okioudk.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.