# graph theory – Short routes in vehicle routing problem

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?