Stochastic single vehicle routing problem with delivery and pick up and a predefined customer sequence

In this paper we study the routing of a single vehicle that delivers products and picks up items with stochastic demand. The vehicle follows a predefined customer sequence and is allowed to return to the depot for loading/unloading as needed. A suitable dynamic programming algorithm is proposed to determine the minimum expected routing cost. Furthermore, the optimal routing policy to be followed by the vehicle’s driver is derived by proposing an appropriate theorem. The efficiency of the algorithm is studied by solving large problem sets.

► We study routing of a vehicle that delivers/picks up products with stochastic demand.
► We develop and analyze an optimal dynamic programming algorithm.
► We identify the optimal routing policy by proposing and proving an appropriate theorem.