Consider the classic Vehicle Routing Problem.
In this paper, the author shows how to optimally partition an optimal TSP tour, into feasible routes. In other words he describes a "route-first cluster-second" approach for the problem, where the clustering part is optimal.
On page $2$, it is written:
Note that it is easily shown that an optimal TSP tour followed by an optimal set of vehicle routes does not necessarily lead to an optimal set of vehicle routes.
I am trying to come up with a very simple example where this is true. Can anyone help?
Let out graph have $6$ vertices on a plane with Manhattan metric (for simplicity). Vertices are point with following coordinates: $v_1(0, 0), v_2(0, 1), v_3(5, 0), v_4(5, 1), v_5(10, 0), v_6(10, 1)$. Then $v_1v_2v_4v_6v_5v_3v_1$ is the optimal TSP tour. Let $v_1$ be depot and vehicle capacity equals 2. If you partition tour optimally you'll have to visit $v_5$ and $v_6$ by one vechicle (22 units length), $v_4$ and $v_2$ by anothere one (12 units length) and $v_3$ by the third one (10 units length), that is 44 units length in total. Optimal set of vehicle routes is the following: visit $v_5$ and $v_6$ by one vechicle (22 units length), $v_3$ and $v_4$ by another one (12 units length) and $v_2$ by the third one (2 units length), that is 36 units length in total.