In this dissertation we consider variants of the vehicle routing problem applied to two problem areas. First, we consider the problem of scheduling deliveries from a central depot to clients in a metric space using a single delivery vehicle. Although this problem involves only a single vehicle rather than a fleet, it is amenable to analysis from both a worst-case and average-case perspective, and has applications to real-world systems. Second, we consider two problems related to the scheduling of air ambulances, one in an offline setting and another in an online setting. Air ambulances are used to provide emergency medical services to residents of both British Columbia and Ontario, Canada. We consider techniques to improve the efficiency of service in these systems.