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 between $4$ and $8$ hours, then there will be a $30$ minute break required. On the other hand, if a vehicle’s time exceeds $6$ hours, then a $60$ minute break is required (if something takes $7$ hours, we’d require only a break of $60$ minutes and not $60 + 30 = 90$ minutes). No route can exceed $8$ hours.

One can show that pushing for longer routes is advantageous without break time rules but not always advantageous with break time rules.

However, my question is the following: Is it ever possible to do better (fewer vehicles) to use shorter routes? I think the answer is no since I can’t come up with an example. If the answer is no, is it possible to show that it’s never possible to do better?