Scandinavian Working Papers in Economics
HomeAboutSeriesSubject/JEL codesAdvanced Search
Department of Business and Economics, University of Southern Denmark Discussion Papers of Business and Economics
Department of Business and Economics, University of Southern Denmark

No 8/2017:
On the submodularity of multi-depot traveling salesman games

Trine Tornøe Platz ()

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; (follow links to similar papers)

JEL-Codes: C71; (follow links to similar papers)

22 pages, July 6, 2017

Before downloading any of the electronic versions below you should read our statement on copyright.
Download GhostScript for viewing Postscript files and the Acrobat Reader for viewing and printing pdf files.

Full text versions of the paper:

dpbe8_2017.pdf?la=da    PDF-file
Download Statistics

Questions (including download problems) about the papers in this series should be directed to Lene Holbæk ()
Report other problems with accessing this service to Sune Karlsson () or Helena Lundin ().

Programing by
Design by Joachim Ekebom

Handle: RePEc:hhs:sdueko:2017_008 This page was generated on 2017-07-06 08:52:16