Vehicle Routing Problems that Minimize the Completion Time: Heuristics, Worst-Case Analyses, and Computational Results

In the standard Vehicle Routing Problem (VRP), we route a fleet of vehicles to deliver the demands of all customers such that the total distance traveled by the fleet is minimized. In this dissertation, we study variants of the VRP that minimize the completion time, i.e., we minimize the distance of the longest route. We call it the min-max objective function. In applications such as disaster relief efforts and military operations, the objective is often to finish the delivery or the task as soon as possible, not to plan routes with the minimum total distance. Even in commercial package delivery nowadays, companies are investing in new technologies to speed up delivery instead of focusing merely on the min-sum objective. In this dissertation, we compare the min-max and the standard (min-sum) objective functions in a worst-case analysis to show that the optimal solution with respect to one objective function can be very poor with respect to the other. The results motivate the design of algorithms specifically for the min-max objective. We study variants of min-max VRPs including one problem from the literature (the min-max Multi-Depot VRP) and two new problems (the min-max Split Delivery Multi-Depot VRP with Minimum Service Requirement and the min-max Close-Enough VRP). We develop heuristics to solve these three problems. We compare the results produced by our heuristics to the best-known solutions in the literature and find that our algorithms are effective. In the case where benchmark instances are not available, we generate instances whose near-optimal solutions can be estimated based on geometry. We formulate the Vehicle Routing Problem with Drones and carry out a theoretical analysis to show the maximum benefit from using drones in addition to trucks to reduce delivery time. The speed-up ratio depends on the number of drones loaded onto one truck and the speed of the drone relative to the speed of the truck.

Gospel Music Training, Performance Practice and Its Impact on Leadership Development and Performed Nationalism in a Collegiate Military Choir

Since America’s beginnings as a British colony, its musical standards have adhered to those of Western Europe. For this reason, musical forms native to America like Black folk spirituals and Gospel music have historically been marginalized in favor of music in the Western classical tradition. Today, a bias towards music of the Western classical tradition exists in those American universities that grant music degrees. While this bias is understandable, inclusion of Gospel music history and performance practice would result in a more complete understanding of American music and its impact on American nationalism. The United States Naval Academy is one of the few American universities that have consistently elevated the performance of Gospel music to the level of Western Classical music within its institutional culture. The motivations for writing this document are to provide a brief history of Gospel music in the United States and of choral music at the Naval Academy. These historical accounts serve as lenses though which the intersection of Gospel music performance practice and leadership development at the United States Naval Academy may be observed. During the last two decades of the twentieth century, Gospel music intersected American military culture at the U.S. Naval Academy. After a few student-led attempts in the 1970s, a Gospel Choir was formed in 1986 but by 1990, it had become an official part of the Music Department. Ultimately, it received institutional support and today, the Gospel Choir is one of three touring choirs authorized to represent the Academy in an official capacity. This document discusses the promotion of Gospel music by the Naval Academy in its efforts to diversify Academy culture and ultimately, Naval and Marine Corps leadership. Finally, this dissertation examines the addition of performed cultural expression (Gospel music) in light of a shift in American nationalism and discusses its impact on Naval Academy culture.

Legacy Resource Management Program Archaeological Reconnaissance Survey, United States Naval Academy, Annapolis, MD.

The Archaeological Reconnaissance Survey of United States Naval Academy will provide the Navy with a rich understanding of the history of this property. A National Register of Historic Places District, such as the Academy, deserves a thorough analysis of its past, in order to preserve what exists and to plan for the future. The goal of this project is to investigate the history of the Academy through traditional historic research, innovative computer analysis of historic maps, oral history interviews, and tract histories. This information has been synthesized to provide the Navy with a planning tool for Public Works, a concise look at the cartographic history of the Academy, and reference manual of the vast amounts of information which have been gathered during the course of this project. This information can serve as a reference tool to help the Public Works department comply with Section 106 regulations of the Historic Sites Preservation Act, with regard to construction. It can also serve as a source of cartographic history for those interested in the Academy's physical development, and as a way of preserving the culture of residents in Annapolis. This program and archaeological survey will ultimately serve to add to the rich history of the United States Naval Academy while preserving an important part of our nation's heritage.