In the standard version of the capacitated vehicle routing problem (VRP), a sequence of deliveries is generated for each vehicle in a homogeneous fleet based at a single depot so that all customers are serviced and the total distance traveled by the fleet is minimized. Each vehicle has a fixed capacity and must leave from and return to the depot. Each vehicle might have a route-length restriction that limits the maximum distance it can travel. Each customer has a known demand and is serviced by exactly one visit of a single vehicle.

For more than 45 years, the standard VRP has attracted an enormous amount of attention in the operations research literature. There are many practical applications of vehicle routing in the distribution of products such as soft drinks, newspapers, groceries, and milk and in street sweeping, solid waste collection,and mail delivery.

In this dissertation, we model and solve variants of the standard VRP. First, we focus on very large VRPs. We develop new, benchmark instances via a problem generator with as many as 1,200 customers along with estimated solutions. We also develop a simple, flexible, fast, and powerful heuristic solution procedure based on the record-to-record travel algorithm and apply our heuristic to the new problems and generate high-quality solutions very quickly.

Next, we turn our focus to five interesting variants of the VRP that have received little attention in the literature but have practical application in the real world: (1) the time dependent traveling salesman problem (TDTSP), (2) the noisy traveling salesman problem (NTSP), (3) the heterogeneous vehicle routing problem (HVRP), (4) the open vehicle routing problem (OVRP), and (5) the landfill routing problem (LRP). For each variant, we develop an effective solution procedure and report computational results. In particular,we solve the TDTSP, HVRP, OVRP, and LRP with our record-to-record travel-based heuristic and generate high-quality results. For the NTSP, we develop a new procedure based on quad trees that outperforms existing solution methods. Finally, for the HVRP and the OVRP, we generate new test problems and solve each new problem using our record-to-record travel-based heuristic.