  We consider the NP-hard 2-period balanced travelling salesman problem. In
this problem the salesman needs to visit a set of customers in two time
periods. A given subset of the customers has to be visited in both periods
while the rest of the customers need to be visited only once, in any of the two
periods. Moreover, it is required that the number of customers visited in the
first period does not differ from the respective number in the second period by
more than p, where p is a given small constant. The objective is to find tours
for visiting the customers in the two periods with minimal total length. We
show that in the case when the underlying distance matrix is a Kalmanson
matrix, the problem can be solved in polynomial time. For the general case, we
propose two new heuristics. A combination of these two heuristics has shown
very favourable results in computational experiments on benchmark instances
from the literature.
