On Games Arising From Multi-Depot Chinese Postman Problems

T.T. Platz, H.J.M. Hamers

Research output: Working paperDiscussion paperOther research output

228 Downloads (Pure)

Abstract

This paper introduces cooperative games arising from multi-depot Chinese postman problems and explores the properties of these games. A multi-depot Chinese postman problem (MDCP) is represented by a connected (di)graph G, a set of k depots that is a subset of the vertices of G, and a non-negative weight function on the edges of G. A solution to the MDCP is a minimum weight tour of the (di)graph that visits all edges (arcs) of the graph and that consists of a collection of subtours such that the subtours originate from dierent depots, and each subtour starts and ends at the same depot. A cooperative Chinese postman (CP) game is induced by a MDCP by associating every edge of the graph with a dierent player. This paper characterizes globally and locally k-CP balanced and submodular (di)graphs. A (di)graph G is called globally (locally) k-CP balanced (respectively submodular), if the induced CP game of the corresponding MDCP problem on G is balanced (respectively submodular) for any (some) choice of the locations of the k depots and every non-negative weight function
Original languageEnglish
Place of PublicationTilburg
PublisherOperations research
Number of pages20
Volume2013-005
Publication statusPublished - 2013

Publication series

NameCentER Discussion Paper
Volume2013-005

Fingerprint

Chinese Postman Problem
Game
Graph in graph theory
Weight Function
Non-negative
Cooperative Game
Arc of a curve
Subset

Keywords

  • Chinese postman problem
  • cooperative game
  • submodularity
  • bal- ancedness

Cite this

Platz, T. T., & Hamers, H. J. M. (2013). On Games Arising From Multi-Depot Chinese Postman Problems. (CentER Discussion Paper; Vol. 2013-005). Tilburg: Operations research.
Platz, T.T. ; Hamers, H.J.M. / On Games Arising From Multi-Depot Chinese Postman Problems. Tilburg : Operations research, 2013. (CentER Discussion Paper).
@techreport{6f68c9c075bc40609ee3462d53105427,
title = "On Games Arising From Multi-Depot Chinese Postman Problems",
abstract = "This paper introduces cooperative games arising from multi-depot Chinese postman problems and explores the properties of these games. A multi-depot Chinese postman problem (MDCP) is represented by a connected (di)graph G, a set of k depots that is a subset of the vertices of G, and a non-negative weight function on the edges of G. A solution to the MDCP is a minimum weight tour of the (di)graph that visits all edges (arcs) of the graph and that consists of a collection of subtours such that the subtours originate from dierent depots, and each subtour starts and ends at the same depot. A cooperative Chinese postman (CP) game is induced by a MDCP by associating every edge of the graph with a dierent player. This paper characterizes globally and locally k-CP balanced and submodular (di)graphs. A (di)graph G is called globally (locally) k-CP balanced (respectively submodular), if the induced CP game of the corresponding MDCP problem on G is balanced (respectively submodular) for any (some) choice of the locations of the k depots and every non-negative weight function",
keywords = "Chinese postman problem, cooperative game, submodularity, bal- ancedness",
author = "T.T. Platz and H.J.M. Hamers",
note = "Pagination: 20",
year = "2013",
language = "English",
volume = "2013-005",
series = "CentER Discussion Paper",
publisher = "Operations research",
type = "WorkingPaper",
institution = "Operations research",

}

Platz, TT & Hamers, HJM 2013 'On Games Arising From Multi-Depot Chinese Postman Problems' CentER Discussion Paper, vol. 2013-005, Operations research, Tilburg.

On Games Arising From Multi-Depot Chinese Postman Problems. / Platz, T.T.; Hamers, H.J.M.

Tilburg : Operations research, 2013. (CentER Discussion Paper; Vol. 2013-005).

Research output: Working paperDiscussion paperOther research output

TY - UNPB

T1 - On Games Arising From Multi-Depot Chinese Postman Problems

AU - Platz, T.T.

AU - Hamers, H.J.M.

N1 - Pagination: 20

PY - 2013

Y1 - 2013

N2 - This paper introduces cooperative games arising from multi-depot Chinese postman problems and explores the properties of these games. A multi-depot Chinese postman problem (MDCP) is represented by a connected (di)graph G, a set of k depots that is a subset of the vertices of G, and a non-negative weight function on the edges of G. A solution to the MDCP is a minimum weight tour of the (di)graph that visits all edges (arcs) of the graph and that consists of a collection of subtours such that the subtours originate from dierent depots, and each subtour starts and ends at the same depot. A cooperative Chinese postman (CP) game is induced by a MDCP by associating every edge of the graph with a dierent player. This paper characterizes globally and locally k-CP balanced and submodular (di)graphs. A (di)graph G is called globally (locally) k-CP balanced (respectively submodular), if the induced CP game of the corresponding MDCP problem on G is balanced (respectively submodular) for any (some) choice of the locations of the k depots and every non-negative weight function

AB - This paper introduces cooperative games arising from multi-depot Chinese postman problems and explores the properties of these games. A multi-depot Chinese postman problem (MDCP) is represented by a connected (di)graph G, a set of k depots that is a subset of the vertices of G, and a non-negative weight function on the edges of G. A solution to the MDCP is a minimum weight tour of the (di)graph that visits all edges (arcs) of the graph and that consists of a collection of subtours such that the subtours originate from dierent depots, and each subtour starts and ends at the same depot. A cooperative Chinese postman (CP) game is induced by a MDCP by associating every edge of the graph with a dierent player. This paper characterizes globally and locally k-CP balanced and submodular (di)graphs. A (di)graph G is called globally (locally) k-CP balanced (respectively submodular), if the induced CP game of the corresponding MDCP problem on G is balanced (respectively submodular) for any (some) choice of the locations of the k depots and every non-negative weight function

KW - Chinese postman problem

KW - cooperative game

KW - submodularity

KW - bal- ancedness

M3 - Discussion paper

VL - 2013-005

T3 - CentER Discussion Paper

BT - On Games Arising From Multi-Depot Chinese Postman Problems

PB - Operations research

CY - Tilburg

ER -

Platz TT, Hamers HJM. On Games Arising From Multi-Depot Chinese Postman Problems. Tilburg: Operations research. 2013. (CentER Discussion Paper).