Cost of selfishness in the allocation of cities in the Multiple Travelling Salesmen Problem

摘要

The decision to centralise or decentralise human organisations needs to be based on quantified evidence, yet little is available in the literature. We provide such data in a variant of the Multiple Travelling Salesmen Problem (MTSP) in which we study how the allocation sub-problem may be decentralised among selfish salesmen. Our contributions are: (ⅰ) this modification of the MTSP to include selfishness; (ⅱ) the proposition of organisations to solve this modified MTSP; and (in) the comparison of these organisations. Our 5 organisations may be summarised as follows: (ⅰ) OptDecentr is a pure Centralised Organisation (CO) in which a Central Authority (CA) finds the best solution that could be found by a Decentralised Organisation (DO); (ⅱ) Cluster and (ⅲ) Auction are CO/DO hybrids; and (ⅳ) P2P and (ⅴ) CNP are pure DO. The sixth and seventh organisations are used as benchmarks: (ⅵ) NoRealloc is a pure DO which ignores the allocation problem; and (ⅶ) FullCentr is a pure CO which solves a different problem, viz., the traditional MTSP. Comparing the efficiency of pairs of these mechanisms quantifies the price of decentralising an organisation. In particular, our model of selfishness in OptDecentr, with 5 (respectively, 9) salesmen, makes the total route length 30% (respectively, 60%) longer than the traditional MTSP in FullCentr when the computation time is limited to 30 min. With this time limit, our results also seem to indicate that the level of coercion of the CA impacts the total route length more than the level of centralisation.