The Biker-hiker problem

There are n travellers who have k bicycles and they wish to complete a journey in the shortest possible time. We investigate optimal solutions of this problem where each traveller cycles for k n of the journey. Each solution is represented by an n × n binary matrix M with k non-zero entries in each row and column. We determine when such a matrix gives an optimal solution. This yields an algorithm deciding the question of optimality of complexity O(n2 log n). We introduce three symmetries of matrices that preserve optimality, allowing identification of minimal non-optimal members of this class. An adjustment to optimal solutions that eliminates unnecessary handovers of cycles is established, which maintains all other features of the solution. We identify two mutually transpose solution types, the first uniquely minimises the number of handovers, while the second keeps the number of separate cohorts to three while bounding their overall separation, in the case 2k n, to under 2 n of the journey.