This paper deals with the problem of planning multiple agent movements through a mission area modeled as a graph. The agents undergo classic communication and temporal constraints, and the quantitative objective is the minimization of the team’s traversal makespan. Additional specificities make the problem a particularly complex routing one: on some nodes are associated durative and coordinated actions to perform, which can involve either the co-presence of several agents or time dependencies. Also, some agents are deployable and able to move on denser graphs: namely, aerial robots can take off and land on the ground vehicle at any planned position, and can fly above ground obstacles. We model the problem as a CSP and solve it with a network flow model. Results show the efficacy of the model and resolution scheme, which provides solutions with one or two orders of magnitude smaller time than a numerical temporal hierarchical planning model, with only a few percent loss of optimality.