On Games Arising From Multi-Depot Chinese Postman Problems

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

Research output: Working paperDiscussion paperOther research output

286 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

Keywords

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

Fingerprint Dive into the research topics of 'On Games Arising From Multi-Depot Chinese Postman Problems'. Together they form a unique fingerprint.

  • 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). Operations research.