In this article we consider a bi-objective vehicle routing problem in which, in addition to the classical minimization of the total routing cost, the operator is also required to minimize the maximum diameter of the routes, this is the maximum distance between any two customers serviced within the same route. This problem arises in applications in which a decision planner needs to integrate the routing decisions into his tactical planning so as to reduce the cost of a potential derouting under uncertainty. In addition to the problem description, we provide a formal linear-integer formulation of the problem and an ad-hoc \(\epsilon\)-constraint method capable of handling small-size problems. We also introduce a variable neighborhood search-based algorithm for the solution of larger problems. We provide a critical analysis of the results obtained after executing our algorithms on some classical instances of the capacitated vehicle routing problem.