Positioning communication infrastructures in vehicular networks: algorithms for maximizing the area of the Delta network

The placement of communication infrastructure in Vehicular Ad Hoc Networks (VANETs) consists of determining the location of Roadside Units (RSUs) to maximize connectivity under deployment constraints. Traditional approaches evaluate connectivity in a binary manner, disregarding its duration throughout the trip. The Delta metric provides a more comprehensive evaluation by relating the fraction of travel time during which vehicles remain connected (ρ1) to the fraction of vehicles that achieve this connectivity level (ρ2). In this work, the problem is addressed by maximizing the area under this curve, considering a maximum number of RSUs. A greedy algorithm and a GRASP-based metaheuristic algorithm are developed, and their results are compared against those obtained by the exact model solved using CPLEX. Results show that the greedy algorithm achieves optimal solutions in small instances, and that both algorithms produce practically equivalent solutions across the evaluated scenarios.