The tugboat scheduling task aims to efficiently allocate tugboat resources to assist ships entering and leaving the port in maritime transportation. Many existing scheduling methods focus on directly finding scheduling solutions. However, they are not suitable to deal with the large-scale and dynamic characteristics of maritime transportation systems due to long scheduling time. Therefore, this paper focuses on finding scheduling rules for large-scale dynamic tugboat scheduling problem (DTug-sp), including two core tasks: allocating ships to tugboats (i.e., the allocation rule) and determining the execution order of ships assigned to a particular tugboat (i.e., the order rule). To solve this problem, we propose a multi-tree genetic programming method for DTug-sp, termed as MTGP-DTsp, which uses a dual-tree encoding strategy to represent the ship allocation rule and the tugboat execution order rule, respectively. Additionally, a new crossover operator is introduced to enhance the effectiveness of the generated scheduling rules. Experimental results demonstrate that MTGP-DTsp can effectively evolve scheduling rules suitable for DTug-sp, achieving the goal of minimizing tugboat assisting time and detecting the minimum weighted average tugboat assisting time, separately.