Unlike its deterministic counterpart, static and stochastic vehicle routing problems (SS-VRP) aim at modeling and solving real-life operational problems by considering uncertainty on data. We consider the SS-VRPTW-CR introduced in Saint- (2017). Like the SS-VRP introduced by Bertsimas (1992), we search for optimal first stage routes for a fleet of vehicles to handle a set of stochastic customer demands, i.e., demands are uncertain and we only know their probabilities. In addition to capacity constraints, customer demands are also constrained by time windows. Unlike all SS-VRP variants, the SS-VRPTW-CR does not make any assumption on the time at which a stochastic demand is revealed, i.e., the reveal time is stochastic as well. To handle this new problem, we introduce waiting locations: Each vehicle is assigned a sequence of waiting locations from which it may serve some associated demands, and the objective is to minimize the expected number of demands that cannot be satisfied in time. In this paper, we propose two new recourse strategies for the SS-VRPTW-CR, together with their closed-form expressions for efficiently computing their expectations: The first one allows us to take vehicle capacities into account; The second one allows us to optimize routes by avoiding some useless trips. We propose two algorithms for searching for routes with optimal expected costs: The first one is an extended branch-and-cut algorithm, based on a stochastic integer formulation, and the second one is a local search based heuristic method. We also introduce a new public benchmark for the SS-VRPTW-CR, based on real-world data coming from the city of Lyon. We evaluate our two algorithms on this benchmark and empirically demonstrate the expected superiority of the SS-VRPTW-CR anticipative actions over a basic "wait-and-serve" policy.
The first SS-VRP-C has been studied by @cite_35 , @cite_54 and @cite_44 as a generalization of the SS-TSP-C. @cite_5 considered general integer demands and compared different heuristics. @cite_0 considered a VRP with stochastic Customers and Demands (SS-VRP-CD). A customer demand is assumed to be revealed either when the vehicle leaves the previous customer or when it arrives at the customer's own location. Two different recourse strategies are proposed, as illustrated in Figure . For both strategies, closed-form mathematical expressions are provided to compute the expected total distance, provided a first stage solution. @cite_8 and @cite_43 developed the first exact algorithm for solving the SS-VRP-CD for instances up to 70 customers, by means of an integer L-shaped method. @cite_15 later proposed a tabu search to efficiently approximate the solution. Experimentations are reported on instances with up to 46 customers. @cite_3 later developed an adaptive memory programming metaheuristic for the SS-VRP-C and assessed it on benchmarks with up to 483 customers and 38 vehicles.
@cite_35 @cite_8 @cite_54 @cite_3 @cite_44 @cite_0 @cite_43 @cite_5 @cite_15
1546027924 2085952738 2031901413 1984143531 2047664145 2047612779
In this article, the following stochastic vehicle routing problem is considered. Each customer has a known probability of presence and a random demand. This problem arises in several contexts, e.g., in the design of less-than-truckload collection routes. Because of uncertainty, it may not be possible to follow vehicle routes as planned. Using a stochastic programming framework, the problem is solved in two stages. In a first stage, planned collection routes are designed. In a second stage, when the set of present customers is known, these routes are followed as planned by skipping the absent customers. Whenever the vehicle capacity is attained or exceeded, the vehicle returns to the depot and resumes its collections along the planned route. This generates a penalty. The problem is to design a first stage solution in order to minimize the expected total cost of the second state solution. This is formulated as a stochastic integer program, and solved for the first time to optimality by means of an integer L-shaped method. We present an adaptive memory programming (AMP) metaheuristic to address the robust capacitated vehicle routing problem under demand uncertainty. Contrary to its deterministic counterpart, the robust formulation allows for uncertain customer demands, and the objective is to determine a minimum cost delivery plan that is feasible for all demand realizations within a prespecified uncertainty set. A crucial step in our heuristic is to verify the robust feasibility of a candidate route. For generic uncertainty sets, this step requires the solution of a convex optimization problem, which becomes computationally prohibitive for large instances. We present two classes of uncertainty sets for which route feasibility can be established much more efficiently. Although we discuss our implementation in the context of the AMP framework, our techniques readily extend to other metaheuristics. Computational studies on standard literature benchmarks with up to 483 customers and 38 vehicles demonstrate that the proposed approach is able to quickly provide high-quality solutions. In the process, we obtain new best solutions for a total of 123 benchmark instances. We consider a natural probabilistic variation of the classical vehicle routing problem (VRP), in which demands are stochastic. Given only a probabilistic description of the demand we need to design routes for the VRP. Motivated by applications in strategic planning and distribution systems, rather than resolving the problem when the demand becomes known, we propose to construct an a priori sequence among all customers of minimal expected total length. We analyze the problem using a variety of theoretical approaches. We find closed-form expressions and algorithms to compute the expected length of an a priori sequence under general probabilistic assumptions. Based on these expressions we find upper and lower bounds for the probabilistic VRP and the VRP re-optimization strategy, in which we find the optimal route at every instance. We propose heuristics and analyze their worst case performance as well as their average behavior using techniques from probabilistic analysis. Our results suggest that our approac... The standard vehicle-scheduling problem is deterministic, assuming all factors are known with certainty in advance of scheduling. In practice there are several areas which might contain uncertainty. This paper suggests ways of tackling these, but concentrates on problems where some customers do not need deliveries during a scheduling period. If the number of such customers is small, semi-fixed routes may be acceptable. As the number of customers omitted rises, there comes a point when rescheduling becomes preferable. The potential savings made by semi-fixed or variable routes over fixed routes are estimated for standard problems. The implications of these savings are then evaluated for a wholesale distributor. This paper considers a version of the stochastic vehicle routing problem where customers are present at locations with some probabilities and have random demands. A tabu search heuristic is developed for this problem. Comparisons with known optimal solutions on problems whose sizes vary from 6 to 46 customers indicate that the heuristic produces an optimal solution in 89.45 of cases, with an average deviation of 0.38 from optimality.