Abstract In multihop relay networks such as LTE-Advanced and the mobile WiMAX network, subscribers move in and out of the Fixed Relays’ (FRs) coverage in different periods. Frequent handover requests generated by population mobility lead to low data rate and load imbalances among FRs. To fulfill the requirement of subscribers, Mobile Relays (MRs), are considered to patrol FRs to offload their relay task which can improve the efficiency of the access network. In this paper, we define and study the Minimum Mobile Relay Path selection problem (MMRP), whose objective is to deploy minimum MRs to patrol FRs when they are “busy”. First, Markov chains are used to predict FRs’ busy period which is then transformed into a busy period graph. Based on this busy period graph, we propose solutions to different relaying scenarios. Maximum matching and the maximum flow technologies are adopted to find heuristic algorithms for these different scenarios respectively. Theoretical analysis and simulation results show that, compared with traditional search algorithms, solutions based on the maximum matching and the maximum flow technologies have O ( n 2 ) complexity, where n is the number of FRs, and they perform better than traditional ways on the number of paths and system overhead. Moreover, the solution using predicted busy periods is more efficient than that when FRs’ busy periods are presupposed.