A general approach for controlling vehicle en-route diversions in dynamic vehicle routing problems

Previous research has shown that vehicle en-route diversion can improve the efficiency of dynamic vehicle routing processes. However, an uncontrolled utilization of en-route diversions may increase demands on drivers and cause distraction. This is likely to result in more accidents or reduced productivity which generates additional costs. Since the benefits to the solution quality make a prohibition of en-route diversions unattractive, we propose a general penalty cost based approach for controlling diversions. In contrast to known approaches that allow all diversions, the proposed approach also considers negative application-dependent consequences of diversions on drivers. The approach limits diversions to those which improve the solution quality above a customizable and application-dependent threshold that estimates their negative consequences. We evaluate the proposed general approach by applying it on an exemplary basis to recent deterministic and pro-active real-time routing approaches. Computational experiments show the impact of different penalty cost values on the resulting number of diversions as well as on the attained solution quality. Based on these results, we derive reasonable application-dependent penalty cost values for considering both the contradicting aims of quick request delivery and reducing diversions to a desired extent.