The Uncertain Capacitated Arc Routing Problem (UCARP) presents unique challenges in real-world applications such as waste collection and winter gritting, where task demands and service costs are stochastic. Although Genetic Programming Hyper-Heuristics (GPHH) have demonstrated strong adaptability to such uncertainties by evolving dynamic routing policies, their complex decision-making processes hinder interpretability. To address this, a novel framework called Differential Evolution with Random Ablation (DERA) is introduced to generate diverse and feasible counterfactual explanations. Unlike traditional methods, DERA systematically explores multiple counterfactual scenarios by integrating random ablation into the optimisation process, thereby uncovering a broader range of plausible alternatives. Experimental results across various UCARP instances show that DERA consistently achieves high feasibility, minimal feature changes, and greater diversity in counterfactual explanations compared to baseline methods. This diversity enables a more comprehensive understanding of GPHH-evolved policies, providing actionable insights to improve decision-making transparency and robustness in dynamic environments.

The computing power network links distributed and heterogeneous computing resources via the network, to enable efficient configuration and utilization of computing power. However, scheduling computing resources within this network presents several challenges, such as resource heterogeneity, vast search spaces, uncertainty, high constraints, and real-time requirements. To simulate the real-world computing power network scheduling problem, this paper integrates cloud servers, fog servers, and edge servers into a unified computing power network, considering their respective GPU, CPU, and bandwidth resources. We introduce a Dual-Tree Genetic Programming (DTGP) approach that simultaneously optimizes two critical decisions—routing and sequencing—to automatically evolve computing power network scheduling heuristics for real-time decision-making. Additionally, to improve the performance of DTGP, we propose new terminal sets tailored to fit within these two GP trees. Experimental results demonstrate that the proposed method significantly outperforms existing state-of-the-art methods in six test scenarios, achieving up to 40% reduction in completion time.

Electric vehicle charging stations (EVCSs) have become a pivotal infrastructure within the electric vehicle (EV) industry. In particular, many EV companies construct self-owned EVCSs to provide better charging service for their customers. For these self-owned EVCSs, to ensure the quality of service for self-owned users and third-party users, dynamic pricing based on the time-of-use (TOU) strategy has been extensively employed. This makes the demand forecasting of EVCSs important since it depicts the relationship between the charging price and the demand of an EVCS. Unfortunately, the existing techniques cannot accurately predict the demand of multiple users simultaneously. Consequently, this article examines the problem of multidemand forecasting of EVCSs, and proposes an efficient method to resolve this issue. The key insight of the proposed method is to train a deep neural network consisting of two subnetworks that can jointly forecast the demand of the self-owned user and the third-party user simultaneously. First, six kinds of features of EVCSs are extracted. Then, a novel deep neural network Atlas based on the attention mechanism is proposed to forecast the multidemand of EVCSs under the TOU strategy. Finally, to resolve the scarcity of historical charging demand data, a coarse-fine training process is proposed to train Atlas for each EVCS. The evaluation based on the real-world dataset of 771 EVCSs from an EV company demonstrates that Atlas significantly outperforms seven state-of-the-art techniques by up to 34.82%$\sim ~61.92$%.

Genetic programming has been successfully used to evolve routing policies that can make real-time routing decisions for uncertain arc routing problems. Although the evolved routing policies are highly effective, they are typically very large and complex, and hard to be understood and trusted by real users. Existing studies have attempted to improve the interpretability by developing new genetic programming approaches to evolve both effective and interpretable (e.g., with smaller program size) routing policies. However, they still have limitations due to the trade-off between effectiveness and interpretability. To address this issue, we propose a new post-hoc explanation approach to explaining the effective but complex routing policies evolved by genetic programming. The new approach includes a local ranking explanation and a global explanation module. The local ranking explanation uses particle swarm optimisation to learn an interpretable linear model that accurately explains the local behaviour of the routing policy for each decision situation. Then, the global explanation module uses a clustering technique to summarise the local explanations into a global explanation. The experimental results and case studies on the benchmark datasets show that the proposed method can obtain accurate and understandable explanations of the routing policies evolved for uncertain arc routing problems. Our explanation approach is not restricted to uncertain arc routing, but has a great potential to be generalised to other optimisation and machine learning problems such as learning classifier systems and reinforcement learning.

