Generalized Riskiness Index in Vehicle Routing Under Uncertain Travel Times: Formulations, Properties, and Exact Solution Framework

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 motivate it better. 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. We mainly reduce the solution space by exploiting the GRI and budget constraints’ properties without losing 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. It can consistently solve instances involving up to 50 nodes, outperforming state-of-the-art methods by more than doubling the manageable instance size.