The rise of global supply chains and e-commerce in recent decades have intensified the relevance of the transportation industry to both the individual and the economy. With rising consumer expectations and slim profit margins, the various sectors within the transportation industry rely on the development of carefully designed routes to remain competitive. Despite the wealth of research on route design, and the responsiveness of the research community to practical considerations, there remain gaps between the work done in practice and that appearing in the literature. Correspondingly, the work in this dissertation is directly in response to conversations had with contacts from real-world companies within the transportation domain. We consider problems presented, verbally, by companies representing three distinct segments of the industry: freight routing, last-mile delivery, and on-demand passenger transport. Each problem is centered around an innovative strategy with the potential to dramatically disrupt its corresponding domain. First, we consider the Shared Truckload (STL) freight shipping model, an alternative to the dominant Less-than-Truckload (LTL) model. Both models pool shipments from multiple customers into a single trailer, but, in the latter, consolidation is facilitated by a hub-and-spoke routing network, whereas, in the the former, freight moves directly from origin to destination. This strategy minimizes travel times and the risk of damage. We then investigate a novel strategy to facilitate last-mile, last-minute delivery, through coordinating a fleet of trucks and a fleet of smaller vehicles, referred to as shuttles. In order to accommodate requests which come in after trucks have been dispatched, shuttles are allowed to pick up packages from a depot and intercept trucks along their routes. This strategy can enable a shipper to make highly competitive service guarantees. Finally, we consider the emerging field of Urban Air Mobility (UAM), a vision of air taxis conveying passengers at lower altitudes throughout urban areas as an efficient alternative to gridlock traffic. In particular, we consider a UAM service company in the early stages of its development, where the chief goal is to maximize market share.

These innovations represent significant deviations from the status quo in their respective fields, and, thus, the existing research for each is slim, if existent. Therefore, we introduce precise mathematical formulations of each of the problems to the research community. We then develop both exact and heuristic approaches to solve the problems, and carry out extensive computational studies comparing the solution methodologies. Furthermore, for each of the problems, we offer a sensitivity analysis and managerial insights. Among our contributions are original algorithms based on solving a set-partitioning formulations via column generation, a highly successful paradigm for solving large linear programs. Among the advantages of this approach is the ability to include highly general route costs and constraints. We illustrate this expressiveness by demonstrating its application to each of the three highly distinct problems we consider.