Premium
Reoptimization strategies for a dynamic vehicle routing problem with mixed backhauls
Author(s) -
Ninikas George,
Minis Ioannis
Publication year - 2014
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21567
Subject(s) - computer science , routing (electronic design automation) , vehicle routing problem , heuristic , plan (archaeology) , process (computing) , mathematical optimization , column generation , order (exchange) , operations research , computer network , mathematics , economics , artificial intelligence , archaeology , history , operating system , finance
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. © 2014 Wiley Periodicals, Inc. NETWORKS, Vol. 64(3), 214–231 2014