In many industries the shipping costs of a product are a major component of a company or organization’s overall expenses. A well-planned delivery schedule can reduce some companies’ costs by as much as 30 percent. Calculating efficient routing plans for large fleets of delivery vehicles can be a complex and time-consuming endeavor, but successful routing strategies can lead to significant economic advantages. This paper presents a new heuristic approach to large-scale, multiple-vehicle routing problems, using a grouping technique with a modified minimal spanning tree. The advantage of this approach is that it creates good-quality solutions in a relatively quick time-frame, when compared against other solution techniques. The efficiency of the proposed algorithm was confirmed by using various test problems and comparing the output of this approach versus the popular Genetic Algorithm for solving routing problems. This effective heuristic approach can be applied to many different kinds of combinatorial optimization, such as construction equipment fleet planning, construction materials delivery planning, waste collection management, and package delivery.