The vehicle routing problem with stochastic demands (VRPSD) generalizes the classic capacitated vehicle routing problem (CVRP) by considering customer demands as random variables that are revealed on vehicle arrival. Our work focuses on modeling VRPSD as a two-stage stochastic program, where a recourse policy describes the recourse actions that should be taken whenever a violation of the vehicle capacity constraint is observed. The objective function then combines the initial planned routes cost (first-stage cost) and the expected recourse cost (second-stage cost). Some state-of-the-art exact algorithms for the VRPSD are branch-and-cut algorithms that use integer-L shaped-based cuts for approximating the (expected) recourse cost function. In this presentation, I will discuss our current progress towards deriving stronger inequalities for better approximating this recourse cost function.

Specifically, we propose to approximate the recourse cost function with the value function of a network-flow type linear program and we then project this value function into the space of the original variables via Benders decomposition. However, due to the size of the network, a standard implementation of the Benders decomposition method can be too time-consuming. Instead, we generate the optimality/feasibility cuts by looking at a cone-relaxation of the original network-flow formulation. This approach has the potential to generate stronger cuts by solving smaller linear programs. Furthermore, by leveraging well known results on the combinatorial structure of network-flow polyhedra, we prove that, under some conditions, it is possible to improve the big-M coefficients of previously proposed integer-L shaped cuts. Computational experiments are still in progress and show the potential of this approach.

Stochastic inventory routing concerns the joint distribution (via vehicle routes) and replenishment of inventory in one warehouse, multiple retailer systems. In such systems, practical considerations impose that vehicle routes conform to a cyclic schedule, for example, according to a weekly repeating pattern, so that upstream and downstream planning processes can be managed efficiently. In this work, we explore a new variant of the stochastic cyclic inventory routing problem by imposing that retailer demand comes from a distributionally robust ambiguity set. This raises several fundamental questions, including what the structure is of optimal distributionally robust inventory replenishment policies for the joint replenishment of retailers in a vehicle route, and how this information can be conveyed into a branch-and-price scheme for optimal inventory routing. At the conference, we will provide insight into these fundamental questions, and provide several approaches based on a price-and-branch scheme.

We study the vehicle routing problem with time windows (VRPTW) under travel time uncertainty considering different uncertainty sets. We propose a new polynomial-time separation algorithm that can be used with any convex uncertainty set and easily incorporated into branch-and-cut, branch-and-price, or heuristic algorithms. This flexibility distinguishes the proposed algorithm from previous works in the robust VRPTW and the robust traveling salesman problem (TSPTW) literature, which mostly rely on the traditional cardinality-constrained uncertainty set or, more recently, on the knapsack uncertainty set. In addition to these uncertainty sets, we consider the ellipsoidal, factor models, and discrete uncertainty sets using instances from the VRPTW literature. We develop tailored branch-and-cut and branch-and-price-and-cut methods to validate the proposed separation algorithm for these sets. Finally, we evaluate the impact of the studied uncertainty sets on the trade-off between the robustness of the solution and its cost.

We address variants of the vehicle routing problem (VRP) under uncertain demand and travel times, considering pickup and delivery operations. Incorporating uncertainty into the formulations and solution methods for these problems poses additional challenges compared to other VRP variants due to the interdependence of pickup and delivery nodes, non-monotonic loads in vehicles, and the additional decision on the vehicle load when leaving the depot. To overcome these challenges, we introduce new approaches based on dynamic programming to effectively incorporate uncertainty in different variants of pickup and delivery operations via robust optimization. We consider the pickup and delivery problem with time windows (PDPTW) and the one-commodity pickup and delivery vehicle routing problem (1-PDVRP), and ways to incorporate uncertainty into compact formulations as well as tailored branch-and-cut methods. The results of computational experiments with benchmark instances show the efficacy of our approaches and their superior performance in comparison to existing approaches.