Developing state-dependent routes for the vehicle routing problem under uncertainty.

摘要

This dissertation extends the study of an extensively studied problem in logistics, the Vehicle Routing Problem (VRP). We first model the variant of this problem that incorporates uncertain customer demands (VRPSD), in a single-vehicle environment, as a Markov Decision Problem (MDP). The advantage of using such a model lies in its ability to incorporate unfolding information---in this case the customer demand, revealed upon visiting the customer---as it is obtained; a focus of our research is utilization of such information. While MDP formulations are not new to the literature, our description of the properties of such formulations represents an enhancement of the existing literature. Furthermore, our computational experiments on VRPSD with a number of MDP-based solution procedures also establish the problem sizes that can effectively be addressed by MDP models, given the dimensional constraints and current computational ability.; Computational intractability, however, implies that exact techniques would be impracticable for large problems; accordingly, we next study some existing heuristic approaches to VRP and VRPSD. We modify these and demonstrate the improvements our modifications can bring about to available solutions, from the perspective either of solution quality in practice, or of guarantees on solution quality or computational time in theory. Apart from these modifications, we use network-flow techniques to construct an approximate solution for a special case of VRP. For VRPSD, in separate sets of computational experiments, we apply an MDP-based procedure and a heuristic tour-improvement procedure to an initial solution, and thereby improve solution quality with reasonable investment in computational resources.; Finally, we use the intuition and solution-development insight gained from the above studies to develop a heuristic approach to solve a real-world problem that to our knowledge has not been addressed in the literature before. This problem is actually a combination of two existing multiple-vehicle VRP variants: (a) a VRPSD that additionally incorporates stochasticity in customer presence, and that is formally referred to as VRPSCD, and (b) a (deterministic) VRP where all vehicles are assumed to conduct delivery as well as pickup (also called backhaul) operations, formally referred to as VRPB. We call this problem the VRPSCDB.; Specifically, we modify existing "tabu search" (a neighborhood search approach that makes recently considered solutions inaccessible, or tabu, for a number of iterations) techniques for solving the VRPSCD, and apply them to VRPSCDB. We also compare our solutions with practice-based solutions, and we incorporate polynomial-time refinements that allow dynamic updates to vehicle routes as new information about customer presence and demands becomes available. Our computational experiments that incorporate such updating show encouraging results.