Consider the vehicle routing problem (VRP), which poses the question of what the optimal set of routes for a fleet of vehicles to traverse in order to deliver to a given set of customers is.
In the classical problem, we seek to minimize the total distance traveled across all vehicles. Instead, I am considering a variant of the problem in which we primarily seek to minimize the number of vehicles and secondarily seek to minimize the total distance.
In this variant, we have a few break time constraints. In particular, these constraints depend on how long a route takes. If a route takes less than $4$ hours, then no break is required. If a route takes between $4$ and $8$ hours, then there will be a $30$ minute break required. Finally, if a vehicle's time exceeds $6$ hours, then a $60$ minute break is required (just to be clear: if a route takes $7$ hours, we'd require only a break of $60$ minutes and not $60 + 30 = 90$ minutes). No route can exceed $8$ hours.
My question is the following: Is it ever possible to do better (i.e. use fewer vehicles) with shorter routes as opposed to longer routes? I am pretty sure the answer is no. I can't come up with a counterexample. If the answer is no, is it possible to show that it's never possible to do better? I would like the triangle inequality to be satisfied.
I think it is possible, particularly if driving time is not strictly proportional to distance between customers (which is normal). Consider the following two diagrams, which have the same depot (A) and customers (B through G). Returns to depot are not shown.
In the first diagram, there are four routes (black, red, green and blue). The black and blue routes are assumed to take long enough that there is only enough time after nodes C or E to make a beeline back to the depot. Similarly, the time between F and G is enough that it is not possible for one vehicle to cover both.
In the second diagram, only three routes are used. The black and blue routes are shorter than in the first diagram. The red route is longer in geometric (distance) terms than either the red or green routes in the first diagram (but perhaps not longer than their combined lengths). It may involve less driving time than either of those routes (for instance, if the red route in the second diagram runs along a highway and the red and green routes in the first diagram use congested local roads with traffic lights).