ON THE CORE OF ROUTING GAMES

A repairman makes a round-trip along a set of customers. He starts in his home location, visits each customer exactly once, and returns home . The cost of his trip has to be shared by the customers. A cooperativ e cost game, called louring game, is associated with this allocation p roblem, and an O(n(2)) algorithm is given which computes a core elemen t of a routing game if the core is non-empty. The non-emptiness of the core depends on the lour which is traversed by the repairman. Several procedures are given to construct tours which guarantee the non-empti ness of the core.