The 2-period Balanced Traveling Salesman Problem

In the 2-period Balanced Traveling Salesman Problem (2B-TSP), the customers must be visited over a period of two days: some must be visited daily, and the others on alternate days (even or odd days); moreover, the number of customers visited in every tour must be ‘balanced’, i.e. it must be the same or, alternatively, the difference between the maximum and the minimum number of visited customers must be less than a given threshold. The salesman’s objective is to minimize the total distance travelled over the two tours. Although this problem may be viewed as a particular case of the Period Traveling Salesman Problem, in the 2-period Balanced TSP the assumptions allow for emphasizing on routing aspects, more than on the assignment of the customers to the various days of the period. The paper proposes two heuristic algorithms particularly suited for the case of Euclidean distances between the customers. Computational experiences and a comparison between the two algorithms are also given.