Scandinavian Working Papers in Business Administration

Discussion Papers,
Norwegian School of Economics, Department of Business and Management Science

No 2019/17: Cooperation of customers in traveling salesman problems with profits

Ondrej Osicka (), Mario Guajardo () and Kurt Jörnsten ()
Additional contact information
Ondrej Osicka: Dept. of Business and Management Science, Norwegian School of Economics, Postal: NHH , Department of Business and Management Science, Helleveien 30, N-5045 Bergen, Norway
Mario Guajardo: Dept. of Business and Management Science, Norwegian School of Economics, Postal: NHH , Department of Business and Management Science, Helleveien 30, N-5045 Bergen, Norway
Kurt Jörnsten: Dept. of Business and Management Science, Norwegian School of Economics, Postal: NHH , Department of Business and Management Science, Helleveien 30, N-5045 Bergen, Norway

Abstract: The traveling salesman problem and its variants are among the most studied problems in the literature on transportation and logistics. In one of these variants known as the profitable tour problem [2], a profit-maximizing 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. The purpose of this paper is to define the profitable tour game, a cooperative version of the profitable tour problem, and to derive its properties. We are particularly interested in prize allocations that create incentives for the carrier to visit all relevant customers. Applications of the profitable tour game might include for example situations in shipping where a carrier is able to serve demands of several customers with a single vehicle. Whether it comes to delivery or pickup of goods, the customers might need to induce the carrier to visit them by offering sufficient rewards. Subsequently, negotiation with other customers in the same position could lead to better prizes while the carrier's visit would remain guaranteed. This knowledge could also be utilized by the carrier by offering specifically tailored discounts on multiple orders from the same area or by evaluating and pricing of new customers.

Keywords: Traveling salesman problem; Profitable tour problem; Prize-collecting TSP; Logistics; Cooperative game theory; Prize allocation

JEL-codes: C00; C71

3 pages, November 22, 2019

Full text files

2630082 PDF-file Full text

Download statistics

Questions (including download problems) about the papers in this series should be directed to Stein Fossen ()
Report other problems with accessing this service to Sune Karlsson ().

RePEc:hhs:nhhfms:2019_017This page generated on 2024-10-02 04:36:09.