The Vehicle Routing Problem with Dynamic Occasional Drivers

Abstract

Technological advances, such as smart phones and mobile internet, allow for new and innovative solutions for transportation of goods to customers. We consider a setting where a company not only uses its own fleet of vehicles to deliver products, but may also make use of ordinary people who are already on the road. This may include people who visit the store, who are willing to take a detour on their way home for a small compensation. The availability of these occasional drivers is naturally highly uncertain, and we assume that some stochastic information is known about their appearance. This leads to a stochastic vehicle routing problem, with dynamic appearance of vehicles. The contribution of this paper is a mixed integer programming formulation, and insights into how routes for the company vehicles could be planned in such a setting. The results of the stochastic model are compared with deterministic strategies with reoptimization.