Paper ID: 2203.05219

Organisations (de-)centralised to a greater or lesser degree for allocating cities in two Multiple Travelling Salesmen Problems

Thierry Moyaux

Decisions in organisations may be made either by a Central Authority (CA), e.g., in a hierarchy, or by the agents in a decentralised way, e.g., in a heterarchy. Since both kinds of organisations have their advantages (e.g., optimality for centralised organisations and reactivity for decentralised ones), our goal is ultimately to understand when and how to use each of them. Our previous work proposed a variant of the Multiple Travelling Salesmen Problem, which we now call MTSPs . We use the subscript "s" to refer to salesmen's selfishness when they minimise their individual route length. If, on the contrary, they are assumed to be benevolent, we add subscript "b" and thus the term MTSPb to refer to the traditional MTSP in which the salesmen minimise the total route length. This article shows how to obtain such benevolent agents by slightly modifying selfish agents. We can then compare organisations which are (de-)centralised to a greater or lesser degree, which enables us to carry out the allocation of cities in the MTSPb . The first experiment shows that the relative efficiency (ranking) of the organisations differs between MTSPb and MTSPs . Since reactivity fosters decentralisation, the second experiment gradually reduces the time taken for it to impact this ranking. Both experiments show that pure centralisation is either the best or the worst option, and that the zone between the two situations is very narrow.

Submitted: Mar 10, 2022