Networked rural electrification offers an alternative strategy to speed up electricity access in rural regions. By leveraging satellite imagery and GIS tools, an electrical distribution network links villages to suitably positioned generation facilities, thereby reducing overall electrification costs. The network design process begins by determining optimal paths between all node pairs, after which a cost-minimizing network topology is selected. Previous studies have shown that the A* (A-star) optimal pathfinding algorithm performs poorly in this context due to the intricate topography of rural settings. Although the multiplier-accelerated A (MAA) algorithm addresses major performance limitations, it still produces only a single path for each node pair, as with standard A. Depending on a single path, project risk increases, as various complications—such as inaccurate GIS data, unforeseen soil conditions, land rights conflicts, political obstacles, and others—may arise during actual implementation. This paper introduces a hybrid pathfinding technique that integrates a genetic algorithm with the A/MAA algorithm. The new method generates a set of near-optimal paths rather than a single optimal route for each connection. Having multiple path options enables project teams to respond rapidly to unforeseen challenges as new data emerges and to modify the network topology before or during construction with only minor effects on total project cost.
Achieving universal access to modern energy by 2030 represents an ambitious objective outlined in the United Nations’ seventh Sustainable Development Goal (SDG7) [1]. Although notable advances have been made, experts widely acknowledge that extending electricity to the remaining unelectrified population is becoming increasingly difficult [2, 3]. These people typically reside in small farming communities (i.e., villages) scattered across remote, hard-to-access areas. Present-day electrification efforts mainly rely on photovoltaic (PV) generation, since it can be installed relatively easily in most places and needs limited technical knowledge for upkeep. Nevertheless, precise capacity planning to achieve economic efficiency remains difficult for such small-scale systems owing to uncertainties affecting both demand and supply [4, 5].
On the supply side, while solar radiation data averaged over broad regions are reliable, actual irradiation at a specific site can differ substantially from regional averages due to local topographic shading and related placement challenges. Although the standard approach places renewable generation directly within individual villages, most villages were originally situated to prioritize access to farmland, water sources, safety, and other practical considerations. These historical decisions frequently result in suboptimal conditions for PV generation, and locating PV arrays exclusively within villages can create problems for both energy production and land use. On the demand side, rural populations often fluctuate considerably over time. Furthermore, per-capita electricity demand is hard to forecast over a 5–20-year horizon, as living conditions and local economies in rural areas can change rapidly. These elements complicate load growth projections, making capacity planning that depends on short-term demand estimates frequently unreliable. Consequently, both over-investment and under-investment are widespread in these small systems. The latest IEA study estimates that 660 million people will remain without access to electricity by 2030 if current methods remain unchanged [3].
To reduce the cost of rural electrification, a major research direction is to determine the most economical mix of energy sources [6, 7]. At the same time, another examines electrical or spatial network configurations to create optimal electricity supply structures [8, 9]. These methods prove effective when reliable forecasts are available or when generation sites face few restrictions. Regrettably, many rural areas fail to meet these requirements.
The present study adopts a distinct strategy centered on power system topology: developing a locally networked power system capable of adjusting to varying village demand levels while leveraging lower-cost or higher-performance sites for electricity generation. Although topological optimization has received considerable attention, most such research greatly simplifies the geometric characteristics of the search space to keep conventional optimization (i.e., routing) techniques computationally feasible. As demonstrated in Li et al. [10, 11], such simplifications can lead to significant inaccuracies and suboptimal outcomes. Consistent with our earlier research [10, 11], we consider it preferable to preserve the full geometric properties—including topography and accessibility—throughout the optimization process.
Figure 1 illustrates the proposed framework. The approach realizes rural electrification through a combination of localized and networked supply, aiming to achieve superior generation efficiency and resource use, enhance implementation flexibility, and provide an adaptable power system that can handle population movements and uneven load growth [10, 11]. We proceed under the premise that initial power system planning will inevitably be imperfect, given the substantial expense of detailed engineering and planning as well as the limited availability of accurate information without costly field surveys. These constraints are commonplace in rural electrification initiatives. Hence, the preliminary design relies on affordable satellite data and GIS tools. Additional refinements occur only after project feasibility has been confirmed.
Figure 1. The networked rural electrification framework.
Under this framework, multiple villages are interconnected using an electrical distribution network. Achieving true cost efficiency usually requires a more sophisticated layout than the straightforward radial configuration that is standard in rural power distribution [12, 13]. Overall expenses tend to drop when villages receive most of their power from larger, centrally located PV plants strategically placed to boost generation performance and reduce total capital investment. At the same time, smaller standalone systems are installed in each village to provide backup or emergency power [10, 11]. Fully engineering such a network involves numerous technical details—including load flow studies, cable dimensioning, and protection coordination—that go far beyond the aims of this preliminary optimization effort focused on terrain characteristics. Instead, the analysis here focuses on one key aspect: finding ways to reduce the cost of building links between villages and suitable generation sites in the difficult landscapes typical of rural areas.
Earlier studies by the authors [10, 11] have already presented the multiplier-accelerated A (MAA) algorithm, which delivers a major boost in efficiency when searching for near-optimal connections. The present paper addresses one of the critical outstanding issues that determines whether the networked rural electrification approach can succeed in practice: the need for adaptable routing between sites. This element is a vital piece of the complete methodology supporting networked rural electrification.
Clusters of villages without electricity access are typically located well away from urban centers and often lie in rugged or hard-to-reach areas (such as small islands). This research focuses on areas with challenging topography, where even minor adjustments to distribution line routes can lead to significant differences in construction and maintenance costs. Specific cases include the Mentougou district near Beijing, China, and the tropical highlands of western Rwanda, locations where the authors have conducted field investigations. In such environments, villages that are geographically close in terms of horizontal distance can still be separated by dramatic elevation shifts caused by mountain ridges or deep river valleys. These territories also feature restricted zones—such as protected nature areas or state-owned lands—where power lines are prohibited. In a digitized terrain map, pathfinding algorithms repeatedly assess the incremental cost of advancing in every possible direction from the present point and weigh those values against accumulated data before choosing the next step. The varied topography in these rural settings frequently causes the cost of movement to vary sharply with the chosen direction at each step. We term this strong directional dependence in cost across the search area ‘anisotropicity.’ Because of this, simple strategies that connect the closest villages with straight-line paths—as might work for high-voltage transmission corridors—result in a distribution network that falls well short of optimal performance [10, 11].
Constructing an optimal network essentially amounts to a route-finding exercise with two core components: (i) determining the cost of the (near) best path linking any pair of nodes, where each node represents either a village or a centralized generation plant, as shown in Figure 1; and (ii) selecting the overall network arrangement that yields the smallest total cost based on the path costs derived in the first step. Theoretically, classical A* pathfinding [14] could handle the first task, while a minimum spanning tree (MST) or a similar method could handle the second. Yet, as prior research has demonstrated [10, 11], standard A proves inefficient for this purpose, and most established acceleration techniques for A also face serious limitations in strongly anisotropic environments. In response, the authors created the multiplier-accelerated A (MAA) and adaptive multiplier-accelerated A (AMAA) algorithms [10, 11, 15]. These methods generate near-optimal outcomes using far fewer computing resources.
Compared with classical A, MAA typically reduces computation time by 90% while maintaining solution quality below 10%; the user can set the desired balance between accuracy and speed. AMAA further develops MAA to handle tougher cases in which routes must start within or bypass sizable regions that incur especially high routing costs. When these algorithms are applied with the MST technique, Figure 2 illustrates a near-optimal network configuration.
Figure 2. Typical optimal network. The connections shown result from applying the minimum spanning tree to the complete set of pairwise routes that link every node to all others.
To determine whether a networked strategy offers economic advantages, MAA outcomes can be benchmarked against the conventional per-village method of rural electrification. When the calculated cost of the networked option falls below that of the traditional approach, networked rural electrification becomes the more economical choice for the given terrain and village layout.
Because the MAA algorithm features prominently throughout this paper, its core characteristics are summarized here. Further explanations appear in Li et al. [10, 11].
(a) During optimal path search, the classical A algorithm evaluates the estimated cost of the current path against previously recorded cost data to guide each movement decision. When certain conditions are satisfied, a globally optimal solution can be assured;
(b) In anisotropic environments, the repeated comparisons described in (a) often compel the A algorithm to abandon partial searches and restart from initial stages many times during the overall routing process, rendering the procedure extremely inefficient;
(c) By introducing a parameter m, MAA deliberately dampens the influence of earlier decisions, thereby decreasing the number of premature restarts and lowering overall computational demand. Here, m controls the rate of attenuation. Setting m = 0 causes MAA to behave identically to classical A. The designation MAA(p) denotes MAA running with m set to p;
(d) As the value of m rises, processing effort declines while the resulting solutions generally deviate further from the true optimum;
(e) Extensive testing has shown that selecting m in the range of 0.5 to 2 typically cuts computation time by 80–98% while reducing solution quality by 5–20%. This range enables users to balance processing speed against desired accuracy based on project needs.
Figure 3 presents a representative view of MAA performance: t indicates computation time in seconds on a standard Windows i7 computer. The global minimum is obtained via classical A. The cost function incorporates expenses for materials, labor, and other factors [10, 11]. A common alternative – in fact, the default practical choice – relies on intuitive routing, also displayed in Figure 3. As the figure demonstrates, the expense associated with this intuitive method (namely, 805) substantially exceeds the costs achieved through systematic optimization, even though the intuitively chosen route occupies roughly the same geographic region as the MAA solutions. This contrast highlights the anisotropic character of rural landscapes: minor adjustments in route alignment can produce significant variations in total cost.
Figure 3. Comparing computed optimal path costs based on A and MAA. The global minimum is computed with the classical A algorithm, while the entries with m = x are routings computed with the MAA algorithm (see text). The straight-line cost computes the cost through all grid squares along a straight-line connection. The intuitive pole placement represents one possible route selected by intuition – i.e., intuitively avoiding the region with known high costs (blue background).
The illustration depicts the routing for a single node pair, which required 92 h when solved with classical A. A realistic network design typically involves linking numerous villages to several potential generation sites, resulting in hundreds of node-pair calculations. Consequently, high computational efficiency becomes essential.
Lastly, an important consideration is that the source data frequently contains errors of 20% or greater regarding technical parameters (such as elevation and soil types) and commonly overlooks critical socio-political constraints that only surface during later planning phases. As a result, any routing solution that stays within 10%–20% of the optimal cost is effectively equivalent to the global optimum under real-world field conditions.
Algorithms derived from A in our prior studies deliver only one near-optimal route for each routing challenge. Nevertheless, real-world deployment often reveals that this lone solution lacks sufficient robustness, since the data used during optimization is almost always partial or imprecise. Generating several near-optimal alternatives, therefore, proves highly useful, giving field teams viable options when conditions on the ground differ from expectations.
Routing procedures of this kind generally rely on a grid-based map in which each cell contains values for the main factors that determine construction costs. Such grid representations are standard in comparable optimization tasks [16, 17]. Here, the base map is usually created from satellite images and digital elevation data to limit the cost of early-stage surveys, whose costs can sometimes match those of actual construction in isolated rural zones. Despite this preparation, some terrain details may be misclassified or entirely overlooked. Even accurate maps cannot account for sudden developments, such as ownership disputes or revisions to land-use rules that alter route costs. A technique capable of producing several distinct network layouts with nearly identical total costs, therefore enables on-site teams to revise connections during detailed planning without major disruption. Standard A and its extensions, including MAA, are intentionally designed to return just one solution per query. For practical projects, an improved method would instead supply multiple routes of roughly equal cost, supporting necessary changes as new information surfaces.
The issue of unreliable input data appears across many infrastructure projects. One notable case involves a gas pipeline spanning several eastern U.S. states that faced intense opposition to one short segment in West Virginia [18] due to environmental objections that planners had not predicted. The lack of prepared, equally economical backup routes worsened the situation considerably.
This article introduces a combined path-search technique that pairs a specially adapted genetic algorithm — known for naturally generating groups of strong solutions — with fine-grained route computation via MAA. The hybrid produces a range of near-optimal network designs and greatly improves adaptability throughout project rollout. Relying on a single route leaves little room for adjustment; rushed redesigns under deadline pressure tend to increase expenses sharply and often result in noticeably weaker final configurations.
With a collection of near-optimal options available, two kinds of fast adaptation become practical: (a) swapping to an equivalent near-optimal route that joins the same nodes along different corridors, and (b) adopting an alternative near-optimal configuration that reconnects all nodes using entirely different pairings and corridors. These possibilities together form a complete multi-path solution consisting of (a) one primary near-optimal route, (b) a group of near-optimal routes yielding equivalent networks (identical in topology but different in geographic layout from the primary network), and (c) additional groups of near-optimal routes yielding alternative networks (different in both topology and geography from the primary network). Figure 4 presents a schematic overview of these families. Generally, moving to an equivalent network involves fewer changes and is therefore favored whenever possible.
Figure 4. Advantages of a multi-path solution, illustrated on a small network with four nodes. The graph on the left shows the family of near-optimal paths connecting the four nodes, leading to the preferred (typically lowest-cost) network. If other impediments are found during implementation, the field team may select different paths connecting the same nodes (upper right), or an alternative set of connections (lower right), all of which have similar costs.
To recap, the networked rural electrification framework first replaces classical A with MAA to accelerate precise route calculations. The contribution here extends that foundation by enabling the creation of route families, thereby offering adaptable solution sets that respond effectively to actual site conditions. At each stage, the final network is assembled from these near-optimal paths using the minimum spanning tree (MST) approach.
Genetic algorithms (GA) represent another possible method for locating optimal paths between node pairs on the test terrain. However, as later sections will clarify, GA typically cannot reach the same degree of optimality as A, MAA, or AMAA. The value of studying GA stems from its ability — once appropriately adjusted — to identify several solutions sharing similar cost levels. This section provides a brief overview of applying GA to pathfinding tasks.
Genetic algorithms [19, 20] serve as a popular tool for solving diverse optimization challenges. Implementation details vary widely according to the nature of the problem. This subsection outlines the adaptation of GA specifically for optimal path search.
Consistent with the formulation in our earlier papers [10, 11], the cost associated with the (i + 1)th step along any path is expressed as:
(1)
Where xi, yi, and hi denote the horizontal coordinates and elevation at the ith location, ai indicates the accessibility rating (reflecting construction difficulty at that spot due to existing land use, safety constraints, soil stability, and related factors) for the ith point shown on Figure 3, and w1 and w2 act as weighting coefficients. Available technology, machinery, material prices, labor rates, and other practical considerations determine these weights. For the calculations performed here, xi, yi ϵ {0,300}, hi ϵ {1, 2, 3}, ai ϵ {0, 3, 10}, w1 = 6 and w2 = 3.
The main aim of this pathfinding algorithm is to reduce the total ∑_{i=0}^P C_{i+1} as much as possible, where P stands for the total count of moves made across the individual grid cells of the map while following one complete route. A simple and easy-to-understand method for achieving this is shown in (Figure 5):
(a) Draw a direct straight line between the starting node and the ending node;
(b) Work out the starting cost of a route that follows this straight line;
(c) Create n random points close to that straight line and join them together to form one possible route;
(d) Work out the full cost of this newly formed route;
(e) Carry out steps (a) to (d) several times to build an initial collection of different routes, known as genotypes;
(f) Order all these generated routes from the highest cost down to the lowest;
(g) Pick only the top k routes from this ordered list;
(h) Run a genetic algorithm on these selected routes to discover a better solution by gradually mutating the group of k starting routes. Here, the crossover operation means exchanging a chosen point from one route with a point from another route, and mutation means shifting any single point in a route to a new random location.
Figure 5. Using a genetic algorithm to obtain an optimal path in this application.
While the A algorithm is free to create an optimal route that can take almost any possible form, a standard genetic algorithm builds its solution using precisely (n+1) straight-line pieces connected end to end. Because of this limitation, GA-generated routes usually have noticeably higher total costs than those generated by A or MAA. The reason is that paths built from straight segments joined together are seldom the most efficient choice inside a strongly direction-dependent cost field. Even so, when the squared Euclidean (R²) distance from the start node to the end node is quite large, the GA is good at spotting one or several rough but promising corridors made up of straight-line pieces. For example, it often avoids crossing zones that are especially difficult or expensive, or it finds a smart, low-cost way to reach the edge of an obstacle, such as a river or a mountain ridge. Afterwards, each of these straight segments can be handled separately with A or MAA (Figure 6). Since the segments are short, the search space for each one stays small, and the calculation stays manageable, except when the anisotropy becomes extremely severe [15].
Figure 6. GA+A hybridization scheme. In the upper panel, an approximate path consisting of a small number of straight-line segments is generated using a genetic algorithm (see text). In the lower panel, detailed routing is completed by applying A to these shorter segments. In a highly anisotropic environment, the computational power required by this method is significantly lower than that required to directly identify the optimal path between the start and end nodes using A.
In the current task, the value of n affects both the GA’s running cost and the overall process’s complexity. Raising n gives the algorithm a chance to examine more of the map and cuts down the work needed later for fine-scale routing. At the same time, it creates many poor-quality child routes that zigzag uselessly and perform poorly. Tests have shown that keeping n small—at 3 or 4 points—usually produces routes cheaper than the very first straight-line guess, but raising n above 7 tends to generate many routes whose costs are actually worse than the ones kept after step (g).
To illustrate the differences, Figure 7 shows the final route costs obtained using GA alone, the combined GA+A method, and pure A to achieve the absolute best possible route.
Figure 7. Resulting path cost from A (global optimum) compared to genetic algorithm (GA) and the hybrid algorithm with initial GA routing followed by MAA(1) detailed routing (GA+A). The GA route cost is 805, but the hybrid application of A to detailed routing reduces this to 452, a 45% savings. As expected, while neither method achieves the cost of the globally optimal (43% of GA), the GA+A produces near-optimal results (56% of GA). Note that the GA algorithm readily bypasses the high-cost area between the two endpoints; the A and MAA algorithms, in contrast, explore large sections of the total map to reach the same conclusion.
As anticipated, A delivers substantially superior performance compared with GA, while the hybrid approach falls somewhere in the middle. Interestingly, the GA outcome in this case matches the straightforward pole-placement technique illustrated in Figure 3. It is worth noting that the GA used here ran for 30 generations, and different runs with different random seeds can yield results of comparable quality. For further comparison, the path cost calculated with MAA(1) stands at 395, which again greatly outperforms the GA result (Figure 3).
These trials indicate that starting with a GA solution and then refining it locally through A, MAA, or AMAA yields solutions with reasonably low costs. Nevertheless, this strategy does not fully resolve the core issue raised previously: the hybrid technique still generates only one route, whereas a multi-path strategy is needed to handle inaccuracies in the input data or unforeseen conditions on the ground. To create such multi-path capability, the conventional GA has been altered by first clustering the starting paths (the genotypes) according to their spatial characteristics before running the evolutionary process. Interpolation has also been incorporated to expand the degrees of freedom and thereby improve the quality of the final solutions.
The fundamental concept behind producing multiple alternative routes is depicted in Figure 8. A set of rough but near-optimal corridors linking the two nodes is first generated via a “levelized” version of the GA and then finalized with detailed routing performed by the MAA algorithm. An additional improvement step (Figure 8) has been added to enhance the optimization’s flexibility and achieve even lower costs, bringing the outcomes closer to the true optimum. Before examining levelization and interpolation more closely, a key influence of anisotropy on GA behavior is reviewed.
Figure 8. Generating a near-optimal path in different zones by using GA and MAA. Routing around the high-cost region in the center of the map is challenging for the A and even MAA algorithms, but readily accomplished by the LIGA algorithm.
In the majority of GA applications, preserving a broad diversity of genotypes is generally recommended [19, 20]. Yet in certain problems with several distinct clusters of strong, near-optimal solutions, exchanging genetic material across those clusters rarely yields meaningful gains (though it cannot be entirely ruled out) [21, 22]. Moreover, such cross-cluster exchanges significantly increase computational demands. Observations from the present study show that GA-based pathfinding in environments with strong anisotropy encounters exactly this difficulty (Figure 9). Early in the selection process, the population tends to split into multiple separate clusters of near-optimal solutions. For instance, routes that detour to the right or left of a concentrated obstacle may incur similar total costs yet lie far apart geographically. In such situations, unrestricted crossover generates a large proportion of inferior paths — in the given example, paths that attempt to cut directly across the obstacle — which wastes processing time and lowers the chance of genuine improvement from one generation to the next. While crossover between genotypes belonging to Group 2 and Group 3 might occasionally create a usable new path by linking along the gray dotted line shown, crossover between genotypes in Group 1 and Group 4, for example, is very unlikely to produce any useful advance.
Figure 9. Genotype grouping.
If the genotypes can be deliberately clustered according to spatial closeness — measured in this work by their average distance from the straight line joining the start and end nodes — then running the GA independently on each cluster allows each group to evolve toward its own set of strong, locally near-optimal solutions. These separate clusters can subsequently be combined to form the desired output: a multi-path solution consisting of a family of good alternative routes.
Clearly, spatial proximity (or any other solitary measure) may not always be the best criterion for clustering. Although more advanced grouping techniques exist, most add significant computational overhead and are difficult to tune at the early planning stage when only sparse information is available. For the goals of this study, generating additional paths that are very close to already-discovered good routes matters less than producing a diverse family of near-optimal paths that span a wider geographic area and therefore offer practical alternatives during actual execution. Consequently, the proposed method employs the simple deviation distance from the straight line between the two nodes as the grouping metric, which it refers to as the “level.” Each level constitutes a separate subgroup of genotypes, with crossover restricted to occur only inside the same level. In implementation, the procedure consists of two main phases:
Step 1: Levelizing — broadly speaking, the method seeks to discover the dominant near-optimal solutions present in distinct zones Z_i, i = 1, 2, … n, where n is the number of solutions the user wishes to obtain. Although the current routing task is limited to three-dimensional space, the same principle can be extended to more general optimization tasks in higher dimensions. To locate a strong solution within a specific zone, only the starting genotypes in that zone are fed into the GA. The chosen metric is the average deviation (distance) of each genotype from the straight line connecting the start and end nodes. Alternatives such as cost-weighted distance or fuzzy classification rules could also serve as the metric, and the reference line could be chosen differently from a simple straight line. For this reason, the more general term “level” is used instead of “deviation” to describe the grouping criterion, and the overall clustering process is called “levelizing”.
Beginning from step (g) of the basic GA procedure, the k lowest-cost randomly created paths are sorted into levels. An illustration of this process appears in Figure 10, where the target configuration is a symmetric three-level index on both sides (i.e., +3, +2, +1, 0, -1, -2, -3), resulting in a total of 7 levels.
Figure 10. Assigning paths to levels.
In general, each level group will generate one or more rough but near-optimal solutions once the previously described genetic algorithm is applied, thereby creating a collection of geographically separated near-optimal paths. The final family of near-optimal paths is assembled by selecting solutions from every level. It is important to recognize that certain zones may carry such high costs that their paths cannot compete with those from other zones. Even so, the user may choose to keep solutions from these expensive zones when a greater routing variety is preferred.
Step 2: Interpolation – Before executing the GA, interpolation is introduced to expand the degrees of freedom. However, once the paths are divided into levels, the limited number of nodes limits the search for lower-cost options. Interpolation addresses this by inserting one extra node at the midpoint of every existing segment (Figure 11). Consequently, when n=3 is used to generate the random paths, the interpolation step yields 7 points for further processing. The genetic algorithm is then run on these enhanced paths.
Figure 11. Path interpolation.
After completion of the GA evolution, the refinement step using A, MAA, or AMAA — as outlined previously — is performed independently on the genotypes belonging to each level.
Referring to the map in Figure 3, Figure 12 presents sample LIGA results for linking the points (50, 60) and (250, 190). The plotted curves illustrate the actual shapes of the coarse near-optimal routes generated for levels −2, 0, and 2 after running the process for 30 generations.
Figure 12. Example GA outputs for three levels after levelization and interpolation.
Following the coarse routing phase with LIGA, fine-scale routing (for example, using A or MAA [10, 11]) is applied to polish the paths shown in Figure 12 (Figure 13). As discussed earlier, the efficiency of A and MAA depends heavily on the extent of the search area. By supplying MAA with a sequence of shorter routing segments — each limited to the immediate vicinity of a straight-line portion — the computational load for the detailed routing stage is greatly reduced. It should be noted, however, that the MAA algorithm is permitted to venture outside the bounding rectangle formed by the endpoints of any given straight-line segment.
Figure 13. LIGA-MAA hybridization for a family of paths.
When MAA(1) is employed to optimize the individual line segments, the costs for the three routes decrease as follows: (a) from 782 to 410 for level = −2, (b) from 959 to 498 for level = 0, and (c) from 973 to 552 for level = 2. These values move considerably closer to the global optimum of 349. As with any artificial intelligence technique, it is impossible to predict with certainty which approach will provide the closest approximation to the global optimum, since the error contributed by each algorithm varies with the degree of anisotropicity in the search space, which remains largely unpredictable in this setting.
Two separate test cases were examined to evaluate the effectiveness and stability of the hybrid technique. The first case fully demonstrates the calculations described above and connects (50, 60) to (250, 190). The second case links (20, 20) to (290, 190). These two examples represent typical scenarios in which (a) a single near-optimal solution tends to dominate and (b) several near-optimal solutions with comparable costs exist simultaneously. In both cases, the GA was executed with 30 and 100 generations, and 15 independent trials used different mutation rates and crossover rules. The same MAA configuration was applied for refining all paths.
Case 1 – connecting (50,60) and (250,190)
A key concern regarding this hybrid strategy is correspondence: do the highest-performing coarse routes generated by LIGA during the initial stage align with the strongest near-optimal routes obtained after MAA refinement? Because the highly anisotropic environment does not guarantee perfect alignment in every instance, the practical question is whether refining only a selected subset of LIGA routes through detailed routing can still yield a useful, compact set of near-optimal solutions.
Mathematically, consider the complete collection of LIGA outcomes
(2)
Ordered according to their costs. Each LIGA route can be further improved via detailed routing, producing a new set Γ = {γ1, γ2, … γN} of identical size that is no longer ordered, since the mapping λi → γi does not necessarily preserve the original ranking. This new set Γ is then sorted by increasing cost to obtain an ordered collection G = {g1, g2, … gL, … gN−1, gN} while preserving the overall mapping from the original LIGA routes to G. Clearly, it is not feasible to know beforehand which λ will transform into which g without actually performing the MAA calculations. In other words, the specific indices s and e in the relation λs → ge cannot be determined in advance. Nevertheless, it is sensible to expect a statistically positive correlation between the initial and final rankings in most situations, even under strong anisotropies.
In practice, performing detailed routing requires substantial computational resources. To address this, we selected a reduced set Λ̂ that includes only the M cheapest routes from Λ. We then applied detailed routing exclusively to this reduced set, which generated the corresponding collection of detailed paths denoted as Γ̂ = {γ1, γ2, …, γM}.
The effectiveness of the chosen value for M can be evaluated by determining what proportion of the lowest-cost detailed paths, represented by Ĝ = {g1, g2, …, gL}, appears within Γ̂. Here, L indicates the target number of alternative near-optimal solutions. Although Ĝ remains unknown in most real-world scenarios unless every possible element is calculated, it is still feasible to create an evaluation metric and validate it through a complete computation on a specific example. This allows us to gain a valuable understanding of how well the two sets correspond.
One suitable metric is given by:
(3)
Where N denotes the operator that counts the elements within a set, and the intersection operator ∩ preserves the mapping from Λ to G. Overall, the goal is to pick an M that brings Q as close to 1 as possible while staying within the project’s available computational limits.
Figure 14 presents the outcomes from a 30-generation GA process that was subsequently refined using MAA(1). These outcomes comprise 15 LIGA routes for each of the seven levels, along with 15 routes generated by a conventional GA approach. The conventional GA selects the top k genotypes without any level-based grouping (‘level=full’), yielding a total of 120 coarse routes. Given that the objective is to identify practical alternative routes, it is sufficient to obtain a reasonable quantity of high-quality routes. According to the figure, refining the top 25–30% of these 120 coarse routes would almost certainly meet the requirements. For an additional perspective, Figure 15 illustrates the relationship between the costs of the coarse routes and their refined counterparts.
Figure 14. Correspondence between LIGA output and refined routes, connection (50,60)–(250,190).
Figure 15. Correlation between coarse and refined routes.
It is worth noting that although refining 25–30% of the LIGA outputs is expected to yield a sufficient number of lower-cost routes, certain challenging zones—such as highly anisotropic regions or areas with very limited accessibility—might still be absent from the final refined set. An important characteristic of the proposed method is that routing through these zones tends to be expensive, so the resulting refined paths are generally less competitive than other options. Nevertheless, the user can keep a small number of routes from these zones as backup options for worst-case scenarios, while recognizing that alternative zones consistently offer lower costs.
As a concrete example, Table 1 and Figure 16 demonstrate a selection of alternative routes for the connection between (50,60) and (250,190). In this particular case, since every refined near-optimal route was fully computed (Figure 14), we selected the best refined near-optimal route from each zone purely for illustrative purposes. In actual applications, and based on the correspondence analysis described earlier, the user can limit the refinement process to only the best 25–30% of the LIGA outputs. The resulting smaller collection can then be used to build the final multi-path solution. Subsequent examples in this work follow this strategy. This specific case also highlights that two routes located far apart geographically can still possess comparable overall costs. Consequently, project teams maintain the ability to make substantial changes to the system routing, aware that paths located north or south of the high-cost area are likely to have similar estimated costs.
Table 1. Computation results using the hybrid method, G = 30, connection (50,60)-(250,190).
Method | Path cost |
MAA* with m = 1 | 395 |
Hybrid | |
No. of generation in LIGA/GA = 30 | |
level = −2 | 380 |
level = −1 | 392 |
level = 1 | 476 |
level = 2 | 528 |
traditional GA (level = full) | 411 |
Straight-line | 2620 |
Global minimum | 349 |
Figure 16. Actual path shapes using hybrid method, G = 30, connection (50,60)-(250,190).
It is widely recognized that the number of generations selected for a genetic algorithm influences the quality of the optimal solution [19]. Genotypes belonging to the same level tend to reach convergence more rapidly than when a GA is run on a comparable number of genotypes without separating them by level (i.e., the “level=full” case). As shown in Table 2 and Figure 17, the refined route cost in the level=full scenario (standard GA) improves by 6.3%, decreasing from 411 to 385 as the number of generations rises from 30 to 100. In contrast, for levels −2 and 2, increasing the generations produces no further improvement. Although these findings align with expected behavior, it must be emphasized that such heuristic observations cannot be formally proven. Additionally, because GA solutions are not unique, comparing the best result at each level alone is not entirely rigorous; however, it still provides useful guidance when deciding on the appropriate number of generations.
Table 2. Computation results using the hybrid method, G = 100, connection (50,60)-(250,190).
Method | Path cost |
Accelerated A* with m = 1 | 395 |
Hybrid | |
No. of generation in LIGA/GA = 100 | |
level = −3 | 407 |
level = −2 | 383 |
level =3 | 577 |
level = 2 | 541 |
traditional GA (level = full) | 385 |
Straight-line | 2620 |
Global minimum | 349 |
Figure 17. Actual path shapes using hybrid method, G = 100, connection (50,60)-(250,190).
Case 2 – connecting (20,20) and (290,290)
This particular connection covers a much longer distance compared with the previous example. Previous studies [10, 11, 15] have shown that A exhibits extremely slow convergence on long paths, as its time complexity grows exponentially with path length. While the considerably faster MAA algorithm [10, 11] substantially shortens the required processing time, it still demands 54 h on a standard i7 desktop computer running Windows. A notable strength of the proposed hybrid approach is its ability to handle the shorter path segments generated by LIGA quickly. However, producing suitable candidates for later MAA refinement also requires a non-negligible amount of time. Consequently, a direct head-to-head comparison of computational efficiency for locating one near-optimal route is not straightforward between the hybrid method and a pure MAA run.
As a rough benchmark, creating 120 coarse routes — including genotype generation, sorting, level assignment, and interpolation — to link (20,20) and (290,290) via LIGA consumed approximately 70 h with a 30-generation GA and 180 h with a 100-generation GA. The refinement time for each coarse route with MAA depends heavily on segment length and the level of terrain anisotropy, ranging from under 1 hour to several hours. Assuming an average refinement time of 3.5 h per coarse route with MAA(1), the hybrid method requires roughly 4.1 h in total to generate one full connection at 30 generations. This represents a clear improvement over the 54 h demanded by standalone MAA(1). Should the user elect to refine 25% of the LIGA outputs (that is, 30 coarse routes), the total runtime of the hybrid algorithm climbs to approximately 175 h. If we further assume that half of the refined outputs — equating to 15 routes — deliver sufficiently low costs to serve as viable alternatives (Figure 16), then the effective average computation time per usable refined route falls to about 11.7 h. Although these estimates remain approximate, they still provide meaningful guidance on the trade-offs between computational effort and solution quality when comparing the hybrid method against pure MAA. It should again be emphasized that the classical A* algorithm was unable to complete the routing task between these two points within a reasonable computation time.
Table 3 and Figure 18 summarize the computational outcomes obtained with G = 30 generations.
Table 3. Computation results using the hybrid method, G = 30, connection (20,20)-(290,290).
Method | Path cost |
Accelerated A*with m = 1 | 634 |
Hybrid | |
No. of generation in LIGA/GA = 30 | |
level = 2 | 712 |
level = 1 | 656 |
level = −2 | 684 |
level = −3 | 762 |
traditional GA (level = full) | 649 |
Straight-line | 3397 |
Accelerated A* with m = 0.5 | 615 |
Figure 18. Actual path shapes using hybrid method, G = 30, connection (20,20)-(290,290).
In this scenario, the most striking result is that the two lowest-cost paths delivered by the hybrid method (corresponding to index = 1 and index = full) are situated on the opposite side of the restricted zone relative to the near-optimal path produced by the standalone MAA(1) algorithm. By comparison, the refined route at level = −2 lies on the same side as the MAA(1) path, albeit with modest differences in its exact geometry. Nevertheless, the costs associated with these three hybrid routes stay closely aligned with the cost of the near-optimal end-to-end MAA(1) solution, even though they traverse entirely different regions of the map. This outcome underscores the strong value of adopting a multi-path solution, as it grants network designers considerable flexibility and the practical ability to swap routes in response to on-site implementation challenges.
After the complete family of near-optimal routes has been established, the minimum spanning tree (MST) can be used to determine the overall network layout. The detailed steps for this process are provided in Li et al. [11]. If the cost of any individual path rises unexpectedly due to changing field conditions, the MST algorithm will automatically select, based on overall network cost, either a replacement route drawn from the same family (thereby preserving an equivalent near-optimal network) or a more extensive reconfiguration of the network topology (Figure 4).
Drawing on the findings from the two detailed application cases (along with numerous additional tests conducted throughout the research), the hybrid strategy that integrates LIGA with MAA successfully delivers a practical multi-path solution. The top-ranked path generally achieves a cost close to that of a single MAA(1) run. The remaining paths may incur costs comparable to or slightly higher than those of the main path, depending on the terrain features. Overall, the approach achieves its main goal by generating several near-optimal routes, thereby mitigating risks commonly encountered in networked rural electrification initiatives.
A key benefit of this method is its ability to preserve flexibility for late-stage decisions while adding only minimal extra cost to the project. This enhanced robustness and reliability allow project teams to keep important options open. Satellite images and GIS software enable rapid map creation, network estimation, and evaluation of the economic benefits of a networked approach versus standalone village electrification. Lowering upfront planning expenses through such preliminary analysis is critical to determining whether networked rural electrification is appropriate for a given region. Moreover, because non-recurring engineering expenses typically account for the largest share of total costs in rural electrification, applying these techniques can meaningfully reduce overall project planning, initial routing, and preliminary budgeting costs. This, in turn, improves the chances of securing funding for village electrification schemes.
More broadly, the techniques introduced in this work could prove useful for other types of infrastructure development in environments with similar anisotropic characteristics. Potential areas include planning for gas and oil pipelines, designing trunk communication lines, and expanding transportation networks. These methods are especially relevant in situations where socio-political considerations — which are difficult to quantify in advance — can exert a major influence on final routing choices.
In real-world applications, a complete design must also incorporate electrical aspects of network configuration. Achieving this integration remains technically difficult during the early phases of a project. In the current model, cable capacity is handled in two separate stages. The present study focuses on the physical and geometric optimization of the network, accounting for construction, installation, deployment, and ongoing access costs. These factors typically outweigh the costs associated with selecting and pricing the actual cables. Once suitable routes have been identified, cable sizing and costing can be addressed afterward by applying CMST — an iterative form of the minimum spanning tree algorithm — to refine cable route selection [23].
Two promising directions for future research are identified:
a) The relationship between the costs of coarse near-optimal routes generated by LIGA and the refined near-optimal routes obtained after MAA processing is examined. Since the true cost of any coarse route is unknown until it undergoes MAA refinement, the existing procedure assumes that refining 25–30% of the LIGA outputs will retain a sufficient number of low-cost options. Although correlation studies indicate this assumption is generally sound, it would be advantageous to refine an even smaller fraction of LIGA outputs, provided that enough low-cost refined routes are still captured. Observations suggest that coarse routes from LIGA that converge quickly tend to show stronger cost agreement after MAA refinement, probably because they traverse areas with lower anisotropy. Therefore, in addition to the coarse route cost itself, the speed of convergence could potentially serve as an additional criterion for deciding which routes to refine.
b) The level metric employed in this study relies on a basic distance measure and uses discrete grouping. To speed up the algorithm, crossover operations between groups at different levels are currently prevented. Allowing selective crossover between certain genotypes might yield improved outcomes. Consequently, developing a more advanced metric (for instance, a fuzzy-based measure) could enable the identification of more valuable routes without sacrificing the rapid convergence rate.
As highlighted by the IEA, meeting SDG7 by 2030 is becoming increasingly difficult. The remaining unelectrified areas are typically more remote, topographically challenging, and harder to reach. Uncertainties in system planning and suboptimal use of energy resources further inflate electrification expenses. If current methods remain unchanged, the IEA estimates that 660 million people will still lack access to electricity by 2030.
To help overcome these challenges, we introduce a networked rural electrification framework that could significantly reduce electrification costs and thereby accelerate progress toward SDG7. Implementing this framework requires computational support to determine line routes efficiently, yet traditional algorithms struggle due to the highly anisotropic nature of the search space. Earlier research led to the creation of two much faster algorithms — MAA and AMAA — that accelerate preliminary network design using satellite imagery and digital elevation models. However, such initial designs often face difficulties arising from inaccuracies in satellite data and GIS analysis, as well as unforeseen site conditions, land-rights conflicts, shifts in land-use policies, or other external factors.
This paper presents the LIGA method and demonstrates its combination with MAA to strengthen the robustness of the networked rural electrification model. Thanks to this enhancement, decision-makers can quickly, cost-effectively, and reliably assess the suitability of the networked approach for their specific context.
None
None
None
None
Open Access The author(s) retain copyright. This article is licensed under the Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License. It may be shared and adapted for non-commercial purposes with appropriate attribution, an indication of changes, and distribution of adaptations under the same license. Third-party material may be subject to separate terms identified in its credit line. View the license at https://creativecommons.org/licenses/by-nc-sa/4.0/.
Institute of Smart Energy Systems Press
