A Branch-and-Benders-Cut Decomposition Framework for Park-and-Ride Location Optimization

Park-and-ride (P&R) facility location optimization involves coupled facility-opening decisions and probabilistic traveler allocation. This study develops a Branch-and-Benders-Cut Decomposition (B&CBD) framework for exact optimization under a specified multinomial logit (MNL) discrete choice model. Following the reformulation of the nonlinear model as a mixed-integer linear programming (MILP) model, the framework exploits origin–destination (OD) separability by retaining facility-location decisions in the master problem and solving traveler-allocation decisions through independent subproblems. Benders decomposition is integrated with a branch-and-cut algorithm, embedding cut generation within a single search tree and avoiding repeated master-problem optimization in the conventional Benders loop. An in–out strategy further guides cut generation using interpolated separation points. Computational experiments on synthetic instances compare the proposed framework with classical Benders decomposition, its in–out variant, and direct MILP solution. B&CBD outperforms the tested Benders variants, although a direct solution is generally faster for small instances. Across 12 Chicago network-based instances, B&CBD reaches the prescribed optimality tolerance in all cases, compared with 10 for the direct solution, and achieves shorter runtimes in all six instances with 20 candidate facilities.