The Traveling Salesman Game for Cost Allocation: The Case Study of the Bus Service in Castellanza. (11th December 2014)

• Record Type: Journal Article
• Authors: Besozzi, Nicola; Ruschetti, Luca; Rossignoli, Chiara; Strozzi, Fernanda
• Other Names: Wang X. Henry Academic Editor.
• Is Part Of: Game theory. Volume 2014(2014)
• Publication Date: 2014-12-11
• Subjects: Game theory -- Periodicals; Game theory; Periodicals; 519.3
• DOI: 10.1155/2014/696945
• Languages: English
• ISSNs: 2314-6559

Abstract

Abstract : This paper studies cost allocation for the bus transportation service in Castellanza, a small town (14, 000 inhabitants ca.) close to Varese, Italy. Carlo Cattaneo University (LIUC) is one of the promoters and funders of this service, together with the City Council and other private agents. The case study is first analysed as a traveling salesman problem (TSP) to find the optimal route. Then the traveling salesman game (TSG) is introduced, where the bus stops are associated with the players of a cooperative game, thus allowing the study of possible allocations of the total cost among them. The optimal route is found by the Branch and Bound algorithm. The Shapley vector and the separable and nonseparable cost are the methods used to allocate the cost of the optimal route among players.