On the submodularity of multi-depot traveling salesman games

Trine Platz

No 8/2017, Discussion Papers on Economics from University of Southern Denmark, Department of Economics

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.

Keywords: Traveling salesman problem; cooperative game; submodularity (search for similar items in EconPapers)
JEL-codes: C71 (search for similar items in EconPapers)
Pages: 22 pages
Date: 2017-07-06
New Economics Papers: this item is included in nep-gth and nep-hpe
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sdu.dk/-/media/files/om_sdu/institutter ... dpbe8_2017.pdf?la=da (application/pdf)
Our link check indicates that this URL is bad, the error code is: 500 Can't connect to www.sdu.dk:80 (A connection attempt failed because the connected party did not properly respond after a period of time, or established connection failed because connected host has failed to respond.)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hhs:sdueko:2017_008

Access Statistics for this paper

More papers in Discussion Papers on Economics from University of Southern Denmark, Department of Economics Department of Economics, University of Southern Denmark, Campusvej 55, DK-5230 Odense M, Denmark. Contact information at EDIRC.
Bibliographic data for series maintained by Astrid Holm Nielsen ().