DYNAMIC ALLOCATION OF RENEWABLE ENERGY THROUGH A STOCHASTIC KNAPSACK PROBLEM FORMULATION FOR AN ACCESS POINT ON THE MOVE
By: Elif Tugce Ceran
The problem studied in this thesis has been motivated by recent industry efforts toward providing Internet service in areas of the world devoid of regular telecommunications infrastructure via flying or floating platforms in the lower stratosphere. According to the abstraction in the thesis, the Access Point on the Move (APOM) having a renewable energy supply feature (solar, wind, etc.) must judiciously allocate this resource to provide service to users that demand service from it while it moves over an area. Within the problem setup, users with various stochastic characteristics (resource demands or rewards) appear in a sequential manner and the APOM must make online decisions whether or not to provide service to each appearing user. The objective of the APOM is to maximize a total utility (reward) provided to the encountered users. The problem is formulated as a 0/1 stochastic knapsack problem with stochastically growing dynamic capacity, solution of which is not available in previous literature. In this thesis, dynamic and stochastic policies are proposed considering the cases of both finite and infinite problem horizons. A threshold based policy based on dynamic programming approach is shown to be optimal under some conditions. Taking advantage of the structural characteristics of the optimal problem, promising suboptimal solutions that can adapt to short-time-scale dynamics are proposed and their performance are analysed in different scenarios. Kalman filtering based prediction of solar energy to inform online resource allocation policies is also considered.
Access Point on the move, dynamic resource allocation, decision problem, threshold policy , energy harvesting, dynamic programming, Stochastic 0/1 knapsack problem, Knapsack with dynamic capacity, Markov Decision Process, Reinforcement Learning, Finite horizon, Infinite horizon, Discount factor