The uncertain capacitated arc routing problem (UCARP) is an important combinatorial optimization problem with many applications in the real world. Genetic programming hyper-heuristic has been successfully used to automatically evolve routing policies, which can make real-time routing decisions for UCARPs. It is desired to evolve routing policies that are both effective and small/simple to be easily understood. The effectiveness and size are two potentially conflicting objectives. A further challenge is the objective selection bias issue, i.e., it is much more likely to obtain small but ineffective routing policies than the effective ones that are typically large. In this article, we propose a new multiobjective genetic programming algorithm to evolve effective and small routing policies. The new algorithm employs the α dominance strategy with a newly proposed α adaptation scheme to address the objective selection bias issue. In addition, it contains a new archive strategy to prevent the loss of promising individuals due to the rotation of training instances. The experimental results showed that the newly proposed algorithm can evolve significantly better routing policies than the current state-of-the-art algorithms for UCARP in terms of both effectiveness and size. We have also analyzed the evolved routing policies to show better interpretability.

The Uncertain Capacitated Arc Routing Problem (UCARP) is a well-known combinatorial optimisation problem that has many real-world applications. Genetic Programming is usually utilised to handle UCARP by evolving effective routing policies, which can respond to the uncertain environment in real-time. Previous studies mainly focus on the effectiveness of the routing policies but ignore the interpretability. In this paper, we focus on post-hoc interpretability, which explains a pre-trained complex routing policy. Unlike the existing explanation methods for classification/regression models, the behaviour of a routing policy is characterised as a ranking process rather than predicting a single output. To address this issue, this paper proposes a Local Ranking Explanation (LRE) method for GP-evolved routing policies for UCARP. Given a UCARP decision situation, LRE trains a linear model that gives the same ranks of the candidate tasks as those of the explained routing policy. The experimental results demonstrate that LRE can obtain more interpretable linear models that have highly correlated and consistent behaviours with the original routing policy in most decision situations. By analysing coefficients and attribute importance of the linear model, we managed to provide a local explanation of the original routing policy in a decision situation.

The uncertain capacitated arc routing problem is an important optimization problem with many real-world applications. Genetic programming is considered a promising hyper-heuristic technique to automatically evolve routing policies that can make effective real-time decisions in an uncertain environment. Most existing research on genetic programming hyper-heuristic for the uncertain capacitated arc routing problem only focused on the test performance aspect. As a result, the routing policies evolved by genetic programming are usually too large and complex, and hard to comprehend. To evolve effective, smaller, and simpler routing policies, this article proposes a novel genetic programming approach, which simplifies the routing policies during the evolutionary process using a niching technique. The simplified routing policies are stored in an external archive. We also developed new elitism, parent selection, and breeding schemes for generating offspring from the original population and the archive. The experimental results show that the newly proposed approach can achieve significantly better test performance than the current state-of-the-art genetic programming algorithms for the uncertain capacitated arc routing problem. The evolved routing policies are smaller, and thus potentially more interpretable.

The Uncertain Capacitated Arc Routing Problem (UCARP) has a variety of real-world applications. Genetic Programming Hyper-heuristic (GPHH) is considered a promising technique to handle UCARP. Many scholars have shown the power of GPHH of evolving effective routing policies. However, the size of the evolved routing policies is ignored. Typically, smaller routing policies can have better interpretability and generalisation. Thus, it is necessary to optimise the size along with the effectiveness. The objective selection bias issue arises as the size is much easier to be optimised than effectiveness. The Pareto front is biased to the size gradually during the evolutionary process. To address this issue, we develop an α dominance criteria based Multi-Objective GP with a self-adaptive α scheme (αMOGP-sa). The basic idea of the α dominance criteria is to set tradeoff rates between objectives. For different instances, the search space can be very different. In this case, the self-adaptive α scheme is employed to automatically tuning the α value during the evolutionary process so that we can identify a valid α value for different instances. This paper examines the proposed algorithm in eight different problem instances. The experimental results showed that αMOGP-sa could effectively handle the objective selection bias issue, and evolve much better Pareto front on Hyper-Volume and Inverted Generational Distance than the current state-of-the-art MOGP approach for UCARP in terms of effectiveness and size on all instances. Also, αMOGP-sa can evolve much smaller routing policies than the state-of-art single-objective GPHH without sacrificing effectiveness.

