Logic-based benders decomposition for multi-Period line planning with vehicle transfers

This paper studies the multi-period line planning problem with vehicle rotation, a fundamental challenge in public transportation system design that integrates line selection, service frequency determination, and inter-period vehicle transfers. The temporal coupling induced by vehicle rotation generates strong interdependencies across planning periods, resulting in large-scale, highly combinatorial optimization models that are difficult to solve with existing mixed-integer programming methods. To address this complexity, we develop two exact decomposition-based solution frameworks. The first is a constraint satisfaction algorithm that iteratively relaxes and reinstates the vehicle flow-balance constraints, progressively reconstructing feasibility through a sequence of restricted master problems. The second is a logic-based Benders decomposition framework in which the feasibility verification stage is reformulated as a max-flow and min-cut problem. This reformulation enables the efficient identification of infeasibilities and the generation of strong feasibility cuts derived from the structure of the underlying network. Extensive computational experiments on three real public transportation networks, Istanbul Metrobüs, Athens Metro , and Quito Trolebús , demonstrate the efficiency and scalability of the proposed methods. The logic-based decomposition algorithm attains optimal solutions up to 99% faster than a state-of-the-art commercial solver and successfully solves instances with more than 300 lines that remain unsolved within 24 hours by conventional algorithms. The results confirm that embedding network-flow reasoning within a logic-based decomposition framework yields a computationally tractable and structurally coherent methodology for large-scale multi-period line planning with vehicle rotation.