Cost of selfishness in the allocation of cities in the Multiple Travelling Salesmen Problem. (March 2020)

• Record Type: Journal Article
• Authors: Moyaux, Thierry; Marcon, Eric
• Is Part Of: Engineering applications of artificial intelligence. Volume 89(2020)
• Publication Date: 2020-03
• Subjects: Centralised Organisation (CO) -- Decentralised Organisation (DO) -- Selfishness -- Multiple Travelling Salesmen Problem (MTSP); Engineering -- Data processing -- Periodicals; Artificial intelligence -- Periodicals; Expert systems (Computer science) -- Periodicals; Ingénierie -- Informatique -- Périodiques; Intelligence artificielle -- Périodiques; Systèmes experts (Informatique) -- Périodiques; Artificial intelligence; Engineering -- Data processing; Expert systems (Computer science); Periodicals; 620.00285
• DOI: 10.1016/j.engappai.2019.103429
• Languages: English
• ISSNs: 0952-1976

Abstract

Abstract: 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: (i) this modification of the MTSP to include selfishness; (ii) the proposition of organisations to solve this modified MTSP; and (iii) the comparison of these organisations. Our 5 organisations may be summarised as follows: (i) 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); (ii) Cluster and (iii) Auction are CO/DO hybrids; and (iv) P2P and (v) CNP are pure DO. The sixth and seventh organisations are used as benchmarks: (vi) NoRealloc is a pure DO which ignores the allocation problem; and (vii) FullCentr is a pure CO which solves a different problem, v i z ., 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.