Note on Stochastic Vehicle Routing With Delivery Choice Under Recourse Options

Abstract

ABSTRACT In this paper, we consider the stochastic vehicle routing problem with delivery choice, where, upon reaching a particular customer, the driver has the choice of how much to deliver once the customer demand is revealed. In our earlier work, a basic version of the problem was considered, in which the driver cannot return to the depot midway in a route to replenish the cargo on board (see Venkateshan and Mathur 2025). In the present work, we expand on the choices that the driver has by allowing the driver to return to the depot to replenish before returning to the same customer or to proceed to the next customer. We prove the optimality of different threshold‐based fulfillment policies. Tests show that these policies significantly reduce the computational effort needed to determine the optimal fulfillment policy along a route, as well as its associated expected profit. We also show that a single‐vehicle tour that visits all customers is optimal even if multiple vehicles are allowed.