The traveling group problem

This paper combines social choice theory with mathematical optimization by applying various group decision concepts to a classical problem of combinatorial optimization, namely the famous traveling salesperson (salesman) problem. The aim of the latter is to find a tour through all vertices of a given graph along edges of minimal total cost. In this contribution we replace the measure of additive edge costs by the social acceptance of different edges and the resulting tours. In particular, for four different voting rules, the Borda rule, Approval voting, Plurality rule and Simple Majority rule, we will investigate the social acceptance of tours derived from global and local decisions. It will be shown that these two decision approaches can lead to widely varying results.