Ninikas, G., Minis, I. 

NETWORKS, accepted - to appear in 2014

We investigate a dynamic routing problem that seeks to plan, in the most efficient way, dynamic pickup requests that arrive in real-time while a predefined plan of serving delivery requests is being executed. Delivery and pick up requests may be served in an arbitrary (mixed) order. We refer to this problem as the Dynamic Vehicle Routing Problem with Mixed Backhauls (DVRPMB). We address DVRPMB through iterative reoptimization. In addition to defining the reoptimization model, we drill-down to significant aspects concerning the reoptimization process; i.e. i) how to reoptimize, ii) when to reoptimize, and iii) what part of the new plan to communicate to the drivers. On some of these aspects, we establish theoretical insights. To solve the reoptimization problem, we propose a Branch-and-Price (B&P) approach and a novel insertion heuristic which is based on column generation and provides near optimal solutions in an efficient manner. We use extensive experimentation to test the proposed methods and analyze the related reoptimization policies. Based on the results obtained we propose reoptimization guidelines under various operational settings.

Keywords: dynamic vehicle routing, reoptimization, dynamic pickup-and-delivery, branch-and-price