The asymmetric distance--constrained vehicle routing problem, consists of finding vehicle tours to connect all customers with a depot, such that the total distance is minimum and the traveled distance by each vehicle is less than or equal to the given maximum value. In order to solve it exactly we develop new tolerance based branching rules within branch and bound method. Since our method was fast but memory consuming, it could stop before optimality is proven. Therefore we introduce the randomness in choosing the node of the search tree. If an optimal solution is not found, we restart our procedure. In that way we get multistart branch and bound method. Computational experiments show that we are able to exactly solve large test instances with up to 1000 customers. As far as we know those instances are the largest compared with other approaches from the literature.