Reoptimization strategies for a dynamic vehicle routing problem with mixed backhauls

Reoptimization strategies for a dynamic vehicle routing problem with mixed backhauls

0.00 Avg rating0 Votes
Article ID: iaor201522267
Volume: 64
Issue: 3
Start Page Number: 214
End Page Number: 231
Publication Date: Oct 2014
Journal: Networks
Authors: ,
Keywords: programming: dynamic, combinatorial optimization, networks, heuristics
Abstract:

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; that is, (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 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.

Reviews

Required fields are marked *. Your email address will not be published.