Branch-and-Cut for the Active-Passive Vehicle Routing Problem

This paper studies the active-passive vehicle-routing problem (APVRP).The APVRP coversarange of logistics applications where pickup-and-delivery requests necessitate a joint operation of active vehicles (e.g., trucks) and passive vehicles (e.g., loading devices such as containers). It supports a flexible coupling and decoupling of active and passive vehicles at customer locations in order to achieve a high utilization of both resources. This flexibility raises the need to synchronize the operations and the movements of active and passive vehicles in time and space. The contribution of the paper is twofold. First, we present a branch-and-cut algorithm for the exact solution of the APVRP that is based on Benders decomposition. Second, our approach can be generalized to deal with other vehicle-routing problems with timing aspects and synchronization constraints. Especially for the more complicated cases in which completion time or duration of routes is part of the objective, we show how stronger optimality cuts can be defined by identifying minimal responsible subset. Computational experiments show that the proposed algorithm outperforms the previousstate-of-the-artfortheAPVRPandcomputeoptimalsolutionsformorethan70previously unsolved benchmark instances.