Abstract Multi-graphs where several edges connect a pair of nodes are an important modelling approach for many real-world optimisation problems. The multi-graph structure is often based on infrastructure and available connections between nodes. In this study, we conduct case studies for a special type of constrained routing and scheduling problems. Using the airport ground movement problem as an example, we analyse how the number of parallel edges and their costs in multi-graph structure influence the quality of obtained solutions found by the routing algorithm. The results show that the number of parallel edges not only affects the computational complexity but also the number of trade-off solutions and the quality of the found solutions. An indicator is further proposed which can estimate when the multi-graph would benefit from a higher number of parallel edges. Furthermore, we show that including edges with dominated costs in the multi-graph can also improve the results in the presence of time window constraints. The findings pave the way to an informed approach to multi-graph creation for similar problems based on multi-graphs.