### Abstract

Original language | English |
---|---|

Place of Publication | Tilburg |

Publisher | Operations research |

Number of pages | 20 |

Volume | 2013-005 |

Publication status | Published - 2013 |

### Publication series

Name | CentER Discussion Paper |
---|---|

Volume | 2013-005 |

### Fingerprint

### Keywords

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

### Cite this

*On Games Arising From Multi-Depot Chinese Postman Problems*. (CentER Discussion Paper; Vol. 2013-005). Tilburg: Operations research.

}

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

Research output: Working paper › Discussion paper › Other 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 -