A roadside unit location problem under uncertainty in demand, migration, and processing

Autonomous vehicle technology is expected to revolutionize the automotive and transportation industries. Because of the large requirements of advanced sensors, abundant computation, and high-speed communication devices, the high production cost is the fundamental barrier to promoting and popularizing autonomous vehicles. Benefiting from the Internet of Things and cloud computing technologies, a large number of roadside units (RSUs) deployed can push the computing capabilities from vehicles to the edge of the network. However, existing studies on vehicle edge computing problems and RSU location models have paid less attention to the uncertainties with regard to model parameters and decision processes. In this paper, we develop a robust satisficing RSU location model integrated with the scheduling of vehicle edge computing. The entropic-risk-based constraints involving uncertainty in the demands for computing tasks and random efficiency in processing and migration are employed to deal with the operational scheduling constraints. The objective is to minimize the riskiness of violating the targets of capacity and latency. We show that this robust satisficing model can be reformulated as an equivalent mixed-integer linear/convex optimization model based on the probability distribution of demands for computing tasks. Both the exact cutting plane approach and the linear-piecewise outer approximation method are designed. Several model extensions are also discussed. The numerical experiments illustrate that compared with the cutting-plane method, the outer approximation method achieves higher computational efficiency when the number of piecewise-linear constraints is small or when dealing with large-scale networks, while the cutting plane method ensures the optimality of solutions. Therefore, decision makers can choose between the two algorithms depending on the trade-off between solution accuracy and computational efficiency. Besides, our robust satisficing model is computationally tractable, and has a better out-of-sample performance and more even distribution of processing capabilities than the benchmark models. Compared with the static policy, the periodic scheduling policy can further improve the satisficing performance. A higher budget for RSU locations results in a greater level of risk intolerance.