Models and algorithms for practical vehicle routing

In this thesis, we consider three practical vehicle routing models and develop algorithms for each model respectively. Each model involves a set of important practical issues that have received little or no attention in the literature. Our study on these models and algorithms is motivated by our interactions with industry, particularly Manugistics, Inc. and its client firms. These models and algorithms are applicable to practical routing problems faced by many other companies as well. We first consider a practical pickup and delivery problem that involves practical complications such as DOT rules, multiple time windows, nested precedence constraints, and complex cost structure. We propose column generation based approaches to this complex problem. It is shown that the approaches are capable of generating near-optimal solutions quickly for randomly generated instances with up to 200 orders. For larger randomly generated instances with up to 500 orders, it is shown that computational times are acceptable. The second model we consider is a capacitated vehicle routing problem with crossdocking options. The vehicle routing decisions in this model involve a combination of direct store delivery and crossdocking delivery, and are more complex than traditional models in which no crossdocking options are available. We study three different cases of this model and for each case we propose a heuristic respectively. We show that the heuristics for the first two cases are asymptotically optimal under some mild conditions, and evaluate the performance of all the heuristics through computational experiments. The third model we consider is a dynamic vehicle routing problem with soft time windows. The problem is dynamic in the sense that customer orders arrive dynamically over time and are not known until their arrivals, and must be assigned in real time to appropriate vehicles. We propose a dynamic column generation methodology to solve this problem. We compare the approach against a simple insertion heuristic and a rolling horizon based approach that is allowed an unlimited computational time at each decision epoch. It is shown that our approach outperforms the first heuristic, and that the gap between our approach and the second evaluating approach is reasonably small