Optimal vehicle routing with lower and upper bounds on route durations

This article is concerned with the problem of finding optimal vehicle routes to minimize the overall travel time, with constraints on the minimum and maximum amount of time spent on each route. The problem extends previous work on the distance‐constrained vehicle routing problem by introducing lower bounds on route durations to ensure that the resulting routes are balanced. The article also explicitly addresses the situation where a solution is artificially balanced as a result of inoptimal orders of visits. The article describes alternative ways in which the restrictions on route connectivity, duration, and artificial balancing can be formulated, and introduces an exact algorithm based on cutting planes and mixed‐integer linear programming. To the best of our knowledge, this is the first exact algorithm proposed for such a problem that explicitly addresses artificially balanced routes. Computational results are presented for three versions of the exact algorithm using TSPLIB instances.