Title: Approximation Algorithms for Vehicle Routing and Scheduling.
Viswanath Nagarajan, Thesis Proposal for Ph.D. in Algorithms, Combinatorics and Optimization.
10:30am Wednesday 23-April
Room 384, 3rd floor Posner Hall (Tepper School of Business)
Broadly speaking, any scheduling problem can be characterized as serving a set of requests using a limited set of resources, subject to constraints detailing how the resources may serve requests. Due to the complicating nature of constraints in typical scheduling problems, most of them are NP-complete and hence we do not expect efficient (i.e. polynomial time) exact algorithms. The two main approaches to practical solutions of such problems are (i) exact algorithms that compute the optimal solution but take exponential time in the worst case, and (ii) heuristic algorithms that run in polynomial time but find near-optimal solutions. An approximation algorithm is an efficient heuristic along with a worst-case guarantee on the quality of the near-optimal solutions found by it. The goal of this thesis is to design approximation algorithms for some scheduling problems, with an emphasis on Vehicle Routing Problems.
Vehicle routing problems (VRPs) form a rich class of variants of the basic Traveling Salesman Problem, that are also practically motivated. In VRPs, a fleet of vehicles represents the resources used to serve a set of client-requests (such as transporting objects to the clients). Many VRPs just seek to minimize cost incurred by the vehicles while serving client requests; a goal in this thesis is to study VRPs that incorporate some additional criteria on the vehicle routes.
All VRPs are defined in relation to a metric space (i.e. set of locations with a distance function on them). Most of the work on approximation algorithms for VRPs has focussed on symmetric metrics. The corresponding problems on asymmetric metrics become considerably harder. Another goal of this thesis is to design algorithms for VRPs on asymmetric metrics.
Committee: R. Ravi (Chair), Gerard Cornuejols, Anupam Gupta, Mike Trick
