Coincidence of cooperative game theoretic solutions in the appointment problem

Abstract

The fixed-route traveling salesman problem with appointments, simply the appointment problem, is concerned with the following situation. Starting from home, a traveler makes a scheduled visit to a group of sponsors and returns home. If a sponsor in the route cancels her appointment, the traveler returns home and waits for the next appointment. We are interested in finding a way of dividing the total traveling cost among sponsors in the appointment problem by applying solutions developed in the cooperative game theory. We show that the well-known solutions of the cooperative game theory, the Shapley value, the nucleolus (or the prenucleolus), and the τ -value, coincide under a mild condition on the traveling cost.