Optimizing RSU deployment in VANETs: a branch-and-benders decomposition approach considering information timeliness requirements

Vehicular ad hoc networks (VANETs) hold significant potential for enhancing road safety and traffic efficiency. The performance of VANETs heavily relies on the strategic deployment of roadside units (RSUs), which gather and disseminate critical information. A key challenge is that different types of information possess varying timeliness requirements, rendering delayed information ineffective. However, this crucial aspect has not been sufficiently addressed in the existing RSU deployment literature. To bridge this gap, we first classify operational scenarios based on discretized traffic flows and information types, analyzing their corresponding transmission time constraints. We then formulate an RSU deployment model that explicitly incorporates these heterogeneous timeliness requirements. To solve this complex problem, we develop a Branch-and-Benders decomposition (BBD) algorithm, which partitions the problem into a master problem for determining RSU locations and multiple subproblems for allocating vehicle communication demands in each scenario. The master problem is solved using a branch-and-cut procedure. Upon finding an integer feasible solution, the dual subproblems are solved to generate optimality and feasibility cuts that are dynamically added to the master problem. Furthermore, we introduce valid inequalities to accelerate convergence. Numerical experiments demonstrate that the proposed BBD algorithm can efficiently generate provably high-quality solutions.