TITLE: A Computation-Implementation Parallelization Approach to Time-Sensitive Applications
STUDENT: Bahar Cavdar
ADVISOR: Dr. Joel Sokol
SUMMARY:
In this thesis, we study time sensitive applications where it is critical to minimize the completion time, i.e., the time passing between receiving the instance and finishing the implementation of the solution. In contrast to the traditional compute-first implement-later approach, we focus on the minimization of the computation time of the solution in addition to finding the best possible solution to the problem. We propose a new approach called Computation-Implementation Parallelization (CIP) and develop methods to embed the computation time into the solution-implementation to minimize the completion time. We implement our approach on the specific cases of the Traveling Salesman Problem (TSP) and Vehicle Routing Problem (VRP). We also present a TSP tour length estimation model that does not make any assumption on the distribution of the nodes.
In the first chapter, we implement our CIP approach on a type of TSP we call the TSP Race problem. In this problem setting, given the same graph and starting from the same point, two salesmen are racing to finish the tour before the other. The race starts as soon as the graphs are released to the salesmen. Therefore, how long they compute is also a factor determining who will win. We demonstrate CIP's effectiveness on TSP Race instances. We also demonstrate a method for determining a priori when CIP will be effective.
In the second chapter, we focus on large-scale parcel delivery. Making good routing decisions has become computationally more demanding due to both increasing size of the logistics operations and also the increasing trend in integrating the problems to make better decisions for the overall system. However, tight schedules in warehouses may allow only very limited time for computation for routing. To improve the solution quality, increasing the computation time may not be always feasible since it requires either shifting the order cutoff time to an earlier point in time or delaying the truck dispatching. To overcome this issue, using our CIP approach, we embed computation into the truck loading phase to create free-computation time.
Our research in CIP opened up a new question on TSP tour length estimators. Tour length estimations can be used to determine the quality of a tour on hand. Estimation models in the TSP literature focus on instances where the node dispersion is known (and often is uniform). In the third chapter, to deal with more general cases, i.e., graphs with non-uniform and unknown node dispersions, we develop a new empirical tour length estimation model for a broader dispersion family based on regression. Our model can estimate the tour lengths of these graphs to +/-3% of the tour length found by the Lin-Kernighan algorithm, with standard deviation of the estimation errors four times smaller than most previous models. When the distribution of the node coordinates is known, it can also estimate the coefficient of the well-known asymptotic tour length estimation formula of Beardwood et al. (1959), whose estimate cannot be computed if the node dispersion is not known. Our model not only produces good estimates on several different dispersion types, but also substitutes for Beardwood et al.'s estimation formula when the distribution is unknown.