Greedy Algorithm for Routing Power and Source Assignment on a Digital Microgrid

In this paper, we propose the Greedy SmAlleSt-cost Path first (GRASP) algorithm to route power from sources to loads in a digital microgrid (DMG). Routing of power from Distributed Energy Resources (DERs) to loads of a DMG comprises the matching loads to DERs and the selection of the smallest -cost path from a load to its supplying DERs. In such a microgrid, one DER may supply power to one or many loads, and one or many DERs may supply the power requested by a load. We compare GRASP with an optimal method based on integer linear programming. GRASP addresses the NP-completeness of the optimal solution while finding paths with comparable costs. GRASP uses heuristics to select match sources and loads and to select the lowest -cost paths in the DMG. We compare the cost achieved by both methods on different test networks to show the trade-offs between lowering complexity and achieving optimal-cost paths. Our results show that GRASP approaches the costs attained by the optimal solution by small margins.