  In the bipartite travelling salesman problem (BTSP), we are given $n=2k$
  cities along with an $n\times n$ distance matrix and a partition of
  the cities into $k$ red and $k$ blue cities. The task is to find a
  shortest tour which alternately visits blue and red cities. We consider the
BTSP restricted to the class of so-called Van der Veen distance matrices. We
show that this case remains NP-hard in general but becomes solvable in
polynomial time when all vertices with odd indices are coloured blue and all
with even indices are coloured red. In the latter case an optimal solution can
be found in $O(n^2)$ time among the set of pyramidal tours.
