The Driver Assignment Vehicle Routing Problem

We introduce the driver assignment vehicle routing problem. In this problem customers are assigned to drivers before demand is known, and after demand is known a routing schedule has to be made such that every driver visits at least a fraction A of its assigned customers. We design a cluster first-route second algorithm to find good solutions to this problem. From our computational experiments we conclude that adhering to driver assignments can lead to an increase of the expected transportation costs of up to 21.0%, and on average 12.7%. Allowing a little flexibility, by choosing A=0.75, leads to an average increase in transportation costs of only 2.9\% with respect to not adhering to the driver assignments. Finally, for instances with A=0.75, we compare the expected transportation costs from constructing only new routes with customers that cannot be visited by their assigned driver, to the costs from trying to also assigning them to drivers that already have customers assigned to it. The former leads to an average increase in expected transportation costs of 15.3%.

Registration to Remy Spliet, spliet@ese.eur.nl is required for availability of lunch.

This event is organised by the Econometric Institute.
Twitter: @MetricsSeminars