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

• A classification of different types of on-route diversions is provided.
• Depending on the negative impacts of diversions, two driver profiles are derived.
• A penalty cost based extension for controlling on-route diversions is proposed.
• Evaluation of penalty values by resulting diversions and attained solution quality.
• Managerial implications for an efficient parameter setting are derived.

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.