Districting for routing with stochastic customers

Abstract

We introduce the vehicle routing and districting problem with stochastic customers (VRDPSC). This problem is modelled and solved as a two-stage stochastic program during which the districting decisions are made in the first stage and the Beardwood–Halton–Hammersley formula is used to approximate the expected routing cost of each district in the second stage. District compactness is also considered as part of the objective function. We have developed a large neighbourhood search heuristic for VRDPSC. The heuristic was tested on modified Solomon instances and on modified Gehring and Homberger instances. Extensive computational results confirm the effectiveness of the proposed heuristic.