743. Branch-and-Cut methods for the Vehicle Routing Problem with Stochastic Demands
Invited abstract in session MD-58: Branch-and-Cut, stream Vehicle Routing and Logistics.
Monday, 14:30-16:00Room: Liberty 1.13
Authors (first author is the speaker)
| 1. | Caio Tomazella
|
| UFSCar | |
| 2. | Pedro Munari
|
| Production Engineering Department, Federal University of Sao Carlos | |
| 3. | Reinaldo Morabito
|
| Dept. of Production Engineering, Federal University of São Carlos |
Abstract
The Vehicle Routing Problem with Stochastic Demands (VRPSD) involves optimizing the routes of a fleet of vehicles to fulfill customer demands while minimising traveling costs. Demand is uncertain, and is modeled using discrete positive values that are realised when the vehicle arrives at the customer. If demand exceeds the vehicle's load, a replenishment trip is required to fulfill the remaining demand, incurring additional expected recourse costs. These recourse costs, which must be considered in the objective function, are calculated through recursive equations. We propose a novel Mixed Integer Programming (MIP) formulation that linearises the recursive equations, allowing us to solve VRPSD instances to optimality using general purpose MIP solvers. Based on this formulation, we developed variants of the Branch-and-Cut method, using both simpler and more sophisticated separation algorithms for the expected recourse costs constraints. We also present Branch-and-Cut methods that employ combinatorial Benders cuts, which are based on the separate computation of the recourse costs. A computational experimentation was performed to assess the efficiency of the proposed methods, and to evaluate how the developed enhancements improve the method’s convergence.
Keywords
- Vehicle Routing
- Stochastic Models
- Branch and Cut
Status: accepted
Back to the list of papers