On the Submodularity of Multi-depot Traveling Salesman Games

Research output: Contribution to journalJournal articleResearchpeer-review

Abstract

The Steiner traveling salesman problem 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 Steiner tour that both starts and ends at the depot and visits all the required locations. If different players are associated with the locations to be visited, the problem 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 game theory.
The purpose of this paper is to generalize the notion of a traveling salesman game to allow for multiple depots in the underlying traveling salesman problem (TSP) and to analyze the submodularity of such multi-depot TS games. A multi-depot TSP can be represented by a connected (di)graph in which a fixed set of vertices 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 analyzed by characterizing graphs and digraphs that induce submodular multi-depot TS games for any choice of depots and for at least one choice of depots, respectively.
The Steiner traveling salesman problem 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 Steiner tour that both starts and ends at the depot and visits all the required locations. If different players are associated with the locations to be visited, the problem 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 game theory.
The purpose of this paper is to generalize the notion of a traveling salesman game to allow for multiple depots in the underlying traveling salesman problem (TSP) and to analyze the submodularity of such multi-depot TS games. A multi-depot TSP can be represented by a connected (di)graph in which a fixed set of vertices 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 analyzed by characterizing graphs and digraphs that induce submodular multi-depot TS games for any choice of depots and for at least one choice of depots, respectively.
LanguageEnglish
JournalDiscrete Applied Mathematics
Volume255
Pages75-85
Number of pages11
ISSN0166-218X
DOIs
StatePublished - Feb 2019

Bibliographical note

Published online: 18 December 2018.

Keywords

  • Steiner traveling salesman problem
  • Cooperative game
  • Submodularity

Cite this

@article{573f4b8705d248d1b2ff3aeea9bf263d,
title = "On the Submodularity of Multi-depot Traveling Salesman Games",
abstract = "The Steiner traveling salesman problem 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 Steiner tour that both starts and ends at the depot and visits all the required locations. If different players are associated with the locations to be visited, the problem 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 game theory.The purpose of this paper is to generalize the notion of a traveling salesman game to allow for multiple depots in the underlying traveling salesman problem (TSP) and to analyze the submodularity of such multi-depot TS games. A multi-depot TSP can be represented by a connected (di)graph in which a fixed set of vertices 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 analyzed by characterizing graphs and digraphs that induce submodular multi-depot TS games for any choice of depots and for at least one choice of depots, respectively.",
keywords = "Steiner traveling salesman problem, Cooperative game, Submodularity, Steiner traveling salesman problem, Cooperative game, Submodularity",
author = "Platz, {Trine Torn{\o}e}",
note = "Published online: 18 December 2018.",
year = "2019",
month = "2",
doi = "10.1016/j.dam.2018.11.029",
language = "English",
volume = "255",
pages = "75--85",
journal = "Discrete Applied Mathematics",
issn = "0166-218X",
publisher = "Elsevier BV North-Holland",

}

On the Submodularity of Multi-depot Traveling Salesman Games. / Platz, Trine Tornøe .

In: Discrete Applied Mathematics, Vol. 255, 02.2019, p. 75-85.

Research output: Contribution to journalJournal articleResearchpeer-review

TY - JOUR

T1 - On the Submodularity of Multi-depot Traveling Salesman Games

AU - Platz,Trine Tornøe

N1 - Published online: 18 December 2018.

PY - 2019/2

Y1 - 2019/2

N2 - The Steiner traveling salesman problem 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 Steiner tour that both starts and ends at the depot and visits all the required locations. If different players are associated with the locations to be visited, the problem 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 game theory.The purpose of this paper is to generalize the notion of a traveling salesman game to allow for multiple depots in the underlying traveling salesman problem (TSP) and to analyze the submodularity of such multi-depot TS games. A multi-depot TSP can be represented by a connected (di)graph in which a fixed set of vertices 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 analyzed by characterizing graphs and digraphs that induce submodular multi-depot TS games for any choice of depots and for at least one choice of depots, respectively.

AB - The Steiner traveling salesman problem 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 Steiner tour that both starts and ends at the depot and visits all the required locations. If different players are associated with the locations to be visited, the problem 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 game theory.The purpose of this paper is to generalize the notion of a traveling salesman game to allow for multiple depots in the underlying traveling salesman problem (TSP) and to analyze the submodularity of such multi-depot TS games. A multi-depot TSP can be represented by a connected (di)graph in which a fixed set of vertices 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 analyzed by characterizing graphs and digraphs that induce submodular multi-depot TS games for any choice of depots and for at least one choice of depots, respectively.

KW - Steiner traveling salesman problem

KW - Cooperative game

KW - Submodularity

KW - Steiner traveling salesman problem

KW - Cooperative game

KW - Submodularity

UR - https://sfx-45cbs.hosted.exlibrisgroup.com/45cbs?url_ver=Z39.88-2004&url_ctx_fmt=info:ofi/fmt:kev:mtx:ctx&ctx_enc=info:ofi/enc:UTF-8&ctx_ver=Z39.88-2004&rfr_id=info:sid/sfxit.com:azlist&sfx.ignore_date_threshold=1&rft.object_id=954925482629&rft.object_portfolio_id=&svc.holdings=yes&svc.fulltext=yes

U2 - 10.1016/j.dam.2018.11.029

DO - 10.1016/j.dam.2018.11.029

M3 - Journal article

VL - 255

SP - 75

EP - 85

JO - Discrete Applied Mathematics

T2 - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

ER -