10th International Conference on Computational Management
HEC Montréal, 1 — 3 May 2013
10th International Conference on Computational Management
HEC Montréal, 1 — 3 May 2013
WA1 Vehicle Routing I
May 1, 2013 10:30 AM – 12:30 PM
Location: Mary Husny
Chaired by Jean-François Cordeau
4 Presentations
-
10:30 AM - 11:00 AM
The Vehicle Routing Problem with Hard Time Windows and Stochastic Service Times
In this presentation we address the Vehicle Routing Problem with Hard Time Windows and Stochastic Service Times (VRPTW-ST). The VRPTW-ST can be defined considering a fleet of homogeneous vehicles initially located at a depot, and a set of customers to be serviced. A time window and a stochastic service time are associated with each customer. Service time probability distributions are supposed to be known and mutually independent. A non-negative travel cost and travel time among customers and depot are also known.
The VRPTW-ST consists of finding a set of vehicle routes such that: (i) Routes start and end at the depot; (ii) All customers are served once; (iii) Service at customers starts within the given time window. Vehicles are however allowed to arrive before the beginning of a time window. In this case vehicles must postpone the beginning of the service until the customer's time window opens. Vehicles are not allowed to arrive after the end of the time window. (iv) The global probability that the route plan is feasible with respect to customers' time windows once the customers' service time becomes known, is higher than a specified "reliability" threshold; (v) The travel distance is minimized.
The VRPTW-ST belongs to the broad family of stochastic Vehicle Routing Problems. Several sources of uncertainty and different solution approaches have been investigated in the literature. Stochastic service and/or travel times have been considered in several studies where either customer time windows are absent, or soft, or a maximal route duration is considered. The VRPTW-ST addresses uncertainty by means of a probabilistic constraint. With respect to previous works, it considers a combination of service time uncertainty and customers hard time windows. To the best of our knowledge, such a problem has never been studied before.
We solve the VRPTW-ST by branch-and-cut-and-price. In particular we provide a new set-partitioning formulation which includes a probabilistic constraint. The column generation subproblem is solved via Dynamic Programming. In order to reduce the number of considered states, we deploy new heuristic and exact dominance rules taking into account both route reduced cost and success probability. This is done by developing a recursive method to exactly compute the arrival time probability distribution at customers. Furthermore, we speed up the algorithm by alternating dynamic programming and Tabu Search in the subproblem, and by dynamically adding violated inequalities.
We finally perform an extensive computational experiences on instances derived from the Solomon's database with two main purposes: 1) Analyze the model behavior under different conditions, such as different service time probability distributions and reliability thresholds; 2) Verify the effectiveness of our algorithm. Results show that our model displays several advantages when benchmarked against deterministic planning approaches that are based on average or worst case estimates of the service time values. Furthermore, our algorithm optimally solves most of the 50-customer instances derived from the family 1 of the Solomon's database.
-
11:00 AM - 11:30 AM
A Branch-Cut-and-Price Algorithm for the Vehicle Routing Problem with Stochastic Demands
This talk presents a state-of-the-art branch-cut-and-price (BCP) algorithm for the vehicle routing problem with stochastic demands (VRPSD). We adapt the model of Christiansen and Lysgaard (Christiansen, H. C. and Lysgaard, J. (2007). A branch-and-price algorithm for the capacitated vehicle routing problem with stochastic demands. Operations Research Letters, 37, 773–781.) and formulate the VRPSD as a set partitioning model with additional constraints. Feasible routes are generated using a dynamic programming algorithm executed over a state-space graph. Our method combines 2-cycle elimination with ng-routes. In addition, our pricing problem is significantly accelerated by the introduction of a new aggregate dominance rule. To speed up the generation of negative reduced costs columns, we use a tabu search heuristic and a bidirectional labelling algorithm. We also add capacity constraints and subset-row inequalities dynamically in order to strengthen the linear relaxation of the master problem. To derive integer solutions, we dynamically choose between 2 types of branching methods. As extensive tests illustrate, our algorithm is very competitive with the one of Christiansen and Lysgaard. We manage to solve 20 additional instances and we considerably improve the computing times for instances already closed. Only 2 instances out of the 40 considered remain unsolved.
-
11:30 AM - 12:00 PM
A Branch-and-Price Approach for a Stochastic Vehicle Routing Problem with Correlated Demands.
Many applications of the Vehicle Routing Problem (VRP) with correlated stochastic demands (supplies) exist in real-life logistic systems. In this paper, we model one type of these problems which is encountered in the context of milk collection from the milk producers' farms in the Province of Quebec. In the derived model, the uncertainty in terms of producers' daily production levels is represented through a set of finite scenarios. We propose a branch-and-price solution approach to optimally solve this problem. Computational results showed that this approach is able to solve instances with up to 25 producers and 10 scenarios.
-
12:00 PM - 12:30 PM
Benders Decomposition for Production Routing under Demand Uncertainty
The production routing problem (PRP) concerns the production and distribution of a single product from a production plant to multiple customers using capacitated vehicles in a discrete and finite time horizon. The PRP is a generalization of the inventory routing problem (IRP) obtained by incorporating production lot-sizing decisions. In this study, we consider the stochastic PRP with demand uncertainty in a two-stage decision process. The decisions in the first stage include production setups and customer visit schedules, while the production and delivery quantities are determined in the second stage. The objective is to jointly minimize the expected total production, inventory, distribution and routing costs. We develop exact solution approaches based on Benders decomposition together with several enhancements for this problem. Two different Benders reformulation schemes are proposed. Furthermore, we compare a standard implementation of the Benders algorithm to one that integrates the Benders cuts within a branch-and-cut framework. This latter implementation is called branch-and-Benders-cut (BBC) and uses only one enumeration tree for the Benders master problem. The Benders master is further enhanced with lower bound lifting inequalities, scenario group cuts and Pareto-optimal cuts. The best version of the Benders decomposition algorithm provides better results than a branch-and-cut algorithm on the standard formulation when solving a large number of scenarios, while the performance of the branch-and-cut algorithm relies heavily on the CPLEX cuts. We further exploit the reoptimization capability of the Benders approach in two stochastic settings, namely, a sample average approximation scheme to handle a large number of scenarios, and a rolling horizon framework for a dynamic and stochastic variant of the PRP. The results show that the computing time of the Benders algorithm using reoptimization is reduced by approximately 40-50% and more than 80% compared to the Benders algorithm without reoptimization and the branch-and-cut algorithm, respectively.