Paper Info
Title
Cooperation of customers in traveling salesman problems with profits
Abstract
In the profitable tour problem, the carrier decides whether to visit a particular customer with respect to the prize the customer offers for being visited and traveling cost associated with the visit, all in the context of other customers. Our focus is on the prizes customers need to offer to ensure being visited by the carrier. This can be formulated as a cooperative game where customers may form coalitions and make decisions on the prize values cooperatively. We define the profitable tour game describing this situation and analyze the cost associated with each coalition of customers and prizes that help to achieve it. We derive properties of the optimal prizes to be offered when the grand coalition is formed. These properties describe relationship between the prizes and the underlying traveling salesman game to provide connection with extensive literature on core allocations in traveling salesman games. The most important result states that the set of optimal prizes coincides with the core of the underlying traveling salesman game if this core is nonempty.
Year
DOI
Venue
2020
10.1007/s11590-019-01429-6
Optimization Letters
Keywords
DocType
Volume
Traveling salesman problem, Profitable tour problem, Prize-collecting TSP, Logistics, Cooperative game theory, Prize allocation
Journal
14
Issue
ISSN
Citations 
5
1862-4472
0
PageRank 
References 
Authors
0.34
0
3
Name
Order
Citations
PageRank
Ondrej Osicka100.34
Mario Guajardo212712.49
Kurt Jørnsten323224.52