[salmonellaeater]

The customers' dislike of the lowest-cost routes might have to do with surprises that can occur along the route. For example, if the vehicle breaks down, it's better to have made as many deliveries as possible already so you don't have to offload as much or any of the cargo to another vehicle. A route that greedily visits deliveries and then has a long return leg is better from this perspective. Another thing that might happen is additional stops might be added as new information becomes available. Leaving the return leg less constrained makes the average cost of adding a stop in a new area lower.