This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Irnich, S. Search for Related Content

A Unified Modeling and Solution Framework for Vehicle Routing and Local Search-Based Metaheuristics

Deutsche Post Endowed Chair of Optimization of Distribution Networks, RWTH, Aachen University, Aachen, Germany
sirnich{at}or.rwth-aachen.de

This paper presents a new unified modeling and heuristic solution framework for vehicle-routing problems (VRPs) with complex side constraints. The work is focused on strong modeling capabilities as well as efficient solution procedures to be used in all kinds of metaheuristics. From the modeling point of view, the framework covers a variety of standard VRP types with classical constraints such as capacity, distance, route length, time window, pairing, and precedence constraints, but also nonstandard "rich" VRPs. From the methodological point of view, local search (LS) is the key solver engine to be used in heuristic solution procedures. First and foremost, the framework introduces two generic techniques for the efficient exploration of edge- and node-exchange neighborhoods. New preprocessing methods allow (n^k) neighborhoods to be searched in time complexity (n^k), i.e., without an additional effort for feasibility testing in the worst case. Moreover, for accelerating LS in the average case, Irnich et al. [Irnich, S., B. Funke, T. Grünert. 2006. Sequential search and its application to vehicle-routing problems. Comput. Oper. Res. 33 2405–2429] have introduced sequential search that is here adapted to cope with rich VRPs (complex side constraints). Computational tests on different types of VRPs indicate that the proposed techniques are highly efficient. Sequential search procedures outperform the currently most efficient search methods, which are based on lexicographic search, on large-scale instances and for nearly all types of neighborhoods by factors of between 10 and 1,000.

Key words: local search; vehicle routing; rich vehicle-routing problems; resource-constrained paths
History: received August 2006; revised March 2007; accepted August 2007.