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 $\frac{k}{n}$ of the journey. Each solution is represented by an $n \times 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(n^2 \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 \leq n$, to under $\frac{2}{n}$ of the journey.

Keywords

bicycles, binary matrices, optimal schemes, Dyck language

2010 Mathematics Subject Classification

05B20

Full Text (PDF format)

Received 15 June 2021

Accepted 5 September 2022

Published 7 November 2023