Robust Road-Side Unit Location Problem

Abstract

The prevalence and development of autonomous vehicle technology can reshape the status quo in vehicle manufacture, transportation, and logistics industries, leading to safer daily travel activities, higher power savings, and lower urban pollution. Traditional autonomous vehicle technology focuses on advancing vehicle-related technology, aiming to equip vehicles with high computational capability at a cost. One key initiative to improve traffic information collection and processing is the development and enhancement of smart road systems. This is often done by deploying a large number of roadside units (RSUs) thanks to the internet of things and cloud computing technology. However, few studies have explored RSU location planning problems under uncertainty. Existing RSU location models in dynamic edge computing scheduling mostly ignore uncertainties associated with task transmission and model parameters. We develop a two-stage robust satisficing RSU location model featuring uncertain demands for computing tasks and random delays in task processing and transmission. The optimization model minimizes the riskiness of violating various capacity budgets and task latency thresholds. We reformulate the robust RSU location model as an equivalent mixed-integer convex optimization model that can be solved by a cutting plane algorithm. We propose two acceleration methods to enhance the problem-solving process. The numerical experiments illustrate that our robust model is computationally tractable and outperforms the deterministic model and queuing model in various metrics. The resulting RSU location pattern differs significantly from that of the deterministic and queueing-based models. Specifically, the robust model can reduce computing task transmission quantity, average task completion time, and the magnitude and probability of capacity budget violation both in our grid network and random-generated networks.