Vehicle routing problems arise when goods must be delivered from a depot to a set of geographically dispersed customers. We consider the vehicle routing problem that has single depot, capacity restrictions, stochastic customers and delivery time window constraints. We formulate such a problem as a two-stage stochastic programming model with resource. We propose an in-exact stochastic approximation approach that can handle such a problem effectively. In this method, we combine and extend some classical algorithms for deterministic vehicle routing problems, and propose a Longest-Distance-First (LDF) rule and a forward approximation approach to deal with the uncertain customers. The solution set can provide the first batch schedule with the ready orders and indicate which orders should be...[ Read more ]

Vehicle routing problems arise when goods must be delivered from a depot to a set of geographically dispersed customers. We consider the vehicle routing problem that has single depot, capacity restrictions, stochastic customers and delivery time window constraints. We formulate such a problem as a two-stage stochastic programming model with resource. We propose an in-exact stochastic approximation approach that can handle such a problem effectively. In this method, we combine and extend some classical algorithms for deterministic vehicle routing problems, and propose a Longest-Distance-First (LDF) rule and a forward approximation approach to deal with the uncertain customers. The solution set can provide the first batch schedule with the ready orders and indicate which orders should be outsourced to other transportation service providers. Since our goal is to search for an "as good as possible" solution within a reasonable time frame instead of an optimal one, there is no guarantee that the "best" solution here is indeed the optimal solution. The algorithm has been tested on 250 instances. In general, the proposed model has successfully produced quick and high-quality solution.