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

摘要

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 (nk) neighborhoods to be searched in time complexity (nk), 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.