Resource extension functions: properties, inversion, and generalization to segments

摘要

The unified modeling and solution framework, presented by Desaulniers et al. (Fleet Management and Logistics. Kluwer Academic, Boston, pp 57–93, 1998), is applicable to nearly all types of vehicle-routing and crew-scheduling problems found in the literature thus far. The framework utilizes resource extension functions (REFs) as its main tool for handling complex side constraints that relate to a single vehicle route or crew schedule. The intention of this paper is to clarify which properties of REFs allow important algorithmic procedures, such as efficient representation of (partial) paths, efficient cost computations, and constant time feasibility checking for partial paths (= segments) and their concatenations. The theoretical results provided by the paper are useful for developing highly efficient solution methods for both exact and heuristic approaches. Acceleration techniques for solving resource-constrained shortest-path subproblems are a key success factor for those exact algorithms which are based on column generation or Lagrangean relaxation. Similarly, those heuristic algorithms which are based on resource-constrained paths can benefit from efficient operations needed to construct or manipulate segments. Fast operations are indispensable for efficient local-search algorithms that explore edge-exchange or node-exchange neighborhoods. Efficiency is crucial, since these operations are repeatedly performed in many types of metaheuristics.