The Effect of Limited Resources in the Dynamic Vehicle Routing Problem with Mixed Backhauls

Abstract

In the dynamic vehicle routing problem with mixed backhauls (DVRPMB) both pick up orders and delivery orders, not related to each other, are served. The requests of the former arrive dynamically while the latter are known a priori. In this study, we focus on the case of limited fleet, which fulfills all delivery orders, but may not have enough capacity to serve all pick up orders within the available working horizon. The problem’s dynamic nature and the attention to customer service raise interesting considerations, especially related to the problem’s objectives. The problem is solved through periodic re-optimization, acknowledging the fact that this pseudo-dynamic approach may lead to some limitations. For the underlying (static) optimization problem we propose appropriate objective functions, which account for vehicle productivity and propose a branch-and-price (BP) approach to solve it to optimality. The results indicate how the performance of the various objectives is impacted by different re-optimization frequencies and policies in this practically relevant environment of dynamic demand served by a limited fleet. Specifically, extensive experimentation indicates that accounting for vehicle productivity within a typical periodic re-optimization solution framework may result to higher customer service under a range of operational settings, in comparison to conventional objectives.

Keywords

• dynamic vehicle routing
• re-optimization
• dynamic pickup-and-delivery
• limited fleet in vehicle routing