Stochastic vehicle routing with delivery choice

Abstract

We consider the problem of designing delivery routes for vehicles where the vendor has the choice of how much of the demandfrom a customer to fulfill. The customer demand is known a priori only as a probability distribution. Exact customer demand isknown only after visiting the customer. Different customers are able to negotiate different prices for each unit of product with thevendor. Given a route, the objective is to decide at each customer location, how much demand to satisfy so as to maximize expectedprofit taking into account a linear penalty cost for unfulfilled demand and the vehicle routing costs. In this article, we developseveral new structural results for this problem. We illustrate how these structural results can be embedded in different heuristicframeworks commonly used for deterministic vehicle routing problems. This helps develop efficient routes for a single vehicle aswell as a multiple vehicle scenario for this stochastic variant. For small-sized problems that allow for exhaustive enumeration,we demonstrate the effectiveness of the illustrated heuristic. For larger problem instances, based on structural results, we developmethods that allow the heuristic to run more efficiently than otherwise. Results are reported on instances based on benchmarkinstances drawn from literature for upward of 100 customers and vehicle capacity up to 600 units. Computational times neededto heuristically solve such problems are within 1 100 s.