Enforcing TSP-optimality in fair vehicle routing by cutting planes

We study a fair capacitated vehicle routing problem, in which a fleet of capacitated vehicles must serve a set of customers such that the difference in length between the longest and shortest route, the range, is minimized. A key challenge is that fairness objectives such as the range can be non-monotonic: they can be reduced by artificially lengthening routes, leading to solutions that violate TS…