Stochastic network programming and the dynamic vehicle allocation problem

Efficiency in trucking and railroad operations is critically dependent on the optimal distribution of vehicles. This problem is known as the Dynamic Vehicle Allocation (DVA) problem. On daily intervals, a fleet carrier receives requests to have loads moved between various pairs of sites. The carrier can accept or decline each request. The carrier knows the requests that exist for the current day, but is uncertain about future requests. Since how the fleet is dispatched today determines the starting location of each vehicle tomorrow, the dispatcher must decide today's routing so today's profits are maximized and so the fleet is well positioned to meet possible future requests.;The problem is formulated as a multistage stochastic linear programs whose core problem in each stage is a minimum cost network flow problem.;The first section considers the exploitation of the internal structure of the network and demonstrates that additional benefits in both approximation and solution methods can be obtained. A property of network flow problems in which the arc upper capacities are independently distributed random variables is discovered which results in a new upper bound on the expected value of the optimal objective value. Next, the ideas of the Out-of-Kilter algorithm for deterministic minimum cost network flow problems are extended in the Stochastic Out-of-Kilter algorithm for two-stage stochastic minimum cost network flow problems. Finally, an upper bounding method is developed for a class of DVA problems.;The second section considers generalizations of the DVA problem, allowing such additional features as backlogging and multiple vehicle types. The first result proves that for a general class of multistage stochastic programs, including the DVA problem and generalizations, solutions of approximation problems constructed from empirical data become arbitrarily close to solutions of the original problem. To solve these approximation problems, the Abridged Nested Decomposition algorithm is developed. This method embeds sampling into an existing solution method for multistage stochastic programs. A computational study using data from actual carriers demonstrates that the Abridged Nested Decomposition algorithm can be effectively applied to the DVA problem and several generalizations.