Genetic Programming Hyper-Heuristic (GPHH) is a promising technique to automatically evolve effective routing policies to handle the uncertain environment in the Uncertain Capacitated Arc Routing Problem (UCARP). Previous studies mainly focus on the effectiveness of the evolved routing policies, but the size is ignored. This paper aims to develop new GPHH methods to optimise the effectiveness and the size simultaneously. There are two challenges. First, it is much easier for GP to generate small but ineffective individuals than effective ones, thus the search can be easily stuck with small but ineffective individuals. Second, the effectiveness evaluation in GPHH is stochastic, making it challenging to identify and retain effective individuals. To address these issues, we develop a Two-Stage Multi-Objective GP algorithm with Archive (TSNSGPII-a). The two-stage framework addresses the bias towards the size. The external archive stores potentially effective individuals that may be lost during the evolution, and reuses them to generate offspring. The experimental results show that TSNSGPII-a can obtain significantly better routing policies than the existing state-of-the-art approaches in terms of both effectiveness and size. If selecting the most effective routing policy from the Pareto front, TSNSGPII-a can obtain significantly smaller routing policies with statistically comparable or significantly better effectiveness.

The Uncertain Capacitated Arc Routing Problem (UCARP) is a very important problem which has many real world applications. Genetic Programming Hyper-heuristic (GPHH), which can automatically evolve effective routing policies, is considered as a promising technique that can handle UCARP effectively. However, GP-evolved routing policies are often very complex and hard to be understood and trusted by human users. In this paper, we aim to improve the interpretability of the GP-evolved routing policies by reducing the size of the GP-evolved routing policies since smaller routing policies tend to be easier to understand. We propose a new Multi-Objective GP (MOGP) to optimise the performance (total cost) and size simultaneously. One main challenge is that the size is much easier to be optimised than the performance. Thus, the population tends to be biased to the small but poor routing policies and quickly lose the ability of exploration. To address this issue, we propose a MOGP approach with α dominance strategy (α-MOGP) which can balance the tradeoff between performance and individual size. The experimental results showed that α-MOGP could obtain much smaller routing policies than the state-of-the-art single-objective GPHH, without deteriorating the performance. Compared with traditional MOGP, α-MOGP can obtain a much better and more widespread Pareto front.

The Uncertain Capacitated Arc Routing Problem (UCARP) is an important problem with many real-world applications. A major challenge in UCARP is to handle the uncertain environment effectively and reduce the recourse cost upon route failures. Genetic Programming Hyper-heuristic (GPHH) has been successfully applied to automatically evolve effective routing policies to make real-time decisions in the routing process. However, most existing studies obtain a single complex routing policy which is hard to interpret. In this paper, we aim to evolve an ensemble of simpler and more interpretable routing policies than a single complex policy. By considering the two critical properties of ensemble learning, i.e., the effectiveness of each ensemble element and the diversity between them, we propose two novel ensemble GP approaches namely DivBaggingGP and DivNichGP. DivBaggingGP evolves the ensemble elements sequentially, while DivNichGP evolves them simultaneously. The experimental results showed that both DivBaggingGP and DivNichGP could obtain more interpretable routing policies than the single complex routing policy. DivNichGP can achieve better test performance than DivBaggingGP as well as the single routing policy evolved by the current state-of-the-art GPHH. This demonstrates the effectiveness of evolving both effective and interpretable routing policies using ensemble learning.