We consider a vehicle routing problem with time windows under uncertain travel times where the goal is to determine routes for a fleet of homogeneous vehicles to arrive at the locations of customers within their stipulated time windows to the maximum extent, while ensuring that the total travel cost does not exceed a prescribed budget. Specifically, a novel performance measure that accounts for the riskiness associated with late arrivals at the customers, called the generalized riskiness index (GRI), is optimized. The GRI covers several existing riskiness indices as special cases and generates new ones. We demonstrate its salient managerial and computational properties to better motivate it. We propose alternative set partitioning-based models of the problem. To obtain the optimal solution, we develop an exact solution framework combining route enumeration and branch-price-and-cut algorithms, in which the GRI is dealt with in route enumeration and column generation subproblems. By exploiting the properties of both the GRI and budget constraint, we mainly reduce the solution space without loss of optimality. The proposed method is tested on a collection of instances derived from the literature. The results show that a new instance of the GRI outperforms several existing riskiness indices in mitigating lateness. The exact method can solve instances with up to 100 nodes to optimality, and can consistently solve instances involving up to 50 nodes, outperforming state-of-the-art methods by more than doubling the manageable instance size.
View Effective Exact Solution Framework for Routing Optimization with Time Windows and Travel Time Uncertainty