<p>Mission planning solvers take an input mission specified by using Boolean and temporal logic operators; however, the techniques have an exponential complexity for verification that restricts solvers to small problem sizes only. Heuristic-driven classic planning techniques cannot model temporal constraints and have exponential computation complexity. Operational research problems like the generalisations of the Vehicle Routing Problem have been solved for huge problem sizes using several evolutionary and metaheuristic approaches. However, the current variants do not allow problems to be taken as a formal expression using the Backus Naur Form nor the probabilistic availability of the sites. This paper is at the confluence of classic planning, temporal planning, and the generalisations of the Vehicle Routing Problem. The proposed approach models an expression tree consisting of conjunction, disjunction, and the sequence operator, which is first solved in a greedy manner using a bottom-up traversal of the tree. The solver returns a Pareto front of solutions using probability and costs as the two objectives. The algorithm is extended to multiple robots. A genetic algorithm is used for further optimisation. Results show a better performance than optimisation baselines over problem sizes that the classic approaches cannot solve.</p>