Static vs. Dynamic Policies for Vehicle Routing Problems with Backhauling and Dynamically Arising Customer Demands

Abstract

Dynamic vehicle routing problems (VRP) have attracted more attention than dynamic vehicle routing problems with backhauling (VRPB) in the relevant literature. Dynamic VRPB are more complex than dynamic VRP, and since VRP are a special case of VRPB, models and algorithms for dynamic VRPB can easily be adapted for dynamic VRP. In this paper, we compare static vs. dynamic policies for solving dynamic VRPB with dynamically arising customer delivery and pickup demands. We develop MILP formulations and search algorithms for small-to-mediumsized problems under static and dynamic policies. Although dynamic policies are always at least as good as static policies, we observe from numerical experimentations that static policies perform relatively well for small-sized problems and low degrees of dynamism (dod). On the other hand, dynamic policies are expected to perform significantly better than static policies for large-sized problems, high degrees of dynamism (dod) and early availabilities of dynamic customer delivery and pickup demand information. We conclude the paper by providing directions for future research on dynamic VRPB