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

dc.contributor.advisorGolden, Bruceen_US
dc.contributor.authorWang, Xingyinen_US
dc.contributor.departmentMathematicsen_US
dc.contributor.publisherDigital Repository at the University of Marylanden_US
dc.contributor.publisherUniversity of Maryland (College Park, Md.)en_US
dc.date.accessioned2016-09-08T05:34:44Z
dc.date.available2016-09-08T05:34:44Z
dc.date.issued2016en_US
dc.description.abstractIn 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.en_US
dc.identifierhttps://doi.org/10.13016/M27F7Z
dc.identifier.urihttp://hdl.handle.net/1903/18710
dc.language.isoenen_US
dc.subject.pqcontrolledOperations researchen_US
dc.subject.pqcontrolledTransportationen_US
dc.subject.pquncontrolledCompletion timeen_US
dc.subject.pquncontrolledHeuristicsen_US
dc.subject.pquncontrolledMin-maxen_US
dc.subject.pquncontrolledVehicle routingen_US
dc.subject.pquncontrolledWorst-caseen_US
dc.titleVehicle Routing Problems that Minimize the Completion Time: Heuristics, Worst-Case Analyses, and Computational Resultsen_US
dc.typeDissertationen_US

Files

Original bundle
Now showing 1 - 4 of 4
Loading...
Thumbnail Image
Name:
Wang_umd_0117E_17396.pdf
Size:
20.05 MB
Format:
Adobe Portable Document Format
No Thumbnail Available
Name:
MMMDSDVRP-MSR.rar
Size:
195.23 KB
Format:
Unknown data format
No Thumbnail Available
Name:
MMSDSDVRP.rar
Size:
111.84 KB
Format:
Unknown data format
No Thumbnail Available
Name:
MMCEVRP.rar
Size:
198.63 KB
Format:
Unknown data format