G-ERMP Algorithm: A Graph-Based Approach for Replica Allocation in Energy Management Systems

Algorithm 4 shows the pseudo-code of G-ERMP. The algorithm has as input the set of scenarios, ξ, the vector of vehicles with their request size, ri, and their capacity, Ci. The output consists of the set of providers P and the set of replicas' assignments S for the current energy manager period. The main idea of G-ERMP is to create a graph based on the replica allocations obtained for each scenario by the GD-ERMP algorithm. Each vertex of this graph represents a vehicle; each edge of the graph indicates a requester j to provider i assignment, weighted by the number of scenarios in which a request of j has been allocated to i by the GD-ERMP algorithm. Then, the algorithm partitions this graph into the set of providers and the set of requesters, and determines the number of replicas for each requester. This partitioning is done so that, for each vehicle, Constraint (9) is satisfied for more than (1 − β) · |ξ| scenarios./n/nG-ERMP starts with an empty set of providers P and empty set of replicas' assignments (Lines 1-2). In each iteration of the algorithm, these sets will be updated. Also, we define vector σ = {σi} to store the number of scenarios in which Constraints (9) are satisfied for each vehicle i (Line 3). We define Γ as a set of vehicles for which Constraints (9) are satisfied. G-ERMP initializes Γ with the empty set (Line 4). Sets/n/nP˜/nand ˜S = { ˜Si} are used to save the set of providers and the set of replicas obtained for each scenario by GD-ERMP (Lines 5-6). G-ERMP creates a graph with |V| vertices. Each vertex represents a vehicle and each edge indicates a request-provider assignment. The weight of an edge from vertex j to vertex i is denoted by wji and is defined as the number of scenarios in which vehicle j is assigned to vehicle i. The indegree of vertex i, i.e., the total weight of edges adjacent to vertex i, is stored in vector indeg = {indegi} (Lines 7-10)./n/nIn order to find the minimum number of providers, in each iteration, G-ERMP selects the vehicle as the provider that has received the maximum number of requests from the various scenarios. Therefore, it choses the vertex with the maximum indegree as a provider (Line 12). Then, it updates the set of providers (Line 13). When a vehicle is selected as a provider, it runs its requests locally, which means that, for this vehicle, Constraint (9) is automatically satisfied. Thus, it adds the current provider to the set Γ (Line 14). The algorithm then updates the replica assignment of vehicles in two steps. In the first step, since vehicle j is selected as a provider, the algorithm removes all the previous assignments from vehicle j on any provider. In fact, the algorithm checks if a request from vehicle j has been assigned to a provider i, it removes that assignment (Lines 16-17). Furthermore, since the remaining capacity of vehicle i is increased, it might be able to serve more requests. Thus, for each vehicle k ∈ V − Γ willing to be assigned to vehicle i, the algorithm updates the assignment if vehicle i has enough capacity. It also updates σ for vehicle k. If σk is greater than (1 − β) · |ξ|, the algorithm adds vehicle k to Γ. Therefore, the algorithm will not generate any further replica for that vehicle (Lines 18-23). In the second step, the algorithm assigns requests from each vehicle g willing to be assigned to vehicle j. It updates the assignment if vehicle i has enough capacity. It also updates σ for vehicle g. If σg is greater than (1 − β) · |ξ|, the algorithm adds vehicle g to Γ (Lines 24-29). The algorithm continues this procedure until all the vehicles are added to set Γ./n/nComplexity Analysis. To investigate the time complexity of G-ERMP, we analyze the time complexity of the two main parts of the algorithm. In the first part, G-ERMP calls GD-ERMP for each scenario. Therefore, as analyzed in the previous section, the time complexity of the first part is O(|ξ| · |V|3). In the second part, G-ERMP builds a graph based on the solution obtained in the first part. The time complexity of the second part mainly depends on the loop in Lines 11-29, which executes O(|V|) times. The main part of the loop consists of the loop in Lines 15-23 which executes O(|P| · (|V/Γ|)) times. Therefore, the time complexity of the second part is O(|V|3). As a result, the total time complexity of G-ERMP is O(|ξ| · |V|3 + |V|3) = O(|ξ| · |V|3), since |ξ| is typically much smaller than |V|3. Thus, the time complexity of G-ERMP is polynomial in the number of vehicles and scenarios.