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.

Flooded with Information from Social Media: Effects of Disaster Information Source and Visuals on Viewers' Cognitive, Affective, and Behavioral Responses

While a variety of crisis types loom as real risks for organizations and communities, and the media landscape continues to evolve, research is needed to help explain and predict how people respond to various kinds of crisis and disaster information. For example, despite the rising prevalence of digital and mobile media centered on still and moving visuals, and stark increases in Americans’ use of visual-based platforms for seeking and sharing disaster information, relatively little is known about how the presence or absence of disaster visuals online might prompt or deter resilience-related feelings, thoughts, and/or behaviors. Yet, with such insights, governmental and other organizational entities as well as communities themselves may best help individuals and communities prepare for, cope with, and recover from adverse events. Thus, this work uses the theoretical lens of the social-mediated crisis communication model (SMCC) coupled with the limited capacity model of motivated mediated message processing (LC4MP) to explore effects of disaster information source and visuals on viewers’ resilience-related responses to an extreme flooding scenario. Results from two experiments are reported. First a preliminary 2 (disaster information source: organization/US National Weather Service vs. news media/USA Today) x 2 (disaster visuals: no visual podcast vs. moving visual video) factorial between-subjects online experiment with a convenience sample of university students probes effects of crisis source and visuals on a variety of cognitive, affective, and behavioral outcomes. A second between-subjects online experiment manipulating still and moving visual pace in online videos (no visual vs. still, slow-pace visual vs. still, medium-pace visual vs. still, fast-pace visual vs. moving, slow-pace visual vs. moving, medium-pace visual vs. moving, fast-pace visual) with a convenience sample recruited from Amazon’s Mechanical Turk (mTurk) similarly probes a variety of potentially resilience-related cognitive, affective, and behavioral outcomes. The role of biological sex as a quasi-experimental variable is also investigated in both studies. Various implications for community resilience and recommendations for risk and disaster communicators are explored. Implications for theory building and future research are also examined. Resulting modifications of the SMCC model (i.e., removing “message strategy” and adding the new category of “message content elements” under organizational considerations) are proposed.