Optimizing the Deployment of Static and Mobile Roadside Units Using a Branch-and-Price Algorithm

The roadside unit (RSU), which enables vehicle-to-infrastructure communication, is essential for improving the communication performance of vehicular ad hoc networks. However, optimizing the deployment of RSUs while considering their deployment at both fixed locations and on mobile vehicles remains a challenging issue. To bridge this gap, we develop two spatio-temporal networks derived from vehicle trajectories. Subsequently, the joint deployment challenge of static and mobile RSUs is articulated as a mixed-integer programming model. After linearization, the model can be directly solved by CPLEX. Additionally, the integrated optimization problem can also be formulated as a route-based model. Due to the exponential growth of route numbers, a branch-and-price (BAP) algorithm is designed to solve the route-based model. Within the framework of the BAP, we develop a heuristic technique for generating effective initial solutions. Based on the characteristics of the spatio-temporal network, a directed acyclic graph shortest path algorithm is utilized to accelerate the solution of column generation pricing problem at each node. Simulation examples are presented to demonstrate the proposed algorithm. The results indicate that the BAP can generate verifiable high-quality solutions and has a significant speed advantage over CPLEX for large-scale problems. Furthermore, a series of sensitivity analyses are conducted to assess the system’s responses to various influencing factors.