DTIST01Most algorithms for solving vehicle routing problems use the criterion of minimizing total travel time in forming their routes. As illustrated in the paper, even in the case of a homogeneous fleet, solutions using other criteria may be preferred to the solution generated by minimizing total travel time. This situation becomes more pronounced when considering a vehicle routing problem where the fleet is non-homogeneous. In this paper, we explore the uses of more complex cost models in deriving solutions to vehicle routing problems, especially in the case of a non- homogeneous fleet. We develop a function called the Measure of Goodness that can be used as the criterion for solving these problems. We show how the Measure of Goodness criterion or special cases of this criterion can be used to compare solutions, generate an initial fleet mix or used as the criterion in a mixed integer program for carrying out between route swaps of the entities to be serviced. The vehicle routing problem emphasized in this paper is the Capacitated Arc Routing Problem with Vehicle/Site Dependencies (CARP-VSD).