Static and dynamic approaches for solving the vehicle routing problem with stochastic demands.

摘要

This research focuses on the vehicle routing problem with stochastic demands (VRPSD). The VRPSD occurs in the delivery of industrial gases and the restocking of retail stores. Since exact customer's demands are uncertain until the vehicle arrives at the customer, a planned route may fail at a given location. If a route failure occurs, different recourses can be taken at extra cost. For example, the remaining customers can be skipped, re-scheduled in extra-trips, or served by the same vehicle after it returns to the depot to refill.; Our research studies the VRPSD from two different perspectives. Our first method (Part I of this dissertation) solves the multiple VRPSD under a two-stage approach and new recourse actions that include customers completed by other vehicles and the re-scheduling of extra-trips. The problem is modeled as a stochastic program with integer recourse, and is formulated as a stochastic extension of the set partitioning problem. We demonstrate via simulation that our new recourse decreases routing cost about 4--5% over the "go to the depot and resume" recourse assumption when the number of unsatisfied customers per route is low.; The second method (Part II of this dissertation) constructs the route dynamically in multiple stages using current information about vehicle capacity. We model the problem as a Markov Decision Process and use a rollout algorithm (RA) for computing the solution. In this method, we assume that after route failures the vehicle goes to the depot for replenishment and that it also performs proactive returns to the depot. We extend previous work on the RA by investigating different base tours, cost-to-go estimation methods, look-ahead policies, and pruning schemes. We find that cost-to-go estimation via simulation reduces the CPU time in about 60% when compared to exact cost-to-go computation. We compare the best rollout solution to the perfect information case being the confidence interval for the overall mean difference (4.565%, 5.27%).; Both two-stage and dynamic approaches exhibit considerable advantages over following deterministic solutions from VRP The best rollout solutions result from merging the two previous approaches.